虽然只做了两道格的。

MyErrorLearn·

题目:MyErrorLearn.py(代码的main.py

题目代码不长,大概意思是,可以访问两次 X妮Oracle (三次留一次提交secret所以是两次),每次返回dr,其中d(s+r)1r(modp)d \equiv (s+r)^{-1} - r' \pmod ppp是1024 bits,rr'是246 bits,两次访问后可以获得d1d_1d2d_2r1r_1r2r_2,目标是求出ss

首先,若知道r1r_1'或者r2r_2'就可求出ss,可以简单推导一下(虽然下面exp用了另一种更复杂的方法,但是我懒得改了就直接贴了):

d(s+r)1r(d+r)(s+r)1(d+r)s1(d+r)rs(1(d+r)r)(d+r)1s(d+r)1r(modp)\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}

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

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

d1(s+r1)1r1(modp)d2(s+r2)1r2(modp)d_1 \equiv (s+r_1)^{-1} - r_1' \pmod p \\ d_2 \equiv (s+r_2)^{-1} - r_2' \pmod p

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

(d1+r1)(s+r1)(d2+r2)(s+r2)(d1+r1)s+(d1+r1)r1(d2+r2)s+(d2+r2)r2(d1+r2d2r2)s(d2+r2)r2(d1+r1)r1(modp)\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}

由于题目的pp并不是取素数,所以为了避免求逆的问题会绕一点弯(虽然其实多试几次也可以避免,不过还是尽量完美一点),为了方便,姑且设(注意都没含ss):

s1(d2+r2)r2(d1+r1)r1(modp)s2(d1+r2d2r2)(modp)\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}

s2ss1(modp)s_2 · s \equiv s_1 \pmod p的关系代回(d1+r1)(s+r1)1(modp)(d_1 + r_1') (s + r_1) \equiv 1 \pmod p以消去ss

s2(d1+r1)(s+r1)s2(d1+r1)(s1+s2r1)s2(d1+r1)(s1+s2r1)s20(modp)\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),直接调二元(因为未知数是r1r_1'r2r_2'所以要二元)解出r1r_1'r2r_2',然后代入求出ss,代码是用ss1s21(modp)s \equiv s_1 s_2^{-1} \pmod p求的ss,也可作参考。

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

1
sage -pip install pwntools --user

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

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

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 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

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

首先把第一次访问Oracle的输出作为“基准”,姑且先记作dxd_xrxr_x,根据上一题推导的

(d1+r1)(s1+s2r1)s20(modp)(d_1 + r_1') (s_1 + s_2r_1) - s_2 \equiv 0 \pmod p

可以得到关系(i=0,1,...,n1i = 0, 1, ..., n-1):

(di+ri)((dx+rx)ri(di+ri)rx+(di+ridxrx)ri)(di+ridxrx)0(di+ri)(dxrx+rxrxdiririri+diri+riridxrirxri)(di+ridxrx)0(di+ri)(dxrx+rxrxdxrirxri)(di+ridxrx)0didx(rxri)+di(rxri)rx+dx(rxri)ri+(rxri)rxridiri+dx+rx0(di(rxri)+1)rx+(dx(rxri)1)ri+(rxri)rxri+(dxdi+didx(rxri))0(modp)\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}

下面为了简化,姑且先记:

Aidi(rxri)+1(modp)Bidx(rxri)1(modp)Cirxri(modp)Didxdi+didx(rxri)(modp)\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}

那就是

Airx+Biri+Cirxri+Di0(modp)A_i r_x' + B_i r_i' + C_i r_x' r_i' + D_i \equiv 0 \pmod p

接下来需要把rir_i'孤立出来放在等号右边(因为rir_i'是”小“的),然后展开模数,最终结果是:

Bi1Airx+Bi1Cirxri+Bi1Dikip=riB_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=2328R=2^{328},起”配平“作用):

L=[pRpRB01C0R1Bn11Cn1R1B01A0RBn11An1RRB01D0RBn11Dn1RR2](2n+2)(2n+2)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)}

构造出来的关系是:

vL=(k0,...,kn1,rxr0,...,rxrn1,rx,1)L=(r0R,...,rn1R,rxr0,...,rxrn1,rxR,R2)=w\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}

粗略计算(相关知识点在一篇很久远而且挺乱的文章):

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

w<σ(L)\|w\| < \sigma(L)即:

2328<(1024+328+1)n+33282n+24328(n+1)<(1024+328+1)n+33284328n+328<(1024+328+1)nn>3281024+328+14328=32841=8\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解出rr'代入求出ss

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# 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上有,怪不得这么多解(逃

首先有一个知识点是,若ab>na b>n且知道aabba(modn)a \pmod nb(modn)b \pmod n,那么就有

kan=a(a(modn))kbn=b(b(modn))k_a n = a - (a \pmod n) \\ k_b n = b - (b \pmod n)

于是通过计算

gcd(a(a(modn)),b(b(modn)))=gcd(kan,kbn)=gcd(ka,kb)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

就有机会恢复nn.

类似地,若知道a(modn)a \pmod nb(modn)b \pmod na2(modn)a^2 \pmod nb2(modn)b^2 \pmod n,也可以通过

gcd((a(modn))2a2(modn),(b(modn))2b2(modn))\rm{gcd}((a \pmod n)^2 - a^2 \pmod n, (b \pmod n)^2 - b^2 \pmod n)

尝试恢复nn

贴一个当时获取nn的EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 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/

总结·