xyctf 2025 crypto wp
xyctf 2025 crypto wp
xyctf 2025 crypto wp
Division
题目描述
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
# -*- encoding: utf-8 -*-
'''
@File : server.py
@Time : 2025/03/20 12:25:03
@Author : LamentXU
'''
import random
print('----Welcome to my division calc----')
print('''
menu:
[1] Division calc
[2] Get flag
''')
while True:
choose = input(': >>> ')
if choose == '1':
try:
denominator = int(input('input the denominator: >>> '))
except:
print('INPUT NUMBERS')
continue
nominator = random.getrandbits(32)
if denominator == '0':
print('NO YOU DONT')
continue
else:
print(f'{nominator}//{denominator} = {nominator//denominator}')
elif choose == '2':
try:
ans = input('input the answer: >>> ')
rand1 = random.getrandbits(11000)
rand2 = random.getrandbits(10000)
correct_ans = rand1 // rand2
if correct_ans == int(ans):
print('WOW')
with open('flag', 'r') as f:
print(f'Here is your flag: {f.read()}')
else:
print(f'NOPE, the correct answer is {correct_ans}')
except:
print('INPUT NUMBERS')
else:
print('Invalid choice')
大概就是可以通过发送除数得到(随机数//除数)结果,除数取一就好，如何发送624个请求，用来预测随机数就行
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
from pwn import *
from extend_mt19937_predictor import ExtendMT19937Predictor
def main():
predictor = ExtendMT19937Predictor()
context.log_level = "debug" # 调试模式
try:
# 连接远程服务器
io = remote("ip", port)
# 等待初始提示符（根据实际输出调整）
io.recvuntil(b">>> ") # 假设提示符是 ">>> "
# 收集 624 个随机数
for i in range(624):
io.sendline(b"1") # 选择选项 1
io.sendlineafter(b">>> ", b"1") # 输入分母 1
io.recvuntil(b" = ")
nominator = int(io.recvline().strip())
predictor.setrandbits(nominator, 32)
print(f"[+] Collected {i+1}/624 samples")
# 预测答案
rand1 = predictor.predict_getrandbits(11000)
rand2 = predictor.predict_getrandbits(10000)
correct_ans = rand1 // rand2
print(f"[+] Predicted answer: {correct_ans}")
# 提交答案
io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b"input the answer: >>> ", str(correct_ans).encode())
# 获取 Flag
print(io.recvall().decode())
except Exception as e:
print(f"[-] Error: {e}")
finally:
io.close()
if __name__ == "__main__":
main()
Complex_signin
题目描述
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
from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag
class Complex:
def __init__(self, re, im):
self.re = re
self.im = im
def __mul__(self, c):
re_ = self.re * c.re - self.im * c.im
im_ = self.re * c.im + self.im * c.re
return Complex(re_, im_)
def __eq__(self, c):
return self.re == c.re and self.im == c.im
def __rshift__(self, m):
return Complex(self.re >> m, self.im >> m)
def __lshift__(self, m):
return Complex(self.re << m, self.im << m)
def __str__(self):
if self.im == 0:
return str(self.re)
elif self.re == 0:
if abs(self.im) == 1:
return f"{'-' if self.im < 0 else ''}i"
else:
return f"{self.im}i"
else:
return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"
def tolist(self):
return [self.re, self.im]
def complex_pow(c, exp, n):
result = Complex(1, 0)
while exp > 0:
if exp & 1:
result = result * c
result.re = result.re % n
result.im = result.im % n
c = c * c
c.re = c.re % n
c.im = c.im % n
exp >>= 1
return result
bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")
'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''
看上去是一个复数域的rsa，泄漏m的高位，但是发现e=3，直接展开
$$ m^3=(a+bi)^3 = (a^3 - 3ab^2) + (3a^2b - b^3)i $$
带入mh的高位，然后在实数处二元coppersmith求解，得到flag
$$ f=(a_h+a_l)^3-(3*(a_h+a_l)*(b_h+b_l)^2)-C[0] $$
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
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
from Crypto.Util.number import *
import hashlib
import itertools
from tqdm import *
from Crypto.Cipher import ChaCha20
import hashlib
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
R.<m1,m2> = PolynomialRing(Zmod(n))
f1=(mh[0]+m1)^3-3*(mh[0]+m1)*(mh[1]+m2)^2-C[0]
f2=(3*(mh[0]+m1)*(mh[1]+m2)*(mh[0]-mh[1]+m1-m2))-C[1]
print(latex(f1))
res = small_roots(f1,bounds=(2^128,2^128),m = 2)
print(res)
a=mh[0]+res[0][0]
b=mh[1]+res[0][1]
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(a + b).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc)}")
复数复数复数
题目描述
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
class ComComplex:
def __init__(self, value=[0,0,0,0]):
self.value = value
def __str__(self):
s = str(self.value[0])
for k,i in enumerate(self.value[1:]):
if i >= 0:
s += '+'
s += str(i) +'ijk'[k]
return s
def __add__(self,x):
return ComComplex([i+j for i,j in zip(self.value,x.value)])
def __mul__(self,x):
a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
return ComComplex([a,b,c,d])
def __mod__(self,x):
return ComComplex([i % x for i in self.value])
def __pow__(self, x, n=None):
tmp = ComComplex(self.value)
a = ComComplex([1,0,0,0])
while x:
if x & 1:
a *= tmp
tmp *= tmp
if n:
a %= n
tmp %= n
x >>= 1
return a
from Crypto.Util.number import *
from secret import flag, hint
p = getPrime(256)
q = getPrime(256)
r = getPrime(256)
n = p * q * r
P = getPrime(512)
assert len(hint) == 20
hints = ComComplex([bytes_to_long(hint[i:i+5]) for i in range(0,20,5)])
keys = ComComplex([0, p, q, r])
print('hint =',hints)
print('gift =',hints*keys%P)
print('P =',P)
e = 65547
m = ComComplex([bytes_to_long(flag[i:i+len(flag)//4+1]) for i in range(0,len(flag),len(flag)//4+1)])
c = pow(m, e, n)
print('n =', n)
print('c =', c)
'''
hint = 375413371936+452903063925i+418564633198j+452841062207k
gift = 8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729+20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171i+22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868j+40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863k
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = 212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103+24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825i+45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125j+96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385k
'''
大概是一个四元数的rsa，先用hint，求解p,q,r
$$ gift=(g_a,g_b,g_c,g_d)=(key_a,key_b,key_c,key_d)* \left( \begin{array}{ccccc} hint_a&hint_b &hint_c &hint_d \\ -hint_b&hint_a &-hint_d &hint_a \\ -hint_c&hint_d &hint_a &-hint_b \\ -hint_d&-hint_c &hint_b &hint_c \\ \end{array} \right) $$
矩阵求逆，得到p,q,r 此时
$$ \begin{gather*} \phi=(p^4-1)(q^4-1)(r^4-1)\\ GCD(\phi,e)=9\\ GCD((p^4-1),e)=GCD((q^4-1),e)=GCD((r^4-1),e)=3 \end{gather*} $$
就分别在p，q，r下用AMM开两次三次方，然后crt得到flag
exp1,求p,q,r
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
from sage.all import *
# Given data
hint = [375413371936, 452903063925, 418564633198, 452841062207]
gift = [
8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729,
20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171,
22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868,
40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863
]
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
a, b, c_hint, d = hint
g0, g1, g2, g3 = gift
# Construct the matrix A and vector B for the first 3 equations
A = matrix(Zmod(P), [
[-b, -c_hint, -d],
[a, -d, c_hint],
[d, a, -b]
])
B = vector(Zmod(P), [g0, g1, g2])
# Solve the linear system A * [p, q, r] = B
try:
pqr = A.solve_right(B)
p, q, r = map(int, pqr)
print(f"p = {p}")
print(f"q = {q}")
print(f"r = {r}")
# Verify with the 4th equation
assert (-c_hint * p + b * q + a * r) % P == g3, "Solution does not satisfy the 4th equation"
# Verify n = p * q * r
assert (p * q * r) == n, "p, q, r do not multiply to n"
print("Verification passed!")
except ValueError as e:
print(f"Error: {e}")
print("The matrix is not invertible modulo P. Try a different set of equations.")
exp2,求flag
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
class ComComplex:
def __init__(self, value=[0,0,0,0]):
self.value = value
def __str__(self):
s = str(self.value[0])
for k,i in enumerate(self.value[1:]):
if i >= 0:
s += '+'
s += str(i) +'ijk'[k]
return s
def __add__(self,x):
return ComComplex([i+j for i,j in zip(self.value,x.value)])
def __mul__(self,x):
a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
return ComComplex([a,b,c,d])
def __mod__(self,x):
return ComComplex([i % x for i in self.value])
def __pow__(self, x, n=None):
tmp = ComComplex(self.value)
a = ComComplex([1,0,0,0])
while x:
if x & 1:
a *= tmp
tmp *= tmp
if n:
a %= n
tmp %= n
x >>= 1
return a
from Crypto.Util.number import *
import gmpy2
import random
def AMM(c,p):
phi_p=(p**4)-1
s_p=phi_p//3
d_p=gmpy2.invert(3,s_p)
l_3=[]
l_3.append(pow(c,d_p,p))
for i in range(1000):
if(len(l_3)>=5):
break
a=ComComplex([random.randint(1,p-1),random.randint(1,p-1),random.randint(1,p-1),random.randint(1,p-1)])
a=pow(a,(p**2-1)//3,p)
a=a*l_3[0]
a=pow(a,1,p)
if(a not in l_3):
l_3.append(a)
l_9=[]
for i in range(len(l_3)):
l_9.append(pow(l_3[i],d_p,p))
for j in range(1000):
if(len(l_9)>=10):
break
a=ComComplex([random.randint(1,p-1),random.randint(1,p-1),random.randint(1,p-1),random.randint(1,p-1)])
a=pow(a,(p**2-1)//3,p)
a=a*l_9[i*3]
a=pow(a,1,p)
if(a not in l_9):
l_9.append(a)
return l_9
p = 63173373914948586508761871207488662566773264479285518327131522282352053209317
q = 80952808249768431401135151583780334402187954631449426293287427758105419709409
r = 79919542113632340528743451299804406313559069843835295267846968468567030982339
e=65547
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = ComComplex([212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103,24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825,45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125,96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385])
c_q=pow(c,1,q)
c_p=pow(c,1,p)
c_r=pow(c,1,r)
d_q=gmpy2.invert(e//9,(q**4-1))
d_p=gmpy2.invert(e//9,(p**4-1))
d_r=gmpy2.invert(e//9,(r**4-1))
c_q=pow(c_q,d_q,q)
c_p=pow(c_p,d_p,p)
c_r=pow(c_r,d_r,r)
m_q=AMM(c_q,q)
m_p=AMM(c_p,p)
m_r=AMM(c_r,r)
print(pow(m_q[0],e,q),c_q)
for i in m_q:
for j in m_p:
for k in m_r:
m=pow(i*ComComplex([(n//q)*gmpy2.invert((n//q),q),0,0,0])+j*ComComplex([(n//p)*gmpy2.invert(n//p,p),0,0,0])+k*ComComplex([(n//r)*(gmpy2.invert((n//r),r)),0,0,0]),1,n)
#print(pow(m,e,n),c)
if(b"fl" in long_to_bytes(m.value[0])):
print(long_to_bytes(m.value[0])+long_to_bytes(m.value[1])+long_to_bytes(m.value[2])+long_to_bytes(m.value[3]))
break
reed
题目描述
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
import string
import random
from secret import flag
assert flag.startswith('XYCTF{') and flag.endswith('}')
flag = flag.rstrip('}').lstrip('XYCTF{')
table = string.ascii_letters + string.digits
assert all(i in table for i in flag)
r = random.Random()
class PRNG:
def __init__(self, seed):
self.a = 1145140
self.b = 19198100
random.seed(seed)
def next(self):
x = random.randint(self.a, self.b)
random.seed(x ** 2 + 1)
return x
def round(self, k):
for _ in range(k):
x = self.next()
return x
def encrypt(msg, a, b):
c = [(a * table.index(m) + b) % 19198111 for m in msg]
return c
seed = int(input('give me seed: '))
prng = PRNG(seed)
a = prng.round(r.randrange(2**16))
b = prng.round(r.randrange(2**16))
enc = encrypt(flag, a, b)
print(enc)
大概有一个随机数生成器，可以自己确定种子，且种子确定的话随机数的序列不变，然后在2**17的范围内选两个数a,b,然后对密文逐字节加密，注意到m是被映射到table上的，及m<62.
可以先随便一个种子，例如seed=0,生成2**17个随机数存入数组，然后c中两两作差，去掉b，爆破a，条件是密文作差在+-62中就行，爆出a再打b就行
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
from hashlib import md5
from Crypto.Util.number import *
import string
import random
from tqdm import *
import gmpy2
table = string.ascii_letters + string.digits
r = random.Random()
class PRNG:
def __init__(self, seed):
self.a = 1145140
self.b = 19198100
random.seed(seed)
def next(self):
x = random.randint(self.a, self.b)
random.seed(x ** 2 + 1)
return x
def round(self, k):
for _ in range(k):
x = self.next()
return x
def encrypt(msg, a, b):
c = [(a * table.index(m) + b) % 19198111 for m in msg]
return c
x=[]
seed = 0
prng = PRNG(seed)
for i in trange(2**17):
x.append(prng.next())
z=[10853585, 10853585, 12411325, 131831, 10853585, 12411325, 5127856, 6685596, 14474296, 17407350, 10488733, 16719693, 9801076, 6685596, 2882459, 5997939, 6685596, 18277433, 18277433, 9801076, 10488733, 8930993, 2882459, 12046473, 17407350, 11358816, 9801076, 12916556, 18277433, 10853585, 8608188, 10853585, 8608188, 1689571, 10853585, 3934968]
y = [(z[i+1] - z[i])%19198111 for i in range(len(z)-1)]
for i in trange(len(x)):
a_=gmpy2.invert(x[i],19198111)
tmp=0
for j in range(len(y)):
m=(y[j]*a_)%19198111
if(m<=62 or m>=(-62+19198111)):
tmp+=1
if(tmp==len(y)):
print(f"a={x[i]}")
break
a=6918617
a_=gmpy2.invert(a,19198111)
for i in trange(len(x)):
c = [(a_ * (m - x[i])) % 19198111 for m in z]
num=0
for i in c:
if(i<=62):
num+=1
if(num==len(c)):
m=[table[i] for i in c]
print("".join(m))
break
choice
题目描述
1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import bytes_to_long
from random import Random
from secret import flag
assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
flag = flag[6:-1]
msg = bytes_to_long(flag)
rand = Random()
test = bytes([i for i in range(255, -1, -1)])
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')
还给了一个random.py来修改了choice函数的作用，经过测试是和getrandbits(8)一样的作用(注意test是倒序，还原就行),然后找到板子. https://wbuildings.github.io/Crypto/MT19937%E5%AE%9E%E6%88%98/ 感谢师傅
exp1
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
from sage.all import *
from random import Random
from tqdm import *
prng = Random()
length = 19968
def myState():
state = [0]*624
i = 0
while i<length:
ind = i//32
expont = i%32
state[ind] = 1<<(31-expont)
s = (3,tuple(state+[0]),None)
yield s
state[ind] = 0
i += 1
def getRow():
rng = Random()
gs = myState()
for i in range(length):
s = next(gs)
rng.setstate(s)
# print(s[1][0])
data=[]
for i in range(length // 8):
data.extend(list(bin(rng.getrandbits(8))[2:].zfill(8)))
data=[int(i) for i in data] # 只有1行，还是length长度
row = vector(GF(2),data)
yield row
def buildBox():
b = matrix(GF(2),length,length)
rg = getRow()
for i in tqdm(range(length)):
b[i] = next(rg)
return b # length * length
# X = Z*(T^-1)
def recoverState(T,leak):
x = T.solve_left(leak)
x = ''.join([str(i) for i in x.list()])
state = []
for i in range(624):
tmp = int(x[i * 32:(i + 1) * 32], 2)
state.append(tmp)
return state
# 根据题型2,还原state,有两种可能,这时候可以用暴破
def backfirst(state):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
tmp = state[623] ^ state[396]
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<= 1
return (1 << 32 - 1) | tmp & low, tmp & low
def pwn(leak,state,guess1,guess2):
prng = Random()
originState = prng.getstate()
state[0] = guess1
s = state
prng.setstate((3, tuple(s + [0]), None))
if True:
print("first")
prng.setstate((3, tuple(s + [0]), None))
now = [prng.getrandbits(8) for i in range(2496)]
if now == leak:
print("true")
print(state)
return
state[0] = guess2
s = state
prng.setstate((3, tuple(s + [0]), None))
if True:
print("second")
prng.setstate((3, tuple(s + [0]), None))
now = [prng.getrandbits(8) for i in range(2496)]
if now == leak:
print("true")
print(state)
return
def main():
T = buildBox()
leak = []
leak1=[int(j) for j in "".join([bin(i)[2:].zfill(8) for i in leak[:19968//8]])]
leak1 = matrix(GF(2), leak1)
# 恢复state
state = recoverState(T,leak1)
print("state恢复完成")
# 两种可能
guess1, guess2 = backfirst(state)
print(guess1, guess2)
pwn(leak,state,guess1,guess2)
main()
得到state exp2
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
state=[]
from random import Random
prng = Random()
prng.setstate((3, tuple(state + [0]), None))
D = [prng.getrandbits(32) for _ in range(624)]
from Crypto.Util.number import *
from extend_mt19937_predictor import ExtendMT19937Predictor
predictor = ExtendMT19937Predictor()
enc = 5042764371819053176884777909105310461303359296255297
for _ in range(624):
predictor.setrandbits(D[_], 32)
for i in range(624):
predictor.backtrack_getrandbits(32)
print(enc.bit_length())
key = predictor.backtrack_getrandbits(enc.bit_length()+3)
print(long_to_bytes(key^enc))
注意异或可能让最高位为零，稍微加几位试试就行
本文由作者按照 CC BY 4.0 进行授权