Ps and Qs

Description

Category: Crypto

Source: SECCON CTF 2017 Quals.

Points: 200

Author: Jisoon Park(js00n.park)

Description:

Ps and Qs

Decrypt it.

(zip file pass:seccon2017)

source : SECCON CTF 2017 Quals.

Write-up

주어진 파일을 unzip으로 풀어보면, RSA public key 2개(pub1.pub, pub2.pub)와 이를 이용해서 암호화 한 파일인 cipher 파일을 확인할 수 있다.
ciper 파일을 복호화하면 flag가 나올 것 같다.

사용할 수 있는 데이터가 두 개의 public key이기 때문에, 두 public key로 부터 공통의 p를 찾아내는 공격을 시도한다. 공격에는 RsaCtfTool이 제공하는 기능을 사용하였다.

(두개의 Key Pair의 n(modulus)이 동일한 p를 이용해서 생성되었기 때문에 gcd(n1, n2)를 통해 p를 직접 계산하고, 이로부터 q와 e를 알아내어 직접 복호화를 수행해도 무방하다. 간단한 계산이긴 하지만, 역시 도구를 사용하는게 더 편리.)

도구의 힘으로 1초도 안되어 p, q를 찾아내고 p, q, e를 이용하여 private key 데이터를 생성하였다.

툴이 찾아준 private key를 파일에 쓰고, 이를 이용하여 cipher 파일을 간단히 복호화 하였다.

Flag : SECCON{1234567890ABCDEF}