[🥈 Silver 4] 소수를 모듈러로 쓴 제곱 PRNG에서 시드 되찾기 — DreamHack the present 풀이

ls -l extracted && file extracted/*

cat extracted/prob.py

from Crypto.Util.number import *
 
flag = bytes_to_long(b'DH{?????????????????????????????????????????????}')
 
class PRNG():
    def __init__(self, seed):
        self.seed = seed
        self.M = getStrongPrime(512)
 
    def next(self):
        self.seed = self.seed ** 2 % self.M
        return self.seed
 
 
 
prng = PRNG(flag)
 
prng.next()
print(f'M = {prng.M}')
print(f'rand = {prng.next()}')

cat extracted/output.txt

openssl prime $(grep -oP "(?<=M = )\d+" extracted/output.txt)

r  = a^((M+1)/4) mod M
r² = a^((M+1)/2) = a · a^((M-1)/2) = a · 1 = a      (a 가 이차잉여일 때)

#!/usr/bin/env python3
"""the present (DreamHack, Silver 4, crypto) — flag 복구
 
prob.py 는 flag 를 정수로 만들어 PRNG 의 seed 로 넣고 next() 를 두 번 부른다.
next() 가 seed <- seed^2 mod M 이므로 출력된 rand 는 flag^4 mod M 이다.
M 이 getStrongPrime(512) 로 만든 '소수'라서 4제곱근은 곧바로 계산된다.
 
M % 4 == 3 이면 QR x 의 제곱근이 x^((M+1)/4) mod M 로 한 번에 나오고,
-1 이 비잉여라 {s, M-s} 중 정확히 하나만 다시 QR 이 된다. 그 하나만 따라가면
4제곱근 후보는 두 개(t, M-t)뿐이라 브루트포스가 필요 없다.
"""
import re
import pathlib
from Crypto.Util.number import long_to_bytes
 
HERE = pathlib.Path(__file__).resolve().parent
OUT = HERE / "extracted" / "output.txt"
 
 
def load_output(path):
    """output.txt 에서 M 과 rand 를 읽는다."""
    text = path.read_text()
    M = int(re.search(r"M\s*=\s*(\d+)", text).group(1))
    rand = int(re.search(r"rand\s*=\s*(\d+)", text).group(1))
    return M, rand
 
 
def is_qr(x, p):
    """오일러 판정법: x 가 p 의 이차잉여인가."""
    return pow(x, (p - 1) // 2, p) == 1
 
 
def sqrt_mod_p3mod4(x, p):
    """p % 4 == 3 인 소수에서 x 의 제곱근 두 개. QR 이 아니면 빈 리스트."""
    if x % p == 0:
        return [0]
    if not is_qr(x, p):
        return []
    r = pow(x, (p + 1) // 4, p)
    return [r, p - r]
 
 
def fourth_roots(x, p):
    """x 의 4제곱근 전부 (p % 4 == 3 가정)."""
    roots = []
    for s in sqrt_mod_p3mod4(x, p):
        roots += sqrt_mod_p3mod4(s, p)
    return sorted(set(roots))
 
 
def main():
    M, rand = load_output(OUT)
    assert M % 4 == 3, "이 스크립트는 M mod 4 == 3 전용 지름길을 쓴다"
    print(f"[*] M    ({M.bit_length()}비트, M mod 4 = {M % 4}) = {M}")
    print(f"[*] rand ({rand.bit_length()}비트) = {rand}")
    print(f"[*] rand 는 이차잉여인가? {is_qr(rand, M)}")
 
    roots = fourth_roots(rand, M)
    print(f"[*] 4제곱근 후보 {len(roots)}개")
    flag = None
    for i, t in enumerate(roots):
        raw = long_to_bytes(t)
        ok = pow(t, 4, M) == rand  # 문제의 암호화를 그대로 되돌려 자체 검증
        printable = all(32 <= c < 127 for c in raw)
        head = raw[:16] if printable else raw[:16].hex()
        print(f"    [{i}] {t.bit_length():3d}비트  검산={ok}  출력가능={printable}  앞부분={head}")
        if ok and printable and raw.startswith(b"DH{") and raw.endswith(b"}"):
            flag = raw.decode()
 
    if flag:
        print(f"\n[+] FLAG = {flag}")
    else:
        print("\n[-] 조건을 만족하는 후보가 없다")
 
 
if __name__ == "__main__":
    main()

python3 solve.py

# verify.sage — SageMath 로 독립 검증
#  1) M 이 정말 소수인가 (소수면 제곱근이 다항시간에 계산된다)
#  2) rand 의 4제곱근을 Sage 의 nth_root 로 전부 구해 solve.py 결과와 대조
 
M = 12045184283108733282877246918018456795629932264538806786957088609817236359725183272225617590814403324378457302095025664842376149624271113548645334599894051
rand = 321609188014782817530081099017386870899897457530475334351599692725892773281779472409503390776505529932157130216692885548245652532540341302761980076422023
 
print("is_prime(M)      =", is_prime(M))
print("M.nbits()        =", Integer(M).nbits())
print("M mod 4          =", M % 4)
print("rand is QR       =", kronecker(rand, M) == 1)
 
roots = Integers(M)(rand).nth_root(4, all=True)
print("네제곱근 개수     =", len(roots))
 
for r in sorted(Integer(x) for x in roots):
    raw = int(r).to_bytes((r.nbits() + 7) // 8, "big")
    ok = power_mod(int(r), 4, M) == rand
    tag = raw.decode() if all(32 <= c < 127 for c in raw) else raw.hex()
    print(f"  {r.nbits():3d}비트  네제곱_검산:{ok}  ->  {tag}")

sage verify.sage

#!/usr/bin/env bash
# the present (DreamHack Silver 4, crypto) — 한 방 재현.
#   extracted/output.txt 의 (M, rand) 만으로 flag 를 복원하고 정답과 대조한다.
#   외부 서버·VM 이 필요 없는 완전 오프라인 문제라 이 스크립트만으로 끝난다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || echo '')
 
python3 -c "import Crypto" 2>/dev/null || { echo "pycryptodome 이 필요하다: pip install pycryptodome"; exit 1; }
 
OUT=$(timeout 120 python3 solve.py 2>&1) || true
 
echo "$OUT" | tail -8
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
if [ -n "$FLAG" ] && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh