from Crypto.Util.number import *import gmpy2from flag import mp = getPrime(1024)q = getPrime(1024)n = p * qe = 65537miao = m * e ** 114514 * pc = pow(miao,e,n)print('n =',n)print('c =',c)n = 15724473323565045396370858465469794253897098805658297755038464795187843864543336878458855839908938174609226125906389647596135126780127853622918512750724133584255813225824621395423147937411028484797397604314549972831401569058888828390709389850009401999311919893801585196625261707533397394617900788093073155283942628090462027599299261904948019001134387413947227412444769837076744236033154179273077282052507015769350002149388500729755099921806453579133365664602172243156399457894104732823874214077421498887133708915560830956009329435645769146484681739460872512462904147532278669159028733288243011480246972212572785396951c = 13979061528868934515991503434842402588520368874011952968148427460697509714748731073556587063579866682867476314979258657484882946029437582223157020767329942522520919760899855118050378516616088604837486252499316743832035392322851380083033361998393452998263670256288025282295743323558056979630144546247582020682237999855779926018311317468574189832558037678809876850876418649656848539996712475992846363312922214381030516807233491184673015387286304596658582165385106253842227343385240797371235750880819135427727076716569309407314242434870197756376022377417240138527121517361247185657355931682447584016791273217145770895952
解题思路
-
分析加密过程：
明文经过变换miao = m * e^114514 * p，然后使用RSA加密得到密文c。这里的模数n = p * q，公钥指数e = 65537。 -
利用GCD分解n：
由于miao包含因子p，加密后的c也必然是p的倍数。通过计算gcd(c, n)可以分解出p，进而得到q = n // p。 -
计算私钥d：
使用欧拉函数φ(n) = (p-1)(q-1)和扩展欧几里得算法计算私钥d，即d ≡ e⁻¹ mod φ(n)。 -
解密得到miao：
用私钥d解密密文c得到miao ≡ c^d mod n。由于miao = m * e^114514 * p，这里需要进一步处理。 -
恢复明文m：
将miao除以p得到temp = m * e^114514。接下来，在模q下计算e^114514的逆元，从而求得m ≡ temp * inv(e^114514) mod q。
import gmpy2from Crypto.Util.number import long_to_bytesn = 15724473323565045396370858465469794253897098805658297755038464795187843864543336878458855839908938174609226125906389647596135126780127853622918512750724133584255813225824621395423147937411028484797397604314549972831401569058888828390709389850009401999311919893801585196625261707533397394617900788093073155283942628090462027599299261904948019001134387413947227412444769837076744236033154179273077282052507015769350002149388500729755099921806453579133365664602172243156399457894104732823874214077421498887133708915560830956009329435645769146484681739460872512462904147532278669159028733288243011480246972212572785396951c = 13979061528868934515991503434842402588520368874011952968148427460697509714748731073556587063579866682867476314979258657484882946029437582223157020767329942522520919760899855118050378516616088604837486252499316743832035392322851380083033361998393452998263670256288025282295743323558056979630144546247582020682237999855779926018311317468574189832558037678809876850876418649656848539996712475992846363312922214381030516807233491184673015387286304596658582165385106253842227343385240797371235750880819135427727076716569309407314242434870197756376022377417240138527121517361247185657355931682447584016791273217145770895952# 分解n得到p和qp = gmpy2.gcd(c, n)q = n // p# 计算phi(n)和私钥dphi = (p - 1) * (q - 1)e = 65537d = gmpy2.invert(e, phi)# 解密得到miaomiao = pow(c, d, n)# 计算temp = m * e^114514temp = miao // p # 因为miao = m * e^114514 * p，整除p得到m * e^114514# 计算e^114514模q的逆元e_exp_modq = pow(e, 114514, q)inv_e_exp = gmpy2.invert(e_exp_modq, q)# 计算m模q并恢复明文m = (temp * inv_e_exp) % qflag = long_to_bytes(m)print(flag.decode())
原文始发于微信公众号（瓜神网络安全&分享）：北京市第六届信息通信行业网络安全技能大赛(初赛)-CTF夺旗阶段 EZRSA writeup
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论