RSA解题思路（一）

博主： warn
发布时间：2023 年 05 月 26 日
217 次浏览
暂无评论
10474字数
分类：默认分类

RSA解题思路（一）

基于LitCTF2023的总结

已知p、q、e求d

import gmpy2  
p = 3487583947589437589237958723892346254777  
q = 8767867843568934765983476584376578389  
e = 65537  
phi = (p-1)*(q-1)       
#接下来求逆元
d = gmpy2.invert(e,phi) 
print d

共享素数

例子：[羊城杯 2021]Bigrsa已解决

from Crypto.Util.number import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

q = GCD(n1,n2)#求出共同的素数
#分别求出p1和p2
p1 = n1 // q
p2 = n2 // q
#通过得到的p1和p2求出逆元d1和d2
d1 = invert(e, (q-1)*(p1-1))
d2 = invert(e, (q-1)*(p2-1))

k=pow(c, d2, n2)#根据题目反向推
m=pow(k, d1, n1)
print(long_to_bytes(m))

得出：SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}

使用yafu分解n求出因子

例子：[LitCTF 2023]yafu (中级)

from Crypto.Util.number import*
import gmpy2

# m = bytes_to_long(flag)
# n  = 1
# for i in range(15):
#     n *=getPrime(32)
# e = 65537
# c = pow(m,e,n)
# print(f'n = {n}')
# print(f'c = {c}')

n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
e=65537

# .\yafu-x64.exe "factor(15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307)"

P1 = 2201440207
P2 = 3354884521
P3 = 2719600579
P4 = 4171911923
P5 = 2923522073
P6 = 3355651511
P7 = 4044505687
P8 = 3989697563
P9 = 2585574697
P10 = 4021078331
P11 = 2151018733
P12 = 2767137487
P13 = 2758708999
P14 = 2906576131
P15 = 2315495107

phi=(P1-1)*(P2-1)*(P3-1)*(P4-1)*(P5-1)*(P6-1)*(P7-1)*(P8-1)*(P9-1)*(P10-1)*(P11-1)*(P12-1)*(P13-1)*(P14-1)*(P15-1)

d = gmpy2.invert(e,phi)

m = gmpy2.powmod(c,d,n)

print(long_to_bytes(m))

得：LitCTF{Mu1tiple_3m4ll_prim5_fac7ors_@re_uns4f5}

备注：分解因子也可以使用factordb.com

如下题>

[LitCTF 2023]factordb (中级)

from Crypto.Util.number import *
import gmpy2
e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

#用factordb分解因子
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239

phi = (p-1)*(q-1)

d=gmpy2.invert(e,phi)

m = gmpy2.powmod(c,d,n)

print(long_to_bytes(m))

LitCTF{it_is_easy_to_solve_question_when_you_know_p_and_q}

已知dp、n、e、c求m（dp泄露）

公式推导：

dp≡d mod (p−1) ——>dp e ≡ d e mod (p−1) ——> d e ≡ k (p-1)+dp *e

由于：d e = 1 mod phi ——> k (p-1) + dp e = 1 mod (p-1)(q-1)

——> k1 (p-1) + dp e = k2 (p-1)(q-1) + 1

设：X = k2 (q - 1) - k1 ——> dp e = X * (p - 1) +1

范围： dp < p-1 ——> X < e ——> 0<X<e

利用公式则可以求出d:

for i in range(1,e):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n//p
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi

例子：[LitCTF 2023]P_Leak

from Crypto.Util.number import *
import gmpy2
e=65537
# m=bytes_to_long(b'xxxx')
# p=getPrime(512)
# q=getPrime(512)
# n=p*q
# phi=(p-1)*(q-1)
# d=inverse(e,phi)
# dp=d%(p-1)
# c=pow(m,e,n)
# print("dp=",dp)
# print("n=",n)
# print("c=",c)
dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
#套用公式
for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phi=(p-1)*(q-1)
        d=gmpy2.invert(e, phi)
        m=gmpy2.powmod(c, d, n)
        break
