Problem: [观安杯 2023]crypto_FakeRSA
思路
- 解题大致思路
EXP
- 具体攻击代码
from Crypto.Util.number import long_to_bytes, inverse
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
N = 19847620135822668847564514587942391948142624860181655735976934793142518668448318713906565631067926756575383231918008750320314318388342153000764317436938181753432239594989585637171839692228131563530710256600537628487979942994048525298362384704877859902808184444222096716564895401232578897723044129300645044323034052671774897679133209083253985051039010667384545090074079940175443302000660736565924866897854894975144801717146983216246279171532978445848360788240501229409058122640344180850723589598379999463896719432194098148150730453207196992264577662129500076382789140147725633949387830756940746588747464997105199040847
e = 0x10001
c1 = 1756115882899235333767373412952685058442578502362305178148708348397221699382473322607024057374181363259992143822782466595632557188733429609610437516825340510258579461836830981981515610525669855890508880687879237365862600631017783112431782409053401059679909119087279725255362593628680270527043535327044114537521767844175613946742069798280407430255538431961464100994053843455293830848713979793641759592848965709164401923805202865181278248599013059304674374932785159449985020076949947804463531636632218338979436633344262978442310866256196263672451806491567851964985444336191269723675403138965510273692493690922361284742
c2 = 2803882274464201632040310581340103954084366760475201812662337610119769672819960061278044921535221513068638607844358489732622395365341033774881175819904209471697333114522738668213960797378289175577854350822191156502389735396131609058051616247521510491333054934440476132327664414576125210514726048893532826553354112713412642050620661244235614627904861745988056133532835701882528265437296782174901011907579127296290336500125990526397809739665495288624623561555437259052010679639283282062401845887548408945917975559038856053229947588628662730086650236283183680761269321053645374046392192539882589660212309427186121150806
g1 = 13683841336865841027652885569517449118992937497136804390789331098331105352858652504602625539672234430450616300504934856205064301811453804827917010475710699981014147946901465471877276000648012394735526065867450733647157768937302975684732550438551576742898866575823747069190609092224595543227133253510681145175984336182160164364554214802315164481578086371211804484783458365930147218337811369364850919070408100347945643554041867922429579033971970570060727603461691767890539331854786545982199998297298219754661137384625652128251904967127785945241854788060742454470903059115886397423042297289925395685450803460831897928252
g2 = 1715827607770822027916388359002895605121557965635122390638079472658089153470011628164369842925275875967712538848782207398137721300785000148786237090186504979128222511965981575912913326516029139664053593759312951800545982648954917607038575718360849770282586139468386428432823626468085403220001310594753857986186494335432908855975879089482927309452461286290921871478006193072624494526500896055795364974923120807686893394782469634994819939396068806887992467663531650404341622534450045351363338604611403508251536208868099600795923830484553848138777019101735178671893852703652034757522746423826105891841738087294547994803
# 1. 利用 g1, g2 因式分解 N
p = gcd(g1 - 1, N)
q = gcd(g2 - 1, N)
print("[+] p =", p)
print("[+] q =", q)
# 2. 计算 m^e 在模 p, q 下的值
me_p = c1 % p
me_q = c2 % q
# 3. CRT 合并
inv_p_mod_q = inverse(p, q)
t = (me_q - me_p) * inv_p_mod_q % q
me_N = (me_p + p * t) % N
# 4. 私钥 d
d = inverse(e, lcm(p-1, q-1))
# 5. 解密得到 m
m = pow(me_N, d, N)
flag = long_to_bytes(m)
print("[+] flag =", flag)
总结
- 对该题的考点总结