RSA算法详解与练习

1. 什么是RSA2. RSA算法描述2.1 产生公私密钥对2.2 RSA加密2.3 RSA解密2.4 RSA相关值 3. 安装gmpy24. 实战练习4.1 已知p、q、e，求d4.2.1 已知p、q、e、密文c，求明文m4.2.2 已知c、q、n、e，求明文m4.3 已知n、e、密文c，求明文m4.4 已知public key、密文c，求明文m4.5 已知p、q、dp、dq、c求明文m4.6已知n、e、dp、c，求m4.7共模攻击4.8已知p+q、（p+1)(q+1)、e、d、以及密文C，求明文m

1. 什么是RSA

1977年，麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密算法，用他们三人的姓氏缩写命名为 RSA。RSA 既不是惟一，也不是最早的非对称加密算法。但它是使用最广泛，因而也是最重要的非对称加密算法。

2. RSA算法描述

2.1 产生公私密钥对

1.随机选择两个不相等的质数p和q。 2.计算p和q的乘积n(n=p*q),n的长度就是密钥长度。 3.计算n的欧拉函数φ(n)： φ(n) = (p-1)(q-1) 4.随机选择一个整数e，也就是公钥当中用来加密的那个数字 条件是1< e < φ(n)，且e与φ(n) 互质。 5.取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) 6.将n和e封装成公钥，n和d封装成私钥，（n，e),(n，d)就是密钥对。

补充说明: 1.下面代码中使用phi代替欧拉函数φ(n) 2.如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。

2.2 RSA加密

