문제에서 대놓고 Wiener’s Attack을 썼다고 알려주고 있다. 실제 문제도 wiener’s attack만 알고 있으면 쉽게 풀 수 있는 문제이다.

WhereIsMyKey.zip

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

flag = b"IxC{???????????????????????????????????????}"

if __name__ == "__main__":
    while True:
        print()
        print("### RSA Server ###")
        print("1. encrypt plain text")
        print("2. decrypt cipher text")
        print("828365. return flag with random key")
        print("0. exit")
        print("menu : ", end='')
        menu = int(input())

        if menu == 1:
            print("N = ", end='')
            N = int(input())
            print("e = ", end='')
            e = int(input())
            print("plain text(hex) = ", end='')
            plain_text = bytes_to_long(bytes.fromhex(input()))

            print("cipher text = " + str(format(pow(plain_text, e, N), 'x')))

        elif menu == 2:
            print("N = ", end='')
            N = int(input())
            print("d = ", end='')
            d = int(input())
            print("cipher text(hex) = ", end='')
            cipher_text = bytes_to_long(bytes.fromhex(input()))

            print("plain text = ", end='')
            print(str(long_to_bytes(pow(cipher_text, d, N)), 'ascii'))

        elif menu == 828365:
            p = getPrime(512)
            q = getPrime(512)
            while p == q:
                q = getPrime(512)

            N = p * q
            d = getPrime(254)
            e = inverse(d, (p-1)*(q-1))
            
            print("flag = " + str(long_to_bytes(pow(bytes_to_long(flag), e, N)).hex()))

            ingredient = list()
            a, b = e, N
            while b > 0:
                ingredient.append(a//b)
                a, b = (b, a%b)

            print("continued fraction = " + str(ingredient))
        
        elif menu == 0:
            exit(0)
        
        else :
            print("Try again")

파이썬 플라스크 파일

828365번 메뉴로 원래는 d를 근사하려고 만들었던 연분수 리스트를 받는다.

이는 $\frac{e}{N}$와 같으므로 원래의 분수로 되돌려서 e와 N을 구한다.

문제의 코드를 보면 N이 1024비트인데 d가 $\frac{N^{0.25}}{3}$보다 작은 254비트이므로 wiener’s attack이 적용될 수 있으므로 d를 구할 수 있다.

이 d로 2번 메뉴를 통해 flag를 복호화하면 된다.

AI는 저 연분수 정보가 도움이 안된다고 하는 것 같다.