RSAbaby

Description

Category: Crypto

Source: Codegate 2018 Quals.

Points: 300

Description:

XD

source : Codegate 2018 Quals.

Write-up

주어진 파일을 unzip으로 풀어보면, RSAbaby.py 파일과 이를 수행한 결과인 Result.txt 파일을 확인할 수 있다. Result.txt에 있는 값들을 이용하여 암호화 된 flag를 푸는 문제임을 쉽게 짐작할 수 있다.

문제로 부터 얻어낼 수 있는 값은 n(modulus), e, h, g, encrypted flag이다.

임의의 a에 대하여, 이므로,

임을 알 수 있다.

형태를 보면 아래의 페르마의 소정리(Fermat's little theorem)와 닮은 것 같다.

페르마의 소정리를 이용할 수 있도록 수식을 확장해 나가보자.

은 p의 배수임을 알 수 있고, n도 p의 배수이므로, GCD를 적용하면 p를 찾아낼 수 있다. (p는 소수니까)

p를 찾아내면 N = pq로 부터 q를 간단히 계산해낼 수 있고, p, q와 e를 알게 되었으므로 d도 알아낼 수 있다.

찾아낸 d를 이용해서 암호화 된 flag를 복호화 하면 원래의 flag 값을 확인 가능하다.

아래는 a를 2로 하여 flag를 계산해내는 코드이다.

import re

enc_flag = (...)
n = (...)
h = (...)
g = (...)
e = 65537

def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n

kp = pow(2, e*g, n) * pow(2, 0xdeadbeef - 1, n) - 1
p, _, _ = xgcd(kp, n)
q = n / p

pi_n = (p-1)*(q-1)
d = mulinv(e, pi_n)

flag = pow(enc_flag, d, n)

print re.sub('(..)', lambda x: chr(int(x.group(1), 16)), hex(flag)[2:])

Flag : Whatever you do, the Basics are the most important :-D