CTF中关于RSA的常见题型
CTF中关于RSA的常见题型关RSA算法原理的描述请看https://blog.csdn.net/weixin_43790779/article/details/1056223271.已知(p, q, e),求d。示例:【CTF秀-crypto4】 p=447685307 q=2037 e=17,提交flag{d}即可。解题思路:import gmpy2p = 447685307q = 2037e
CTF中关于RSA的常见题型
关RSA算法原理的描述请看https://blog.csdn.net/weixin_43790779/article/details/105622327
1.已知(p, q, e),求d。
示例:【CTF秀-crypto4】 p=447685307 q=2037 e=17,提交flag{d}即可。
解题思路:
import gmpy2
p = 447685307
q = 2037
e = 17
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(d)
2.已知(p, q, e,c),求m。
示例:【CTF秀-crypto5】 p=447685307 q=2037 e=17 c=704796792,提交flag{m}。
解题思路:
import gmpy2
p=447685307
q=2037
e=17
c=704796792
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,p*q)
print(m)
3.已知(p, q, dp,dq,c),求m。
示例:【BUUCTF-RSA1】
解题思路:
m
=
c
d
m
o
d
n
m = c^d \ \ mod\ \ n
m=cd mod n
n
=
p
∗
q
n = p*q
n=p∗q
d
p
≡
d
m
o
d
(
p
−
1
)
①
dp ≡ d \ \ mod\ \ (p-1) \ \ ①
dp≡d mod (p−1) ①
d
q
≡
d
m
o
d
(
q
−
1
)
②
dq ≡ d \ \ mod\ \ (q-1) \ \ ②
dq≡d mod (q−1) ②
m
p
≡
c
d
m
o
d
p
③
mp ≡ c^d \ \ mod\ \ p \ \ ③
mp≡cd mod p ③
m
q
≡
c
d
m
o
d
q
④
mq ≡ c^d \ \ mod\ \ q \ \ ④
mq≡cd mod q ④
由③得,
c
d
=
k
∗
p
+
m
p
⑤
c^d=k*p+mp\ \ ⑤
cd=k∗p+mp ⑤
将⑤代入④得,
k
∗
p
≡
m
p
−
m
q
m
o
d
q
k*p≡mp-mq \ \ mod\ \ q
k∗p≡mp−mq mod q
k
≡
p
−
1
∗
(
m
p
−
m
q
)
m
o
d
q
⑥
k≡p^{-1}*(mp-mq) \ \ mod\ \ q \ \ ⑥
k≡p−1∗(mp−mq) mod q ⑥
将⑥代入⑤得,
c
d
=
[
p
−
1
∗
(
m
p
−
m
q
)
m
o
d
q
]
∗
p
+
m
p
c^d=[p^{-1}*(mp-mq) \ \ mod\ \ q]*p+mp
cd=[p−1∗(mp−mq) mod q]∗p+mp
由①,②可得,
d
=
d
p
+
k
1
∗
(
p
−
1
)
=
d
q
+
k
2
∗
(
q
−
1
)
d=dp+k_1*(p-1)=dq+k_2*(q-1)
d=dp+k1∗(p−1)=dq+k2∗(q−1)
由费马小定理可知,
m
p
≡
c
d
m
o
d
p
≡
c
d
p
+
k
1
∗
(
p
−
1
)
m
o
d
p
≡
c
d
p
m
o
d
p
mp ≡c^d \ \ mod\ \ p≡c^{dp+k_1*(p-1)} \ \ mod\ \ p≡c^{dp} \ \ mod\ \ p
mp≡cd mod p≡cdp+k1∗(p−1) mod p≡cdp mod p
m
q
≡
c
d
m
o
d
q
≡
c
d
q
+
k
2
∗
(
q
−
1
)
m
o
d
q
≡
c
d
q
m
o
d
q
mq ≡c^d \ \ mod\ \ q≡c^{dq+k_2*(q-1)} \ \ mod\ \ q≡c^{dq} \ \ mod\ \ q
mq≡cd mod q≡cdq+k2∗(q−1) mod q≡cdq mod q
故
m
≡
c
d
=
[
p
−
1
∗
(
c
d
p
m
o
d
p
−
c
d
q
m
o
d
q
)
]
m
o
d
q
∗
p
+
m
p
m≡c^d=[p^{-1}*(c^{dp} \ \ mod\ \ p-c^{dq} \ \ mod\ \ q)] \ \ mod\ \ q*p+mp
m≡cd=[p−1∗(cdp mod p−cdq mod q)] mod q∗p+mp
脚本代码如下:
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
import gmpy2
import binascii
I = gmpy2.invert(p,q)
mp = gmpy2.powmod(c,dp,p)
mq = gmpy2.powmod(c,dq,q)
m = ((I*(mp-mq))%q)*p+mp
print(binascii.unhexlify(hex(m)[2:]))
4.已知(e,dp, n, c),求m。
示例:【BUUCTF-RSA2】
解题思路:
e
∗
d
≡
1
m
o
d
(
p
−
1
)
(
q
−
1
)
e*d≡1\ \ mod\ \ (p-1)(q-1)
e∗d≡1 mod (p−1)(q−1)
d
p
≡
d
m
o
d
(
p
−
1
)
=
=
>
e
∗
d
p
≡
e
∗
d
m
o
d
(
p
−
1
)
dp≡d\ \ mod\ \ (p-1)\ ==> \ \ e*dp≡e*d\ \ mod\ \ (p-1)
dp≡d mod (p−1) ==> e∗dp≡e∗d mod (p−1)
故
e
∗
d
=
k
1
(
p
−
1
)
(
q
−
1
)
+
1
=
k
2
(
p
−
1
)
+
e
∗
d
p
e*d=k_1(p-1)(q-1)+1=k_2(p-1)+e*dp
e∗d=k1(p−1)(q−1)+1=k2(p−1)+e∗dp,
e
∗
d
p
=
(
p
−
1
)
(
k
1
(
q
−
1
)
−
k
2
)
+
1
e*dp=(p-1)(k_1(q-1)-k_2)+1
e∗dp=(p−1)(k1(q−1)−k2)+1,
因为dp<p,故
e
>
(
k
1
(
q
−
1
)
−
k
2
)
e>(k_1(q-1)-k_2)
e>(k1(q−1)−k2)
(
k
1
(
q
−
1
)
−
k
2
)
∈
(
1
,
e
)
(k_1(q-1)-k_2)∈(1,e)
(k1(q−1)−k2)∈(1,e),遍历即可求得p的值。
脚本代码如下:
import gmpy2
import binascii
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,e):
if (e*dp-1)%i == 0 and n%((e*dp-1)//i+1)==0:
q = n//((e*dp-1)//i+1)
phi = (q-1)*((e*dp-1)//i)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(binascii.unhexlify(hex(m)[2:]))
5.已知(n, e1, e2,c1,c2),求m。
示例:【BUUCTF-RSA3】
解题思路: 涉及知识点为共模攻击
c
1
≡
m
e
1
m
o
d
n
c1≡m^{e1}\ \ mod\ \ n
c1≡me1 mod n
c
2
≡
m
e
2
m
o
d
n
c2≡m^{e2}\ \ mod\ \ n
c2≡me2 mod n
当e1,e2互质时,有ae1+be2=1(其中a,b必为一正一负)。
利用扩展欧几里得算法可求得(a,b)的一组解。
c
1
a
∗
c
2
b
m
o
d
n
c1^a * c2^b\ \ mod\ \ n
c1a∗c2b mod n
=
(
(
m
e
1
m
o
d
n
)
a
∗
(
m
e
2
m
o
d
n
)
b
)
m
o
d
n
=((m^{e1}\ \ mod\ \ n)^a * (m^{e2}\ \ mod\ \ n)^b)\ \ mod\ \ n
=((me1 mod n)a∗(me2 mod n)b) mod n
=
m
a
∗
e
1
+
b
∗
e
2
m
o
d
n
,
=m^{a*e1+b*e2}\ \ mod\ \ n,
=ma∗e1+b∗e2 mod n,
因为
a
∗
e
1
+
b
∗
e
2
=
1
a*e1+b*e2=1
a∗e1+b∗e2=1,所以
m
≡
c
1
a
∗
c
2
b
m
o
d
n
m≡c1^a * c2^b\ \ mod\ \ n
m≡c1a∗c2b mod n
脚本代码如下:
import gmpy2
import binascii
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e1 = 11187289
e2 = 9647291
s = gmpy2.gcdext(e1,e2)
a = s[1]
b = s[2]
if a<0:
a = -a
c1 = gmpy2.invert(c1,n)
else:
b = -b
c2 = gmpy2.invert(c2,n)
m = (gmpy2.powmod(c1,a,n)*gmpy2.powmod(c2,b,n))%n
print(binascii.unhexlify(hex(m)[2:]))
6.已知( e,n1,c1,n2,c2),求m。
示例:【CTF秀-easyrsa2】
解题思路: 两组数中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:]))
7.已知(p+q,p-q, e,c),求m。
示例:[BJDCTF 2nd]rsa0
解题思路:
import gmpy2
import libnum
e=16300321
a=21350430512059560135536506725886192791652921782342757815537127809818896096167861777432862988721624947176730121127946250044713187944377040826978092675745896
b=1553262765888789433201396543987134442184487100865056152409628170591088051337453032936901834118611146414395714768350794090251064953913440485676167006809370
c=54505145716437017236783669089525458569996474667747952435007039609752579283598944353442923680602360632342975079757448484712025793719352475806343163818881133707590318426509468029706897810742965068881431810720947035196632950024324040788801133194474150406380691624739115334015886740557921339305357167098392744905
p = (a+b)//2
q = (a-b)//2
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,p*q)
print(libnum.n2s(m))
7.已知(e,n,c),求m。
示例:【CTF秀-easyrsa1】
解题思路:
可以分解n得到p,q,在线分解大整数网址http://www.factordb.com/index.php 。
脚本代码如下:
import gmpy2
import binascii
e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
p = 1201147059438530786835365194567
q = 1212112637077862917192191913841
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(binascii.unhexlify(hex(m)[2:]))
8.已知(e,n,c),求m。(低加密指数攻击)
示例:【CTF秀-easyrsa4】
解题思路: 题中e=3相对于n,c来说极小,故可知是低加密指数攻击。
①
当
m
3
<
n
时
,
c
=
m
3
,
直
接
将
c
开
三
次
方
即
可
得
到
m
;
当m^3<n时,c = m^3,直接将c开三次方即可得到m;
当m3<n时,c=m3,直接将c开三次方即可得到m;
②
当
m
3
>
n
时
,
c
=
m
3
−
i
∗
n
,
只
要
找
到
i
,
使
得
c
+
i
n
能
够
开
三
次
方
即
可
得
到
m
。
当m^3>n时,c = m^3-i *n,只要找到i,使得c+in能够开三次方即可得到m。
当m3>n时,c=m3−i∗n,只要找到i,使得c+in能够开三次方即可得到m。
脚本代码如下:
import gmpy2
import binascii
e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661
i = 0
while True:
if gmpy2.iroot((c+i*n),3)[1] == True:
m = gmpy2.iroot((c+i*n),3)[0]
break
i += 1
print(binascii.unhexlify(hex(m)[2:]))
9.已知(e,n,c),求m。(低解密指数攻击)
示例:【CTF秀-easyrsa5】
解题思路: 题中e很大,故可知是低解密指数攻击。
可以使用破解脚本:求出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(binascii.unhexlify(hex(m)[2:]))
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)