print(long_to_bytes(m))

当e和phi不互素

当e非常小，但n很大：

由于 c = m ** e mod n:

当 m e < n 时， c = m e 只要对c开方就可以得到m

当 m e> n 时， m e = k * n + c，需要对 k 进行爆破

例子：[LitCTF 2023]e的学问：

from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'xxxxxx')
# p=getPrime(256)
# q=getPrime(256)
e=74
# n=p*q
# c=pow(m,e,n)
# print("p=",p)
# print("q=",q)
# print("c=",c)
p= 86053582917386343422567174764040471033234388106968488834872953625339458483149
q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

n = p*q
#套用公式求解
i = 0
while 1:
    m = gmpy2.iroot(i*n+c,e)
    if(m[1] == True):
        print(long_to_bytes(m))
        break
    i += 1

RSA解方程

利用sympy库，将已知的方程组求解

例子：[LitCTF 2023]easy_math (中级)

from Crypto.Util.number import *
import gmpy2
import sympy
# from secret import flag

# m = bytes_to_long(flag)
e = 65537
# p = getPrime(512)
# q = getPrime(128)
# n = p*q
# hint = p**3-q**5
# c = pow(m,e,n)
# print(f'n = {n}')
# print(f'c = {c}')
# print(f'hint = {hint}')

n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932

#这一步利用方程组求解p，q
p = sympy.Symbol('p')
q = sympy.Symbol('q')
solve_value = sympy.solve([p*q-n,p**3-q**5-hint],[p,q])
print(solve_value)

#得到p,q
# p=7321664971326604351487965655099805117568571010588695608389113791312918573783115429227542573780838065461696504325762281209452761930184231131129306271846427
# q=304683618109085947723284393392507415311

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

RSA异或

由：n1=n2^n3 可得：

n2 = n1^n3, n3 = n1 ^n2

例子：The same common divisor (高级)

from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'xxxxxx')
e=65537
# p=getPrime(1024)
# q1=getPrime(1024)
# q2=getPrime(1024)
# n1=p*q1
# n2=p*q2
# c1=pow(m,e,n1)
# c2=pow(m,e,n2)
# n3=n1^n2
# print('n1=',n1)
# print('n3=',n3)
# print('c1=',c1)
# print('c2=',c2)
n1= 9852079772293301283705208653824307027320071498525390578148444258198605733768947108049676831872672654449631852459503049139275329796717506126689710613873813880735666507857022786447784753088176997374711523987152412069255685005264853118880922539048290400078105858759506186417678959028622484823376958194324034590514104266608644398160457382895380141070373685334979803658172378382884352616985632157233900719194944197689860219335238499593658894630966428723660931647038577670614850305719449893199713589368780231046895222526070730152875112477675102652862254926169713030701937231206405968412044029177246460558028793385980934233
n3= 4940268030889181135441311597961813780480775970170156650560367030148383674257975796516865571557828263935532335958510269356443566533284856608454193676600884849913964971291145182724888816164723930966472329604608512023988191536173112847915884014445539739070437180314205284883149421228744714989392788108329929896637182055266508625177260492776962915873036873839946591259443753924970795669864031580632650140641456386202636466624658715315856453572441182758855085077441336516178544978457053552156714181607801760605521338788424464551796638531143900048375037218585999440622490119344971822707261432953755569507740550277088437182
c1= 7066425618980522033304943700150361912772559890076173881522840300333719222157667104461410726444725540513601550570478331917063911791020088865705346188662290524599499769112250751103647749860198318955619903728724860941709527724500004142950768744200491448875522031555564384426372047270359602780292587644737898593450148108629904854675417943165292922990980758572264063039172969633878015560735737699147707712154627358077477591293746136250207139049702201052305840453700782016480965369600667516646007546442708862429431724013679189842300429421340122052682391471347471758814138218632022564279296594279507382548264409296929401260
c2= 854668035897095127498890630660344701894030345838998465420605524714323454298819946231147930930739944351187708040037822108105697983018529921300277486094149269105712677374751164879455815185393395371001495146490416978221501351569800028842842393448555836910486037183218754013655794027528039329299851644787006463456162952383099752894635657833907958930587328480492546831654755627949756658554724024525108575961076341962292900510328611128404001877137799465932130220386963518903892403159969133882215092783063943679288192557384595152566356483424061922742307738886179947575613661171671781544283180451958232826666741028590085269
#利用公式
n2 = n3 ^ n1
p=gmpy2.gcd(n1,n2)
q=n1//p
c=c1
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=gmpy2.invert(e, phi_n)
m=pow(c, d, n)
print(long_to_bytes(m))

