[CryptoHack] Inferius Prime

RSA를 구현했나보다. 문제 파일이 주어지고 있다.

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 3

# n will be 8 * (100 + 100) = 1600 bits strong which is pretty good
while True:
    p = getPrime(100)
    q = getPrime(100)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    if d != -1 and GCD(e, phi) == 1:
        break

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

 

위의 코드로 실행했을 때 결과는 다음과 같다.

단순하게 rsa를 구현한 것 같아 보인다.

먼저 주어진 n을 sagemath를 통해 소인수분해 해주었다.

그 다음 phi N을 구해주고 d를 구한다. 구한 d로 복호화 해주면 끝!

from Crypto.Util.number import *
from gmpy2 import *

n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373

p=752708788837165590355094155871
q=986369682585281993933185289261

phi=(p-1)*(q-1)

d=pow(e,-1,phi)

pt=pow(ct,d,n)

print(long_to_bytes(pt))

 

코드는 다음과 같다.

성공!

🚩 crypto{N33d_b1g_pR1m35}