Coppersmith学习

Coppersmith Method 学习#

学习资料#

Coppersmith method - Wikipedia
Coppersmith, D. (1996). “Finding a Small Root of a Univariate Modular Equation”. Advances in Cryptology — EUROCRYPT ‘96. Lecture Notes in Computer Science. Vol. 1070. pp. 155–165. doi:10.1007/3-540-68339-9_14. ISBN 978-3-540-61186-8.
Chapter 19: Coppersmith’s Method and Related Applications. Mathematics of Public Key Cryptography by Steven Galbraith ch19.pdf
有很多例题 coppersmith铜匠入门 | saga131密之作坊

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

题目#

1
from Crypto.Util.number import *
2
flag = b'NSSCTF{******}'
3

4
m = bytes_to_long(flag)
5

6
a = getPrime(512)
7
b = getPrime(512)
8
c = getPrime(512)
9
d = getPrime(512)
10
x = getPrime(128)
11

12
p = getPrime(1024)
13

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

17
print(f'p = {p}')
18
print(f'a = {a}')
19
print(f'b = {b}')
20
print(f'c = {c}')
21
print(f'd = {d}')
22
print(f'y = {y}')
23
print(f'h = {x*m}')
24

25
'''
26
p = 133497915779382863191750985139274661777547262395290628161924420897772911005538338729076080701700641387222690295548776566406640902391412661622674862629221960258683570655393881212072865809598640669325347893228617784548982886334708010706482958773921901369314425694414231562752232070402056445403762485870067804611
27
a = 9956367951694116871507184264812038680047685394446603010101493156120195118634053526664122377707243776744926630820373051608195739431033785355316509320690639
28
b = 10372715760267086803036635068149481902075294943354407472550232447612611381527989796797133302495652064200149218004252582942179771677307157495328484190016267
29
c = 6954444546090251351899752282258945069765577103755637726562318645879810909547057855773433206441550954298878711294660493586907360045986061150306446126101573
30
d = 12708905621484064085174866220764918657140490021181156214236692898034114314742314389460399916798129560082685314351680895409634875081403212130502800572290391
31
y = 89881957270704175663646084308402351944545222001266778194637035700540903495792268004845278611707036762628657152963392762363015748904045511650663013086598899685992255568758440781657480520250399778976982455784259655683731183717562593121780657623767804362641533930566522430
32
h = 584447473604416360596641349947186936435346265446590336271443321812736224750414727189483734666053582372219773206703655293254283559436185831581631
33
'''

分析#

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

1
from Crypto.Util.number import long_to_bytes
2

3
p = 133497915779382863191750985139274661777547262395290628161924420897772911005538338729076080701700641387222690295548776566406640902391412661622674862629221960258683570655393881212072865809598640669325347893228617784548982886334708010706482958773921901369314425694414231562752232070402056445403762485870067804611
4
a = 9956367951694116871507184264812038680047685394446603010101493156120195118634053526664122377707243776744926630820373051608195739431033785355316509320690639
5
b = 10372715760267086803036635068149481902075294943354407472550232447612611381527989796797133302495652064200149218004252582942179771677307157495328484190016267
6
c = 6954444546090251351899752282258945069765577103755637726562318645879810909547057855773433206441550954298878711294660493586907360045986061150306446126101573
7
d = 12708905621484064085174866220764918657140490021181156214236692898034114314742314389460399916798129560082685314351680895409634875081403212130502800572290391
8
y = 89881957270704175663646084308402351944545222001266778194637035700540903495792268004845278611707036762628657152963392762363015748904045511650663013086598899685992255568758440781657480520250399778976982455784259655683731183717562593121780657623767804362641533930566522430
9
h = 584447473604416360596641349947186936435346265446590336271443321812736224750414727189483734666053582372219773206703655293254283559436185831581631
10

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

16
for x in roots:
17
    x = int(x)
18
    print("\n[+] x =", x)
19
    if h % x != 0:
20
        continue
21
    m = h // x
22
    print("[*] m =", m)
23
    print("[*] flag =", long_to_bytes(m))
24

