RSA加密常见题型总结

• 对于基础的RSA加密，我们只需要了解加密和解密过程，而不需要了解RSA加密这个理论是如何推导出来的（当然如果有数论基础的话可以这么干）。
• 先对RSA加密过程进行简单的介绍，基础题型基本上就是想办法求p或q，从而把n分解出来，这样解密就可以一葫芦画瓢了。

rsa加密原理

• 明文为m，密文为c

1. 找两个质数p、q
2. 计算n=p*q
3. 计算n的欧拉函数φ（n）=（p-1）*（q-1）
4. 公钥e，要求1＜e＜φ（n），且e为整数，还需要e、φ（n）互质
5. 确定私钥d，d要满足e*d除以φ（n）余数为1

• 加密

$$密文c，c=m^e(mod n)$$

• 解密

$$明文m，m=c^d(modn)$$

解密rsa关键

• 公开传播的是：n、e、c

• 解密要用到：n、d、c

• 所以rsa解密的关键就是要得到私钥d

• 要得到d，需要通过e*d除以φ（n）余数为1

• 在求d之前就需要求φ（n）

• 而φ（n）=（p-1）*（q-1）

• 所以解密rsa的关键需要求p、q

• n = p*q，可以通过分解质因素来对p、q进行爆破（当p、q比较小或者p、q比较接近的时候是可以分解的）

• 了解RSA加密和解密的过程后，接下来就对CTF的RSA基础题（差不多已经成为模版题了）进行归纳

常用结论

• 以下结论是在做题中比较经常用到的关于数论的一些结论。

RSA简单题型

直接解密

可分解n

泄露p、q关系式

低指数加密

共享素数

共享素数_题型总结

• 参考博客：https://mp.weixin.qq.com/s/F6isyS6omxCVLriFGAjWgg

• 这个也算是一个比较基础的题型，在RSA中，一个明文m分别被n1和n2进行RSA加密得到c1和c2，这两个加密e都是一样的。而n1和n2的生成过程和关系如下。（即，在n1和n2中有一个共同的素数p，可以表示为(n1,n2)=p）

• 在题目中一般都会给出n1和n2的值，当n1和n2已知，我们就可以使用欧几里得算法（也就是辗转相除法）将n1和n2的最大公因数求出来(在这种情况下n1和n2的最大公因数为p)

• 知道了p的值，我们就可以求得q1=n1//p、q2=n2//p

from Crypto.Util.number import *
m=bytes_to_long(b'xxxxxx')
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)

• 在这种情况下就可以使用python中gmpy2库的gcd函数求的p，具体语法如下：

import gmpy2
n1 = xxxxx
n2 = xxxxx
p = gmpy2.gcd(n1,n2) # 使用欧几里得算法求最大公因数

• 基本上就是这样的一个总结，关于gcd的实现对于数学计算请参考数论书，对于编程算法请参考算法书。这里只是对gcd进行简单使用。
• 如果单考gcd是非常基础的，这时共享素数的题目就会和其他知识点合起来一起考。

共享素数1

• 题目来源：[FSCTF 2023]Do you know gcd? | NSSCTF
• 题目附件如下：[FSCTF 2023]Do you know gcd?

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

m1=bytes_to_long(flag[:16])
m2=bytes_to_long(flag[16:])
p=getPrime(1024)
q1=getPrime(1024)
q2=getPrime(1024)
n1=p*q1
n2=p*q2
e=65537
c1=pow(m1,e,n1)
c2=pow(m2,e,n2)
print("n1=",n1)
print("n2=",n2)
print("c1=",c1)
print("c2=",c2)
'''
n1= 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857
n2= 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577
c1= 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179
c2= 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621
'''

• 这题就是比较典型的共享素数的题型，这边n1=p*q1和n2=p*q2，这样就有gcd(n1,n2)=p，所以q1=n1//p、q2=n2//p，之后就是正常的RSA解密了。

• exp如下:

