왜 사람들이 RSA에서 하나가 아니라 두 개의 소수를 곱하는 지 의문을 품고 있다.
주어진 문제 파일이다. n을 두 소수 p와 q의 곱으로 구한 것이 아닌 하나의 소수로 만들었기에 phi(N) 역시 n-1로 바로 구할 수 있다.
따라서 해당 phi(N)을 바탕으로 d를 구하고 복호화를 수행하면 간단하게 평문을 얻을 수 있다.
from Crypto.Util.number import *
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
d=pow(e,-1,n-1)
print(long_to_bytes(pow(ct,d,n)))
코드는 위와 같다.
성공!
🚩 crypto{0n3_pr1m3_41n7_pr1m3_l0l}