25
"""
26
[+] roots = [208220680240996722513583102044151290091]
27

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

NSSCTF工坊[RSA4] P3 代换降次#

题目#

1
from Crypto.Util.number import *
2
flag = b'NSSCTF{******}'
3

4
p = getPrime(512)
5
q = getPrime(512)
6
n = p*q
7
e = 3
8

9
m1 = bytes_to_long(flag)
10

11
a = getPrime(128)
12
b = getPrime(128)
13
m2 = a*m1 + b
14

15
c1 = pow(m1, e, n)
16
c2 = pow(m2, e, n)
17

18
print(f'n = {n}')
19
print(f'a = {a}')
20
print(f'b = {b}')
21
print(f'c1 = {c1}')
22
print(f'c2 = {c2}')
23

24
'''
25
n = 100458074154921630841467009716211081004496986067171453439200150708921645946139163766441611050743248698408002732330100522747315912617782265320913313460939731072047224701193946357341685422329349168512101723657005099845122860786073559690394636750367940135874243034107367507957642817011696553619030089913082650051
26
a = 235598638113466821523819951671842238817
27
b = 183046284622289531351267591814278208143
28
c1 = 59213026759461784288811267183372841532509333531605324857784387344377914885661521950844577998650904368265218037805476510488318417561718106578315758637105422183211905379616339980270327392640886739452625323181466064322246845738001714864060399808732460864513032069624364554351131806580712989439398464697132652674
29
c2 = 3451970836023636992808694960720139231990590529637727188690993996140273782744393239397467373679391223914185297028545706156586953463105320180151843119949047044046733716896796505869700601788410522957973779842899158545218190431782013633486273807312128458720848868027747769057989052968304813931468091592761421857
30
'''

分析#

m_2= am_1+b\\ c_1 \equiv m_1^3 \pmod{n}\\ c_2 \equiv m_2^3\equiv(am_1+b)^3 \equiv a^3m_1^3+3a^2m_1^2b+ 3am_1b^2+ b^3\pmod{n}

注意到 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$ 以降次

c_2 \equiv a^3c_1+3a^2m_1^2b+ 3am_1b^2+ b^3\pmod{n}

1
from Crypto.Util.number import long_to_bytes
2

3
n = 100458074154921630841467009716211081004496986067171453439200150708921645946139163766441611050743248698408002732330100522747315912617782265320913313460939731072047224701193946357341685422329349168512101723657005099845122860786073559690394636750367940135874243034107367507957642817011696553619030089913082650051
4
a = 235598638113466821523819951671842238817
5
b = 183046284622289531351267591814278208143
6
c1 = 59213026759461784288811267183372841532509333531605324857784387344377914885661521950844577998650904368265218037805476510488318417561718106578315758637105422183211905379616339980270327392640886739452625323181466064322246845738001714864060399808732460864513032069624364554351131806580712989439398464697132652674
7
c2 = 3451970836023636992808694960720139231990590529637727188690993996140273782744393239397467373679391223914185297028545706156586953463105320180151843119949047044046733716896796505869700601788410522957973779842899158545218190431782013633486273807312128458720848868027747769057989052968304813931468091592761421857
8

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

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

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

20
"""
21
[+] roots = [2806865643354785581943930084864034922303658457463090366746051046593966390253248941889426497639009694016125]
22

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

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

题目#

1
from Crypto.Util.number import *
2
flag = b'NSSCTF{******}'
3

4
p = getPrime(700)
5
q = getPrime(700)
6
n = p*q
7
e = 5
8

9
m1 = bytes_to_long(flag)
10

11
a = getPrime(128)
12
b = getPrime(128)
13
m2 = a*m1 + b
14

15
c1 = pow(m1, e, n)
16
c2 = pow(m2, e, n)
17

18
print(f'n = {n}')
19
print(f'a = {a}')
20
print(f'b = {b}')
21
print(f'c1 = {c1}')
22
print(f'c2 = {c2}')
23

24
'''
25
n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
26
a = 285426137705625850725555147387995674019
27
b = 277985464990476154618471183198080357743
28
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
29
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048
30
'''

分析#

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

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

c_1 \equiv m_1 ^ e\\ c_2 \equiv m_2 ^ e\\ m_2 = am_1 + b

易知 $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)$

x - m_1 = \gcd(f, g)

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

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

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

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

最后算出来的gcd 要记得 monic

1
from Crypto.Util.number import long_to_bytes
2

3
n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
4
a = 285426137705625850725555147387995674019
5
b = 277985464990476154618471183198080357743
6
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
7
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048
8
e = 5
9

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

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

15
def gcd(f, g):
16
    while g != 0:
17
        f, g = g, f % g
18
    return f
19

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

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

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

题目#

1
from Crypto.Util.number import *
2
m = bytes_to_long(b'NSSCTF{******}')
3

