Coppersmith Method 学习

学习资料

NSSCTF工坊[RSA4] P2 最基础的用法

题目

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
from Crypto.Util.number import *
flag = b'NSSCTF{******}'

m = bytes_to_long(flag)

a = getPrime(512)
b = getPrime(512)
c = getPrime(512)
d = getPrime(512)
x = getPrime(128)

p = getPrime(1024)

y = a*x**3 + b*x**2 + c*x + d
y = y%p

print(f'p = {p}')
print(f'a = {a}')
print(f'b = {b}')
print(f'c = {c}')
print(f'd = {d}')
print(f'y = {y}')
print(f'h = {x*m}')

'''
p = 133497915779382863191750985139274661777547262395290628161924420897772911005538338729076080701700641387222690295548776566406640902391412661622674862629221960258683570655393881212072865809598640669325347893228617784548982886334708010706482958773921901369314425694414231562752232070402056445403762485870067804611
a = 9956367951694116871507184264812038680047685394446603010101493156120195118634053526664122377707243776744926630820373051608195739431033785355316509320690639
b = 10372715760267086803036635068149481902075294943354407472550232447612611381527989796797133302495652064200149218004252582942179771677307157495328484190016267
c = 6954444546090251351899752282258945069765577103755637726562318645879810909547057855773433206441550954298878711294660493586907360045986061150306446126101573
d = 12708905621484064085174866220764918657140490021181156214236692898034114314742314389460399916798129560082685314351680895409634875081403212130502800572290391
y = 89881957270704175663646084308402351944545222001266778194637035700540903495792268004845278611707036762628657152963392762363015748904045511650663013086598899685992255568758440781657480520250399778976982455784259655683731183717562593121780657623767804362641533930566522430
h = 584447473604416360596641349947186936435346265446590336271443321812736224750414727189483734666053582372219773206703655293254283559436185831581631
'''

分析

最基础的用法，求模多项式的小根

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
from Crypto.Util.number import long_to_bytes

p = 133497915779382863191750985139274661777547262395290628161924420897772911005538338729076080701700641387222690295548776566406640902391412661622674862629221960258683570655393881212072865809598640669325347893228617784548982886334708010706482958773921901369314425694414231562752232070402056445403762485870067804611
a = 9956367951694116871507184264812038680047685394446603010101493156120195118634053526664122377707243776744926630820373051608195739431033785355316509320690639
b = 10372715760267086803036635068149481902075294943354407472550232447612611381527989796797133302495652064200149218004252582942179771677307157495328484190016267
c = 6954444546090251351899752282258945069765577103755637726562318645879810909547057855773433206441550954298878711294660493586907360045986061150306446126101573
d = 12708905621484064085174866220764918657140490021181156214236692898034114314742314389460399916798129560082685314351680895409634875081403212130502800572290391
y = 89881957270704175663646084308402351944545222001266778194637035700540903495792268004845278611707036762628657152963392762363015748904045511650663013086598899685992255568758440781657480520250399778976982455784259655683731183717562593121780657623767804362641533930566522430
h = 584447473604416360596641349947186936435346265446590336271443321812736224750414727189483734666053582372219773206703655293254283559436185831581631

PR.<x> = PolynomialRing(Zmod(p))
f = a*x**3 + b*x**2 + c*x + d - y
roots = f.monic().small_roots()
print("[+] roots =", roots)

for x in roots:
    x = int(x)
    print("\n[+] x =", x)
    if h % x != 0:
        continue
    m = h // x
    print("[*] m =", m)
    print("[*] flag =", long_to_bytes(m))

"""
[+] roots = [208220680240996722513583102044151290091]

[+] x = 208220680240996722513583102044151290091
[*] m = 2806865643354785605407484846826426640471843693771605689945043127438975845650147246282645691174715937666941
[*] flag = b'NSSCTF{fdf4236b-50a9-4d4b-96fb-fe9ba9d7dff7}'
"""

NSSCTF工坊[RSA4] P3 代换降次

题目

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
from Crypto.Util.number import *
flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3

m1 = bytes_to_long(flag)

a = getPrime(128)
b = getPrime(128)
m2 = a*m1 + b

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