import libnum
import gmpy2
n1= 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857
n2= 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577
c1= 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179
c2= 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621
e= 65537
p = gmpy2.gcd(n1,n2)
q1 = n1//p
q2 = n2//p
phi1= (p-1)*(q1-1)
phi2= (p-1)*(q2-1)
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
m1 = libnum.n2s(int(m1))
m2 = libnum.n2s(int(m2))
flag = m1+m2
print(flag)
# FSCTF{0hN0_Y0u_f1nd_th3_gcd!}

求phi(n)

RSA中等题型

RSA与同余

e与phi(n)不互素

一般情况

*特殊情况–rabin算法

• 当e=2的时候，开方的方法就失效了，这时需要使用一种特殊的算法来对结果进行修正，这就是rabin算法

最小公因数和最大公倍数

共模攻击

• 参考：b站up风二西

• 最近学了一下共模攻击，共模攻击还是比较简单，也是比较模版的。

• 共模攻击是在特定条件下产生的：

  • 一个用户发送了两条消息，这两条消息的分别为m1和m2
  • 这两个消息用了同一个n，并且使用了e1和e2数作为指数
  • 通过计算得到c1 = m**e1 mod (n)、c2 = m**e2 mod (n)
  • 这种题型就是RSA的共模攻击的题型

• 一般题目就会给出如下信息：

"""
加密的密文c1、c2
加密的指数e1、e2
模数n
下面给出一个例子
"""
from Crypto.Util.number import *
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = getPrime(16)
e2 = getPrime(16)
p = getPrime(512)
q = getPrime(512)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)

• 该题就是主要就是gcd(e1,e2)的三种情况，分别对应着共模攻击1、2、3：
  • 第一种情况，也是最简单的情况：gcd(e1,e2)=1。
  • 第二种情况，稍微复杂一点：gcd(e1,e2)≠1
  • 第三种情况，也是最复杂的一种情况：gcd(e1,e2)非常大

共模攻击1

• 这个是最基本的题型，现在就给出一个例题

from Crypto.Util.number import *
import gmpy2
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = getPrime(16)
e2 = getPrime(16)
p = getPrime(512)
q = getPrime(512)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
"""
e1 = 35603
e2 = 53849
n = 65844835114811311147300780798656143825222359960203887804404336766671754915238143105361685751338600606205234241717554977556014391502151140599030174376626752597123335946780943028787393505875282845874194789937021373169837205020116739523929406808658690735666690634468817779530981170477446002242151051007841320499
c1 = 3652946455096596922421828601712210382877573893656617028922252423601007198550547136141125408399184017530737069617361752419721283095525888153494847215557513043342658287550672860273427773994030007220020707376113461073627581510167395737557600247794396378096347654764650186631167120330986770904279007941507562441
c2 = 16647423266182678960959947505427682046836995492595463854876112200789807987236540245845356081678424736418596164492737256401436506552449871347507391421521217966841767869954716106409257585276208800895615701515817235738827206889142921421410764420295206520038281264810899421047195121134469562492729516621808418924
gcd(e1,e2) = 1
"""

• 先给出推导过程要用到的数论相关的定理

相关定理

• 首先是著名的裴蜀定理

$$\begin{array}{l} 若(a,b)=d,则存在s,t∈Z有as+bt=d.\\ \end{array}$$

• 还有就是同余的基本运算，这里就不写出了。

• 接下来推导一下解密过程：

推导过程

$$\begin{array}{l} 已知: \\ c_1=m^{e_1}~~mod~(n)\\ c_2=m^{e_2}~~mod~(n)\\ gcd(e_1,e_2)=1\\ e1,e2\\ n \end{array}$$

• 接下来根据已知和定理推导这个攻击过程：

