[드림핵] Amo's gift

코드 분석

from Crypto.Util.number import *

FLAG = b"DH{FAKE_FLAG}"
FLAG = bytes_to_long(FLAG)

while True: # RSA의 공개키 N 생성 과정
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 0x10001
    if GCD(e, (p - 1) * (q - 1)) == 1:
        break

일반적인 RSA key 생성 과정.
p, q를 생성하여 e라는 값에 부합하는 N이 될때까지 루프를 반복한다.

# Here is amo's gift for you!
gifts = []
for i in range(800):
    if isPrime(i): # 2-800까지 중 소수에 대해서
        gift = [p % i, q % i]
        gift = sorted(gift) # What's wrong with you, AMO?
        gifts.append(gift)

2-800 사이의 모든 소수로 p와 q를 나눈 나머지에 대해서, 그대로가 아니라 크기 순으로 다시 정렬하여 gifts에 차례대로 넣는다.

이때 중요한 것은, 2-800까지의 모든 소수의 곱은 약 330자리 수로 이는 p, q보다는 크지만 N이나 $\phi(N)$보다는 턱없이 작은 수라는 것이다.

FLAG_enc = pow(FLAG, e, N)

print(f"{N = }")
print(f"{e = }")
print(f"{FLAG_enc = }")
print(f"{gifts = }")

우리에게 제공하는 정보는 RSA의 공개키 정보인 (N, e)와 암호화된 플래그 값과, gifts라는 리스트이다.

풀이 시도

가장 이상적인 풀이는, 주어진 gifts를 통해서 p와 q를 완전히 복원하는 것이다.

p와 q는 2-800까지의 소수의 곱보다 작기 때문에 CRT(중국인의 나머지 정리)로 온전하게 복원할 수 있는 여지가 있다.

하지만 문제는, gifts의 구성 리스트들이 원소의 온전한 순서를 유지하고 있지 못하다는 것이다.

brute-forcing으로 gifts가 가능한 모든 경우의 수를 생각해보면, 2-800까지의 소수가 약 140개이므로 연산량이 대략 $2^{140} \approx (10^3)^{14} = 10^{42}$, 논외다.

아무리 고민해도 p와 q를 각각 알아내기 위해서는 정확한 gifts의 정렬 전 순서가 필요했고, 상식적으로 복원하기 불가능하다고 판단했다.

2-800까지의 모든 소수의 곱의 범위에서 확인할 수 있는 것이 오직 p와 q 혹은 $\phi(N)$의 인수인 p-1과 q-1 뿐이라고 생각했다.

하지만 생각해보니 p+q도 구할 수 있기는 했고 이걸 이용해서 뭘할 수 있을까 고민했다.

풀이

처음에 문제를 생각할 때, 궁극적으로 구해야하는 목적이 p와 q 자체라고 생각했으나 결국은 복호화 하기 위한 RSA의 개인키를 알아야 했고 이는 $\phi(N)$만 알면 곱의 역원을 구하는 간단한 과정만 거치면 된다.

$\phi(N) = (p-1) \times (q-1) = p \times q - p - q + 1 = N - p - q + 1$

그렇기에, p와 q의 합을 구하면 $\phi(N)$를 손쉽게 계산할 수 있다.

p와 q의 합의 나머지 값은, p의 나머지 값과 q의 나머지 값의 합이라는 점을 이용하자.

그렇다면 p+q에 대한 나머지 값은 아래와 같이 간단하게 계산할 수 있다.

for i in range(leng):
        remain_list.append((gifts[i][0] + gifts[i][1])%prime_list[i])

그리고 요기에다가 CRT를 적용해주면, p+q를 간단하게 복원 가능하다.
마지막으로 이를 통해 $\phi(N)$을 계산하면, 아래와 같은 방법으로 개인 키 d를 복원할 수 있다.

d = pow(e, -1, phi_n)