print(f'n = {n}')
print(f'a = {a}')
print(f'b = {b}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 100458074154921630841467009716211081004496986067171453439200150708921645946139163766441611050743248698408002732330100522747315912617782265320913313460939731072047224701193946357341685422329349168512101723657005099845122860786073559690394636750367940135874243034107367507957642817011696553619030089913082650051
a = 235598638113466821523819951671842238817
b = 183046284622289531351267591814278208143
c1 = 59213026759461784288811267183372841532509333531605324857784387344377914885661521950844577998650904368265218037805476510488318417561718106578315758637105422183211905379616339980270327392640886739452625323181466064322246845738001714864060399808732460864513032069624364554351131806580712989439398464697132652674
c2 = 3451970836023636992808694960720139231990590529637727188690993996140273782744393239397467373679391223914185297028545706156586953463105320180151843119949047044046733716896796505869700601788410522957973779842899158545218190431782013633486273807312128458720848868027747769057989052968304813931468091592761421857
'''

分析

注意到 Integer(bytes_to_long(f"NSSCTF{{{uuid4()}}}".encode())).nbits() 长度 351bit

因此直接 copper $c_2 \equiv a^3m_1^3+3a^2m_1^2b+ 3am_1b^2+ b^3$ 这个度 $3$ 的多项式是 copper 不出来的，考虑使用 $c_1$ 代换 $m_1^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
from Crypto.Util.number import long_to_bytes

n = 100458074154921630841467009716211081004496986067171453439200150708921645946139163766441611050743248698408002732330100522747315912617782265320913313460939731072047224701193946357341685422329349168512101723657005099845122860786073559690394636750367940135874243034107367507957642817011696553619030089913082650051
a = 235598638113466821523819951671842238817
b = 183046284622289531351267591814278208143
c1 = 59213026759461784288811267183372841532509333531605324857784387344377914885661521950844577998650904368265218037805476510488318417561718106578315758637105422183211905379616339980270327392640886739452625323181466064322246845738001714864060399808732460864513032069624364554351131806580712989439398464697132652674
c2 = 3451970836023636992808694960720139231990590529637727188690993996140273782744393239397467373679391223914185297028545706156586953463105320180151843119949047044046733716896796505869700601788410522957973779842899158545218190431782013633486273807312128458720848868027747769057989052968304813931468091592761421857

PR.<x> = PolynomialRing(Zmod(n))

f = a^3*c1 + 3*a^2*x^2*b + 3*a*x*b^2 + b^3 - c2
roots = f.monic().small_roots()
print("[+] roots =", roots)

for m1 in roots:
    m1 = int(m1)
    print("\n[+] m1 =", m1)
    print("[*] flag =", long_to_bytes(m1))

"""
[+] roots = [2806865643354785581943930084864034922303658457463090366746051046593966390253248941889426497639009694016125]

[+] m1 = 2806865643354785581943930084864034922303658457463090366746051046593966390253248941889426497639009694016125
[*] flag = b'NSSCTF{76f8044e-7bf9-43cd-885f-22f611628b8b}'
"""

NSSCTF工坊[RSA4] P4 Franklin-Reiter 相关消息攻击

题目

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
from Crypto.Util.number import *
flag = b'NSSCTF{******}'

p = getPrime(700)
q = getPrime(700)
n = p*q
e = 5

m1 = bytes_to_long(flag)

a = getPrime(128)
b = getPrime(128)
m2 = a*m1 + b

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

print(f'n = {n}')
print(f'a = {a}')
print(f'b = {b}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
a = 285426137705625850725555147387995674019
b = 277985464990476154618471183198080357743
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048
'''

分析

正常解 coppersmith 肯定是没法子了，得找找别的方法

介绍：Franklin-Reiter 相关消息攻击！

易知 $0 \equiv m_1^e - c_1$ 且 $0 \equiv m_2^e - c_2 \equiv (am_1+b)^e - c_2$

所以 $f(x) \equiv x^e-c_1$ 和 $g(x) \equiv (ax+b)^e - c_2$ 有公共根 $x \equiv m_1$ 即有公因式 $(x - m_1)$

$\mathbb{Z}$ 下的 gcd 函数是这样的

1
2
3
4
def gcd(a, b):
	while b != 0:
		a, b = b, a % b
	return a

改成 $\mathbb{Z}/n\mathbb{Z}[x]$ 下的一样能用

1
2
3
4
def gcd(f, g):
    while g != 0:
        f, g = g, f % g
    return f

最后算出来的gcd 要记得 monic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import long_to_bytes

n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
a = 285426137705625850725555147387995674019
b = 277985464990476154618471183198080357743
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048
e = 5

PR.<x> = PolynomialRing(Zmod(n))

f = x^e - c1
g = (a*x + b)^e - c2

def gcd(f, g):
    while g != 0:
        f, g = g, f % g
    return f

m = -gcd(f, g).monic()[0]
print(long_to_bytes(int(m)))

# b'NSSCTF{ca5e5ba4-57f1-4902-9448-d78b2cb05618}'

NSSCTF工坊[RSA4] P7 Franklin-Reiter 相关消息攻击

题目

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
from Crypto.Util.number import *
m = bytes_to_long(b'NSSCTF{******}')

p = getPrime(512)
q = getPrime(512)

n = p*q

e = 9

r = getPrime(512)

c1 = pow(m, e, n)
c2 = pow(m+r, e, n)


print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'r = {r}')
print(f'n = {n}')


'''
c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229
'''

分析

同 NSSCTF工坊[RSA4] P4 Franklin-Reiter 相关消息攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes

c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229
e = 9

PR.<x> = PolynomialRing(Zmod(n))

f = x^e - c1
g = (x + r)^e - c2

def gcd(f, g):
    while g != 0:
        f, g = g, f % g
    return f

m = -gcd(f, g).monic()[0]
print(long_to_bytes(int(m)))

NSSCTF工坊[RSA4] P5 Håstad 广播攻击

题目

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
import random
from Crypto.Util.number import *
m = bytes_to_long(b'NSSCTF{******}')
e = 3
cnt = 5
A = [random.randint(1, 128) for i in range(cnt)]
B = [random.randint(1, 1024) for i in range(cnt)]
Cs = []
Ns = []
ds = []
for i in range(cnt):
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    Ns.append(N)
    c = pow(A[i] * m + B[i], e, N)
    Cs.append(c)

print(f'Cs = {Cs}')
print(f'Ns = {Ns}')
print(f'A = {A}')
print(f'B = {B}')

