Dreamhack - d (writeup)

이번에는 드림의 "d"문제를 풀어 볼 것이다.

 

일단 아래 문제코드를 살펴보자.

반응형

from Crypto.Util.number import *
from flag import flag

p = bytes_to_long(flag)
assert isPrime(p)
q = getPrime(256)
d = pow(65537, -1, (p - 1) * (q - 1))
print(d)
# 22800184635336356769510601710348610828272762269559262549105379768650621669527077640437441133467920490241918976205665073

위 파이썬 코드의 내용을 정리하면 아래와 같다.

d = 22800184635336356769510601710348610828272762269559262549105379768650621669527077640437441133467920490241918976205665073
e = 65537

q는 256비트

처음에는 어떤 방법으로 할 지 전혀 모르겠는 것 같아서 rsa 위키백과를 보다가 우연히 아래와 같은 부분을 확인했다.

이걸 보고 ed-1이 소인수분해가 가능하면 p나 q를 구할 수 있을 것이라고 알게 되었다.

 

그래서 아래의 두 사이트를 참고하여 ed-1를 소인수분해 했다.

http://factordb.com/

https://www.alpertron.com.ar/ECM.HTM

소인수 분해 결과

2 * 2 * 2 * 2 * 3 * 5 * 5 * 37 * 1117 * 4029461 * 1403014978139 * 284368748316481195117 * 18741210882440665187461519398960291465361283084482741278982029639876282810203

그러면 이를 조합하여 ed-1의 모든 인수를 구한 뒤, int를 bytes로 바꿨을때 "DH{"를 포함하는 숫자가 p, int의 길이가 256비트인 숫자가 q가 되는 수를 구하는 python 으로 아래와 같이 구현 가능하다.

from Crypto.Util.number import *

factors = [(2, 4), (3, 1), (5, 2), (37, 1), (1117, 1), (4029461, 1), (1403014978139, 1), (284368748316481195117, 1), (18741210882440665187461519398960291465361283084482741278982029639876282810203, 1)]

all_factors = [1]

for (prime, power) in factors:  # <- 인수 구하기
    new_factors = []
    for factor in all_factors:
        for i in range(1, power+1):
            new_factors.append(factor * prime**i)
    all_factors += new_factors

for i in all_factors:
    num = i+1
    if isPrime(num):
        num_bytes = long_to_bytes(num)
        if b'DH{' in num_bytes:    #  <- p 즉 flag 판별
            print("FLAG : "+num_bytes.decode('utf-8'))
            print("p = " + str(num))
        elif num.bit_length() == 256:  #  <- q 판별
            print("q = " + str(num))

이 프로그램을 실행하면 아래와 같이 flag(p), q를 구할 수 있다.