提问人:Shark44 提问时间:7/20/2023 更新时间:7/20/2023 访问量:322
RSA - CTF 加密和解密
RSA - CTF Encrypt and Decrypt
问:
我目前正在尝试解决 RSA 上的实践 CTF 挑战。挑战赛的源代码如下:
from Crypto.Util.number import getStrongPrime, bytes_to_long
from secret import flag
p = getStrongPrime(1024)
n = p*p
ct = pow(bytes_to_long(flag),65537,n)
print(f"N: {n}")
print("e: 65537")
print(f"Ciphertext: {ct}")
我的目标是找到这面旗帜。我注意到 n 只不过是 p 的平方,所以基本上 p=q 就 RSA 而言。 这是我用来解决挑战的脚本:
from sympy import factorint
from Crypto.Util.number import inverse
from Crypto.Util.number import long_to_bytes, bytes_to_long
N = 17247429011400091594903121614278317774635194567355664182083286460825623278786842450296276336243601369886531345460567758683264711621579053621928923112845729038920820584866481858788199156251002137294317693549968171587560980199578605277615016297806648517292231417503335937517545040818693753744974426077235846550662950287459352497273884563460997553049302884794110615691778846001187875451148062541191040207901569501139838046342432918478105568543142728845613434476488073435158841063873479450746792085243366610793708083771235300723836114651517179308753861599354559357082701098376497379860365093082194763554366394532766270441
e = 65537
ciphertext = 73856274733636037480705118582707253154331884152543812530396852364910317444631279978151266880998392327051579551195174910966346458203462739328504111752660934987920144143256608807202384495146366180063763952442956953997212234338589093090543779433867912610529819086616268003032728521238128403257422990840265611603144926710938571975237945229348543608800432648053640151779084773334154380549080493528741315675693189798034401372997956383236742945661608648934118804562523298133099955814197894630073716823425525171494907446686386474871039477578650745672272267639633128732470409207666675371064176768285518092393337398629693441
#print(factorint(N)) #square of 131329467414590894604854795173365398896201184952104193748129988169713995480202398488092403487193967215049091388509880107122001081151286397499791450577587622771865343057370826566912737156758236033887044593314395514760330131964758403355753063826514226886688942810874269688433452014205077769669852552277528221229
p = 131329467414590894604854795173365398896201184952104193748129988169713995480202398488092403487193967215049091388509880107122001081151286397499791450577587622771865343057370826566912737156758236033887044593314395514760330131964758403355753063826514226886688942810874269688433452014205077769669852552277528221229
q = p
#print(p*p==N) This is true
#Now that we have found p and q..
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(ciphertext, d, N)
print(m)
print(ciphertext == pow(m,e,N)) #False..
现在,问题是我正确地找到了 p(尽管 N 非常大),但是如果我尝试计算 phi、d 和相应的 m,通过重新计算密文它不匹配,这意味着 m 是错误的。有没有人对我做错了什么有任何建议?
答:
2赞
Topaco
7/20/2023
#1
phi(p*q)=(p-1)*(q-1)
成立 if 和 是不同的素数(即 )。对于应用,请参阅此处。p
q
p!=q
p=q
phi(p*p)=p*(p-1)
因此,如果将第二个代码片段替换为 ,则结果符合预期(即 返回 )。phi=(p-1)*(q-1)
phi=p*(p-1)
ciphertext == pow(m,e,N)
True
评论
0赞
Shark44
7/20/2023
那行得通,谢谢。
评论