'''
Cs = [3883550483902420926234302242195949363902226654053022494278088796963093148922544154652393440710324453957805003804862341179812753736616349557399185135880313324078548975985811806182903172952051652658588498612963004980264760087430598878125976827727487812798234711111712162020259061748840871764150680864715622600474900724019717, 44236067230701013362887598977513235723198800481322709348886355202907732899445854511587419035591039483362973933824325371001141984765195796979842132811747908218486539899605454036424269293612496645594202012384509417494958938609654993954815298870367636552785788956298375017694826184378792550191638399421497826339423606821604157, 6357650953899476167368901224389387403906446759598372329485772462484633677698135444868033121301336092469156582681179266678600618088894651608959308419170191169045155695737438290373562868522834196889856654007109891894017495798358315308038562408520108440771857096111507359080036538511243240503551392124933753089110476128205879, 22113876206623661433094377745740418662890776774627724662206682745097788065566600734855556673140969239465263787646309908630165398806037735405429975451284487302914604239730662891329034924321076102542709261476260968369261179396546360622009680551846353241542278987410340410787241742872482813920394082039159494900989803139848, 3482139402999788223900773097355269284333433274039980036209713091774078099956379218113295375979469580323031564990774054948555715060182912479470463142901382767332589017162687376944227096536463901792518843690268101660074429034365722795293704792196728134808253362549344588424246863639211005569740713503298812433885633339928000]
Ns = [16475947720089128737086499038994656469812989231809435921247088488421456071533054401942524421620331649062071397844226728071767213827034006847771426419523100773295773164564476217357610574522713490589578290280800714302496527429690267342283298617108512673396866659851168908725556917773195601048972304412711680140760801040935590195586074637385222382292803661244860123231496798860777536415139625565081790463543592610972293444445484103576151223863074744798386995109810985102707212603792744509634887671301358727199987659311189567616661188675145831286196163294361139604739930788248190209148634033965292667427275010588011907449, 20577756967813119473983751142406348831049793754920537415005815223703461130310397180758312537008616509869607815711902558904863798387297921980544196445945053155779852988514975874071063143079007922739179751830691324912287324521191080786349595537328978318940405478035852622078260078106150355838894304903666410802941404171580632337325226810035755441751019274785623857299274197733366157959314887828355684391955406242669453470960096408521602483306976326328443227588146790803825249363494429478920856868334932355802422905860734038456902208606699044555491079703407805059303577939602439962034474867810455961978123428573930309579, 25378900199358568547963276996842869295995268651191814514603221510827400166103120330924988917554751086130358554721062101701515825946297524373525439060420148179742729309006073061967296139229954269726231365437710075337125457376990188019604789882474361937774315087501386157518068677103700336670450539759041322742305750381808526633011613014316600728378154635620303486714630541107978228937765593165029293600696974317531575469630789089360595175501977260250968161370460576429760743419177492425307438895058834861598683601140950473599184767494278677563047031229859204765208419798131798581975676005652781036214330956450007099403, 9926930930542540303568927026135349869339912234415090245441062010278559018661286180235901235221302260175325531516014675014545716516533078219977130807590578846757066721033900594646767488495122383467444918251577083210413483316448060657426105745966157951221212755678202988755054192555411944547922101946719460879213184073264876177559979901796761414990531875287201475974601204234252323254624416703924391519239658714195344209537776288504410483034555245167972866281710032749023882686703242857598745646748066876170805806058616787854614797120972981188197354785585317082619741063413472652781873599900240100437586392949061248911, 20830107058752240343833750223075661528901765032886427653372256688107333986271844745610709207164953960695218903201021174901973495649232416991828815735226979007977454196096030222267886398005100472650709789400722193947140354500257454594031250139843254349174343293378469322212240525155348525032929797789787100019790044104691478313003888625343348575779856701393153928092199647854293030744711864943595605801812851745568294572509414459253058726953902809163955547592002726224051451969415362170516701646937298176613945563863745599843208814303891064544739910893746169725919856235296428308161065429422882694228900677440053029677]
A = [56, 126, 66, 10, 54]
B = [261, 191, 877, 352, 62]
'''

分析

Håstad 广播攻击，参考代码：4.8. 低加密指数广播攻击 - 4.8.4 扩展 | 独奏の小屋

类似中国剩余定理 CRT

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
from Crypto.Util.number import long_to_bytes

Cs = [3883550483902420926234302242195949363902226654053022494278088796963093148922544154652393440710324453957805003804862341179812753736616349557399185135880313324078548975985811806182903172952051652658588498612963004980264760087430598878125976827727487812798234711111712162020259061748840871764150680864715622600474900724019717, 44236067230701013362887598977513235723198800481322709348886355202907732899445854511587419035591039483362973933824325371001141984765195796979842132811747908218486539899605454036424269293612496645594202012384509417494958938609654993954815298870367636552785788956298375017694826184378792550191638399421497826339423606821604157, 6357650953899476167368901224389387403906446759598372329485772462484633677698135444868033121301336092469156582681179266678600618088894651608959308419170191169045155695737438290373562868522834196889856654007109891894017495798358315308038562408520108440771857096111507359080036538511243240503551392124933753089110476128205879, 22113876206623661433094377745740418662890776774627724662206682745097788065566600734855556673140969239465263787646309908630165398806037735405429975451284487302914604239730662891329034924321076102542709261476260968369261179396546360622009680551846353241542278987410340410787241742872482813920394082039159494900989803139848, 3482139402999788223900773097355269284333433274039980036209713091774078099956379218113295375979469580323031564990774054948555715060182912479470463142901382767332589017162687376944227096536463901792518843690268101660074429034365722795293704792196728134808253362549344588424246863639211005569740713503298812433885633339928000]
Ns = [16475947720089128737086499038994656469812989231809435921247088488421456071533054401942524421620331649062071397844226728071767213827034006847771426419523100773295773164564476217357610574522713490589578290280800714302496527429690267342283298617108512673396866659851168908725556917773195601048972304412711680140760801040935590195586074637385222382292803661244860123231496798860777536415139625565081790463543592610972293444445484103576151223863074744798386995109810985102707212603792744509634887671301358727199987659311189567616661188675145831286196163294361139604739930788248190209148634033965292667427275010588011907449, 20577756967813119473983751142406348831049793754920537415005815223703461130310397180758312537008616509869607815711902558904863798387297921980544196445945053155779852988514975874071063143079007922739179751830691324912287324521191080786349595537328978318940405478035852622078260078106150355838894304903666410802941404171580632337325226810035755441751019274785623857299274197733366157959314887828355684391955406242669453470960096408521602483306976326328443227588146790803825249363494429478920856868334932355802422905860734038456902208606699044555491079703407805059303577939602439962034474867810455961978123428573930309579, 25378900199358568547963276996842869295995268651191814514603221510827400166103120330924988917554751086130358554721062101701515825946297524373525439060420148179742729309006073061967296139229954269726231365437710075337125457376990188019604789882474361937774315087501386157518068677103700336670450539759041322742305750381808526633011613014316600728378154635620303486714630541107978228937765593165029293600696974317531575469630789089360595175501977260250968161370460576429760743419177492425307438895058834861598683601140950473599184767494278677563047031229859204765208419798131798581975676005652781036214330956450007099403, 9926930930542540303568927026135349869339912234415090245441062010278559018661286180235901235221302260175325531516014675014545716516533078219977130807590578846757066721033900594646767488495122383467444918251577083210413483316448060657426105745966157951221212755678202988755054192555411944547922101946719460879213184073264876177559979901796761414990531875287201475974601204234252323254624416703924391519239658714195344209537776288504410483034555245167972866281710032749023882686703242857598745646748066876170805806058616787854614797120972981188197354785585317082619741063413472652781873599900240100437586392949061248911, 20830107058752240343833750223075661528901765032886427653372256688107333986271844745610709207164953960695218903201021174901973495649232416991828815735226979007977454196096030222267886398005100472650709789400722193947140354500257454594031250139843254349174343293378469322212240525155348525032929797789787100019790044104691478313003888625343348575779856701393153928092199647854293030744711864943595605801812851745568294572509414459253058726953902809163955547592002726224051451969415362170516701646937298176613945563863745599843208814303891064544739910893746169725919856235296428308161065429422882694228900677440053029677]
A = [56, 126, 66, 10, 54]
B = [261, 191, 877, 352, 62]
e = 3
cnt = 5

