2023西湖论剑部分密码题Writeup

虽然只做了两道格的。

MyErrorLearn·

题目：MyErrorLearn.py（代码的main.py）

题目代码不长，大概意思是，可以访问两次 X妮Oracle （三次留一次提交secret所以是两次），每次返回d和r，其中$d \equiv (s+r)^{-1} - r' \pmod p$，$p$是1024 bits，$r'$是246 bits，两次访问后可以获得$d_1$、$d_2$、$r_1$、$r_2$，目标是求出$s$。

首先，若知道$r_1'$或者$r_2'$就可求出$s$，可以简单推导一下（虽然下面exp用了另一种更复杂的方法，但是我懒得改了就直接贴了）：

$$\begin{aligned} d &\equiv (s+r)^{-1} - r' \\ (d + r') (s + r) &\equiv 1 \\ (d + r') s &\equiv 1 - (d + r') r \\ s &\equiv (1 - (d + r') r) (d + r')^{-1} \\ s &\equiv (d + r')^{-1} - r \pmod p \end{aligned}$$

所以可以吧问题转化为求$r_1'$或者$r_2'$。而观察可得$r_1'$、$r_2'$与$p$相比都是“小”的，所以自然会想到用格的方法（这个可能需要经验），而格的方法中由于Coppersmith的式子推导比较简单、可以直接调现成的代码、而且一般（或许是指单条式子？）情况下比普通格的方法效果更好，所以可以先考虑Coppersmith。

下面作简单的式子推导。首先已知的关系是

$$d_1 \equiv (s+r_1)^{-1} - r_1' \pmod p \\ d_2 \equiv (s+r_2)^{-1} - r_2' \pmod p$$

如果单用一条式子会遇到一个问题，就$s$是“大”的、不能被Coppersmith解出的未知数，所以要想方法消去，消去的方法也不难，就是联立两个方程：

$$\begin{aligned} (d_1 + r_1') (s + r_1) &\equiv (d_2 + r_2') (s + r_2) \\ (d_1 + r_1') s + (d_1 + r_1') r_1 &\equiv (d_2 + r_2') s + (d_2 + r_2') r_2 \\ (d_1 + r_2 - d_2 - r_2) s &\equiv (d_2 + r_2') r_2 - (d_1 + r_1') r_1 \pmod p \end{aligned}$$

由于题目的$p$并不是取素数，所以为了避免求逆的问题会绕一点弯（虽然其实多试几次也可以避免，不过还是尽量完美一点），为了方便，姑且设（注意都没含$s$）：

$$\begin{aligned} s_1 &\equiv (d_2 + r_2') r_2 - (d_1 + r_1') r_1 \pmod p \\ s_2 &\equiv (d_1 + r_2 - d_2 - r_2) \pmod p \end{aligned}$$

把$s_2 · s \equiv s_1 \pmod p$的关系代回$(d_1 + r_1') (s + r_1) \equiv 1 \pmod p$以消去$s$：

$$\begin{aligned} s_2 (d_1 + r_1') (s + r_1) &\equiv s_2 \\ (d_1 + r_1') (s_1 + s_2r_1) &\equiv s_2 \\ (d_1 + r_1') (s_1 + s_2r_1) - s_2 &\equiv 0 \pmod p \end{aligned}$$

最后推出来的式子就是Coppersmith需要的式子（见exp），直接调二元（因为未知数是$r_1'$和$r_2'$所以要二元）解出$r_1'$和$r_2'$，然后代入求出$s$，代码是用$s \equiv s_1 s_2^{-1} \pmod p$求的$s$，也可作参考。

PS：exp的交互用的是pwntools（我也不知道一个搞密码的为什么会有这个东西，逃），直接用pip只会安装到Python中，所以需要用Sage调用pip安装，命令：

sage -pip install pwntools --user

PPS：exp中remote应该替换为题目给的nc地址，为了方便调试我用ncat开了个本地的服务，命令：

ncat -vc 'python ./main.py' -kl 127.0.0.1 9006

EXP：

# Sage

# https://github.com/defund/coppersmith/blob/master/coppersmith.sage
load('copper.sage')
# sage -pip install pwntools --user
from pwn import *

# ncat -vc 'python ./main.py' -kl 127.0.0.1 9006
rmo = remote('127.0.0.1', 9006)

rmo.readuntil(b'> mod = ')
p = Integer(rmo.readline())
print(p)

rmo.sendline(b'1')
rmo.readuntil(b'> r = ')
r1 = Integer(rmo.readline())
rmo.readuntil(b'> d = ')
d1 = Integer(rmo.readline())
print(r1, d1)

rmo.sendline(b'1')
rmo.readuntil(b'> r = ')
r2 = Integer(rmo.readline())
rmo.readuntil(b'> d = ')
d2 = Integer(rmo.readline())
print(r2, d2)

P.<r1_, r2_> = PolynomialRing(Zmod(p))
s1 = ((d2 + r2_) * r2 - (d1 + r1_) * r1)
s2 = (d1 + r1_ - d2 - r2_)
bounds = [2^246, 2^246]

f = (d1 + r1_) * (s1 + s2 * r1) - s2
res = small_roots(f, bounds)
print(res)

r1_, r2_ = res[0]
s1 = ((d2 + r2_) * r2 - (d1 + r1_) * r1)
s2 = (d1 + r1_ - d2 - r2_)
s = s1 * Integer(s2).inverse_mod(p) % p
print(s)

rmo.sendline(b'2')
rmo.sendline(bytes(str(s), encoding='utf-8'))

rmo.interactive()
rmo.close()

PPPS：更多的Coppermith资料可以参考之前的文章

MyErrorLearnTwice·

题目：MyErrorLearnTwice.py（代码的main.py）

上一题的魔改，把$r'$换成328 bits，不能直接用Coppersmith解，但是 X妮Oracle 可以访问15次（同样留一次提交flag）。$r'$虽然变大了，单跟$p$相比仍然是“小”的，所以也优先考虑格的方法，直觉上这么多次Oracle的访问有点像藏数问题（HNP），下面按HNP的方向构造式子。

首先把第一次访问Oracle的输出作为“基准”，姑且先记作$d_x$和$r_x$，根据上一题推导的

$$(d_1 + r_1') (s_1 + s_2r_1) - s_2 \equiv 0 \pmod p$$

可以得到关系（$i = 0, 1, ..., n-1$）：

$$\begin{aligned} (d_i + r_i') ( (d_x + r_x') r_i - (d_i +r_i') r_x + (d_i + r_i' -d_x - r_x') r_i ) - (d_i + r_i' -d_x -r_x') &\equiv 0 \\ (d_i + r_i') (d_x r_x + r_x' r_x - d_i r_i - r_i' r_i + d_i r_i + r_i' r_i - d_x r_i -r_x' r_i) - (d_i + r_i' -d_x -r_x') &\equiv 0 \\ (d_i + r_i') (d_x r_x + r_x' r_x - d_x r_i -r_x' r_i) - (d_i + r_i' -d_x -r_x') &\equiv 0 \\ d_i d_x (r_x - r_i) + d_i (r_x - r_i) r_x' + d_x (r_x - r_i) r_i' + (r_x - r_i) r_x' r_i' - d_i - r_i' + d_x + r_x' &\equiv 0 \\ (d_i(r_x - r_i) + 1) r_x' + (d_x (r_x - r_i) - 1) r_i' + (r_x - r_i) r_x' r_i' + (d_x - d_i + d_i d_x (r_x - r_i)) &\equiv 0 \pmod p \end{aligned}$$

下面为了简化，姑且先记：

$$\begin{aligned} A_i &\equiv d_i(r_x - r_i) + 1 \pmod p \\ B_i &\equiv d_x (r_x - r_i) - 1 \pmod p \\ C_i &\equiv r_x - r_i \pmod p \\ D_i &\equiv d_x - d_i + d_i d_x (r_x - r_i) \pmod p \end{aligned}$$

那就是

$$A_i r_x' + B_i r_i' + C_i r_x' r_i' + D_i \equiv 0 \pmod p$$

接下来需要把$r_i'$孤立出来放在等号右边（因为$r_i'$是”小“的），然后展开模数，最终结果是：

$$B_i^{-1} A_i r_x' + B_i^{-1} C_i r_x' r_i' + B_i^{-1} D_i - k_i p = -r_i'$$

有了这个式子已经可以构造格了，构造结果不唯一，下面画一下我构造的（其中$R=2^{328}$，起”配平“作用）：

$$L = \begin{bmatrix} \begin{array}{lll|lll|ll} -p R & & & & & & & & \\ & \ddots & & & & & & & \\ & & -p R & & & & & & \\ \hline B_0^{-1} C_0 R & & & 1 & & & & & \\ & \ddots & & & \ddots & & & & \\ & & B_{n-1}^{-1} C_{n-1} R & & & 1 & & & \\ \hline B_0^{-1} A_0 R & \cdots & B_{n-1}^{-1} A_{n-1} R & & & & R & & \\ B_0^{-1} D_0 R & \cdots & B_{n-1}^{-1} D_{n-1} R & & & & & R^2 & \\ \end{array} \end{bmatrix}_{(2n+2)*(2n+2)}$$

构造出来的关系是：

$$\begin{aligned} v·L &= (k_0, ..., k_{n-1}, | r_x' r_0', ..., r_x' r_{n-1}', | r_x', 1 ) · L \\ &= (-r_0 R, ..., -r_{n-1} R, | r_x' r_0', ..., r_x' r_{n-1}', | r_x' R, R^2) = w \end{aligned}$$

粗略计算（相关知识点在一篇很久远而且挺乱的文章）：

$$\begin{aligned} \|w\| &≈ 2^{2*328} \\ \sigma(L) &≈ 2^{\frac{(1024+328+1)n + 3*328}{2n + 2}} \end{aligned}$$

若$\|w\| < \sigma(L)$即：

$$\begin{aligned} 2*328 &< \frac{(1024+328+1)n + 3*328}{2n + 2} \\ 4*328 (n+1) &< (1024+328+1)n + 3*328 \\ 4*328 n + 328 &< (1024+328+1)n \\ n &> \frac{328}{1024+328+1 - 4*328} = \frac{328}{41} = 8 \end{aligned}$$

算上”基准“的获取，总共访问10次Oracle就足够了，不过把15次全用完问题也不大。

最后就是LLL解出$r'$代入求出$s$。

EXP：

# Sage

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            if BB[ii, jj] == 0:
                a += ' '
            else:
                a += 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

from pwn import *
rmo = remote('127.0.0.1', 9006)

rmo.readuntil(b'> mod = ')
p = Integer(rmo.readline())
print(p)

rmo.sendline(b'1')
rmo.readuntil(b'> r = ')
rx = Integer(rmo.readline())
rmo.readuntil(b'> d = ')
dx = Integer(rmo.readline())
print(rx, dx)

n = 14
r = []
d = []
for i in range(n):
  rmo.sendline(b'1')
  rmo.readuntil(b'> r = ')
  r += [Integer(rmo.readline())]
  rmo.readuntil(b'> d = ')
  d += [Integer(rmo.readline())]
  print(r[-1], d[-1])

R = 2^328
Mt = matrix(ZZ, 2*n+2)
for i in range(n):
  Ai = (d[i] * (rx - r[i]) + 1) % p
  Bi = (dx * (rx - r[i]) - 1) % p
  Ci = (rx - r[i]) % p
  Di = (d[i] - dx - d[i] * dx * (rx - r[i])) % p

  Bii = Bi.inverse_mod(p)
  AA = (Bii * Ai) % p
  BB = (Bii * Ci) % p
  CC = (Bii * Di) % p

  Mt[i,   i]   = -p * R
  Mt[n+i, i]   = BB * R
  Mt[n+i, n+i] = 1
  Mt[-2,  i]   = AA * R
  Mt[-1,  i]   = CC * R
Mt[-2, -2] = R
Mt[-1, -1] = R^2

matrix_overview(Mt)
#L = Mt.BKZ()
L = Mt.LLL()
print(L[0])

for i in range(n):
  try:
    assert L[0][i] % R == 0
    ri_ = abs(L[0][i] // R)
    #s = (-1 + r[i] * Integer(d[i] + ri_).inverse_mod(p)) % p
    s = (Integer(d[i] + ri_).inverse_mod(p) - r[i]) % p
  except:
    print('?%d' % i)
    continue
  print()
  print(s)

  rmo.sendline(b'2')
  rmo.sendline(bytes(str(s), encoding='utf-8'))
  break

rmo.interactive()
rmo.close()

LockByLock·

题目：LockByLock.py（代码的main.py）

这题其实没做完，赛后才知道Pollard’s kangaroo algorithm可以直接解，原来wiki上有，怪不得这么多解（逃

首先有一个知识点是，若$a b>n$且知道$a$、$b$、$a \pmod n$和$b \pmod n$，那么就有

$$k_a n = a - (a \pmod n) \\ k_b n = b - (b \pmod n)$$

于是通过计算

$$\rm{gcd}(a - (a \pmod n), b - (b \pmod n)) = \rm{gcd}(k_a n, k_b n) = \rm{gcd}(k_a, k_b) · n$$

就有机会恢复$n$.

类似地，若知道$a \pmod n$、$b \pmod n$、$a^2 \pmod n$和$b^2 \pmod n$，也可以通过

$$\rm{gcd}((a \pmod n)^2 - a^2 \pmod n, (b \pmod n)^2 - b^2 \pmod n)$$

尝试恢复$n$。

贴一个当时获取$n$的EXP：

# Sage

from pwn import *
#context.log_level = 'debug'
rmo = remote('127.0.0.1', 9006)

rmo.readuntil(b'Alice: locked msg1 = ')
fm1 = Integer(rmo.readline())
rmo.readuntil(b'Bob: locked msg2 = ')
fm2 = Integer(rmo.readline())
rmo.readuntil(b'Alice: unlocked msg3 = ')
fm3 = Integer(rmo.readline())
rmo.readuntil(b'Bob: lock lock, unlock lock!')

o = 2
o2 = o^2

rmo.sendline(bytes(str(o), encoding='utf-8'))
rmo.readuntil(b'Alice: locked msg1 = ')
om1 = Integer(rmo.readline())
rmo.readuntil(b'Bob: locked msg2 = ')
om2 = Integer(rmo.readline())
rmo.readuntil(b'Alice: unlocked msg3 = ')
om3 = Integer(rmo.readline())
rmo.readuntil(b'Bob: lock lock, unlock lock!')
print('Debug > om1 = %d' % om1)
print('Debug > om2 = %d' % om2)
print('Debug > om3 = %d' % om3)

rmo.sendline(bytes(str(o2), encoding='utf-8'))
rmo.readuntil(b'Alice: locked msg1 = ')
o2m1 = Integer(rmo.readline())
rmo.readuntil(b'Bob: locked msg2 = ')
o2m2 = Integer(rmo.readline())
rmo.readuntil(b'Alice: unlocked msg3 = ')
o2m3 = Integer(rmo.readline())

n = gcd(om1^2 - o2m1, om3^2 - o2m3)
if len(bin(n))-2 > 2048:
  if n % 2 == 0:
    n //= 2
  if n % 3 == 0:
    n //= 3
# if ...
assert len(bin(n))-2 == 2048
print('Debug > n = %d' % n)
rmo.close()


# TODO: cai
# https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_chosen_plain_cipher/

总结·

菜