[🥉 Bronze 1] q = nextPrime(p) 한 줄로 무너진 자작 PGP — DreamHack Pretty Good Privacy 풀이

file extracted/* && cat extracted/enc.asc

gpg --list-packets extracted/enc.asc; gpg --list-packets extracted/pub.asc

python3 parse_pgp.py extracted/pub.asc extracted/enc.asc

n = a² − b² = (a − b)(a + b)

#!/usr/bin/env python3
"""q = nextPrime(p) 라 |p-q| 가 극히 작다 → Fermat 인수분해."""
from math import isqrt
import time
 
N = 78574622397097820678949935904930701355539503053568778574333582718520010791986457848131234051799716988383894120456993071770989011651678060403273301126723277989383156012898531112838853848487707804983112615122507562047566366611384489740128147950638551395991406841390176005369328690645540213230474384906309452863
 
t0 = time.time()
a = isqrt(N)
if a * a < N:
    a += 1
it = 0
while True:
    it += 1
    b2 = a * a - N
    b = isqrt(b2)
    if b * b == b2:
        break
    a += 1
p, q = a - b, a + b
assert p * q == N and p != 1
print(f"반복 횟수 = {it}   소요 = {time.time()-t0:.3f}s")
print(f"a = ceil(sqrt(N)) + {it-1}")
print(f"p = {p}")
print(f"q = {q}")
print(f"q - p = {q - p}")
print(f"p 비트수 = {p.bit_length()}, q 비트수 = {q.bit_length()}")

python3 factor.py

#!/usr/bin/env python3
"""문제 설명의 'q = nextPrime(p)' 가 실제로 그러한지 sympy 로 확인한다."""
from math import isqrt
from sympy import isprime, nextprime
from solve import read_pubkey, fermat
from pathlib import Path
 
n, e = read_pubkey(Path(__file__).resolve().parent / "extracted/pub.asc")
p, q, it = fermat(n)
print(f"p 소수?          {isprime(p)}")
print(f"q 소수?          {isprime(q)}")
print(f"p * q == n ?     {p * q == n}")
print(f"nextprime(p)==q ? {nextprime(p) == q}")
print(f"q - p            = {q - p}")
print(f"isqrt(n) - p     = {isqrt(n) - p}   (p 와 q 사이 딱 중간)")
print(f"Fermat 반복 횟수  = {it}")

python3 check_primes.py

d = pow(e, -1, (p - 1) * (q - 1) // gcd(p - 1, q - 1))   # λ(n) 기준

00 02 [0이 아닌 랜덤 패딩 …] 00 ‖ algo(1) ‖ session_key ‖ checksum(2)

python3 traps.py

#!/usr/bin/env python3
# Pretty Good Privacy (DreamHack Bronze 1, crypto) — 자체 완결 풀이
#
#   pub.asc 에서 n·e 를 뜯어내고 q = nextPrime(p) 라는 힌트대로 Fermat 으로 쪼갠 뒤,
#   PKESK 의 세션키를 RSA 로 풀고 SEIPD 를 OpenPGP-CFB 로 복호해 flag 를 꺼낸다.
#   외부 PGP 라이브러리를 쓰지 않고 RFC 4880 을 직접 구현했다.
import base64, hashlib, sys, zlib
from math import isqrt
from pathlib import Path
from Crypto.Cipher import AES, DES3
from Crypto.Cipher import CAST
 
HERE = Path(__file__).resolve().parent
 
# ── 1. ASCII Armor 해제 ──────────────────────────────────────────────
def unarmor(path):
    body, on = [], False
    for line in Path(path).read_text().splitlines():
        if line.startswith("-----BEGIN"):
            on = True; continue
        if line.startswith("-----END"):
            break
        if on and line.strip() and not line.startswith("="):
            body.append(line)
    return base64.b64decode("".join(body))
 
# ── 2. 패킷 분해 (new/old 두 형식 모두) ──────────────────────────────
def packets(buf):
    i = 0
    while i < len(buf):
        h = buf[i]; i += 1
        if not h & 0x80:
            raise ValueError(f"패킷 헤더가 아니다: {h:#x}")
        if h & 0x40:                                    # new format
            tag = h & 0x3f
            l = buf[i]; i += 1
            if l < 192:
                ln = l
            elif l < 224:
                ln = ((l - 192) << 8) + buf[i] + 192; i += 1
            elif l == 255:
                ln = int.from_bytes(buf[i:i+4], "big"); i += 4
            else:
                raise ValueError("부분 길이(partial body)는 다루지 않는다")
        else:                                           # old format
            tag = (h >> 2) & 0x0f
            nl = [1, 2, 4][h & 0x03]
            ln = int.from_bytes(buf[i:i+nl], "big"); i += nl
        yield tag, buf[i:i+ln]
        i += ln
 
def mpi(buf, off):
    bits = int.from_bytes(buf[off:off+2], "big")
    nb = (bits + 7) // 8
    return int.from_bytes(buf[off+2:off+2+nb], "big"), off + 2 + nb
 
# ── 3. 공개키에서 n, e ──────────────────────────────────────────────
def read_pubkey(path):
    for tag, d in packets(unarmor(path)):
        if tag == 6:
            assert d[0] == 4 and d[5] == 1, "v4 RSA 키가 아니다"
            n, off = mpi(d, 6)
            e, _ = mpi(d, off)
            return n, e
    raise ValueError("공개키 패킷 없음")
 
# ── 4. Fermat 인수분해 (p, q 가 붙어 있을 때만 성립) ────────────────
def fermat(n, rounds=1 << 20):
    a = isqrt(n)
    if a * a < n:
        a += 1
    for k in range(rounds):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b, k + 1
        a += 1
    raise ValueError("Fermat 실패 — p, q 가 충분히 가깝지 않다")
 
# ── 5. PKESK → 세션키 (EME-PKCS1-v1_5 언패딩) ───────────────────────
def session_key(pkesk, n, d):
    assert pkesk[0] == 3 and pkesk[9] == 1, "v3 RSA PKESK 가 아니다"
    c, _ = mpi(pkesk, 10)
    m = pow(c, d, n).to_bytes((n.bit_length() + 7) // 8, "big")
    assert m[0] == 0x00 and m[1] == 0x02, f"PKCS#1 v1.5 블록타입 불일치: {m[:2].hex()}"
    body = m[2:][m[2:].index(b"\x00") + 1:]          # 0x00 구분자 이후가 알맹이
    algo, key, chk = body[0], body[1:-2], int.from_bytes(body[-2:], "big")
    assert sum(key) % 65536 == chk, "세션키 체크섬 불일치"
    return algo, key
 
# ── 6. SEIPD 복호 (OpenPGP-CFB, IV=0, resync 없음) ──────────────────
BLOCK = {2: 8, 3: 8, 7: 16, 8: 16, 9: 16}
NAME  = {2: "3DES", 3: "CAST5", 7: "AES-128", 8: "AES-192", 9: "AES-256"}
 
def sym_decrypt(algo, key, seipd):
    assert seipd[0] == 1, "SEIPD v1 이 아니다"
    bs = BLOCK[algo]
    if algo == 2:
        c = DES3.new(key, DES3.MODE_CFB, iv=b"\x00" * bs, segment_size=bs * 8)
    elif algo == 3:
        c = CAST.new(key, CAST.MODE_CFB, iv=b"\x00" * bs, segment_size=bs * 8)
    else:
        c = AES.new(key, AES.MODE_CFB, iv=b"\x00" * bs, segment_size=bs * 8)
    pt = c.decrypt(seipd[1:])
    assert pt[bs-2:bs] == pt[bs:bs+2], "CFB 프리픽스 검사 실패 — 세션키가 틀렸다"
    body, mdc = pt[bs+2:-22], pt[-22:]
    assert mdc[:2] == b"\xd3\x14", "MDC 패킷이 아니다"
    assert hashlib.sha1(pt[:-20]).digest() == mdc[2:], "MDC(SHA-1) 불일치 — 변조됨"
    return body
 
# ── 7. 압축 해제 + Literal 패킷에서 본문 ────────────────────────────
def literal(body):
    for tag, d in packets(body):
        if tag == 8:                                    # Compressed Data
            algo = d[0]
            raw = d[1:]
            plain = (zlib.decompressobj(-15).decompress(raw) if algo == 1 else
                     zlib.decompress(raw) if algo == 2 else raw)
            return literal(plain)
        if tag == 11:                                   # Literal Data
            nl = d[1]
            fname = d[2:2+nl].decode(errors="replace")
            return fname, d[2+nl+4:]
    raise ValueError("Literal 패킷 없음")
 
# ── 실행 ────────────────────────────────────────────────────────────
def main():
    n, e = read_pubkey(HERE / "extracted/pub.asc")
    print(f"[+] n = {n}")
    print(f"[+] e = {e}  ({n.bit_length()} bit)")
 
    p, q, it = fermat(n)
    print(f"[+] Fermat {it}회 만에 분해, q - p = {q - p}")
    print(f"[+] p = {p}")
    print(f"[+] q = {q}")
 
    d = pow(e, -1, (p - 1) * (q - 1) // __import__("math").gcd(p - 1, q - 1))
    print(f"[+] d = {d}")
 
    pkesk = seipd = None
    for tag, data in packets(unarmor(HERE / "extracted/enc.asc")):
        if tag == 1:  pkesk = data
        if tag == 18: seipd = data
 
    algo, key = session_key(pkesk, n, d)
    print(f"[+] 세션 대칭키: {NAME[algo]} / {key.hex()}")
 
    fname, data = literal(sym_decrypt(algo, key, seipd))
    print(f"[+] 원본 파일명 = {fname!r}")
    print()
    print(data.decode(errors="replace").strip())
 
if __name__ == "__main__":
    main()

python3 solve.py

#!/usr/bin/env python3
"""쪼갠 p, q 로 OpenPGP v4 비밀키 패킷을 조립해 sec.asc 를 만든다.
 
pub.asc 의 UserID·자체서명 패킷은 그대로 두고 공개키 패킷(tag 6)만
비밀키 패킷(tag 5)으로 바꿔 끼운다 — 서명 대상(키 재료 + UserID)이
그대로라 자체서명이 계속 유효하고, gpg 가 정상 키로 받아 준다.
"""
import base64
from pathlib import Path
from solve import unarmor, packets, mpi, read_pubkey, fermat
 
HERE = Path(__file__).resolve().parent
 
def to_mpi(x):
    b = x.to_bytes((x.bit_length() + 7) // 8, "big")
    return x.bit_length().to_bytes(2, "big") + b
 
def new_packet(tag, body):
    """new-format 헤더로 패킷 하나를 감싼다."""
    if len(body) < 192:
        ln = bytes([len(body)])
    elif len(body) < 8384:
        v = len(body) - 192
        ln = bytes([(v >> 8) + 192, v & 0xFF])
    else:
        ln = b"\xff" + len(body).to_bytes(4, "big")
    return bytes([0xC0 | tag]) + ln + body
 
CRC24_INIT, CRC24_POLY = 0xB704CE, 0x1864CFB
def crc24(data):
    crc = CRC24_INIT
    for b in data:
        crc ^= b << 16
        for _ in range(8):
            crc <<= 1
            if crc & 0x1000000:
                crc ^= CRC24_POLY
    return crc & 0xFFFFFF
 
def armor(kind, data):
    b64 = base64.b64encode(data).decode()
    lines = [b64[i:i+64] for i in range(0, len(b64), 64)]
    chk = base64.b64encode(crc24(data).to_bytes(3, "big")).decode()
    return (f"-----BEGIN PGP {kind}-----\n\n" + "\n".join(lines) +
            f"\n={chk}\n-----END PGP {kind}-----\n")
 
n, e = read_pubkey(HERE / "extracted/pub.asc")
p, q, _ = fermat(n)
assert p < q                                   # OpenPGP 는 p < q, u = p^-1 mod q
d = pow(e, -1, (p - 1) * (q - 1))
u = pow(p, -1, q)
 
out = b""
for tag, body in packets(unarmor(HERE / "extracted/pub.asc")):
    if tag == 6:
        secret = to_mpi(d) + to_mpi(p) + to_mpi(q) + to_mpi(u)
        secret += (sum(secret) % 65536).to_bytes(2, "big")   # S2K usage 0 → 단순 합 체크섬
        out += new_packet(5, body + b"\x00" + secret)        # 0x00 = 암호화하지 않음
    else:
        out += new_packet(tag, body)
 
(HERE / "sec.asc").write_text(armor("PRIVATE KEY BLOCK", out))
print(f"sec.asc 생성 완료 ({len(out)} bytes, 패킷 tag 5/13/2)")

rm -rf gnupg && mkdir -m 700 gnupg && python3 make_seckey.py && GNUPGHOME=$PWD/gnupg gpg --batch --import sec.asc && GNUPGHOME=$PWD/gnupg gpg --batch --decrypt extracted/enc.asc

#!/usr/bin/env bash
# Pretty Good Privacy (DreamHack Bronze 1, crypto) — 한 방 재현.
#   ① 순수 파이썬 풀이(solve.py)로 flag 를 뽑고
#   ② 재구성한 비밀키를 진짜 gpg 에 물려 같은 값이 나오는지 교차검증한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
# 기대값: sync_nas.sh 가 만든 문제.json 이 있으면 그걸, 없으면 제출로 확인된 값을 쓴다.
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null \
         || echo 'acsc{RSA is fine, unless you implement it badly}')
 
echo "=== ① 순수 파이썬 (RFC 4880 직접 구현) ==="
OUT=$(timeout 300 python3 solve.py 2>&1) || true
echo "$OUT" | tail -6
FLAG=$(printf '%s' "$OUT" | grep -aoE 'acsc\{[^}]+\}' | head -1)
 
echo
echo "=== ② gpg 교차검증 (재구성한 비밀키) ==="
rm -rf gnupg && mkdir -m 700 gnupg
python3 make_seckey.py
GNUPGHOME=$PWD/gnupg gpg --batch --quiet --import sec.asc
GOUT=$(GNUPGHOME=$PWD/gnupg gpg --batch --decrypt extracted/enc.asc 2>&1) || true
echo "$GOUT" | tail -4
GFLAG=$(printf '%s' "$GOUT" | grep -aoE 'acsc\{[^}]+\}' | head -1)
 
echo
if [ -n "$FLAG" ] && [ "$FLAG" = "$EXPECT" ] && [ "$GFLAG" = "$EXPECT" ]; then
  echo "✅ PASS  $FLAG   (파이썬·gpg 양쪽 일치)"; exit 0
fi
echo "❌ FAIL (python='${FLAG:-없음}' / gpg='${GFLAG:-없음}' / 기대='$EXPECT')"; exit 1

./reproduce.sh