babyrsa

Description

Category: Crypto

Source: 0CTF/TCTF 2019 Quals.

Points: 74

Author: Jisoon Park(js00n.park)

Description:

RSA challs are always easy, right? Even if N is not a integer.

babyrsa.zip

Write-up

압축을 풀어보면 암호화된 flag, public key와 rsa.sage를 얻을 수 있다.

[...]

R.<a> = GF(2^2049)

def encrypt(m):
    global n
    assert len(m) <= 256
    m_int = Integer(m.encode('hex'), 16)
    m_poly = P(R.fetch_int(m_int))
    c_poly = pow(m_poly, e, n)
    c_int = R(c_poly).integer_representation()
    c = format(c_int, '0256x').decode('hex')
    return c

if __name__ == '__main__':
    ptext = flag + os.urandom(256-len(flag))
    ctext = encrypt(ptext)
    with open('flag.enc', 'wb') as f:
        f.write(ctext)

sage 파일을 보면 RSA encryption 알고리즘이 간단하게 구현되어 있는데, 정수 기반이 아니라 다항식 기반으로 운영되고 있는 것을 알 수 있다.

from sage.all import GF, PolynomialRing

P=PolynomialRing(GF(2),'x')
e = 31337
n = P('x^2048 + x^2046 + x^2043 + x^2040 + x^2036 + x^2035 + x^2034 + x^2033 + [...]

public key 파일을 열어보면 마찬가지로 다항식 모양으로 선언된 modulus를 확인할 수 있다.

이렇게 생긴 RSA 시스템은 처음 보는데, 관련된 자료가 있을지 한번 검색을 해보자. polynomial rsa라는 키워드로 검색을 해보면, Polynomial based RSA라는 문서를 가장 먼저 찾을 수 있다. Polynomial RSA에 대한 실질적인 설명은 2.1.2장에 나와 있다.

완전히 이해는 어렵지만, 대충 훑어보면 일반적인 RSA와 비슷하게 P(x)와 Q(x)를 구한 후 이를 곱해서 N(x)를 만들어서 암호화와 복호화를 수행하는 것 같다.

문제에 주어진 것은 다항식이라는 것을 제외하면 크게 특이해 보이지 않는 n과 e와 암호화 함수 정도인데, 일반적인 RSA 문제에서는 이런 경우에 N이 인수분해 가능한 형식으로 주어지는 경우가 많다.

다항식은 어떻게 인수분해 할 수 있을까. 위의 문서를 계속 훑어보다 보면 4.3절에 Polynomial factorization에 관한 내용과 Berlekamp's algorithm이 있는 것을 볼 수 있는데 나는 이해할 수 없었다.

문제가 sage 코드로 주어졌는데, sage에서 할 수 있는 방법이 없을까 싶어 sage polynomial factorization으로 검색해 보았더니 sage의 polynomial factorization 항목을 찾을 수 있었다.

간단해 보이는데 실제로 되는지 확인해 보자.

0.1초만에 주어진 다항식 n을 821차 다항식과 1227차 다항식으로 분리해준다. 다항식이 딱 두개 나오는걸 보니 뭔가 성공적인 것 같다.

아까의 문서에서 P(x), Q(x)로 부터 private key d를 어떻게 구하는지 찾아보자.

P(x)와 Q(x)의 최고차항의 차수를 각각 n와 m이라고 하면, s = (p^m - 1)(p^n - 1)이고, d = e^(-1) mod s라고 한다. s가 phi(N)과 비슷하게 계산되고 사용되는 것 같다.

위의 다항식 분해에서 최고차항이 821, 1227이었으니 m과 n을 각각 821과 1227이라고 하고, p가 2일 때 s를 계산해 보자.(P=PolynomialRing(GF(2),'x') 라고 정의되어서 p = 2라고 하였다.)

sage가 간단하게 d를 계산해 주었다.

이제 encrypt 함수를 참고해서 decryption을 해보자.

별다른 문제없이 decryption을 성공하여 flag를 확인할 수 있었다.

Flag : flag{P1ea5e_k33p_N_as_A_inTegeR_~~}