RSA（欧拉定理）

欧拉定理： m ** phi mod n ≡ 1

例子：[LitCTF 2023]Euler

题目：

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,n-p-q+3,n)
print(f'n = {n}')
print(f'c = {c}')
"""
n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441
"""

题目中：c = pow(m,n-p-q+3,n)

由 n = p q ——>n-p-q+3 = (p-1)(q-1)+2=phi+2

根据欧拉定理： m phi mod n ≡ 1 ——> m phi = 1 mod n

则 c = m (phi+2) mod n = m 2 mod n

这样就转换为了低指数暴力破解了

from Crypto.Util.number import *
import gmpy2
# from secret import flag

# m = bytes_to_long(flag)
# p = getPrime(512)
# q = getPrime(512)
# n = p*q
# c = pow(m,n-p-q+3,n)
# print(f'n = {n}')
# print(f'c = {c}')

n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441

#这里做了默认e =65537
for i in range (0,65537):
    c1 = c + i*n
    m,f = gmpy2.iroot(c1,2)
    if f:
        print(long_to_bytes(m))
        break

RSA 低指数加密 P +p高位泄露

题目：

from Crypto.Util.number import *
m=bytes_to_long(b'XXXX')
e=65537
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print(p)
c=pow(m,e,n)
P=p>>340
print(P)
a=pow(P,3,n)
print("n=",n)
print("c=",c)
print("a=",a)
#n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
#c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
#a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

由上面的经验积累，我们可以很容易想到爆破P

from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'XXXX')
e=65537
# p=getPrime(1024)
# q=getPrime(1024)
# n=p*q
# print(p)
# c=pow(m,e,n)
# P=p>>340
# print(P)
# a=pow(P,3,n)
# print("n=",n)
# print("c=",c)
# print("a=",a)
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

#破解P:
for i in range(e):
    a1 = a+i*n
    P,f = gmpy2.iroot(a1, 3)
    if(f):
        break
print(P)

# P=66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946

p位于高位，P位于低位，属于p高位泄露攻击

这题的求解需要使用sage,可使用在线网站：Sage Cell Server (sagemath.org)

使用Coppersmith脚本:

