20220826-网鼎杯-CryptoSecWriteUp
crypto091
已知信息
1 | 安全顶会USENIX Security 2021 |
首批放号的联通号码是1709打头，再加上中国的地区码86，爆破一下就是
1 | from itertools import product |
crypto405-grasshopper
题目
1 | from Crypto.Util.number import * |
1 | Grasshopper#00:2066 |
总共42轮，加密流程大致如下，已知每次轮密钥的最后一个数，即每次的密文
关键是目测出前5个明文为flag{，可以列5个方程，如下
1 | flag = b'flag{' |
可用Gröbner基解方程，当然$p$不知道需要爆破，之后解密环节也是可以逆回去的，每轮解密都需要用到上一轮产生的轮密钥
1 | from Crypto.Util.number import * |
其他解法（由尚师傅提供
关于解方程，次数有一定规律，可以考虑用消元法。从编程实现角度来说，可以将幂指数和等号右边的数列一个矩阵，即（可以发现是一个斜着的杨辉三角）
$$
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & | & c_0’\\
5 & 4 & 3 & 2 & 1 & | & c_1’\\
15 & 10 & 6 & 3 & 1 & | & c_2’\\
35 & 20 & 10 & 4 & 1 & | & c_3’\\
70 & 35 & 15 & 5 & 1 & | & c_4’
\end{bmatrix}\notag
$$
通过初等行变换将左边的方针化成单位矩阵，得到的右边就是方程的解。要注意的是，和线性方程不一样，这里初等行变换对于原等式来说某一行乘以$a$：原等式两边同时幂上$a$
将某一行减去另外一行的$c$倍：相当于做除法，也就是乘以相应逆元
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
40from Crypto.Util.number import *
from gmpy2 import invert
with open("output.txt", 'r') as fp:
tmp = fp.readlines()
code = []
for i in tmp:
code.append(int(i[:-1][-4:], 16))
left = [102,
1192407267456,
1918196473060530916599580974905403195260928,
56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896,
53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536]
cof = [[1, 1, 1, 1, 1],
[5, 4, 3, 2, 1],
[15, 10, 6, 3, 1],
[35, 20, 10, 4, 1],
[70, 35, 15, 5, 1]]
p = 59441
for i in range(5):
cof[i].append((code[i] * invert(left[i], p)) % p)
for i in range(4):
tmp = cof[i][5]
for j in range(i+1, 5):
mul = cof[j][i]
for k in range(5):
cof[j][k] = -cof[j][k] + mul * cof[i][k]
cof[j][5] = (pow(tmp, mul, p) * invert(cof[j][5], p)) % p
for i in range(4, 0, -1):
tmp = cof[i][5]
for j in range(i-1, -1, -1):
mul = cof[j][i]
for k in range(5):
cof[j][k] -= mul * cof[i][k]
cof[j][5] = (cof[j][5] * invert(pow(tmp, mul, p), p)) % p
print(cof)
# [[1, 0, 0, 0, 0, mpz(28358)], [0, 1, 0, 0, 0, mpz(39970)], [0, 0, 1, 0, 0, mpz(28105)], [0, 0, 0, 1, 0, mpz(42009)], [0, 0, 0, 0, 1, mpz(46211)]]和Gröbner解得的是一样的
crypto162-david_homework
考点
- Fibonacci
- 矩阵快速幂
题目代码
1 | from secret import flag |
类似求斐波那契数列的优化，比较基础
大约跑一个多小时
1 | from hashlib import md5,sha256 |
更简便的思路（由尚师傅提供
因为通式可以写成$f(n) = a\times f(n-1)+b\times f(n-2)+c\times f(n-3)$的形式，对应矩阵相乘
$$
\begin{bmatrix}
a & b & c\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}\times
\begin{bmatrix}
f(n-1)\\
f(n-2)\\
f(n-3)
\end{bmatrix}=
\begin{bmatrix}
f(n)\\
f(n-1)\\
f(n-2)
\end{bmatrix}\notag
$$
最终
$$
\begin{bmatrix}
f(n)\\
f(n-1)\\
f(n-2)
\end{bmatrix}=
{\begin{bmatrix}
a & b & c\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}}^{n-5}\times
\begin{bmatrix}
f(5)\\
f(4)\\
f(3)
\end{bmatrix}\notag
$$
仔细观察可以发现和Fibonacci的优化算法异曲同工，但是可以用矩阵快速幂的算法比如
[353, -1162, 32767]，用sage来求解就是1
2
3
4
5
6
7
8
9
10
11
12
13def cal(i, cof):
if i < 3:
return i + 1
else:
return cof[2] * cal(i - 3, cof) + cof[1] * cal(i - 2, cof) + cof[0] * cal(i - 1, cof)
cof = [353, -1162, 32767]
a = [[cof[2],cof[1],cof[0]],[1,0,0],[0,1,0]]
b = [cal(5, cof),cal(4, cof),cal(3, cof)]
a, b = map(Matrix, [a, b])
f200000 = Matrix(a) ^ (200000 - 5) * vector(b)
f200000 = f200000[0]
矩阵快速幂
和模运算时的快速幂类似，基本思想就是
1 | while(n): |