Fs = []

for i in range(cnt):
    PR.<x> = PolynomialRing(Zmod(Ns[i]))
    f = (A[i] * x + B[i])^e - Cs[i]
    f = f.monic()
    f = f.change_ring(ZZ)
    Fs.append(f)

F = crt(Fs,Ns)
M = reduce(lambda x,y: x*y, Ns)
FF = F.change_ring(Zmod(M))
m = FF.small_roots()[0]
print(long_to_bytes(int(m)))

# b'NSSCTF{35036d92-a21e-4a72-b95b-9dbbe753ecc3}'

NSSCTF工坊[RSA4] P6 SMUPE 问题

题目

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
import random
from Crypto.Util.number import *
m = bytes_to_long(b'NSSCTF{******}')
e = [3, 3, 5, 5, 5]
cnt = 5
A = [random.randint(1, 128) for i in range(cnt)]
B = [random.randint(1, 1024) for i in range(cnt)]
Cs = []
Ns = []
ds = []
for i in range(cnt):
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    Ns.append(N)
    c = pow(A[i] * m + B[i], e[i], N)
    Cs.append(c)

print(f'Cs = {Cs}')
print(f'Ns = {Ns}')
print(f'A = {A}')
print(f'B = {B}')

'''
Cs = [1638372860396333830858192139299197565315535797114047251934794618479536350353064186140459367290707128364710894701037380862116232991456320452033817724729745999551370161110364719775843718524874686887258953369568831680913879476181277785920985528366522169515587323204831502022101524013959969707030218702665635534427846097310528, 24875103245287518333798583341170669610612985353699595724009027288108265538326708679930645795919635882205442133007431151523157879281206220723880745758565471501438254496442690083695181899335274484890789079296262809116356375268279845048678237286447923982167817217922153443176926762232059077533241044053964988769850924306985288, 64688172933628370164101081823612690628987450046625542396917972565171355353907472697857255273381548322579305723285123851525656566580337341114653428214836087595329638898225145943365511037774869374134885003316128253926961420282704740956759510282270641913416144450959604091354160410240665076557553695082195679797827535998182932257141208537699109343258070255441327703937342812407754987740672481360192201134257594522722416452532574980648175817255926752015634178759148371873886725487426882416560377719144628014480729074137290874113394638649, 2331510898077623659120984694249257439156322301842388986730933314009350853947089766519871253176646702446795943582256729119033154456495699173945031006143311061427619102940335615125087858864022720270624007893746341836293909702537610528426633085355155950799091717823412938027363876570661223166297511428235178239172777386054157082903814899961457013918859628205065752880604381763832163537338551244398891801443773401629786720308176486501031559320335954176695196225203579812567823068688019940197116285653102121974647104338589625423162979123200000, 43352520643859740433225512983905414415548381386134203892101097918185149451843972944152506360707251233402378401486868477947209998018140026240239412053179633750634829740693522063308924633469091372871162080586416600131760956876088974352867618081110555761392159757815560347289247112408714776983781605234434193615594699312985986139327998952524143416350988540093792251368427565860264534170095799987780694458909019564914374157162696794037736526763479508220179034487041180476942175322953798097172419873588374189541978291235559914015746424832]
Ns = [18851715582267592911067637781505654688524006829609246212518637897179276424340538881817812202528554956234031661903911094094631063183133761100477455043312123459298106634164727720627011192110779310094771478538283788677548037922530846281891688189750395295091964623923749350256625089576542690752106832774515171043826627323369467260229924116376613509392517052062075900227272040203183759436637270279153088519018200373369193287900910393638164679806105636141482865492140475543667203300150180799017010647191076802371803957049729665372388660643393619274625881752621206735741181918995753694012667166942840946695127545765890742063, 10267889563711456032579409966472790716819993551437295130252040883990243681903448974535591113545723576913765740482844093394217174748720819947126768257873382519317182097620449979975383634794725676148262423293825784384533131631434500141020335993500562261013949796155168237990517113432978329233691874362416933639983930536969236091719851430961549012395926775041931819868164629850848771931505977967078205269399517880792473005512550209988476927697762292764104113892623269364458825553466135026856101503576301198196565099526473547248865742864274841493027912793979121030411574680325683879250124843231524231297963898683611241527, 13319929603701741793046504861847275881318265379528541599237187836042138080675688093798835275556697353969650992398737328710351200421781106774355347739070892841366306344713730729129300977800957626288502163079067715579382767916393807593767445074588824226624616133919776732577297061788596743900830022053036147505073981250694269494874718657327986653908553022998256475699594299485467200757418076210359679356806790879777840686012933726208975488043576064467651494231751296178499718963576152784658938960177680763100892103245100085259616393419229979173756419121148473713407084223326468838444608241533523272737548699784114288903, 15549454451010517732114866346347857621738418424726590607108866905866201671458396332585415677794254468988000522332928496951404966782246273839731570675805037547434885303486571417761150107287375265185136666085669367768385334732360327965658288195932251712038801089064036484182689420567148777802229959025706026709147490355638461816828297349827923064039389517458474972494803430895794622409100453812936135163906960476019328052200697229957383357240180993014685003281514802948810450239516985749998285384120569891328984748185007801287194757011610585773959113119657356194098917480068595559585415503075706079451596444873538025303, 10893748607240110955496798243605432030914497581057961213501578142738832043376333318606333861002076584473798177824249978795107994620002676260061434742704861691017695197358462123116073867166385116309506188722505093349759974669126863738760846667781081937653476878088812043691664173859578763022307064317030903235196823302973152319271598841684324885625237030423977448610068847582315745648803893547950848775977888604054275196982524051414526965045483738781651554877828535198984557716599475979572917851219474771059404496356672662467552795811246938928548202179363916774439119111218984949582826015360298300266708147597580287967]
A = [42, 104, 13, 106, 12]
B = [338, 554, 768, 638, 548]
'''

