RSA部分题型收集

发表于 更新于 阅读次数： Waline： 本文字数： 20k 阅读时长 ≈ 1:13

继上篇RSA入门

感觉所有RSA内容放在一篇博客有些冗长，决定分两个文章进行记录

十二、e和phi不互素

这种情况在比赛中比较常见。在做这类题目之前，建议先了解sagemath基本使用方法

当$e$与$\phi(n)$不互素时，则不存在模$\phi(n)$的逆元$d$使得$ed \equiv 1(mod \quad \phi(n))$

处理方式1:

这种处理方式是最简单也是最常规的

令$t = gcd(e,\phi(n))$

设$e = e’\times t$，则$e’ = \frac{e}{t}$

则$c \equiv m^e \mod n \longrightarrow c \equiv (m ^t)^{e’} \mod n$

求$e’$对应的$d$，解出$m^t \equiv c^d \mod n$

在$m^t < n$的情况下开根即可获得$m$

例题1

task.py

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
import gmpy2
import libnum
import random
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)

while 1:
    e = random.randint(100, 1000)
    p = libnum.generate_prime(1024)
    q = libnum.generate_prime(1024)
    phi_n = (p - 1) * (q - 1)
    t = gmpy2.gcd(e, phi_n)
    if t == e:
        continue
    t1 = e // t
    if gmpy2.invert(t1, phi_n) and t > 1:
        break
n = p * q
c = pow(m, e, n)
print("p=", p)
print("q=", q)
print("e=", e)
print("c=", c)

exp.py

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

p = 171854505164939390402295426493389586289972154851849140728417624619463988154808053805729538974688869671559032639921300088271234681410193379381085714252211392886408792711387524667824537369266846649573070209815436507363007636943912350208275895292853801665488228125846058987049326903498661007035974420392738723323
q = 145951936627745243523384785325963094339728144811023266133546816860787405503371056873662508073284279180417626507724315776654624382665743082805910036891739754019932290977071276850239245644056698685966997752654383650764557358649666141576105936215709831181842086893228254304235678475375978464394818353375373451573
n = p*q
e = 830
c= 4413268199893347044741276120215584703428167052744516280494996526431559720190092261631829389527634625276020346166956540800884139234489942113764564139232948414263452549927818365096023041932432723988241639527832673120924732407691135173154085803338322715604275530735968992726708155724384432557207264839248502158712330572704509492520346044648676055223193900826626346707083590815897507927683083455678855000344499804465073698745769989966769567497677402668725931090596642504740789789740965769347050166069295727209131555338513809368814890255851742010120871635378654904140016065148709710206173069000137023824698858539843753921

phi = (p-1)*(q-1)
t = gmpy2.gcd(e,phi)
if t != 1:
    print(t)
    e1 = e // t
    d = gmpy2.invert(e1,phi)
    m = pow(c,d,n)
    print(long_to_bytes(gmpy2.iroot(m,t)[0]))

处理方式2:

使用sagemath，建立有限域，然后开根，以一个例题简要说明

task.py

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

m = bytes_to_long(flag)
e = 2
p = getPrime(512)
q = getPrime(512)
n = p * q

c = pow(m,e,n)
print(f"c = {c}")
print(f"p = {p}")
print(f"q = {q}")
print(f"n = {n}")

"""
c = 3136716033729406787100895984031132591372408032397380657110411936279557864804613451803228203558942365572618855741582340710496951283998288077886684480798840909615843832888291672118118174611935731391325961
p = 6995170125828760803175021463861846748101755707034027896253692749933464491557662142860042836548188827042797130278821285624095121174944527912522028416084887
q = 12272700813225623560132355056448185486009112345760462061684545263916365691442580749089054915285013385322910087693364777427389347919562222271368766699836367
n = 85849630091910220195429598000499270755938566349764235961421375317755949910077610512936495968854306764812963460054159547290157103999299511719875933657730205460710045409434205381402766954402709130620384187298033137488697869180531872534818830013412093865496100309052022972165149312556870258314510623053681685529
"""

exp.sage

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

c = 3136716033729406787100895984031132591372408032397380657110411936279557864804613451803228203558942365572618855741582340710496951283998288077886684480798840909615843832888291672118118174611935731391325961
p = 6995170125828760803175021463861846748101755707034027896253692749933464491557662142860042836548188827042797130278821285624095121174944527912522028416084887
q = 12272700813225623560132355056448185486009112345760462061684545263916365691442580749089054915285013385322910087693364777427389347919562222271368766699836367
n = 85849630091910220195429598000499270755938566349764235961421375317755949910077610512936495968854306764812963460054159547290157103999299511719875933657730205460710045409434205381402766954402709130620384187298033137488697869180531872534818830013412093865496100309052022972165149312556870258314510623053681685529

R.<x> = PolynomialRing(Zmod(p))
f = x^2 - c
res1 = f.roots()

R.<x> = PolynomialRing(Zmod(q))
f = x^2 - c
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt([int(i[0]),int(j[0])],[p,q])
        print(long_to_bytes(m))

当$m < p$的时候，不需要中国剩余定理也能出

两种处理方式的综合

例题1——2022ctfshow卷王杯

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag

n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)

print(p,q,r,s,t,sep='\n')
print(c)

'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''

看似白给，其实$e$和$\phi(n)$不互素

而且在flag前面填充了一些数据，导致$m^e > n$，所以直接开根号也不可取

本题$c \equiv m^e \mod n$，等价于m满足下面五个式子:
$$
m^2 \equiv c \mod p
$$

$$
m^2 \equiv c \mod q
$$

$$
m^2 \equiv c \mod r
$$

$$
m^2 \equiv c \mod s
$$

$$
m^2 \equiv c \mod t
$$

我们在5个因子下求解，再用中国剩余定理组合即可

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from sympy.ntheory.modular import crt
import gmpy2
from Crypto.Util.number import *

p = 145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q = 116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r = 157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s = 100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t = 93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c = 9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
e = 2

R.<x> = PolynomialRing(Zmod(p))
f = x^e - c
f = f.monic()
res1 = f.roots()

R.<x> = PolynomialRing(Zmod(q))
f = x^e - c
f = f.monic()
res2 = f.roots()

R.<x> = PolynomialRing(Zmod(r))
f = x^e - c
f = f.monic()
res3 = f.roots()

R.<x> = PolynomialRing(Zmod(s))
f = x^e - c
f = f.monic()
res4 = f.roots()

R.<x> = PolynomialRing(Zmod(t))
f = x^e - c
f = f.monic()
res5 = f.roots()


for i in res1:
    for j in res2:
        for k in res3:
            for a in res4:
                for b in res5:
                    m_list = [int(i[0]),int(j[0]),int(k[0]),int(a[0]),int(b[0])]
                    a_list= [p,q,r,s,t]
                    solve = CRT_list(m_list,a_list)
                    flag = long_to_bytes(solve)
                    if b'ctfshow' in flag:
                    	print(flag)
# ctfshow{D0_y0u_R3aLly_Kn0w_Ra8IN_alg0RI7HM?}

例题2——2018高校运维挑战赛AzureRSA

task.txt

1
2
3
4
5
6
7
8
9
10
n1=0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723L
e1=0xfae3aL
c1=0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbeaL
n2=0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63L
e2=0x1f9eaeL
c2=0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347L
assert pow(flag,e1,n1)==c1
assert pow(flag,e2,n2)==c2
assert gcd(e1,(p1-1)*(q1-1))==14
assert gcd(e2,(p2-1)*(q2-1))==14

本题两个n均可分解

分解情况如下:

1
2
3
4
p1 = 12037827528067911684278967221392433256129944002157200272548317200308481572950474775891360447285969682243206009995242277136633522897723532096467191105943909
q1 = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
p2 = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
q2 = 12301580698247665838432962460247894405698817646605188562297985838079356879336309758823376086396761749681729993573203954506346863479448531269351981555913253

我们可以发现$n_1,n_2$之间存在公因数

设$e$和$\phi(n)$的公因数为$t$，则$e = e’t$，$e’ = \frac{e}{t}$，有$e’d \equiv 1 \mod \phi(n)$

$\therefore m^t \equiv c^d \mod n$

本题$t = 14$，于是我们有
$$
res_1 \equiv m^{14} \mod n_1
$$

$$
res_2 \equiv m^{14} \mod n_2
$$

用中国剩余定理解出其特解$res$，即$res \equiv m^{14} \mod lcm(n_1,n_2) \longrightarrow res \equiv m^{14} \mod pq_1q_2$

把它当作一个$e=14$的RSA加密，此时我们计算$\phi(n) = (p_1 - 1)(q_1-1)(q_2-1)$

我们分别求$e = 14$和$p_1 -1 $,$q_1-1$,$q_2-1$的公因数，结果分别是2,14,2

那么我们转换成$res \equiv m^{14} \mod p_1q_2$

我们分别在$\mod p_1$和$\mod q_2$下用有限域开根求出解，再用中国剩余定理

exp.sage

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
n1 = 0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723
e1 = 0xfae3a
c1 = 0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbea
n2 = 0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63
e2 = 0x1f9eae
c2 = 0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347

p1 = 12037827528067911684278967221392433256129944002157200272548317200308481572950474775891360447285969682243206009995242277136633522897723532096467191105943909
q1 = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
p2 = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
q2 = 12301580698247665838432962460247894405698817646605188562297985838079356879336309758823376086396761749681729993573203954506346863479448531269351981555913253


phi1 = (p1-1)*(q1-1)
phi2 = (p2-1)*(q2-1)
def decrypt(c,e,phi,n):
    t = gmpy2.gcd(e,phi)
    if t != 1:
        e1 = e // t
        d = gmpy2.invert(e1,phi)
        m = pow(c,d,n)
        return m
    
res1 = decrypt(c1,e1,phi1,n1)
res2 = decrypt(c2,e2,phi2,n2)


res = crt([res1,res2],[n1,n2])
phi = (p1 - 1)*(q2 - 1)
n = p1 * q2
m2 = decrypt(res,14,phi,n)

R.<x> = PolynomialRing(Zmod(p1))
f = x^2 - m2
sol1 = f.roots()

R.<x> = PolynomialRing(Zmod(q2))
f = x^2 - m2
sol2 = f.roots()

for i in sol1:
    for j in sol2:
        m = crt([int(i[0]),int(j[0])],[p1,q2])
        print(long_to_bytes(m))
        # EIS{Comm0n_Div15or_plus_CRT_is_so_easy|cb2733b9e69ab3a9bd526fa1}

处理方式3：

AMM开根，具体原理可以参考:奇安信攻防社区-有限域上的高次开根AMM算法在RSA上的应用 (butian.net)

例题 2021黑盾杯Crypto1

task.txt

1
2
3
4
5
e = 1801
c = pow(m,e,p)

c =821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998 
p =19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143 

exp.sage

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
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm

e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143

def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result
def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

mp = AMM(c,e,p)
p_proot = findAllPRoot(p, e)
mps = findAllSolutions(mp, p_proot, c, p)

for i in mps:
	flag = long_to_bytes(int(i))
	if b'flag' in flag:
		print(flag)
        # flag{Enj01_m1sc_A0d_cr0}

另一种解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *

e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143

