XYCTF Crypto WP
XYCTF:
1.signin/signin Revenge
经过源码分析，可知此题是个简单的逆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
42from Crypto.Util.number import *
from tqdm import *
import gmpy2
flag=b'XYCTF{uuid}'
flag=bytes_to_long(flag)
leak=bin(int(flag))
while 1:
leak += "0"
if len(leak) == 514:
break
def swap_bits(input_str):
input_list = list(input_str[2:])
length = len(input_list)
for i in range(length // 2):
temp = input_list[i]
input_list[i] = input_list[length - 1 - i]
input_list[length - 1 - i] = temp
return ''.join(input_list)
input_str = leak
result = swap_bits(input_str)
a=result
def custom_add(input_str):
input_list = list(input_str)
length = len(input_list)
for i in range(length):
input_list[i] = str((int(input_list[i]) + i + 1) % 10)
result = ''.join(input_list)
return result
input_str = a
result = custom_add(input_str)
b=result
print(b)
#12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456799123455688902334677801123467889022356679901344568891223566790013455788911245667990234457899122345679001335668890233566789113445789912234568900133566889012456679901245568891223457790013356688911234677801124556789122356678011335668890223467789013445788902335577801123557889112456679901245577801223566890113455689911234677891224556899023
解题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
41from Crypto.Util.number import *
str1="12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567780013445689912234577900123457889012456678001344578891223456790012445788911245667800124557789122355788001234578890133566799013445688902335578800124556899013356678911245567991223557880013345689911235667890134457899122355788001345578890133467780013445778902335667900133556899112456679011344578801233467789112355779912234577990233556780113"
list1=[int(i) for i in str1]
print(list1)
list2=[]
for i in range(len(list1)):
if i%10==0:
list2.append(list1[i]-1)
if i%10==1:
list2.append(list1[i]-2)
if i%10==2:
list2.append(list1[i]-3)
if i%10==3:
list2.append(list1[i]-4)
if i%10==4:
list2.append(list1[i]-5)
if i%10==5:
list2.append(list1[i]-6)
if i%10==6:
list2.append(list1[i]-7)
if i%10==7:
list2.append(list1[i]-8)
if i%10==8:
if list1[i]==0:
list2.append(1)
if list1[i]==9:
list2.append(0)
if i%10==9:
list2.append(list1[i])
print(list2)
for i in range(len(list2)//2):
temp=list2[i]
list2[i]=list2[len(list2)-i-1]
list2[len(list2)-i-1]=temp
print(list2)
str2=''.join(str(i) for i in list2)
print(str2)
leak=0b10110000101100101000011010101000100011001111011001101110011100101100101001100110110000100110010011001000011011100101101001101110011000000110001011000010010110100110100011001000011010001100110001011010110001000110001001101000011000000101101001100010110001000111001001100100011000000110011001100100011100000110000001101000011011000110010011111010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
leak2=int(0b10110000101100101000011010101000100011001111011001101110011100101100101001100110110000100110010011001000011011100101101001101110011000000110001011000010010110100110100011001000011010001100110001011010110001000110001001101000011000000101101001100010110001000111001001100100011000000110011001100100011100000110000001101000011011000110010011111010)
leak1=int(leak)
print(long_to_bytes(leak2//2))
2.happy_to_solve1
1 | from Crypto.Util.number import * |
由于 next_prime(q) 与 q 的差距很小，我们可以通过解方程并稍微爆破一下来做（ p+q 的值可根据异或的特征进行推测）
exp1:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24from Crypto.Util.number import *
from sympy import *
from gmpy2 import *
from tqdm import tqdm
n=24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c=14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
a1=2**512-1
a2=a1+2**513
x=symbols('x')
'''
for i in tqdm(range(10000)):
equation=(-1)*x**2+(a1-i)*x+a1*i-n
solution=solve(equation,x)[0]
if "sqrt" not in str(solution):
print(a1-solution)
break
'''
p=11186104509771514497905845277525414324848282003961401424656189058347435564219816052776565548550435972724614541793612778837623695399649245354880712765072167
q=n//p
e=65537
d=invert(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))
exp2:学长的1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19from Crypto.Util.number import *
from gmpy2 import iroot
n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
pqsum = (1 << 512) - 1
while True:
if iroot(pqsum**2-4*n, 2)[1]:
break
pqsum += 1
p = (pqsum - iroot(pqsum**2-4*n, 2)[0]) // 2
q = pqsum - p
assert n == p*q
phi = (p-1)*(q-1)
d = inverse(65537, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
3.factor1
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14import gmpy2
import hashlib
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
我的解法：
类似 wiener
只不过换成$n^{3}$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
98import gmpy2
import libnum
import hashlib
import random
def continuedFra(x, y):
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
numerator = 0
denominator = 1
for x in cf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
d = wienerAttack(e, n ** 3)
print('d=', d)
k = e * d - 1
r = k
t = 0
while True:
r = r // 2
t += 1
if r % 2 == 1:
break
success = False
for i in range(1, 101):
g = random.randint(0, n)
y = pow(g, r, n)
if y == 1 or y == n - 1:
continue
for j in range(1, t):
x = pow(y, 2, n)
if x == 1:
success = True
break
elif x == n - 1:
continue
else:
y = x
if success:
break
else:
continue
if success:
p = libnum.gcd(y - 1, n)
q = n // p
print('P: ' + '%s' % p)
print('Q: ' + '%s' % q)
hash_result = hashlib.md5(str(p + q).encode()).hexdigest()
print(b'XYCTF{' + hash_result.encode() + b'}')
else:
print('Cannot compute P and Q')
密码大佬糖醋小鸡块是用二元 copper 做的
粘一下他的 wp1
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
67from Crypto.Util.number import *
import hashlib
import itertools
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 []
#part1 get k,p3q3
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
PR.<x,y> = PolynomialRing(Zmod(e))
f = 1 + x * (n^3 - y + 1)
res = small_roots(f , bounds = (2^512,(2^512)^3) , m=7 , d=3)
k = int(res[0][0])
p3q3 = int(res[0][1])
#part2 factor n
p, q = var('p, q')
res = solve([p*q == n, p^3 + q^3 == p3q3], p, q)
#print(res)
p = 9212046353930376594996890089494718736894378991991381248242532319628627449681664076081705664941905594411935750003102856235503684466394327681725704255564467
q = n // p
assert p*q == n
#part3 get flag
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(flag)
#XYCTF{a83211a70e18145a59671c08ddc67ba4}
4.babyRSAMAX
据出题人说我是非预期做法
做法：p-1 光滑+有限域开根
首先观察题目，发现n是p-1光滑数，直接分解，然后求e1
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
48from Crypto.Util.number import *
from gmpy2 import *
from sympy import *
N=39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
n=2
a=2
''''
while True:
a=pow(a,n,N)
res=GCD(a-1,N)
if res!=1 and res!=N:
q=N//res
print(res,q)
break
n+=1
'''
p=236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769440558816351105253794964040981919231484098097671084895302287425479
q=166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176579651490080696973849607356408696043718492499993062863415424578199
print(p.bit_length())
print(q.bit_length())
print(isPrime(p))
print(isPrime(q))
t=65537
y =1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217
d1=inverse(t,(p-1)*(q-1))
phi=(p-1)*(q-1)
x=pow(y,d1,N)
print(long_to_bytes(x))
e=4096
print(GCD(e,phi))
e1=e//4
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
#d2=inverse(e1,phi)
roots = []
roots.append(c)
for i in range(12):
new_roots = []
for r in roots:
new_roots.append(nthroot_mod(r,2,n))
new_roots.append(N-nthroot_mod(r,2,n))
roots = new_roots
if b"XYCTF" in long_to_bytes(x):
print(long_to_bytes(x))
for i in roots:
if b"XYCTF" in long_to_bytes(i):
print(long_to_bytes(i))
break
虽然 gift 没啥用，但 e=4096 ,是个不互素问题，在有限域对其求根1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#sage
c=16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
e=4096
p=236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769440558816351105253794964040981919231484098097671084895302287425479
q=166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176579651490080696973849607356408696043718492499993062863415424578199
print(1)
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()
print(mps)
print(mqs)
#[(236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769404214275971858584747720119200208117068403781208566503489403215434, 1), (36344540379246669047243921781711114415694316462518391812884210045, 1)]
#[(166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176543306949701450304802363434626984929302798183530544471602540368154, 1), (36344540379246669047243921781711114415694316462518391812884210045, 1)]
最后得到的四个中有一个便是答案1
2
3
4
5
6
7
8
9
10from Crypto.Util.number import *
a1=236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769404214275971858584747720119200208117068403781208566503489403215434
a2=36344540379246669047243921781711114415694316462518391812884210045
a3=166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176543306949701450304802363434626984929302798183530544471602540368154
a4=36344540379246669047243921781711114415694316462518391812884210045
print(long_to_bytes(a1))
print(long_to_bytes(a2))
print(long_to_bytes(a3))
print(long_to_bytes(a4))
#XYCTF{Rabin_is_so_biggggg!}
5.x0r
看着复杂，实际简单
简单的交互题
题目：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
42from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
flag = open("flag.txt", "rb").read()
key = os.urandom(16)
iv = os.urandom(16)
flag = pad(flag, 16)
def aes_encrypt(key, plaintext):
cipher = AES.new(key, AES.MODE_ECB)
return cipher.encrypt(plaintext)
def encrypt(key, plaintext, iv):
ciphertext = b""
for i in range(0, len(plaintext), AES.block_size):
key_block = aes_encrypt(key, iv)
ciphertext_block = bytes(
[plaintext[i + j] ^ key_block[j] for j in range(AES.block_size)]
)
ciphertext += ciphertext_block
iv = key_block
return ciphertext
while 1:
try:
print("1.print\n2.input\n3.exit")
a = input("> ")
if a == "1":
print((iv + encrypt(key, flag, iv)).hex())
elif a == "2":
ivs = bytes.fromhex(input("iv: "))
inputs = bytes.fromhex(input("message: "))
print(encrypt(key, inputs, ivs).hex())
elif a == "3":
exit(0)
else:
print("You need input 1,2,3")
except:exit(0)
exp:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
import os
a="b7d9a9bf3c136e95dda7224ef73a40b658c414e8b2813fc9fda207ebcc5e35ed87d5992b58af6e5dcaf40255af12ff0fef07136388bac374771d52b57cf9e9ba"
print(len(a))
iv=bytes.fromhex(a[:32])
cipher=bytes.fromhex(a[32:])
cc=bytes.fromhex(a[96:])
print(len(iv))
print(len(cipher))
key_block=[]
print(cc)
for i in range(16):
key_block.append(0^cc[i])
print(key_block)
key=''.join([hex(b)[2:] for b in key_block])
print(iv)
print(a[:32])
print(len(key))
b="58594354467b61393630323665322d373837322d343439352d383764332d6461343962623232316164617d0a04040404"
print(bytes.fromhex(b))
6.complex_dlp
这道题需要把复数域的运算转到实数域上
解法1:
模长1
2
3
4
5
6
7
8
9
10
11
12from sage.all import *
from Crypto.Util.number import *
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
g = 3 + 7*I
c = 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908*I
F = GF(p)
x = discrete_log(F(abs(c)**2), F(abs(g)**2))
print(x)
# x = 11043386733210093783917591062922767739440701223101839768310052590794700044066655
print(long_to_bytes(int(x)))
解法2：鸡块的解法：扩域1
2
3
4
5
6
7
8
9
10
11
12from Crypto.Util.number import *
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
F.<i> = GF(p^2, modulus = x^2 + 1)
g = F(3 + 7*i)
c = F(5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908*i)
m = discrete_log(F(c^(p+1)) , F(g^(p+1)) , operation="*" , ord=p-1)
print(long_to_bytes(int(m)))
#XYCTF{___c0mp13x_d1p_15_3@5y_f0r_y0u___}
7.fakeRSA
题目：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
26from Crypto.Util.number import *
flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)
G = Zmod(p)
def function(X, Y, Z):
def part(a, b, c):
return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
def parts(n):
Gx.<a, b, c> = G[]
if n == 0: return vector([a, b, c])
mid = parts(n // 2)
result = mid(*mid)
if n % 2 == 0: return result
else: return part(*result)
return parts(n)(X, Y, Z)
print(function(69, 48, 52))
#1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
#(1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246)
这是一个矩阵的 dlp 问题
给出
求 n
关键是把 $A$ 化为 Jordan 标准型
得
然后计算上三角矩阵的 n 次方的通项公式，进行矩阵求解。
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
25from Crypto.Util.number import *
from sage.all import *
p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
K = Zmod(p)
A = matrix(K, [[9, 0, -36], [6, 0, -27], [0, 1, 0]])
u = vector(K, (69, 48, 52))
v = vector(
K,
(1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246),
)
J, P = A.jordan_form(transformation=True)
# A^n*v=u
# A=PJP^-1
# J^n*vv=uu
print(J)
vv = ~P * v
uu = ~P * u
a, b, c = uu
aa, bb, cc = vv
n = (18 * bb * c - 18 * b * cc) / (6 * c * cc)
print(n)
a=11248090436223445352625693407089269386223255468324240386169564292825656540049141991068475773
print(long_to_bytes(a))
#XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}
8.反方向的密码 相思
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from Crypto.Util.number import *
import hashlib
from secrets import flag
def hash(x):
return hashlib.sha256(x.encode()).digest()
def pad(message):
return message + hash(str(len(message)))
m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)
# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243
爆破长度和 flag 头尾可以获得部分明文，然后进行 coppersmith 恢复明文
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
57from Crypto.Util.number import *
import hashlib
from sage.all import *
import string
from tqdm import tqdm
flag = b'XYCTF{You_wi11_b3_b3ttEr!!!let_me}'
n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243
c1 = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
m1=b'XYCTF{You_wi11_b3_b3ttEr}'
m1=bytes_to_long(m1)
c2=pow(m1,3,n)
def hash(x):
return hashlib.sha256(x.encode()).digest()
def pad(message):
print(bytes_to_long(hash(str(len(message)))).bit_length())
print(bytes_to_long(message)*2**256 + bytes_to_long(hash(str(len(message)))))
print(bytes_to_long(message + hash(str(len(message)))))
print()
return message + hash(str(len(message)))
m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
e = 3
c = pow(m, e, n)
c=c1
print(len(flag))
for length in tqdm(range(20, 50)):
PR = PolynomialRing(Zmod(n), 'x')
x = PR.gen()
padding = bytes_to_long(hash(str(length)))
knownprefix = b'XYCTF{'
kplen = len(knownprefix)
f = (bytes_to_long(knownprefix)*2**(256+length*8-kplen*8) +x*2**(256+8) +bytes_to_long(b'}')*2**256 + padding)**3 - c
f = f.monic()
bitlength = length*8 - 1
roots = f.small_roots(X=2**(bitlength-kplen*8-8), beta=(bitlength-kplen*8-8)/1024,epsilon=0.01)
if roots:
print(roots)
print(long_to_bytes(int(roots[0])))
break
print(roots[0])
print(long_to_bytes(int(roots[0])))
#bytes_to_long(i.encode())*2**(256+length*8-kplen*8) +
''''
for i in string.ascii_letters+string.digits+'_':
for j in string.ascii_letters+string.digits+'_':
for k in string.ascii_letters+string.digits+'_':
'''
exp2:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from Crypto.Util.number import *
import hashlib
def hash(x):
return hashlib.sha256(x.encode()).digest()
def pad(message):
return message + hash(str(len(message)))
c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243
e = 3
for i in range(8,100):
end = bytes_to_long(b'}'+hash(str(i)))
begin=bytes_to_long(b'XYCTF{')
R.<x> = PolynomialRing(Zmod(n))
f=(begin*16^(66+2*i-14)+x*16^66+end)^e-c
root = f.monic().small_roots(X=256^(i-7),beta = 0.4)
if root:
print(long_to_bytes(int(begin*16^(2*i-14)+root[0]))+b'}')
9.反方向的密码 情难
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import hashlib
from Crypto.Util.number import *
from secrets import flag
def hash(x):
return hashlib.sha512(x.encode()).digest() * 2
def pad(message):
return (message[: len(message) // 2] + hash(str(len(message))) + message[len(message) // 2 :])
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
e = 2
m = bytes_to_long(pad(flag))
print(pow(m, e, n))
print(n)
# 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
# 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263
与相思类似，不过这里是用二元 copper
就是要注意讨论一下奇偶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
91from sage.all import *
from Crypto.Util.number import *
import hashlib
from tqdm import tqdm
import itertools
c=3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
n=26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263
e=2
def hash(x):
return hashlib.sha512(x.encode()).digest() * 2
def pad(message):
return (message[: len(message) // 2] + hash(str(len(message))) + message[len(message) // 2 :])
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
if isinstance(f, Polynomial):
x, = polygens(f.base_ring(), f.variable_name(), 1)
f = f(x)
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 []
m=b"XYCTF{you_will_be_happy}"
m=bytes_to_long(pad(m))
c1=pow(m,e,n)
for length in tqdm(range(20,40)):
fix = bytes_to_long(hash(str(length*2)))
PR = PolynomialRing(Zmod(n), "x,y")
xx, yy = PR.gens()
f = (bytes_to_long(b'}')+yy*2**8+fix*2**(8*length)+xx*2**(1024+8*length)+bytes_to_long(b'XYCTF{')*2**(1024+8*2*(length-3)))**2-c
try:
x, y = small_roots(f, [2 ** (8*(length-6)), 2 ** (8*(length-1))], m=1, d=4)[0]
x, y = ZZ(x), ZZ(y)
print(long_to_bytes(x))
print(long_to_bytes(y))
except IndexError:continue
for length in tqdm(range(20, 40)):
fix = bytes_to_long(hash(str(length * 2 + 1)))
PR = PolynomialRing(Zmod(n), "x,y")
xx, yy = PR.gens()
f = (bytes_to_long(b'}') + yy * 2**8 + fix * 2**(8 * (length + 1)) + xx * 2**(1024 + 8 * (length + 1)) + bytes_to_long(b'XYCTF{') * 2**(1024 + 8 * (2 * length - 5)))**2 - c
try:
x, y = small_roots(f, [2**(8 * (length - 6)), 2**(8 * length)], m=1, d=4)[0]
x, y = ZZ(x), ZZ(y)
print(long_to_bytes(x))
print(long_to_bytes(y))
except IndexError:continue
10.happy_to_solve2
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import random
from Crypto.Util.number import *
from secrets import flag
def get_happy_prime():
while 1:
p = int("".join([random.choice("123") for _ in range(512)]))
q = int("".join([random.choice("567") for _ in range(512)]))
if isPrime(p) and isPrime(q):
return (p,q)
m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
# 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546
观察 p、q 的生成，这个题可以用 dfs 深搜
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
35from Crypto.Util.number import *
from random import *
from tqdm import tqdm
import random
from itertools import product
n=697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
c=153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546
print(n.bit_length())
def base10(ss):
r = 0
for x in ss[::-1]:
r = r * 10 + x
return r
def dfs(ps, qs, mod):
if base10(ps) * base10(qs) == n:
yield base10(ps), base10(qs)
return
for pp, qq in product((1,2,3), (5,6,7)):
p = base10(ps + [pp])
q = base10(qs + [qq])
if p * q % mod == n % mod:
yield from dfs(ps + [pp], qs + [qq], mod * 10)
p, q = next(dfs([], [], 1))
print(p)
print(q)
e=65537
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
11.factor3
题目：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
31from Crypto.Util.number import *
import random
flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
while True:
x = random.getrandbits(256)
y = random.getrandbits(256)
if y % 2 == 0:
continue
p = x ** 3 + 3 * y ** 3
if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
return p
p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m
print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")
N: 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e: 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
c: 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716
这题是个 paper 题，但也可以不用 paper
用二元copper爆出k和p+q1
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
63from Crypto.Util.number import *
from sage.all import *
n=913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e=494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
if isinstance(f, Polynomial):
x, = polygens(f.base_ring(), f.variable_name(), 1)
f = f(x)
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 []
P = PolynomialRing(Zmod(e), "k,s")
kk, ss = P.gens()
f = 1 + kk * (n **2 + ss * (ss + n + 1) - n + 1)
k, s = small_roots(f, (2 ** 320, 2 ** 769), m=3, d=4)[0] # take ~1min
k, s = ZZ(k), ZZ(s)
print(f"{k = }")
print(f"{s = }")
然后根据推的公式解出d1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from Crypto.Util.number import *
n=913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e=494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
print(n.bit_length())
print(e.bit_length())
k = 1251257306657373659654605739485817595695717202438149781637777849635371292306024253248630690054410
print(k.bit_length())
c=4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716
pqsum= 1925420229022578583406139554581551835655011964695773657501082158233633376833949737222087944109022904389943420455209060081354234597292378923627336957822763834975165642898757928184306157864510241547740313972548801708249946480791494352
d=k*(n**2+pqsum*(pqsum+n+1)-n+1)//e
print(d.bit_length())
print(isPrime(d))
m=d**2^c
for i in range(1000000):
if b"XYCTF{I_love_to_p" in long_to_bytes(m):
m = (d+i) ** 2 ^ c
print(i)
print(long_to_bytes(m))
12.Random_rr
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from Crypto.Util.number import *
from random import randint
flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
def generate():
fw = open("random", "w")
for i in range(648):
fw.write(str(random.getrandbits(32))+"\n")
fw.close()
generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])
ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")
三步走
1.梅森随机数预测
2.反解出 k
3.通过 gcd 求出 m1
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
83from Crypto.Util.number import *
from random import randint
from tqdm import *
from sage.all import *
from randcrack import RandCrack
import re
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [1462227062794249126369859823370329795444295554631867449122519463903085153603985900680740216206168716423777588580245877886440288748604020630699018542826979566965387039050150069523167528973701117587082189067128448763762233651697690088165126309640643249893980922783446939093480513501423929380273397400708296781344423099729594996935151205635124630966978346265570102760841188859706856157965455490428917432012469015925570881840242441646984344205989934223312311722527845, 17436088264981004997841810232705191434707487036117316568031039310756229463817709762330626096875057666532776781413031682988478368320631200639484646124749334955850093397553177978996330881043557698983399584498223222105144624884205328876488334329130830465297477669138121963831402080876078357077714205039964108868193841782271495425644463200232523492344001660692840819160127541347575190224749912289543698786833926857916729347030739521501971908837887266088602825603179428932500122868635833564921115729380769315969449959847532694279060981180556955413680421245680949817931938812637093078177255366095925596232172597647804659446, 169559415577702492912881115171844374594897133030580223300760597578879930554761809414648409965790290108683744070236827542547112767931390381215817208191241194452401715396697138137182840759511035487717013487364495797652031544286820278750675326239062595892448739046788242584477837603604028584783800711126256213550041835365566067529075264741159242623075137208552904103323636912832758118607742414554050834861661347524996361121876885982545956793412777613516967651789645670837406737788560923095674100190720996844931263803247711890541497769408802573382496173181275896304033554412089516486158308042512557770316390458745235174270820619821158359708588836275104941171089532593072639298996037834372691067497283819036389853616602440038642702961597540965107104661813887585271108258467582, 353291124480685802122760873619558181197925748758526501461956322344713145481696018545548833112663130052221102526199589136442461136617134139228771440873303781403752812631064169836368616974931324935659661616432397250323791027357698736360780111349622044193849460721756463896782586060025792712427344165223388631274105033257953386232975622550466772244070538660725769821337872161112606157590652531598571409049763994992112562965984307203582687185746063109802744989804265169651236595150092278455325980064053498109201539606445526852506504951020231421164201055246981085535835484260199043182412639045612970769228962343363308833437852540654614315024696428638587640053405690902605225272716392141318356689485996722112797193445203157167283359129296847476836010747322296658815494204920904679373943240361056289263055689989853602794079068762252790541020355479732830748629340531275553956346072236216251442369981439899969148055895199797337493316, 15179303239962972288090709923258186951958171456436855682777477692171617505348532247047242658368307257431505429176030938743052282481669819891838891541215477308429612423006023438195430836574000543742809228546430000091179899316856488547218901706415026288318088205302049807334703045024896255849147262301854988225565498235577522563864689394270282449494777293613090615435735306391538191861818216934248371120219493426168505800995544058108910908179783162033445093246274431640068273309491502382851514221655427718436104350319852529981208352415296770552441024164515192550794244703092453886081781025084452892498434750021938722777929757172650087934502975720197724550995892550276217204632074271485875928952811717435969392225184804651569530492559664256153442664382496786312755369567453642365570522203867667064702855064117777248996452839510530112258447365219153330364325480082364302480271013963043808407808026617207478317657335771085499907980998058580300198585325142615450209133083897393551483195987009899057506802305527262738968147264513649676062280043385168050292062437784343481003416836360329, 104314025112423274137233712089887942843544143270638359212971052274128269239471444157192816218808079846611202214084249469627150795706839411653429768726632207799788014550224322493762432406192490957609286668132611092680358220234900446241372261756133560546933898911405464919838498505955386741631220042481687693247513434548162014035705016381807652211578605534090062861927303094187322830394428003720849259122728764020582018050036758593860110512593538102856625101436236685192028585785277359733026956010177985114124809725271266235518425292300207754430093643901348424098723963444965623388363705031341005891153453971749807676104809873756494951980451522602316873491452723525098105304097227244362803315664527459814806074055296007282695273078439762481309737546526713550861490435485841202437290236273820499123268038887900937637888673263245804550050225236201356152470642062093953920448272200600863673489805148880500648543349624355627609552339313652249538084845763001317045938369921466480729660920730443079784782692236767617383867121962635468379178835807692901877341892412552450901873955386866840632105626000662355131829735238309392134598804443268332424263236647235664725585301289855948091012922650578186399459695913486992557308313400835129903295472, 4343840077241661846268935044680587301922553038527003445558194299629246437770144538620877381238906692028249854972040151877119476048349008469539245051594012783879085195059417005760769680951795800991838280644405366143799108863486512837967757384337716585187068737628553329955797218927948991807398217726158890043209786493155396314350961622153611660511283644242391666275370968989005241503828383899735010790229677725184129352599961733027673035747501574385230757945287667652891580150423322079486963198642876365246595747082980621374167798723795545482544349625906607527172146616536749758514128592808962495027958181278487153055495228539745094046329616245517171769643273537017191271548980274132500153620316208900769372928143878394476769232210760910446165114726727346459588121745157883051053172477968719246421056145184230282266693069367823549866560055702512612897427682313787206166585448900167833527105055197710187205451619052189815465364328045147326853372540758120163941655690535948810941959546749120505801600233689886118090477238999842117697450804442045413189286597419777550661497797676126492038567180797469427287581550651480006192621101368344597554817693129617367587265330631435038864934907358392135820575836786357021588185619258824320681971817694708190104082162236078675439624893099574428154391060852816948575281188326664739692492957173855447270784701674993602965772572705572236661284175838750276, 33232188464261655563179500532261332740673268011927651630320348613939386668276216461522230721806580297413734568274970935459682942632905228878109266134442095157849521426423087852309281434787500339731212538950209119002423508188676963099974651225610558899243654721531277558550493327350452829753190227897808568073543678269898207509403265336445740620238191925668387207191570780928973245140015529624527394339504110166219539275461482559378890285009329265175900569903390034280071197123026951890243045598372762777194271518734277493717862068019851753397533687634966545727487904367806612431117675184708993348444665119927999157611733751268566184403876833185469516137451908620375918418813671459671015165252098516843945558856771686910403711604755349007547521956309000907909321344073563215005461926587582952949359614987174889724241132421264477252674765866525922832869625858802619129860030857164098812287559445509108640318149480136605636205337149260208047286736509632239281682602528730811378780178290081953095940304361016309200367801327179710042344212586894803008913891990437132132154254944818304511848018157641226316486358816741537666493766664969385708412966038685156129617636758707978377511764106375364810771789547724915964400747168477073598611228354770053945278770974453529085850122110633659583211141893829685722257824029598188511772787791704436267726687275674340238387313917520001746093685584958790950657401396602667943161883455431709467342749040393470692558305012064228847045344065542300917341497880086951027085764240682050347639183710265265174608568581, 444779920211605528457399163778798302264962864500581879449061229089239557061028178632115126869104894859226622560444516783454331855728643653865605416497057611218192216553619406318123596530221714071025603907837449777716507496519968322248412164964314856154515711925650355367893348523307966596574094376371033024957143232394835676102505384939927310874548633276763683911796494980021115548783946752097475837673376331732397502955289357489918575906500096508563791334858578196054364575510262549227364768636710590870090347574179185730720326430135005745433229085504757196383182089273767249820043995239845148428050144582143617569531992315827635029452027206779513658792594533984308575410806115812027902735755703109725290139038156207495514857551309765646867686889984088386887429907974093388131425361751082756577755914020028802552784669428525627343682049455098817841762010840270014859394810253384211716918791183946657609375093285440242734069437770190190813413589772304378568548089845839766313942144795085022405996403115650259032402819679689834193687730312737088900035185810701229565183457677574983602078058685068344436316207621825755389502057132478973466812474466361405511892936227130460055637816125221120263639554189413490859455156262013094121152711225170530206766029467454109467305401401846460468093777715624211347060013862325763649394914935407437210178038317290293919361423759769343159231891689139655490453425886071219512994202371899835337440763173124439640514220811318874946924703189200447691715469272243497270647235873464259786562267062001636730421451659510209634262617060501219332722128011149714434675517928550498574212874429311999930642838137400894349532393752915440919307741932816838690395606129263401130, 7602657349299010857087412189053904610014835470031847851883656349200899897074907434799227128793882909815738193292999732731888978083302895341590290406257165745016960805038897127665671830799203429105439046544232550057709873279272509500788880966204623301536523568757142788616714342396835348896652095993273120352216558215593487864297089604696564960677302089801831232789103069985778444311388865194583877243016764859298874263207514989622286824950955134805871171552294553075628653085978727480483509447782713038101591216015129434695340034230885326874585545666722007375755217543974918948104058213162198622707539613172458718150254646150294432030411829433714905174414616923009739539225989262351006787760054622647363592552091025438151580366414103445836645659713990402360169403016672502089016488614454624878982485618028646781661937237681350359808210590576468884385972827124881157769458685969004277110291444619196405001534224888721294643753150729204059438079951844348808565383170513314781032113884141668626087014977362543472261224194658720773278314480331562064521903562028929772245246023044918780612944818960063465178711539798601604042918647125400052489298307932451350609822767956789584605169244797260390089496546479886501231620453426723358141585623383732719446553408376039010770786422589076208046136110959032740167791347231308499822725649244370210435390174503003095419480360405606956944343844737311175070859345840892142099028930344584283138344997292575870767828146422997758547138227712103360348602516685557024226449188853398358276132193649977284120887692434143592539192811494203655959855535383027295793357853938962196086241223840647731695273486642076372427955673144634441281545597498351950046381851656586528708237353884336502685431879297832928729212632646314921058694911651155140211366665485536218812420299903213130769617228499207211355651173115373832276702819917, 84264285782731568162877315100957489042921709978064128681351268312087746569277269486245900009777400169887830271723552358655565447593550146955011831050100818215000508691318113595184405583164046098487595114378660143656870174865126611342542042359190092909153954755450866325242940723529598062222899187359928557844177883049590925651498994463750219753412624841866695746278533280094878847475236701017015819139013181859456526369446971330754812310385508018904191327621492159168820784532796330689921699298448074204812463376397381282323119448865011664447416851175564248969000702694318145335362835482058897168517488161967391334177372697703315388808719141005307789457461912851355132825731054246686755461163054191160703614564317990818604434605413936738139726767800963911739280012496306857434637923374480459728565199969705867209254398601345461449150134011614149873500167983320745189254670021733091744167981087834156449345560645456017335407633688885028006913440590401180339340613693275890333649989994343631183579024732181147263210054753733928915807504572214832934722959416211618552311628264441740006263506928574652072303741962304773970001278403931114817733924209744938397932123215729579525983133592585604481836441256004482294972680139829929612014077833332681473454850703790455910234390018139844986977475904490461864701830158535403553678623812164036013559496102371103327886019446045373299153105962515417300141416878319759519389540938146354852993808369804508844242989928184577744636058484630309125804687764207122455205953467056765480238519667329086954915863584834116160428194118255018588109352554311335461224660821734294806261011545470878130619510996578906865491369421849868743287382195889612248362671647411387033198694140556943015854769888065336118318462104334038850907108272666824691321243254155599118711741561988645703051401242347980726593263524750481061186510425684386819376145632247818469939222055128225225680599982324030716227856712465076900465158037591919290264095582887285060549164180202017670962738795868581166749, 86875322477430958180737121081750310417552562568937472111462285494068077044224883282734365519155742412567742579384640688864318774506290688726649362821127869025823526558190891391368772700819437828837459806248988365684079824273784568628472269256575474035185709547347651993828702097549741334374364807937523943589572886556418546138161477442285095981598112603569341799645993286627117775387075506854483018231019196901947857611575841702330988975450215180893407629689116208362182111134678579611569697431926172879405158644545853375597102146456828749129737059398592090470207221930164907529449914731078780527501106015075222892079609819142004929517650214077829963858911041047626149998836986070729125260139028680402532903187215589441565748744974914634384575746331436503499349361029226889115930910170650991829637232214683931349631413139076186550993209917767820494311457665926894684877305970805039969582722809409057884485422798810134923124618610122219627418825157655548696504402394251875250216209088386596839289090205455355830326463145513637140192806838161127837601889645337809125003492037067870634529636104813436961659217629590299188696646907180990318511335172435862882285594729483438730028804396906143686407113299921602779063868388165847291926366314379673487291861917979020712234162374569910970226596823115360201748087179946804305525598669650976080327154187180758461602309422875784085236535569730334773176739598656049048170461638432200220436248431274572686422522379720157015816524948018313551155878299198696729645812418550240418562460968434597425565276688472550697127256796390159826046074365566403255645195972270118195562599397495009632518911353576570958767630794735474661250425256764192128158589944999335063602995713281667673220224066976800182326927451684095263096450327503087613798593569273550869670074927576509772147487168451681956168877773772760560498198909642263656809675890678191288443016329637625633073593034921242604872479828009991046383160941673220022936977188891725330716968754725864852252393788824966035242075304806536640145214252474418277831012513594308952183851343958969850677298051187040013011759593833806518361877966381266531975488250988830914527197364101, 12512746540434506671622137154487272479684301796741804852784466276118318939301642459078381853231258719083628458347218300308117654564963998239910113998177176145693597297093613404613373790353962391872079537076763899617842035568892498763955045462691124784114867824842208398619557012590225397311703746359043524766454656517843775988786861851276648768563329960194176509861369794873055457605566481169738163028805838726245153501259733517437071411250664053003146288253452678594410757071147688309902950173685554263072263315677468119998237322488014934897657616287531839226555887811741614460852594517274931125186552830901907056814814364537922270306184144816527619368461860735029130410855453249885989873125086119053183377748071520492963343904276809950936122217011456932719335145019854799217844683275916251254411759723367406995497382110560047670724344385060716483035502136838796674166618447372318994376720742190789098253575402714952812659933854943786548064525033834188130429821475033759906784746466100360319090217901641302494652036828536156345999295944207311903908579168517843644212223034389569172093947663228241575508427027088548956357607118349234005954956185598117597472201788146015733232957686350215358611056864787006128071212201859644019363381882103578216957110324101802774053325622415064181605199128828290427210592657379567354577480538732546950307498243047731412124485919082022649710227773753299708907420377570860905912772090222116049362619789689065827376289781835174416236170541192824551498867290178284835242340226614885213085297034699023207334693204443834177633980478287732765627349487390651101805889417613406850491982522373652059294595205056982377527663490663856624298132703619405155068989422975395069609806200717991260670611916599446743505075260280455301127997860556855773088502432536965641419712974469765402344889497455850368646912720700712406187148014080534412935202873400913358906387215078903911309526903672652336133008199048483053203616435313691633319058270312626100467991257715266040851461069620411861732977165671779365665772314236597023035647614424138241559672376552675319414807273488451981119673616629216737966281726964723616994609707694019677386869057732381647985259361201436431774138127924914503212637589804812882400769493547225221791707699401249315407469433861394473469478007958068015775562155959407640271035, 8708772086314275150137563047822324600135662221530061604490923488781196834561031216119766508710300439592586098337033648172158478037428422016638015261006654452028325941079516640378163094114359263904509663697697446450829644183714138570138053299079111099978730162273301464139950471846002885912898793623780911069208262571511170830772519224286142285588233365329150597172851602037056835267890472296625561911616145092230018104567552026345101742597268103327522556484095066615892886223565058357363680363535631942614863586767642475310674520180258183502370763782154430809207907408245635540513317210636762204031484268471851140728225200408406477879491421034411771595550287534644492458168126531514396470443302572852034873709549055869547530655956369042654261333529517571359153739442787262860093740661118519451621018435524810049086927689546375333874177211297659402716374232772574921960004351227056283357373573456626553641214672035447396850649297539465342595024155246359918811294045883925114447310675847751632815638598802360958589640694941216735143869543493813631906641446867757344570346832228628926669569641235390679032157550781745139542693343976899951858605641387961226781860479580622706408871423958897669045935376111333791269969907893321496309204776813332733513920276388085041994007557204267637656364577970814757016037506402807507663275686948184629913418881333357288030576799576733495401166943446587740185387874828772125373722620767643073868513719861621143440955960613060364895903611801265463530162601221089578458698304546551933625165213065587195349408747310822367615685148092899114446129224352042234315865770543693346677200293484242331181710417082363209828386909100998998888639900536186820795298321286714108461675397032864388542110213210827364423163325349547591341479159200210127489502278231430650721377665744894470461939053982524090875574789651853588962397719426413835176058841208314719781852021952695059793831541054574871680705012400864629090745303863048197498118155019461006670125137061405464976922277176269488571398394629261276128473896794210626729855368774199524936087915252643083350806653978162434973122894687105799198912067140963567030871513363285565713597188757003358857092315759659368775879258759880919191003344516366609757523241375325301693755640462733509474415702644254270875174073203609818099246161951619877073996976627155333499346477458629618081495288947853190429723736471113704267980053978389993182103772852202476116179106939188158462552458652108321980165243577989, 600670032931697501164308145888014197492570434182237560158362504047400318743985557099146474331125213856150404793770533457208418057346330441677143608228832189090853249915025345091440471977572520377721353552421230209210878714408072035504562082229497678931477951277415656323261513473676851714174232119110952631892409156281805902829840067360861715042158260954202580085062540987292060373485291126788640037325353253582263912429148264582730931166497761524857603024286533377786733733569503217095911870554634981195459051734711257551318783862993538532061516918229242512785148483203666879172553287417202171558010581931339490420944579378230441427075256586289381172933294401587550551868745979621899498946185449116142910195187754784531077545817750030440559239594200572501795505647816820925940699189807911408560014741609936565474163109147615538288077368434085501495660339791023107653834631734799739401195331082524762689829404043854362928974818455326969933539941993127168162613893714556812406931262398133232164550840686759286879519200522303631666340760585955445333243578595829239195345013932609791828394260147075352440178009791316103080071026057431465935054583990885807722362958473601534263884483797804520563080119843829936517581710475224995487406412704094626227661853966476374689727423649602092208013642493973696165953898208578723428386172214500367650457610332358123936218429284291631085293746168516063238704669713654100448973473107547290896972051178145687724778934856166935295480879225802399479077346027327314330339492654814903821691676533513420126315351413897998334933276481425781316933061160336396245725800475529909180155168951048807842776329370733724945778641650510054608686950632422179126803289332576361096595524712081770649946303450447653874189205658344800236157548893404541684986435295108661952487239009695950009496079506381196591935645314690427759872790821975631216132209928929354223296595481820239561580620161078572691513920025180731146443551810374070796784563832569069540610771634802811283644303060748631402280436293606074124845116433560780371614622560694771710506136314406382632695962443912413902134325317328060708301892967007571381754948796760722223816096248930178117187568894324829422197591098693433015570587292619159140504205675563120383480457405492676888099039922054652604691220210221980510833810667665873272200431377635693722100801416566512889633584494029920362450447581541351127279435858414431885445382278645820452301854483001535497815948240428726604118517960146521827602352741617814422650606656703172306618878677224079000419335204662784233051630328692085443396990051814696765167700904476881356841198817297213897315038, 16802200282185468546709956092597774740677661549186109526956115242473121883967931163131646187704424819015848998645400207990914089013740921040117435052153841770979793783160919446710908856026577921822303736856837341534046856200378566367573847587481842033197417244157615430123019293064402352517730950287717412467467865654183120580805017956735624709774788608215096623799957840473617022005811932787883583498153009349216019520591315741115282954188920266939008472763372248700697866120997747281838993436471646694877967037584713292557154069090849429661358360669249141411401563354311865086301325223201338603660585063135197133579821848197298915130533944228373462645556131332664180638837298172981687095294316288287474397100963640912775346092923086826604630609655904543259441330900502644107449819662176812660489691326329405408557397950478553867742426469439899689820127149948041436799921133103166748621889384866646157787616184868217116001323368301878471584588973680319019047080248726830275150507574175166679909676797693790108124055103246880427997452475987304179562314626608037471679968401792562140826537740199515244895441348559877458197387323837253170889409923432265627983693113613925422770696270052261532295092167140744798998616784973950454662490861686686088097664631333759768155114942862532519746034900590201459240562835926241941887144381202153705241903628166984657567323072355632922438685555213721062141830979317585407175747781177680148572415131107678588710821046069788978524572240303124373546329950302755883009871688891897763945611072996185025629828607383345003927868697847599452468428107980542821610672736393669832455756995387290606284835293616942665638848969022879828703775592928644725559259945529304050112289143946763124018433851771902626785481385869955110673938215223622863613678412315324306153440766902206001688838913230436350171971289551619865068519200736270652193304810653015371888594169504114520468603987418351580463962583790787745908309177358777801427510313483309516938585851407176405272323275406264541269998648558076115710572739949113174179063104037408892800012305672645293826133157192205750448664938758484140537975600112928783731131731160554472918720908169457539285420601699964488745103603485765360051670848460168635009550254451173622724686795853530317243637913985666214527422655976232855531815124677038149005239212580323707459514903671850604938595975480625971419288321333482646971954799306704972896590507695031753549266109898497496991269990475759448688581247659517684220339086012734812415537965920455360852739093844076811759759173303373454199660054006117215442176739570999154607921395801738324345694513716171731402600767074759488172948500119306978382635362273371756452203795420879806823382694171689272398990752964743539328906992588078386684970091097095002524822271111900103]
c1 = 363788646363430038957594782766177313516930410013028761096125449525352900311987342432332707389678725464245570305442656091083147693929633253905472222223119105496597576680892700795690978029583841539541374381306488238546636925041645743837795052980068923686651284191050257037214462852085566417008362992641640639862428112228493556483476170926590723955399664612288121797929235261679990399185352352544286959163976884867676390120340127790862048627561021372508575978346406322179713972665443056495181281314029605259955375166316993493231524529034376084736285226932730392410446057610167031627686895389188357267336304140707750661551754532703726810046229782522509583068679068266026330534604220136448779670239303044844594369863033342562614954908580980797071779438702134548396966154384817728024762723793272143181635940946334888845065820620182286804643281323447179363272699368386379953273502775010659085362938622805062632668642982294663858335244396163857338508227323801751681995976156487970781553331051080424612021398707159108830544940316009623664909356175231889874464365926612039289520439021685692867423908585449824825323639525381296026274686349117857285659369998795553471936274903352010099265109629071229881541531543477669574187083631324785284254322
c2 = 408184822131518156560324293475775283916865330287271026174896526350123511666895281956297307670862799857291692050125369779347444868678108319280695068081984027607535529170555137883873801205238074937937942433229726545428621408643537931796698659949811571615439710035675674461716185346635792745790874541046465708604310892716226150611709100803537856333225160587696062166931121471905405372834167788843039506170303362597157739646424300148724721973787617390725217064863182798206515059995025139870581046657455818390197378360718268577414540468313327849155326977072599665355467818781585456624519602844435476444300792593181233725708809256956289242348798772583396011536497809799519543692707372931861510836406771810916160714625641110048105945905698555148489134800297890071585166636593108936219686471652288476546797128397632673886639590166634763861905600305344338904568157848336645918449260801970498973364463883003344546391045331665345600454985730993059182020185438557159428617482719829271986950641093353253897984198499501965120625507862855814501340943227107501804839977088104677785444986972836309787440401273632064782837200999263612507784233705263545942160822597103292282242714942650302979883274746718391358487897324158260429570732440514025523470979
final = []
s2n=lambda x: [int(x) for x in re.findall(r"\-?\d+\.?\d*",x)]
f=open("./random.txt","r").readlines()
random1=[]
for i in range(648):
random1.append(s2n(f[i]))
random2=[]
for i in range(648):
random2.append(random1[i][0])
#part1 dlog by p-adic
#part2 HGCD
def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x**m)
b_top, b_bot = b.quo_rem(x**m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x**(m // 2))
e_top, e_bot = e.quo_rem(x**(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11
def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)
rc=RandCrack()
for i in range(624):
rc.submit(random2[i])
for i in range(25):
key=rc.predict_getrandbits(32)
key1= int(str(key)[0])
print(key)
print(key1)
for i in trange(16):
R = Zp(rr, prec=i+key1)
x = (R(ks[i]).log() / R(69).log()).lift()-key
final.append(x)
PR = PolynomialRing(Zmod(n),'x')
x=PR.gen()
f1 = sum(k*x**i for i, k in enumerate(final))**((1<<7)-1) - c1
f2 = x**((1<<16)+1) - c2
f2 = f2 % f1
res = GCD(f1,f2)
m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
if b"XYCTF{" in flag:
print(flag)
13.重生之我要当oi爷pro
题目：1
2
3
4
5
6
7
8
9
10
11
12
13def f(a, b, p):
t = 0
for i in range(len(b)):
t += pow(a, i, p) * b[i] % p
return t % p
p = 1041231053
a = open("flag.png", "rb").read()
b = open("enc.txt", "w")
for i in range(len(a)):
b.write(str(i) + str(f(i, a, p)) + "\n")
这个题一看就不像 CTF 题，倒感觉像 ACM 题，我是用拉格朗日插值做的
跑了很久
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
27from sage.all import *
from PIL import *
import re
import tqdm
import io
p=1041231053
s2n=lambda x: [int(x) for x in re.findall(r"\-?\d+\.?\d*",x)]
f=open("./enc.txt","r").readlines()
b=[s2n(f[i])[1] for i in range(1214960)]
#b=vector(GF(p),b)
def special_lagrand(p, n, ys):
PR=PolynomialRing(GF(p),'x')
x=PR.gen()
res = 0
F = GF(p)
cst = prod(F(0-_) for _ in range(1, n))
basep = prod(x-_ for _ in range(0, n))
for i in tqdm.tqdm(range(n)):
if i:
basep = basep * (x-(i-1)) // (x-i)
cst = cst * i * inverse_mod((i-1)-(n-1), p)
res += ys[i] * basep / F(cst)
return res
a=special_lagrand(p,1214960,b)
print(a)
p=open('plain1.txt','w')
p.write(str(a))
第二步：补 01
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
61import re
from Crypto.Util.number import *
from tqdm import tqdm
s2n=lambda x: [int(x) for x in re.findall(r"\-?\d+\.?\d*",x)]
f=open("./plain.txt","r").readlines()
a=[s2n(f[0])]
print(a[0][2])
print(len(a[0]))
for i in tqdm(range(1,2429900,2)):
if a[0][i]-a[0][i+2]!=1:
flag1=a[0][0:i+1]
flag1+=[0,a[0][i]-1]
flag1+=a[0][i+1:]
a[0]=flag1
i-=2
print(len(a[0]))
e=open('plain1.txt','w')
for i in range(len(a[0])):
e.write(str(a[0][i]))
e.write(",")
#print(chr(0))
''''
for i in tqdm(range(0,len(a[0]),2)):
flag.append(a[0][i])
print(flag[0])
print(flag[-1])
print(len(flag))
b=''.join(chr(i)for i in flag)
c=b""
for i in b:
d=open('flag2.png','wb')
d.write(b)
'''
''''
for i in tqdm(range(1,2051975,2)):
if a[0][i]-a[0][i+1]!=1:
flag1=a[0][0:i+1]
flag1+=[0,a[0][i]-1]
flag1+=a[0][i+1:]
a[0]=flag1
print(len(a[0]))
e=open('plain1.txt','w')
for i in range(len(a[0])):
e.write(str(a[0][i]))
e.write(",")
for i in tqdm(range(0,len(a[0]),2)):
flag.append(a[0][i])
print(flag[0])
print(flag[-1])
b=''.join(chr(i)for i in flag)
c=b""
for i in flag:
c+=long_to_bytes(i)
print(c)
d=open('flag2.png','wb')
d.write(c)
#p=open('plain2.txt','w')
#p.write(a)
'''
第三步：提取系数并生成图片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
56import re
from Crypto.Util.number import *
from tqdm import tqdm
s2n=lambda x: [int(x) for x in re.findall(r"\-?\d+\.?\d*",x)]
f=open("./plain1.txt","r").readlines()
a=[s2n(f[0])]
print(a[0])
print(len(a[0]))
flag=[]
#print(chr(0))
for i in tqdm(range(0,len(a[0]),2)):
flag.append(a[0][i])
print(flag[0])
print(flag[-1])
print(len(flag))
c=b""
for i in tqdm(range(len(flag))):
c+=long_to_bytes(flag[len(flag)-1-i])
d=open('flag3.png','wb')
d.write(c)
''''
c=b""
for i in b:
d=open('flag2.png','wb')
d.write(b)
'''
''''
for i in tqdm(range(1,2051975,2)):
if a[0][i]-a[0][i+1]!=1:
flag1=a[0][0:i+1]
flag1+=[0,a[0][i]-1]
flag1+=a[0][i+1:]
a[0]=flag1
print(len(a[0]))
e=open('plain1.txt','w')
for i in range(len(a[0])):
e.write(str(a[0][i]))
e.write(",")
for i in tqdm(range(0,len(a[0]),2)):
flag.append(a[0][i])
print(flag[0])
print(flag[-1])
b=''.join(chr(i)for i in flag)
c=b""
for i in flag:
c+=long_to_bytes(i)
print(c)
d=open('flag2.png','wb')
d.write(c)
#p=open('plain2.txt','w')
#p.write(a)
'''
exp2:picoCTFwp的优化（直接粘鸡块佬的wp了）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
73import multiprocessing as mp
p = 1041231053
X = []
Y = []
for line in open(r'D:\CTF_challs\py\crypto\2024\XYCTF 2024\encoded.txt', 'r').read().strip().split('\n'):
x, y = line.split(' ')
X.append(int(x))
Y.append(int(y))
K = GF(p)
R = PolynomialRing(K, 'x')
def compZ(X):
x = R.gen()
Z = K(1)
for xk in X:
Z *= (x-xk)
return Z
def comp(X, Y, Xother):
Z = compZ(Xother)
Y = [y/Z(x) for x, y in zip(X, Y)]
return Y, Z
def solve(X, Y):
n = len(Y)
print("Solving for", n, "points...")
# just use lagrange interpolation if the degree is small enough
if n <= 10:
return R.lagrange_polynomial(list(zip(X, Y)))
nhalf = n // 2
X1 = X[:nhalf]
Y1 = Y[:nhalf]
X2 = X[nhalf:]
Y2 = Y[nhalf:]
# parallelize the computation of the two halves
if nhalf > 10000:
with mp.Pool(2) as pool:
result1 = pool.apply_async(comp, (X1, Y1, X2))
result2 = pool.apply_async(comp, (X2, Y2, X1))
Y1, Z2 = result1.get()
Y2, Z1 = result2.get()
else:
Y1, Z2 = comp(X1, Y1, X2)
Y2, Z1 = comp(X2, Y2, X1)
# solve recursively
f1 = solve(X1, Y1)
f2 = solve(X2, Y2)
# put it back together
return f1*Z2 + f2*Z1
def test():
Xt = X[:1000]
Yt = Y[:1000]
f = solve(Xt, Yt)
for x, y in zip(Xt, Yt):
assert f(x) == y
test()
f = solve(X, Y)
with open("111.bmp","wb") as tt:
tt.write(bytearray(f.coefficients(sparse=False)[:-1]))
exp3:正解：多项式插值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
150from Crypto.Util.number import *
import collections
class tree(object):
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def printAllLine(self):
q = collections.deque() # 先进先出队列
q.append(self)
line = 0
pre = 1
nxt = 0
while pre:
for i in range(pre):
node = q.pop()
if node.left != None:
q.append(node.left)
q.append(node.right)
nxt += 2
print(f"Node {line}-{i} = {node.data}")
pre = nxt
nxt = 0
line += 1
print()
def printAllNode(self):
q = collections.deque() # 先进先出队列
q.append(self)
line = 0
pre = 1
nxt = 0
while pre:
for i in range(pre):
node = q.pop()
if node.left != None:
q.append(node.left)
q.append(node.right)
nxt += 2
print(f"Node {line}-{i} = {node.data}")
pre = nxt
nxt = 0
line += 1
print()
def printAllNode(self):
q = collections.deque() # 先进先出队列
q.append(self)
cnt = 0
while len(q):
node = q.pop()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
print(f"Node {cnt} = {node.data}")
cnt += 1
def getMulTree(ls, l, r):
# ls 为以 x-i 为叶节点构成的乘积树
if l == r:
return tree(ls[l])
else:
mid = (l + r) // 2
ltree = getMulTree(ls, l, mid)
rtree = getMulTree(ls, mid + 1, r)
tr = tree(ltree.data * rtree.data, ltree, rtree)
return tr
def getMul(ls, l, r):
# ls 为以 x-i 为叶节点构成的乘积树
if l == r:
return ls[l]
else:
mid = (l + r) // 2
ld = getMul(ls, l, mid)
rd = getMul(ls, mid + 1, r)
return ld * rd
def poly_eval(pol, lx):
# lx 为因变量列表, 元素类型为 int
def dfs(node, res):
if node.left:
(node.left).data = node.data % (node.left).data
(node.right).data = node.data % (node.right).data
dfs(node.left, res)
dfs(node.right, res)
else:
res.append(node.data(lx[len(res)]))
# 构建乘积树; pol 是关于 x 的多项式环
print(f"[+] get multiple tree")
polx = [x - i for i in lx]
tr = getMulTree(polx, 0, len(polx) - 1)
tr.data = pol % tr.data
res = []
dfs(tr, res)
return res
def mergeMul(v, polx, l, r):
if l == r:
return v[l], polx[l]
else:
mid = (l + r) // 2
f0, M0 = mergeMul(v, polx, l, mid)
f1, M1 = mergeMul(v, polx, mid + 1, r)
f = f0 * M1 + f1 * M0
M = M1 * M0
return f, M
# sage
from time import *
lx = []
ly = []
for line in open('C:\crypto\\enc.txt', 'r').read().strip().split('\n'):
x, y = line.split(' ')
lx.append(int(x))
ly.append(int(y))
p = 1041231053
Zp = Zmod(p)
P.<x> = PolynomialRing(Zp)
# 得到 M(x)
print(f'[+] geting M(x)')
st = time()
polx = [x - i for i in lx]
Mtree = getMulTree(polx, 0, len(polx)-1)
M = Mtree.data
print(f'- cost {time() - st} s\n')
# 得到所有 M'(xi), vi
coff = M.list()
M_ = P([i*coff[i] for i in range(len(coff))][1:])
st = time()
print(f'[+] geting M\'(xi) and vi')
Mxi = poly_eval(M_, lx)
v = [ly[i]/Mxi[i] for i in range(len(ly))]
print(f'- cost {time() - st} s')
# 计算 f(x)
print(f'[+] calculate f(x)')
f = mergeMul(v, polx, 0, len(v)-1)[0]
fs = [i for i in f]
wo=open('C:\crypto\\flag.png','wb')
for i in fs:
wo.write(long_to_bytes(i))
14.*happy_to_solve3
题目：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
30import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
n = 1024
rho = 2
gamma = 0.352
delta = (1 - gamma) / 2
def get_happy_prime():
p = getPrime(n // 2)
q = getPrime(n // 2)
N = p * q
if 2 * q - p > gmpy2.iroot(N, 3)[0] and 2 * q - p < int(N**gamma / 16):
d = random.randint(int(N ** (delta - 0.001)), int(N**delta))
e = gmpy2.invert(d, (p - 1) * (q - 1))
return N, e
N, e = get_happy_prime()
m = bytes_to_long(flag)
print(N)
print(e)
print(pow(m, e, N))
# 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
# 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
# 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357
这个题一看，无论是 wiener 还是格，界都无法满足
所以应该是 paper 题，但当时没找到
是这篇文章：”Revisiting Wiener’s Attack– New Weak Keys in RSA*”
使用 paper 的 exp 回头再补
exp2: 糖醋小鸡块佬的方法：通过题目条件已知高位带入 boneh and durfee 求解
粘一下大佬的wp1
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296from Crypto.Util.number import *
import itertools
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = False
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print (a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print ("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ)
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print ("failure")
return 0,0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)
# check if determinant is correctly bounded
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print ("We do not have det < bound. Solutions might not be found.")
print ("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print ("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)
# LLL
if debug:
print ("optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug:
print ("LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print ("looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print ("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print ("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print ("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
#
return solx, soly
nbit = 1024
n = 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
e = 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
c = 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357
import gmpy2
qh = int(gmpy2.iroot(n//2,2)[0] >> 360 << 360)
ph = (n // qh) >> 360 << 360
#part1 boneh and durfee to get d
if(1):
m = 3
delta = 0.33
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(n^delta) # this _might_ be too much
Y = 2^360 # correct if p, q are ~ same size
A = (n+1)//2 - (ph+qh)//2
PR.<x,y> = PolynomialRing(ZZ)
f = 1+x*(A+y)
res = boneh_durfee(f, e, m, t, X, Y)
print(res)
#part2 get d
res = (11905625603785812461702294975756895543980946484478574101835243414442286593759448613358049647316155274, 152665725363549086276160040606397627101715395584023352342706962320368673856094243978666140464721353176202314)
k2 = 11905625603785812461702294975756895543980946484478574101835243414442286593759448613358049647316155274
pl_ql = 152665725363549086276160040606397627101715395584023352342706962320368673856094243978666140464721353176202314
d = (1+k2*(A+pl_ql)) // e
print(len(bin(d)))
print(long_to_bytes(int(pow(c,d,n))))
#XYCTF{68f1880cdafd99fbf9a156946cb39dd86477886f1d115636e149e12c16f99af0}
15.*easy_ecc
题目：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
48from Crypto.Util.number import *
from hashlib import sha256
from secret import flag, secret,SECRET
assert flag[6:-1] == sha256(long_to_bytes(secret)).hexdigest().encode()
class ECC_easy:
def __init__(self):
self.a = 1365855822212045061018261334821659180641576788523935479
self.b = 17329427219955161804703200105884322768704934833367341
self.p = 1365855822212045061018261334821659180641576788523935481
def add(self, P, Q):
mul_inv = lambda x: pow(x, -1, self.p)
x1, y1 = P
x2, y2 = Q
if P!=Q:
l=(y2-y1)*inverse(x2-x1,self.p)%self.p
else:l=(3*x1**2+2*self.a*x1+1)*inverse(2*self.b*y1,self.p)%self.p
temp1 = (self.b*l**2-self.a-x1-x2)%self.p
temp2 = ((2*x1+x2+self.a)*l-self.b*l**3-y1)%self.p
x3 = temp1
y3 = temp2
return x3, y3
def mul(self, x, P):
Q = SECRET
x = x % self.p
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q
def ispoint(self, x, y):
return (self.a * x ** 2 + x ** 3+x) % self.p == (self.b * y ** 2) % self.p
ecc = ECC_easy()
LLLL = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
assert ecc.ispoint(LLLL[0], LLLL[1])
END = ecc.mul(secret, LLLL)
print(END)
# (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)
当时转为正常的椭圆曲线后发现是奇异的，然后就不太会做了
还是粘一下大佬的wp1
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
49from Crypto.Util.number import *
from hashlib import sha256
A = 1365855822212045061018261334821659180641576788523935479
B = 17329427219955161804703200105884322768704934833367341
p = 1365855822212045061018261334821659180641576788523935481
#part2 map to ECC
F = GF(p)
a = F(3-A^2) / F(3*B^2)
b = F(2*A^3-9*A) / F(27*B^3)
def edwards_to_ECC(x,y):
x3 = (F(3*x) + F(A)) / F(3*B)
y3 = F(y) / F(B)
#now curve is y^2 = x^3 + ax + b
return (x3,y3)
G = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
mG = (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)
G_ecc = edwards_to_ECC(G[0],G[1])
mG_ecc = edwards_to_ECC(mG[0],mG[1])
#part3 singular curve attack(map point to Fp)
P.<x> = GF(p)[]
f = x^3 + a*x + b
print(f.factor())
alpha = -544257272453066077953551360625531658485543339865638914
beta = -277341277305912905111158613570595863670490108792657653
def map(x, y):
r = F(alpha - beta).sqrt()
t = F(r * (x - alpha))
return F((y + t) / (y - t))
mg = map(mG_ecc[0], mG_ecc[1])
g = map(G_ecc[0], G_ecc[1])
m = discrete_log(mg,g,ord = p-1)
flag = b"XYCTF{" + sha256(long_to_bytes(int(m))).hexdigest().encode() + b"}"
print(flag)
#XYCTF{ec9a6e17537e81b7f593f65f7e2ca5d575e6b34c504c24e4afb40c1e9dc4be0d}
16.*new_LCG(还没看)
题目：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
63from Crypto.Util.number import *
import random
from secrets import flag
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
class LCG1:
def __init__(self, seed, a, b, m):
self.seed = seed
self.a = a
self.b = b
self.m = m
self.sum = 0
def next(self):
old_seed = self.seed
self.seed = (self.a * self.seed + self.b * self.sum) % self.m
self.sum += old_seed
return self.seed
class LCG2:
def __init__(self, seed, q, A, B):
self.E = EllipticCurve(GF(q), [A, B])
self.P = self.E.lift_x(seed)
self.b = self.E.random_point()
def next(self):
self.P = self.P + self.b
return self.P[0]
a1 = random.randint(1, p)
b1 = random.randint(1, p)
seed1 = random.randint(1, p)
lcg1 = LCG1(seed1, a1, b1, p)
c1 = []
for _ in range(10):
c1.append(lcg1.next())
a2 = random.randint(1, q)
b2 = random.randint(1, q)
seed2 = random.randint(1, q)
lcg2 = LCG2(seed2, q, a2, b2)
c2 = []
for _ in range(10):
c2.append(lcg2.next())
c = bytes_to_long(flag)
e = 65537
print(n)
print(pow(c, e, n))
print(c1)
print(c2)
# 942554394956393500634473023924044851150783066435925660508624376974971108656861080872622432250172571195245180102507380675343264066303507696268870722959770362631674931170602993210221083436437860191861911457384526742569208842886612504579678703976889217504241741044075116270718940025586448491942058697669033418724145042156461740336592337509609124425828725269151627786668070531098444935129266626770404736852607352075247856808563388127774523912002202264558855255067503
# 91351185520045025851535940537599785616890151570421939971146348618267656786110090770321857244701820126026227283965934212135946431643320325513590505155214070540638751565105300361430272638957420276596026161454413739823593506516275224444666187442238624864548263927274591212614561916913851855552516864387460946267629794664216228596534684933791607740725160394841711539767932339281214673649553407414347293480522175832736301571839298158011533849603878482322619858083471
# [6924229081976334180193477951417117275396656434968000032228908231511246053064833236257422745299036986875244562025221130619850904830372215788197314906896784,707045810464337488125013716300756405499020414540801863434513087687914538170573314824134496890600422837133767094273649381435979038909605432188919586751472,561487665739111774897165274560908487232457333748910467998343202097778699925650682704996443560224288857862513676706660506594465853704042586896087391214886,6498834369085375452441121562339384727357898216850540864190840194924515286757125433756518026123451611578553656133012172518080309106483207567929943790044792,5508345401684913940610183958526398635406187349043368834080838153611810896629693027245511688366776749176652858929409374912959736262162942801190344337268446,7604410082265211154108357446507297790451766698177313130672954202813796888988719242951127448112228332967892794819415211618572734294964346056056171483002307,7699815879242527638422887386550759485127768822609011364311314299885418068889791030639324882736871756700299169635780542149704586720216395186814592666988591,829748131720382599696653359722612708514830904084605048590882951300049701148883021283243506081300427041733299385325284399270633917941134488957784480285437,7084115400374950827522650500486495223539292992998875483730758098005030106055310282589342193536381973309924074043955222228738842206417828828756951777504457,7482796067314266426215648326036921955183807741134787613584977300821023398375789725848056657250086288687570875979072368004217788222537115232191230702833854]
# [12573984103581521249597169818949825744876735847170990673204303602848066091917704946653820386665801380026230957120354174481948164514637637956459534723582285, 6441954407109995413858792101472089558106780628459991101662507565699664222341697230094798036088532393057448200220905589679548875702178737462785403325555226, 11684244745641367106386196774447204674089853123966422387024948921795099192025069760680924547214190425118261001002764397184950251157744938735586522727499550, 10396243416373326695473843427139385116708652845789644861965876346553795313454773668473030130335970707089781482749749170266279229263892370064669233541305377, 9090748241360606371310281608818966855338110969397659720953951845805983771894064629343960530245792700858927510839835850767728294266738917884471006979663157, 11489848045104749332790333272128633885019156159805805159750174723808043569789257625027794186359921080743368220606914862583644262009648261345452266067697628, 649349258009900424806913260265314442160901414078390702088746248078789581041616487825633046538335114117254875547413590064940767523651802950986197978665018, 6302136940345077947382276151657194124073457559487274425879887978386901058162385833414602346299055653879087077862824771863209271498552774720708307840705334, 5844526398244645236473089500608731415060125566027525405618000580381149761653744142808567706048834618328671311836990498943019718294135733114642775270792763, 4834548043993868659061606699822957422840040425976833628462093089330507589865407793951971491111695171201542345470702059513427268037868859282999222070054388]
17.*LCG_and_HNP(也没看)
题目：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
38from Crypto.Util.number import *
import random
from secrets import flag
class LCG:
def __init__(self, seed, a, b, p):
self.seed = seed
self.a = a
self.b = b
self.p = p
def next(self):
self.seed = (self.seed * self.a + self.b) % self.p
return self.seed >> (self.p.bit_length() - 8)
m = bytes_to_long(flag)
p = getPrime(128)
a = random.randint(1, p)
b = random.randint(1, p)
seed = random.randint(1, p)
out = []
lcg = LCG(seed, a, b, p)
for i in range(30):
out.append(lcg.next())
key = ""
while 1:
key += str(lcg.next())
if int(key) >= m:
break
with open("out.txt", "w") as f:
f.write(f"p={p}\n")
f.write(f"a={a}\n")
f.write(f"b={b}\n")
f.write(f"out={out}\n")
f.write(f"c={int(key)^m}")
18.*铜匠
copper 练习，但也没咋看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
43from Crypto.Util.number import *
from secrets import flag
m = bytes_to_long(flag)
m1 = getRandomRange(1, m)
m2 = getRandomRange(1, m)
m3 = m - m1 - m2
def task1():
e = 149
p = getPrime(512)
q = getPrime(512)
n = p * q
d = inverse(e,(p-1)*(q-1))
return (pow(m1, e, n), d >> 222 << 222, n)
def task2():
e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
return (pow(m2, e, n), (p + q) & ((1 << 624) - 1), n)
def task3():
e = 65537
p = getPrime(512)
q = getPrime(512)
n = p * q
return (pow(m3, e, n), (p ^ q) >> 200, n)
c1, leak1, n1 = task1()
c2, leak2, n2 = task2()
c3, leak3, n3 = task3()
print(c1, leak1, n1)
print(c2, leak2, n2)
print(c3, leak3, n3)
# (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
# (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
# (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)
19.*Complex_rsa
题目：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
53from Crypto.Util.number import *
from secrets 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 __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 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
m = bytes_to_long(flag)
key = getRandomNBitInteger(m.bit_length())
c = m ^ key
com = Complex(key, c)
p = getPrime(512)
q = getPrime(512)
e = 9
enc = complex_pow(com, e, p * q)
print(enc)
print(Complex(p, q) * Complex(p, q))
# 66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 + 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004i
# -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120 + 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862i
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
76from sage.matrix.matrix2 import Matrix
import libnum
from Crypto.Util.number import *
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 __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 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
def resultant(f1, f2, var):
return Matrix.determinant(f1.sylvester_matrix(f2, var))
def complex_root(c,e,p):
R.<x,y>=PolynomialRing(Zmod(p))
com=[]
ff=complex_pow(Complex(x,y),e,p)
f1=ff.re - c.re
f2=ff.im - c.im
hx = resultant(f1, f2, y)
rx = hx.univariate_polynomial().roots()
xx, _ = zip(*rx)
hy = resultant(f1, f2, x)
ry = hy.univariate_polynomial().roots()
yy, _ = zip(*ry)
for i in xx:
for j in yy:
com.append([i,j])
return com
n = 117681206424442789771700470467427053026336146020232526212158216665057406716158961837401811613640431472928771810331836487477617583442415375917193495383026751820278204379206796080561472818274231032292091582594525160449157911586912037436688225284606325564142873165418888798645467021956186910345125460419980741431
e = 9
c=Complex(66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943,65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004)
p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
q = 11531144714660489617244423924607904114688972598683439999377362467380544567879231460623526800789918614728790840508257630983753525432337178000220918002499321
mmp=complex_root(c,e,p)
mmq=complex_root(c,e,q)
for kn1 in mmp:
for kn2 in mmq:
key1,enc1,key2,enc2=kn1[0],kn1[1],kn2[0],kn2[1]
key=libnum.solve_crt([int(key1),int(key2)],[p,q])
enc=libnum.solve_crt([int(enc1),int(enc2)],[p,q])
m=long_to_bytes(int(key)^^int(enc))
if b'flag' in m:
print(key,enc)
print(m)
还是太菜了，很多题都不会…