分析

$e$ 不一样大，可以取前两个或者后三个来进行 Hastad (非预期)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import long_to_bytes

e = [3, 3, 5, 5, 5]
Cs = [1638372860396333830858192139299197565315535797114047251934794618479536350353064186140459367290707128364710894701037380862116232991456320452033817724729745999551370161110364719775843718524874686887258953369568831680913879476181277785920985528366522169515587323204831502022101524013959969707030218702665635534427846097310528, 24875103245287518333798583341170669610612985353699595724009027288108265538326708679930645795919635882205442133007431151523157879281206220723880745758565471501438254496442690083695181899335274484890789079296262809116356375268279845048678237286447923982167817217922153443176926762232059077533241044053964988769850924306985288, 64688172933628370164101081823612690628987450046625542396917972565171355353907472697857255273381548322579305723285123851525656566580337341114653428214836087595329638898225145943365511037774869374134885003316128253926961420282704740956759510282270641913416144450959604091354160410240665076557553695082195679797827535998182932257141208537699109343258070255441327703937342812407754987740672481360192201134257594522722416452532574980648175817255926752015634178759148371873886725487426882416560377719144628014480729074137290874113394638649, 2331510898077623659120984694249257439156322301842388986730933314009350853947089766519871253176646702446795943582256729119033154456495699173945031006143311061427619102940335615125087858864022720270624007893746341836293909702537610528426633085355155950799091717823412938027363876570661223166297511428235178239172777386054157082903814899961457013918859628205065752880604381763832163537338551244398891801443773401629786720308176486501031559320335954176695196225203579812567823068688019940197116285653102121974647104338589625423162979123200000, 43352520643859740433225512983905414415548381386134203892101097918185149451843972944152506360707251233402378401486868477947209998018140026240239412053179633750634829740693522063308924633469091372871162080586416600131760956876088974352867618081110555761392159757815560347289247112408714776983781605234434193615594699312985986139327998952524143416350988540093792251368427565860264534170095799987780694458909019564914374157162696794037736526763479508220179034487041180476942175322953798097172419873588374189541978291235559914015746424832]
Ns = [18851715582267592911067637781505654688524006829609246212518637897179276424340538881817812202528554956234031661903911094094631063183133761100477455043312123459298106634164727720627011192110779310094771478538283788677548037922530846281891688189750395295091964623923749350256625089576542690752106832774515171043826627323369467260229924116376613509392517052062075900227272040203183759436637270279153088519018200373369193287900910393638164679806105636141482865492140475543667203300150180799017010647191076802371803957049729665372388660643393619274625881752621206735741181918995753694012667166942840946695127545765890742063, 10267889563711456032579409966472790716819993551437295130252040883990243681903448974535591113545723576913765740482844093394217174748720819947126768257873382519317182097620449979975383634794725676148262423293825784384533131631434500141020335993500562261013949796155168237990517113432978329233691874362416933639983930536969236091719851430961549012395926775041931819868164629850848771931505977967078205269399517880792473005512550209988476927697762292764104113892623269364458825553466135026856101503576301198196565099526473547248865742864274841493027912793979121030411574680325683879250124843231524231297963898683611241527, 13319929603701741793046504861847275881318265379528541599237187836042138080675688093798835275556697353969650992398737328710351200421781106774355347739070892841366306344713730729129300977800957626288502163079067715579382767916393807593767445074588824226624616133919776732577297061788596743900830022053036147505073981250694269494874718657327986653908553022998256475699594299485467200757418076210359679356806790879777840686012933726208975488043576064467651494231751296178499718963576152784658938960177680763100892103245100085259616393419229979173756419121148473713407084223326468838444608241533523272737548699784114288903, 15549454451010517732114866346347857621738418424726590607108866905866201671458396332585415677794254468988000522332928496951404966782246273839731570675805037547434885303486571417761150107287375265185136666085669367768385334732360327965658288195932251712038801089064036484182689420567148777802229959025706026709147490355638461816828297349827923064039389517458474972494803430895794622409100453812936135163906960476019328052200697229957383357240180993014685003281514802948810450239516985749998285384120569891328984748185007801287194757011610585773959113119657356194098917480068595559585415503075706079451596444873538025303, 10893748607240110955496798243605432030914497581057961213501578142738832043376333318606333861002076584473798177824249978795107994620002676260061434742704861691017695197358462123116073867166385116309506188722505093349759974669126863738760846667781081937653476878088812043691664173859578763022307064317030903235196823302973152319271598841684324885625237030423977448610068847582315745648803893547950848775977888604054275196982524051414526965045483738781651554877828535198984557716599475979572917851219474771059404496356672662467552795811246938928548202179363916774439119111218984949582826015360298300266708147597580287967]
A = [42, 104, 13, 106, 12]
B = [338, 554, 768, 638, 548]

Fs = []

for i in [2, 3, 4]:
    PR.<x> = PolynomialRing(Zmod(Ns[i]))
    f = (A[i] * x + B[i])^e[i] - Cs[i]
    f = f.monic()
    f = f.change_ring(ZZ)
    Fs.append(f)

F = crt(Fs,Ns[2:5])
M = reduce(lambda x,y: x*y, Ns[2:5])
FF = F.change_ring(Zmod(M))
m = FF.monic().small_roots()[0]
print(long_to_bytes(int(m)))

# b'NSSCTF{62e90a0e-c982-4a00-8ae9-eb493786a7d6}'

也可以将每个式子配好相同的次数，即 SMUPE 问题 (预期解)

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
from Crypto.Util.number import long_to_bytes

