CTF中常见的RSA题型
一.分解得到p,q，实现对密码的攻击
当n不大或者n已经被分解过之后，可以尝试使用该方法
可以使用大整数分解网站查询有无已经分解出来的http://factordb.com/
本地的话可以使用yafu进行分解。
分解出p,q后即可得到私钥，从而实现破解密文。
以这个为例，我们仅了解n,c,e,但是我们可以分解n,分解结果如下
得到分解结果后就可以正常RSA脚本解密了
所用脚本如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| import gmpy2
from Crypto.Util.number import long_to_bytes
q = 189239861511125143212536989589123569301
p = 386123125371923651191219869811293586459
e = 65537
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
n = q*p
print(n)
d = gmpy2.invert(e, (p - 1) * (q - 1))
print("d=",d)
m = pow(c, d, n)
print(m)
print(long_to_bytes(m))
|
二.低加密指数攻击
当e很小的时候，可以尝试该攻击方式。
RSA的加解密原理中有c=m^e+kn,我们可以对k进行爆破，直到c-kn可以开根，从而得到m。
在这个实例中，我们可以发现n很大，尝试大整数分解后无果，但是e很小。
尝试进行低加密指数攻击，可以得到原始明文
以下为使用的脚本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| from gmpy2 import *
from Crypto.Util.number import *
n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e=0x3
c=0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
n=int(n)
e=int(e)
c=int(c)
m=iroot(c,e)
if m[1]:
m=m[0]
print(long_to_bytes(m))
|
三.共模攻击
当存在多组的c和e时，e之间互质，模数n相同，可以尝试进行共模攻击，以下为详细步骤
- 获取两个不同的RSA公钥： 攻击者首先需要获取两个不同的RSA公钥，这两个公钥具有相同的共模（即两个公钥的N值相同），但指数（e值）是不同的。
- 确定公共模数N： 攻击者知道两个公钥的N值相同。N是两个素数（p和q）的乘积，而这两个素数生成了不同的RSA公钥。攻击者需要将N值提取出来，这样他们就能够使用相同的N进行攻击。
- 计算最大公约数（GCD）： 使用欧几里得算法，攻击者计算两个公钥的指数之间的最大公约数（GCD）。这是攻击的关键步骤，因为共模攻击的基础是使用GCD来找到两个指数的线性组合，从而获得一个可以破解加密的私钥。
- 计算私钥： 一旦攻击者找到两个指数的线性组合，他们就可以使用扩展的欧几里得算法来计算相应的私钥d。私钥d是用于解密信息的关键。
- 解密信息： 攻击者使用计算出的私钥d来解密之前被RSA加密的信息。
以下面题目为例，可以看到仅知道两组的e和c,可以进行RSA共模攻击
使用脚本如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import gmpy2
import libnum
c1= 295658788074157816670393593671184451782123605135184996662528766686642109492132533952160456440919197939935742027629210419312032730004032666912404179229952394343569590488768472800784830058534578639706805456277578757250365834591813481786084959844340418320620440636997732915872346619679993987903742079972676425404864295283955565746004124045155664762158516005326368384488346997494926539295740248007606864906884407198601326915643000764477435205579583836917598642053869541648731754384026407310786288997756775232852732033054591953078116290088267188296560877481534143707414153749140670404213262630122369941889862912426176115220410931992046973925991075473656781794097329513119548617920256625579072719981729556158392454956362838720993254919638177786730004086883044525967823454986241038123671907279715773848673713008902432841449556980494600938989397567019338970200872333713986608537678650318511128703055185979834233315117153115613952940778789222515375743186066883492596068186378372611075958909412662251913621375996518671118244409393829141365207153662416265238312206577474940661548038715230313608405518108581922154335405303862701783678336161505643508831482409054761542959278392940037561736468155509922530420964726953308604138731805543997557197893
c2= 219454357017359138238563345020257296433275019950745269658921329153689267055871241202626317639487122341365759606018366576305678949982408366815977617307888894995289951707241009621444691307275542686770303994110416384086739599181934011812163156338859395115724413628620575935425221522079154607411877822646179457455118804970038865452163833416447505142114976758532806787419762250921421272492466133659234602794242531776209324085944417173098820895755851386042954303555790085402616519592065446023510096773546730662074307900123349548340507067971393642039476326402523930789953483843698593104578179169624886357604650615249286150367204109726460230037005175927865466199600272190112483494387929732049738312695796015009178606906549093365261114132002222704510637261038978031857378729856467918978246977163353146981239215886053379980533235786905270211605457443266127512667882149285155542735532327780898540341696557860555884277608448996773250847560675650046440569736010800155992053362696097992699863059686881689842065077997427372972290872427656847223849769329713841670853267584161386494525686204330028142217737052411422895042170169703550774908415280261731967511925122636118468176645781785352430657090024109246103061415446942211482659025722233229083093876
n= 549785700554963543393222974982211136067042846536450239199968863551137077564447156832697813202963334596948298760762991663065504535035143397250208506445202607659676332816610122258862787906629525548439909792727593939957178783466989816894454522630301104349317697612174888605090061231211194974337772507249418567229560145454791075929946332668360553910328900103264562348881791004831033587660163923517440406942993348972589262051083908075790422096042338651001937740085414301019827335549437397656318095919875053213333008551761167437683250592542156348138055482054331330609375930693247365749085041596578748797801601289693449629548744535914348450016287545136436964138806081283470239420969311905998245715160353982174880912315601876305613349276824998688275587308133069178764001924866079232824850209407236694426779262951463035278887804883917516580169051530590466082511045503107508117656821592538792566264160105940730326929474477787053681516844548383814388361089499629312831727731267796167205124844987064389097138747938870221504684958713047985374714612321540288239995935347905120710583169131356970267386562665138437631517802641426575996558648777831102462652517305151412695166331935115971277205305816897886952646432233312318756155702046584205507027737
e1 = 3247473589
e2 = 3698409173
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
return int(m)
m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m)))
|
参考文章：https://blog.csdn.net/qq_45521281/article/details/114706622