网鼎杯-Qualifier-2022/青龙组/Crypto/crypto405 writeup
网鼎杯-Qualifier-2022/青龙组/Crypto/crypto405 writeup
1. challenge
下载附件得到源码和密文
from Crypto.Util.number import *
from random import randrange
# from grassfield import flag
flag=b"ffffffff"
p = getPrime(16)
print(p)
k = [randrange(1,p) for i in range(5)]
print(k)
for i in range(len(flag)):
grasshopper = flag[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j] % p
print('Grasshopper#'+str(i).zfill(2)+':'+hex(grasshopper)[2:].zfill(4))
点击查看密文
Grasshopper#00:2066 Grasshopper#01:a222 Grasshopper#02:cbb1 Grasshopper#03:dbb4 Grasshopper#04:deb4 Grasshopper#05:b1c5 Grasshopper#06:33a4 Grasshopper#07:c051 Grasshopper#08:3b79 Grasshopper#09:6bf8 Grasshopper#10:2131 Grasshopper#11:2c40 Grasshopper#12:91ba Grasshopper#13:7b44 Grasshopper#14:5f25 Grasshopper#15:0208 Grasshopper#16:7edb Grasshopper#17:62b5 Grasshopper#18:cec5 Grasshopper#19:5ab3 Grasshopper#20:3c46 Grasshopper#21:c272 Grasshopper#22:714b Grasshopper#23:9e0b Grasshopper#24:48ee Grasshopper#25:44cc Grasshopper#26:05a0 Grasshopper#27:3da3 Grasshopper#28:11b1 Grasshopper#29:259f Grasshopper#30:899d Grasshopper#31:a130 Grasshopper#32:e58f Grasshopper#33:23f3 Grasshopper#34:5829 Grasshopper#35:6beb Grasshopper#36:3681 Grasshopper#37:0054 Grasshopper#38:a189 Grasshopper#39:2765 Grasshopper#40:c63d Grasshopper#41:bc68
分析
只要能看懂题目，就不难解题。关键在于每一轮的k都会变化，加密过程转换成数学公式为：
$$ \begin{align} & k_i^0 = m_i*k_{i-1}^0 \notag \newline & k_i^j = k_{i-1}^j*k_i^j \notag \newline & c_i = k_i^4 \notag \end{align} $$
方法一
阅读代码可知，每一轮的k，都与上一轮的k相关。又已知flag格式为flag{*}，即已知明文前五位，可以列出5个模p的方程式：
from Crypto.Util.number import *
def generate_equations(m, k):
k = k.copy()
equations = []
for i in range(5):
grasshopper = m[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j]
equations.append(grasshopper)
return equations
def show_equations(equations, c):
for i in range(len(equations)):
show(equations[i]-c[i])
p = 2^16-1
p = previous_prime(p)
R.<k0,k1,k2,k3,k4,m0,m1,m2,m3,m4,c0,c1,c2,c3,c4> = GF(p)[]
m = [m0,m1,m2,m3,m4]
k = [k0,k1,k2,k3,k4]
c = [c0,c1,c2,c3,c4]
equations = generate_equations(m, k)
show_equations(equations, c)
$$ \begin{align} & k_{0} k_{1} k_{2} k_{3} k_{4} m_{0} - c_{0} \notag \newline & k_{0}^{5} k_{1}^{4} k_{2}^{3} k_{3}^{2} k_{4} m_{0}^{5} m_{1} - c_{1} \notag \newline & k_{0}^{15} k_{1}^{10} k_{2}^{6} k_{3}^{3} k_{4} m_{0}^{15} m_{1}^{5} m_{2} - c_{2} \notag \newline & k_{0}^{35} k_{1}^{20} k_{2}^{10} k_{3}^{4} k_{4} m_{0}^{35} m_{1}^{15} m_{2}^{5} m_{3} - c_{3} \notag \newline & k_{0}^{70} k_{1}^{35} k_{2}^{15} k_{3}^{5} k_{4} m_{0}^{70} m_{1}^{35} m_{2}^{15} m_{3}^{5} m_{4} - c_{4} \notag \end{align} $$
5个未知数，5个同余方程，可解。但我不会自动解，考虑手动消元。
观察发现$k_4$的幂都是1, 每个方程式除以前式，可得到关于$k_0,k_1,k_2,k_3$的4个同余方程式：
def temp_k4_elimination(equations, c):
equations = [equations[i+1]/equations[i] for i in range(4)]
c = [c[i+1]/c[i] for i in range(4)]
show_equations(equations, c)
temp_k4_elimination(equations, c)
$$ \begin{align} & \frac{k_{0}^{4} k_{1}^{3} k_{2}^{2} k_{3} m_{0}^{4} m_{1} c_{0} - c_{1}}{c_{0}} \notag \newline & \frac{k_{0}^{10} k_{1}^{6} k_{2}^{3} k_{3} m_{0}^{10} m_{1}^{4} m_{2} c_{1} - c_{2}}{c_{1}} \notag \newline & \frac{k_{0}^{20} k_{1}^{10} k_{2}^{4} k_{3} m_{0}^{20} m_{1}^{10} m_{2}^{4} m_{3} c_{2} - c_{3}}{c_{2}} \notag \newline & \frac{k_{0}^{35} k_{1}^{15} k_{2}^{5} k_{3} m_{0}^{35} m_{1}^{20} m_{2}^{10} m_{3}^{4} m_{4} c_{3} - c_{4}}{c_{3}} \notag \end{align} $$
观察发现$k_3$的幂都是1, 同理，重复上述动作，可逐个消元，将方程组化简。
def simplify_equations(equations, c):
c = c.copy()
simplified_equations = [equations[0]-c[0]]
for _ in range(4):
equations =[equations[i+1]/equations[i] for i in range(len(equations)-1)]
c = [c[i+1]/c[i] for i in range(len(c)-1)]
simplified_equations.append(equations[0]-c[0])
for i in range(len(simplified_equations)):
show(simplified_equations[i])
return simplified_equations
simplified_equations = simplify_equations(equations, c)
$$ \begin{align} & k_{0} k_{1} k_{2} k_{3} k_{4} m_{0} - c_{0} \notag \newline & \frac{k_{0}^{4} k_{1}^{3} k_{2}^{2} k_{3} m_{0}^{4} m_{1} c_{0} - c_{1}}{c_{0}} \notag \newline & \frac{k_{0}^{6} k_{1}^{3} k_{2} m_{0}^{6} m_{1}^{3} m_{2} c_{1}^{2} - c_{0} c_{2}}{c_{1}^{2}} \notag \newline & \frac{k_{0}^{4} k_{1} m_{0}^{4} m_{1}^{3} m_{2}^{2} m_{3} c_{0} c_{2}^{3} - c_{1}^{3} c_{3}}{c_{0} c_{2}^{3}} \notag \newline & \frac{k_{0} m_{0} m_{1} m_{2} m_{3} m_{4} c_{1}^{4} c_{3}^{4} - c_{0} c_{2}^{6} c_{4}}{c_{1}^{4} c_{3}^{4}} \notag \end{align} $$
def solve_equations(equations, kwargs, k):
k = k.copy()
for i in range(5):
equation = equations[5-i-1]
for j in range(i+1):
kwargs[f'k{j}'] = k[j]
k[i] = int(equation(**kwargs).univariate_polynomial().roots()[0][0])
# print(f"k[{i}]=", k[i])
return k
output = [0x2066,0xa222,0xcbb1,0xdbb4,0xdeb4,0xb1c5,0x33a4,0xc051,0x3b79,0x6bf8,0x2131,0x2c40,0x91ba,0x7b44,0x5f25,0x0208,0x7edb,0x62b5,0xcec5,0x5ab3,0x3c46,0xc272,0x714b,0x9e0b,0x48ee,0x44cc,0x05a0,0x3da3,0x11b1,0x259f,0x899d,0xa130,0xe58f,0x23f3,0x5829,0x6beb,0x3681,0x0054,0xa189,0x2765,0xc63d,0xbc68,]
known_plain = 'flag{'
known_m = [ord(i) for i in known_plain]
kwargs = {}
for i in range(5):
kwargs[f'm{i}'] = known_m[i]
kwargs[f'c{i}'] = output[i]
kwargs[f'k{i}'] = 1
k_init = solve_equations(simplified_equations, kwargs, k)
求出k，则可解出明文，$m_ik_0k_1k_2k_3k_4\equiv c_i\mod p \Rightarrow m_i\equiv c_i*{k_0k_1k_2k_3k_4}^{-1}\mod p$
完整exp如下：
from tqdm import tqdm
def generate_equations(m, k):
k = k.copy()
equations = []
for i in range(5):
grasshopper = m[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j]
equations.append(grasshopper)
return equations
def simplify_equations(equations, c):
c = c.copy()
simplified_equations = [equations[0]-c[0]]
for _ in range(4):
equations =[equations[i+1]/equations[i] for i in range(len(equations)-1)]
c = [c[i+1]/c[i] for i in range(len(c)-1)]
simplified_equations.append(equations[0]-c[0])
return simplified_equations
def solve_equations(equations, kwargs, k):
k = k.copy()
for i in range(5):
equation = equations[5-i-1]
for j in range(i+1):
kwargs[f'k{j}'] = k[j]
k[i] = int(equation(**kwargs).univariate_polynomial().roots()[0][0])
# print(f"k[{i}]=", k[i])
return k
def update_k(m, k):
grasshopper = m
for j in range(5):
k[j] = grasshopper = grasshopper * k[j] %p
return k
def decrypt(k):
m = known_m.copy()
for i in range(5, len(output)):
mi = output[i]*inverse_mod(k[0]*k[1]*k[2]*k[3]*k[4], p)%p
if mi > 128:
break
m.append(mi)
k = update_k(mi, k)
return m
known_plain = 'flag{'
known_m = [ord(i) for i in known_plain]
output = [0x2066,0xa222,0xcbb1,0xdbb4,0xdeb4,0xb1c5,0x33a4,0xc051,0x3b79,0x6bf8,0x2131,0x2c40,0x91ba,0x7b44,0x5f25,0x0208,0x7edb,0x62b5,0xcec5,0x5ab3,0x3c46,0xc272,0x714b,0x9e0b,0x48ee,0x44cc,0x05a0,0x3da3,0x11b1,0x259f,0x899d,0xa130,0xe58f,0x23f3,0x5829,0x6beb,0x3681,0x0054,0xa189,0x2765,0xc63d,0xbc68,]
c = output[:5]
p = 2^16-1
pbar = tqdm(total=int(prime_pi(2^16)-prime_pi(2^15)))
while p.nbits()<=16:
pbar.update()
p = previous_prime(p)
R.<k0,k1,k2,k3,k4,m0,m1,m2,m3,m4,c0,c1,c2,c3,c4> = GF(p)[]
k = [k0,k1,k2,k3,k4]
equations = generate_equations(known_m, k)
simplified_equations = simplify_equations(equations, c)
kwargs = {}
for i in range(5):
kwargs[f'k{i}'] = 1
k_init = solve_equations(simplified_equations, kwargs, k)
k_iterate = k_init.copy()
for i in known_m:
k_iterate = update_k(i, k_iterate)
m = decrypt(k_iterate)
if len(m)==42:
flag = "".join([chr(i) for i in m])
print(flag)
print("k:", k_init)
print("p:", p)
break
pbar.close()
18% 534/3030 [00:02<00:10, 231.04it/s]
flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}
k: [28358, 39970, 28105, 42009, 46211]
p: 59441
方法二
for i in range(len(flag)):
grasshopper = flag[i]
for j in range(5):
k[j] = grasshopper = grasshopper * k[j] % p
根据代码知道，每一轮的密文，就是每一轮的$k_4$。每一轮的$k_4$为该轮的$k_3$乘以上一轮的$k_4$。
即，记第i轮的$k_j$为$k^j_i$，密文为$c_i$，有：
$$ \begin{align} & c_i = k_i^4 \notag \newline & k_i^j \equiv k_i^{j-1} k_{i-1}^j \mod p \notag \newline \Rightarrow & k_i^{j-1}\equiv k_i^j*{k_{i-1}^j}^{-1} \mod p \notag \end{align} \notag $$
已知$k_i^4$，则可以求得$k_i^3$，同理可求得$k_i^0$。
另有: $$ \begin{align} \notag & k_i^0\equiv k_{i-1}^0*m_i\mod p \notag \newline \Rightarrow & m_i \equiv k_i^0*{k_{i-1}^0}^{-1}\mod p \notag \end{align} $$
因为p是16位的素数，已知flag格式为flag{*}，则可以爆破p，解密出明文，根据明文格式判断是否为正确的flag。
from tqdm import tqdm
output = [0x2066,0xa222,0xcbb1,0xdbb4,0xdeb4,0xb1c5,0x33a4,0xc051,0x3b79,0x6bf8,0x2131,0x2c40,0x91ba,0x7b44,0x5f25,0x0208,0x7edb,0x62b5,0xcec5,0x5ab3,0x3c46,0xc272,0x714b,0x9e0b,0x48ee,0x44cc,0x05a0,0x3da3,0x11b1,0x259f,0x899d,0xa130,0xe58f,0x23f3,0x5829,0x6beb,0x3681,0x0054,0xa189,0x2765,0xc63d,0xbc68]
p = 2^15-1
pbar = tqdm(total=int(prime_pi(2^16)-prime_pi(2^15)))
while p.nbits()<=16:
pbar.update()
p = next_prime(p)
k = output.copy()
for _ in range(5):
if p in k:
break
k = [k[i]*inverse_mod(k[i-1], p)%p for i in range(1, len(k))]
if k[-1] == ord('}'):
flag = "flag{"+"".join([chr(i) for i in k])
print(flag)
break
pbar.close()
77% 2322/3030 [00:00<00:00, 3877.36it/s]
flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}