g = pow(2,(p-1) // e,p)
d0 = inverse(e,(p - 1) // e)
m0 = pow(c,d0,p)

for i in range(e):
    m = m0 * pow(g,i,p) % p
    flag = long_to_bytes(m)
    if b"flag" in flag:
        print(flag)

没搞懂原理

十三、Rabin

简单了解一下Rabin加密体制流程

一年后回头再看，Rabin只是e=2的RSA

密钥生成

选取两个大素数$p,q$，并且满足
$$
p \equiv 3 \mod 4
$$

$$
q \equiv 3 \mod 4
$$

即$p,q$都是$4k + 3$形式的素数

接下来计算$n = p\times q$，$(p,q)$作为私钥，$n$作为公钥

加密过程

$$
c \equiv m^2(mod \quad n)
$$

解密过程

$$
\because c \equiv m^2 \mod n
$$

即
$$
c \equiv m ^ 2 \mod p
$$

$$
c \equiv m ^ 2 \mod q
$$

根据二次剩余得

$c^{\frac{p-1}{2}} \equiv 1 \mod p$同乘c得：$c^{\frac{p+1}{2}} \equiv c \mod p$，开根号得$c^{\frac{p+1}{4}} \mod p$，所以$m_p =c^{\frac{p+1}{4}}$

同理$m_q = c^{\frac{q+1}{4}}$

此时得到两个同余式
$$
m \equiv m_p \mod p
$$

$$
m \equiv m_q \mod q
$$

再解中国剩余定理即可

例题

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
import libnum
import random
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
n = p * q
e = 2
c = pow(m, e, n)
print("p=", p)
print("q=", q)
print("n=", n)
print("c=", c)
print("e=", e)

exp.py

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

p= 13314362720917602133969793252481444316247612541287913579795797774897851142465370812511985605994998073433561235021924708067874236781706611485522371488232623
q= 10711516497864529822020903304369858958930042711451857859791558135232705853374332295320094676061294774680048276363750484537945067473851592618816785752809803
n= 142617015943661365869136488949628046624950745436416195175536421279851751774402291519010668496730147866462378904972514253007029491632653461771497495733152729212900224242492221133006321373540619376544526943204146111719397605460529531608654329571698129077171108416638061409327725762114841023226929126272738803269
c= 3136716033731857617369889733308430982192049734478834150612954276064433287574994581343168243135342097712334250357890492021703404008556737899236668582163912130637742227325170121650071435166332685070232329
e= 2

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
# 因为rabin 加密有四种结果，全部列出。
aa = [a, b, c, d]
for i in aa:
    print(long_to_bytes(int(i)))

两次有限域开根再中国剩余定理也可以解

exp.sage

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

p = 13314362720917602133969793252481444316247612541287913579795797774897851142465370812511985605994998073433561235021924708067874236781706611485522371488232623
q = 10711516497864529822020903304369858958930042711451857859791558135232705853374332295320094676061294774680048276363750484537945067473851592618816785752809803
n = 142617015943661365869136488949628046624950745436416195175536421279851751774402291519010668496730147866462378904972514253007029491632653461771497495733152729212900224242492221133006321373540619376544526943204146111719397605460529531608654329571698129077171108416638061409327725762114841023226929126272738803269
c = 3136716033731857617369889733308430982192049734478834150612954276064433287574994581343168243135342097712334250357890492021703404008556737899236668582163912130637742227325170121650071435166332685070232329
e = 2

R.<x> = PolynomialRing(Zmod(p))
f = x^2 - c
res1 = f.roots()

R.<x> = PolynomialRing(Zmod(q))
f = x^2 - c
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt([int(i[0]),int(j[0])],[p,q])
        print(long_to_bytes(int(m)))

多次解Rabin

题目来源NSSCTF ROUND#11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
assert p > q
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)

print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

先当脚本小子

exp.py

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

num1= 134186458247304184975418956047750205959249518467116558944535042073046353646812210914711656218265319503240074967140027248278994209294869476247136854741631971975560846483033205230015783696055443897579440474585892990793595602095853960468928457703619205343030230201261058516219352855127626321847429189498666288452
num2= 142252615203395148320392930915384149783801592719030740337592034613073131106036364733480644482188684184951026866672011061092572389846929838149296357261088256882232316029199097203257003822750826537629358422813658558008420810100860520289261141533787464661186681371090873356089237613080052677646446751824502044253
n= 154128165952806886790805410291540694477027958542517309121222164274741570806324940112942356615458298064007096476638232940977238598879453357856259085001745763666030177657087772721079761302637352680091939676709372354103177660093164629417313468356185431895723026835950366030712541994019375251534778666996491342313
c= 9061020000447780498751583220055526057707259079063266050917693522289697419950637286020502996753375864826169562714946009146452528404466989211057548905704856329650955828939737304126685040898740775635547039660982064419976700425595503919207903099686497044429265908046033565745195837408532764433870408185128447965

tmp = num1+num2

p = gmpy2.gcd(n,tmp)
q = n // p

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

cs = [c]
for i in range(16):
    ps = []
    for c2 in cs:
        r = pow(c2, (p + 1) // 4, p)
        s = pow(c2, (q + 1) // 4, q)

        x = (r * inv_q * q + s * inv_p * p) % n
        y = (r * inv_q * q - s * inv_p * p) % n
        if x not in ps:
            ps.append(x)
        if n - x not in ps:
            ps.append(n - x)
        if y not in ps:
            ps.append(y)
        if n - y not in ps:
            ps.append(n - y)
    cs = ps

for m in cs:
    print(long_to_bytes(m))

下面的三个题型将涉及CopperSmith，师傅们可以通读一遍:密码学学习笔记 之 Coppersmith’s Method | Van1sh的小屋 (jayxv.github.io)

十四、m高位泄露

这类题目会有两种情况，第一种情况是代码很直白的给出m的高位，第二种情况是利用flag头之类的信息来获取高位

情况1：直接给出m的高位

例题

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"

m = libnum.s2n(flag)
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
n = p * q
m1 = ((m >> 300) << 300)
e = 3
c = pow(m, e, n)

print("n =", n)
print("c =", c)
print("e =", e)
print("m1 =", m1)
"""
n = 89449659165373664419599666603079125351786161891254199117045952387178298091726343680198833028457552478360463001966084179577576990766724383528486250298768666097882661565765202949881673799125950008229527772973603379916117935790703989917655837756217393025354969853495238961762669326690100145696530290685977278593
c = 175676150266637032446485438802315236532165610668245377791442524569846934587347877260997089793552024464242407355427955652050327122630649033488529560135042402737218074153101020540979958586399761415542047850951996733997549252310811350769808163958303048261417309757780500291307110596781699418188514782424677
e = 3
m1 = 56006392791978632601307849398736624069259692797382051345599538506145258779412417900757721790977933312
"""

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import long_to_bytes

n = 89449659165373664419599666603079125351786161891254199117045952387178298091726343680198833028457552478360463001966084179577576990766724383528486250298768666097882661565765202949881673799125950008229527772973603379916117935790703989917655837756217393025354969853495238961762669326690100145696530290685977278593
c = 175676150266637032446485438802315236532165610668245377791442524569846934587347877260997089793552024464242407355427955652050327122630649033488529560135042402737218074153101020540979958586399761415542047850951996733997549252310811350769808163958303048261417309757780500291307110596781699418188514782424677
e = 3
m1 = 56006392791978632601307849398736624069259692797382051345599538506145258779412417900757721790977933312


R.<x> = PolynomialRing(Zmod(n))
f = (m1 + x)^e - c
res = f.small_roots(X = 2^300,beta = 1)
if res != []:
	m = m1 + res[0]
	print(long_to_bytes(int(m)))

情况2:利用flag头等已知信息

例题——2024XYCTF 反方向的密码 相思

task.py

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

def hash(x):
    return hashlib.sha256(x.encode()).digest()

def pad(message):
    return message + hash(str(len(message)))

m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)
# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

m可以看为m = bytes_to_long(b"XYCTF{xxxxxxxxxxxxxxxxxxxx}" + pad)

pad可以爆破，所以只需要求解中间未知的字符，就相当于一个m高位和低位泄露的题

exp.sage

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 *
import hashlib

c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

def hash(x):
    return hashlib.sha256(x.encode()).digest()

for i in range(10,40):									#i代表{}中未知数的个数
    prefix = bytes_to_long(b"XYCTF{") * 256^(32 + 1 + i)
    
    pad = hash(str(i+7))
    low = bytes_to_long(b"}" + pad)
    
    R.<x> = PolynomialRing(Zmod(n))
    
    f = (prefix + x*256^33 + low)^3 - c
    f = f.monic()
    res = f.small_roots(X=256^i)
    if res != []:
        m = prefix + int(res[0])*256^33 + low
        print(long_to_bytes(int(m)))
        # XYCTF{!__d3ng__hu0__1@n__3h@n__Chu__!}

十五、p高位泄露

这类题目也有两种情况，第一种情况是代码很直白的给出p的高位，第二种情况是利用其他信息获取p的高位

p的高位泄露是有条件的，经过我的不完全准确的统计(以512bit的p为例)

当beta=0.4时，在未知位数少于等于227bit时，可以恢复p

当beta=0.4,epsilon=0.01时，在未知位数少于等于248bit时，可以恢复p

例题1

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n = p * q
e = 65537
p1 = ((p >> 256) << 256)
c = pow(m, e, n)
print("n =", n)
print("c =", c)
print("e =", e)
print("p1 =", p1)
"""
n = 25412529168113241701978154909309452589891277619233574149177682749114694998754065178357796120946044207438029964927062297462478639487054245771692139625849995546462111249773750389956600652870714030563605023702161513442866609937847422556059608499864578170270126239637444959812121589196901129645564580908045557218006330672260617798453633543627607790892960895904087738679492228779277752739734608284915605638138243297198792777112179909034121738317943791638151509031222745851940804609153731748776002638455252820409482251897734211263626398933847861538578761515233197699408866935293343456161438639398890089434015875977218250399
c = 11832017536820850822990089557724269863899815227776358234936663617587241671432348464674233033185082415100398087268764691266148966050993867487703853445199053612975005945065305992972854436834255574224203980327515867976652513642869374642661621841855735886358661741631500029948344306194937625466742946921106659582316643893949403548828556819907948714983462986507817955376793071143086032085845182853003634916425312911434933416448638808160541352834497686975061092257675653110414264672490891200433992043618040530275350634723043175666891682239033429796170154980192829798607191555482341170827932551423162833473892514972387547888
e = 65537
p1 = 174553077493661081676268351785469032783476528521014320107330821253075206651723812600343204348306643031578070226902979453793372875180300634043015175074746912397887970195415967163417566827459210112867899640388623940244194079258961165834045219906954836822089775153665401751146892024327963835455414059781203165184
"""

exp.sage

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

n = 25412529168113241701978154909309452589891277619233574149177682749114694998754065178357796120946044207438029964927062297462478639487054245771692139625849995546462111249773750389956600652870714030563605023702161513442866609937847422556059608499864578170270126239637444959812121589196901129645564580908045557218006330672260617798453633543627607790892960895904087738679492228779277752739734608284915605638138243297198792777112179909034121738317943791638151509031222745851940804609153731748776002638455252820409482251897734211263626398933847861538578761515233197699408866935293343456161438639398890089434015875977218250399
c = 11832017536820850822990089557724269863899815227776358234936663617587241671432348464674233033185082415100398087268764691266148966050993867487703853445199053612975005945065305992972854436834255574224203980327515867976652513642869374642661621841855735886358661741631500029948344306194937625466742946921106659582316643893949403548828556819907948714983462986507817955376793071143086032085845182853003634916425312911434933416448638808160541352834497686975061092257675653110414264672490891200433992043618040530275350634723043175666891682239033429796170154980192829798607191555482341170827932551423162833473892514972387547888
e = 65537
p_high = 174553077493661081676268351785469032783476528521014320107330821253075206651723812600343204348306643031578070226902979453793372875180300634043015175074746912397887970195415967163417566827459210112867899640388623940244194079258961165834045219906954836822089775153665401751146892024327963835455414059781203165184

R.<x> = PolynomialRing(Zmod(n))
f = p_high + x
res = f.small_roots(X = 2^256,beta = 0.4)
if res != []:
    p = p_high + int(res[0])
    q = n // p
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))

例题2——2023LitCTF Babyxor

task.py

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

m = bytes_to_long(flag)
assert len(flag)==32
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = p^m
c2 = pow(m,e,n)	
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
"""
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
"""

因为flag长度为32，转为int的值为256bit，因为p为512的数，所以p ^ m的高256bit和p的高256bit是一样的，间接告诉我们p的高位

这个未知位数不太满足我们前面说的攻击条件，差了8位，因此需要做一点爆破

exp.sage

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
import gmpy2
from tqdm import *
from Crypto.Util.number import *

n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
e = 65537
pbits = 512

p_high = c1 >> 256
for i in trange(2**8):
    p4 = p_high << 8			#这里需要先爆破8位，使得知道264位以后再恢复p
    p4 = p4 + i
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    R.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    res = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
    if res != []:
        p = p4 + int(x[0])
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c2,d,n)
        print(long_to_bytes(int(m)))
        break

#LitCTF{oh!!!!coppersmith_is_fun}

例题3

有些题目不一定给出高位，还有可能给出低位，甚至给出部分高位和部分低位。其本质是一样的，我们只需要改变多项式即可

task.py

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


p, q = getPrime(1024), getPrime(1024)
N = p * q
p0 = p ^ (bytes_to_long(flag)<<444)		
m = bytes_to_long(flag)
c = pow(m, 65537, N)
print(len(flag))
print('c=',c)
print('N=',N)
print('p0=',p0)


# 54	
# c= 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149
# N= 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943
# p0= 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191

因为m左移444位，这样子m后面444位都是0，所以异或之后，不影响p低位444值

根据flag长度是54，转成int数据就432bit，左移444位后是876位，异或之后，p的高(1024 - 876) = 148位也是不变的。所以我们有了p的部分高位和低位

还是利用coppersmith，改个多项式即可

exp.sage

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

p0 = 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191
c = 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149
n = 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943
e = 65537

phigh = p0 >> 876 <<876
tmp = int("1" * 444,2)
plow = p0 & tmp

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

f = phigh + x*2**444 + plow
f = f.monic()
res = f.small_roots(X=2^432,beta=0.4)
if res != []:
    p = int(phigh + res[0]*2**444+plow)
    print("p =",p)
    q = n // p
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))

十六、d低位泄露

攻击条件:e在可爆破范围，并且已知d的低位

推导:
$$
\because ed \equiv 1 \mod \phi(n)
$$

$$
\therefore ed = k(p-1)(q-1) + 1
$$

即
$$
ed = kn - kp - kq + k + 1
$$
假设我们知道d的低L位，并且记为$d_{low}$，我们对上式同模$2^L$，于是有
$$
ed_{low} \equiv kn - kp - kq + k + 1 \mod 2^L
$$
两边同时乘上p得到
$$
ed_{low} \equiv knp -kp^2 - kn +(k+1)p \mod 2^L
$$
此时上式只有k和p是未知的，因为$0 < k < e$，所以可对k进行爆破，解同余式得到p的低位，再用coppersmith恢复p

例题

task.py

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
import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
while True:
    p = libnum.generate_prime(512)
    q = libnum.generate_prime(512)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 3
    if gmpy2.gcd(e, phi_n) == 1:
        break

d = gmpy2.invert(e, phi_n)
d1 = d & ((1 << 486) - 1)
c = pow(m, e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("dlow =", d1)
"""
n = 52742121495363456830645578439066440260525635701449452038623040460534514676940962601979528301396249463310635013618692939847284377316096998174539886900202801371512846078230196507601167693580439935790730812348102969592553942497201279143623565409782692807615767067494338127711608771029145341503069929345973282553
e = 3
c = 175676150266403096249431407570554929021369604168136874268275844375181688894753012319267533769923727863698572157250017689244151605424698000831986135513112136594197978237874400825236288135820643994889528170234514127521418132167932446836545721803621236277931291609749528037915073270452302613264065194049125
dlow = 8681746171122274095992828774600905650260279086049883317863420271848455130773826835383939352151607850521826888046119078445911475580784484455485323
"""

exp.sage

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
from Crypto.Util.number import long_to_bytes,inverse
from tqdm import *

n = 52742121495363456830645578439066440260525635701449452038623040460534514676940962601979528301396249463310635013618692939847284377316096998174539886900202801371512846078230196507601167693580439935790730812348102969592553942497201279143623565409782692807615767067494338127711608771029145341503069929345973282553
e = 3
c = 175676150266403096249431407570554929021369604168136874268275844375181688894753012319267533769923727863698572157250017689244151605424698000831986135513112136594197978237874400825236288135820643994889528170234514127521418132167932446836545721803621236277931291609749528037915073270452302613264065194049125
dlow = 8681746171122274095992828774600905650260279086049883317863420271848455130773826835383939352151607850521826888046119078445911475580784484455485323

def get_full_p(p_low,n,pbits):
    kbits = p_low.bit_length()
    R.<x> = PolynomialRing(Zmod(n))
    f = x * 2^kbits + p_low
    f = f.monic()
    res = f.small_roots(X = 2^(pbits-kbits),beta=0.4)
    if res != []:
        p = int(res[0]) * 2^kbits + p_low
        return p
    
for k in trange(e):
    var('p')
    f1 = e*dlow*p - (k*n*p - k*p^2 - k*n + (k+1)*p)
    roots = solve_mod(f1,2^486)
    if roots != []:
        for root in roots:
            if int(root[0]).bit_length() == 486:
                p = get_full_p(int(root[0]),n,512)
                if p:
                    q = n // p
                    d = inverse(3,(p-1)*(q-1))
                    m = pow(c,d,n)
                    print(long_to_bytes(m))
                    break

2023强网拟态决赛——BadRSA

task.py

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 *

f = open('flag.txt','rb')
m = bytes_to_long(f.readline().strip())

p = getPrime(512)
q = getPrime(512)
e = getPrime(8)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
leak = d & ((1<<265) - 1)

print(f'e = {e}')
print(f'leak = {leak}')
print(f'n = {n}')
c = pow(m,e,n)
print(f'c = {c}')

'''
e = 149
leak = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299
'''

由$ed \equiv 1 \mod \phi(n)$

即$ed = k(p-1)(q-1) + 1$

两边同时模$2^{265}$，得$ed_0 \equiv k(p-1)(q-1) + 1 \mod 2^{265}$，这里$d_0 = leak$

$\therefore ed_0 \equiv k(pq - p - q + 1) + 1 \mod 2^{265}$

再同乘$p$，得到$ed_0p \equiv knp - kp^2 - kn + kp + p \mod 2^{265}$

因为$d \approx 1023bit$

所以$k < e$

爆破$k$，解方程得到$p$的低位，然后用copper恢复$p$

要调copper的参数，解方程得到的只有$p$的低265位,还差247位

exp.sage

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

e = 149
d0 = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299

for k in range(1,e):
    var("p")
    temp = e*d0*p
    f = (k*n*p - k*p^2 - k*n + k*p + p) - temp  == 0

    roots = solve_mod([f],2^265)
    if roots != []:
        for root in roots:
            plow = int(root[0])
#             print(plow)
# 55136429770900518182274612434328885021714880080534773062619965935822096183916139
            R.<x> = PolynomialRing(Zmod(n))
            
            f1 = x*2^265 + plow
            f1 = f1.monic()
            res = f1.small_roots(X=2^247,beta=0.5,epsilon = 0.01)
            if res != []:
                print(res)
                # [188210689227294472160085325314952069542671020803828390144430392548173787275]
                p = int(res[0])*2^265 + plow
                print("p =",p)
                # p = 11158174168280917736979570452068827611755694573672250873587467083259280584739528118050085070475912733864211083865201596017044398008278425498714490994488939
                q = n // p
                d = gmpy2.invert(e,(p-1)*(q-1))
                m = pow(c,d,n)
                print(long_to_bytes(int(m)))
                # flag{827ccb0eea8a706c4c34a16891f84e7b}
                break

这里beta = 0.5是因为，对于度（即最大次方）为$d$的多项式，要求根小于$n^{\frac{\beta^2}{d} - \epsilon}$，而且要求因子$p > n^{\beta}$

此题$d = 1$，经过计算我们要求的根的上界为$2^{247}$，$\frac{247}{1024} = 0.2412$，所以取beta = 0.5可以恢复p。界这个东西感觉有点玄学，只能多做题多感受了

十七、Franklin-Reiter相关消息攻击

攻击条件:

当Alice使用同一公钥对两个具有线性关系的消息$M_1,M_2$进行加密，并将加密后的消息$C_1,C_2$发送给了Bob，我们就可能可以获得对应的消息$M_1,M_2$。假设模数为$N$，$M_1,M_2$的线性关系如下：

$M_1 \equiv f(M_2) \mod N$

其中$f$为一个线性函数，比如$f = ax+b$

存脚本就好了

例题1

task.py

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

m1 = bytes_to_long(flag)
N = getPrime(512)*getPrime(512)
e = 17

c1 = pow(m1, e, N)

a = getRandomNBitInteger(512)
b = getRandomNBitInteger(512)
m2 = a * m1 + b
c2 = pow(m2, e, N)

print(N, a, b, c1, c2, sep="\n")

# 51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
# 13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
# 12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
# 18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
# 14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import libnum

n = 51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a = 13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
b = 12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
c1 = 18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2 = 14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720
e = 17

def franklinReiter(n,e,c1,c2,a,b):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (a*x+b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() 
    return -gcd(g1, g2)[0]

m = franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))

例题2——SICTFround2 签到题来咯

