【密码学】破解RSA密码（Python代码实现）

题目👇

已知有人写了如下的代码，并将生成的(n,e,c)以及(n2,e2,c2,(p2+1)*(q2+1))输出。

from Crypto.Util.number import *

def ef():
    p=getPrime(512)
    q=getPrime(512)
    flag=open("flag","rb").read()
    m=bytes_to_long(flag)
    e=65537
    n=p*q
    c=pow(m,e,n)
    print(n,e,c)  #
    return p,q

def epq(p,q):
    p2=getPrime(1024)
    q2=getPrime(1024)
    e2=65537
    m2=p+q
    n2=p2*q2
    c2=pow(m2,e2,n2)
    print(n2,e2,c2,(p2+1)*(q2+1)) #

p,q=ef()
epq(p,q)

输出(n,e,c)以及(n2,e2,c2,(p2+1)*(q2+1))如下：

(86902041785171683231305301154659574124170175717542478743469937094129588097899526472297338165763793395403138052107436307148655516237914989260641272558370267587581870375426597336633068656306063961150434589742092844368242428011721324737315708847899038491875643600715933822290329122093126146305056053635875427149L, 65537, 15833685544860151615528563318175057334854555807563811248911092184962045410721043935895279999715546874344448072757248024629816018687138160349497178202841685747385455984597261139196670787723191129190281464722284764818569442853999503305719960273532581788705319675785365330814771611391805600982635624166616994909L)

(18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828433745751900636977114625384201443358493405946175157229330447527380345317933922535718700042422977893867943656666930789561406630888405895439054817890293649823406983304364531032464229623788486039136673884818993067818472490283937605836580590843487927803181532325018537076264511576862025094690559279649143498659102849L, 65537, 7392251042794448813724942265095985628606500546061544026052413736090062985580390082556940969813307099293888028876436850564855740297176392396726998769680589219160575972891500463789856128741737806143813567755324525667951325489807002065570746854557547784519649141813876707420713784143969266692484619922991587339418980913573323306950701125825931923149350170489304772562424051072424741158162269063304635895188390600892069271483630208193319815348033784877031408074730563809389105637498825225265591866481815230255385046830196748192233124781928655809322769875744414705189416861877961926362356094198048709542228727393696757158L, 18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828434020648157035533967661393926860975983001244775722594600595802713222548261077015534360904269663877978505992018966625264663179236777522008665977063509158288897299644184441313228368572324485490486359818154230942787018240908451883098571389138398322839231059197174670650732257722735400365023996558029601185819826736L)

请编写代码，求出flag。

思路分析👇

首先要搞清楚RSA的加密解密原理，其算法过程如下：

由用户选择两个互异并且距离较远的大素数p和q；

计算n=p×q和**φn)=(p-1)×(q-1)**；

选择正整数e，使其与f(n)的最大公约数为1；

然后计算正整数d，使得e×d 对f(n)的余数为1，即e×d≡1 mod φ(n)，最后销毁p和q。

经过以上步骤，得出公钥对(n,e)和私钥对(n,d)。

设M为明文，C为对应的密文，

则加密变换为：C=M^e mod n；

解密变换为：M=C^d mod n。

题目中设有两层RSA加密。

第一次加密是用公钥e=65537对明文flag加密，这一步是肯定要有的，但是我们不知道p和q具体是多少，求出φ(n)=(p-1)×(q-1)是很困难的，暴力破解1000多位的RSA花费时间不可估计，所以题目给了一些提示，这便是第二次加密的原因。

第二次加密是用公钥e=65537对第一次加密中的私钥p和q之和加密，加密的原理还是基本的RSA，不同的是虽然第二次加密用的新随机生成的私钥p2和q2，但是题目还额外给出了(p2+1)×(q2+1)这个信息，这便是突破口。

所以解题的方法就是递推回去，先解开第二层RSA加密，得到第一层加密中使用的私钥对之和p+q，再继续解第一层加密，最后得到结果flag。

①先解第二层加密👇

第二层加密给出了n2,e2,c2,(p2+1)×(q2+1)这四个参数，因为n2=p2×q2，简单推导我们可以得到

