[CTF Writeup / Crypto] LA CTF 2024 - very hot

간단한 RSA 문제.

코드는 다음과 같음.

from Crypto.Util.number import getPrime, isPrime, bytes_to_long

from flag import FLAG

FLAG = bytes_to_long(FLAG.encode())

p = getPrime(384)

while(not isPrime(p + 6) or not isPrime(p + 12)):

    p = getPrime(384)

q = p + 6

r = p + 12

n = p * q * r

e = 2**16 + 1

ct = pow(FLAG, e, n)

print(f'n: {n}')

print(f'e: {e}')

print(f'ct: {ct}')

 

우선 Prime이 384로 작음. factordb로 소인수분해가 가능할 수 있음.

n을 p * q * r 의 형태로 3개의 곱으로 구성함.

factordb를 통해 두개의 값으로 소인수분해가 가능했는데, 이 중 확실히 소수인 값을 p로 가정하고 assert 구문을 통해 검증을 시도함.

p를 구했으므로 phi값을 연산, 이를 이용해 d 값을 구하고, 복호화.

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

n = 10565111742...5037870799

e = 65537

ct = 9953835612...77985

# factordb

a = 219427656538...2077

b = 4814849645...31387

assert ((a+6) * (a+12) == b)

p = a

q = p + 6

r = p + 12

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

d = inverse(e, phi)

pt = pow(ct, d, n)

print(long_to_bytes(pt))