$$\begin{array}{l} 因为存在(e_1,e_2)=1\\ 所以由裴蜀定理得存在s,t∈Z有e_1s+e_2t=1\\ 所以\\ c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)\\ c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)\\ 所以\\ c_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}~~mod(n)\\ 可以得到\\ c_1^{s}c_2^{t} = m^{e_1s+e_2t}~~mod(n)\\ 最后得到\\ c_1^{s}c_2^{t} = m~~mod(n) \end{array}$$

• 现在就将问题转换为求s、t，这里我们可以使用拓展欧几里得算法进行计算。在Python中的gmpy2库有一个函数gcdext(a1,a2)这个函数可以用来计算s、t，接下来就介绍这个函数的使用
  • 这个函数传入的是两个参数：e1、e2
  • 这个函数内部实现的就是拓展欧几里得算法，这个算法的具体过程不多介绍
  • 这个函数返回值有三个：第一个返回值返回的是gcd(e1,e2)的值，第二个返回值返回的是s，第三个返回值返回的是t

import gmpy2
e1 = 43019
e2 = 54011
gmpy2.gcdext(e1,e2)
mpz(1), mpz(23050), mpz(-18359)

• 现在直接给出例题的exp：

import libnum
import gmpy2
e1 = 35603
e2 = 53849
n = 65844835114811311147300780798656143825222359960203887804404336766671754915238143105361685751338600606205234241717554977556014391502151140599030174376626752597123335946780943028787393505875282845874194789937021373169837205020116739523929406808658690735666690634468817779530981170477446002242151051007841320499
c1 = 3652946455096596922421828601712210382877573893656617028922252423601007198550547136141125408399184017530737069617361752419721283095525888153494847215557513043342658287550672860273427773994030007220020707376113461073627581510167395737557600247794396378096347654764650186631167120330986770904279007941507562441
c2 = 16647423266182678960959947505427682046836995492595463854876112200789807987236540245845356081678424736418596164492737256401436506552449871347507391421521217966841767869954716106409257585276208800895615701515817235738827206889142921421410764420295206520038281264810899421047195121134469562492729516621808418924
_, s1, s2 = gmpy2.gcdext(e1,e2)
m = (pow(c1,s1,n)*pow(c2,s2,n))%n
print(libnum.n2s(int(m)))
# flag{12025e72-7f21-4cf1-b779-7d343e6c28e8}

共模攻击2

• 现在来介绍一下当gcd(e1,e2)≠1的情况，这种情况仍然要先使用gmpy2.gcdext(e1,e2)，推导过程如共模攻击1。
• 接下来给出一个例题：

from Crypto.Util.number import *
import gmpy2
import random
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = random.randint(2**9,2**10)
e2 = random.randint(2**9,2**10)
p = getPrime(2048)
q = getPrime(2048)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
"""
e1 = 776
e2 = 660
n = 83685592643015631285511109663325122006760075584070237854675562002076227876018375942188686437412417554344776894370097201033426874441336708646624883445380146070344328421967347863076320208287674554891010711418786407828605518837809737258170089927317008100377276660831635304144479856615378434494150317241691405699
c1 = 36299289915782897291165052853638301870957152722428510897342204593316850303542079849676568285857303159762709605563489283030869099273611779877254853356688986853696443779220783593658624342473581938754872289713670062547043089816659273356194704277435964456461072332286114555658456270426215294643175591217906091755
c2 = 49943255108816727418959338909424707941215549374121313411779599086453527489023566862613934533928451896342569719440495017955832687024686166587752169810336138451439400664572517556546110360539667183745627145127591816783932939746214213153708059533454010448797476344617536862513447513045215949581066286489331011975
gcd(e1,e2) = 4
"""

推导过程

$$\begin{array}{l} 已知: \\ c_1=m^{e_1}~~mod~(n)\\ c_2=m^{e_2}~~mod~(n)\\ gcd(e_1,e_2)=x\\ e1,e2\\ n \end{array}$$