4
p = getPrime(512)
5
q = getPrime(512)
6

7
n = p*q
8

9
e = 9
10

11
r = getPrime(512)
12

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

16

17
print(f'c1 = {c1}')
18
print(f'c2 = {c2}')
19
print(f'r = {r}')
20
print(f'n = {n}')
21

22

23
'''
24
c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
25
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
26
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
27
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229
28
'''

分析#

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

1
from Crypto.Util.number import long_to_bytes
2

3
c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
4
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
5
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
6
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229
7
e = 9
8

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

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

14
def gcd(f, g):
15
    while g != 0:
16
        f, g = g, f % g
17
    return f
18

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

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

题目#

1
import random
2
from Crypto.Util.number import *
3
m = bytes_to_long(b'NSSCTF{******}')
4
e = 3
5
cnt = 5
6
A = [random.randint(1, 128) for i in range(cnt)]
7
B = [random.randint(1, 1024) for i in range(cnt)]
8
Cs = []
9
Ns = []
10
ds = []
11
for i in range(cnt):
12
    p = getPrime(1024)
13
    q = getPrime(1024)
14
    N = p * q
15
    Ns.append(N)
16
    c = pow(A[i] * m + B[i], e, N)
17
    Cs.append(c)
18

19
print(f'Cs = {Cs}')
20
print(f'Ns = {Ns}')
21
print(f'A = {A}')
22
print(f'B = {B}')
23

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

分析#

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

类似中国剩余定理 CRT

1
from Crypto.Util.number import long_to_bytes
2

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

10
Fs = []
11

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

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

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

NSSCTF工坊[RSA4] P6 SMUPE 问题#

题目#

1
import random
2
from Crypto.Util.number import *
3
m = bytes_to_long(b'NSSCTF{******}')
4
e = [3, 3, 5, 5, 5]
5
cnt = 5
6
A = [random.randint(1, 128) for i in range(cnt)]
7
B = [random.randint(1, 1024) for i in range(cnt)]
8
Cs = []
9
Ns = []
10
ds = []
11
for i in range(cnt):
12
    p = getPrime(1024)
13
    q = getPrime(1024)
14
    N = p * q
15
    Ns.append(N)
16
    c = pow(A[i] * m + B[i], e[i], N)
17
    Cs.append(c)
18

19
print(f'Cs = {Cs}')
20
print(f'Ns = {Ns}')
21
print(f'A = {A}')
22
print(f'B = {B}')
23

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

分析#

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

1
from Crypto.Util.number import long_to_bytes
2

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

9
Fs = []
10

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

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

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

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

1
from Crypto.Util.number import long_to_bytes
2

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

9
max_e = max(e)
10

11
Fs = []
12

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

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

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

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

题目#

1
from Crypto.Util.number import *
2

3
p = getPrime(512)
4
q = getPrime(512)
5

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

8
n = p*q
9
m = bytes_to_long(flag)
10

11
e = 3
12
c = pow(m, e, n)
13

14
print(f'n = {n}')
15
print(f'm = {m>>100}')
16
print(f'c = {c}')
17

18
'''
19
n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
20
m = 2214226572250613833249705195927505959981823363137633354626532745196588970707
21
c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333
22
'''

分析#

$e$ 小， $m$ 大部分高位泄露，设 $m = m_{high} + m_{low}$ ，则 $c \equiv m ^ e \equiv (m_{high} + m_{low})^3$

1
reset()
2
from Crypto.Util.number import long_to_bytes
3

4
k = 100
5
n = 1527542955109141740955682973826193262775892499957309448026045241470857728195657663426381459817190647872750820593934305392986732687654051540838628636529717414135863605586498459487983117670942529496973140251670874510207985224170313618738268651184582186637089407746738836054395760157095709388670653150429457223183161697730087281761369404956762102465246289770300941300936135728738323821631682286737786472020790680432476428922187234364341215016265407571963282147129157
6
mh = 2214226572250613833249705195927505959981823363137633354626532745196588970707
7
mh = mh << k
8
c = 22113876206623661468496987580282614626160320529328454393375952035910523390370709980915981609422504775420007441257006956611997263223244837790238493516238723139514158563675396731542096229586616735753203254810465452822757959264870210654015436735165961713016222816604825816304606749448517022584926571828009062411578367333
9
e = 3
10

11

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

16
roots = f.small_roots()
17
print(roots)
18

19
for root in roots:
20
    root = int(root)
