Daily Crypto CTF Advent Calendar 2025

zer0pts CTF 2023: easy_factoring Upsolve

Last updated at 2025-12-24Posted at 2025-12-24

easy_factoring

authored by mitsu

The word "decomposition" has multiple meanings.
Can you decompose?

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
$$
で計算された$N$が渡されます。素因数分解し、$p,q$が素数かつ$N=pq$となればフラグを得られます。

解法

$N$の平方和の分解は、ガウス整数環$\mathbb{Z}[i] = ${$a+bi | a, b\in \mathbb{Z}$}の素元分解ができれば解けるそうです。
さて、$N$がガウス素数$\pi_1, \cdots, \pi_n$を用いて
$$
N = (\pi_1 \bar{\pi_1})\cdots(\pi_n \bar{\pi_n})
$$
のように書けたとしましょう。
このとき、$N$は
$$
N = (a+bi)(a-bi) = (\pi_1 \bar{\pi_1})\cdots(\pi_n \bar{\pi_n})
$$
となるため、素元分解で現れた因数に関してすべての組み合わせを計算すれば、$p,q$が復元できます。

from pwn import *
from itertools import combinations
from sage.all import *


HOST = "34.170.146.252"
PORT = 37079

while True:
    io = remote(HOST, PORT)
    io.recvuntil(b"N: ")
    N = ZZ[I](io.recvline().strip().decode())

    print(N)

    factors = list(factor(N))
    for i in range(len(factors)):
        factors[i] = factors[i][0]

    for i in range(1, len(factors) + 1):
        for j in combinations(factors, i):
            mul = prod(j)
            if is_prime(ZZ(abs(mul[0]))) and is_prime(ZZ(abs(mul[1]))) and mul.norm() == ZZ(N):
                print(mul)
                io.sendlineafter(b"p: ", str(abs(mul[0])).encode())
                io.sendlineafter(b"q: ", str(abs(mul[1])).encode())
                io.interactive()
    io.close()

Flag: zer0pts{piyopiyo_Fermat's_Sum_of_Square_meow!!}

別解

当初は以下のコードでフラグを出していました。
が、作問者Writeupみたらライブラリ使って解くのは非想定解らしいので、勉強のために作問者の解き方を色々調べて上記の解き方をしました。

from sage.all import *
from pwn import *
from Crypto.Util.number import isPrime


HOST = "34.170.146.252"
PORT = 18693

while True:
    io = remote(HOST, PORT)
    io.recvuntil(b"N: ")
    N = ZZ[I](io.recvline().strip().decode())
    print(f"N: {N}")
    p,q= two_squares(N)

    if isPrime(int(p)) and isPrime(int(q)):
        io.sendlineafter( b"p: ", str(p).encode())
        io.sendlineafter( b"q: ", str(q).encode())
        io.interactive()
    else:
        print("Factors are not prime!")
        io.close()

参考文献

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up