e = [3, 3, 5, 5, 5]
Cs = [1638372860396333830858192139299197565315535797114047251934794618479536350353064186140459367290707128364710894701037380862116232991456320452033817724729745999551370161110364719775843718524874686887258953369568831680913879476181277785920985528366522169515587323204831502022101524013959969707030218702665635534427846097310528, 24875103245287518333798583341170669610612985353699595724009027288108265538326708679930645795919635882205442133007431151523157879281206220723880745758565471501438254496442690083695181899335274484890789079296262809116356375268279845048678237286447923982167817217922153443176926762232059077533241044053964988769850924306985288, 64688172933628370164101081823612690628987450046625542396917972565171355353907472697857255273381548322579305723285123851525656566580337341114653428214836087595329638898225145943365511037774869374134885003316128253926961420282704740956759510282270641913416144450959604091354160410240665076557553695082195679797827535998182932257141208537699109343258070255441327703937342812407754987740672481360192201134257594522722416452532574980648175817255926752015634178759148371873886725487426882416560377719144628014480729074137290874113394638649, 2331510898077623659120984694249257439156322301842388986730933314009350853947089766519871253176646702446795943582256729119033154456495699173945031006143311061427619102940335615125087858864022720270624007893746341836293909702537610528426633085355155950799091717823412938027363876570661223166297511428235178239172777386054157082903814899961457013918859628205065752880604381763832163537338551244398891801443773401629786720308176486501031559320335954176695196225203579812567823068688019940197116285653102121974647104338589625423162979123200000, 43352520643859740433225512983905414415548381386134203892101097918185149451843972944152506360707251233402378401486868477947209998018140026240239412053179633750634829740693522063308924633469091372871162080586416600131760956876088974352867618081110555761392159757815560347289247112408714776983781605234434193615594699312985986139327998952524143416350988540093792251368427565860264534170095799987780694458909019564914374157162696794037736526763479508220179034487041180476942175322953798097172419873588374189541978291235559914015746424832]
Ns = [18851715582267592911067637781505654688524006829609246212518637897179276424340538881817812202528554956234031661903911094094631063183133761100477455043312123459298106634164727720627011192110779310094771478538283788677548037922530846281891688189750395295091964623923749350256625089576542690752106832774515171043826627323369467260229924116376613509392517052062075900227272040203183759436637270279153088519018200373369193287900910393638164679806105636141482865492140475543667203300150180799017010647191076802371803957049729665372388660643393619274625881752621206735741181918995753694012667166942840946695127545765890742063, 10267889563711456032579409966472790716819993551437295130252040883990243681903448974535591113545723576913765740482844093394217174748720819947126768257873382519317182097620449979975383634794725676148262423293825784384533131631434500141020335993500562261013949796155168237990517113432978329233691874362416933639983930536969236091719851430961549012395926775041931819868164629850848771931505977967078205269399517880792473005512550209988476927697762292764104113892623269364458825553466135026856101503576301198196565099526473547248865742864274841493027912793979121030411574680325683879250124843231524231297963898683611241527, 13319929603701741793046504861847275881318265379528541599237187836042138080675688093798835275556697353969650992398737328710351200421781106774355347739070892841366306344713730729129300977800957626288502163079067715579382767916393807593767445074588824226624616133919776732577297061788596743900830022053036147505073981250694269494874718657327986653908553022998256475699594299485467200757418076210359679356806790879777840686012933726208975488043576064467651494231751296178499718963576152784658938960177680763100892103245100085259616393419229979173756419121148473713407084223326468838444608241533523272737548699784114288903, 15549454451010517732114866346347857621738418424726590607108866905866201671458396332585415677794254468988000522332928496951404966782246273839731570675805037547434885303486571417761150107287375265185136666085669367768385334732360327965658288195932251712038801089064036484182689420567148777802229959025706026709147490355638461816828297349827923064039389517458474972494803430895794622409100453812936135163906960476019328052200697229957383357240180993014685003281514802948810450239516985749998285384120569891328984748185007801287194757011610585773959113119657356194098917480068595559585415503075706079451596444873538025303, 10893748607240110955496798243605432030914497581057961213501578142738832043376333318606333861002076584473798177824249978795107994620002676260061434742704861691017695197358462123116073867166385116309506188722505093349759974669126863738760846667781081937653476878088812043691664173859578763022307064317030903235196823302973152319271598841684324885625237030423977448610068847582315745648803893547950848775977888604054275196982524051414526965045483738781651554877828535198984557716599475979572917851219474771059404496356672662467552795811246938928548202179363916774439119111218984949582826015360298300266708147597580287967]
A = [42, 104, 13, 106, 12]
B = [338, 554, 768, 638, 548]

max_e = max(e)

Fs = []

for i in range(5):
    PR.<x> = PolynomialRing(Zmod(Ns[i]))
    f = (A[i] * x + B[i])^e[i] - Cs[i]
    f = f * x ^ (max_e - e[i])
    f = f.monic()
    f = f.change_ring(ZZ)
    Fs.append(f)

F = crt(Fs,Ns)
M = reduce(lambda x,y: x*y, Ns)
FF = F.change_ring(Zmod(M))
m = FF.monic().small_roots()[0]
print(long_to_bytes(int(m)))

# b'NSSCTF{62e90a0e-c982-4a00-8ae9-eb493786a7d6}'

NSSCTF工坊[RSA4] P8 m高位泄露

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

flag = b'NSSCTF{******}'

n = p*q
m = bytes_to_long(flag)

e = 3
c = pow(m, e, n)

print(f'n = {n}')
print(f'm = {m>>100}')
print(f'c = {c}')

'''
n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
m = 2214226572250613833249705195927505959981823363137633354626532745196588970707
c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333
'''

分析

$e$ 小，$m$ 大部分高位泄露，设 $m = m{high} + m{low}$，则 $c \equiv m ^ e \equiv (m{high} + m{low})^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
reset()
from Crypto.Util.number import long_to_bytes

k = 100
n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
mh = 2214226572250613833249705195927505959981823363137633354626532745196588970707
mh = mh << k
c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333
e = 3


PRn.<x> = PolynomialRing(Zmod(n))
f = (mh + x)^e - c
f = f.monic()

roots = f.small_roots()
print(roots)

for root in roots:
    root = int(root)
    print("\n[+] get root:", root)
    print("[*] m =", mh + root)
    print("[*]", long_to_bytes(mh + root))