21
    print("\n[+] get root:", root)
22
    print("[*] m =", mh + root)
23
    print("[*]", long_to_bytes(mh + root))
24

25
"""
26
[586224111363642075583459307645]
27

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

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

题目#

1
from Crypto.Util.number import *
2

3
p = getPrime(512)
4
q = getPrime(512)
5

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

8
n = p*q
9
m = bytes_to_long(flag)
10

11
e = 65537
12
c = pow(m, e, n)
13

14
print(f'n = {n}')
15
print(f'p = {p>>100}')
16
print(f'c = {c}')
17

18
'''
19
n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
20
p = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
21
c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223
22
'''

分析#

n = pq = q(p_h + p_l)

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

1
reset()
2
from Crypto.Util.number import long_to_bytes
3

4
k = 100
5

6
e = 0x10001
7
n = 64335017257291288694879798080666629573501118113377179370850991421806469826103134483305987256497147128148330360834028920504233940886960965527818740354522230977284177508093687651712761343376265176857120577153061490788347779327206437787594150381508592990273475278503352979893670354730287704989079247190299342871
8
ph = 7550547038897825994210519739007596111285476244196123253081036462313916767780871742001683690783926938603422562506786339392389
9
ph = ph << k
10
c = 63156227746402147833665215816432368072100003179308515827461336094419526246728847463629131014545663919689064970828884371592840335299717484415279040662500514230579275586231051576688620810169339105201465431624989678170362157914366609856305650090630980489686792938272599406165204410721499875713189193728688835223
11

12

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

15
f = ph + x
16
f = f.monic()
17

18
roots = f.small_roots(X = 2^k, beta = .4)
19
print(roots)
20
for root in roots:
21
    root = int(root)
22
    p = ph + root
23
    print("\n[+] get root:", root)
24
    if n % p != 0:
25
        print("[-] wrong answer")
26
        continue
27
    print("[*] p =", p)
28
    q = n // p
29
    phi = (p-1)*(q-1)
30
    d = int(pow(e, -1, phi))
31
    m = int(pow(c, d, n))
32
    print("[*]", long_to_bytes(m))
33
"""
34
[454816335479034891704851699843]
35

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

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

题目#

1
from Crypto.Util.number import *
2

3
p = getPrime(512)
4
q = getPrime(512)
5

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

8
n = p*q
9
m = bytes_to_long(flag)
10

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

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

19
'''
20
n = 156739515226635581524592797610847324418529702729659760727202454324501479907596255649349406182566636617352761983459648380669151952249526892078378572831346100444943020314226860094300911303589453661009834514243241261318188779118227457185670049393331570167726982038500849886842419000632840251465852441285715712609
21
d = 1865327042408619801352057511348007441275330638921397637214779955824487081626289235627502761209800783644652914147540081431451
22
c = 72260884070910873253619893714557327479300651539617744913822595501549980223259020597000998829262506949824325397279990912888752157554696212466966682483623575703479116305560808218806054242135099446883072418808228726774129042552815016924170283352225826854235696829480360844745488070927932843928843556296485306121
23
'''

分析#

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

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

ed \equiv 1 \pmod {(p-1)(q-1)}\\ 7d = 1 + k (p-1)(q-1) \space (\text{where } k < 7)

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

7d_{low} \equiv 1 + k (p-1)(q-1) \pmod{2^{410}}

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

7d_{low}p \equiv 1 + k(pn - p^2 - n - p) \pmod{2^{410}}

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

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

1
from Crypto.Util.number import long_to_bytes
2

3
n = 156739515226635581524592797610847324418529702729659760727202454324501479907596255649349406182566636617352761983459648380669151952249526892078378572831346100444943020314226860094300911303589453661009834514243241261318188779118227457185670049393331570167726982038500849886842419000632840251465852441285715712609
4
dl = 1865327042408619801352057511348007441275330638921397637214779955824487081626289235627502761209800783644652914147540081431451
5
c = 72260884070910873253619893714557327479300651539617744913822595501549980223259020597000998829262506949824325397279990912888752157554696212466966682483623575703479116305560808218806054242135099446883072418808228726774129042552815016924170283352225826854235696829480360844745488070927932843928843556296485306121
6

7
def get_p_low():
8
    print("get_p_low")
9
    maybe_p_low = []
10
    p = var('p')
11
    for k in range(1, 7+1):
12
        f = k * (n*p - p^2 - n + p) + p - 7*dl*p
