RSA总结

发表于 2020-12-19 更新于 2021-06-30 分类于 RSA 阅读次数：

本文字数： 13k 阅读时长 ≈ 12 分钟

RSA总结

基本原理:

选择两个大素数p、q，计算出模数N=p*q
计算欧拉函数φ = (p-1) * (q-1)，随机选择一个e(1<e<φ)，满足e和φ互质
取e的模反数d，计算方法为:e * d ≡ 1 (mod φ)，e一般取65537
对明文m进行加密：c = pow(m, e, N),可以得到密文c (m<n)
对密文c进行解密：m = pow(c, d, N),可以得到明文m

整理：

p 和 q：两个大的质数，是另一个参数N的的两个因子。
N：大整数，可以称之为模数
e 和 d：互为无反数的两个指数
c 和 m：密文和明文
(N, e)：公钥
(N, d)：私钥
pow(x, y, z)：效果等效pow(x, y) % z，先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。
密钥长度：n以二进制表示的的位数，例如密钥长度为512代表n用二进制表示的长度为512bit
一般商业化的密钥取4096位，迄今为止超级计算机破解的密钥位数为700多位

安全性分析

对于RSA加密算法，公钥(N, e)为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文

保障RSA的安全性

1.定期更换密钥
2.不同的用户不可以使用相同的模数N
3.p与q的差值要大，最好是差几个比特
4.p-1与q-1都应该有大的素因子，一般建议选择的两个大素数p、q使得 p=2p+1和q=2q+1也是素数
5.e的选择不要太小
6.d的选择也是不可以太小，最好满足d>=n的4分之1

CTF常见攻击手法

暴力分解N的方法

[yafu]: https://blog.csdn.net/cliffordr/article/details/82747087 “window下安装yafu”

p,q相差不大或相差巨大时
[factordb]: http://www.factordb.com/index.php “在线分解网站”

n不超过1024位时

下面不再分析n能被上述方法分解的情况
对于N由多于两个的素数相乘的情况，N 的欧拉函数的数值由多个素数的欧拉函数相乘

1.对RSA的公共模数攻击（BUU-RSA3）

适用于：使用相同的模数 N 、不同的私钥，加密同一明文消息

已知c1,c2,e1,e2,n1=n2

c1 = pow(m, e1, N)
c2 = pow(m, e2, N)
m = pow(c1, d1, N)
m = pow(c2, d2, N)

原理分析

from Crypto.Util.number import *
import gmpy2
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397

e1=11187289
e2=9647291


_, s1, s2 = gmpy2.gcdext(e1, e2)

m = pow(c1, s1, n) * pow(c2, s2, n) % n
print (long_to_bytes(m))

2.公约数分解n

识别此类题目，通常会发现题目给了多个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。可以直接gcd(n1,n2)求出一个因数，进而分解n，得到另一个因数

n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a

print "p: "+str(gcd(n1,n2))
print "q1: "+str(n1/gcd(n1,n2))
print "q2: "+str(n2/gcd(n1,n2))

3.低加密指数分解攻击

在RSA中e也称为加密指数。由于e是随机选取的，如果选取的e太小，导致m^e仍然比模数N来的小，相当于密文C只是明文的e次方而已，可以对密文进行开方即可得到明文

e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
求明文m?

import gmpy2
import libnum
c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
m = gmpy2.isqrt(c)
m = int(m)
m_text = libnum.n2s(m)  #将 十六进制转为 字符
print(m_text)

也有可能e的三次方会比n大但是大不了太多，可以进行爆破,每次多加一个n。

1
2
3

n=0x9683f5f8073b6cd9df96ee4dbe6629c7965e1edd2854afa113d80c44f5dfcf030a18c1b2ff40575fe8e222230d7bb5b6dd8c419c9d4bca1a7e84440a2a87f691e2c0c76caaab61492db143a61132f584ba874a98363c23e93218ac83d1dd715db6711009ceda2a31820bbacaf1b6171bbaa68d1be76fe986e4b4c1b66d10af25
e=0x3
c=0x8541ee560f77d8fe536d48eab425b0505e86178e6ffefa1b0c37ccbfc6cb5f9a7727baeb3916356d6fce3205cd4e586a1cc407703b3f709e2011d7b66eaaeea9e381e595b4d515c433682eb3906d9870fadbffd0695c0168aa26447f7a049c260456f51e937ce75b74e5c3c2bd7709b981898016a3a18f15ae99763ff40805aa