"""
[586224111363642075583459307645]

[+] get root: 586224111363642075583459307645
[*] m = 2806865643354785581450142994351107732326351637470254633277360198619644201711450860255199207594318928228477
[*] b'NSSCTF{688404a6-c408-4196-bc43-7f18317a9170}'
"""

NSSCTF工坊[RSA4] P9 把 $n$ 的因数 $b \ge N^\beta$ 当作模数

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

flag = b'NSSCTF{******}'

n = p*q
m = bytes_to_long(flag)

e = 65537
c = pow(m, e, n)

print(f'n = {n}')
print(f'p = {p>>100}')
print(f'c = {c}')

'''
n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
p = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223
'''

分析

$p$ 和 $q$ 的位数约为 $n$ 的一半，利用“给定 $\beta$，快速求出模某个 $b$ 意义下较小的根，其中 $b \ge n^\beta$，是 $n$ 的因数”。 small_roots 时设 beta<.5

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
reset()
from Crypto.Util.number import long_to_bytes

k = 100

e = 0x10001
n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
ph = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
ph = ph << k
c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223


PRn.<x> = PolynomialRing(Zmod(n))

f = ph + x
f = f.monic()

roots = f.small_roots(X = 2^k, beta = .4)
print(roots)
for root in roots:
    root = int(root)
    p = ph + root
    print("\n[+] get root:", root)
    if n % p != 0:
        print("[-] wrong answer")
        continue
    print("[*] p =", p)
    q = n // p
    phi = (p-1)*(q-1)
    d = int(pow(e, -1, phi))
    m = int(pow(c, d, n))
    print("[*]", long_to_bytes(m))
"""
[454816335479034891704851699843]

[+] get root: 454816335479034891704851699843
[*] p = 9571455485910309291916917316888534528443339900073567672342627514933886471478666308857617873057362700447653818641726655818289650455563616992849737369983107
[*] b'NSSCTF{36a5ae48-f281-4576-8d1f-acab0666bff2}'
"""

NSSCTF工坊[RSA4] P10 已知 d 低位，求 p, q

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

flag = b'NSSCTF{******}'

n = p*q
m = bytes_to_long(flag)

e = 7
d = inverse(e, (p-1)*(q-1))
c = pow(m, e, n)

print(f'n = {n}')
print(f'd = {d&(2**410-1)}')
print(f'c = {c}')

'''
n = 156739515226635581524592797610847324418529702729659760727202454324501479907596255649349406182566636617352761983459648380669151952249526892078378572831346100444943020314226860094300911303589453661009834514243241261318188779118227457185670049393331570167726982038500849886842419000632840251465852441285715712609
d = 1865327042408619801352057511348007441275330638921397637214779955824487081626289235627502761209800783644652914147540081431451
c = 72260884070910873253619893714557327479300651539617744913822595501549980223259020597000998829262506949824325397279990912888752157554696212466966682483623575703479116305560808218806054242135099446883072418808228726774129042552815016924170283352225826854235696829480360844745488070927932843928843556296485306121
'''

分析

参考 phase 4: 已知 d 低位，求 p, q | Pion1eer

已知 $d$ 的低 $410$ 位，即已知 $d_{low} = d \bmod 2^{410}$

两边取 $\bmod{2^{410}}$

以 $\frac{n}{p}$ 代替 $q$，化为单变量等式：

模意义下一元二次方程，解完可以得到 $p_{low} = p \bmod {2^{410}}$

然后再利用 P9 解出完整的 $p$ 即可

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
from Crypto.Util.number import long_to_bytes

n = 156739515226635581524592797610847324418529702729659760727202454324501479907596255649349406182566636617352761983459648380669151952249526892078378572831346100444943020314226860094300911303589453661009834514243241261318188779118227457185670049393331570167726982038500849886842419000632840251465852441285715712609
dl = 1865327042408619801352057511348007441275330638921397637214779955824487081626289235627502761209800783644652914147540081431451
c = 72260884070910873253619893714557327479300651539617744913822595501549980223259020597000998829262506949824325397279990912888752157554696212466966682483623575703479116305560808218806054242135099446883072418808228726774129042552815016924170283352225826854235696829480360844745488070927932843928843556296485306121

def get_p_low():
    print("get_p_low")
    maybe_p_low = []
    p = var('p')
    for k in range(1, 7+1):
        f = k * (n*p - p^2 - n + p) + p - 7*dl*p
        roots = solve_mod([f], 2^410)
        maybe_p_low += [int(root[0]) for root in roots]
        print(f"[+] k =", k,"\troots =", roots)
    print("maybe_p_low:", maybe_p_low)
    
    maybe_p = []
    for p_low in maybe_p_low:
        p = get_full_p(p_low)
        if p:
            maybe_p.append(p)
    
    print(maybe_p)

    for p in maybe_p:
        if n % p == 0:
            print("Found p:", p)
            return p

def get_full_p(p_low):
    PR.<x> = PolynomialRing(Zmod(n))
    p = x * 2^410 + p_low - n
    roots = p.monic().small_roots(X = 2^(512-410), beta = .4)
    if roots:
        return int(p(roots[0]))
    return None

p = get_p_low()
q = n // p
assert n == p * q

e = 7
d = pow(e, -1, (p-1)*(q-1))

m = pow(c, d, n)
long_to_bytes(m)