# sage
P = 66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946
n = 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
kbits = 340
pbits = (P << kbits).nbits()
pbar = (P << kbits) & (2^pbits-2^kbits)
print ("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
#这里引用[LitCTF 2023]Where is P? jiaqiniu的WriteUp

pbits = P<<kbits.nbits().nbits() ——————————此题的kbits为340

PR. = PolynomialRing(Zmod(n)) 用于生成一个以x为符号的一元多项式环

f = x + pbar 定义求解的函数多项式小值根求解及因子分解，其中X表示求解根的上界

求出p后，就是简单的RSA求解了：

# sage
from Crypto.Util.number import *
import gmpy2

# m=bytes_to_long(b'XXXX')
e=65537
# p=getPrime(1024)
# q=getPrime(1024)
# n=p*q
# print(p)
# c=pow(m,e,n)
# P=p>>340
# print(P)
# a=pow(P,3,n)
# print("n=",n)
# print("c=",c)
# print("a=",a)
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

#破解P:
# for i in range(e):
#     a1 = a+i*n
#     P,f = gmpy2.iroot(a1, 3)
#     if(f):
#         break
# print(P)

P=66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946


p=148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459

q =n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

最后修改：2023 年 08 月 04 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

RSA解题思路（一）
评论数： 0
RSA算法原理
评论数： 0
关于crypto的long_to_bytes报错
评论数： 0
关于留言板
评论数： 0
文件上传漏洞（入门）
评论数： 0

正则绕过(一)
评论数： 0
RSA算法原理
评论数： 0
23工控-wp
评论数： 0
关于留言板
评论数： 0
Hackergame2023-wp
评论数： 0

RSA解题思路（一）

warn • 2023 年 05 月 26 日

<h1>RSA解题思路（一）</h1><h2>基于LitCTF2023的总结</h2><h2>已知p、q、e求d</h2><pre><code class="lang-python">import gmpy2  
p = 3487583947589437589237958723892346254777  
q = 8767867843568934765983476584376578389  
e = 65537  
phi = (p-1)*(q-1)       
#接下来求逆元
d = gmpy2.invert(e,phi) 
print d </code></pre><h2>共享素数</h2><p>例子：[羊城杯 2021]Bigrsa已解决</p><pre><code class="lang-python">from Crypto.Util.number import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

q = GCD(n1,n2)#求出共同的素数
#分别求出p1和p2
p1 = n1 // q
p2 = n2 // q
#通过得到的p1和p2求出逆元d1和d2
d1 = invert(e, (q-1)*(p1-1))
d2 = invert(e, (q-1)*(p2-1))

k=pow(c, d2, n2)#根据题目反向推
m=pow(k, d1, n1)
print(long_to_bytes(m))</code></pre><p>得出：SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}</p><h2>使用yafu分解n求出因子</h2><p>例子：[LitCTF 2023]yafu (中级)</p><pre><code class="lang-python">from Crypto.Util.number import*
import gmpy2

# m = bytes_to_long(flag)
# n  = 1
# for i in range(15):
#     n *=getPrime(32)
# e = 65537
# c = pow(m,e,n)
# print(f'n = {n}')
# print(f'c = {c}')

n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
e=65537

# .\yafu-x64.exe &quot;factor(15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307)&quot;

P1 = 2201440207
P2 = 3354884521
P3 = 2719600579
P4 = 4171911923
P5 = 2923522073
P6 = 3355651511
P7 = 4044505687
P8 = 3989697563
P9 = 2585574697
P10 = 4021078331
P11 = 2151018733
P12 = 2767137487
P13 = 2758708999
P14 = 2906576131
P15 = 2315495107

phi=(P1-1)*(P2-1)*(P3-1)*(P4-1)*(P5-1)*(P6-1)*(P7-1)*(P8-1)*(P9-1)*(P10-1)*(P11-1)*(P12-1)*(P13-1)*(P14-1)*(P15-1)

d = gmpy2.invert(e,phi)

m = gmpy2.powmod(c,d,n)

print(long_to_bytes(m))</code></pre><p>得：LitCTF{Mu1tiple_3m4ll_prim5_fac7ors_@re_uns4f5}</p><h2>备注：分解因子也可以使用<span class="external-link"><a class="no-external-link" href="http://www.factordb.com/" target="_blank"><i data-feather="external-link"></i>factordb.com</a></span></h2><p>如下题&gt;</p><h2>[LitCTF 2023]factordb (中级)</h2><pre><code>from Crypto.Util.number import *
import gmpy2
e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

#用factordb分解因子
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239

phi = (p-1)*(q-1)

d=gmpy2.invert(e,phi)

m = gmpy2.powmod(c,d,n)

print(long_to_bytes(m))</code></pre><p>LitCTF{it_is_easy_to_solve_question_when_you_know_p_and_q}</p><h2>已知dp、n、e、c求m（dp泄露）</h2><h3>公式推导：</h3><p>    dp≡d mod (p−1)  ——&gt;dp <em> e ≡ d </em>e mod (p−1) ——&gt; d <em> e  ≡ k </em>(p-1)+dp *e</p><p>    由于：d <em> e = 1 mod phi  ——&gt; k </em> (p-1) + dp <em> e = 1 mod (p-1)</em>(q-1)</p><p>    ——&gt; k1 <em> (p-1) + dp </em> e = k2 <em> (p-1)</em>(q-1) + 1</p><p>    设：X = k2 <em> (q - 1) - k1 ——&gt; dp </em> e = X * (p - 1) +1</p><p>    范围： dp &lt; p-1  ——&gt;  X &lt; e ——&gt; 0&lt;X&lt;e</p><p>利用公式则可以求出d:</p><pre><code class="lang-python">for i in range(1,e):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n//p
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi</code></pre><h3>例子：[LitCTF 2023]P_Leak</h3><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
e=65537
# m=bytes_to_long(b'xxxx')
# p=getPrime(512)
# q=getPrime(512)
# n=p*q
# phi=(p-1)*(q-1)
# d=inverse(e,phi)
# dp=d%(p-1)
# c=pow(m,e,n)
# print(&quot;dp=&quot;,dp)
# print(&quot;n=&quot;,n)
# print(&quot;c=&quot;,c)
dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
#套用公式
for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phi=(p-1)*(q-1)
        d=gmpy2.invert(e, phi)
        m=gmpy2.powmod(c, d, n)
        break
print(long_to_bytes(m))</code></pre><h2>当e和phi不互素</h2><p>当e非常小，但n很大：</p><p>    由于 c = m ** e mod n:</p><p>    当 m <strong> e &lt; n 时， c = m </strong> e 只要对c开方就可以得到m</p><p>    当 m <strong> e&gt; n 时 ， m </strong> e = k * n +  c，需要对 k 进行爆破</p><p>例子：[LitCTF 2023]e的学问：</p><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'xxxxxx')
# p=getPrime(256)
# q=getPrime(256)
e=74
# n=p*q
# c=pow(m,e,n)
# print(&quot;p=&quot;,p)
# print(&quot;q=&quot;,q)
# print(&quot;c=&quot;,c)
p= 86053582917386343422567174764040471033234388106968488834872953625339458483149
q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

n = p*q
#套用公式求解
i = 0
while 1:
    m = gmpy2.iroot(i*n+c,e)
    if(m[1] == True):
        print(long_to_bytes(m))
        break
    i += 1
</code></pre><h2>RSA解方程</h2><p>利用sympy库，将已知的方程组求解</p><p>例子：[LitCTF 2023]easy_math (中级)</p><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
import sympy
# from secret import flag

# m = bytes_to_long(flag)
e = 65537
# p = getPrime(512)
# q = getPrime(128)
# n = p*q
# hint = p**3-q**5
# c = pow(m,e,n)
# print(f'n = {n}')
# print(f'c = {c}')
# print(f'hint = {hint}')

n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932

#这一步利用方程组求解p，q
p = sympy.Symbol('p')
q = sympy.Symbol('q')
solve_value = sympy.solve([p*q-n,p**3-q**5-hint],[p,q])
print(solve_value)