$$\begin{array}{l} 因为存在(e_1,e_2)=1\\ 所以由裴蜀定理得存在s,t∈Z有e_1s+e_2t=x\\ 所以\\ c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)\\ c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)\\ 所以\\ c_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}~~mod(n)\\ 可以得到\\ c_1^{s}c_2^{t} = m^{e_1s+e_2t}~~mod(n)\\ 最后得到\\ c_1^{s}c_2^{t} = m^{x}~~mod(n)\\ 这时再由于x比较小，所以m^x肯定会比n小，也就简化问题为低指数加密直接开方就行 \end{array}$$

共模攻击3

• 对于共模攻击第二种情况，是一种特殊情况，常常gcd(e1,e2)≠1且gcd(e1,e2)=x，其中x的值非常大。这时第二种特殊情况的解密方式就失效了，这样就需要其他方法进行解密。
• 当时作为题目，如果向前两题那样给e1、e2、n1、c1、c2意义不大，这就给出一个例题来解释一下为什么意义不大。
• 例题：

from Crypto.Util.number import *
import gmpy2
import random
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = getPrime(128)
e2 = getPrime(128)*e1
p = getPrime(512)
q = getPrime(512)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("p =",p)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))

"""
p = 12354667105956633645505885082487144682190452234798696744645997387099207576568782658631934442079562902043942456124262934833548127310904873471712197692223151
e1 = 270516821232137091700320423668458210961
e2 = 74165178148542517862331801316190749703819740833698961718616221944701759350097
n = 124362644099775589902895946839476348022174413338453678145721401915709742155330759419413072770801553367457435578733663875712725966971469138012348937210118369098587641022291949571805775053379343137964405130964761576037870442836679696951637890160763897515307124266679985615100850012111585355232442117821511116901
c1 = 5323866568296193592597888660757755576275196057389707734801436861257713948360702550013617233647471845666237618134195707677924589283657252990214667642119909872937843516583639340445395869497166850947229435636274414115414211682655409715959874952450741948274955268734077411469869317050217707925192320235463094105
c2 = 104238473081393587128152794405440554852627276869818642357715651393772747872001157068855372215013597488429196715877035300272216480821841080478521897746953706089933552869973864682399422752122505619328890632827768730523178351333183920997307503412724769094244190744010864067403009477588562252732503656561124542489
gcd(e1,e2) = 270516821232137091700320423668458210961
"""

• 这题使用m = (pow(c1,s1,n)*pow(c2,s2,n))%n求得后就会出现新的e，这样就相当于另一个RSA加密。如果已知p的话，就可以直接解密了，但是我们已知p还用共模攻击干嘛。所以这题意义不大。

import libnum
import gmpy2
p = 12354667105956633645505885082487144682190452234798696744645997387099207576568782658631934442079562902043942456124262934833548127310904873471712197692223151
e1 = 270516821232137091700320423668458210961
e2 = 74165178148542517862331801316190749703819740833698961718616221944701759350097
n = 124362644099775589902895946839476348022174413338453678145721401915709742155330759419413072770801553367457435578733663875712725966971469138012348937210118369098587641022291949571805775053379343137964405130964761576037870442836679696951637890160763897515307124266679985615100850012111585355232442117821511116901
c1 = 5323866568296193592597888660757755576275196057389707734801436861257713948360702550013617233647471845666237618134195707677924589283657252990214667642119909872937843516583639340445395869497166850947229435636274414115414211682655409715959874952450741948274955268734077411469869317050217707925192320235463094105
c2 = 104238473081393587128152794405440554852627276869818642357715651393772747872001157068855372215013597488429196715877035300272216480821841080478521897746953706089933552869973864682399422752122505619328890632827768730523178351333183920997307503412724769094244190744010864067403009477588562252732503656561124542489
#gcd(e1,e2) = 270516821232137091700320423668458210961
e, s1, s2 = gmpy2.gcdext(e1,e2)
q = n//p
m = (pow(c1,s1,n)*pow(c2,s2,n))%n
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(m,d,n)
print(libnum.n2s(int(m)))
# b'flag{4053c1a4-c301-4e23-b920-28b017ba38df}'