13
        roots = solve_mod([f], 2^410)
14
        maybe_p_low += [int(root[0]) for root in roots]
15
        print(f"[+] k =", k,"\troots =", roots)
16
    print("maybe_p_low:", maybe_p_low)
17

18
    maybe_p = []
19
    for p_low in maybe_p_low:
20
        p = get_full_p(p_low)
21
        if p:
22
            maybe_p.append(p)
23

24
    print(maybe_p)
25

26
    for p in maybe_p:
27
        if n % p == 0:
28
            print("Found p:", p)
29
            return p
30

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

39
p = get_p_low()
40
q = n // p
41
assert n == p * q
42

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

46
m = pow(c, d, n)
47
long_to_bytes(m)
48

49
"""
50
get_p_low
51
[+] k = 1   roots = []
52
[+] k = 2   roots = []
53
[+] k = 3   roots = [(15782400274410125266299615039204687648239749624968048772538108316107834343510984483373502800953549213874615211388273835803,), (216175167833235042695566043002922999174165975344341575587144398195111696541111662186439526374789175117314044084502035159091,), (346310384669534424742257269055590207562442091107108658414862505953310729961666657395968108020811191637670221223899952987931,), (546703152228359342171523697019308519088368316826482185229468795832314592159267335099034131594646817541109650097013714311219,), (676838369064658724218214923071975727476644432589249268057186903590513625579822330308562713240668834061465827236411632140059,), (877231136623483641647481351035694039002570658308622794871793193469517487777423008011628736814504459964905256109525393463347,), (1007366353459783023694172577088361247390846774071389877699511301227716521197978003221157318460526476485261433248923311292187,), (1207759121018607941123439005052079558916772999790763404514117591106720383395578680924223342034362102388700862122037072615475,), (1337894337854907323170130231104746767305049115553530487341835698864919416816133676133751923680384118909057039261434990444315,), (1538287105413732240599396659068465078830975341272904014156441988743923279013734353836817947254219744812496468134548751767603,), (1668422322250031622646087885121132287219251457035671096984160096502122312434289349046346528900241761332852645273946669596443,), (1868815089808856540075354313084850598745177682755044623798766386381126174631890026749412552474077387236292074147060430919731,), (1998950306645155922122045539137517807133453798517811706626484494139325208052445021958941134120099403756648251286458348748571,), (2199343074203980839551311967101236118659380024237185233441090784018329070250045699662007157693935029660087680159572110071859,), (2329478291040280221598003193153903327047656139999952316268808891776528103670600694871535739339957046180443857298970027900699,), (2529871058599105139027269621117621638573582365719325843083415181655531965868201372574601762913792672083883286172083789223987,)]
54
[+] k = 4   roots = []
55
[+] k = 5   roots = []
56
[+] k = 6   roots = []
57
[+] k = 7   roots = []
58
maybe_p_low: [15782400274410125266299615039204687648239749624968048772538108316107834343510984483373502800953549213874615211388273835803, 216175167833235042695566043002922999174165975344341575587144398195111696541111662186439526374789175117314044084502035159091, 346310384669534424742257269055590207562442091107108658414862505953310729961666657395968108020811191637670221223899952987931, 546703152228359342171523697019308519088368316826482185229468795832314592159267335099034131594646817541109650097013714311219, 676838369064658724218214923071975727476644432589249268057186903590513625579822330308562713240668834061465827236411632140059, 877231136623483641647481351035694039002570658308622794871793193469517487777423008011628736814504459964905256109525393463347, 1007366353459783023694172577088361247390846774071389877699511301227716521197978003221157318460526476485261433248923311292187, 1207759121018607941123439005052079558916772999790763404514117591106720383395578680924223342034362102388700862122037072615475, 1337894337854907323170130231104746767305049115553530487341835698864919416816133676133751923680384118909057039261434990444315, 1538287105413732240599396659068465078830975341272904014156441988743923279013734353836817947254219744812496468134548751767603, 1668422322250031622646087885121132287219251457035671096984160096502122312434289349046346528900241761332852645273946669596443, 1868815089808856540075354313084850598745177682755044623798766386381126174631890026749412552474077387236292074147060430919731, 1998950306645155922122045539137517807133453798517811706626484494139325208052445021958941134120099403756648251286458348748571, 2199343074203980839551311967101236118659380024237185233441090784018329070250045699662007157693935029660087680159572110071859, 2329478291040280221598003193153903327047656139999952316268808891776528103670600694871535739339957046180443857298970027900699, 2529871058599105139027269621117621638573582365719325843083415181655531965868201372574601762913792672083883286172083789223987]
59
[12808244700891848571681229867945939151349649203736478559496534700297805628016283555802028490128990889103978707177718442769816734510420394810692765321412379, 12237392311510232207733315168168939306945753136553292583198371223481698647146588134299029434945831935900733541708388736093730289336504023586822354826680371]
60
Found p: 12808244700891848571681229867945939151349649203736478559496534700297805628016283555802028490128990889103978707177718442769816734510420394810692765321412379
61
b'NSSCTF{e5430ded-500c-4cc0-9bdb-b4e40a9be3a0}'
62
"""

