RSA之共模攻击与共享素数

前言

RSA作为非对称加密算法，拥有公开的加密密钥和解密密钥，应用十分广泛，是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验。作为小白，学习时也是学习到了一丁点，做个总结。

一、RSA加密原理？

1，RSA公开密钥密码体制的原理是：根据数论，寻求两个

大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。说白了，RSA的安全性在于大素数要进行因式分解时很难，因此要保证安全性，就需要1024位甚至更大的密钥。

具体加密流程如下：

（1）选取大素数p和q，计算乘积n=pq，以及 $\varphi$ 。（欧拉函数）

（2）意选择一个大整数e作为密钥，满足e与
$\varphi$ 互素即gcd(e，
$\varphi$ )=1。（e要大于p和q）

（3）确定解密d，满足(de)mod $\varphi$ =1。知道e和
$\varphi$ 求逆元就可求出d。

（4）将明文m加密成密文c，c=!¹(http://www.aiwin.fun/)modn

（5）将密文解密为明文m，m=(c^d)modn

例子：



from Crypto.Util.number import *
p=10169921435575123642561867469669552661717864247752251361375671837367086221354750692635829007786009042729357644276462913457660789233674358081650339142863821
q=10210039189276167395636779557271057346691950991057423589319031237857569595284598319093522326723650646963251941930167018746859556383067696079622198265424441
n = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
e = 65537
fn=(p-1)*(q-1)
d=inverse(e,fn)
flag=b'nihaoaaiwin'
m = bytes_to_long(flag)
c = pow(m, e, n)
print("加密后的密文为:",c)
m1=pow(c,d,n)
print("解密后的明文为:",long_to_bytes(m1))



输出如下:
加密后的密文为: 30320996978056503700180465013618017867185163406587660979060034770264427208999150051618292506467843676241784987801020669459045151758956796476538538705868012636734817663009612301968140319291758424485877429701139619211904602824840221908092573624994756427093909243980813356205286511538441868918324257389972848295
解密后的明文为: b'nihaoaaiwin'

二、共享素数

1，共享素数是指RSA加密时进行了两次加密，并且给出了加密钥e，两次加密的n1和n2，密文c。

例题：[羊城杯2021]Bigrsa:

题目如下:



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

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
print(m)
c = pow(m, e, n1)  # c=(m^e)%n1
c = pow(c, e, n2)  # c=(c^e)%n2
print(c)
# 加密了两次明文



# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

题目中对明文进行了两次的加密，分别使用两次的n，要通过密文解出明文m，那么就得知道两次加密的解密钥d，要求出解密钥d就得需要知道p，q通过求逆元的方法求出d。但是n1和n2的值非常大，通过爆破求因式分解显示不太可能。因此可以看看两个n之间是否存在共用的素数。

解密脚本：



from Crypto.Util.number import *
from gmpy2 import powmod as po, gmpy2
import sympy

c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
q = gmpy2.gcd(n1, n2)#求n1和n2的最大公因数
p1 = n1 // q
p2 = n2 // q
fn1 = (q - 1) * (p2 - 1)  # 求下面的&n;
fn2 = (q - 1) * (p1 - 1)  # 求上面的&n;
d1 = inverse(e, fn1)  # (de)mod((p-1)*(q-1))=1  求到第一次解密密钥d1
d2 = inverse(e, fn2)  # 求出第二次解密密钥d2
m = pow(c, d2, n2)  # 先对第二次加密进行解密
m = pow(m, d1, n1)  # 用第二次解密结果继续解密
print(long_to_bytes(m))

三、共模攻击

1，共模攻击是指利用不同的e和相同的p，q进行两次加密后，通过两次密文c求明文m。

通过公式理解：

a=(m^e1)modn，b=(m^e2)modn。（e1,e2,n,a,b已知情况下求明文m,)

因为 m=(c^d)modn

通过欧几里德算法可知:对于gcd(e1,e2)=1的两个互质数，必定有t,z使e1t+e2z=1，当e1，e2都为正数时，t和z必定是一正一负。

要求出m，正是利用e1t+e2z=1进行求解。

证明如下：

因此可以通过密文a，b以及欧几里德算法求t和z求出明文m。

例题:[SWPUCTF 2021新生赛]crypto1和crypto2:

1，crypto2的题目:



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

flag = '***************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))

n = p * q
e1 = getPrime(32)
e2 = getPrime(32)

flag1 = pow(m1, e1, n)  # flag1=(m1^e1)%n
flag2 = pow(m1, e2, n)  # flag2=(m1^e2)%n   (de)mod&n;=1    m=(c2^d2)%n
print('flag1= ' + str(flag1))
print('flag2= ' + str(flag2))
print('e1= ' + str(e1))
print('e2= ' + str(e2))
print('n= ' + str(n))

# flag1= 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
# flag2= 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
# e1= 3247473589
# e2= 3698409173
# n= 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313

解密脚本如下：



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

flag1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
flag2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1 = 3247473589
e2 = 3698409173
n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313


def rsa_gong_N_def(e1, e2, c1, c2, n):
    e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
    s = gmpy2.gcdext(e1, e2)  # 扩展欧几里得算法  t*e1+z*e2=1,求出t和z
    t = s[1]
    z = s[2]
    if t < 0:  # 要求c的s次幂，就要先计算c的模反元素c2r，然后求c2r的-s2次幂
        t = - t
        c1 = gmpy2.invert(c1, n)  # 求c1的逆元
    elif z < 0:
        z = -z
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1, t, n) * pow(c2, z, n)) % n  # (c1^s1*c2^s2)%n=m%n=m
    return m


result = rsa_gong_N_def(e1, e2, flag1, flag2, n)
print(long_to_bytes(result))

2，crypto1:



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



flag  = '****************************'
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))

e1e2 = 3087# 3*3*7*7*7
n = p*q
print()

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437

这题要比上题的难度高，题目并没有给出e1和e2的具体值，只给出了e1e2，所以要对e1，e2的值进行爆破，此时求得的(a^tb^z)%n=(m^k)%n，k为e1和e2的最大公因数，并非原明文m。

解密脚本如下:



import gmpy2
from Crypto.Util.number import long_to_bytes

flag1 = 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
flag2 = 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n = 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1e2 = 3087


def rsa_gong_N_def(e1, e2, c1, c2, n):
    e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
    s = gmpy2.gcdext(e1, e2)  # 扩展欧几里得算法
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n  # m=(m^7)%n
    return int(m)


def de(c, e, n):  # 因为此时的m不是真正的m，而是m^k，所以对m^k进行爆破
    k = 0
    while k < 1000:
        mk = c + n * k  # 对(m^7)%n的值+nk，直至能够进行开最大公因数次方,就求出了明文m,当得到m^7时进行开7次方就得到了明文m
        flag, true = gmpy2.iroot(mk, e)  # 若能开方,则会返回true
        if True == true:
            return flag
        k += 1


for e1 in range(2, e1e2):
    if e1e2 % e1 == 0:  # 爆破可整除的e1,e2
        e2 = e1e2 // e1
        c = rsa_gong_N_def(e1, e2, flag1, flag2, n)  # 返回的结果为(m^k)%n,(m^7)%n
        print(c)
        e = gmpy2.gcd(e1, e2)  # 求出e1和e2的最大公因数,7
        m1 = de(c, e, n)
        if m1:
            print(long_to_bytes(int(m1)))

{} ↩

~ ~ The End ~ ~

首页|Aiwin