[CryptoHack] Modulus Inutilis

내 소수는 지금 충분히 커야 한다고? 뭔 소린지 모르겠다.

#!/usr/bin/env python3

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

e = 3
d = -1

while d == -1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

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

 

문제 코드이다. 이번에는 e를 3으로 암호화하고 있는 것을 확인할 수 있다.

또한 결과 파일을 보면 n이 ct에 비해 훨씬 큰 수임을 확인할 수 있다. 이런 경우에는 ct의 세제곱근을 구하면 쉽게 pt를 구할 수 있다.

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

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

with local_context() as ctx:
    ctx.precision = 3000
    m = cbrt(ct)    

    print(long_to_bytes(int(m)))

 

정답을 구하는 코드이다. cbrt 함수는 세제곱근을 구해주는 함수이다. 위의 precision은 정밀도를 설정해준 것이다.

flag를 얻었다.

🚩 crypto{N33d_m04R_p4dd1ng}