• 接下来介绍另一题，另一题才是共模攻击3的题型。

from Crypto.Util.number import *
import gmpy2
import random
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
k1 = random.randint(2**128,2**256)
k2 = random.randint(2**128,2**256)
e1 = getPrime(128)*k1
e2 = getPrime(128)*k1*k2
e3 = getPrime(128)*k2
p = getPrime(1024)
q = getPrime(1024)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
c3 = pow(m,e3,n)
print("e1 =",e1)
print("e2 =",e2)
print("e3 =",e3)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("c3 =",c3)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
print("gcd(e2,e3) = ",gmpy2.gcd(e2,e3))
"""
e1 = 6839979093843017245130935971073531650625865408597324093158075653007572029459535748591107780971041110617821327885728
e2 = 527282383778630558435877705949699484729936503257091129495571879289998217841325217564810314237039659729265596452756258253436101100968118657130954223308875205257774585781949600635959096231751360
e3 = 20987998930730242130690830835028138615595244455228017878066112490327400892650229366898248406466316235857196958485710
n = 22175144708990630853036480868376123403731448276285717131186187150462023495494103565746117568235683365313517827941106620902013918484064641114476913481110938950785308733160550905735102713320438455824065792338146147847335388226116646541800245464845211085540907602598972170387771602880693683773805550988596358558621125283407314509610950378661338714027095643635739361829648482049383174885258194773716516785232715071895492339469667922183918303613284066664177945669438336799055529602328784963091965710713100236033780379337460945498971432359098326842627948461349746702776166953869600658895170340420434234372122272110975044659
c1 = 11426478179683336827224880779953157546776076551240828268809350458296893628522712784864907995111968644902442693072364448063747658422225255036189101385357784689296259496649527761401899948136054211133883265341970543967599869525260654979500412480663418057379308458996911392485335767582507518973447401423943878293895212638047157663802239344638641314156758830964491691323026524366328874683360987516802872498983112781643154651435374108641997212467699796213730738052002284134749351805453079045833498972827333585113428885026516509660161906337450878179654072288419436265826131479983858828205102056301019221745568319757344882310
c2 = 924553363795544361249557963373014280364009962681904215742379062140845462422058966956557303658832168491456051793505960008265313560082631349096509445336008684455437098964906094258030833746463869703797105150834953261601859026067804458980569864595116130499800793859913206222086000196754618550748639846744131641000960761007475985837366717289369284418559314663298108941564271462247365885229310605727917343982395106384199224643917254074484080305027204503813125672333323007771938062630610901748714884555438154614828690121207720526744717299121320271203097954739219600201683737833195114592138439396587112769674492174781048345
c3 = 14746267922953594508934987983405936746727004380259552828471117039223733948341026916910718225093159503573963075699179842175533457878937869802023486477372942785557938018982551170721496415115172951210353253311347031831419025904122683204153082041761968643487702640595950727384113933573702782931552657234931764298271273287655619903274377134978785223623709621560907111004144880046847332195005770181319177034333945769165118402546185793312611428185399654124299299022380187589974664553807713456469247091344949181479956722950070165387894955829314074403945814066771174510119236751891447097319232129235383321537697205679053840336
gcd(e1,e2) = 29540346448235016595457107953809410509141879299370840061983373145010008818272
gcd(e2,e3) =  68493250011952459219512675036017846580344175598507893778164361048080116129970
"""

• 接下来对该题型进行推导，其实就是使用两次共模攻击。

推导过程