首先对明文进行比特串分组，使得每个分组对应的十进制数小于n，然后依次对每个分组m做一次加密，所有分组的密文构成的序列就是原始消息的加密结果，即m满足0<=m<n，则加密算法为： c≡ m^e mod n; c为密文，且0<=c<n。 （还可以表示为c = pow(m, e, N）

也就是说RSA加密是对明文的E次方后除以N后求余数的过程。只要知道E和N就可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥。即公钥=(E,N)

2.3 RSA解密

对于密文0<=c<n，解密算法为： m≡ c^d mod n;（还可以表示为m = pow(c, d, N)）

也就是说对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥。即私钥=(D,N)

2.4 RSA相关值

值含义p 和 q两个不相等的质数n大整数n，称之为模数e 和 d互为模反数的两个指数c 和 m分别是密文和明文

3. 安装gmpy2

检查一下是否安装了wheel文件包，在cmd中输入wheel，查看一下 如果没有安装，则输入pip install wheel安装 安装好wheel后，还需要再安装gmpy2所需要的whl文件，查找需要的whl文件包。注意，whl文件包需要和你所安装的python3版本一致；

输入python查看电脑Python版本所支持的whl文件版本 我使用的是python3.8 32位，下载gmpy2‑2.0.8‑cp38‑cp38‑win32.whl，放到python文件目录下。

然后再在cmd中输入：pip install （whl文件的路径） 最后输入：pip install gmpy2就可以安装，没有报错即安装成功

4. 实战练习

4.1 已知p、q、e，求d

[BUUCTF]RSA

编写脚本

import gmpy2 p = 473398607161 q = 4511491 e = 17 d = gmpy2.invert(e,(p-1)*(q-1)) print(d)

运行得到

4.2.1 已知p、q、e、密文c，求明文m

[BUUCTF] rsarsa

打开文档，给出了p、q、e的值 方法一：使用RSAtool工具 使用rsatool工具计算d的值，直接填入p,q,把e = 65537转换为16进制在再填入，再点击Calc.D,即可获得D的值。 然后编写脚本

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 C = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 d = 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977 n = p*q flag = pow(C,d,n) print(flag)

得到明文flag 方法二：利用gmpy2直接写脚本

import gmpy2 p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 e = 65537 C = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 #1.求d d = gmpy2.invert(e,(p-1)*(q-1)) #2.求n n = p*q #3.m=pow(c,d,n) flag = pow(C,d,n) print(flag)

得到明文flag

[ctfshow]babyrsa

import gmpy2 import binascii e = 65537 p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179 q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501 c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194 phi = (p-1)*(q-1) d = gmpy2.invert(e,phi) m = gmpy2.powmod(c,d,p*q) print(binascii.unhexlify(hex(m)[2:]))

运行脚本得到

b'flag{b4by_R5A}'

4.2.2 已知c、q、n、e，求明文m

参考文章 给了 c, q, n ,e

求 p : n//q

求 d: d = invmod(e,(p-1)*(q-1))

求 flag : flag = pow(c,d,n)

import libnum n = 191051885543358947736760989661967468461742175898801910645529003886391047898839624568290216360845330501814019720570327197669064365268607597117598905046895097642708006373182989953758208523010345148200475257538336602695211819055893667974317905617522838840325499754862033348148407978527792816186094297381925119601464149 q = 166836705584681518148179737955842605213272207836752187845124149461151181903779374775281529346854786259719545699157508885500818994019618158708212777833768444327658647324555090459233657737950932895018766440119999513331707759691054888319029069397903003240927552065429412176600134636921146805408664505115889561043 c = 177177672061025662936587345347268313127241651965256882323180749317515733256088163186914550682635245294414879862810654773207644687262596440870094409378849307188485755700138797651039936445998433830516207630858733090581643592843521203499818069822504434370840254518614785953412492701730326524258672860416318501278155194 e = 0x10001 p = n//q print(p) d = libnum.invmod(e,(p-1)*(q-1)) print(d) i = pow(c,d,n) print(libnum.n2s(i))

4.3 已知n、e、密文c，求明文m

[ctfshow]easyrsa1 分解质因数n

编写脚本

import gmpy2 import binascii e = 65537 n = 1455925529734358105461406532259911790807347616464991065301847 c = 69380371057914246192606760686152233225659503366319332065009 #1.将n分解为p和q p = 1201147059438530786835365194567 q = 1212112637077862917192191913841 phi = (p-1)*(q-1) #2.求d d = gmpy2.invert(e,phi) #3.m=pow(c,d,n) m = gmpy2.powmod(c,d,n) print(binascii.unhexlify(hex(m)[2:])) #binascii.unhexlify(hexstr):从十六进制字符串hexstr返回二进制数据

运行脚本 注： 1.在线分解质因数：http://www.factordb.com

2.代码中涉及到了python之binascii模块相关知识

4.4 已知public key、密文c，求明文m

[BUUCTF]RSA 下载附件 用记事本打开pub.key 解析公钥 模数和指数即为n和e，还需要把n从十六进制转换为十进制 分解n，得到p和q

接下来就是通过脚本求出明文m

脚本需要用到python的rsa库，在cmd中输入pip install rsa即可完成安装 脚本

import gmpy2 import rsa e=65537 n=86934482296048119190666062003494800588905656017203025617216654058378322103517 p=285960468890451637935629440372639283459 q=304008741604601924494328155975272418463 phin = (p-1) * (q-1) d=gmpy2.invert(e, phin) key=rsa.PrivateKey(n,e,int(d),p,q) with open("flag.enc","rb") as f: f=f.read() print(rsa.decrypt(f,key))

运行脚本，得到flag。

4.5 已知p、q、dp、dq、c求明文m

[BUUCTF]RSA1

这道题属于已知p、q、dp、dq、c求明文类型 上脚本

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852 import gmpy2 I = gmpy2.invert(q,p) mp = pow(c,dp,p) mq = pow(c,dq,q) #求幂取模运算 m = (((mp-mq)*I)%p)*q+mq #求明文公式 print(hex(m)) #转为十六进制

运行脚本 然后将16进制转换成字符串

4.6已知n、e、dp、c，求m

[BUUCTF]RSA2

下载附件，题目给出公钥n,e以及dp

dp=d%(p-1)

脚本

import gmpy2 import rsa import binascii p=0 e=65537 c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751 dp=905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 n=248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113 temp=dp*e for i in range(1,e) : if (temp-1)%i==0: x=(temp-1)//i+1 y=n%x if y==0: p=x break q=n//p #'//'代表向下取整,'/'得到的是浮点数 d=gmpy2.invert(e,(p-1)*(q-1)) key=rsa.PrivateKey(n,e,d,p,q) m=pow(c,d,n) print(binascii.unhexlify(hex(m)[2:])) #unhexlify()的作用是返回16进制数对应的字符串

运行结果

4.7共模攻击

[BUUCTF]RSA3 出现两个加密使用相同的模，可以在不知道私钥的情况下得到明文，这就是RSA中的共模攻击。 脚本

from gmpy2 import invert # 欧几里得算法 def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def main(): n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e1 = 11187289 e2 = 9647291 s = egcd(e1, e2) s1 = s[1] s2 = s[2] # 求模反元素 if s1<0: s1 = - s1 c1 = invert(c1, n) elif s2<0: s2 = - s2 c2 = invert(c2, n) m = pow(c1,s1,n)*pow(c2,s2,n) % n print(m) if __name__ == '__main__': main()

运行脚本，得到明文m 转16进制

666c61677b34396439313037376131616263623134663161396435343663383062653965667d

十六进制转字符串

4.8已知p+q、（p+1)(q+1)、e、d、以及密文C，求明文m

[GUET-CTF2019]BabyRSA

已知p+q、（p+1)(q+1)、e、d,以及密文c.

利用 RSA的解密公式：

M=C^d mod n n = p*q

所以推算出求n的公式

n = (p+1)*(q+1) - (p+q) - 1

脚本

import libnum a = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea b = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740 e = 0xe6b1bee47bd63f615c7d0a43c529d219 d = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5 c= 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a n = b-a-1 m = pow(c,d,n) print(libnum.n2s(m)) #（n2s将数值转化为字符串）

运行脚本

---

看到一份来自漏斗社区的RSA解题思路思维导图，收藏起来8。