学了RSA也有这么久了，也遇到了不少类型的题，有的还是不够熟悉，经常去找之前的题解，所以在这进行一个总结，仅供自己复习。
基础型
e、n、c、p、q都直接给了，或者给了e、n、c，且n能直接分解（用在线工具[factordb]( (factordb.com))，或者用yafu工具），yafu使用方法：
1、打开cmd
2、输入yafu-x64进入命令行
3、factor(n)进行分解
公共n求最大公约数
给了两组e、n、c，且e相同，可通过欧几里得算法求两个n的最大公因数p，任取一个n求q即可。例题：
e = 65537
n = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815
e = 65537
n = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062
题解：
from gmpy2 import *
from Crypto.Util.number import *
e = 65537
N1 = ...
c1 = ...
N2 = ...
c2 = ...
p = gcd(N1,N2)
q = N1//p
phi_n = (p-1)*(q-1)
d = invert(e,phi_n)
m = powmod(c1,d,N1)
print(long_to_bytes(m))
共模攻击
辨别：在加密过程中使用了相同的模n。即：
$c1 \equiv m^{e1}modn$
$c2 \equiv m^{e2}modn$
此时，若gcd(e1,e2)==1，即满足e1和e2互质（这是条件），则根据扩展欧几里德算法，存在整数x，y使得 gcd(a,b) = ax + by = 1，x，y一正一负。例题：
e = 65537
n = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815
e = 65537
n = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062
上脚本：
from gmpy2 import *
from Crypto.Util.number import *
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
e1 = 797
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849
s = gcdext(e1, e2) # 扩展欧几里得算法，得到x，y，即ax+by=gcd(a,b)
m1 = powmod(c1, s[1], n)
m2 = powmod(c2, s[2], n)
m = (m1 * m2) % n
print(long_to_bytes(m))
当e1、e2不互质的时候：
例题：
from Crypto.Util.number import *
import flag
m = bytes_to_long(flag)
e1 = 48962
e2 = 66178
n = 18860369147161365317340760162866306836686697680846811944837525142094856930255357992224861932502678887338047932416586264487563280104455484470518505575982638957066232366620444129592623580448780279399782392083991547954590556920717209212482445902845072979824531295227122087005328625492707047115278826342706540914391041033384618302388052687378992551465208371915035810094231252839812407943878738609286676636774736392475263370142941833197641681827222571447640581231321051378079977425216352080089055565879331328870704795555436373276587131799610797673278730556710522033793163582006298599248443648391365945739803799759208412011
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print(c1)
print(c2)
'''
8613537634119817185155272069724215821261502753897680368332473105731276727035745443592819454806477981283715550315851312831340854217517903975094325165715987314802899358584294660215757240879510853658444661114490264596301862506878022135569410048415005252178514287234533868840630161183869939991555602468487578733675434463064488885921541342226521120909235223498544415343888143224658487428920236913875537187557430887594101112657770131698810387032315312800619926314949944831347186397402097955887891854519378386696517453058151877155140010862009372094440887174497300023488022072080735029791984039108005731524158286249846599020
14637407053483452510936547930656437891459748958635038831745659935591080935826794189726839533344174265143534935674164484645261024138431001051253620877911980801362391581222598461660768452830991217119032510285272732906508998826596416696378913979520753807777557025929961891891578412021310298729664588391181354934234148879115134784075492408092902530343308032791699592672083441783844865546262990424730354475384345284755603167482346607091994025187669205551777555680600617237729519664050016268626418960329977209535510624693641114431858780992939833419462877347678568926750888288245604118695171802250604433391748818746492871808
'''
print(gcd(e1,e2))==2
发现e1、e2有公因数2，因为指数比较小，参考低加密指数攻击，只需要在（m1*m2）上开2次方就行，代码如下：
from gmpy2 import *
from Crypto.Util.number import *
n = 18860369147161365317340760162866306836686697680846811944837525142094856930255357992224861932502678887338047932416586264487563280104455484470518505575982638957066232366620444129592623580448780279399782392083991547954590556920717209212482445902845072979824531295227122087005328625492707047115278826342706540914391041033384618302388052687378992551465208371915035810094231252839812407943878738609286676636774736392475263370142941833197641681827222571447640581231321051378079977425216352080089055565879331328870704795555436373276587131799610797673278730556710522033793163582006298599248443648391365945739803799759208412011
e1 = 48962
c1 = 8613537634119817185155272069724215821261502753897680368332473105731276727035745443592819454806477981283715550315851312831340854217517903975094325165715987314802899358584294660215757240879510853658444661114490264596301862506878022135569410048415005252178514287234533868840630161183869939991555602468487578733675434463064488885921541342226521120909235223498544415343888143224658487428920236913875537187557430887594101112657770131698810387032315312800619926314949944831347186397402097955887891854519378386696517453058151877155140010862009372094440887174497300023488022072080735029791984039108005731524158286249846599020
e2 = 66178
c2 = 14637407053483452510936547930656437891459748958635038831745659935591080935826794189726839533344174265143534935674164484645261024138431001051253620877911980801362391581222598461660768452830991217119032510285272732906508998826596416696378913979520753807777557025929961891891578412021310298729664588391181354934234148879115134784075492408092902530343308032791699592672083441783844865546262990424730354475384345284755603167482346607091994025187669205551777555680600617237729519664050016268626418960329977209535510624693641114431858780992939833419462877347678568926750888288245604118695171802250604433391748818746492871808
s = gcdext(e1, e2)
m1 = pow(c1, s[1], n)
m2 = pow(c2, s[2], n)
print(gcd(e1,e2))
m = (m1 * m2) % n
m = iroot(m,2)[0]
print(long_to_bytes(m))
低加密指数攻击
顾名思义，低加密指数是说加密指数e比较小。一般满足e = 3
第一种情况，若明文比较小，满足$m^{e}<n$，那么，$c\equiv m^{e}$ mod n = $m^{e}$，对c开e(3)次方即为明文m。
第二种情况，若明文同样比较小，但$m^{e}>n$，且只是比n稍大，此时我们可以进行爆破。
因为$c=m^{e}+kn$，即$m^{e}=c+kn$，若c + kn能开三次方，那明文也就出来了。
第二种情况脚本：
e = 3
n1 = ***
c1 = ***
k = 0
while 1:
res = iroot(k*n1+c1,e)
if(res[1] == True):
m1 = res[0]
break
k += 1
低加密指数广播攻击
因为还没有碰到过这种类型的题，所以借鉴下大佬的思路和脚本。
同样e很小，一般取e=3（这里的3代表了给出的c和n的组数）。若使用相同的加密指数给一个接收者群发送相同的信息，那么可以进行广播攻击得到明文。
$c1\equiv m^emod$ n1
$c2\equiv m^emod$ n2
$c3\equiv m^emod$ n3
由中国剩余定理：
设n1，n2，n3是两两互素的正整数，M = $n1 \cdot n2 \cdot n3$，则$M_i=\frac {M}{n_i}$，
此时，对于同余式$m^e \equiv c_i \space mod \space n_i$，有唯一解：
$m^e \equiv c_1 \cdot M_1 \cdot y_1 + c_2 \cdot M_2 \cdot y_2 + c_3 \cdot M_3 \cdot y_3 \space mod \space M$
脚本：
from gmpy2 import*
from Crypto.Util.number import *
n1=...
n2=...
n3=...
c1=...
c2=...
c3=...
e=3
n =[n1,n2,n3]
c =[c1,c2,c3]
def CRT(n,c):
sum = 0
N = reduce(lambda x,y:x*y,n) # ni 的乘积,N=n1*n2*n3
for n_i, a_i in zip(n,c): # zip()将对象打包成元组
N_i = N // n_i #Mi=M/ni
sum += c_i*N_i*invert(N_i,n_i) #sum=C1M1y1+C2M2y2+C3M3y3
return sum % N
x = CRT(n,c)
m = iroot(x,e)[0]
print(long_to_bytes(m))
低解密指数攻击
参考之前写的Wiener-attack
dp泄露
前提条件$dp\equiv d$ mod (p-1)
推导过程：
在$dp\equiv d$ mod (p-1)两边同乘上e，得到$dp\ast e \equiv ed mod (p-1)$ ，
变形得$ed\equiv dp\ast e mod (p-1) = dp\ast e+k1(p-1)$，又已知$ed \equiv1$ mod $\phi(n)$，
故$dp\ast e+k1(p-1)\equiv1 mod \phi(n) = 1 + k2(p-1)\ast (q-1)$，
再次变形得$dp\ast e = 1 + k2(p-1)\ast (q-1)-k1(p-1)$，
提取公因式(p-1)得，$dp\ast e = 1+[k2(q-1)-k1]\ast (p-1)$
因为dp是比p小的，故dp < p-1。再结合上面的等式可以知道，0 < [k2(q-1) - k1] * (p-1) < e
爆破出p-1，使p能被n整除
脚本如下：
from Crypto.Util.number import *
import gmpy2
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_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(long_to_bytes(m))
给出dp、dq
$dp = d \space mod \space (p-1)$
$dq = d \space mod \space (q-1)$
解题脚本：
import gmpy2
import libnum
def decrypt(dp,dq,p,q,c):
InvQ = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
m = (((mp-mq)*InvQ) % p)*q+mq
print(libnum.n2s(int(m)).decode())
p= ...
q= ...
c= ...
dq= ...
dp= ...
decrypt(dp,dq,p,q,c)
e与$\phi(n)$不互素
例题：
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
print('p=',p)
print('q=',q)
n=p*q
e=65537
c=pow(m,e,n)
print('c=',c)
#p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
#q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
#c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595
用基础方法解不出来，原因是e与$\phi(n)$不互素，又$\phi(n) = (p-1) \cdot (q-1)$，求$gcd(e,(p-1))和gcd(e,(q-1))$，发现$e与p-1$互素。把$e \cdot d = 1 mod (p-1)(q-1)$和$m = c ^ d mod p \cdot q$拆开，利用含p的部分求解即可：
from gmpy2 import *
from Crypto.Util.number import *
e = 65537
p = 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q = 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c = 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595
n = p*q
phi_n = (p-1)*(q-1)
print(gcd(e,q-1))
d = invert(e,(p-1))
m = pow(c,d,p)
print(long_to_bytes(m))
已知n、e、d求p、q
import random
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n, e, d):
p = 1
q = 1
while p == 1 and q == 1:
k = d * e - 1
g = random.randint(0, n)
while p == 1 and q == 1 and k % 2 == 0:
k //= 2
y = pow(g, k, n)
if y != 1 and gcd(y - 1, n) > 1:
p = gcd(y - 1, n)
q = n // p
return p, q
算法过程：
- 设 k = de – 1。如果 k 为奇数，则转到步骤 4。
- 将 k 写为 k = 2 t r，其中 r 是除以 k 的最大奇整数，t ≥ 1。或者更简单地说，将 k 反复除以 2，直到得到一个奇数。
- 对于 i = 1 到 100 执行以下操作：
- 生成一个范围为 [0， n−1] 的随机整数 g。
- 设 y = gr mod n
- 如果 y = 1 或 y = n – 1，则转到步骤 3.1（即重复此循环）。
- 对于 j = 1 到 t – 1 执行：
- 设 x = y2 mod n
- 如果 x = 1，请转到（外部）步骤 5。
- 如果 x = n – 1，请转到步骤 3.1。
- 设 y = x。
- 设 x = y2 mod n
- 如果 x = 1，请转到（外部）步骤 5。
- 继续
- 输出“未找到质因数”并停止。
- 设 p = GCD（y – 1， n），设 q = n/p
- 输出（p，q）作为主要因子。
参考：c# - 根据私有指数 （d）、公共指数 （e） 和模数 （n） 计算素数 p 和 q - 堆栈溢出 (stackoverflow.com)
n是p的r次方
给出$n = p^r$，此时$\phi(n) = p^r - p^{r-1}$
可以根据定义推导：
$\phi(n)等于小于n的自然数中与n互质的数的个数，$
$对于p^r，质因数只有p，则不互质数依次为：p、2p、…、p^{r-1}\cdot p，共有p^{r-1}个$
故$\phi(n) = p^r - p^{r-1}$
待补充。。。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com