SYCTF-2023 安洵杯 Crypto 部分题解

 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

from Crypto.Util.number import *
from random import randint
from secret import flag

def TrickPrime(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    cut = randint(1,256)
    temp = p*q
    print('clown =',temp)
    game  = (p&(2**bits-1)) >>cut<<cut #p高位需要给出
    print("trick =",game)
    return p,q

def CrazyPrime(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    r = getPrime(nbits)
    n = p * q * r
    print("n =", n)
    m = getPrime(256)
    P = pow(m, p, n)
    Q = pow(m, q, n)
    R = pow(m, r, n)
    print("P =", P)
    print("Q =", Q)
    print("R =", R)
    return m

P,Q = TrickPrime(512)
R   = CrazyPrime(512)
N =P*Q*R
phi = (P-1)*(Q-1)*(R-1)
e = 65537
d = inverse(e,phi)
m = bytes_to_long(flag)
c = pow(m,e,N)
print("c = ",c)

'''
clown =  128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209
trick =  13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576

n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259
P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052
Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499
R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030

c =  10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949
'''

 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

# sagemath 10.0
# sagemath 10.0
clown =  128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209
trick =  13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576
print(hex(trick)) # 0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d9560784892728000000000000000000000000000000000000000000000000000
# 求其hex长度: trick2hex去除尾部所有0再减去1(最后一位因为bit2hex位数不够会补0,所以这一位可能不是真实的p中的部分(仅对于hex的呈现),所以要减去1)
cache = len(hex(trick).rstrip('0')) - 2 -1 # rstrip('0')去除尾部所有0, -2 是`0x`格式
print(f'cache = {cache}\n泄漏bit位长: bitLens = {cache*4}') # 泄漏p高位 bitLen > 300, 因此可以 coppersmith 分解 clown(n) 得到 P, Q
cut = 512 - cache*4
print(f'{cut = }')

n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259
P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052
Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499
R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030

c =  10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949

PR.<x> = PolynomialRing(Zmod(clown)) # 定义多项式环, Zmod(n)是模n的多项式环
f = trick + x # 定义多项式f
p_low = f.small_roots(X = 2**cut, beta=0.45)[0]
print(f'{hex(p_low) = }')
print(f'{p_low = }')
# p_low = 76347864203588455868161824448305083084387260376528823546715135
print(f'p_low的二进制位长: {len(bin(p_low))-2}') # -2是因为bin()返回的字符串前面有0b
p = p_low + trick
print(hex(p))
q = clown//int(p)
assert p*q == clown # 确保p,q是clown的因子

# 计算R
"""
PR.<x> = PolynomialRing(Zmod(n))
r = (P-x)*(Q-x)*(R-x)
rm = r.monic() # 用monic方法将r转化为首一多项式

_R = ZZ(rm.small_roots(X=2**256)[0]) # ZZ是整数环
N = ZZ(p)*ZZ(q)*ZZ(_R)

e = 65537
phi = (p-1)*(q-1)*(_R-1)
# 也可以不算R, 因为flag很小可以直接用p,q算得出的phi, 同时为了匹配p, q, 我们N也换成p*q即为clown
"""

N = clown
phi = (p-1)*(q-1)
d = int(inverse_mod(e,phi))
m = pow(c,d,N)
from Crypto.Util.number import *
print(long_to_bytes(int(m)))
print(m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Output:
0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d9560784892728000000000000000000000000000000000000000000000000000
cache = 76
泄漏bit位长: bitLens = 304
cut = 208
hex(p_low) = '0x2f82ea9f0e432e03c74e113f0f2d3ee868da63335cdc30a29bff'
p_low = 76347864203588455868161824448305083084387260376528823546715135
p_low的二进制位长: 206
0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d956078489272af82ea9f0e432e03c74e113f0f2d3ee868da63335cdc30a29bff
b'SYC{N0b0dy_Kn0vvs_CryPt0_be7t3r_7haN_Me}'
695436377443587187633900436650862817189253770609407637864965962513329890598866383949073658766717