i = 0
while 1:
    res = iroot(c+i*n,3)
    if(res[1] == 1):
        print(res)
        break
    i = i+1

4.Rabin加密算法

Rabin加密算法是一种RSA 的衍生算法，特征是e=2.

加密原理

$c\quad = \quad m^2 \quad mod\quad n$

解密原理

计算出 $m_q 和 m_p$

$m_p\quad=\quad\sqrt{c}\quad mod\quad p$ $m_q\quad= \quad \sqrt{c}\quad mod \quad q$

扩展欧几里得计算出a和b

$y_p*p \quad+\quad y_q*q\quad=\quad1$

解出四个明文

$a\quad=\quad( y_p*p*m_q\quad {+}\quad y_q*q*m_p )\quad mod n$ $b\quad=\quad n\quad-\quad a$ $a\quad=\quad( y_p*p*m_q\quad {-}\quad y_q*q*m_p )\quad mod n$ ${d\quad = \quad n\quad-\quad c}$

解密脚本

def rabin_decrypt(c, p, q, e=2):  
    n = p * q  
    mp = pow(c, (p + 1) / 4, p)  
    mq = pow(c, (q + 1) / 4, q)  
    yp = gmpy2.invert(p, q)  
    yq = gmpy2.invert(q, p)  
    r = (yp * p * mq + yq * q * mp) % n  
    rr = n - r  
    s = (yp * p * mq - yq * q * mp) % n  
    ss = n - s  
    return (r, rr, s, ss)

5.低解密指数攻击（CTFSHOW-RSA5）

在RSA中d也称为解密指数。当d比较小的时候，或者说e特别大的时候

适用情况：e过大或过小（一般e过大时使用）可使用算法快速推断出d的值

引用RSA-wiener——attack https://github.com/pablocelayes/rsa-wiener-attack

下下来之后新建一个python库，把.py文件都放进去。引用时会报错，大概就是修改几个import，之后就可以用了

from Crypto.Util.number import *
import gmpy2
import RSAwienerHacker.RSAwienerHacker
e = 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345
n = 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231
c = 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827

d = RSAwienerHacker.RSAwienerHacker.hack_RSA(e,n)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

5.dp，dq泄露（已知p、q、dp、dq、c）（BUU-RSA1）

简单说明dp，dq参数是为了让解密更快的产生

dp=d%(p-1)
dq=d%(q-1)

IMG_20201118_224842

import gmpy2
from Crypto.Util.number import *

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852


I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(long_to_bytes(m))

6.dp泄露

不同于上面的dp，dq泄露，需要一些其他技巧

原理

求解脚本

def getd(n,e,dp):
    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/(((dp*e-1)/i)+1)
                phi = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d

7.中国剩余定理的应用

问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

这是很典型的中国剩余定理的问题，要明白中国剩余定理，需要明白上述问题的解决方法，自行掌握

给出一个题目的解题脚本

from Crypto.Util.number import *
import gmpy2
enc=[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]
from functools import reduce
def egcd(a, b):
    """扩展欧几里得"""
    if 0 == b:
        return 1, 0, a
    x, y, q = egcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q
def chinese_remainder(pairs):
    """中国剩余定理"""
    mod_list, remainder_list = [p['n'] for p in pairs], [p['c'] for p in pairs]
    mod_product = reduce(lambda x, y: x * y, mod_list)
    mi_list = [mod_product//x for x in mod_list]
    mi_inverse = [egcd(mi_list[i], mod_list[i])[0] for i in range(len(mi_list))]
    x = 0
    for i in range(len(remainder_list)):
        x += mi_list[i] * mi_inverse[i] * remainder_list[i]
        x %= mod_product
    return x
if __name__=='__main__':
    s=chinese_remainder(enc)
    print(long_to_bytes(gmpy2.iroot(s,10)[0]))

Zpano's Blog

RSA总结

RSA总结

基本原理:

安全性分析

保障RSA的安全性

CTF常见攻击手法

1.对RSA的公共模数攻击（BUU-RSA3）

原理分析

2.公约数分解n

3.低加密指数分解攻击

4.Rabin加密算法

加密原理

解密原理

解密脚本

5.低解密指数攻击（CTFSHOW-RSA5）

5.dp，dq泄露（已知p、q、dp、dq、c）（BUU-RSA1）

6.dp泄露

原理

求解脚本

7.中国剩余定理的应用

8.待补充，不同情况下的高低位泄露