Push it to the limit.
$e$가 $N^{1 \over 12}$ 가량의 크기인 RSA에서 $d_p$, $d_q$의 LSB가 주어진다. 이때 $p$와 $q$를 찾아내면 되는 문제다.
검색을 열심히 하면 $d_p$와 $d_q$의 LSB를 통해 비밀 키를 복구하는 논문을 찾을 수 있다. “Approximate Divisor Multiples – Factoring with Only a Third of the Secret CRT-Exponents”라는 논문이다. 초록에 “$N^{1 \over 12}$에서 이 공격이 가장 취약하다”라는 이야기를 하는데, 여기서 감을 잡아야 한다.
GitHub에 이 논문 제목을 집어넣어서 검색하면 저자가 만든 구현체 스크립트를 얻어낼 수 있다. implementation_new_attack.sage이다. 이걸 그대로 실행하면 안 되고, 몇 가지 수정을 줘야 하는데… 그건 공격 스크립트 (1) 참조. 이를 통해서 $d_p$를 얻을 수 있다.
이제 여기서 비밀 키를 복구해내면 된다. $p = \mathrm{gcd}(N, 2^{ed_p - 1} - 1)$를 바탕으로 하면 된다. 암호문 복호화하면 플래그가 나온다. 공격 스크립트 (2) 참조.
WACon{Factoring_with_only_a_third_of_the_bits}
Oops,, I erase the original bmp file,, It was a dumb mistake,,
[+] The picture size is 1920 x 1281
ECB 펭귄을 보신 적이 있나요?
대충 ECB 암호화가 나쁜 이유를 설명하는 사진이다. 같은 데이터의 블록이 같은 결과로 암호화되므로 데이터의 기밀성이 지켜지지 않는다는 이유다.
이제 문제를 보자. $C = g^P + a \times i^2 + b \times i + c$로 암호화가 되는 것을 볼 수 있다. $a, b, c$항은 지울 수 있지만, 나머지 부분은 DLP이므로 풀어낼 수가 없다. 저걸 풀 수 있으면 CTF가 아니라 논문을 써야지…
핵심은, $a, b, c$항을 지우고 나면, 동일한 블록이 동일한 결과로 암호화된다는 것이다. BMP는 이미지를 압축하지 않으므로, 위와 같이 픽셀의 규칙이 일부분 보존되어 있을 거라 기대해볼 수 있다.