φ(n2)=(p2-1)×(q2-1)=p2×q2-p2-q2+1=2×p2×q2-(p2×q2+p2+q2+1)+2

根据扩展欧几里得算出公钥e=65537模φ(n2)的逆inv2，然后直接将c2和inv2模n2运算即可得到第二层加密的明文p+q的值。

②解第一层加密👇

第二层加密给出了n,e,c这三个参数，因为n=p×q，简单推导我们可以得到

φ(n)=(p-1)×(q-1)=p×q-p-q+1=p×q-(p+q)+1

根据扩展欧几里得算出公钥e=65537模φ(n)的逆inv，然后直接将c和inv模n运算即可得到第一层加密的明文flag的字节值。

最后的字节值别忘了使用long_to_bytes()转换成最后的明文flag。

代码示例👇

①对思路分析中的猜想进行验证测试👇

#coding:utf-8
#author:Mitchell
#date:12.24
from Crypto.Util.number import *

#欧几里得求最大公因子
def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

#扩展欧几里得求模逆
def exgcd(a, m):
    if gcd(a, m) != 1:
        return None
    u1,u2,u3 = 1, 0, a
    v1,v2,v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3#地板除
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

#模拟第一层加密
def ef():
    p=getPrime(512)
    q=getPrime(512)
    flag=b'Legends never die!'
    print('falg=',flag)
    m=bytes_to_long(flag)
    print('m=',m)
    e=65537
    n=p*q
    c=pow(m,e,n)
    return p,q,(n,e,c)  #

#模拟第二层加密
def epq(p,q):
    p2=getPrime(1024)
    q2=getPrime(1024)
    e2=65537
    m2=p+q
    print('m2=',m2)
    n2=p2*q2
    c2=pow(m2,e2,n2) 
    return (n2,e2,c2,(p2+1)*(q2+1)) #

#模拟参数生成，这里的p和q仅仅用于参数生成，按规则不能直接查看
p,q,A=ef()
B=epq(p,q)
#求得φ(n2)=(p2-1)×(q2-1)=p2×q2-p2-q2+1=2×p2×q2-(p2×q2+p2+q2+1)+2
phi2=B[0]*2-B[3]+2
#使用扩展欧几里得求出inv2
inv2=exgcd(B[1],phi2)
#第二层解密
m2=pow(B[2],inv2,B[0])
print('解密解得m2=',m2)
#求得φ(n)=(p-1)×(q-1)=p×q-p-q+1=p×q-(p+q)+1
phi=A[0]-m2+1
#使用扩展欧几里得求出inv
inv=exgcd(A[1],phi)
#第一层解密
m=pow(A[2],inv,A[0])
print('解密解得m=',m)
#转码得到flag
flag=long_to_bytes(m)
print('解密解得flag=',flag)

②实操破解题目中的RSA👇

#coding:utf-8
#author:Mitchell
#date:12.24
from Crypto.Util.number import *

'''已知有人写了如下的代码，并将生成的(n,e,c)以及(n2,e2,c2,(p2+1)*(q2+1))输出。
def ef():
    p=getPrime(512)
    q=getPrime(512)
    flag=open("flag","rb").read()
    m=bytes_to_long(flag)
    e=65537
    n=p*q
    c=pow(m,e,n)
    print(n,e,c)  #
    return p,q

def epq(p,q):
    p2=getPrime(1024)
    q2=getPrime(1024)
    e2=65537
    m2=p+q
    n2=p2*q2
    c2=pow(m2,e2,n2) 
    print(n2,e2,c2,(p2+1)*(q2+1)) #

p,q=ef()
epq(p,q)

输出(n,e,c)以及(n2,e2,c2,(p2+1)*(q2+1))如下：

(86902041785171683231305301154659574124170175717542478743469937094129588097899526472297338165763793395403138052107436307148655516237914989260641272558370267587581870375426597336633068656306063961150434589742092844368242428011721324737315708847899038491875643600715933822290329122093126146305056053635875427149L, 65537, 15833685544860151615528563318175057334854555807563811248911092184962045410721043935895279999715546874344448072757248024629816018687138160349497178202841685747385455984597261139196670787723191129190281464722284764818569442853999503305719960273532581788705319675785365330814771611391805600982635624166616994909L)

(18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828433745751900636977114625384201443358493405946175157229330447527380345317933922535718700042422977893867943656666930789561406630888405895439054817890293649823406983304364531032464229623788486039136673884818993067818472490283937605836580590843487927803181532325018537076264511576862025094690559279649143498659102849L, 
65537, 
7392251042794448813724942265095985628606500546061544026052413736090062985580390082556940969813307099293888028876436850564855740297176392396726998769680589219160575972891500463789856128741737806143813567755324525667951325489807002065570746854557547784519649141813876707420713784143969266692484619922991587339418980913573323306950701125825931923149350170489304772562424051072424741158162269063304635895188390600892069271483630208193319815348033784877031408074730563809389105637498825225265591866481815230255385046830196748192233124781928655809322769875744414705189416861877961926362356094198048709542228727393696757158L, 
18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828434020648157035533967661393926860975983001244775722594600595802713222548261077015534360904269663877978505992018966625264663179236777522008665977063509158288897299644184441313228368572324485490486359818154230942787018240908451883098571389138398322839231059197174670650732257722735400365023996558029601185819826736L)

请编写代码，求出flag。'''

