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?
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).