[Dreamhack] uncommon e

풀이 

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

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

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q

    # e = 0x10001 
    # assert GCD((p - 1)*(q - 1), e) == 1... Oh, COME ON.. Stop generating that stupid COMMON e.
    for e1 in range(0x100, 0x10001):
        if GCD(p - 1, e1) >= 0x100: # much better!
            break

    for e2 in range(0x100, 0x10001):
        if GCD(q - 1, e2) >= 0x100: # This is nice!!
            break

    if GCD(e1, e2) == 1: # UN-UN common == common :P
        break

print(f"{N = }")
print(f"{e1 = }")
print(f"{e2 = }")

FLAG_enc1 = pow(FLAG, e1, N)
FLAG_enc2 = pow(FLAG, e2, N)

print(f"{FLAG_enc1 = }")
print(f"{FLAG_enc2 = }")

제공된 코드를 살펴보면 새로운 방식으로 공개키 e1과 e2를 설정하여 암호화를 하고 있다. 이 때, e1과 e2가 서로소 관계이기 때문에 확장 유클리드 알고리즘에 따라서 e1*d1 + e2*d2 = 1 (d1, d2는 각각 e1,e2의 역원)이라는 공식이 성립한다. 

e1*d1 + e2*d2 = 1이라는 공식을 활용하면, 복호화 과정에서 위와 같은 관계가 성립된다. e1과 e2는 output.txt 파일에서 주어져있으므로 간단히 역원을 구하는 과정을 통해서 flag를 얻을 수 있을 것이다. 

exec(open('./uncommon_e/output.txt', 'r').read())

from Crypto.Util.number import long_to_bytes, inverse

d1 = inverse(e1, e2)
d2 = -(d1*e1 - 1) // e2

m = pow(FLAG_enc1, d1, N) * pow(FLAG_enc2, d2, N) % N


res = long_to_bytes(m)
print(res)

이렇게 복호화 코드를 작성하고 실행해보면 아래와 같이 플래그를 얻을 수 있다.