$$\begin{array}{l} 由于gcd(e_1,e_2)=x1\\ 由于gcd(e_2,e_3)=x2\\ 由裴蜀定理得存在s11,s12∈Z有e_1s11+e_2s12=x1\\ 由裴蜀定理得存在s21,s22∈Z有e_1s21+e_2s22=x2\\ 所以对c_1、c_2进行共模攻击、对c_2、c_3进行共模攻击\\ 会得到\\ m_1 = m^{x_1}~~mod(n)\\ m_2 = m^{x_2}~~mod(n)\\ 同时有gcd(x_1,x_2)=x\\ 这时我们再对m_1、m_2进行共模攻击即可得到\\ m = m^x ~~mod(n)\\ 这时m^x比较小,这样就可以直接开方了 \end{array}$$

• exp如下：

import libnum
import gmpy2
e1 = 6839979093843017245130935971073531650625865408597324093158075653007572029459535748591107780971041110617821327885728
e2 = 527282383778630558435877705949699484729936503257091129495571879289998217841325217564810314237039659729265596452756258253436101100968118657130954223308875205257774585781949600635959096231751360
e3 = 20987998930730242130690830835028138615595244455228017878066112490327400892650229366898248406466316235857196958485710
n = 22175144708990630853036480868376123403731448276285717131186187150462023495494103565746117568235683365313517827941106620902013918484064641114476913481110938950785308733160550905735102713320438455824065792338146147847335388226116646541800245464845211085540907602598972170387771602880693683773805550988596358558621125283407314509610950378661338714027095643635739361829648482049383174885258194773716516785232715071895492339469667922183918303613284066664177945669438336799055529602328784963091965710713100236033780379337460945498971432359098326842627948461349746702776166953869600658895170340420434234372122272110975044659
c1 = 11426478179683336827224880779953157546776076551240828268809350458296893628522712784864907995111968644902442693072364448063747658422225255036189101385357784689296259496649527761401899948136054211133883265341970543967599869525260654979500412480663418057379308458996911392485335767582507518973447401423943878293895212638047157663802239344638641314156758830964491691323026524366328874683360987516802872498983112781643154651435374108641997212467699796213730738052002284134749351805453079045833498972827333585113428885026516509660161906337450878179654072288419436265826131479983858828205102056301019221745568319757344882310
c2 = 924553363795544361249557963373014280364009962681904215742379062140845462422058966956557303658832168491456051793505960008265313560082631349096509445336008684455437098964906094258030833746463869703797105150834953261601859026067804458980569864595116130499800793859913206222086000196754618550748639846744131641000960761007475985837366717289369284418559314663298108941564271462247365885229310605727917343982395106384199224643917254074484080305027204503813125672333323007771938062630610901748714884555438154614828690121207720526744717299121320271203097954739219600201683737833195114592138439396587112769674492174781048345
c3 = 14746267922953594508934987983405936746727004380259552828471117039223733948341026916910718225093159503573963075699179842175533457878937869802023486477372942785557938018982551170721496415115172951210353253311347031831419025904122683204153082041761968643487702640595950727384113933573702782931552657234931764298271273287655619903274377134978785223623709621560907111004144880046847332195005770181319177034333945769165118402546185793312611428185399654124299299022380187589974664553807713456469247091344949181479956722950070165387894955829314074403945814066771174510119236751891447097319232129235383321537697205679053840336
#gcd(e1,e2) = 29540346448235016595457107953809410509141879299370840061983373145010008818272
#gcd(e2,e3) =  68493250011952459219512675036017846580344175598507893778164361048080116129970
x1,s11,s12 = gmpy2.gcdext(e1,e2)
x2,s21,s22 = gmpy2.gcdext(e2,e3)
print(x1)
print(x2)
m1 = (pow(c1,s11,n)*pow(c2,s12,n))%n
m2 = (pow(c2,s21,n)*pow(c3,s22,n))%n
print(m1,m2)
x, s31,s32 = gmpy2.gcdext(x1,x2)
m = (pow(m1,s31,n)*pow(m2,s32,n))%n
m = gmpy2.iroot(m,6)[0]
print(libnum.n2s(int(m)))
# b'flag{a1c50828-6199-48c1-8297-a9c44a823ed0}'

RSA困难题型