0%

杂题闲记-2

GACTF2020

Elgamal-RSA

一开始直接把key给了。。。不过本身Elgamal部分本身就很简单,其实并无所谓

先求解Elgamal,计算出secret:

已知:

$c_1 = g^r $

$ c_2 = m * g^{dr} $

$ c_{11} = g^{B*r + A} $

$ c_{12} = m * g^{B*r + A} $

$ h = g ^ d$

推导:

\[ c_2 ^{-B} = m^{-B} * (g^d)^{-Br} \]

\[ c_{12} * c_2^{-B} = m^{1-B} * (g^d)^A \]

\[ (c_{12} * c_2^{-B})^{\frac{1}{1-B}} = m * (g^d)^{\frac{A}{1-B}} \]

\[ (c_{12} * c_2^{-B})^{\frac{1}{1-B}} * h^{\frac{1-B}{A}} = m\]

从而得到secret,之后计算\(\phi(n)\),发现有 \(e|\phi(n)\),但\(n\)有6个素因子,都不大,故对每个素因数\(p_i\),先在$ p_i^{l_i}$下decrypt,即把e当作

\[ \frac{e}{gcd(e, \phi(p_i^{l_i}))} \]

得到\(m_i\),之后求模$ p_i^{l_i}\(下\)m_i$的 \(gcd(e, \phi(p_i^{l_i}))\) 次根,然后CRT即可,完整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
from Crypto_tools import *

g, h, A, B, p, q =
c1, c2 =
c11, c12 =

# calculate the secret
g_br = (inverse(pow(g, A, p), p) * c11) % p
tmp = pow(c12 * inverse(pow(c2, B, p), p), inverse(1-B, q), p)
m = tmp * inverse(pow(h, A * inverse(1-B, q), p), p)

c =
n = m % p
e = 0x1296
primes = [232087313537, 104280142799213, 28079229001363, 653551912583, 42044128297, 802576647765917]
index = [5, 6, 14, 15, 6, 7]

# check the primes
base = 1
for i in range(len(primes)):
base = base * (primes[i]**index[i])
print(base == n)

phi = []
for i in range(len(primes)):
phi.append(primes[i] ** (index[i]-1) * (primes[i]-1))

low_e = []
for i in phi:
low_e.append(int(gcd(i, e)))

low_n = []
for i in range(len(primes)):
low_n.append(primes[i] ** index[i])

