[ImaginaryCTF 2023] - sus

이 문제는 너무 너무 신박해서 아직도 사실 100% 이해가 되지는 않았다. 뭔가 나의 시야를 한층 더 넓혀주는 문제인 것 같고, 예전에 KMO 를 하면서 "어떻게 이런 생각을 하지" 라는 생각이 다시금 들게 하는 문제였던 것 같다... 앞으로 열심히 해야겠다..

🖲️ Code Analysis

from Crypto.Util.number import getPrime, isPrime, bytes_to_long

def sus(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp

p, q = sus(512, 3)
r = getPrime(512 * 3)
n = p * q * r
e = 65537
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

이 문제도 매우 간단한데, 기본적인 RSA 에서 $n  = p \times q \times r$ 이라는 부분이 특이하다. 

결국 코드를 더 분석해보면, $q = p^2 + p + 1$이라는 것이 되고, 이 문제는 $p \times (p^2 + p + 1) \times r$ 꼴의 정수를 인수분해 하는 문제로 변환할 수 있게 된다. 

💡 Main Idea

먼저, 내가 설명하기에 앞서, discord 에 문제 제작자가 만들어놓은 설명 사진을 첨부하겠다..

 

solution from maple3142 from ictf discord server :)

간단하게 한국어로 요약해보자면, 무작위 3차 방정식을 만드러내고, 이를 modulus로 몫환으로 만들었을 때, 이 modulus 가 irreducible, 즉 인수분해가 되지 않는다면 $GF(p^3)$ 로도 볼 수 있다는 것이다. 

 

이렇게 만들어진 GF위의 임의의 원소 $\alpha$ 에 대해서, $\alpha^n$ 을 하게 되면,  order가 $p^3 - 1$이 되는데, 이는 인수분해 해보면 $(p-1)\times(p^2 + p + 1)$ 이 되기 때문에 $\alpha^n$은 결국 order 가 $p-1$이 되게 된다. (대부분)

 

따라서 p-1 번만 제곱해서 항등원이 되기 위해서는 방정식이 $u + 0x + 0x^2$ 꼴이 되어야 하기 때문에, $x^1$ 이나 $x^2$의 계수는 p의 배수가 될 수밖에 없다. 따라서 이 수와 n 을 GCD 하게 되면, p 값이 도출된다. 

 

사실 여기서 내가 이해가 되지 않는 점은, 왜 하필 상수만이 남아야 하는지 의문이다. (p-1) 제곱을 해서 항등원이 나오려면 $x$ 나 $x^2$ 만이 남아도 성립하게 되는 것이 아닌가..??

또, 왜 order 가 꼭 $p^3 -1 $ 이 되는 것인지도 의문이다. GF(p^3) 위에서의 원소는 order 이 $p^3 - 1$이 아닐텐데,,, 

이 궁금증을 해결해주신면 아무나 밥을 사드리겠습니다 ^^

📖 Exploit Code

뭐 결국 풀이를 작성해보면 다음과 같다. (건방지게 풀이가 상당히 짧다)

from output import *
from Crypto.Util.number import *

R = PolynomialRing(Zmod(n), "x")

while True:
    Q = R.quo(R.random_element(3))
    res = gcd(int(list(Q.random_element() ^ n)[1]), n)
    if res > 1:
        p = res
        q = p^2 + p + 1
        r = n // (p*q)
        assert p * q * r == n

        phi = (p-1)*(q-1)*(r-1)
        d = inverse(e, phi)
        flag = pow(c, d, n)
        print(long_to_bytes(flag).decode())
        break