这里就对mix这题进行记录
mix
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
| from Crypto.Util.number import *
from secret import flag
import random
p = getStrongPrime(2048)
q = getStrongPrime(2048)
s = getStrongPrime(2048)
r = int(裴波那契数列[2022])
mask = b'******'
enc1 = b'******'
flag1 = b'CMCTF{' +enc1 + mask + b'}'
e = 0o10001
m = bytes_to_long(enc1)
n = p * q * r
c = pow(m, e, n)
hint = p*s*q - p*s - q*s + s
print('n=',n)
print('c=',c)
print('hint=',hint)
\
\
\
def lfsr(R, mask):
output = (R << 1) & 0xffffffffffffffffffffffffffffffff
i = (R & mask) & 0xffffffffffffffffffffffffffffffff
lastbit=0
while i != 0:
lastbit ^= (i & 1)
i = i >> 1
output ^= lastbit
return (output,lastbit)
num_mask = bytes_to_long(mask)
R = random.getrandbits(128)
print(R)
for _ in range(128):
R,out = lfsr(R,num_mask)
print(R)
|
对于第一部分来说我们需要先求出r
条件中给出我们要求的是fib（2022），这里有多种方法可以求解，暴力递归或者DP或者矩阵快速幂
这里暴力递归的时间复杂度是O(2N)
DP的时间复杂度是O(N)
矩阵快速幂的时间复杂度是O（logN ）
这里介绍下如何用快速幂来求斐波那契数列的第n项
对于斐波那契数列我们知道 fn = fn − 1 + fn − 2
这个数列是这个样子的 0，1，1，2，3，5，8… 首先我们先定义向量$\vec{v1}$和$\vec{v2}$ $$
v1=\begin{pmatrix}
0\\
1
\end{pmatrix}
$$
$$
v2=\begin{pmatrix}
1\\
1
\end{pmatrix}
$$
这里我们可以看作$\vec{v1}$通过左乘一个矩阵得到了$\vec{v2}$，即 $$
\begin{pmatrix}
a & b\\
c &d
\end{pmatrix}
\begin{pmatrix}
0\\
1
\end{pmatrix}=\begin{pmatrix}
1\\
1
\end{pmatrix}
$$ 这里要解除参数a,b,c,d我们就还需要一组 $$
\begin{pmatrix}
a & b\\
c &d
\end{pmatrix}
\begin{pmatrix}
1\\
1
\end{pmatrix}=\begin{pmatrix}
1\\
2
\end{pmatrix}
$$ 根据矩阵的乘法就可以知道
a=0 b=1 c=1 d=1,那么M矩阵也就出来了 $$
\begin{pmatrix}
a & b\\
c &d
\end{pmatrix}=
\begin{pmatrix}
0 & 1\\
1 &1
\end{pmatrix}
$$ 我们想求第n项,就变成了M的n-1次方乘上v1
现在问题就转换成了求一个矩阵的高次幂
先看传统的快速幂是如何求解的
假设现在要求的是353
将53转换成二进制也就是110101
把二进制位上不为0的数表示出来就会得到 332 * 316 * 34 * 31 = 353
那么对于矩阵来说也是如此
回到本题，要求的是第2022项
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
| def matrix_mult(A, B):
"""2x2 矩阵乘法"""
return [
[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
[A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]],
]
def matrix_pow(mat, power):
"""矩阵快速幂"""
result = [[1, 0], [0, 1]] # 单位矩阵，区别于普通的快速幂初始的我们要取单位矩阵
while power > 0:
if power % 2 == 1:
result = matrix_mult(result, mat)
mat = matrix_mult(mat, mat)
power //= 2
return result
def fibonacci(n):
if n == 0:
return 0
mat = [[1, 1], [1, 0]]
mat_pow = matrix_pow(mat, n - 1)
return mat_pow[0][0]
print(fibonacci(2022)) # 输出 fib(2022)
|
这里用DP的代码是
1
2
3
4
5
6
7
8
9
10
11
12
| def fibonacci(n):
if n == 0:
return 0
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fibonacci(2022))
|
1
| r=167310648784659280728144836725590014814177400797476760876753704080114260114536495380135014244628641540465009479015934299376306193238817784129405465804445140758993423687143146613390123354557936785042721146861530732824681611737331775039385078670522766530356710254069894988375176317365030278080713218413201048678360636199830514037131301419749286901789895779518426772646405033423571360115994228553098871046696520981384561779336
|
我们还知道 hint = p * s * q − p * s − q * s + s
hint = s * (n − p − q + 1)
也就是hint是phi的倍数
所以我可以直接求出私钥
1
2
3
4
5
6
7
8
9
10
11
| e = 0o10001
d = pow(e, -1, hint)
m = pow(c, d, n)
enc1 = long_to_bytes(m)
print(enc1)
|
第二部分是LFSR
这里的LFSR是已经输入和输出要求掩码mask，所以可以通过解方程来实现求解
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| def init(state):
result = [int(i) for i in bin(state)[2:]]
PadLenth = 128 - len(result)
result = [ 0 ] * PadLenth + result
assert len(result) == 128
return result
def solve_GF2_linear_system(A, b):
"""
使用 SageMath 在 GF(2) 上求解线性方程组 Ax = b
:param A: 系数矩阵
:param b: 结果向量
:return: 解向量 x
"""
F = GF(2)
A_GF2 = Matrix(F, A)
b_GF2 = vector(F, b)
try:
x = A_GF2.solve_right(b_GF2)
return x
except ValueError:
return None
def solution(m):
a,b = m[0],m[1]
solution = solve_GF2_linear_system(a, b)
if solution:
print(f"解向量为: {solution}")
return solution
else:
print("无解")
return None
def change(seed,random):
All = seed + random
a = [[0]*128 for _ in range(128)]
b = random
for i in range(128):
a[i] = All[i:i+128]
return (a,b)
random1 = 176011035589551066670092363165068881602
random2 = 157117237038314150714243518116791116977
random1,random2 = map(init, [random1,random2])
ans = solution(change(random1,random2))
mask = int("".join(str(i) for i in ans),2)
mask = long_to_bytes(int(mask))
print(mask)
|