task.py

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
e = getPrime(10)
n = p*q
c1 = pow(114*m+2333,e,n)
c2 = pow(514*m+4555,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
'''
n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931
'''

本题未知e，爆破一下e即可

exp.sage

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
# sage
import libnum
from Crypto.Util.number import *

n = 
c1 = 
c2 = 
E = []

for i in range(2^9,2^10):
    if isPrime(i):
        E.append(i)
        
def franklinReiter(n,e,c1,c2):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (114*x + 2333)^e - c1
    g2 = (514*x + 4555)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

# print(E)
for e in E:
    m = franklinReiter(n,e,c1,c2)
    flag = long_to_bytes(int(m))
    if b'SICTF' in flag:
        print(flag)
        break
    else:
        continue

例题3——2023领航杯 RSA3

在前面的例子中，加密指数都不太大，脚本运行起来都算快。接下来这道例题，加密指数e为65537，如果不使用更优的方法，会很浪费时间

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

参考：HALF-GCD算法的阐述_half gcd_Entropy Increaser的博客-CSDN博客

多项式 gcd 的正确姿势：Half-GCD 算法 - whx1003 - 博客园 (cnblogs.com)

脚本来源：rkm0959_implements/Half_GCD/code.sage at main · rkm0959/rkm0959_implements (github.com)

我们引入使用了HGCD算法的Franklin-Reiter相关消息攻击的脚本

exp.sage

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

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 
n2 = 
c1 = 
c2 = 
R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
#CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}

十八、Boneh-Durfee攻击

攻击条件:$d < N^{0.292}$

存脚本即可

exp.sage

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
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
from __future__ import print_function
import time

############################################
# Config
##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
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

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 0xc2fd2913bae61f845ac94e4ee1bb10d8531dda830d31bb221dac5f179a8f883f15046d7aa179aff848db2734b8f88cc73d09f35c445c74ee35b01a96eb7b0a6ad9cb9ccd6c02c3f8c55ecabb55501bb2c318a38cac2db69d510e152756054aaed064ac2a454e46d9b3b755b67b46906fbff8dd9aeca6755909333f5f81bf74db
    # the public exponent
    e = 0x19441f679c9609f2484eb9b2658d7138252b847b2ed8ad182be7976ed57a3e441af14897ce041f3e07916445b88181c22f510150584eee4b0f776a5a487a4472a99f2ddc95efdd2b380ab4480533808b8c92e63ace57fb42bac8315fa487d03bec86d854314bc2ec4f99b192bb98710be151599d60f224114f6b33f47e357517

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .18 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    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

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

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

    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("private key found:", d)
    else:
        print("=== no solution was found ===")

    if debug:
        print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()

例题 2023楚慧杯——so large e

task.py

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
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from flag import flag
import random

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = random.getrandbits(1024)
assert size(e)==1024
phi = (p-1)*(q-1)
assert GCD(e,phi)==1
d = inverse(e,phi)
assert size(d)==269

pub = (n, e)
PublicKey = RSA.construct(pub)
with open('pub.pem', 'wb') as f :
    f.write(PublicKey.exportKey())

c = pow(m,e,n)
print('c =',c)

print(long_to_bytes(pow(c,d,n)))


#c = 6838759631922176040297411386959306230064807618456930982742841698524622016849807235726065272136043603027166249075560058232683230155346614429566511309977857815138004298815137913729662337535371277019856193898546849896085411001528569293727010020290576888205244471943227253000727727343731590226737192613447347860

提取公钥得到n,e

发现$\frac{d}{n} = 0.26269$

多半就是boneh_durfee攻击手段

改改example()函数的delta和m即可

delta就是$\frac{d}{n}$的大小

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
#sage
from __future__ import print_function
import time

############################################
# Config
##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
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

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 116518679305515263290840706715579691213922169271634579327519562902613543582623449606741546472920401997930041388553141909069487589461948798111698856100819163407893673249162209631978914843896272256274862501461321020961958367098759183487116417487922645782638510876609728886007680825340200888068103951956139343723
    e = 113449247876071397911206070019495939088171696712182747502133063172021565345788627261740950665891922659340020397229619329204520999096535909867327960323598168596664323692312516466648588320607291284630435682282630745947689431909998401389566081966753438869725583665294310689820290368901166811028660086977458571233
    # the public exponent
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .27 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 5 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    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

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

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

    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("private key found:", d)
    else:
        print("=== no solution was found ===")

    if debug:
        print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()

例题 2023领航杯 bd

task.py

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 *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)


print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

"""
n = 73337798113265277242402875272164983073482378701520700321577706460042584510776095519204866950129951930143711572581533177043149866218358557626070702546982947219557280493881836314492046745063916644418320245218549690820002504737756133747743286301499039227014032044403571945455215839074583290324966069724343874361
e = 42681919079074901709680276679968298324860328305878264036188155781983964226653746568102282190906458519960811259171162918944726137301701132135900454469634110653076655027353831375989861927565774719655974876907429954299669710134188543166679161864800926130527741511760447090995444554722545165685959110788876766283
c = 35616516401097721876690503261383371143934066789806504179229622323608172352486702183654617788750099596415052166506074598646146147151595929618406796332682042252530491640781065608144381326123387506000855818316664510273026302748073274714692374375426255513608075674924804166600192903250052744024508330641045908599
hint1 = 740477612377832718425
hint2 = 767891335159501447918
"""

这是一种利用上p,q高位的boneh-durfee，论文:367.pdf (iacr.org)

对大佬实验的脚本进行修改：Codes of the manuscript—Practical Attacks on Small Private Exponent RSA—New Records and New Insi - Pastebin.com

这类题没太搞懂原理，只能当个脚本小子先

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
import time
time.clock = time.time
 
debug = True
 
strict = False
 
helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
# 显示有用矢量的统计数据
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")
    
# 显示带有 0 和 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)

# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1（最后一个向量）开始
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
    
    # 开始从后面检查
    for ii in range(current, -1, -1):
        #  如果它没有用
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
             # 让我们检查它是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果另一个向量受到影响：
                # 我们增加计数
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
 
            # 等级：0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            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
 
           # 等级：1
            #如果只有一个受到影响，我们会检查
            # 如果它正在影响别的向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果它影响哪怕一个向量
                    # 我们放弃这个
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受到影响，则将其删除，并且
                # 这个有用的向量不够有用
                #与我们无用的相比
                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 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
 
 在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 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-移位
    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 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
 
    # y-移位
    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 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)
 
    # 构造格 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)
 
    #约化格的原型
    if helpful_only:
        #  #自动删除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0
 
    # 检查向量是否有帮助
    if debug:
        helpful_vectors(BB, modulus^mm)
 
    # 检查行列式是否正确界定
    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.BKZ(block_size=25)
    BB = BB.LLL()
 
    if debug:
        print ("LLL is done!")
 
    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
 
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
 
            # 对于i and j, 构造两个多项式
 
            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)
 
            # 结果
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
 
 
            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
 
def example():
    ############################################
    # 随机生成数据
    ##########################################
    #start_time =time.perf_counter
    start =time.clock()
    size = 512
    length_N = 2*size
    ss = 0
    s = 70
    M = 1   # the number of experiments
    delta = 299/1024

    for i in range(M):
#         p =  random_prime(2^size,None,2^(size-1))
#         q =  random_prime(2^size,None,2^(size-1))
#         if(p<q):
#             temp=p
#             p=q
#             q=temp
        N = 73337798113265277242402875272164983073482378701520700321577706460042584510776095519204866950129951930143711572581533177043149866218358557626070702546982947219557280493881836314492046745063916644418320245218549690820002504737756133747743286301499039227014032044403571945455215839074583290324966069724343874361
        e = 42681919079074901709680276679968298324860328305878264036188155781983964226653746568102282190906458519960811259171162918944726137301701132135900454469634110653076655027353831375989861927565774719655974876907429954299669710134188543166679161864800926130527741511760447090995444554722545165685959110788876766283
        hint1 = 740477612377832718425   # p高位
        hint2 = 767891335159501447918  # q高位
#         print ("p真实高",s,"比特：", int(p/2^(512-s)))
#         print ("q真实高",s,"比特：", int(q/2^(512-s)))
#         N = p*q;
 
 
    # 解密指数d的指数( 最大0.292)  
    
        m = 7   # 格大小（越大越好/越慢）
        t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
        X = floor(N^delta)  # 
        Y = floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同，则正确
        for l in range(int(hint1),int(hint1)+1):
            print('\n\n\n l=',l)
            pM=l;
            p0=pM*2^(size-s)+2^(size-s)-1;
            q0=N/p0;
            qM=int(q0/2^(size-s))
            A = N + 1-pM*2^(size-s)-qM*2^(size-s);
        #A = N+1
            P.<x,y> = PolynomialRing(ZZ)
            pol = 1 + x * (A + y)  #构建的方程
 
            # Checking bounds
            #if debug:
                #print ("=== 核对数据 ===")
                #print ("* delta:", delta)
                #print ("* delta < 0.292", delta < 0.292)
                #print ("* size of e:", ceil(log(e)/log(2)))  # e的bit数
                # print ("* size of N:", len(bin(N)))          # N的bit数
                #print ("* size of N:", ceil(log(N)/log(2)))  # N的bit数
                #print ("* m:", m, ", t:", t)
 
            # boneh_durfee
            if debug:
                ##print ("=== running algorithm ===")
                start_time = time.time()
 
 
            solx, soly = boneh_durfee(pol, e, m, t, X, Y)
 
 
            if solx > 0:
                #print ("=== solution found ===")
                if False:
                    print ("x:", solx)
                    print ("y:", soly)
 
                d_sol = int(pol(solx, soly) / e)
                ss=ss+1

                print ("=== solution found ===")
                print ("p的高比特为：",l)
                print ("q的高比特为：",qM)
                print ("d=",d_sol) 
 
            if debug:
                print("=== %s seconds ===" % (time.time() - start_time))
            #break
        print("ss=",ss)
                            #end=time.process_time
        end=time.clock()
        print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
    example()

十九、一些和数论推导相关的题目

1.hint = pow(ap+b,q,n)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import libnum
import gmpy2
import uuid
from Crypto.Util.number import *

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)

