RSA-CTF中n=p²场景下解密失败问题求助

错误原因 #

你误用了普通双素数RSA的欧拉函数公式。当n=p²（素数的平方）时，欧拉函数的正确公式是：

φ(n) = p*(p-1)

而非你使用的(p-1)*(q-1)（该公式仅适用于p≠q的普通RSA场景）。这是因为对于素数幂p^k，欧拉函数的计算规则是φ(p^k) = p^k - p^(k-1)，代入k=2就得到p² - p = p(p-1)。

修正后的求解脚本 #

from sympy import factorint
from Crypto.Util.number import inverse, long_to_bytes

N = 17247429011400091594903121614278317774635194567355664182083286460825623278786842450296276336243601369886531345460567758683264711621579053621928923112845729038920820584866481858788199156251002137294317693549968171587560980199578605277615016297806648517292231417503335937517545040818693753744974426077235846550662950287459352497273884563460997553049302884794110615691778846001187875451148062541191040207901569501139838046342432918478105568543142728845613434476488073435158841063873479450746792085243366610793708083771235300723836114651517179308753861599354559357082701098376497379860365093082194763554366394532766270441
e = 65537
ciphertext = 73856274733636037480705118582707253154331884152543812530396852364910317444631279978151266880998392327051579551195174910966346458203462739328504111752660934987920144143256608807202384495146366180063763952442956953997212234338589093090543779433867912610529819086616268003032728521238128403257422990840265611603144926710938571975237945229348543608800432648053640151779084773334154380549080493528741315675693189798034401372997956383236742945661608648934118804562523298133099955814197894630073716823425525171494907446686386474871039477578650745672272267639633128732470409207666675371064176768285518092393337398629693441

p = 131329467414590894604854795173365398896201184952104193748129988169713995480202398488092403487193967215049091388509880107122001081151286397499791450577587622771865343057370826566912737156758236033887044593314395514760330131964758403355753063826514226886688942810874269688433452014205077769669852552277528221229

# 使用素数平方的欧拉函数公式
phi = p * (p - 1)
d = inverse(e, phi)
m = pow(ciphertext, d, N)

# 验证加密还原
print(ciphertext == pow(m, e, N)) # 现在会输出True
# 转换为flag
print(long_to_bytes(m))

补充说明 #

修正欧拉函数后，计算出的私钥d满足e*d ≡ 1 mod φ(n)，此时解密得到的明文m再加密后会完全匹配原密文，最终通过long_to_bytes即可还原出flag。

内容的提问来源于stack exchange，提问作者Shark44