NSSCTF工坊[RSA4] P11 Boneh and Durfee Attack#

题目#

1
from Crypto.Util.number import *
2

3
p = getPrime(512)
4
q = getPrime(512)
5

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

8
n = p*q
9
m = bytes_to_long(flag)
10

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

15
print(f'n = {n}')
16
print(f'e = {e}')
17
print(f'c = {c}')
18

19
'''
20
n = 160114502501162084436964583573537478796032975208003641998245321466054315024090626426576990670846673676284220472762005347545857048805279326218401844652650972020279579076862422448095751869541093396088035262462766840652498826036642824370917665518133929602675230369722990871966227199496065637730328810028624771799
21
e = 45345940569506069958442629331605385637541863502889625766318025882612322508079296362452308633027956256763871699363730475762179734871820426435674201573024637206928394192742633431788159554008858191365192772486379417021387095234660386008405855409257903024187126197769938866986740500855322639995703897171982472409
22
c = 54804574756729863920967159846060185937697266820658443964397350756668642051647933464063713653569896152539760694973280490768379727191709149635944250514794939902138783777815040318178431874892245462786377699958110644049375757179588739287406833915772871299296750059138805811112990483420256564588150314150915692126
23
'''

分析#

由

d \approx N^{0.27}

估算得:

ed^2 \ge \frac{1}{2} N^{3/2}

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

参考:

拿到新的板板

1
from Crypto.Util.number import *
2

3
N = 160114502501162084436964583573537478796032975208003641998245321466054315024090626426576990670846673676284220472762005347545857048805279326218401844652650972020279579076862422448095751869541093396088035262462766840652498826036642824370917665518133929602675230369722990871966227199496065637730328810028624771799
4
e = 45345940569506069958442629331605385637541863502889625766318025882612322508079296362452308633027956256763871699363730475762179734871820426435674201573024637206928394192742633431788159554008858191365192772486379417021387095234660386008405855409257903024187126197769938866986740500855322639995703897171982472409
5
c = 54804574756729863920967159846060185937697266820658443964397350756668642051647933464063713653569896152539760694973280490768379727191709149635944250514794939902138783777815040318178431874892245462786377699958110644049375757179588739287406833915772871299296750059138805811112990483420256564588150314150915692126
6
"""
7
Setting debug to true will display more informations
8
about the lattice, the bounds, the vectors...
9
"""
10
debug = False
11

12
"""
13
Setting strict to true will stop the algorithm (and
14
return (-1, -1)) if we don't have a correct
15
upperbound on the determinant. Note that this
16
doesn't necesseraly mean that no solutions
17
will be found since the theoretical upperbound is
18
usualy far away from actual results. That is why
19
you should probably use `strict = False`
20
"""
21
strict = False
22

23
"""
24
This is experimental, but has provided remarkable results
25
so far. It tries to reduce the lattice as much as it can
26
while keeping its efficiency. I see no reason not to use
27
this option, but if things don't work, you should try
28
disabling it
29
"""
30
helpful_only = True
31
dimension_min = 7  # stop removing if lattice reaches that dimension
32

33

34
############################################
35
# Functions
36
##########################################
37

38
# display stats on helpful vectors
39
def helpful_vectors(BB, modulus):
40
    nothelpful = 0
41
    for ii in range(BB.dimensions()[0]):
42
        if BB[ii, ii] >= modulus:
43
            nothelpful += 1
44

45
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
46

47

48
# display matrix picture with 0 and X
49
def matrix_overview(BB, bound):
50
    for ii in range(BB.dimensions()[0]):
51
        a = ('%02d ' % ii)
52
        for jj in range(BB.dimensions()[1]):
53
            a += '0' if BB[ii, jj] == 0 else 'X'
