英文:
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}")
我的目标是找到Flag。我注意到n实际上就是p的平方，因此在RSA术语中可以说p=q。以下是我用来解决这个挑战的脚本：
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
# 打印p*p是否等于N，注释掉了以保持清晰
# print(p*p==N) This is true
# 现在我们已经找到了p和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是错误的。是否有人能提出我做错了什么的建议？
英文:
I am currently trying to solve a practice CTF challenge on RSA. The source code of the challenge is the following:
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}")
My goal is to find the flag. I noticed that n is nothing other than p squared, so basically p=q in terms of RSA.
This is the script that I am using to solve the challenge:
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..
Now, the problem is that I correctly find the p (although N is very big), but then if I try to compute phi, d and the respective m, by recomputing the ciphertext it doesn't match, meaning that m is wrong. Does anyone have any proposal on what I am making wrong?
答案1
得分: 2
phi(p*q)=(p-1)*(q-1) 成立，如果 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）。
英文:
phi(p*q)=(p-1)*(q-1) holds if p and q are distinct prime numbers (i.e. p!=q). For p=q applies instead: phi(p*p)=p*(p-1), see here.
So if you replace in your 2nd code snippet phi=(p-1)*(q-1) by phi=p*(p-1), then the result is as expected (i.e. ciphertext == pow(m,e,N) returns True).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论