"""
get_p_low
[+] k = 1 	roots = []
[+] k = 2 	roots = []
[+] k = 3 	roots = [(15782400274410125266299615039204687648239749624968048772538108316107834343510984483373502800953549213874615211388273835803,), (216175167833235042695566043002922999174165975344341575587144398195111696541111662186439526374789175117314044084502035159091,), (346310384669534424742257269055590207562442091107108658414862505953310729961666657395968108020811191637670221223899952987931,), (546703152228359342171523697019308519088368316826482185229468795832314592159267335099034131594646817541109650097013714311219,), (676838369064658724218214923071975727476644432589249268057186903590513625579822330308562713240668834061465827236411632140059,), (877231136623483641647481351035694039002570658308622794871793193469517487777423008011628736814504459964905256109525393463347,), (1007366353459783023694172577088361247390846774071389877699511301227716521197978003221157318460526476485261433248923311292187,), (1207759121018607941123439005052079558916772999790763404514117591106720383395578680924223342034362102388700862122037072615475,), (1337894337854907323170130231104746767305049115553530487341835698864919416816133676133751923680384118909057039261434990444315,), (1538287105413732240599396659068465078830975341272904014156441988743923279013734353836817947254219744812496468134548751767603,), (1668422322250031622646087885121132287219251457035671096984160096502122312434289349046346528900241761332852645273946669596443,), (1868815089808856540075354313084850598745177682755044623798766386381126174631890026749412552474077387236292074147060430919731,), (1998950306645155922122045539137517807133453798517811706626484494139325208052445021958941134120099403756648251286458348748571,), (2199343074203980839551311967101236118659380024237185233441090784018329070250045699662007157693935029660087680159572110071859,), (2329478291040280221598003193153903327047656139999952316268808891776528103670600694871535739339957046180443857298970027900699,), (2529871058599105139027269621117621638573582365719325843083415181655531965868201372574601762913792672083883286172083789223987,)]
[+] k = 4 	roots = []
[+] k = 5 	roots = []
[+] k = 6 	roots = []
[+] k = 7 	roots = []
maybe_p_low: [15782400274410125266299615039204687648239749624968048772538108316107834343510984483373502800953549213874615211388273835803, 216175167833235042695566043002922999174165975344341575587144398195111696541111662186439526374789175117314044084502035159091, 346310384669534424742257269055590207562442091107108658414862505953310729961666657395968108020811191637670221223899952987931, 546703152228359342171523697019308519088368316826482185229468795832314592159267335099034131594646817541109650097013714311219, 676838369064658724218214923071975727476644432589249268057186903590513625579822330308562713240668834061465827236411632140059, 877231136623483641647481351035694039002570658308622794871793193469517487777423008011628736814504459964905256109525393463347, 1007366353459783023694172577088361247390846774071389877699511301227716521197978003221157318460526476485261433248923311292187, 1207759121018607941123439005052079558916772999790763404514117591106720383395578680924223342034362102388700862122037072615475, 1337894337854907323170130231104746767305049115553530487341835698864919416816133676133751923680384118909057039261434990444315, 1538287105413732240599396659068465078830975341272904014156441988743923279013734353836817947254219744812496468134548751767603, 1668422322250031622646087885121132287219251457035671096984160096502122312434289349046346528900241761332852645273946669596443, 1868815089808856540075354313084850598745177682755044623798766386381126174631890026749412552474077387236292074147060430919731, 1998950306645155922122045539137517807133453798517811706626484494139325208052445021958941134120099403756648251286458348748571, 2199343074203980839551311967101236118659380024237185233441090784018329070250045699662007157693935029660087680159572110071859, 2329478291040280221598003193153903327047656139999952316268808891776528103670600694871535739339957046180443857298970027900699, 2529871058599105139027269621117621638573582365719325843083415181655531965868201372574601762913792672083883286172083789223987]
[12808244700891848571681229867945939151349649203736478559496534700297805628016283555802028490128990889103978707177718442769816734510420394810692765321412379, 12237392311510232207733315168168939306945753136553292583198371223481698647146588134299029434945831935900733541708388736093730289336504023586822354826680371]
Found p: 12808244700891848571681229867945939151349649203736478559496534700297805628016283555802028490128990889103978707177718442769816734510420394810692765321412379
b'NSSCTF{e5430ded-500c-4cc0-9bdb-b4e40a9be3a0}'
"""

NSSCTF工坊[RSA4] P11 Boneh and Durfee Attack

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

flag = b'NSSCTF{******}'

n = p*q
m = bytes_to_long(flag)

d = getPrime(int(1024*0.27))
e = inverse(d, (p-1)*(q-1))
c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 160114502501162084436964583573537478796032975208003641998245321466054315024090626426576990670846673676284220472762005347545857048805279326218401844652650972020279579076862422448095751869541093396088035262462766840652498826036642824370917665518133929602675230369722990871966227199496065637730328810028624771799
e = 45345940569506069958442629331605385637541863502889625766318025882612322508079296362452308633027956256763871699363730475762179734871820426435674201573024637206928394192742633431788159554008858191365192772486379417021387095234660386008405855409257903024187126197769938866986740500855322639995703897171982472409
c = 54804574756729863920967159846060185937697266820658443964397350756668642051647933464063713653569896152539760694973280490768379727191709149635944250514794939902138783777815040318178431874892245462786377699958110644049375757179588739287406833915772871299296750059138805811112990483420256564588150314150915692126
'''

分析

由

估算得:

不满足 weiner attack 的条件 $ed^2 \lessapprox \frac{1}{2} N^{3/2}$

参考:

拿到新的板板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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
from Crypto.Util.number import *

N = 160114502501162084436964583573537478796032975208003641998245321466054315024090626426576990670846673676284220472762005347545857048805279326218401844652650972020279579076862422448095751869541093396088035262462766840652498826036642824370917665518133929602675230369722990871966227199496065637730328810028624771799
e = 45345940569506069958442629331605385637541863502889625766318025882612322508079296362452308633027956256763871699363730475762179734871820426435674201573024637206928394192742633431788159554008858191365192772486379417021387095234660386008405855409257903024187126197769938866986740500855322639995703897171982472409
c = 54804574756729863920967159846060185937697266820658443964397350756668642051647933464063713653569896152539760694973280490768379727191709149635944250514794939902138783777815040318178431874892245462786377699958110644049375757179588739287406833915772871299296750059138805811112990483420256564588150314150915692126
"""
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


delta = .271  # this means that d < N^delta
m = 8  # size of the lattice (bigger the better/slower)
t = int((1 - 2 * delta) * m)  # optimization from Herrmann and May
X = 2 * floor(N ^ delta)  # this _might_ be too much
Y = floor(N ^ (1 / 2))  # correct if p, q are ~ same size
P.<x,y> = PolynomialRing(ZZ)
A = int((N + 1) / 2)
pol = 1 + x * (A + y)

solx, soly = boneh_durfee(pol, e, m, t, X, Y)

d = int(pol(solx, soly) / e)
print(d)
m = power_mod(c, d, N)
print(long_to_bytes(m))

__END__