2022重庆市大学生信息安全竞赛Root_RSA WP

思路

已知e,P,Euler(Q),c,n.求m.

P = p**3

分解P,得到p

Q = q**2

根据欧拉函数性质,可知

Euler(Q) = q*(q-1)

分解phi_Q得到一个大因数,这个数比剩下的因数乘积大很多,所以可以推断这个大因数应该不是q,但是是q的倍数。

n = p*q*r
q*r = n/p

可知q*r的值,对phi_Q求公约数,可以得到q,进而得到r.

计算得到phi_n,对e取模反元素得到d.

至此,私钥对(n,d)已经取得,对消息解密,得到原文。

Exp如下:

from Crypto.Util.number import *
import gmpy2
from hashlib import md5

e = 65537
n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303
p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487
# p**3==P
# phi_Q = q*(q-1)
phi_Q = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620
r_q = n//p # q*r
q = gmpy2.gcd(r_q, phi_Q)
r = r_q//q
phi_n = (p-1)*(q-1)*(r-1)

c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)

flag =flag[5:-1]
m = md5()
m.update(flag)
digest = m.hexdigest()
print("flag{"+digest+"}")

赛题文件

Root_RSA附件

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