54
            if BB.dimensions()[0] < 60:
55
                a += ' '
56
        if BB[ii, ii] >= bound:
57
            a += '~'
58
        print(a)
59

60

61
# tries to remove unhelpful vectors
62
# we start at current = n-1 (last vector)
63
def remove_unhelpful(BB, monomials, bound, current):
64
    # end of our recursive function
65
    if current == -1 or BB.dimensions()[0] <= dimension_min:
66
        return BB
67

68
    # we start by checking from the end
69
    for ii in range(current, -1, -1):
70
        # if it is unhelpful:
71
        if BB[ii, ii] >= bound:
72
            affected_vectors = 0
73
            affected_vector_index = 0
74
            # let's check if it affects other vectors
75
            for jj in range(ii + 1, BB.dimensions()[0]):
76
                # if another vector is affected:
77
                # we increase the count
78
                if BB[jj, ii] != 0:
79
                    affected_vectors += 1
80
                    affected_vector_index = jj
81

82
            # level:0
83
            # if no other vectors end up affected
84
            # we remove it
85
            if affected_vectors == 0:
86
                # print("* removing unhelpful vector", ii)
87
                BB = BB.delete_columns([ii])
88
                BB = BB.delete_rows([ii])
89
                monomials.pop(ii)
90
                BB = remove_unhelpful(BB, monomials, bound, ii - 1)
91
                return BB
92

93
            # level:1
94
            # if just one was affected we check
95
            # if it is affecting someone else
96
            elif affected_vectors == 1:
97
                affected_deeper = True
98
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
99
                    # if it is affecting even one vector
100
                    # we give up on this one
101
                    if BB[kk, affected_vector_index] != 0:
102
                        affected_deeper = False
103
                # remove both it if no other vector was affected and
104
                # this helpful vector is not helpful enough
105
                # compared to our unhelpful one
106
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(
107
                        bound - BB[ii, ii]):
108
                    # print("* removing unhelpful vectors", ii, "and", affected_vector_index)
109
                    BB = BB.delete_columns([affected_vector_index, ii])
110
                    BB = BB.delete_rows([affected_vector_index, ii])
111
                    monomials.pop(affected_vector_index)
112
                    monomials.pop(ii)
113
                    BB = remove_unhelpful(BB, monomials, bound, ii - 1)
114
                    return BB
115
    # nothing happened
116
    return BB
117

118

119
"""
120
Returns:
121
* 0,0   if it fails
122
* -1,-1 if `strict=true`, and determinant doesn't bound
123
* x0,y0 the solutions of `pol`
124
"""
125

126

127
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
128
    """
129
    Boneh and Durfee revisited by Herrmann and May
130

131
    finds a solution if:
132
    * d < N^delta
133
    * |x| < e^delta
134
    * |y| < e^0.5
135
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
136
    """
137

138
    # substitution (Herrman and May)
139
    PR.<u,x,y> = PolynomialRing(ZZ)
140
    Q = PR.quotient(x * y + 1 - u)  # u = xy + 1
141
    polZ = Q(pol).lift()
142

143
    UU = XX * YY + 1
144

145
    # x-shifts
146
    gg = []
147
    for kk in range(mm + 1):
148
        for ii in range(mm - kk + 1):
149
            xshift = x ^ ii * modulus ^ (mm - kk) * polZ(u, x, y) ^ kk
150
            gg.append(xshift)
151
    gg.sort()
152

153
    # x-shifts list of monomials
154
    monomials = []
155
    for polynomial in gg:
156
        for monomial in polynomial.monomials():
157
            if monomial not in monomials:
158
                monomials.append(monomial)
159
    monomials.sort()
160

161
    # y-shifts (selected by Herrman and May)
162
    for jj in range(1, tt + 1):
163
        for kk in range(floor(mm / tt) * jj, mm + 1):
164
            yshift = y ^ jj * polZ(u, x, y) ^ kk * modulus ^ (mm - kk)
165
            yshift = Q(yshift).lift()
166
            gg.append(yshift)  # substitution
167

168
    # y-shifts list of monomials
169
    for jj in range(1, tt + 1):
170
        for kk in range(floor(mm / tt) * jj, mm + 1):
171
            monomials.append(u ^ kk * y ^ jj)
172

173
    # construct lattice B
174
    nn = len(monomials)
175
    BB = Matrix(ZZ, nn)
176
    for ii in range(nn):
