[Zer0pts 2023] - easy factoring

이 문제는 디스코드에 soon_harri 의 힌트가 없었다면 풀지 못했을지도 모르는,, 신기한 문제이다. 얼핏 보면 매우 간단하지만, 막상 마주하면 어떻게 문제를 풀어야 할지 감도 오지 않는 기상천외한 문제이다. 풀이를 작성하고도 수많은 브루트 포싱을 통해서 결국 플래그를 구해내게 되었고, 이 과정 또한 너무 오래 걸린 것 같다.

🖲️ Code Analysis

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

딱히 문제를 설명할 필요도 없는 것 같다. $ N = p^2 + q^2 $ 의 값을 주고, p 와 q 를 구해내면 플래그를 주는 간단한 문제이다. 

💡 Main Idea

이 문제의 핵심적인 아이디어는 바로 Gaussian Integer 이다. 

Gaussian integer - Wikipedia

가우스 정수는 단순한 정수가 아닌, $ G = \left \{ a + bi\;|\, a , b \in \mathbb{Z} \right \} $ 집합 안에 있는 모든 수를 말한다. 갑자기 왜 복소수가 튀어나오냐고 의문을 가질 수도 있지만, N 을 가우스 정수로 인수분해할 수 있다는 것이 핵심이다. 

 

$ N = p^2 + q^2 = (p + qi) \times (p - qi) $ 로 표현이 가능하다. 따라서 sage 를 이용해서 비교적 간단하게 풀 수 있다. 

(사실 이 문제는 sage 의 기능을 알고 있더라면 그래도 쉽게 풀지 않았을까..? 라는 생각이 들긴 할 정도로 sage 에 의존하는 문제이다.. ㅠㅠ)

📖 Exploit Code

from pwn import *
# context.log_level = "debug"

while True:
    REMOTE = 1
    if REMOTE:
        io = remote("crypto.2023.zer0pts.com", int(10333))
    else:
        io = process(["python3", "server.py"])

    io.recvuntil(b"N: ")
    N = int(io.recvline().strip().decode())
    print(f"[*] N = {N}")

    print("[*] Solving diophantine equation")
    G = GaussianIntegers()
    Gn = G(N)

    for d in divisors(Gn):
        p, q  = abs(d.real()), abs(d.imag())
        if is_prime(p) and is_prime(q) and d.norm() == N:
            print("[*] Solved!!")
            break

    io.sendlineafter(b"p: ", str(p).encode())
    io.sendlineafter(b"q: ", str(q).encode())
    res = io.recvline().strip()

    if res == b"omg":
        print("[*] Failed..")

    else:
        io.recvline()
        flag = io.recvline().strip().decode()
        print(flag)
        break

    io.close()

이렇게 Divisors 라는 함수를 사용해서 주어진 수를 나누는 모든 수를 계산할 수 있는 것 같다. 이 계산을 ZZ[i] 상에서 해주면 (가우스 정수) 앞서 말했던 $ p + qi$ 꼴을 구해낼 수 있을 것이다.