您的位置 首页 CTF

搬运:CTF RSA入门及ctfshow easyrsa1-8 WP

以下搬运至mumuzi师傅的博客。https://blog.csdn.net/qq_42880719 博主也是…

以下搬运至mumuzi师傅的博客。https://blog.csdn.net/qq_42880719

博主也是才入门密码学,今天边学边刷了8道RSA,赶忙来记录一下学习RSA的过程(学习的书籍为:深入浅出密码学)

题目使用的是ctfshow crypto分区中的easyrsa1-8题

————————————————————F12sec———————————————————————-

前置知识
模运算
乘法逆元
欧拉函数
RSA知识
easyrsa1-8题

前置知识

模运算

假设a,r,m∈Z(Z为整数集),并且m>0。如果m除a-r,可记作:

a ≡ r mod m

其中m为模数,r为余数
讨论推导过程,如下:

1.余数计算:
总可以找到一个a∈Z,使得

a = q · m + r , 其中0 ≤ r < m

由于a – r = q · m(m除a-r),上面的表达式可以写作:

a ≡ r mod m(r∈{0,1,2,…,m-1})

如a=88,m=12,则

88 = 12 ·7 + 4
因此88 ≡ 4 mod 12

2.余数不唯一:
对每个给定的m和a,可能同时存在无限多个有效的余数,如:
a = 12,m = 9,以下三个结果都是正确的

12 ≡3 mod 9 ,因为 9 |(12-3)
12 ≡21 mod 9 ,因为 9 |(21-3)
12 ≡ -6 mod 9 ,因为 9 |(-6-3)

其中,x | y 表示 x除y

3.等价类中所有成员的行为等价
对于一个给定模数m,选择等价类中任何一个元素来计算,结果都是一样的。例如:
计算3⁸ mod 7
对于这种值较小的数,可以直接计算

3⁸ = 6561 ≡ 2 mod 7

如果数字较大呢?下面这种方法可以有效简化计算

将3⁸ 替换为3⁴ ·3⁴ = 81 ·81
因为81 = 11 · 7 +4
则3⁸ = 81 · 81 ≡ 4 · 4 =16 mod 7
最后得到16 ≡ 2 mod 7

乘法逆元

假设a ∈ Z,乘法逆元a⁻¹可以定义为:

a · a⁻¹ ≡ 1 mod m

可以通过一种简单方法判断给定元素a的逆元是否存在:
当且仅当gcd(a,m) = 1,一个元素a∈Z存在乘法逆元a⁻¹,其中gcd表示最大公约数。
举例:
Z₂₆中15的乘法逆元是否存在?

因为gcd(15,26) = 1,即最大公约数为1,所以15的逆元存在

Z₂₆中14的乘法逆元是否存在?

因为gcd(14,26) = 2 ≠ 1,所以Z₂₆中14的乘法逆元不存在

欧拉函数

在一个环Zm = {1,2,…,m-1}中,研究多少个数与m互质,这个数目可以由欧拉函数给出,定义如下:

Zm内与m互素的整数可以表示为φ(m)

举例:m = 6,即Z₆={0,1,2,3,4,5}

gcd(0,6) = 6
gcd(1,6) = 1
gcd(2,6) = 2
gcd(3,6) = 3
gcd(4,6) = 2
gcd(5,6) = 1
可以发现1,5符合条件,最后得到
φ(6) = 2

但是如果m非常大呢,这里就需要用到更简单的计算方法:

举例:
m = 240

m = 240 = 16 · 15 = 2⁴ · 3 · 5
有三个不同的质因子即n = 3
则φ(m) = (2⁴ – 2³)(3¹ – 3º)(5¹ – 5º) = 8 · 2 · 4 =64

RSA知识

上面积累了那么多,进入正题,先摆上两个公式:

加密公式mᵉ ≡ c mod n(c ≡ mᵉ mod n)
解密公式cᵈ ≡ m mod n(m ≡ cᵈ mod n)

秘钥生成过程
1.选择两个不相等的质数p和q
2.计算q与p的乘积n
3.计算n的欧拉函数φ(n)
4.选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质
5.计算e对于φ(n)的模反元素d(如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。这时,b就叫做a的“模反元素”。)
用公式表示为

ed≡1(modφ(n))

6.(n,e)打包为公钥,(n,d)打包为私钥

加密过程举例

首先取一个明文m,假设为4
选择不相等的质数,假设q=3,p=11
计算n = 33
计算φ(n) = (3-1)(11-1) = 20
选择一个整数e,假设e=3
计算d ≡ e⁻¹ ≡ 7 mod 20,即d = 7
计算mᵉ ≡ c mod n,即 64 ≡ 31 mod 33,得到c = 33

此时得到密文c = 31,公钥对(33,3),私钥对(33,7)

解密过程举例
假设只知道n=33,c=31,e=3
首先分解n,n=11·3
其次计算欧拉数φ(n) = (11-1)·(3-1)=20
计算模反元素d,d = (20+1)/ 3 =7
解密 cᵈ ≡ m mod n,即31⁷ ≡ m mod 33,计算得到 m = 4

————————————————————F12sec———————————————————————-

以上为RSA的加密和解密过程,通过实例可以很容易了解到RSA的基础算法,下面用python来进行计算

easyrsa1-8题

easyrsa1

e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009

利用factordb在线分解n,得到

q = 1201147059438530786835365194567
p = 1212112637077862917192191913841
import gmpy2
import binascii

e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
q = 1201147059438530786835365194567
p = 1212112637077862917192191913841

L = (p-1)*(q-1)
d = gmpy2.invert(e,L) # 求逆元
m = gmpy2.powmod(c,d,n) # 幂取模,结果是 m = (c^d) mod n