177
        BB[ii, 0] = gg[ii](0, 0, 0)
178
        for jj in range(1, ii + 1):
179
            if monomials[jj] in gg[ii].monomials():
180
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU, XX, YY)
181

182
    # Prototype to reduce the lattice
183
    if helpful_only:
184
        # automatically remove
185
        BB = remove_unhelpful(BB, monomials, modulus ^ mm, nn - 1)
186
        # reset dimension
187
        nn = BB.dimensions()[0]
188
        if nn == 0:
189
            print("failure")
190
            return 0, 0
191

192
    # check if vectors are helpful
193
    if debug:
194
        helpful_vectors(BB, modulus ^ mm)
195

196
    # check if determinant is correctly bounded
197
    det = BB.det()
198
    bound = modulus ^ (mm * nn)
199
    if det >= bound:
200
        # print("We do not have det < bound. Solutions might not be found.")
201
        # print("Try with highers m and t.")
202
        if debug:
203
            diff = (log(det) - log(bound)) / log(2)
204
            # print("size det(L) - size e^(m*n) = ", floor(diff))
205
        if strict:
206
            return -1, -1
207
    else:
208
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
209

210
    # display the lattice basis
211
    if debug:
212
        matrix_overview(BB, modulus ^ mm)
213

214
    # LLL
215
    if debug:
216
        print("optimizing basis of the lattice via LLL, this can take a long time")
217

218
    BB = BB.LLL()
219

220
    if debug:
221
        print("LLL is done!")
222

223
    # transform vector i & j -> polynomials 1 & 2
224
    if debug:
225
        print("looking for independent vectors in the lattice")
226
    found_polynomials = False
227

228
    for pol1_idx in range(nn - 1):
229
        for pol2_idx in range(pol1_idx + 1, nn):
230
            # for i and j, create the two polynomials
231
            PR.<w,z> = PolynomialRing(ZZ)
232
            pol1 = pol2 = 0
233
            for jj in range(nn):
234
                pol1 += monomials[jj](w * z + 1, w, z) * BB[pol1_idx, jj] / monomials[jj](UU, XX, YY)
235
                pol2 += monomials[jj](w * z + 1, w, z) * BB[pol2_idx, jj] / monomials[jj](UU, XX, YY)
236

237
            # resultant
238
            PR.<q> = PolynomialRing(ZZ)
239
            rr = pol1.resultant(pol2)
240

241
            # are these good polynomials?
242
            if rr.is_zero() or rr.monomials() == [1]:
243
                continue
244
            else:
245
                # print("found them, using vectors", pol1_idx, "and", pol2_idx)
246
                found_polynomials = True
247
                break
248
        if found_polynomials:
249
            break
250

251
    if not found_polynomials:
252
        # print("no independant vectors could be found. This should very rarely happen...")
253
        return 0, 0
254

255
    rr = rr(q, q)
256

257
    # solutions
258
    soly = rr.roots()
259

260
    if len(soly) == 0:
261
        # print("Your prediction (delta) is too small")
262
        return 0, 0
263

264
    soly = soly[0][0]
265
    ss = pol1(q, soly)
266
    solx = ss.roots()[0][0]
267

268
    #
269
    return solx, soly
270

271

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

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

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

音乐

Coppersmith学习

Coppersmith Method 学习#

学习资料#

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

题目#

分析#

NSSCTF工坊[RSA4] P3 代换降次#

题目#

分析#

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

题目#

分析#

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

题目#

分析#

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

题目#

分析#

NSSCTF工坊[RSA4] P6 SMUPE 问题#

题目#

分析#

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

题目#

分析#

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

题目#

分析#

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

题目#

分析#

NSSCTF工坊[RSA4] P11 Boneh and Durfee Attack#

题目#

分析#

评论区

文章目录

音乐

Coppersmith学习

Coppersmith Method 学习#

学习资料#

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

题目#

分析#

NSSCTF工坊[RSA4] P3 代换降次#

题目#

分析#

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

题目#

分析#

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

题目#

分析#

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

题目#

分析#

NSSCTF工坊[RSA4] P6 SMUPE 问题#

题目#

分析#

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

题目#

分析#

NSSCTF工坊[RSA4] P9 把 nnn 的因数 b≥Nβb \ge N^\betab≥Nβ 当作模数#

题目#

分析#

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

题目#

分析#

NSSCTF工坊[RSA4] P11 Boneh and Durfee Attack#

题目#

分析#

评论区

文章目录

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