zer0pts CTF 2023 : easy_factoring

[roaris]

https://alpacahack.com/challenges/easy-factoring

[roaris]

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)

[roaris]

• $p, q$ は素数
• $p^2+q^2$ が与えられる

$p, q$ が一意に決まるのか ($p, q$ の交換は除いて) というところが気になる 一意に決まらないと、この問題は解けない

[roaris]

全然分からないのでwriteup見たら、ガウス素数とか出てきた 何も知らない...

[roaris]

https://qiita.com/kusano_k/items/3c6809ff163e2edbe826#easy_factoring-crypto この解法なら自分にも理解できそう