print(binascii.unhexlify(hex(m)[2:])) 

————————————————————F12sec———————————————————————-

easyrsa2

e84d48eaff91b01c3a43e3a4ef500ba9

题目中e相同,n,c不同,求出n1与n2的最大公因数即为p,之后就可以得到q和d,从而求解m

import gmpy2
import binascii

e = 65537
n1 = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c1 = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815

n2 = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c2 = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062

p = gmpy2.gcd(n1,n2) # 欧几里得算法
q = n1 // p
phi = (p-1)*(q-1)

d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c1,d,n1)

print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa3

182ed48bcf3f98cbccb2a39e8ae67000-1可以观察到n相同,但e,c不同,为共模攻击
共模攻击:
使用了相同的模数n,用不同的秘钥e加密同一信息m

c1 = m^e1 % n
c2 = m^e2 % n

根据扩展的欧几里得算法,可以得到
e1s1 + e2s2 = gcd(e1, e2) = 1,s1、s2皆为整数,但是一正一负。

所以(c1^s1*c2^s2)%n
= ((m^e1%n)^s1*(m^e2%n)^s2)%n
化简为
((m^e1)^s1*(m^e2)^s2)%n
=(m^(e1^s1+e2^s2))%n
因为前面提到e1s1 + e2s2 = 1
所以(c1^s1*c2^s2)%n = m%n
最后得到c1^s1*c2^s2 = m

根据此可以写脚本

import gmpy2
import binascii

e1 = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849

s = gmpy2.gcdext(e1,e2)# 扩展欧几里得算法
m1 = gmpy2.powmod(c1,s[1],n)
m2 = gmpy2.powmod(c2,s[2],n)

m = (m1*m2)%n
print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa4

1e608a3e99696f1bc763d6c1f5aff652

e很小,为低加密指数攻击
①m3<n,也就是说m3=c。
②m3>n,即(m3+i·n)mod n=c(爆破i)

import gmpy2
import binascii

e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661

i = 0
while True:
    if gmpy2.iroot((c+i*n),3)[1] == True:#gmpy2.iroot(x,n) x开n次根
        m = gmpy2.iroot((c+i*n),3)[0]
        break
    i += 1

print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa5

3fe51c27a4491ca7ad8c3bbf7143730c-1

e和n都很大,根据加密的过程,可以很容易爆破出d,为低解密指数攻击
爆破d脚本https://github.com/pablocelayes/rsa-wiener-attack
注意要将破解脚本和rsa-wiener-attack的py文件放在同一目录下

import gmpy2
import binascii
import RSAwienerHacker

e = 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345
n = 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231
c = 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827

d = RSAwienerHacker.hack_RSA(e,n)
m = gmpy2.powmod(c,d,n)
print(d)
print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa6
题目给出了一个py文件:

ed1ce2f87340b51bb6f2079f0bd153ea可以看到p与q很接近,使用yafu分解n

得到q,p。

import gmpy2
import binascii

e = 0x10001
n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257
q = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385801
p = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385163

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa7

d02d58388c98d310751ed97217841bfd

p损失掉了低位数据,用sagemath恢复p(自行安装windows版sagemath)

得到50487ba4749a47e7784af486eef1a3d9-1

import gmpy2
import binascii

p = 147305526294483975294006704928271118039370615054437206404408410848858740256154476278591035455064149531353089038270283281541411458250950936656537283482331598521457077465891874559349872035197398406708610440618635013091489698011474611145014167945729411970665381793142591665313979405475889978830728651549052207969
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
c = 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691
e = 0x10001

q = n//p
phi = (q-1)*(p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

————————————————————F12sec———————————————————————-

easyrsa8

下载附件,给出了public.key和flag.enc
首先使用python(或在线网站http://tool.chacuo.net/cryptrsakeyparse/)分解n,e

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from numpy import long

public = RSA.importKey(open('public.key').read())
n = long(public.n)
e = long(public.e)
print(n)
print(e)

得到

1b276a47eae2fd6fbab528093e96081e最后写脚本

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from numpy import long
import gmpy2
import binascii

public = RSA.importKey(open('public.key').read())
n = long(public.n)
e = long(public.e)
print(n)
print(e)
p = 97
q = 106249972159566919549855203174197828387397831115262336234662051342543151219702510584956705611794290291345944183845955839244363030579896461607496959399297130227066841321473005074379950936513608503266587950271044991876848389878395867601515004796212227929894460104645781488319246866661398816686697306692491058609
d = 4520639064487098151327174667961365516283539231992543792882057746866179464294032313887767783621724945557985447874376379715922452725597335427159165685648572663979688014560576024497341124412004366514253110547369977143739781801290219136578513871764574450392367530817034216313429071683911546803031169524669257788417
rsakey = RSA.importKey(open('public.key','r').read())
privatekey = RSA.construct((n,e,d,p,q))
rsa = PKCS1_OAEP.new(privatekey)
m = rsa.decrypt(open('flag.enc','rb').read())
print(m)

本文参考博客:
https://blog.csdn.net/weixin_44617902/article/details/109318766
https://blog.csdn.net/weixin_43790779/article/details/108562895
https://blog.csdn.net/weixin_40328085/article/details/100837778
https://blog.csdn.net/qq_31408919/article/details/104917729
https://www.cnblogs.com/rainbowcloud/p/10141301.html
参考书籍:
深入浅出密码学

本文来自网络,不代表F12sec立场,转载请注明出处:http://www.0dayhack.net/index.php/678/
头像

作者: ENJOEY

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

CAPTCHAis initialing...
联系我们

联系我们

QQ群:884338047

在线咨询: QQ交谈

邮箱: 2676666667@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部