#得到p,q
# p=7321664971326604351487965655099805117568571010588695608389113791312918573783115429227542573780838065461696504325762281209452761930184231131129306271846427
# q=304683618109085947723284393392507415311

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))</code></pre><h2>RSA异或</h2><p>由：n1=n2^n3 可得：</p><p>n2 = n1^n3, n3 = n1 ^n2</p><p>例子：The same common divisor (高级)</p><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'xxxxxx')
e=65537
# p=getPrime(1024)
# q1=getPrime(1024)
# q2=getPrime(1024)
# n1=p*q1
# n2=p*q2
# c1=pow(m,e,n1)
# c2=pow(m,e,n2)
# n3=n1^n2
# print('n1=',n1)
# print('n3=',n3)
# print('c1=',c1)
# print('c2=',c2)
n1= 9852079772293301283705208653824307027320071498525390578148444258198605733768947108049676831872672654449631852459503049139275329796717506126689710613873813880735666507857022786447784753088176997374711523987152412069255685005264853118880922539048290400078105858759506186417678959028622484823376958194324034590514104266608644398160457382895380141070373685334979803658172378382884352616985632157233900719194944197689860219335238499593658894630966428723660931647038577670614850305719449893199713589368780231046895222526070730152875112477675102652862254926169713030701937231206405968412044029177246460558028793385980934233
n3= 4940268030889181135441311597961813780480775970170156650560367030148383674257975796516865571557828263935532335958510269356443566533284856608454193676600884849913964971291145182724888816164723930966472329604608512023988191536173112847915884014445539739070437180314205284883149421228744714989392788108329929896637182055266508625177260492776962915873036873839946591259443753924970795669864031580632650140641456386202636466624658715315856453572441182758855085077441336516178544978457053552156714181607801760605521338788424464551796638531143900048375037218585999440622490119344971822707261432953755569507740550277088437182
c1= 7066425618980522033304943700150361912772559890076173881522840300333719222157667104461410726444725540513601550570478331917063911791020088865705346188662290524599499769112250751103647749860198318955619903728724860941709527724500004142950768744200491448875522031555564384426372047270359602780292587644737898593450148108629904854675417943165292922990980758572264063039172969633878015560735737699147707712154627358077477591293746136250207139049702201052305840453700782016480965369600667516646007546442708862429431724013679189842300429421340122052682391471347471758814138218632022564279296594279507382548264409296929401260
c2= 854668035897095127498890630660344701894030345838998465420605524714323454298819946231147930930739944351187708040037822108105697983018529921300277486094149269105712677374751164879455815185393395371001495146490416978221501351569800028842842393448555836910486037183218754013655794027528039329299851644787006463456162952383099752894635657833907958930587328480492546831654755627949756658554724024525108575961076341962292900510328611128404001877137799465932130220386963518903892403159969133882215092783063943679288192557384595152566356483424061922742307738886179947575613661171671781544283180451958232826666741028590085269
#利用公式
n2 = n3 ^ n1
p=gmpy2.gcd(n1,n2)
q=n1//p
c=c1
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=gmpy2.invert(e, phi_n)
m=pow(c, d, n)
print(long_to_bytes(m))</code></pre><h2>RSA（欧拉定理）</h2><p>欧拉定理： m ** phi mod n ≡  1</p><p>例子：[LitCTF 2023]Euler</p><p>题目：</p><pre><code class="lang-python">from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,n-p-q+3,n)
print(f'n = {n}')
print(f'c = {c}')
&quot;&quot;&quot;
n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441
&quot;&quot;&quot;</code></pre><p>题目中：c = pow(m,n-p-q+3,n)</p><p>由 n = p <em> q ——&gt;n-p-q+3 = (p-1)</em>(q-1)+2=phi+2</p><p>根据欧拉定理： m <strong> phi mod n ≡  1 ——&gt; m </strong> phi = 1 mod n</p><p>则 c = m <strong> (phi+2) mod n = m </strong> 2 mod n</p><p>这样就转换为了低指数暴力破解了</p><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
# from secret import flag

# m = bytes_to_long(flag)
# p = getPrime(512)
# q = getPrime(512)
# n = p*q
# c = pow(m,n-p-q+3,n)
# print(f'n = {n}')
# print(f'c = {c}')

n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441

#这里做了默认e =65537
for i in range (0,65537):
    c1 = c + i*n
    m,f = gmpy2.iroot(c1,2)
    if f:
        print(long_to_bytes(m))
        break</code></pre><h2>RSA 低指数加密 P +p高位泄露</h2><p>题目：</p><pre><code class="lang-python">from Crypto.Util.number import *
