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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
| from sage.all import *
import random
from Crypto.Util.number import long_to_bytes
lcg_gen_6 = [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168,
464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755]
"""
seed = 2023
x = [seed]
x = x + lcg_gen_6
"""
x = lcg_gen_6
x1 = x[0]
x2 = x[1]
x3 = x[2]
t = []
for i in range(1, len(x)):
t.append(x[i] - x[i-1])
# 恢复 Modulus
m = 0
for i in range(1, len(t)-1):
m = GCD(t[i+1]*t[i-1] - t[i]*t[i], m)
print(f'[+] modulus: {m}')
n = m
# 恢复 Multiplier, Increment (a, b)
R = Zmod(n)
a = R(x[2] - x[1]) / (x[1] - x[0])
b = R(x[1] - a * x[0])
print(f'[+] a = {a}\n[+] b = {b}')
# 也许参数位置不对
p = ZZ(a)
e = ZZ(b)
Q = ZZ(n)
# Q \equiv q^2 \pmod{p}
# 求二次剩余, 返回空, 大概率位置错了
# []
# check location
print(f'[*] Parameters location check:\t{is_prime(p)} {is_prime(e)} {is_prime(Q)}')
# 1 0 1
# p, q, e 均为 512-bits 素数, 而上面第二个返回值为 False, 则说明位置错了
Q, e = e, Q
# 判二次剩余
if not legendre_symbol(Q, p) == 1:
print('[-] No solution')
else:
print('[+] Found solution')
# Solution quadratic residue
# Modulus is prime, So
# Cipolla Algorithm
class CipollaAlgorithm:
def __init__(self, p):
self.p = p # 模数p
def mul(self, a, b, w):
# 复数乘法
x = (a[0] * b[0] + a[1] * b[1] * w) % self.p
y = (a[0] * b[1] + a[1] * b[0]) % self.p
return (x, y)
def qpow_r(self, a, b):
# 实数快速幂
res = 1
while b:
if b & 1:
res = res * a % self.p
a = a * a % self.p
b >>= 1
return res
def qpow_i(self, a, b, w):
# 复数快速幂
res = (1, 0)
while b:
if b & 1:
res = self.mul(res, a, w)
a = self.mul(a, a, w)
b >>= 1
return res[0]
def cipolla(self, n):
n %= self.p
if self.qpow_r(n, (self.p - 1) // 2) == self.p - 1:
return -1 # 没有解
while True:
a = random.randint(0, self.p-1)
w = (a*a - n) % self.p
if self.qpow_r(w, (self.p - 1) // 2) == self.p - 1:
break
x = (a, 1)
return self.qpow_i(x, (self.p + 1) // 2, w)
# Q = q^2 mod p
p = p
n = Q
cipolla = CipollaAlgorithm(p)
ans1 = cipolla.cipolla(n)
ans2 = (-ans1) % p
ans = []
if ans1 == -1:
print("[-] No solution")
else:
if ans1 > ans2:
ans1, ans2 = ans2, ans1
if ans1 == ans2:
ans.append(ans1)
else:
ans.append(ans1)
ans.append(ans2)
# check prime
for i in ans:
if not is_prime(i):
# print(f'[-] {i} is not prime')
pass
else:
q = i
print(f'[+] {i} is prime')
print('[*] DONE Quadratic Residue')
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924
m = pow(c, d, p * q)
print(f'[*] 全因子解密: \n{long_to_bytes(m)}')
# uuid 长 42 bytes
# DASCTF{} 长 8 bytes
# 50 * 8 = 400 bits < 512 bits
# 单因子解密
phi = p - 1
d = inverse_mod(e, phi)
m = power_mod(c, d, p)
print(f'[*] 单因子解密: \n{long_to_bytes(m)}')
"""
inva = inverse(a, n)
x1 = x[0]
for i in range(300):
x1 = (x1 - b) * inva % n
try:
flag = long_to_bytes(x1)
if b'flag{' in flag:
print(flag)
except Exception as err:
print(err)
continue
"""
|