low_c = []
for i in range(len(primes)):
low_c.append(pow(c, inverse(e//low_e[i], phi[i]), low_n[i]))

for i in range(len(low_n)):
print('\n%d primes'%(i+1))
print('n = ' + str(low_n[i]))
print('root = ' + str(low_e[i]))
print('c = ' + str(low_c[i]))

# use sage's 'Mod(c,n).nth_root(root)'
candidate = [353407247512303965045365245273514113979254413155723038594, 118406996121335867872417220406950412663021908207429086460086709649567668592818842789, 40838194187011975196269228876765908865444944296745005849695833986972327289154552784299932702051642970620861282724383667531261441125357573017325620944049102688903343462724551047586535304480, 1695123516800295425246681257666516560158663239197207672350847711896311171077931594423061655507605147792730816972030575396344034948137641207075718430653779535756721008018915068547, 4723044149650256515091565811539899787013565528592340044059397238, 214489300896472271161382790695870756301586580281999239401045130054091244899629639375835223662794331991713]

# check
for i in range(len(candidate)):
assert pow(candidate[i], e, low_n[i]) == c % low_n[i]

# find all roots
roots = []
for i in range(len(candidate)):
roots.append(all_roots_mod(low_n[i], candidate[i], low_e[i], phi[i]))

# check again
for i in range(len(candidate)):
for j in roots[i]:
assert pow(j, e, low_n[i]) == c % low_n[i]

# solve
for i_1 in range(6):
for i_2 in range(6):
if i_1 == i_2:
continue
for i in roots[i_1]:
for j in roots[i_2]:
possible = long_to_bytes(GCRT([low_n[i_1], low_n[i_2]], [i, j])[0])
if all_ascii(possible):
print(possible)
sys.exit()
Square

这题本质是要求出二元二次方程的整数通解,即求出解之间的递推式。使用这个工具可以轻松解决,此处探讨一种特殊情况的原理(太久不看分析,感觉完全不会构造了orz),一般性情况的原理可见这里

二元二次方程可定义通式:\(Ax^2 + Bxy+Cy^2+Dx+Ey+F = 0 \quad (1)\)

\(\exists k \in Z_+, \ let \ B^2 -4AC = k^2\) (此处即为特殊条件)

之后进行构造求解,根本思想是降低次数,即通过构造简化为二元一次方程求解

一般需要降次时,容易想到需要构造平方来,于是先使用一个系数产生可配项

$(1) * 4A $

\[ \Rightarrow 4A^2x^2 + 4ABxy + 4ACy^2 +4ADx +4AEy + 4AF = 0 \quad (2)\]

之后2式加减\((B^2y^2 + 2BDy +D^2)\) (通过这个构造trick来化简)

\[ \Rightarrow 4 A^2 x^2 + 4 A B+x y + B^2 y^2 + 4 A D x + 2 B D y + D^2 + \]

\[ 4 A C y^2 - B^2 y^2 + 4 A E y - 2 B D y + 4 A F - D^2 = 0 \]

由此构造平方和,化简得\((2Ax+By+D)^2 - (ky)^2 +(4AE-2BD)*y = D^2 - 4AF \quad (3)\)

再将左边构造成两个平方差

$(3) * k^2 + (2AE-BD)^2 $

\[ \Rightarrow (2Akx + Bky +Dk)^2 - (k^2y + (2AE-BD))^2 = D^2k^2 - 4AFk^2 + (2AE-BD)^2 \]

由此利用平方差公式,得到:

\[ \Rightarrow [(2Akx + Bky +Dk) + (k^2y + 2AE-BD)][(2Akx + Bky +Dk) - (k^2y + 2AE-BD)] \]

\[ = D^2k^2 - 4AFk^2 + (2AE-BD)^2\]

此时分两种情况讨论:

\(C = D^2k^2 - 4AFk^2 + (2AE-BD)^2\)

  1. C为0:

    即有\(D^2k^2 - 4AFk^2 + (2AE-BD)^2 = 0\),则左边的积的两个因子(简称为\(f_1, f_2\))必然有一个因子为0,这就转换成了两个二元一次方程,之后只需判断有无解,选择相适的解集即可。

  2. C不为0:

    此时对C进行因子分解,得到所有因子(包含所有负数)\(divisor_i, i = 1, 2, \dots, s\)

    \(f_1, f_2\), 逐个判断\(f_1 = divisor_i\) 解的正确性,遍历\(divisor\) 数列,必然可以得到原方程的解集。

本题具体解法比较麻烦,属于较为一般的情况,了解构造思想即可。

RCTF2020

infantECC | working

使用定理:

GF(p)上形为\(y^2 = x^3 + b\) 的椭圆曲线在\(p\equiv 2 \mod 3\)时,阶数为p+1(这种曲线即为所谓的超奇异曲线)

emmmm准备复现的时候发现ROIS把博客删了???,只找到了Hellman的wp,但我主要是想看看多元Copper Smith的使用方法。。。所以就只能面向exp复现了。。。

猜测\(E_p, E_q\) 均为超奇异曲线(否则无法做题)

则已知s,r的低256位,且 \(s*r \equiv \mod ((p+1)*(q+1))\)

\((p+1)*(q+1) = n + (p+q) + 1\),n未知,但已知\(E_n\)两个点,故通过ECC可以很容易复原出来:

\(k*n = gcd((x_1^3+b-y_1^2), (x_2^3+b-y_2^2))\)

k较小,得到结果分解即可得到n:

1
2
3
N = gcd(int(Cy)^2-int(Cx)^3-int(b), int(Ty)^2-int(Tx)^3-int(b))
# 下面代码为消除k
N = factor_trial_division(N, 1000)[-1][0]

将s,r看作e,d,由此问题转化为了类似于Copper Smtih中Partial d的情况

可知有 \(k*(p+1)*(q+1) = e*d - 1\) ,且\(d < 2^{412}\)

\(\Rightarrow k *(n + p + q + 1) = e*d -1\)

\(s = p+q\),且已知d的低256位\(d_{low}\),则 \(\Rightarrow k * (n+s+1) = e * (d_{high}* 2 ^{256}+ d_{low})-1\)

存在三个变量:\(k, s, d_{high}\)

此处使用三元Copper Smith 求解,先考虑三个变量的上界:

\(k = \frac{e*d - 1}{(p+1)*(q-1)} \leq 2 ^{1024 + 412 - 1024} = 2 ^ {412}\)

\(s = (p+1)*(q+1) \leq 2 ^ {1024}\)

\(d_{high} = \frac{d - d_{low}}{2^{256}} \leq 2^{412-256} = 2^{156}\)

这里考虑类似于Boneh and Durfee attack,具体原理可以先看这篇论文

尝试使用二元Cooper去解

\(s = p+q\)

\(k'*(n + s + 1) \equiv e * d_{low} -1 \mod 2^{256}\)

还有 \(p^2 - sp +n \equiv 0 \mod 2^{256}\)

上式乘\(p\),下式乘\(k'\),相加得到\(k'np + k'p + p +k'p^2 + k'n \equiv ed_{low}p \mod 2^{256}\)

\(\Rightarrow k'p^2 + (k'n + k' + 1 - ed_{low}) p + k'n \equiv 0 \mod 2^{256}\)

此时只剩下两个未知量\(k', p\), 通常\(k'\)是采用在\((0, e-1)\) 下爆破来获取,而这里e为1024位,显然并不现实。。

De1CTF2020

easy_RSA

Ver学长tql,比赛的时候还没入门,于是只能复现的时候看了,本题貌似不小心和D3CTF的撞了,学长后来也很懵233

本题利用的是Howgrave-Graham and Seifert’s Attack是基于Wiener's Attack(\(d < N^{\frac{1}{4}}\))和Guo's Common Modulus Attack(\(d < N^{\frac{1}{3}}\))的一种攻击,通过这篇paper,可以比较清晰的了解原理,也可以看官方wp

可行性分析:

相较于其借鉴的两种攻击,此种攻击对d的范围限制更小,根据所有公钥数量r,有约束\(d < N^{\frac{3+r}{7r}}\),原题中给了两个e,故r = 2,即需\(d< N^{\frac{5}{14}}\),而所给d范围限定在\([N^{\frac{1}{3}}, 2^{49} *N^{\frac{1}{3}} ]\),约为\([N^{\frac{1}{3}}, N^{\frac{1}{3}+0.023} ]\)

而又有 \(\frac{1}{3} + 0.023 \approx 0.357 \approx \frac{5}{14}\)

可以看到d基本是在范围内的,故攻击可行

已知:n组\(e_i\),满足\(e_i * d_i = 1 + ki * \phi(N), d < N^{\delta}\)

本题使用了\(lcm(N)\),相当于\(e_i * d_i = 1 + ki * \frac{\phi(N)}{g}\),并无无太大影响

依据四个等式可以列出矩阵:

之后为了能够正确格基约化,需要将各分量放缩到数量级相近,通过简单计算使用如下放缩矩阵即可:

之后直接求解方程组,得到向量\(x_2\),然后利用如下推导,即可求出\(\phi(N)\) \[ e_i * d_i = 1 + k_i * \frac{\phi(N)}{g}\\ \Rightarrow \phi(N) = \frac{e_id_ig-g}{k_i}\\ \Rightarrow \phi(N) = \frac{e_id_ig}{k_i} + \frac{g}{k_i}\\ \Rightarrow e_i * \frac{k_2d_1g}{k_1k_2}-1 \leq \phi(N) \leq e_i * \frac{k_2d_1g}{k_1k_2} + 1 \]

最后等式中未知的分母,分子即为\(x_2\)向量中的分量,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
from Crypto_tools import *
from sage.all import *
from sage.all_cmdline import *


N =
e1 =
e2 =
c =
E = [e1, e2]

for i in range(2048//3, 2048//3 + 50):
x = Integer(i) / Integer(2048)
print(i)
N_1 = round(N**(Integer(1)/Integer(2)))
N_2 = round(N**(1+x))

N_3 = round(N**(Integer(i) / Integer(100)))
A = Matrix(ZZ, [[N, -N_1 * N, 0, N**2],
[0, N_1 * e2, -N_2 * e2, -e2*N],
[0, 0, N_2 * e1, -e1*N],
[0, 0, 0, e1*e2]])

AL = A.LLL()
C = Matrix(ZZ, AL[0])
B = A.solve_left(C)[0]

phi_base = floor(e2 * (B[1] // B[0]))
for j in range(-1, 2):
phi = phi_base + j
for e in E:
d = inverse(e, phi)
m = long_to_bytes(pow(c, d, N))
if all_ascii(m):
print(m)
sys.exit(1)

奇怪的想法

emmm我在复现的时候看paper,就觉得很奇怪,为什么构造的等式一定是这四个呢:

从理论上来说,将\(G_{1,2}\) 替换成\(k_1W_2\),似乎也无伤大雅,但我尝试这样构造之后,并没有成功,即便爆破了放缩的系数,仍然无法求解,而且误差相当的大,后来算了一波bound,发现确实不符合2333,大概作者写的时候可能也经历了这种尝试吧。

不过这题也帮我梳理了一种构造Latiice时的步骤:

  1. 寻找n组等式,其中具有n个未知量
  2. 通过这n组等式,提取出n个未知量作为初始向量x,构造秩为n的矩阵A,并有\(xA = y\)
  3. 计算向量y的范数,分析各分量的数量级,通过一个放缩矩阵D,将y向量各分量尽量放缩到一个数量级上
  4. 对矩阵\(A' = AD\)使用格基约化,利用约简出的向量和\(A'\) 矩阵求出向量x,得到欲求量

Pwnhub2020 Crypto theme

CoinFlip

知识点:

Elgamal加密时所选p(即模)的安全准则:DDH假设(Decisional Diffie–Hellman)

对于随机选取的\(a, b \in Z_p\),已知\(g^a, g^b\),产生的 \(g^{ab}\) 接近于\(Z_p\) 上的随机数

可以形式化为:

  1. 若p存在k次剩余\(r_k\)\(\frac{p-1}{k}\) 也应为一大素数
  2. 对于p上的任意椭圆曲线E,E的阶很大
  3. 对于p上的超椭圆曲线,其Jacobian的阶很大

如上所述,GF上的乘法群并不符合DDH假设,因为其可以通过计算Lengendre符号区分\(g^ab\)和一般随机序列。故直接根据所给公钥,区分两组明文,但存在一定概率性(两组明文的Lengendre符号可能相同)。

测试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
from Crypto.PublicKey import ElGamal
from Crypto.Util.number import bytes_to_long
import os
from random import SystemRandom
from Crypto_tools import *


p =
g =
y =
pubkey = ElGamal.construct((p, g, y))
base = jacobi(y, p)
for i in tqdm(range(2**10)):
rnd = SystemRandom()
msg1 = bytes_to_long(b"Head" + os.urandom(124))
msg2 = bytes_to_long(b"Tail" + os.urandom(124))

count = 0
while True:
coin = rnd.randrange(2)
gift = pubkey._encrypt([msg1, msg2][coin], rnd.randrange(1, p - 1))
check_1 = jacobi(gift[0], p)
check_2 = jacobi(gift[1], p)
ans = 0
if check_1 == 1:
if check_2 == 1:
ans = 0
else:
ans = 1
elif check_1 == -1 and base == -1:
if check_2 == 1:
ans = 1
else:
ans = 0
if ans == coin:
count += 1
if count == 50:
print('try %d times' % i)
print('flag{LordRiot\'s test flag}')
exit()
else:
break

注意pycrypto中的Elgamal由于继承关系,encrypt函数为空,应调用_encrypt函数。

Oblivious transfer

核心漏洞是在于始终使用一组RSA公私钥,从而可以构造两个连接,利用不变量来爆破,wp郑佬写的很详细了,这里就不详述了,我这里把大小写区分了一下,大概跑一百多次就可以跑出结果,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
from pwn import *
from Crypto.Util.number import *
from itertools import product

# main-decrypt
main_connection = remote('127.0.0.1', 10001)
n = int(main_connection.recvline())
e = int(main_connection.recvline())
init_x0 = int(main_connection.recvline())
init_x1 = int(main_connection.recvline())
main_connection.sendline(str(init_x0))
msg0 = int(main_connection.recvline())
init_enc1 = int(main_connection.recvline())

# sub-attack
attack_connection = remote('127.0.0.1', 10001)
attack_connection.recvline()
attack_connection.recvline()
possible = [set(range(256)) for _ in range(256)]
cnt = 1
little_min = 97
little_max = 122
big_min = 65
big_max = 90

while True:
x0 = int(attack_connection.recvline())
x1 = int(attack_connection.recvline())
attack_connection.sendline(str(init_x0 - init_x1 + x0))
enc0 = int(attack_connection.recvline())
enc1 = int(attack_connection.recvline())
attack_connection.sendline('0')
attack_connection.sendline('0')

bytes_enc = long_to_bytes(enc0, 256)[::-1]

for i in range(256):
if i == 0:
carrymin = 0
carrymax = 0
else:
if min(possible[i - 1]) + big_min >= 256:
carrymin = 1
else:
carrymin = 0
if max(possible[i - 1]) + little_max < 256:
carrymax = 0
else:
carrymax = 1

if i == 256 - 1:
little_start = bytes_enc[i] - carrymax
little_end = bytes_enc[i] - carrymin
big_start = bytes_enc[i] - carrymax
big_end = bytes_enc[i] - carrymin
else:
little_start = bytes_enc[i] - little_max - carrymax
little_end = bytes_enc[i] - little_min - carrymin
big_start = bytes_enc[i] - big_max - carrymax
big_end = bytes_enc[i] - big_min - carrymin
tmp = set(x % 256 for x in range(little_start, little_end + 1)) | set(x % 256 for x in range(big_start, big_end + 1))
possible[i] &= tmp

limit = 1
for i in range(256):
limit *= len(possible[i])
cnt += 1
print(cnt, limit.bit_length())

if limit < 50000:
print("Trying all possibilities")
for b in product(*possible):
m = bytes_to_long(bytes(b[::-1])) % n
if pow(m, e, n) == init_x0 - init_x1:
main_connection.sendline(str(msg0))
main_connection.sendline(str((init_enc1 - m) % n))
print('Got')
print(main_connection.recvline())
main_connection.interactive()
print("Failed")
attack_connection.close()
main_connection.close()
exit()