m=bytes_to_long(b'XXXX')
e=65537
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print(p)
c=pow(m,e,n)
P=p&gt;&gt;340
print(P)
a=pow(P,3,n)
print(&quot;n=&quot;,n)
print(&quot;c=&quot;,c)
print(&quot;a=&quot;,a)
#n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
#c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
#a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605
</code></pre><p>由上面的经验积累，我们可以很容易想到爆破P</p><pre><code class="lang-python">from Crypto.Util.number import *
import gmpy2
# m=bytes_to_long(b'XXXX')
e=65537
# p=getPrime(1024)
# q=getPrime(1024)
# n=p*q
# print(p)
# c=pow(m,e,n)
# P=p&gt;&gt;340
# print(P)
# a=pow(P,3,n)
# print(&quot;n=&quot;,n)
# print(&quot;c=&quot;,c)
# print(&quot;a=&quot;,a)
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

#破解P:
for i in range(e):
    a1 = a+i*n
    P,f = gmpy2.iroot(a1, 3)
    if(f):
        break
print(P)

# P=66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946
</code></pre><p>p位于高位，P位于低位，属于p高位泄露攻击</p><p>这题的求解需要使用sage,可使用在线网站：<span class="external-link"><a class="no-external-link" href="https://sagecell.sagemath.org/" target="_blank"><i data-feather="external-link"></i>Sage Cell Server (sagemath.org)</a></span></p><p>使用Coppersmith脚本:</p><pre><code class="lang-R"># sage
P = 66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946
n = 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
kbits = 340
pbits = (P &lt;&lt; kbits).nbits()
pbar = (P &lt;&lt; kbits) &amp; (2^pbits-2^kbits)
print (&quot;upper %d bits (of %d bits) is given&quot; % (pbits-kbits, pbits))

PR.&lt;x&gt; = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root &lt; 2^kbits with factor &gt;= n^0.3
#这里引用[LitCTF 2023]Where is P? jiaqiniu的WriteUp</code></pre><p>    </p><p>    pbits = P&lt;&lt;kbits.nbits().nbits()  ——————————此题的kbits为340</p><p>    PR.<x> = PolynomialRing(Zmod(n)) 用于生成一个以x为符号的<span class="external-link"><a class="no-external-link" href="https://so.csdn.net/so/search?q=一元多项式&spm=1001.2101.3001.7020" target="_blank"><i data-feather="external-link"></i>一元多项式</a></span>环</p><p>    f = x + pbar 定义求解的函数 <span class="external-link"><a class="no-external-link" href="https://so.csdn.net/so/search?q=多项式&spm=1001.2101.3001.7020" target="_blank"><i data-feather="external-link"></i>多项式</a></span>小值根求解及因子分解，其中X表示求解根的上界</p><p>求出p后，就是简单的RSA求解了：</p><pre><code class="lang-pyth"># sage
from Crypto.Util.number import *
import gmpy2

# m=bytes_to_long(b'XXXX')
e=65537
# p=getPrime(1024)
# q=getPrime(1024)
# n=p*q
# print(p)
# c=pow(m,e,n)
# P=p&gt;&gt;340
# print(P)
# a=pow(P,3,n)
# print(&quot;n=&quot;,n)
# print(&quot;c=&quot;,c)
# print(&quot;a=&quot;,a)
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

#破解P:
# for i in range(e):
#     a1 = a+i*n
#     P,f = gmpy2.iroot(a1, 3)
#     if(f):
#         break
# print(P)

P=66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946

p=148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459

q =n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))</code></pre>

RSA解题思路（一）

基于LitCTF2023的总结

已知p、q、e求d

共享素数

使用yafu分解n求出因子

备注：分解因子也可以使用factordb.com

[LitCTF 2023]factordb (中级)

已知dp、n、e、c求m（dp泄露）

公式推导：

例子：[LitCTF 2023]P_Leak

当e和phi不互素

RSA解方程

RSA异或

RSA（欧拉定理）

RSA 低指数加密 P +p高位泄露

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

RSA解题思路（一）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款