#欧几里得求最大公因子
def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

#扩展欧几里得求模逆
def exgcd(a, m):
    if gcd(a, m) != 1:
        return None
    u1,u2,u3 = 1, 0, a
    v1,v2,v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3#地板除
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

A=(86902041785171683231305301154659574124170175717542478743469937094129588097899526472297338165763793395403138052107436307148655516237914989260641272558370267587581870375426597336633068656306063961150434589742092844368242428011721324737315708847899038491875643600715933822290329122093126146305056053635875427149, 65537, 15833685544860151615528563318175057334854555807563811248911092184962045410721043935895279999715546874344448072757248024629816018687138160349497178202841685747385455984597261139196670787723191129190281464722284764818569442853999503305719960273532581788705319675785365330814771611391805600982635624166616994909)

B=(18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828433745751900636977114625384201443358493405946175157229330447527380345317933922535718700042422977893867943656666930789561406630888405895439054817890293649823406983304364531032464229623788486039136673884818993067818472490283937605836580590843487927803181532325018537076264511576862025094690559279649143498659102849, 
65537, 
7392251042794448813724942265095985628606500546061544026052413736090062985580390082556940969813307099293888028876436850564855740297176392396726998769680589219160575972891500463789856128741737806143813567755324525667951325489807002065570746854557547784519649141813876707420713784143969266692484619922991587339418980913573323306950701125825931923149350170489304772562424051072424741158162269063304635895188390600892069271483630208193319815348033784877031408074730563809389105637498825225265591866481815230255385046830196748192233124781928655809322769875744414705189416861877961926362356094198048709542228727393696757158, 
18591274039015146371355461783271676729436253989312203484465267365829253730222536917260636899143825565341750487371058728119621305795504534209590790135844600724302582139316981344931079461283380928221091934542959757790517904211220170283310587231962911318192160954877212603169707693638590690557518269614342828434020648157035533967661393926860975983001244775722594600595802713222548261077015534360904269663877978505992018966625264663179236777522008665977063509158288897299644184441313228368572324485490486359818154230942787018240908451883098571389138398322839231059197174670650732257722735400365023996558029601185819826736)

#求得φ(n2)=(p2-1)×(q2-1)=p2×q2-p2-q2+1=2×p2×q2-(p2×q2+p2+q2+1)+2
phi2=B[0]*2-B[3]+2
#使用扩展欧几里得求出inv2
inv2=exgcd(B[1],phi2)
#第二层解密
m2=pow(B[2],inv2,B[0])
print('解密解得m2=',m2)
#求得φ(n)=(p-1)×(q-1)=p×q-p-q+1=p×q-(p+q)+1
phi=A[0]-m2+1
#使用扩展欧几里得求出inv
inv=exgcd(A[1],phi)
#第一层解密
m=pow(A[2],inv,A[0])
print('解密解得m=',m)
#转码得到flag
flag=long_to_bytes(m)
print('解密解得flag=',flag)

运行效果👇

①测试结果👇

②实操效果👇

最终的flag为flag{3101231231231231c421cccccc}，这个熟悉的格式，爷青回！