RSA学习

了解结构

  • 明文m

  • 密文c

  • 公钥e，一个整数，一般情况下是公开的

  • 两个大质数p,q,一般不公开，通过计算n=p*q得到n，此时n的逆向分解很困难，保证加密安全性

  • 私钥d,解密用的钥匙，不公开，但满足条件$e*d mod (p-1)(q-1)=1$ .所以可计算得出,计算代码：

    gmpy2.invert(e,(p-1)*(q-1))

  • 加密过程：$c=m^emodn$ 计算代码: c=pow(m,e,n)

  • 解密过程：$m=c^dmod n$ 计算代码：m=pow(c,d,n)

n可以被直接分解

例题：BUUCTF：[WUSTCTF2020]babyrsa

附件给出c,n,e,此题的n不算太大，因此可以分解n为p,q,然后算出私钥d,即可解出答案

exp:

c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537
p=189239861511125143212536989589123569301
q=386123125371923651191219869811293586459

import gmpy2
from Crypto.Util.number import *

d=gmpy2.invert(e,(p-1)*(q-1))
print("d=",d)

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

低加密指数攻击 (e很小)

特征，n很大但e很小

例题：BUUCTF Dangrous RSA

此题n太大了，分解不了，因此换一个思路，由于e 很小，则有条件$c=m^e+kn$ 。这样我们可以爆破这个k的值，让m可以开方，这样可以直接爆破出密文

exp:

n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793

e=3

c=0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

from gmpy2 import *
from Crypto.Util.number import *
# 爆破函数，从k=0开始，逐步爆破，直到m可以被e开方
def de(c, e, n):
    k = 0
    while True:
        m = c - n*k
        result, flag = gmpy2.iroot(m, e) #判断m开方e是否为整数，如是，则flag=True。
        if flag == True:
            return result
        k += 1

m=de(c,e,n)

print(m)
print(long_to_bytes(m))

低指数加密广播攻击

特征:多组n，c，但是使用的是同一个e且e很小

例题：BUUCTF RSA4

多组n,c时考虑将n,c放入数组中，形式为n=[n1,n2,n3]，c=[c1,c2,c3]。然后使用sympy库中的中国剩余定理，这具体是个啥定理我目前也不太理解，但是调用crt(c,n)方法可以得出m的e次方，最后开方即可

from gmpy2 import *
from Crypto.Util.number import *
from sympy.ntheory.modular import *

n1=int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1=int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

n2=int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2=int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

n3=int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3=int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

e=1
n=[n1,n2,n3]
c=[c1,c2,c3]
result,mod=crt(n,c)
#这里我爆破e的值，如果开方成功则输出答案
while e<1000:
    value, is_perfect = gmpy2.iroot(result, e)
    if is_perfect==True:
        print(long_to_bytes(value))
    e+=1

公因数攻击

特征：很多组n,c

例题：BUUCTF RSA5

题目给出了e和贼多组n，c。因此考虑公因数攻击，当有很多组n时，有可能出现两个n之间存在公因数的情况。又因为n是由指数p*q,因此得到公因数就等于得到了p和q，则题目可解

n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

...........
#20组数据就不摆上来了

e=65537

from gmpy2 import *
from Crypto.Util.number import *
from libnum import *

n=[]
c=[]
p=[]

for i in range(1,20):
    n.append(eval('n'+str(i)))
    c.append(eval('n'+str(i)))

for i in range(len(n)):
    for j in range(i+1,len(n)):
        if gmpy2.gcd(n[i],n[j])!=1:
            print("i=%d j=%d" %(i,j))
            print(gmpy2.gcd(n[i],n[j]))

p=gmpy2.gcd(n5,n18)
q=n18//p

d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c18,d,n18)
print(long_to_bytes(m))

共模攻击

特征:多组e，c，共用一个n，且e之间最好互质

例题：BUUCTF [BJDCTF2020]rsa_output

解法：当e1,e2互质时，他们的最大公因数为1，即gcd(e1,e2)=1。根据欧几里得拓展算法，可以得到一个有解的式子：$e1x+e2y=gcd(e1,e2)$ 。得到x,y之后，根据加密过程，化简式子可得:$m=(c1^x*c2^y)modn$。由此得到明文。

exp

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

n=21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111

e1=3659
e2=2767

c1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227


_,x,y=gmpy2.gcdext(e1,e2)#拓展欧几里得算法，得到x,y
print(gcd(e1,e2))#查看e1,e2是否互质
print(x,y)
m=pow(c1,y,n)*pow(c2,x,n)%n#这里我就理解为x,y是密文解密的私钥了
print(m)
print(long_to_bytes(m))

dp泄露

特征：提供了dp，e，n，c

例题：BUUCTF RSA2

解析：这个题有点抽象，n不够大的情况下可以直接分解为p,q，然后求解私钥就能解了，没用到dp。

当然我们先知道dp是什么，$dp=d\%(p-1)$ 。随后推导可以得到：$edp=1+k(p-1)$。随后使用爆破求k的方式即可求出p，随后求出q，最后就能得到密钥d。

import gmpy2
from Crypto.Util.number import long_to_bytes
 
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
 
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
 
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 // (((dp * e - 1) // i) + 1)
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)
 
print(m)
print(long_to_bytes(m))

dp,dq泄露

特征：给出了dp,dq,则不需要e即可得出明文

例题：BUUCTF RSA1

解析：

$m1 = c^{dp}modp$

$m2 = c^{dq}modq$

$m = (((m1-m2)I)\%p)q+m2$

I表示p,q的逆元

exp

import gmpy2
from Crypto.Util.number import *


p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469

dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041

c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

i=gmpy2.invert(p,q)
print("i=",i)

m1=pow(c,dp,p)
m2=pow(c,dq,q)


m=(((m1-m2)*i)%q)*p+m2
print(m)
print(long_to_bytes(m))