magic – 다섯 개의 큰 정수, N – 1024비트 RSA 모듈러스, e – 공개 지수 65537, c – 복호화해야 할 암호문. magic 값들 차분→세 행렬식 계산 후 GCD로 LCG 모듈러 p 복원→N/p=q→φ=(p-1)(q-1)→d=e^{-1} mod φ→c^d mod N으로 평문 추출하면 flag값을 알아낼 수 있다.

from __future__ import annotations

import binascii
from functools import reduce
from math import gcd

def recover_lcg_modulus(outputs: list[int]) -> int:
    diffs = [outputs[i + 1] - outputs[i] for i in range(len(outputs) - 1)]
    determinants = [diffs[i + 2] * diffs[i] - diffs[i + 1] * diffs[i + 1]
                     for i in range(len(diffs) - 2)]
    return reduce(gcd, determinants)

def recover_lcg_parameters(outputs: list[int], modulus: int) -> tuple[int, int]:
    x0, x1, x2 = outputs[:3]
    inv_den = pow((x1 - x0) % modulus, -1, modulus)
    a = ((x2 - x1) * inv_den) % modulus
    c = (x1 - a * x0) % modulus
    return a, c

def decrypt_rsa_magic(magic: list[int], N: int, e: int, c: int) -> bytes:
    p = recover_lcg_modulus(magic)
    q = N // p
    if p * q != N:
        raise ValueError("N 인수분해 실패; 계산된 p가 N을 나누지 않음")
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    plaintext_int = pow(c, d, N)
    hex_plain = format(plaintext_int, "x")
    if len(hex_plain) % 2:
        hex_plain = "0" + hex_plain
    return binascii.unhexlify(hex_plain)

def main() -> None:
    magic = [
        5787271386232140802415848037357292200492083882111971000129760788311089175930299376289161215874474715799351454070878582251687914775680761456101625297456892,
        5387606674726816082872610132875782527981170957076072680923994077089077976064392652252370277732171159642334409737331562019904590620888542541827717485113752,
        8626813144153450863326526978937642827960900471127853257361958103243078281538385888983439090031905533720665350648755896855476802807423703305517452660147355,
        1872979443975227995935637296750387505645616831379674309114728836574395312482706795529036206552423055700987377954505652312366332939354723406001342424122358,
        4931753853283648195589701767102112310944252190842102303652590403853615847306776280311251936851699971378590087509438123963034451272804781439556584435505901,
    ]
    N = 109074475661513195386347529878847653525066013979447623634672837526534779342254426211196990092087543057592914253366967405036738772402899175058372181938780141827862196403530817367346609634886009660373504705163832963810537444261419237976851935668770550613169673224960460503911295178003058365136612663341299983313
    e = 65537
    c = 17105155785407276085345997971088333947167848217427002799040362954041554640183792147706711255009531752373034539830942249185707384204560028872976040858835969379984356330875515755060870292949684300727962830885860251054647362624239983610820847460636592878264757476971385962718588508475554159060207702430258180509
    plaintext = decrypt_rsa_magic(magic, N, e, c)
    print(plaintext)

if __name__ == "__main__":
    main()