e = 65537
p = getPrime(1024)
q = getPrime(1024
n = p * q
c = pow(m, e, n)
hint = pow(2020 * p + 2021, q, n)
print(f'n={n}')
print(f'c={c}')
print(f'hint={hint}')

把hint展开
$$
hint \equiv (2020p + 2021)^q \mod n
$$
模$p$能得到
$$
hint \equiv 2021^q \mod p
$$
两边同时取p次方
$$
hint^p \equiv 2021^n \mod p
$$
即
$$
hint \equiv 2021^n \mod p
$$
p = gcd(pow(2021,n,n) - hint,n)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

n = 27020725261160598541077357737650775795182555998856810737571508044949928734067444441660366270392732456051807439301564552672200975582350577967001486740668193835704559129378410828266554536148151615878808327988333060924165410762016082268322936465413880236634083213834739549234631742766416876749808978934944262651307600621868854944164060642189749365967978497831698002669974744487926082412272998646851047638183126945784060957075393737537570645086672473571281053798891685646561828588448040073373363454584468753860529849749093081434144360661566815886630699933232263079413562069476421802192735693386029862725050469209845710383
c = 10188807385387617708190575473905502994151677148079820873886980571555051900701810208218351138721306416600688313703084580808183634201231599134123549448962443376514560489130860694363901933597676373555599555647232128717993571185822894818704143675318690577221330618533739592165564396729937983659337232822442555504262694675199751730664450120569727835850996566436129543730932040989365233424791093843941154003052950306359994891955336607690065213304872738280674213630736611351982705373394299097653653497017756036211550125607093109216729483090391729134062236908282557149575812220142872855836932590459512028618076264332235518829
hint = 15179972145975733285419381814235528011288991423484121653543845156913121513320504879647666067298415751234264897435338898933073713420024176276221164394369781676781604128149168834126855517212300158864797800121336042194751965268493010327202598446572764475343894613152062609436699715193914479572113800212525965140106015838636914979735618606768207651697548364440806425770871133439416876157686985836939255598747973339866125864303982956813846287509191028829738926404992619459242904729015823730553526572575372668559669124599614613391797015393641171177282129497503752370800088634017972208535899870704612274473042064675033593148
e = 65537

p = gmpy2.gcd(pow(2021,n,n)-hint,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

2.hint = pow(ap+b,e,n)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
e = 65537
n = p * q
h = 20211102
hc = pow(h + p * 1111, e, n)
c = pow(m, e, n)
print("hc=", hc)
print("n=", n)
print("c=", c)
hc = 71505320953946158049530109094654497075489963071106175336722892393493112481336409391299522595724154571954223093317880494307263262649833222750675105885636892419350501821324979706283867758665536771783209816719106279467902518895579024290387800216711663670572861182058425925280993190282267615052256942516011995207
n = 76856511192427852645963041043072791148703422665129663050712492700760489247788743818199589072069758934570218804936479267319288093436111548055922916898782764333246946326823653877357695179165138863843657328764265204547147092074499832221138997131011222722917338444675582832114206750168113207646100633238664244737
c = 39246179387125192271554620313966311736032348078183121707012959204367908070472764506984235827179206718838172586811066682034907967943722841257765922283692526422653916506577810629430853963448057701574209912936660396486847365579797147723437378122880075493171892191049105237005801787649587080840600670585409293046

$$
hint \equiv (ap + b)^e \mod n
$$

两边模p得到
$$
hint \equiv b^e \mod p
$$
p = gcd(pow(b,e,n)-hint,n)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2

hint = 71505320953946158049530109094654497075489963071106175336722892393493112481336409391299522595724154571954223093317880494307263262649833222750675105885636892419350501821324979706283867758665536771783209816719106279467902518895579024290387800216711663670572861182058425925280993190282267615052256942516011995207
n = 76856511192427852645963041043072791148703422665129663050712492700760489247788743818199589072069758934570218804936479267319288093436111548055922916898782764333246946326823653877357695179165138863843657328764265204547147092074499832221138997131011222722917338444675582832114206750168113207646100633238664244737
c = 39246179387125192271554620313966311736032348078183121707012959204367908070472764506984235827179206718838172586811066682034907967943722841257765922283692526422653916506577810629430853963448057701574209912936660396486847365579797147723437378122880075493171892191049105237005801787649587080840600670585409293046
e = 65537
b = 20211102

p = gmpy2.gcd(pow(b,e,n)-hint,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

3.q = inverse(e,p)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
e = 65537

while 1:
    p = libnum.generate_prime(512)
    q = libnum.invmod(e, p)
    if gmpy2.is_prime(q):
        break
n=p*q
c=pow(m,e,n)
print("n=",n)
print("c=",c)

$$
eq \equiv 1 \mod p
$$

所以有
$$
eq = kp + 1
$$
两边同时乘$p$
$$
en = kp^2 + 1
$$
这个k和e差不多大，在e不太大的情况下可以枚举k解这个方程

还有个方法就是

从$en = kp^2 + 1$，凑出$4ken + 1 = (2kp+1)^2$

所以$p = \frac{(4ken+1)^{\frac{1}{2}}-1}{2k}$

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2

n = 58204114420266684815970658378327773998564393394613074044159240444415512492622689982761518905542522328879289101538953676661805875053162972893258897360344016406294652339343767887745752686437325346837603712186500309908703326587069304255508650910107794737000566778637055164127273830551001009133332601839918695739
c = 43430611858598126654595145883807180034546121754009334579568652220639483233618841529702503298293207886941913478597477904682701187000781983315547295293641024286170190626012102497319037012751300959255076727985925313853559910457404758461819072120343343943528618993507783981659418177044469142912677141806591464788
e = 65537

for k in range(1,e):
    t = gmpy2.iroot((4*k*e*n + 1),2)
    if t[1]:
        p = (t[0]-1) // (2*k)
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
        break

4.pow(m,p,n)和pow(m,q,n)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
n=p*q
x=pow(m,p,n)
y=pow(m,q,n)
print("n=",n)
print("x=",x)
print("y=",y)

$$
x \equiv m ^ p \mod n
$$

由费马小定理得
$$
x \equiv m \mod p
$$
同理
$$
y \equiv m \mod q
$$
即
$$
x = k_1p + m
$$

$$
y = k_2q + m
$$

相乘之后得到
$$
xy = m^2 + (k_1p+k_2q)m + k_1k_2n
$$
再次化简
$$
xy \equiv m^2 + (x-m + y - m)m \mod n
$$
然后用copper解

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

n = 119168018353396473071220326930634033296857570351877525203349067654228903288865563346158289110924833018314600851680403536994000145188490252887831026813814036968773088160020677568623347649228357482873911613625537196000702331852604517461327776409524836030721808860499640682583008287503643735346752806150919473547
x = 20889450245206188360163017466832661797042512279294313816641964974342193835127401896327018708629718120262511077145232274218469726065543657294173612852238031375768722870519066517281989421725687761586428233882899166319861093186744865410310768961853709659722549327714475931676224727563796969392665870925936060875
y = 32080707538492572190029237251694217148237404571842762312567934187316746458298295007401945958852986479911593108750816992042333214302313415615710205763277908672519589955718578006218124903939275787171888825356704546781455848117466648569999021535956085557973651213126679157398458139672913801297571585910183741493

R.<m> = PolynomialRing(Zmod(n))

f = x*y - m^2 - m*(x - m + y - m)
f = f.monic()
root = f.small_roots(X=2^336)
if root != []:
    print(long_to_bytes(int(root[0])))

5.leak = d + p

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"

m = bytes_to_long(flag.encode())
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = inverse(e,(p-1)*(q-1))

leak = d + p
c = pow(m,e,n)
print(f"leak = {leak}")
print(f"c = {c}")
print(f"n = {n}")

$$
leak = d + p
$$

同时乘上e
$$
leak \times e = ed + ep
$$

$$
\because ed = k(p-1)(q-1) + 1
$$

$$
\therefore leak \times e = k(p-1)(q-1) + ep + 1 = (k_1 + e)(p-1) + e + 1
$$

则
$$
2^{leak\times e} \equiv 2^{(p-1)(k_1+e)+e+1} \equiv 2^{e+1} \mod p
$$
p = gcd(pow(2,e*leak,n) - pow(2,e+1,n),n)

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

leak = 43773730595208010615167769243389712919043986781372553925103531305753192121900940758872887224717935746491356121136709395293427821519713664465479239343568683512805566797519940659245386786069452631897152582632812964236464253538638932777814445952543179981728372597574240011522586022744496408528369815424689627714
c = 32609109759602838902299290553935199233727818772965249106067660946940666082748851189532358246129713630287421754985189526470019256048805899987261287835158990237267846168718587057488187109882012577904592602367187436017302897260666096753156638501800052563311351183911829268477864436682312113353547663292164618797
n = 73687428902140845363357908478989818544523419338611246958530518113252515978963884581173646615800353308789787478447973996695401703969420384980841285031836556985268236880854319562700104921035182736733530699304849659644263120110205601793351720111745179867010541532557489688430577820860370652773129870929371931513
e = 65537

p = gmpy2.gcd(pow(2,leak * e,n) - pow(2,e + 1,n),n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

接下来三个题型来源于2023 数据安全产业人才能力挑战赛—math_exam

6.leak = (n + p) % (q-1)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
if p <= q:
    p, q = q, p
e = 0x10001
n = p * q
c = pow(m, e, n)
leak = (n + p) % (q-1)
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')

#e = 65537
#c = 846622880180923496523897101093587388412673197929101816777894080453907929979417582433675846206418833989406082027835614960931951892393700870678469052366477889491688459558189367255658278968722099012534045477993924284003153851171132420751750724394405070269223797513951991873714156884423926582172189394011114952
#n = 159452716285492879108396025652299064897348745847754101475050126796260046052685162344131542880739092630022413124977374334652652450809186959288635651980201026825896903174847709657312399801033678426271413442323084354665643010763178857967804623680894444913369256168333223214048037661178587978535722147091129404833
#leak = 2669103705669857828725305123419482758456336465207378766363532584323475128597302561377245054918781031448710846825859151788151496659511563529987056456136018

$$
leak \equiv (n + p) \mod q-1
$$

即
$$
leak \equiv p(q + 1) \mod q-1
$$

$$
\therefore leak \equiv 2p \mod q-1
$$

题目确定了$p > q$
$$
\therefore p \mod q-1 = p - q + 1
$$

$$
\therefore leak \equiv 2(p-q + 1)
$$

再联立$n = p \times q$解方程即可分解n

exp.py

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 *
from sympy import solve,symbols
import gmpy2

e = 65537
c = 846622880180923496523897101093587388412673197929101816777894080453907929979417582433675846206418833989406082027835614960931951892393700870678469052366477889491688459558189367255658278968722099012534045477993924284003153851171132420751750724394405070269223797513951991873714156884423926582172189394011114952
n = 159452716285492879108396025652299064897348745847754101475050126796260046052685162344131542880739092630022413124977374334652652450809186959288635651980201026825896903174847709657312399801033678426271413442323084354665643010763178857967804623680894444913369256168333223214048037661178587978535722147091129404833
leak = 2669103705669857828725305123419482758456336465207378766363532584323475128597302561377245054918781031448710846825859151788151496659511563529987056456136018

p = symbols('p')
q = symbols('q')

eq1 = 2*(p-q+1) - leak
eq2 = p*q - n

solution = solve((eq1,eq2),(p,q))
print(solution)

p = int(solution[1][0])
q = int(solution[1][1])
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

7.leak = d + p + q

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)

e = 0x10001
n = p * q
c = pow(m, e, n)
d=libnum.invmod(e,(p-1)*(q-1))
leak = d+p+q
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')

#e = 65537
#c = 65194823373091792824101730983124740337276083358867621564067880339279446092377567969207237986613196892737474455781661885696122256698478429450971196633786693648866129636737262041654769618993094832127875251068775632567036646408374963058703320605733921797230106462440860984746880466416824674570639694481298708147
#n = 101929257180069933443442160085713121307068880188090652033345240568607589666231813199686824369361640378636124324844158355533056421197926269617986872835671463371353540696806173813019752742218460997272803573114119876536384486655117245296360474103378827486280279523273344156760793016731778663058274770626116861407
#leak = 87007773233816810147344015772388866522443114032719766646343787373996588014373656496789294836431302130125588646180886383013958151442324020038131736683796464202667423644714259545194662934238144990354387370533656134036753530002005551694211595695927699196016268145816389892292091218491443784193805171731592693841

$$
leak = d + p + q
$$

$$
\therefore d = leak - (p + q)
$$

则
$$
m \equiv c^d \equiv c^{leak -(p+q)} \mod n
$$
因为$\phi(n) = n - (p+q) + 1$
$$
\therefore m \equiv c^{leak - (n + 1)} \mod n
$$

exp.py

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

c = 65194823373091792824101730983124740337276083358867621564067880339279446092377567969207237986613196892737474455781661885696122256698478429450971196633786693648866129636737262041654769618993094832127875251068775632567036646408374963058703320605733921797230106462440860984746880466416824674570639694481298708147
n = 101929257180069933443442160085713121307068880188090652033345240568607589666231813199686824369361640378636124324844158355533056421197926269617986872835671463371353540696806173813019752742218460997272803573114119876536384486655117245296360474103378827486280279523273344156760793016731778663058274770626116861407
leak = 87007773233816810147344015772388866522443114032719766646343787373996588014373656496789294836431302130125588646180886383013958151442324020038131736683796464202667423644714259545194662934238144990354387370533656134036753530002005551694211595695927699196016268145816389892292091218491443784193805171731592693841

m = pow(c,leak - n - 1,n)
print(long_to_bytes(m))

8.leak = pow(p,q,n) + pow(q,p,n) % n

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)

e = 0x10001
n = p * q
c = pow(m, e, n)
leak = (pow(p, q, n) + pow(q, p, n)) % n
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')

$$
leak \equiv (p^q \mod n + q^p \mod n) \mod n
$$

由费马小定理得
$$
leak \equiv (p^q \mod q + q^p \mod p) \mod n
$$
即
$$
leak \equiv p + q \mod n
$$

$$
\because p + q < n
$$

$$
\therefore leak = p + q
$$

然后
$$
(p-q)^2 = (p+q)^2 - 4n = leak^2 - 4n
$$

$$
\therefore p = \frac{((p+q) + (p-q))}{2}
$$

或者解方程

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2

e = 65537
c = 59662555342583061013008608133060203475725526601468647442902301335538953096485921516133656618941085620436784211565880744663573927593670579237831797055934897166262528476227281479029026508166848256301828084036716500159067642101104810756620735383857351274773983199968924981397675373272878756685629789497697821620
n = 83332115751539889489689110273690067288993797655970253065863170986174973047785854940017477990345318506407680986257706329521142524295434171889087917406552261883625775754882538291980506944585738241124811588555071095223782766762626040473256423491630224616140407276984106458673447870374272906086783555489477673207
leak = 18881487897809480964326513919135880296801378921812225600834164247018332292886076618571738627353925482046410714540439662613766662197119044934743578662330528

p_q = gmpy2.iroot(leak ** 2 - 4 * n,2)[0]
p = (leak + p_q) // 2
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

2023数据安全产业人才能力挑战赛——math_exam

task.py

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
import os
from Crypto.Util.number import *
from secret import flag

bits = 512

def pad(msg, length):
    pad_length = length - len(msg) - 1
    pad_data = os.urandom(pad_length)
    return msg + b'\x00' + pad_data

def unpad(msg):
    return msg.split(b"\x00")[0]

def challenge1(m):
    p, q = [getPrime(bits) for i in range(2)]
    if p <= q:
        p, q = q, p
    e = 0x10001
    n = p * q
    c = pow(m, e, n)
    leak = (n + p) % (q-1)
    print('-------- challenge 1 --------')
    print(f'{e = }')
    print(f'{c = }')
    print(f'{n = }')
    print(f'{leak = }')

def challenge2(m):
    p, q = [getPrime(bits) for i in range(2)]
    e = 0x10001
    n = p * q
    d = inverse(e, (p-1)*(q-1))
    c = pow(m, e, n)
    leak = d + p + q
    print('-------- challenge 2 --------')
    print(f'{e = }')
    print(f'{c = }')
    print(f'{n = }')
    print(f'{leak = }')

def challenge3(m):
    p, q = [getPrime(bits) for i in range(2)]
    e = 0x10001
    n = p * q
    c = pow(m, e, n)
    leak = (pow(p, q, n) + pow(q, p, n)) % n
    print('-------- challenge 3 --------')
    print(f'{e = }')
    print(f'{c = }')
    print(f'{n = }')
    print(f'{leak = }')

assert len(flag) == 42
ms = []
for i in range(0, 42, 14):
    ms.append(bytes_to_long(pad(flag[i:i+14], bits//4-1)))

m1, m2, m3 = ms
challenge1(m1)
challenge2(m2)
challenge3(m3)

"""
-------- challenge 1 --------
e = 65537
c = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278
-------- challenge 2 --------
e = 65537
c = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003
-------- challenge 3 --------
e = 65537
c = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848
"""

exp.py

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
from sympy import symbols,solve
from Crypto.Util.number import *
import gmpy2

e = 65537
c1 = 
n1 = 
leak1 = 

p1 = symbols('p1')
q1 = symbols('q1')

eq1 = 2*(p1-q1+1)-leak1
eq2 = p1 * q1- n1

solution1 = solve((eq1,eq2),(p1,q1))

p1,q1 = int(solution1[1][0]),int(solution1[1][1])
d1 = gmpy2.invert(e,(p1-1)*(q1-1))
m1 = pow(c1,d1,n1)
flag1 = long_to_bytes(m1)[:14]

c2 = 
n2 = 
leak2 = 

tmp = leak2 - n2 -1
m2 = pow(c2,tmp,n2)
flag2 = long_to_bytes(m2)[:14]

c3 = 
n3 = 
leak3 = 

p3 = symbols('p3')
q3 = symbols('q3')

eq3 = p3 + q3 - leak3
eq4 = p3 * q3 - n3

solution3 = solve((eq3,eq4),(p3,q3))

p3,q3 = int(solution3[0][0]),int(solution3[0][1])
d3 = gmpy2.invert(e,(p3-1)*(q3-1))
m3 = pow(c3,d3,n3)
flag3 = long_to_bytes(m3)[:14]

flag = flag1 + flag2 + flag3
print(flag)

二十、剪枝相关

1.gift = p ^ q

题目来源：2023陕西省技能大赛——奇怪得asr

task.py

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

key = 'flag{**********}'

bits = 1024
msg = bytes_to_long(key.encode())

e = 65537
p = getPrime(bits)
q = getPrime(bits)
n = p * q

def encrypt1(msg, e, n):
    c = pow(msg, e, n)
    return c

seed = p ^ q
a = getPrime(bits)
b = getPrime(bits)
n1 = getPrime(bits)

def encrypt2(seed):
    enc = []
    for i in range(10):
        seed = (a * seed + b) % n1
        enc.append(seed)
    return enc
    
c = encrypt1(msg, e, n)
enc = encrypt2(seed)
print("n = ", n)
print("c = ", c)
print("n1 = ", n1)
print("enc = ", enc)

n =  24044063028844014127418595700558729326190738802687551098858513077613750188240082663594575453404975706225242363463089392757425008423696150244560748490108425645064339883915929498539109384801415313004805586193044292137299902797522618277016789979196782551492020031695781792205215671106103568559626617762521687128199445018651010056934305055040748892733145467040663073395258760159451903432330506383025685265502086582538667772105057401245864822281535425692919273252955571196166824113519446568745718898654447958192533288063735350717599092500158028352667339959012630051251024677881674246253876293205648190626145653304572328397
c =  14883053247652228283811442762780942186987432684268901119544211089991663825267989728286381980568977804079766160707988623895155236079459150322336701772385709429870215701045797411519212730389048862111088898917402253368572002593328131895422933030329446097639972123501482601377059155708292321789694103528266681104521268192526745361895856566384239849048923482217529011549596939269967690907738755747213669693953769070736092857407573675987242774763239531688324956444305397953424851627349331117467417542814921554060612622936755420459029769026126293588814831034143264949347763031994934813475762839410192390466491651507733968227
n1 =  137670797028117726329534659376416493367957852768263083700434198723955223922183386928456013703791817601151754417828367188186912209697081337658512940425529211281290630976671911327606706953154608427885071841566358882014021242768190762103365969320014710368160869517966437591299370072284930202718943785099916898209
enc =  [101737402423360536260958229788866250367716256968287178187558336481872788309727545478736771692477306412259739856568227009850831432381180909815512654609798228982433082928392936844193974517574281026029228179913579225687286945054175762659252515268270399329404664775893089132101252158524000295899895962104782878103, 37355684997487259669354747104430314505839306993101096210478266975184357608742619438151118843905165289324251734149329596611854110739738607745107961453008343886403511257039401245484528985856920723694142989180291902939107642020398816995584650913417698279936585230648639613028793148102494100898288564799111024672, 58677759595639211550435023449462812079890625834313820227189340593596480924226619376872336960357021314847975570175387751632125898437020801920862764666175594874885587518469384576361008639967382152477408865298759987606155830674598034578657554841283906976808719095766296677147076808250022898199866472085742989883, 61841632061818470036288407041172200048676249787061823756736224887116113640875444187463656719652972233582538657844183320242896612625995507633237074900538692102956750184024574603018257213912795847625926653585010890014291951218199774765624860625726555381815237888483974246173727262881650634287497285246796321130, 7618244158597756867387754433401378508070531356170836765779245254233413235386172690733378371343899289510629513166609513857423499004879497768588665836034791151090648182168421570449377835494883902907064269417199065924565304966242954268460876762295575715334403142360198583318323418975108290758222653083011275844, 106276841058222138994123556391380518368163552919305398852484130331884811278068151915582752795463570013359693610495645946230044828403849434903415989487924763756589202218361370725532394478569304449884620166937809374355282324069422109879874964479199929174533104879048175102339134830614476339153367475243140156049, 54574757236475194407137831004617398270525645136836468973535243574661043352422598443323384197261529289829451787586618886007968913414366545291507686451774653217577858375086817168124727394445167274831801876424578654786480330913650363551771258617533162477541882336257099777912519011890593910515860435759936717781, 15567087904962670212229825713697043597876172881256160613623383896576159414077875401117959132252949501643234465895697270909085179587988268864498823765197994781747034644583869111599516151129007414228897958635533561248099927507725880289417298814703767549313482346652043188826434944367260731729064673486516315207, 10757138067445225320504771816863593606847219020279502671965413470243269270456133564739090471033889069283122519782525412134604896073598293410977787230108853737796640474070194546344190858079847734817109910030714675258996740807873872365037296486121580542250452443305370358407408558223735250474249180772656905880, 68097848963949068260912124852455363245291187860801223898468533992003737157497436432969031551088942445561676359631354280979357356539429863946694570097104716411407829017684705171462511875250672979623888463245258237680782731827727876526411531354910982579164963119481534453651300645314177478026462894232377307020]

先通过LCG求出seed，然后剪枝得到p,q。LCG就不过多赘述了

exp.py

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
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(3000)

gift = 39428646082513135314545544161912595458975375891528176714825766497155482031976852156313956476772023258684487799640179241987139554034654104867011313090105438798561154654679825702410748780286094326639330840289843154525176685892323447168072417654823748596238888125898914210332775882916911771786984574407163323116
N = 24044063028844014127418595700558729326190738802687551098858513077613750188240082663594575453404975706225242363463089392757425008423696150244560748490108425645064339883915929498539109384801415313004805586193044292137299902797522618277016789979196782551492020031695781792205215671106103568559626617762521687128199445018651010056934305055040748892733145467040663073395258760159451903432330506383025685265502086582538667772105057401245864822281535425692919273252955571196166824113519446568745718898654447958192533288063735350717599092500158028352667339959012630051251024677881674246253876293205648190626145653304572328397
c = 14883053247652228283811442762780942186987432684268901119544211089991663825267989728286381980568977804079766160707988623895155236079459150322336701772385709429870215701045797411519212730389048862111088898917402253368572002593328131895422933030329446097639972123501482601377059155708292321789694103528266681104521268192526745361895856566384239849048923482217529011549596939269967690907738755747213669693953769070736092857407573675987242774763239531688324956444305397953424851627349331117467417542814921554060612622936755420459029769026126293588814831034143264949347763031994934813475762839410192390466491651507733968227

# 低位往高位爆
def findp(p,q):
    if len(p) == 1024:
        pp = int(p,2)
        if N % pp == 0:
            print("p = ",pp)
            print("q = ",N // pp)
            qq = N // pp
            d = inverse(65537,(pp-1)*(qq-1))
            m = pow(c,d,N)
            print(long_to_bytes(m))
            return
    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp ^ qq) % (2 ** l) == gift % (2 ** l) and pp * qq % (2 ** l) == N % (2**l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)

findp('1','1')
# flag{y0u_kn0w_Pruning_and_lcg}

2.gift = p ^ （q >> 16）

题目来源：2023DASCTF暑期挑战赛——EzRSA

task.py

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 *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)

print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
pow(n,e,N) = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
pow(secret,e,n) = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
pow(flag,e,n) = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

思路很清晰，先分解N，解RSA得到n，再富兰克林相关消息攻击求解flag。

这里只展示剪枝分解N

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
from tqdm import *

sys.setrecursionlimit(3000)
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377

# 低位往高位爆
def findp(p,q):
    if len(p) == 512:
        pp = int(p,2)
        if N % pp == 0:
            print("p = ",pp)
            print("q = ",N // pp)
            
    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp ^ (qq >> 16)) % (2 ** l) == gift % (2 ** l) and pp * qq % (2 ** l) == N % (2 ** l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)
            
for i in trange(2**16,2**17):
    findp('1',bin(i)[2:])
"""
p =  8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
q =  9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297
"""

3.不会取名字

题目来源:2024HDCTF——ezrsa

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import random
import hashlib
from secret import flag


gen1 = lambda bits=1024, rand=lambda n: bytes(random.getrandbits(1) for _ in range(n)): (getPrime(bits//2, randfunc=rand), getPrime(bits//2, randfunc=rand))

gen2 = lambda alpha=512, K=500, T=getPrime(506): next(((p, q, T) for q, r in [(getPrime(alpha), getPrime(alpha))] for k in range(2, K+1) if (isPrime(p := r + (k * q - r) % T))), None)

p1,q1=gen1()
p2, q2, T = gen2()
assert flag == "DASCTF{" + hashlib.md5(str(p1 + p2 + q1 + q2).encode()).hexdigest() + "}"
print(p1*q1)
print((p2*q2,T))
# 44945076854246685060397710825960160082061127479194994041436997195972585701097443198954359213635892234058786065342178389181538153413878118039445271277476379366294977408981257175008890470376094381644530106799352839565803317977637572325347776636285703517680754624094985374606187797141657688145287340444623176193
# (57784854392324291351358704449756491526369373648574288191576366413179694041729248864428194536249209588548791706980878177790271653262097539281383559433402738548851606776347237650302071287124974607439996041713554182180186588308614458904981542909792071322939678815174962366963098166320441995961513884899917498099, 150514823288951667574011681197229106951781617714873679347685702558528178681176081082658953342482323349796111911103531429615442550000291753989779754337491)

这里仅对gen1()这部分讲解

gen1()，关键就是把getPrime(bits,randfunc=None)改成了getPrime(bits,randfunc=rand)

我不太清楚randfunc起到什么作用，自己打印几组数据发现，gen1生成的素数每8bit只有2个情况，分别是

00000000 00000001

而高8位必定是10000000

通过这个性质，再利用p * q % 2**l == n % 2**l，写一个剪枝就可以爆出来

exp.py

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

n1 = 44945076854246685060397710825960160082061127479194994041436997195972585701097443198954359213635892234058786065342178389181538153413878118039445271277476379366294977408981257175008890470376094381644530106799352839565803317977637572325347776636285703517680754624094985374606187797141657688145287340444623176193

def find(p,q,l):
    if l == 504:
        pp = int("10000000"+ p,2)
        qq = int("10000000"+ q,2)
        if n1 % pp == 0:
            print(f"p1 = {pp}")
            print(f"q1 = {qq}")
            return 
    else:
        pp = int(p,2)
        qq = int(q,2)
        if pp * qq % 2**l == n1 % 2**l:
            find("00000001" + p,"00000001" + q,l+8)
            find("00000001" + p,"00000000" + q,l+8)
            find("00000000" + p,"00000001" + q,l+8)
            find("00000000" + p,"00000000" + q,l+8)

find("00000001","00000001",8)

4.不会取名字

题目来源:2024osuCTF

task.py

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
from Crypto.Util.number import isPrime,bytes_to_long
import random
import os

def getWYSIprime():
    while True:
        digits = [random.choice("727") for _ in range(272)]
        prime = int("".join(digits))
        if isPrime(prime):
            return prime
        
# RSA encryption using the WYSI primes
p = getWYSIprime()
q = getWYSIprime()
n = p * q
e = 65537
flag = bytes_to_long(os.getenv("FLAG",b"osu{fake_flag_for_testing}"))
ciphertext = pow(flag,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ciphertext = {ciphertext}")
"""
n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450
"""

素数由7 or 2组成，所以剪枝就好了，和二进制的01没什么区别

exp.py

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
from Crypto.Util.number import *
import itertools
import gmpy2

n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450

def findp(p,q):
    l = len(p)
    if l == 272 and n % int(p) == 0:
        q = n // int(p)
        print(f"p = {p}")
        print(f"q = {q}")
    else:
        table = ["2","7"]
        for i,j in itertools.product(table,repeat=2):
            pp = int(i + p)
            qq = int(j + q)
            if pp * qq % 10**l == n % 10**l:
                findp(i+p,j+q)
                
# findp("7","7")
p = 27777727727777722777277277777272772727772722777777277777277772227772772772227272727777772772772727227772777277727777777222777777277727772272272777772722727722777727277727727777777772772777772777277772222727227777777222727777772772272727777222777777277777727272772272272277
q = 77777772777772222722727222227777272777772777772277727772722777777777227277727272772727277277272772727227272772772222277777772727727772722772777272727777272722772777277777277777277777727777277277777277777272772772777777727772727277727777772772777772272772272222227777777227
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(ciphertext,d,n)
print(long_to_bytes(m))
# osu{h4v3_y0u_3v3r_n0t1c3d_th4t_727_1s_pr1m3?}

这四种其实感觉都算是一个类型的。还有很多类型的剪枝可以参考:Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

5.剪枝高位泄露

改编自2024XYCTF——铜匠——part3

task.py

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 *
from uuid import uuid4

flag = "flag{" + str(uuid4()) + "}"
m = bytes_to_long(flag.encode())

e = 65537
p = getPrime(512)
q = getPrime(512)
n = p * q
n = p * q
c = pow(m,e,n)
hint = (p ^ q) >> 200

print(f"c = {c}")
print(f"hint = {hint}")
print(f"n = {n}")
"""
c = 131369115652458166734046676308463999858958566061027321031978783010359641091133329180071403453658128376834077573719048417128188606423319316139110362434662107918020440100011984923813248515798307240829242781364796147914413916010985480344221078382648887106771447184119879293816004142774768308105423590006218154095
hint = 1418156189500701046118843280016917462701888775284481310064968961841401532967678842766145628051
n = 149674440332297459310104619359509309480607215578927485825557593606756533602713173946403283163260154493438427348209708307170391308942988466700336664636266655214819841710712761463985437035510015805275916279554381867547108324810390610671268389247357987728963839572199589558858271355105026004101888297456720686127
"""

原理参考:2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from Crypto.Util.number import *

c = 77362292774939745985127248740136531356798680244461718641182309736632869439528624490319564705732587035892746550259989967311639940839352531540590481816143399815777578738222244349541298856970218973629828183402846736572747940317185733010901816452760815595925525717774150109667814870300394441913855689875810419726
hint = 3952699881526141586582096584337236735424573202916336803978009509888494841237961467284222140708
n = 101811981048263163700430054305833461232304464649339483324456752139265661172425623344370861924802283149319747333342558424458871624320190755682987168048547266046556603061770039238687342160962557147928318419071351955573359146111983095312306624896541836196196950684743489047140141567937687816622755267268993977151
e = 65537

leak = hint << 200
leak = bin(leak)[2:].zfill(512)
leakbits = 200                          # 缺失的位数

def findp(pp,qq,l):
    p_Min = int(pp + (512-l)*"0",2)
    p_Max = int(pp + (512-l)*"1",2)
    q_Min = int(qq + (512-l)*"0",2)
    q_Max = int(qq + (512-l)*"1",2)

    if(l == 512 - leakbits):
        R.<x> = PolynomialRing(Zmod(n))
        phigh = p_Min
        f = phigh + x
        root = f.small_roots(X=2^leakbits, beta=0.499)
        if root != []:
            p = phigh + int(root[0])
            q = n // p
            d = inverse(e,(p-1)*(q-1))
            m = pow(c,d,n)
            print(long_to_bytes(m))
    
    if (p_Max * q_Max < n) or (p_Min * q_Min > n):
        return
    
    # 以下是根据异或来操作的
    if leak[l] == '0':
        findp(pp + '1',qq + '1',l+1)
        findp(pp + '0',qq + '0',l+1)
    if leak[l] == '1':
        findp(pp + '1',qq + '0',l+1)
        findp(pp + '0',qq + '1',l+1)

findp('1','1',1)

二十一、一些分解n常用的方法

1.费马分解

$$
n = p\times q = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2
$$

简单来说，费马分解干了这样一件事:

从$a = \sqrt{n}$开始，逐步增加，直到发现$a^2 - n$是一个平方数，就找到了正确的$a,b$，然后就可以计算$p = a +b ,q = a -b$

从这个思想可以发现，这个算法的效率取决于$\frac{p+q}{2}$和$\sqrt{n}$的差距，所以当$p,q$接近的时候，用费马分解可以很快计算出$p,q$

这里给出一个脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from math import isqrt

def fermat(n):
    a = isqrt(n)
    b2 = a * a - n
    b = isqrt(n)
    count = 0
    while b * b != b2:
        a = a + 1
        b2 = a * a - n
        b = isqrt(b2)
        count += 1
    p = a + b
    q = a - b
    assert n == p * q
    return p, q

例题——MoeCTF2023 |p-q|

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
with open("flag.txt","rb") as fs:
    flag = fs.read().strip()
assert len(flag) == 72

m = int.from_bytes(flag,"big")

from Crypto.Util.number import getPrime, isPrime

def next_prime(p):
    while True:
        p += 2
        if isPrime(p):
            return p

p = getPrime(2048)
q = next_prime(p)
n = p * q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("c =",c)

# n = 329960318345010350458589325571454799968957932130539403944044204698872359769449414256378111233592533561892402020955736786563103586897940757198920737583107357264433730515123570697570757034221232010688796344257587359198400915567115397034901247038275403825404094129637119512164953012131445747740645183682571690806238508035172474685818036517880994658466362305677430221344381425792427288500814551334928982040579744048907401043058567486871621293983772331951723963911377839286050368715384227640638031857101612517441295926821712605955984000617738833973829140899288164786111118033301974794123637285172303688427806450817155786233788027512244397952849209700013205803489334055814513866650854230478124920442832221946442593769555237909177172933634236392800414176981780444770542047378630756636857018730168151824307814244094763132088236333995807013617801783919113541391133267230410179444855465611792191833319172887852945902960736744468250550722314565805440432977225703650102517531531476188269635151281661081058374242768608270563131619806585194608795817118466680430500830137335634289617464844004904410907221482919453859885955054140320857757297655475489972268282336250384384926216818756762307686391740965586168590784252524275489515352125321398406426217
# c = 307746143297103281117512771170735061509547958991947416701685589829711285274762039205145422734327595082350457374530975854337055433998982493020603245187129916580627539476324521854057990929173492940833073106540441902619425074887573232779899379436737429823569006431370954961865581168635086246592539153824456681688944066925973182272443586463636373955966146029489121226571408532284480270826510961605206483011204059402338926815599691009406841471142048842308786000059979977645988396524814553253493672729395573658564825709547262230219183672493306100392069182994445509803952976016630731417479238769736432223194249245020320183199001774879893442186017555682902409661647546547835345461056900610391514595370600575845979413984555709077635397717741521573798309855584473259503981955303774208127361309229536010653615696850725905168242705387575720694946072789441481191449772933265705810128547553027708513478130258801233619669699177901566688737559102165508239876805822898509541232565766265491283807922473440397456701500524925191214292669986798631732639221198138026031561329502985577205314190565609214349344303324429408234237832110076900414483795318189628198913032900272406887003325858236057373096880675754802725017537119549989304878960436575670784578550

这里p,q是相邻的素数，可以直接开根号分解，也可以用费马分解

exp.py

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 math import isqrt
from Crypto.Util.number import *

def fermat(n):
    a = isqrt(n)
    b2 = a * a - n
    b = isqrt(n)
    count = 0
    while b * b != b2:
        a = a + 1
        b2 = a * a - n
        b = isqrt(b2)
        count += 1
    p = a + b
    q = a - b
    assert n == p * q
    return p, q

n = 
c = 
p,q = fermat(n)
d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

2.p-1光滑

原理没了解，就存个脚本吧

脚本来源:RSA攻击：Smooth攻击_p-1光滑攻击-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2

def Pollards_p_1(N):
    a = 2	# 为了快速计算以及满足费马小定理条件
    n = 2	# 从1开始没必要
    
    while True:
        a = pow(a, n, N)	# 递推计算a^B!
        res = gmpy2.gcd(a - 1, N)	# 尝试计算p
        if res != 1 and res != N:	# 满足条件后返回
            return res
        n += 1

例题——NCTF2019 childRSA

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

exp.py

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

def Pollards_p_1(N):
    a = 2	# 为了快速计算以及满足费马小定理条件
    n = 2	# 从1开始没必要
    
    while True:
        a = pow(a, n, N)	# 递推计算a^B!
        res = gmpy2.gcd(a - 1, N)	# 尝试计算p
        if res != 1 and res != N:	# 满足条件后返回
            return res
        n += 1
        
n = 
c = 
p = Pollards_p_1(n)
q = n // p
d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}

3.p+1光滑

脚本来源:

1
2
3
4
5
6
7
8
9
10
11
def lucas(c, d, N):
	x = c # a1
	y = (c**2 - 2) % N # a2
	for bit in bin(d)[3:]: # 快速乘(从高到低位)--我个人理解
		if bit == '1':
			x = (x*y - c) % N # 下标对应a_{x+y}，其次保证a_{2k-1}=a_{k}a_{k-1}-a_{0}成立
			y = (y**2 - 2) % N # 使得y翻倍--正常的快速幂流程
		else:
			y = (x*y - c) % N # 保证a_{2k-1}=a_{k}a_{k-1}-a_{0}成立
			x = (x**2 - 2) % N # a_{k} 翻倍
	return x #返回a_{ed}

才疏学浅，没找到例题

4.已知phi和n分解n

如果是两个因子的,$n = p\times q$，那么直接联立方程就可以解

如果是多因子的话，就没这么容易了，以NKCTF2023的ezRSA为例

例题——NKCTF2023 ezRSA

task.py

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
from Crypto.Util.number import *
from secret import flag

m1 = bytes_to_long(flag[:len(flag)//3])
m2 = bytes_to_long(flag[len(flag)//3:])

def gen():
    prime_list  = []
    for i in range(4):
        prime_list.append(getPrime(512))
    return sorted(prime_list)

prime_list = gen()
p,q,r,t = prime_list[0],prime_list[3],prime_list[1],prime_list[2]
e = 65537
n = p*q*r*t
phi = (p-1)*(q-1)*(r-1)*(t-1)
c1 = pow(m1,e,p*q)
p1 = getPrime(512)
q1 = getPrime(512)
N = p1*q1
c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)
print(f'n = {n}')
print(f'phi = {phi}')
print(f'c1 = {c1}')
print(f'N = {N}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

'''
n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409
N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078
'''

exp.py

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
from math import gcd
from math import isqrt
from random import randrange
from gmpy2 import is_prime


def factorize(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method only works for a modulus consisting of 2 primes!
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors, or None if the factors were not found
    """
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)
    
n = 
phi = 
prime_list = sorted(factorize_multi_prime(n,phi))
p,q,r,s = prime_list[0],prime_list[3],prime_list[1],prime_list[2]

5.已知e,d分解n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random
import gmpy2

def divide_pq(e, d, n):
    k = e*d - 1
    while True:
        g = random.randint(2, n-1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gmpy2.gcd(x-1, n) > 1:
                p = gmpy2.gcd(x-1, n)
                return (p, n//p)

二十二、不知道叫什么分类的题目

给出p + q低位

题目改编自2024XYCTF——铜匠——part2

task.py

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

flag = "flag{" + str(uuid4()) + "}"
m = bytes_to_long(flag.encode())

e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q

c = pow(m, e, n)
hint = (p + q) & ((1 << 624) - 1)
print(f"c = {c}")
print(f"hint = {hint}")
print(f"n = {n}")
"""
c = 15315623227108436291858457034857784719507552879018189851637500530704870673436079954784519165863568569923075589417879105802430194799540543536178163710092884414704414320471378011034947694757321045648672645088739109820484000260862752393231610482665197130322211444656668269314857325584729333799747940039582233403795688967132390847508527859286606080564369696319857802230684766189133382904414261588681956483620140766886760632093938290509495921191051004955960321224324525865371027175220422824090922909186107029324403060456677201122370380708945945621513853659281202197178155661602947407740113932985040400431009519035927170893
hint = 24765551240982534917083490896297931130347202481167225145278716583234238038819431100154290815134734511033735464993876484465992525732351399544319245104113383110187111270727627683278542339074
n = 17551595965847360101001559529386245228497232313421489853434901311116953087050954433040038840788997073271446971526589676430781788129026667353632541062149232552031818920006832783397173014011531311807992794738323157382559849771809561200626834225824761208921248849766951980339089458227127422515917026821919873970760316856393212652571020677585627719682906485373773819364730302897222175047226443095023421963275036185038777190349527562337069435775581997139041749482233185668100893166822768561406331106814954573421744711888039361670837655170604347860448702902142977569791794645486978083071644858164529311966931143494605467581
"""

由题意知$hint \equiv p+q \mod 2^{624}$

除此之外还可以得到$n_{low} \equiv p\times q \mod 2^{624}$

于是有$n_{low} \equiv p(hint - p) \mod 2^{624}$，解这个方程，然后得到p的低位，再用coppersmith

exp.sage

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 *

c = 
hint = 
n = 
e = 65537


n_low = n % 2^624
var('p')
f = p * (hint - p) - n_low
res = solve_mod(f,2^624)
for i in res:
    plow = int(i[0])
    R.<x> = PolynomialRing(Zmod(n))
    f2 = x * 2^624 + plow
    f2 = f2.monic()
    root = f2.small_roots(X = 2^400,beta=0.4)
    if root != []:
        p = int(root[0])*2^624 + plow
        q = n // p
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))

给出p + q高位

题目改编自2023贵阳大数据安全精英赛——childrsa

task.py

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

flag = "flag{" + str(uuid4()) + "}"
m = bytes_to_long(flag.encode())

e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m,e,n)
hint = (p + q) >> 400

print(f"c = {c}")
print(f"hint = {hint}")
print(f"n = {n}")
"""
c = 9968814618309288374765866491408679544255429893255485341540355195679112942954793887247314436025657932769746362042585414910893400260770578028623836705800055045072907439444477587736093915786634848757052762926680474130492661750432044025559425178180215747669943104929529122332455902347039817592660193268467698523220383789551009222998925658852390205657636722754375420684776093364112335355059660951403603124371637134722485720098467185512008162108300224681045740170399118079432119176169258163078208915377786922862558709935512780853980376778422910630993460815435812492821018759585591884031366023668940372754253922297009332299
hint = 105339843160443546161059100165057877716740618426298713183228594499797346255161510101279378179555206038228997256205578377516899889823785206924887213498045434452190147663923551839494492842528
n = 18082068933780051996564597024915927694586996785675007728934595064379707482865414885175435323040864143693167921685287351955951750372213399691641808639756160589090710830417826035004009898533761679036070970158874299127191974011618903726273713888134189317545858033157115955525192756551460792306555827664839412205373639439765940037587708927072607585261515428021124875200073775443189376478576573477677951404802079319347815808709279487553524912259078196698834492416001870786404364835221144821510700252279703537618579227763205158431798627532437072037863851605556234186314341793234064284447561153310642226744523000217117902339
"""

我们可以联立$p+q$的高位和$n = p \times q$解方程组，此时解出来的$p$和正确的$p$高位是一样的，最后再用coppersmith去解低400位

实际测试发现，解方程可能存在误差，所以最后用copper处理低405位

Exp

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 *

c = 
hint = 
n = 
e = 65537

R.<x> = PolynomialRing(RealField(2048))

f = x * ((hint << 400) - x) - n
res = f.roots()
for root in res:
    phigh = int(root[0]) >> 405 << 405
    PR.<x> = PolynomialRing(Zmod(n))
    f1 = phigh + x
    res1 = f1.small_roots(X = 2^405,beta=0.4)
    if res1 != []:
        p = phigh + int(res1[0])
        q = n // p
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))

已知p^2 + q^2分解n = p*q

利用sagemath自带函数two_squares()，甚至有three_squares()

二十三、私钥文件提取参数

常考的就是PKCS1形式的私钥文件，参考:参考文章

先生成私钥文件

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

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
d = inverse(e,(p-1)*(q-1))

print(f"n = {n}")
print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"dp = {d % (p-1)}")
print(f"dq = {d % (q-1)}")
print(f"inv = {inverse(p,q)}")

privatekey = RSA.construct((n,e,int(d)))

with open("privatekey.pem","wb") as f2:
    f2.write(privatekey.export_key())

得到

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
-----BEGIN RSA PRIVATE KEY-----
MIIEogIBAAKCAQEAhgPB1hHIr7An3HDG1dqJo8UQu+5oOLOA119z0rZESozrr1ox
3g0Ku86t1X1OpbawWr8cFzXgYsDtgZPWhEExbsU/qHGZXewo8ofe/4Sa/s1DOpUm
ZIFsM/YAtWEex+aTwA9FT+6EZ3OYJatmY9iq9ewnAjeCdBwll04C8vT9Ke73Xndn
B8tTtL2S4hIcuz7vVd1HTZSfQ+ousLUM5OuTe0361NFqp4RFhhHjtM9cuvyaPaMF
vRFoemXyCH8pfxgl4llFSBJitPAeLBxHpV9PjlLBp4kYIzPrYDMp1AF2seQyvb8W
NujFcu0ZvOZRuHxULiUT2RI2srZ6eyAoq7RXiwIDAQABAoIBAE/yw9tqZpfw9ga7
PNNteTk7Ih2LP5+77nwN1LH6zEjRQvUsUJ2QmDusM+YtyBJyJ0krw51RJdikEcyA
nrPtlIjpoW1iv8TZUyBE0FMND848NAQp4GqLDzr8YjXSh6NnufMU6RujRlfVDQpD
82RTaMInLKpU5T1RYVefUYERiEpQCJjzDd2fb1UlCJx6XZguTXTsqCmhr7Lr6xN1
WvSdTY2a7cPxnusggrCaiYxoCjJQRPl+Z4O33gHkXNbZnch5YlEQui1+fanofKuk
lK3mAbqBwo/lfXXAu5GbhMdIZ6Iw68vAiFJQtuwvOYE1h6sN3EHsjnfkbfgC+uu4
1QQfAvECgYEAyBFidz8w3ijHW+XDcH20JhHxEMAmFTUf0fXI11x3ECk+6c2yAH1v
DHM4rr3KHspVhEJzyNVsVBg1I4JF5gSkPWsygjdoyMPqjQ9M0YP2Qho6iiiz20c3
w+K9cBezTNtDn+N/gqOrJLBGOpru1zwpfroS4ie76QNpAUZ83OQUVrkCgYEAq3sG
B0rZvn3+LbQ3S/AlydpnZYf6e85FUt3fQukRBI4vLl6SpOMJSZfQQUnM+P09t2z7
rH3w4QLOYbfEndt1I/MMhfWb7a96I/Cfw9mW48RIUrk4MUtV/Pq7bKz0vzq/DBnA
44nAsa46bb9ysjJ6+fcnLWNLWz4O9+vBeFaGPmMCgYB+vnSwsrmUpCTX1REhPKFZ
1NfxEqmNmeAUtS6NMKjE9jxDBeqUYOJu8regC9/17ZyLc0XCn2JHTCat3iPF+n7J
4hVXZR7ewS7gOiciPAVQDymyyOJYMh/j2srELl+KewW2TvtCmckcLwfurKROenCX
Ne4sk5t5nI1zH2KO1XcFEQKBgH9DeD/lPyBu5TsKKpfDDGh4HJBvkGhdt3k+jLld
u3GEDGP/cBnLHVNuxfIOUX7ggvMkgMuNVD3KFVzUQ6lb+93IPZ0VoLmPp7gQlqGF
VMSJIZuzNo7u+Ewd0QdgfOuHL85NNqgnzciQI3DbysWRTU9CK+M1c/GtZvJ8F0O2
Az89AoGAILpBAbTHYaBpdXrN4axCm9wbJzEJlk0Pv9BvNXly5LiU/xJsgppP/gmP
9NmUN8QKmp3dmxM9Ub36DYGpZRyPKbKfjKQfSraLXwokr7aIm4jc7Ow0NBBgTsfS
EaqTgYiY9axcqaYS9I5iyfQZt9Kl/hJX6aT9s2M+DQfchzaFWkQ=
-----END RSA PRIVATE KEY-----

解base64再转16进制得到下面的内容

1
30 82 04 a2 02 01 00 02 82 01 01 00 86 03 c1 d6 11 c8 af b0 27 dc 70 c6 d5 da 89 a3 c5 10 bb ee 68 38 b3 80 d7 5f 73 d2 b6 44 4a 8c eb af 5a 31 de 0d 0a bb ce ad d5 7d 4e a5 b6 b0 5a bf 1c 17 35 e0 62 c0 ed 81 93 d6 84 41 31 6e c5 3f a8 71 99 5d ec 28 f2 87 de ff 84 9a fe cd 43 3a 95 26 64 81 6c 33 f6 00 b5 61 1e c7 e6 93 c0 0f 45 4f ee 84 67 73 98 25 ab 66 63 d8 aa f5 ec 27 02 37 82 74 1c 25 97 4e 02 f2 f4 fd 29 ee f7 5e 77 67 07 cb 53 b4 bd 92 e2 12 1c bb 3e ef 55 dd 47 4d 94 9f 43 ea 2e b0 b5 0c e4 eb 93 7b 4d fa d4 d1 6a a7 84 45 86 11 e3 b4 cf 5c ba fc 9a 3d a3 05 bd 11 68 7a 65 f2 08 7f 29 7f 18 25 e2 59 45 48 12 62 b4 f0 1e 2c 1c 47 a5 5f 4f 8e 52 c1 a7 89 18 23 33 eb 60 33 29 d4 01 76 b1 e4 32 bd bf 16 36 e8 c5 72 ed 19 bc e6 51 b8 7c 54 2e 25 13 d9 12 36 b2 b6 7a 7b 20 28 ab b4 57 8b 02 03 01 00 01 02 82 01 00 4f f2 c3 db 6a 66 97 f0 f6 06 bb 3c d3 6d 79 39 3b 22 1d 8b 3f 9f bb ee 7c 0d d4 b1 fa cc 48 d1 42 f5 2c 50 9d 90 98 3b ac 33 e6 2d c8 12 72 27 49 2b c3 9d 51 25 d8 a4 11 cc 80 9e b3 ed 94 88 e9 a1 6d 62 bf c4 d9 53 20 44 d0 53 0d 0f ce 3c 34 04 29 e0 6a 8b 0f 3a fc 62 35 d2 87 a3 67 b9 f3 14 e9 1b a3 46 57 d5 0d 0a 43 f3 64 53 68 c2 27 2c aa 54 e5 3d 51 61 57 9f 51 81 11 88 4a 50 08 98 f3 0d dd 9f 6f 55 25 08 9c 7a 5d 98 2e 4d 74 ec a8 29 a1 af b2 eb eb 13 75 5a f4 9d 4d 8d 9a ed c3 f1 9e eb 20 82 b0 9a 89 8c 68 0a 32 50 44 f9 7e 67 83 b7 de 01 e4 5c d6 d9 9d c8 79 62 51 10 ba 2d 7e 7d a9 e8 7c ab a4 94 ad e6 01 ba 81 c2 8f e5 7d 75 c0 bb 91 9b 84 c7 48 67 a2 30 eb cb c0 88 52 50 b6 ec 2f 39 81 35 87 ab 0d dc 41 ec 8e 77 e4 6d f8 02 fa eb b8 d5 04 1f 02 f1 02 81 81 00 c8 11 62 77 3f 30 de 28 c7 5b e5 c3 70 7d b4 26 11 f1 10 c0 26 15 35 1f d1 f5 c8 d7 5c 77 10 29 3e e9 cd b2 00 7d 6f 0c 73 38 ae bd ca 1e ca 55 84 42 73 c8 d5 6c 54 18 35 23 82 45 e6 04 a4 3d 6b 32 82 37 68 c8 c3 ea 8d 0f 4c d1 83 f6 42 1a 3a 8a 28 b3 db 47 37 c3 e2 bd 70 17 b3 4c db 43 9f e3 7f 82 a3 ab 24 b0 46 3a 9a ee d7 3c 29 7e ba 12 e2 27 bb e9 03 69 01 46 7c dc e4 14 56 b9 02 81 81 00 ab 7b 06 07 4a d9 be 7d fe 2d b4 37 4b f0 25 c9 da 67 65 87 fa 7b ce 45 52 dd df 42 e9 11 04 8e 2f 2e 5e 92 a4 e3 09 49 97 d0 41 49 cc f8 fd 3d b7 6c fb ac 7d f0 e1 02 ce 61 b7 c4 9d db 75 23 f3 0c 85 f5 9b ed af 7a 23 f0 9f c3 d9 96 e3 c4 48 52 b9 38 31 4b 55 fc fa bb 6c ac f4 bf 3a bf 0c 19 c0 e3 89 c0 b1 ae 3a 6d bf 72 b2 32 7a f9 f7 27 2d 63 4b 5b 3e 0e f7 eb c1 78 56 86 3e 63 02 81 80 7e be 74 b0 b2 b9 94 a4 24 d7 d5 11 21 3c a1 59 d4 d7 f1 12 a9 8d 99 e0 14 b5 2e 8d 30 a8 c4 f6 3c 43 05 ea 94 60 e2 6e f2 b7 a0 0b df f5 ed 9c 8b 73 45 c2 9f 62 47 4c 26 ad de 23 c5 fa 7e c9 e2 15 57 65 1e de c1 2e e0 3a 27 22 3c 05 50 0f 29 b2 c8 e2 58 32 1f e3 da ca c4 2e 5f 8a 7b 05 b6 4e fb 42 99 c9 1c 2f 07 ee ac a4 4e 7a 70 97 35 ee 2c 93 9b 79 9c 8d 73 1f 62 8e d5 77 05 11 02 81 80 7f 43 78 3f e5 3f 20 6e e5 3b 0a 2a 97 c3 0c 68 78 1c 90 6f 90 68 5d b7 79 3e 8c b9 5d bb 71 84 0c 63 ff 70 19 cb 1d 53 6e c5 f2 0e 51 7e e0 82 f3 24 80 cb 8d 54 3d ca 15 5c d4 43 a9 5b fb dd c8 3d 9d 15 a0 b9 8f a7 b8 10 96 a1 85 54 c4 89 21 9b b3 36 8e ee f8 4c 1d d1 07 60 7c eb 87 2f ce 4d 36 a8 27 cd c8 90 23 70 db ca c5 91 4d 4f 42 2b e3 35 73 f1 ad 66 f2 7c 17 43 b6 03 3f 3d 02 81 80 20 ba 41 01 b4 c7 61 a0 69 75 7a cd e1 ac 42 9b dc 1b 27 31 09 96 4d 0f bf d0 6f 35 79 72 e4 b8 94 ff 12 6c 82 9a 4f fe 09 8f f4 d9 94 37 c4 0a 9a 9d dd 9b 13 3d 51 bd fa 0d 81 a9 65 1c 8f 29 b2 9f 8c a4 1f 4a b6 8b 5f 0a 24 af b6 88 9b 88 dc ec ec 34 34 10 60 4e c7 d2 11 aa 93 81 88 98 f5 ac 5c a9 a6 12 f4 8e 62 c9 f4 19 b7 d2 a5 fe 12 57 e9 a4 fd b3 63 3e 0d 07 dc 87 36 85 5a 44

对其格式化

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
30 82 04 a2 
	02 01 
		00 
	
	02 82 01 01 
		00 86 03 c1 d6 11 c8 af b0 27 dc 70 c6 d5 da 89 a3 c5 10 bb ee 68 38 b3 80 d7 5f 73 d2 b6 44 4a 8c eb af 5a 31 de 0d 0a bb ce ad d5 7d 4e a5 b6 b0 5a bf 1c 17 35 e0 62 c0 ed 81 93 d6 84 41 31 6e c5 3f a8 71 99 5d ec 28 f2 87 de ff 84 9a fe cd 43 3a 95 26 64 81 6c 33 f6 00 b5 61 1e c7 e6 93 c0 0f 45 4f ee 84 67 73 98 25 ab 66 63 d8 aa f5 ec 27 02 37 82 74 1c 25 97 4e 02 f2 f4 fd 29 ee f7 5e 77 67 07 cb 53 b4 bd 92 e2 12 1c bb 3e ef 55 dd 47 4d 94 9f 43 ea 2e b0 b5 0c e4 eb 93 7b 4d fa d4 d1 6a a7 84 45 86 11 e3 b4 cf 5c ba fc 9a 3d a3 05 bd 11 68 7a 65 f2 08 7f 29 7f 18 25 e2 59 45 48 12 62 b4 f0 1e 2c 1c 47 a5 5f 4f 8e 52 c1 a7 89 18 23 33 eb 60 33 29 d4 01 76 b1 e4 32 bd bf 16 36 e8 c5 72 ed 19 bc e6 51 b8 7c 54 2e 25 13 d9 12 36 b2 b6 7a 7b 20 28 ab b4 57 8b 
		
	02 03 
		01 00 01 
		
	02 82 01 00 
		4f f2 c3 db 6a 66 97 f0 f6 06 bb 3c d3 6d 79 39 3b 22 1d 8b 3f 9f bb ee 7c 0d d4 b1 fa cc 48 d1 42 f5 2c 50 9d 90 98 3b ac 33 e6 2d c8 12 72 27 49 2b c3 9d 51 25 d8 a4 11 cc 80 9e b3 ed 94 88 e9 a1 6d 62 bf c4 d9 53 20 44 d0 53 0d 0f ce 3c 34 04 29 e0 6a 8b 0f 3a fc 62 35 d2 87 a3 67 b9 f3 14 e9 1b a3 46 57 d5 0d 0a 43 f3 64 53 68 c2 27 2c aa 54 e5 3d 51 61 57 9f 51 81 11 88 4a 50 08 98 f3 0d dd 9f 6f 55 25 08 9c 7a 5d 98 2e 4d 74 ec a8 29 a1 af b2 eb eb 13 75 5a f4 9d 4d 8d 9a ed c3 f1 9e eb 20 82 b0 9a 89 8c 68 0a 32 50 44 f9 7e 67 83 b7 de 01 e4 5c d6 d9 9d c8 79 62 51 10 ba 2d 7e 7d a9 e8 7c ab a4 94 ad e6 01 ba 81 c2 8f e5 7d 75 c0 bb 91 9b 84 c7 48 67 a2 30 eb cb c0 88 52 50 b6 ec 2f 39 81 35 87 ab 0d dc 41 ec 8e 77 e4 6d f8 02 fa eb b8 d5 04 1f 02 f1 
		
	02 81 81 00 
		c8 11 62 77 3f 30 de 28 c7 5b e5 c3 70 7d b4 26 11 f1 10 c0 26 15 35 1f d1 f5 c8 d7 5c 77 10 29 3e e9 cd b2 00 7d 6f 0c 73 38 ae bd ca 1e ca 55 84 42 73 c8 d5 6c 54 18 35 23 82 45 e6 04 a4 3d 6b 32 82 37 68 c8 c3 ea 8d 0f 4c d1 83 f6 42 1a 3a 8a 28 b3 db 47 37 c3 e2 bd 70 17 b3 4c db 43 9f e3 7f 82 a3 ab 24 b0 46 3a 9a ee d7 3c 29 7e ba 12 e2 27 bb e9 03 69 01 46 7c dc e4 14 56 b9 
		
	02 81 81 00 
		ab 7b 06 07 4a d9 be 7d fe 2d b4 37 4b f0 25 c9 da 67 65 87 fa 7b ce 45 52 dd df 42 e9 11 04 8e 2f 2e 5e 92 a4 e3 09 49 97 d0 41 49 cc f8 fd 3d b7 6c fb ac 7d f0 e1 02 ce 61 b7 c4 9d db 75 23 f3 0c 85 f5 9b ed af 7a 23 f0 9f c3 d9 96 e3 c4 48 52 b9 38 31 4b 55 fc fa bb 6c ac f4 bf 3a bf 0c 19 c0 e3 89 c0 b1 ae 3a 6d bf 72 b2 32 7a f9 f7 27 2d 63 4b 5b 3e 0e f7 eb c1 78 56 86 3e 63 
		
	02 81 80 
		7e be 74 b0 b2 b9 94 a4 24 d7 d5 11 21 3c a1 59 d4 d7 f1 12 a9 8d 99 e0 14 b5 2e 8d 30 a8 c4 f6 3c 43 05 ea 94 60 e2 6e f2 b7 a0 0b df f5 ed 9c 8b 73 45 c2 9f 62 47 4c 26 ad de 23 c5 fa 7e c9 e2 15 57 65 1e de c1 2e e0 3a 27 22 3c 05 50 0f 29 b2 c8 e2 58 32 1f e3 da ca c4 2e 5f 8a 7b 05 b6 4e fb 42 99 c9 1c 2f 07 ee ac a4 4e 7a 70 97 35 ee 2c 93 9b 79 9c 8d 73 1f 62 8e d5 77 05 11 
		
	02 81 80 
		7f 43 78 3f e5 3f 20 6e e5 3b 0a 2a 97 c3 0c 68 78 1c 90 6f 90 68 5d b7 79 3e 8c b9 5d bb 71 84 0c 63 ff 70 19 cb 1d 53 6e c5 f2 0e 51 7e e0 82 f3 24 80 cb 8d 54 3d ca 15 5c d4 43 a9 5b fb dd c8 3d 9d 15 a0 b9 8f a7 b8 10 96 a1 85 54 c4 89 21 9b b3 36 8e ee f8 4c 1d d1 07 60 7c eb 87 2f ce 4d 36 a8 27 cd c8 90 23 70 db ca c5 91 4d 4f 42 2b e3 35 73 f1 ad 66 f2 7c 17 43 b6 03 3f 3d 
		
	02 81 80 
		20 ba 41 01 b4 c7 61 a0 69 75 7a cd e1 ac 42 9b dc 1b 27 31 09 96 4d 0f bf d0 6f 35 79 72 e4 b8 94 ff 12 6c 82 9a 4f fe 09 8f f4 d9 94 37 c4 0a 9a 9d dd 9b 13 3d 51 bd fa 0d 81 a9 65 1c 8f 29 b2 9f 8c a4 1f 4a b6 8b 5f 0a 24 af b6 88 9b 88 dc ec ec 34 34 10 60 4e c7 d2 11 aa 93 81 88 98 f5 ac 5c a9 a6 12 f4 8e 62 c9 f4 19 b7 d2 a5 fe 12 57 e9 a4 fd b3 63 3e 0d 07 dc 87 36 85 5a 44

再通过OpenSSL来查看一下密钥的各参数情况

1
openssl rsa -in 文件名 -text -noout
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
Private-Key: (2048 bit, 2 primes)
modulus:
    00:86:03:c1:d6:11:c8:af:b0:27:dc:70:c6:d5:da:
    89:a3:c5:10:bb:ee:68:38:b3:80:d7:5f:73:d2:b6:
    44:4a:8c:eb:af:5a:31:de:0d:0a:bb:ce:ad:d5:7d:
    4e:a5:b6:b0:5a:bf:1c:17:35:e0:62:c0:ed:81:93:
    d6:84:41:31:6e:c5:3f:a8:71:99:5d:ec:28:f2:87:
    de:ff:84:9a:fe:cd:43:3a:95:26:64:81:6c:33:f6:
    00:b5:61:1e:c7:e6:93:c0:0f:45:4f:ee:84:67:73:
    98:25:ab:66:63:d8:aa:f5:ec:27:02:37:82:74:1c:
    25:97:4e:02:f2:f4:fd:29:ee:f7:5e:77:67:07:cb:
    53:b4:bd:92:e2:12:1c:bb:3e:ef:55:dd:47:4d:94:
    9f:43:ea:2e:b0:b5:0c:e4:eb:93:7b:4d:fa:d4:d1:
    6a:a7:84:45:86:11:e3:b4:cf:5c:ba:fc:9a:3d:a3:
    05:bd:11:68:7a:65:f2:08:7f:29:7f:18:25:e2:59:
    45:48:12:62:b4:f0:1e:2c:1c:47:a5:5f:4f:8e:52:
    c1:a7:89:18:23:33:eb:60:33:29:d4:01:76:b1:e4:
    32:bd:bf:16:36:e8:c5:72:ed:19:bc:e6:51:b8:7c:
    54:2e:25:13:d9:12:36:b2:b6:7a:7b:20:28:ab:b4:
    57:8b
publicExponent: 65537 (0x10001)
privateExponent:
    4f:f2:c3:db:6a:66:97:f0:f6:06:bb:3c:d3:6d:79:
    39:3b:22:1d:8b:3f:9f:bb:ee:7c:0d:d4:b1:fa:cc:
    48:d1:42:f5:2c:50:9d:90:98:3b:ac:33:e6:2d:c8:
    12:72:27:49:2b:c3:9d:51:25:d8:a4:11:cc:80:9e:
    b3:ed:94:88:e9:a1:6d:62:bf:c4:d9:53:20:44:d0:
    53:0d:0f:ce:3c:34:04:29:e0:6a:8b:0f:3a:fc:62:
    35:d2:87:a3:67:b9:f3:14:e9:1b:a3:46:57:d5:0d:
    0a:43:f3:64:53:68:c2:27:2c:aa:54:e5:3d:51:61:
    57:9f:51:81:11:88:4a:50:08:98:f3:0d:dd:9f:6f:
    55:25:08:9c:7a:5d:98:2e:4d:74:ec:a8:29:a1:af:
    b2:eb:eb:13:75:5a:f4:9d:4d:8d:9a:ed:c3:f1:9e:
    eb:20:82:b0:9a:89:8c:68:0a:32:50:44:f9:7e:67:
    83:b7:de:01:e4:5c:d6:d9:9d:c8:79:62:51:10:ba:
    2d:7e:7d:a9:e8:7c:ab:a4:94:ad:e6:01:ba:81:c2:
    8f:e5:7d:75:c0:bb:91:9b:84:c7:48:67:a2:30:eb:
    cb:c0:88:52:50:b6:ec:2f:39:81:35:87:ab:0d:dc:
    41:ec:8e:77:e4:6d:f8:02:fa:eb:b8:d5:04:1f:02:
    f1
prime1:
    00:c8:11:62:77:3f:30:de:28:c7:5b:e5:c3:70:7d:
    b4:26:11:f1:10:c0:26:15:35:1f:d1:f5:c8:d7:5c:
    77:10:29:3e:e9:cd:b2:00:7d:6f:0c:73:38:ae:bd:
    ca:1e:ca:55:84:42:73:c8:d5:6c:54:18:35:23:82:
    45:e6:04:a4:3d:6b:32:82:37:68:c8:c3:ea:8d:0f:
    4c:d1:83:f6:42:1a:3a:8a:28:b3:db:47:37:c3:e2:
    bd:70:17:b3:4c:db:43:9f:e3:7f:82:a3:ab:24:b0:
    46:3a:9a:ee:d7:3c:29:7e:ba:12:e2:27:bb:e9:03:
    69:01:46:7c:dc:e4:14:56:b9
prime2:
    00:ab:7b:06:07:4a:d9:be:7d:fe:2d:b4:37:4b:f0:
    25:c9:da:67:65:87:fa:7b:ce:45:52:dd:df:42:e9:
    11:04:8e:2f:2e:5e:92:a4:e3:09:49:97:d0:41:49:
    cc:f8:fd:3d:b7:6c:fb:ac:7d:f0:e1:02:ce:61:b7:
    c4:9d:db:75:23:f3:0c:85:f5:9b:ed:af:7a:23:f0:
    9f:c3:d9:96:e3:c4:48:52:b9:38:31:4b:55:fc:fa:
    bb:6c:ac:f4:bf:3a:bf:0c:19:c0:e3:89:c0:b1:ae:
    3a:6d:bf:72:b2:32:7a:f9:f7:27:2d:63:4b:5b:3e:
    0e:f7:eb:c1:78:56:86:3e:63
exponent1:
    7e:be:74:b0:b2:b9:94:a4:24:d7:d5:11:21:3c:a1:
    59:d4:d7:f1:12:a9:8d:99:e0:14:b5:2e:8d:30:a8:
    c4:f6:3c:43:05:ea:94:60:e2:6e:f2:b7:a0:0b:df:
    f5:ed:9c:8b:73:45:c2:9f:62:47:4c:26:ad:de:23:
    c5:fa:7e:c9:e2:15:57:65:1e:de:c1:2e:e0:3a:27:
    22:3c:05:50:0f:29:b2:c8:e2:58:32:1f:e3:da:ca:
    c4:2e:5f:8a:7b:05:b6:4e:fb:42:99:c9:1c:2f:07:
    ee:ac:a4:4e:7a:70:97:35:ee:2c:93:9b:79:9c:8d:
    73:1f:62:8e:d5:77:05:11
exponent2:
    7f:43:78:3f:e5:3f:20:6e:e5:3b:0a:2a:97:c3:0c:
    68:78:1c:90:6f:90:68:5d:b7:79:3e:8c:b9:5d:bb:
    71:84:0c:63:ff:70:19:cb:1d:53:6e:c5:f2:0e:51:
    7e:e0:82:f3:24:80:cb:8d:54:3d:ca:15:5c:d4:43:
    a9:5b:fb:dd:c8:3d:9d:15:a0:b9:8f:a7:b8:10:96:
    a1:85:54:c4:89:21:9b:b3:36:8e:ee:f8:4c:1d:d1:
    07:60:7c:eb:87:2f:ce:4d:36:a8:27:cd:c8:90:23:
    70:db:ca:c5:91:4d:4f:42:2b:e3:35:73:f1:ad:66:
    f2:7c:17:43:b6:03:3f:3d
coefficient:
    20:ba:41:01:b4:c7:61:a0:69:75:7a:cd:e1:ac:42:
    9b:dc:1b:27:31:09:96:4d:0f:bf:d0:6f:35:79:72:
    e4:b8:94:ff:12:6c:82:9a:4f:fe:09:8f:f4:d9:94:
    37:c4:0a:9a:9d:dd:9b:13:3d:51:bd:fa:0d:81:a9:
    65:1c:8f:29:b2:9f:8c:a4:1f:4a:b6:8b:5f:0a:24:
    af:b6:88:9b:88:dc:ec:ec:34:34:10:60:4e:c7:d2:
    11:aa:93:81:88:98:f5:ac:5c:a9:a6:12:f4:8e:62:
    c9:f4:19:b7:d2:a5:fe:12:57:e9:a4:fd:b3:63:3e:
    0d:07:dc:87:36:85:5a:44

经过对比可以知道，结构为

1
2
3
4
5
6
7
8
9
10
11
RSAPrivateKey ::= SEQUENCE {
 version Version,
 modulus INTEGER, -- n
 publicExponent INTEGER, -- e
 privateExponent INTEGER, -- d
 prime1 INTEGER, -- p
 prime2 INTEGER, -- q
 exponent1 INTEGER, -- d mod (p-1)
 exponent2 INTEGER, -- d mod (q-1)
 coefficient INTEGER -- (inverse of q) mod p 
}

2048bit的私钥文件和1024bit的私钥文件对比

2048 02820101(n) 0203(e) 028201(d) 028181(p) 028181(q) 028180(d % (p-1)) 028180(d % (q-1)) 028180(invert(q,p))
1024 028181(n) 0203(e) 028180(d) 024100(p) 024100(q) 0240 0240 0240

这个表也没权威性，找参数就找02这样的分隔符就好了。

NSSCTFRound16——break

题目给出如下文件:

pri-break.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
Bc8tSTrvGJm2oYuCzIz+Yg4nwwKBgQDiYUawe5Y+rPbFhVOMVB8ZByfMa4LjeSDd
Z23jEGvylBHSeyvFCQq3ISUE40k1D2XmmeaZML3a1nUn6ORIWGaG2phcwrWLkR6n
ubVmb1QJSzgzmFHGnL56KHByZxD9q6DPB+o6gGWt8/6ddBl2NIZU/1btdPQgojfA
XXJFzR92RQKBgQC7qlB0U7m2U4FdG9eelSd+WSKNUVllZAuHji7jgh7Ox6La9xN5
miGZ1yvP44yX218OJ9Zi08o6vIrM6Eil45KzTtGm4iuIn8CMpox+5eUtoxyvxa9r
s2Wu+IRZN9zCME+p+qI8/TG27dIyDzsdgNqcUo8ESls7uW5/FEA7bYTCiQKBgQC7
1KybeB+kZ0zlfIdi8tVOpeI+uaHDbdh3+/5wHUsD3hmfg7VAag0q/2RA1vkB/oG1
QVLVHl0Yu0I/1/u5jyeakrtClAegAsvlrK+3i321rGS4YpTPb3SX1P/f3GZ7o7Ds
touA+NHk8IL9T7xkmJYw5h/RLG32ucH6aU6MXfLR5QKBgD/skfdFxGWxhHk6U1mS
27IM9jJNg9xLz5nxzkqPPhLn+rdgIIuTuQtv++eEjEP++7ZV10rg5yKVJd/bxy8H
2IN7aQo7kZWulHTQDZMFwgOhn0u6glJi+qC8bWzYDFOQSFrY9XQ3vwKMspqm+697
xM+dMUW0LML6oUE9ZjEiAY/5
-----END PRIVATE KEY-----

cipher.txt

1
6081370370545409218106271903400346695565292992689150366474451604281551878507114813906275593034729563149286993189430514737137534129570304832172520820901940874698337733991868650159489601159238582002010625666203730677577976307606665760650563172302688129824842780090723167480409842707790983962415315804311334507726664838464859751689906850572044873633896253285381878416855505301919877714965930289139921111644393144686543207867970807469735534838601255712764863973853116693691206791007433101433703535127367245739289103650669095061417223994665200039533840922696282929063608853551346533188464573323230476645532002621795338655

cipher中这个值是2046bit，可以推出n是2048bit的

这个私钥文件的内容转成16进制得到

1
2
3
4
5
6
7
8
9
10
11
12
13
	05 cf 2d 49 3a ef 18 99 b6 a1 8b 82 cc 8c fe 62 0e 27 c3 

02 81 81 00 
	e2 61 46 b0 7b 96 3e ac f6 c5 85 53 8c 54 1f 19 07 27 cc 6b 82 e3 79 20 dd 67 6d e3 10 6b f2 94 11 d2 7b 2b c5 09 0a b7 21 25 04 e3 49 35 0f 65 e6 99 e6 99 30 bd da d6 75 27 e8 e4 48 58 66 86 da 98 5c c2 b5 8b 91 1e a7 b9 b5 66 6f 54 09 4b 38 33 98 51 c6 9c be 7a 28 70 72 67 10 fd ab a0 cf 07 ea 3a 80 65 ad f3 fe 9d 74 19 76 34 86 54 ff 56 ed 74 f4 20 a2 37 c0 5d 72 45 cd 1f 76 45 

02 81 81 00 
	bb aa 50 74 53 b9 b6 53 81 5d 1b d7 9e 95 27 7e 59 22 8d 51 59 65 64 0b 87 8e 2e e3 82 1e ce c7 a2 da f7 13 79 9a 21 99 d7 2b cf e3 8c 97 db 5f 0e 27 d6 62 d3 ca 3a bc 8a cc e8 48 a5 e3 92 b3 4e d1 a6 e2 2b 88 9f c0 8c a6 8c 7e e5 e5 2d a3 1c af c5 af 6b b3 65 ae f8 84 59 37 dc c2 30 4f a9 fa a2 3c fd 31 b6 ed d2 32 0f 3b 1d 80 da 9c 52 8f 04 4a 5b 3b b9 6e 7f 14 40 3b 6d 84 c2 89 

02 81 81 00 
	bb d4 ac 9b 78 1f a4 67 4c e5 7c 87 62 f2 d5 4e a5 e2 3e b9 a1 c3 6d d8 77 fb fe 70 1d 4b 03 de 19 9f 83 b5 40 6a 0d 2a ff 64 40 d6 f9 01 fe 81 b5 41 52 d5 1e 5d 18 bb 42 3f d7 fb b9 8f 27 9a 92 bb 42 94 07 a0 02 cb e5 ac af b7 8b 7d b5 ac 64 b8 62 94 cf 6f 74 97 d4 ff df dc 66 7b a3 b0 ec b6 8b 80 f8 d1 e4 f0 82 fd 4f bc 64 98 96 30 e6 1f d1 2c 6d f6 b9 c1 fa 69 4e 8c 5d f2 d1 e5 

02 81 80 
	3f ec 91 f7 45 c4 65 b1 84 79 3a 53 59 92 db b2 0c f6 32 4d 83 dc 4b cf 99 f1 ce 4a 8f 3e 12 e7 fa b7 60 20 8b 93 b9 0b 6f fb e7 84 8c 43 fe fb b6 55 d7 4a e0 e7 22 95 25 df db c7 2f 07 d8 83 7b 69 0a 3b 91 95 ae 94 74 d0 0d 93 05 c2 03 a1 9f 4b ba 82 52 62 fa a0 bc 6d 6c d8 0c 53 90 48 5a d8 f5 74 37 bf 02 8c b2 9a a6 fb af 7b c4 cf 9d 31 45 b4 2c c2 fa a1 41 3d 66 31 22 01 8f f9

我们已知$q,d_p,d_q,q^{-1}$

直接用$m = c^{d_p} \mod p$解即可

exp

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

q = 0xe26146b07b963eacf6c585538c541f190727cc6b82e37920dd676de3106bf29411d27b2bc5090ab7212504e349350f65e699e69930bddad67527e8e448586686da985cc2b58b911ea7b9b5666f54094b38339851c69cbe7a2870726710fdaba0cf07ea3a8065adf3fe9d741976348654ff56ed74f420a237c05d7245cd1f7645
dp = 0xbbaa507453b9b653815d1bd79e95277e59228d515965640b878e2ee3821ecec7a2daf713799a2199d72bcfe38c97db5f0e27d662d3ca3abc8acce848a5e392b34ed1a6e22b889fc08ca68c7ee5e52da31cafc5af6bb365aef8845937dcc2304fa9faa23cfd31b6edd2320f3b1d80da9c528f044a5b3bb96e7f14403b6d84c289
dq = 0xbbd4ac9b781fa4674ce57c8762f2d54ea5e23eb9a1c36dd877fbfe701d4b03de199f83b5406a0d2aff6440d6f901fe81b54152d51e5d18bb423fd7fbb98f279a92bb429407a002cbe5acafb78b7db5ac64b86294cf6f7497d4ffdfdc667ba3b0ecb68b80f8d1e4f082fd4fbc64989630e61fd12c6df6b9c1fa694e8c5df2d1e5
inv = 0x3fec91f745c465b184793a535992dbb20cf6324d83dc4bcf99f1ce4a8f3e12e7fab760208b93b90b6ffbe7848c43fefbb655d74ae0e7229525dfdbc72f07d8837b690a3b9195ae9474d00d9305c203a19f4bba825262faa0bc6d6cd80c5390485ad8f57437bf028cb29aa6fbaf7bc4cf9d3145b42cc2faa1413d663122018ff9
c = 6081370370545409218106271903400346695565292992689150366474451604281551878507114813906275593034729563149286993189430514737137534129570304832172520820901940874698337733991868650159489601159238582002010625666203730677577976307606665760650563172302688129824842780090723167480409842707790983962415315804311334507726664838464859751689906850572044873633896253285381878416855505301919877714965930289139921111644393144686543207867970807469735534838601255712764863973853116693691206791007433101433703535127367245739289103650669095061417223994665200039533840922696282929063608853551346533188464573323230476645532002621795338655

m = pow(c,dq,q)
print(long_to_bytes(m))
# flag{oi!_you_find___what_i_Wa1t_talK_y0n!!!}

2022蓝帽杯——corrupted_key

task.py

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag

key = RSA.generate(1024)
open("flag.enc",'wb').write(PKCS1_OAEP.new(key.publickey()).encrypt(flag))
open('priv.pem','wb').write(key.exportKey('PEM'))

priv.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB








yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
-----END RSA PRIVATE KEY-----

把已有的内容进行解码，可以得到$n,e$，inverse(q,p)，以及$d_q$的低120位

1
2
3
4
5
6
7
8
9
30 82 02 5e 
	02 01 
		00 
	
	02 81 81 00 
		d7 15 25 06 aa 9c ec 05 e5 33 5d 6b 46 f5 49 14 07 c3 19 9f d5 10 91 f1 f6 03 0d 37 62 b9 e0 3f 49 c9 dc dc 07 50 54 e0 cc 14 8b 97 4b 41 85 4b d9 3b 4e e1 6a 2a 87 6e e6 20 05 e8 0e f8 06 b7 aa 3b 64 b1 bf 9b 1f a7 73 e3 53 d0 cd b9 ff 97 83 dd d5 f5 e6 74 99 ad 10 f3 61 e9 38 d0 0b 82 a6 a4 c4 2a 05 35 c5 e7 67 21 79 8e 86 b4 5c d4 b8 d0 3b 0d 7e 75 c2 be 87 66 a1 e8 43 bd c6 41 
		
	02 03 
		01 00 01
1
2
3
4
c9 0b ce cf 1c ba b3 35 85 85 e8 a0 41 d1 b1 
	
	02 41 00 
		e3 01 6c b3 60 9c 1d 64 3c 16 74 39 c3 b9 38 b8 81 f4 23 7f 24 86 0d 3b 1c b8 5a 62 6d 5c cd 47 26 96 4e 0f 82 70 d6 c4 df 9e bf eb cc 53 8e 4e e5 e1 a7 b7 36 8e de 51 ec 6a e9 17 f7 8e b5 98

$$
\because d_q \equiv d \mod q-1
$$

$$
\therefore d_q = d + k(q-1)
$$

两边同乘e
$$
ed_q = ed + ke(q-1)
$$

$$
\because ed = k_1(p-1)(q-1) + 1
$$

$$
\therefore ed_q = k_2(q-1) + 1
$$

即
$$
ed_q + k_2 - 1 = k_2q
$$

$$
\therefore ed_q + k_2 -1 \equiv k_2q \mod 2^{120}
$$

$$
\because dq < q-1
$$

$$
\therefore e > k
$$

枚举k，解方程即求出所有$q$的低120位的可能取值
$$
\because inv ×q \equiv 1 \mod p
$$

$$
inv\times q -1 = kp
$$

两边同乘q得到
$$
inv \times q\times q -q = kn
$$
即
$$
inv \times q^2 - q \equiv 0 \mod n
$$
然后用coper求解

exp.sage

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
#sage
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from gmpy2 import *
from tqdm import *

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
inv = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
d_low = 0xc90bcecf1cbab3358585e8a041d1b1
q_low = []
c = open("flag.enc",'rb').read()

for i in trange(1,e):
    try:
        q0 = invert(i, 2 ** 120) * (e * d_low + i - 1) % 2 ^ 120
        q_low.append(q0)
    except:
        continue

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

for i in trange(len(q_low)-1,-1,-1):
    f = inv * (2^120*x + int(q_low[i]))^2 - (2^120*x + int(q_low[i]))
    f = f.monic()
    root = f.small_roots(X = 2^(512-120))
    if root:
        q = 2^120 * int(root[0]) + int(q_low[i])
        p = n // q
        if p * q == n:
            d = gmpy2.invert(e, (p - 1) * (q - 1))
            print("p = ",p)
            print("q = ",q)
            print("d = ",d)
            key = RSA.construct((int(n),int(e),int(d),int(p),int(q)))
            newkey = PKCS1_OAEP.new(key)
            flag = newkey.decrypt(c)
            print(flag)
            break

2024CISCN——ezrsa

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
from secret import flag

m = bytes_to_long(flag)
key = RSA.generate(1024)
passphrase = str(random.randint(0,999999)).zfill(6).encode()
output = key.export_key(passphrase=passphrase).split(b'\n')
for i in range(7, 15):
    output[i] = b'*' * 64
with open("priv.pem", 'wb') as f:
    for line in output:
        f.write(line + b'\n')
with open("enc.txt", 'w') as f:
    f.write(str(key._encrypt(m)))

priv.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,435BF84C562FE793

9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh
WiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdD
ig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSI
jLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==
-----END RSA PRIVATE KEY-----

类似蓝帽杯2022的corrupted_key

不一样的是，这题得到的pem文件内容是加密的

根据代码

1
key.export_key(passphrase=passphrase).split(b'\n')

找到Crypto下的源代码

RSA.py

发现关键代码

如果passphrase存在，则随机生成一个salt，然后使用PKBDF1方法加密两次拼接得到key。

此时使用的加密方式为3des,模式为cbc,iv为salt

由此我们可以根据passphrase的生成方式来爆破出唯一的passphrase

根据私钥的格式，开头一定是3082，再根据n为1024bit，那么在私钥中n的格式为028181,加密参数e大概率为65537，即0x10001

那么其在私钥中则为 0203010001。

解密后存在如下特征的明文，那么当前的passphrase为所求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF1
from Crypto.Hash import MD5
import base64


enc1 = "9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlhWiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdDig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH"
enc2 = "hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSIjLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg=="

salt = bytes.fromhex("435bf84c562fe793")
dict = [str(i).zfill(6).encode() for i in range(0,1000000)]
for passphrase in dict:
    key = PBKDF1(passphrase, salt, 16, 1, MD5)
    key += PBKDF1(key + passphrase, salt, 8, 1, MD5)
    cipher = DES3.new(key, DES3.MODE_CBC, salt)
    data = cipher.decrypt(base64.b64decode(enc1)).hex()
    if data.startswith("3082") and "028181" in data and "0203010001" in data:
        print(data)
        print(passphrase)
        data2 = cipher.decrypt(base64.b64decode(enc2)).hex()
        print(data2)
        break

得到

1
2
3
4
5
6
7
8
9
10
11
30 82 02 5c
	02 01
		00 		 
		
	02 81 81 00
a1 8f 01 1b eb ac ce da 1c 68 12 73 0b 9e 62 72 0d 3c bd 68 57 af 2c f8 43 18 60 f5 dc 83 c5 52 0f 24 2f 3b e7 c9 e9 6d 7f 96 b4 18 98 ff 00 0f db 7e 43 ef 6f 1e 71 7b 2b 79 00 f3 56 60 a2 1d 1b 16 b5 18 49 be 97 a0 b0 f7 cb cf 5c fe 0f 00 37 0c ce 61 93 fe fa 1f ed 97 b3 7b d3 67 a6 73 56 51 62 ce 17 b0 22 57 08 c0 32 96 1d 17 5b bc 2c 82 9b f2 e1 6e ab c7 e0 88 1f ec a0 97 5c 81

	02 03 
		01 00 01

6a 03 30 64 c5 a0 dff c8 f2 36 3b 34 0e 50 24 05 f1 52 c4 29 87 1a 7a cd d2 8b e1 b6 43 b4 65 28 00 b8 8a 3d 23 cc 57 47 7d 75 dd 55 55 b6 35 16 76 16 ef 5c 60 9d 69 ce 3c 2a ed cb 03 b6 2f 92 9b bc d8 91 ca dc 0b a0 31 ae 6f ec 8a 21 16 d0 80 80 80 80 80 80 80 8

再根据私钥格式提取n,e,dq,inv

因为本题中中间部分的私钥文件缺失，而且加密是cbc的，导致enc2第一块解密的结果错误，需要去掉，也就是说正确的dq只有48bit

因此得到

1
2
3
4
n = 0xa18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_leak= 0x8f2363b340e5
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d

$$
\because ed_q = 1 + k(q-1)
$$

$$
\therefore kq = ed_q +k-1
$$

k可以爆破，但不知道q，所以没办法构造1元coppersmith
$$
\because inv \times q \equiv 1 \mod p
$$

$$
\therefore inv \times q - 1 \equiv 0 \mod p
$$

同乘kq
$$
inv \times q \times kq - kq \equiv 0 \mod n
$$
此时会有个突兀的q，不好处理，我们再同乘k，得到
$$
inv \times (kq)^2 - k\times kq \equiv 0 \mod n
$$
得到两个式子：
$$
tmp = e(x + dq_{low})+k-1
$$

$$
inv\times tmp^2 - k\times tmp \equiv 0 \mod n
$$

恢复出dq之后，$q = (ed_q + k - 1) // k$

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
from tqdm import *
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

n = 0xa18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_leak= 0x8f2363b340e5
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989

def coppersmith(k):
    R.<x> = PolynomialRing(Zmod(n))
    tmp = e * (x * 2^48 + dq_leak) + k - 1          # kq
    f = inv * tmp^2 - k*tmp
    f = f.monic()
    x0 = f.small_roots(X=2^464,beta=1,epsilon=0.09)
    return x0

for k in trange(1，e):
    x0 = coppersmith(k)
    if x0 != []:
        dq = int(x0[0]) * 2^48 + dq_leak
        q = (e*dq + k - 1) // k
        # print(f"k = {k}")
        # k = 47794
        p = n // q
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))
        # b'flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}'
        break

参考：20220709-蓝帽杯-CryptoSecWriteUp | 4XWi11’s Blog

在求出q后，其实pow(c,dq,q)也能出flag，不用求p

-------------已经到底啦！-------------