문제: DreamHack 워게임 — pprintable 분류: crypto 난이도: 💠 Platinum 4 FLAG:
GoN{This_Flag_iS_cOnSTrUcTEd_wITh_pURe_ASCII_lATTers_aNd_IT_also_RSA_seCert_P_and_Q_so_we_nEEd_some_Gibberish_like__aPelDKfjpNXiAHIFudNEKsM__iNcLuded_becAUse_p_and_q_ShOuld_be_prIme_nuMBer_sORRy_for_the_inCONvenIEncE_but_i_tHINk_THIs_is_SUpEr_cOol_iSnT_it}
문제 설명은 두 줄이 전부다.
p says he wants to be a printable!
(and q also wants to just because for his friend. how adorable :>)소수 p 가 printable 이 되고 싶다는 말장난인데, 이게 문제 이름이자 풀이의 전부다.
받은 파일은 두 개뿐이라 먼저 그것부터 확인했다.
ls -l extracted && file extracted/* && wc -c extracted/*
문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | pprintable (DreamHack 워게임 #589) |
| 난이도 | 💠 Platinum 4 |
| 분류 | crypto |
| 출제 | c0m0r1 · 2022-08-22 공개 |
| 제공 파일 | chal.py (출제 스크립트), out.txt (출력값 7줄) |
| 서버 | 없음 — 파일만으로 완결된다 |
| 핵심 기법 | RSA 부분키 노출 + branch-and-prune, 부족한 정보는 평문 문자 집합으로 메우기 |
흐름은 이렇다. 플래그 256글자를 앞뒤로 반씩 잘라 그대로 1024비트 소수 p, q 로 쓰고
N = p*q 를 공개한다. 그리고 p, q 의 비트를 랜덤 마스크로 35% 정도만 남긴 채 같이 준다.
부분키 복원 알고리즘이 요구하는 비율에는 한참 못 미치는데, 그 간격을 메우는 정보가 문제 안에 이미 들어 있다. 플래그가 문자열이라는 것 자체다.
🧩 배경 — 플래그를 그대로 소수로 쓴 RSA
chal.py 는 짧다. 전문을 그대로 옮긴다.
from secret import flag
import string
from gmpy2 import *
from random import SystemRandom
SIZE = 2048
# read flag and construct RSA p, q
assert(len(flag) == SIZE // 8)
assert(all(c in string.ascii_letters or c in ['{', '}', '_'] for c in flag))
p = int.from_bytes(flag[:SIZE // 2 // 8].encode(), byteorder = "big")
q = int.from_bytes(flag[SIZE // 2 // 8:].encode(), byteorder = "big")
assert(is_prime(p))
assert(is_prime(q))
# generate textbook RSA key
N = p*q
phi = (p - 1) * (q - 1)
e = 0x10001
d = int(gmpy2.invert(e, phi))
pt = int.from_bytes(b"flag{this_is_fake_flag_:P}", byteorder = "big")
ct = pow(pt, e, N)
# generate random mask and redact p,q
p_mask = 0
q_mask = 0
cryptogen = SystemRandom()
for i in range(SIZE // 2):
# the SOTA paper says u need 50%
# not a chance :p
if cryptogen.random() < 0.35:
p_mask |= 1
if cryptogen.random() < 0.35:
q_mask |= 1
p_mask <<= 1
q_mask <<= 1
p_redacted = p & p_mask
q_redacted = q & q_mask
print("N : 0x%x"%N)
print("e : 0x%x"%e)
print("p_redacted : 0x%x"%p_redacted)
print("p_mask : 0x%x"%p_mask)
print("q_redacted : 0x%x"%q_redacted)
print("q_mask : 0x%x"%q_mask)
print("ct : 0x%x"%ct)읽고 나면 구조가 다 보인다.
SIZE = 2048 이니 플래그는 256글자다. 앞 128글자를 빅엔디언 정수로 만든 게 p,
뒤 128글자가 q. 둘 다 소수여야 한다는 assert 가 걸려 있으니, 출제자는 조건을
만족하는 문장이 나올 때까지 플래그 문구를 갈아 끼웠을 것이다.
실제로 복원된 플래그 중간에 뜻 없는 aPelDKfjpNXiAHIFudNEKsM 같은 덩어리가 끼어 있는데,
그게 소수를 맞추려고 넣은 자리다. 플래그 본문에도 그렇게 적혀 있다.
ct 는 미끼다. 암호화한 평문이 flag{this_is_fake_flag_:P} 라고 코드에 그대로 박혀 있다.
복호화해 봐야 진짜 플래그가 나오지 않는다. 다만 나중에 복원한 소인수가 맞는지 검산하는 데는
쓸모가 있다 — 우리가 구한 p, q 로 개인키를 만들어 ct 를 풀었을 때 저 가짜 평문이
나오면 인수분해가 맞은 것이다.
진짜 핵심은 마지막 마스크 루프다. 비트마다 35% 확률로 마스크를 켜고, p_redacted = p & p_mask
로 그 자리의 비트만 남긴 채 공개한다. 주석까지 도발적이다.
# the SOTA paper says u need 50%
# not a chance :p여기서 말하는 논문이 Heninger 와 Shacham 의 Reconstructing RSA Private Keys from Random Key Bits (CRYPTO 2009) 다. 아래에서 다시 다룬다.
out.txt 는 그 print 문들의 출력이라 일곱 줄인데, 한 줄이 500자를 넘는다.
줄 앞머리만 잘라서 보면 형식이 바로 보인다.
cut -c1-108 extracted/out.txt
🔬 정찰 — 받은 값이 실제로 어떤 모양인가
숫자를 눈으로 보는 것보다 재 보는 게 빠르다. 파싱해서 비트 단위 통계를 찍는 스크립트를 만들었다.
#!/usr/bin/env python3
"""out.txt 에 실려 온 값들이 실제로 어떤 모양인지 재 본다."""
from pathlib import Path
HERE = Path(__file__).resolve().parent
vals = {}
for line in (HERE / "extracted" / "out.txt").read_text().strip().splitlines():
key, _, val = line.partition(":")
vals[key.strip()] = int(val.strip(), 16)
N, e, ct = vals["N"], vals["e"], vals["ct"]
print(f"[N] {N.bit_length()} bits (p, q 가 각각 1024비트면 2048 이어야 하는데 2045)")
print(f"[e] {hex(e)}")
print(f"[ct] {ct.bit_length()} bits")
print()
for name in ("p", "q"):
mask = vals[f"{name}_mask"]
red = vals[f"{name}_redacted"]
known = bin(mask).count("1")
print(f"[{name}] 공개 비트 {known}/1024 = {known / 10.24:.2f}%")
print(f" mask 최상위 비트 위치 : {mask.bit_length() - 1} (1024비트인데 1024번 비트가 산다)")
print(f" mask 의 bit0 : {mask & 1} (루프 끝 << 때문에 LSB 는 절대 안 알려준다)")
print(f" redacted & ~mask == 0 : {red & ~mask == 0} (마스크 밖은 전부 0 — 정상)")
print()
print("[참고] Heninger-Shacham(CRYPTO 2009)이 요구하는 최소 공개 비율 : 약 57%")
print("[참고] 지금 가진 것 : 35.16%")python3 params.py
여기서 네 가지가 잡힌다.
N 이 2048비트가 아니라 2045비트다. p, q 가 각각 1024비트짜리 랜덤 소수라면
곱은 2047~2048비트가 나와야 한다. 그런데 p 의 최상위 바이트는 플래그의 첫 글자,
즉 ASCII 대문자다. 어떤 영문자든 0x80 미만이라 최상위 비트가 0이고,
그래서 p 도 q 도 실제로는 1023비트다. 곱이 2045비트인 게 자연스럽다.
플래그가 문자열이라는 사실이 N 의 비트 수에서부터 새어 나온다.
공개된 비트는 정확히 360개, 35.16%다. 코드의 0.35 와 맞는다.
마스크의 0번 비트는 항상 0이다. 루프가 p_mask |= 1 로 최하위 비트를 켠 다음
p_mask <<= 1 로 밀기 때문에, 마지막 시프트가 0번 자리를 비운 채 끝난다.
그래서 마스크는 1번부터 1024번 비트에 걸쳐 있고, p 의 최하위 비트만은 절대 알려주지 않는다.
다행히 그 한 비트는 공짜로 안다 — p 가 소수라 홀수다.
마스크 비트 몇 개는 헛돈다. 마스크 최상위가 1024번 비트인데 p 는 1023비트라,
p 에 존재하지도 않는 자리에 마스크가 걸린 경우가 있다. 세어 보니 p 쪽 1개, q 쪽 2개다.
360개 중 몇 개는 정보가 아니라는 뜻인데, 어차피 우리 탐색은 그 자리를 printable 조건으로
따로 막으므로 실질 손해는 없다.
격자는 쓸 수 없다
RSA 부분 정보 문제를 보면 먼저 Coppersmith 를 떠올리게 된다.
p 의 상위 절반을 안다면 N 에 대한 작은 근 찾기로 나머지를 뽑을 수 있다.
그런데 여기서는 못 쓴다. 아는 비트가 연속 블록이 아니라 전 구간에 흩뿌려져 있다. Coppersmith 계열은 "미지수가 하나이고 그 크기가 작다"는 형태로 정리돼야 하는데, 1024비트 전역에 664개의 구멍이 랜덤하게 뚫린 상태는 그렇게 정리되지 않는다. 미지 비트를 각각 변수로 두면 변수가 664개짜리 다변수 문제가 되고, 격자로 다룰 크기를 넘는다.
그래서 접근이 달라진다. 대수적으로 한 방에 푸는 대신, 낮은 자리부터 한 비트씩 세워 나가면서 말이 안 되는 가지를 쳐내는 쪽이다.
🧱 배경 — 왜 낮은 자리부터인가
p*q = N 이라는 등식은 mod 2^k 로 잘라도 그대로 성립한다.
p · q ≡ N (mod 2^k)곱셈의 자리올림은 낮은 자리에서 높은 자리로만 흐른다. 그래서 p 와 q 의 하위 k비트만
정해지면 곱의 하위 k비트가 완전히 결정된다. 상위 비트가 뭐든 영향을 주지 않는다.
반대로 최상위부터 세우려 하면, 아직 정하지 않은 하위 비트에서 올라오는 자리올림 때문에
검증 자체가 안 된다. LSB 부터 가야 하는 이유가 이것이다.
이제 한 걸음을 정확히 써 보자. p ≡ p_i (mod 2^i), q ≡ q_i (mod 2^i) 까지 확정했고
이 둘이 p_i * q_i ≡ N (mod 2^i) 를 만족한다고 하자. 다음 비트를 a, b 라 두면
p = p_i + a·2^i + (더 높은 자리)
q = q_i + b·2^i + (더 높은 자리)이고, mod 2^(i+1) 에서 2^i 보다 높은 항은 전부 사라지므로
p·q ≡ p_i·q_i + 2^i·(a·q_i + b·p_i) (mod 2^(i+1))가 된다. p 와 q 는 홀수라 p_i, q_i 도 홀수다. 따라서 a*q_i + b*p_i ≡ a + b (mod 2) 이고,
결국 다음 비트가 만족해야 할 조건은 딱 하나로 줄어든다.
a + b ≡ (N - p_i·q_i) / 2^i (mod 2)우변을 c 라 하면 가능한 (a, b) 는 (0, c) 와 (1, 1-c) 둘뿐이다.
비트 하나를 전진할 때마다 후보가 정확히 두 갈래로 갈린다.
우변은 코드에서 ((N - pl*ql) >> i) & 1 한 줄이다. 불변식 덕분에 N - p_i*q_i 는
항상 2^i 로 나누어떨어지고, 파이썬의 음수 우측 시프트가 무한 정밀도 2의 보수처럼
동작해서 뺄셈 결과가 음수여도 이 식이 그대로 맞는다.
그럼 어디서 쳐내나
갈라진 두 갈래를 줄이는 게 공개된 비트다. p_mask 의 i번 비트가 켜져 있으면 a 는
p_redacted 의 그 비트값이어야 한다. 두 갈래는 a 값이 서로 다르므로, 한쪽이 즉시 죽는다.
q 쪽도 마찬가지다.
이게 Heninger-Shacham 의 branch-and-prune 이다. 그리고 이 알고리즘이 언제 성립하는지에 대한
답이 논문에 있다. 잘못된 가지 하나를 따라가면 매 비트마다 두 갈래로 늘어나고,
각 갈래는 p 쪽 마스크에 걸려 죽을 확률과 q 쪽 마스크에 걸려 죽을 확률을 각각 가진다.
공개 비율을 δ 라 하면 잘못된 가지의 기대 증식률은
2 · (1 - δ/2)^2이고, 이 값이 1보다 작아야 탐색이 끝난다. 풀면 δ > 0.5858 이다. 논문은 더 정밀하게 세어 0.57 을 제시한다. 어느 쪽이든 우리가 가진 35.16% 는 한참 모자란다.
출제자 주석의 not a chance :p 가 이걸 가리킨다. 정공법으로는 안 된다.
🐛 삽질 — 정말 안 되는지 돌려 봤다
계산으로는 안 된다고 나왔지만, 계산이 틀렸을 수도 있으니 실제로 돌려 확인했다. 제약을 하나씩 끄고 실행할 수 있게 실험용 스크립트를 따로 만들었다.
#!/usr/bin/env python3
"""
제약을 하나씩 빼고 branch-and-prune 을 돌려 본다 — 왜 둘 다 필요한지 보려고.
--mode mask : 마스크만 (= 원조 Heninger-Shacham). printable 검사 없음
--mode printable : printable 만. 공개 비트 무시
--mode both : 둘 다 (solve.py 와 같은 조건)
후보가 --cap 을 넘으면 거기서 멈추고 몇 번째 비트에서 터졌는지 보고한다.
"""
import argparse
import string
from pathlib import Path
HERE = Path(__file__).resolve().parent
ALLOWED = {ord(c) for c in string.ascii_letters} | {ord(c) for c in "{}_"}
LOWOK = [None] + [{v & ((1 << j) - 1) for v in ALLOWED} for j in range(1, 9)]
ap = argparse.ArgumentParser()
ap.add_argument("--mode", choices=("mask", "printable", "both"), default="mask")
ap.add_argument("--cap", type=int, default=200000)
ap.add_argument("--bits", type=int, default=1024)
args = ap.parse_args()
vals = {}
for line in (HERE / "extracted" / "out.txt").read_text().strip().splitlines():
k, _, v = line.partition(":")
vals[k.strip()] = int(v.strip(), 16)
N = vals["N"]
use_mask = args.mode in ("mask", "both")
use_pr = args.mode in ("printable", "both")
p_mask = vals["p_mask"] if use_mask else 0
q_mask = vals["q_mask"] if use_mask else 0
p_red, q_red = vals["p_redacted"], vals["q_redacted"]
print(f"mode={args.mode} (마스크 {'사용' if use_mask else '무시'}, "
f"printable {'사용' if use_pr else '무시'}) cap={args.cap}")
cands = [(1, 1)]
for i in range(1, args.bits):
nxt = []
j, base = (i % 8) + 1, i - (i % 8)
ok = LOWOK[j]
pk, pb = (p_mask >> i) & 1, (p_red >> i) & 1
qk, qb = (q_mask >> i) & 1, (q_red >> i) & 1
for pl, ql in cands:
carry = ((N - pl * ql) >> i) & 1
for a in (0, 1):
if pk and a != pb:
continue
b = carry ^ a
if qk and b != qb:
continue
np_ = pl | (a << i)
nq_ = ql | (b << i)
if use_pr:
if ((np_ >> base) & ((1 << j) - 1)) not in ok:
continue
if ((nq_ >> base) & ((1 << j) - 1)) not in ok:
continue
nxt.append((np_, nq_))
cands = nxt
if i % 8 == 7:
print(f" bit {i + 1:4d} : 후보 {len(cands):8d}")
if len(cands) > args.cap:
# 터지는 것도 이 실험의 결과다 — 에러가 아니므로 0 으로 끝낸다
print(f"\n>>> bit {i + 1} 에서 후보 {len(cands)}개 — cap 초과, 중단")
print(">>> 이 추세면 1024비트까지 못 간다")
raise SystemExit(0)
if not cands:
print(f"\n>>> bit {i + 1} 에서 후보 전멸")
raise SystemExit(2)
print(f"\n>>> 끝까지 감. 최종 후보 {len(cands)}개")
for p, q in cands:
if p * q == N:
print(">>> p*q == N 인 해가 있다")▶🐛 삽질 — 마스크만으로, 그리고 printable 만으로 각각 돌려 본 결과
먼저 원조 방식 그대로, 공개된 비트만 가지고 돌렸다.
python3 naive_bnp.py --mode mask --cap 200000
64비트를 세우는 데 후보가 이미 7만 개를 넘고, 70비트에서 30만 개를 찍고 멈춘다. 8비트마다 대략 11배씩 불어나는 셈이라 예측한 증식률과 맞는다. 1024비트는 꿈도 못 꾼다.
반대로 마스크를 무시하고 printable 조건만 쓰면 어떨까. 이쪽이 더 빨리 터진다.
python3 naive_bnp.py --mode printable --cap 200000
37비트 만에 24만 개다. 당연하다. 마스크가 없으면 매 비트가 무조건 두 갈래로 갈라지므로 바이트당 256배로 늘고, 바이트 경계에서 55/256 로 깎아 봐야 순 증가율이 11배가 넘는다.
둘 중 어느 하나만으로는 안 된다는 게 여기서 확정됐다. 그러니 둘을 겹쳐야 한다.
💣 핵심 — 문자 집합이 메우는 22%
chal.py 의 두 번째 assert 를 다시 본다.
assert(all(c in string.ascii_letters or c in ['{', '}', '_'] for c in flag))플래그의 모든 글자가 영문 대소문자 52개, 그리고 {, }, _ 안에 있어야 한다.
전부 합쳐 55종이다. 그런데 p 와 q 는 그 플래그 바이트를 그대로 읽은 정수다.
즉 p 의 128바이트 하나하나가 이 55종 중 하나여야 한다.
이게 얼마나 강한 조건인지 계산해 봤다.
#!/usr/bin/env python3
"""chal.py 의 assert 가 허용하는 문자 집합이 얼마나 좁은지 계산한다."""
import string
ALLOWED = sorted({ord(c) for c in string.ascii_letters} | {ord(c) for c in "{}_"})
print(f"허용 문자 수 : {len(ALLOWED)} / 256")
print(f"바이트 값 범위 : {min(ALLOWED)} ~ {max(ALLOWED)} (0x{min(ALLOWED):02x} ~ 0x{max(ALLOWED):02x})")
print(f"최상위 비트가 1인 값 : {[v for v in ALLOWED if v & 0x80]} ← 하나도 없다")
print()
# 하위 j비트만 확정됐을 때 남는 패턴 수 = 바이트 경계 전에도 쳐낼 수 있는가
print("하위 j비트만 정해졌을 때 살아남는 패턴 / 전체")
for j in range(1, 9):
pats = {v & ((1 << j) - 1) for v in ALLOWED}
print(f" j={j}: {len(pats):3d} / {1 << j:3d} 생존률 {len(pats) / (1 << j) * 100:5.1f}%")
print()
# 비트 하나당 후보 증가율 vs 바이트당 감소율
known = 0.3516
grow = 2 * (1 - known * 0.5) ** 2
print(f"비트 1개 전진 시 후보 배율 : 2 x (1 - 0.3516/2)^2 = {grow:.4f} (1 보다 크다 = 발산)")
print(f"8비트(1바이트) 누적 : {grow ** 8:.2f} 배")
print(f"바이트 경계 printable 검사 : (55/256)^2 = {(55 / 256) ** 2:.5f} 배")
print(f"→ 바이트당 최종 배율 : {grow ** 8 * (55 / 256) ** 2:.4f} (1 보다 작다 = 수렴)")python3 charset.py
숫자가 딱 맞아떨어진다.
마스크만 쓸 때 비트당 증식률은 1.3586 이고, 8비트를 가면 11.61배가 된다.
그런데 바이트가 완성되는 순간 그 바이트는 55/256, 즉 21.5% 확률로만 살아남는다.
p 와 q 양쪽에 걸리니 0.0462배다. 곱하면 바이트당 0.5358배 —
1보다 작으니 후보 집합이 커지지 않는다.
즉 부족했던 22%p 를 암호학이 아니라 플래그의 문자 집합이 메운다.
문제 이름 pprintable 이 그대로 답이었던 셈이다.
출력의 j 표를 보면 바이트 경계까지 기다릴 필요도 없다는 걸 알 수 있다. 하위 4비트까지는 모든 패턴이 가능해서 못 쳐내지만, 5비트부터 90.6%, 6비트 85.9%, 7비트에서 43.0% 로 급격히 좁아진다. 7비트에서 확 줄어드는 이유는 55종이 128가지 패턴 중 55개만 차지하기 때문이고, 8비트째에 21.5% 로 다시 반이 되는 건 최상위 비트가 반드시 0이어야 해서다. 그래서 구현에서는 바이트를 다 채우기 전에도 매 비트마다 부분 검사를 건다. 최종 결과는 같지만 중간에 들고 있는 후보 수가 줄어든다.

🎯 구현 — solve.py
세울 것은 다 세웠으니 코드로 옮긴다. 상태는 (p mod 2^i, q mod 2^i) 쌍의 리스트 하나면 된다.
비트마다 두 갈래로 늘리고, 마스크 두 개와 printable 한 개로 거른다.
#!/usr/bin/env python3
"""
pprintable (DreamHack #589, Platinum 4, crypto) — solver
주어진 것: N, e, ct, p_redacted, p_mask, q_redacted, q_mask (extracted/out.txt)
목표: flag (256자). p = int(flag[:128]), q = int(flag[128:]) 이므로
p, q 를 복원하면 그대로 flag 가 된다.
핵심:
1) p*q = N 이므로 LSB 부터 k비트씩 확정해 나가면
p*q ≡ N (mod 2^k) 라는 관계가 매 비트마다 후보를 2개로 묶어 준다.
2) 마스크로 공개된 비트(35.16%)가 그 2개 중 하나를 자주 쳐낸다.
— 이것만으로는 부족하다(Heninger–Shacham 은 ~57% 를 요구).
3) 부족분은 "flag 의 모든 바이트가 printable(ascii_letters + { } _ = 55종)"
이라는 제약이 메운다. 바이트 경계마다 55/256 만 살아남으므로
8비트에 한 번씩 후보가 크게 줄어든다.
실행: python3 solve.py (extracted/out.txt 를 읽는다)
python3 solve.py --quiet (바이트별 후보수 로그 생략)
"""
import argparse
import string
import sys
import time
from pathlib import Path
HERE = Path(__file__).resolve().parent
OUT = HERE / "extracted" / "out.txt"
# ── chal.py 의 assert 와 같은 문자 집합 (55종) ───────────────────────────────
ALLOWED = {ord(c) for c in string.ascii_letters} | {ord(c) for c in "{}_"}
# 바이트를 LSB 쪽부터 j비트만 확정했을 때 가능한 하위 j비트 패턴
# (바이트 경계 전에도 미리 쳐내려고 미리 만들어 둔다)
LOWOK = [None] + [{v & ((1 << j) - 1) for v in ALLOWED} for j in range(1, 9)]
def parse_out(path):
vals = {}
for line in path.read_text().strip().splitlines():
key, _, val = line.partition(":")
vals[key.strip()] = int(val.strip(), 16)
return vals
def recover(N, p_red, p_mask, q_red, q_mask, nbits=1024,
verbose=True, log_every=8, trace=None):
"""LSB 부터 한 비트씩 branch-and-prune. (p mod 2^i, q mod 2^i) 쌍을 들고 간다."""
# bit 0: N 이 홀수이므로 p, q 모두 홀수
cands = [(1, 1)]
peak = 1
hist = []
t0 = time.time()
for i in range(1, nbits):
nxt = []
j = (i % 8) + 1 # 지금 바이트에서 확정되는 비트 수
base = i - (i % 8) # 지금 바이트의 시작 비트 위치
ok = LOWOK[j]
pm_known = (p_mask >> i) & 1
pm_bit = (p_red >> i) & 1
qm_known = (q_mask >> i) & 1
qm_bit = (q_red >> i) & 1
for pl, ql in cands:
# p*q ≡ N (mod 2^(i+1)) 를 만족시키려면 a + b ≡ carry (mod 2)
carry = ((N - pl * ql) >> i) & 1
for a in (0, 1):
if pm_known and a != pm_bit:
continue
b = carry ^ a
if qm_known and b != qm_bit:
continue
np_ = pl | (a << i)
if ((np_ >> base) & ((1 << j) - 1)) not in ok:
continue
nq_ = ql | (b << i)
if ((nq_ >> base) & ((1 << j) - 1)) not in ok:
continue
nxt.append((np_, nq_))
cands = nxt
peak = max(peak, len(cands))
if i % 8 == 7:
byte_no = (i + 1) // 8
hist.append((byte_no, len(cands)))
if verbose and byte_no % log_every == 0:
print(f" bit {i + 1:4d} (byte {byte_no:3d}/128) : 후보 {len(cands):6d}")
if not cands:
raise SystemExit("후보가 전멸했다 — 가정이 틀렸다")
if verbose:
print(f" 완료: {time.time() - t0:.1f}s, 최종 후보 {len(cands)}개, 최대 동시후보 {peak}개")
if trace:
Path(trace).write_text("".join(f"{b}\t{n}\n" for b, n in hist))
return cands
def main():
ap = argparse.ArgumentParser()
ap.add_argument("--quiet", action="store_true")
ap.add_argument("--out", default=str(OUT))
ap.add_argument("--log-every", type=int, default=8,
help="몇 바이트마다 후보 수를 찍을지 (기본 8)")
ap.add_argument("--trace", default="", help="바이트별 후보 수를 TSV 로 저장")
args = ap.parse_args()
verbose = not args.quiet
v = parse_out(Path(args.out))
N, e, ct = v["N"], v["e"], v["ct"]
print(f"[*] N : {N.bit_length()} bits")
print(f"[*] 공개된 비트 p {bin(v['p_mask']).count('1')}/1024 "
f"({bin(v['p_mask']).count('1') / 10.24:.2f}%), "
f"q {bin(v['q_mask']).count('1')}/1024 "
f"({bin(v['q_mask']).count('1') / 10.24:.2f}%)")
print("[*] branch-and-prune 시작 (LSB→MSB, 바이트마다 printable 검사)")
cands = recover(N, v["p_redacted"], v["p_mask"],
v["q_redacted"], v["q_mask"], verbose=verbose,
log_every=args.log_every, trace=args.trace)
for p, q in cands:
if p * q != N:
continue
pb = p.to_bytes(128, "big")
qb = q.to_bytes(128, "big")
for a, b in ((pb, qb), (qb, pb)):
flag = (a + b).decode()
# 이 문제의 플래그는 DH{} 가 아니다 — 여는 중괄호가 앞쪽에,
# 닫는 중괄호가 맨 끝에 오는 쪽이 p||q 의 올바른 순서다
if "{" in flag[:8] and flag.endswith("}"):
print(f"\n[+] p = {hex(p)[:40]}...")
print(f"[+] q = {hex(q)[:40]}...")
print(f"[+] p*q == N : {p * q == N}")
print(f"\nFLAG ({len(flag)}자):\n{flag}")
# 덤으로: 문제의 가짜 평문이 정말 복호화되는지도 확인
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(ct, d, N)
dec = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(f"\n[검산] ct 복호화 → {dec!r}")
return 0
print("[-] p*q == N 을 만족하는 후보를 찾지 못했다", file=sys.stderr)
return 1
if __name__ == "__main__":
sys.exit(main())몇 군데만 짚는다.
시작이 [(1, 1)] 인 건 N 이 홀수라 p, q 가 모두 홀수이기 때문이다.
마스크가 0번 비트를 절대 안 알려주지만 여기는 공짜로 채워진다.
p*q ≡ N (mod 2^1024) 만 강제하므로 끝까지 갔다고 정답이 보장되지는 않는다.
p, q 가 각각 1024비트 미만이라 모든 비트가 확정되면 값이 정해지고,
그때 p * q != N 인 후보는 마지막에 걸러 낸다.
--trace 는 바이트마다 살아남은 후보 수를 파일로 떨어뜨린다. 아래 그래프에 쓸 데이터다.
python3 solve.py --trace bnp_trace.txt
0.0초다. 1024비트 소수 두 개를 복원하는 데 체감할 시간이 걸리지 않는다. 최대 동시 후보는 859개였고, 바이트 경계 기준으로는 43번째 바이트에서 188개가 최고였다. 이론값 0.5358배가 실제로도 유지된 셈이다.
추적 데이터를 그대로 그려 보면 모양이 더 분명하다. 그래프도 그 파일에서 바로 뽑았다.
#!/usr/bin/env python3
"""bnp_trace.txt (바이트별 살아남은 후보 수) 를 SVG 막대그래프로 그린다."""
import math
import sys
from pathlib import Path
HERE = Path(__file__).resolve().parent
rows = [l.split("\t") for l in (HERE / "bnp_trace.txt").read_text().strip().splitlines()]
data = [(int(a), int(b)) for a, b in rows]
out = Path(sys.argv[1]) if len(sys.argv) > 1 else HERE / "chart_trace.svg"
W, H = 1200, 460
L, R, T, B = 70, 30, 60, 56
pw, ph = W - L - R, H - T - B
top = max(n for _, n in data)
ymax = 10 ** math.ceil(math.log10(top)) # 로그 눈금 상한
def y(n):
# 1 이 바닥, ymax 가 천장인 로그 스케일
return T + ph - ph * math.log10(max(n, 1) + 1) / math.log10(ymax + 1)
bw = pw / len(data)
bars = []
for i, (byte_no, n) in enumerate(data):
x = L + i * bw
top_y = y(n)
color = "#f97583" if n >= 100 else ("#f0883e" if n >= 10 else "#7ee787")
bars.append(f'<rect x="{x:.1f}" y="{top_y:.1f}" width="{bw * 0.78:.1f}" '
f'height="{T + ph - top_y:.1f}" fill="{color}" opacity="0.9"/>')
grid = []
for v in (1, 10, 100, 1000):
if v > ymax:
break
gy = y(v)
grid.append(f'<line x1="{L}" y1="{gy:.1f}" x2="{W - R}" y2="{gy:.1f}" '
f'stroke="#30363d" stroke-width="1"/>')
grid.append(f'<text x="{L - 12}" y="{gy + 5:.1f}" font-family="DejaVu Sans Mono, monospace" '
f'font-size="15" fill="#8b949e" text-anchor="end">{v}</text>')
ticks = []
for byte_no in (16, 32, 48, 64, 80, 96, 112, 128):
x = L + (byte_no - 0.5) * bw
ticks.append(f'<text x="{x:.1f}" y="{T + ph + 26}" font-family="DejaVu Sans Mono, monospace" '
f'font-size="15" fill="#8b949e" text-anchor="middle">{byte_no}</text>')
svg = f"""<?xml version="1.0" encoding="UTF-8"?>
<svg xmlns="http://www.w3.org/2000/svg" width="{W}" height="{H}" viewBox="0 0 {W} {H}">
<rect width="{W}" height="{H}" fill="#0d1117"/>
<text x="{W / 2}" y="34" font-family="DejaVu Sans Mono, monospace" font-size="19"
fill="#e6edf3" text-anchor="middle" xml:space="preserve">바이트 경계마다 살아남은 (p, q) 후보 수 · 로그 눈금</text>
{''.join(grid)}
{''.join(bars)}
<line x1="{L}" y1="{T + ph}" x2="{W - R}" y2="{T + ph}" stroke="#484f58" stroke-width="1"/>
{''.join(ticks)}
<text x="{W / 2}" y="{H - 12}" font-family="DejaVu Sans Mono, monospace" font-size="15"
fill="#8b949e" text-anchor="middle" xml:space="preserve">확정한 바이트 수 (LSB 쪽부터)</text>
</svg>
"""
out.write_text(svg)
print(f"{out} ({len(data)} bytes, 최대 {top}개)")python3 plot_trace.py chart_trace.svg
rsvg-convert -w 1200 chart_trace.svg -o 10_chart_trace.png
봉우리가 몇 번 솟지만 매번 다시 주저앉는다. 이게 0.5358배의 의미다. 운이 나빠 몇 바이트 연속으로 마스크가 비면 잠깐 늘어나고, 마스크가 촘촘한 구간에서 바로 회수된다. 끝까지 단조 감소하는 게 아니라 이렇게 출렁이며 내려온다.
🕳️ 함정 — 플래그 형식을 DH{ 로 박아 두면 정답을 버린다
▶🐛 삽질 — 인수분해에 성공해 놓고 실패 메시지를 봤다
처음 돌린 solve.py 는 마지막 판정을 이렇게 썼다.
if flag.startswith("DH{") and flag.endswith("}"):드림핵 플래그는 대부분 DH{...} 라서 습관적으로 그렇게 짰다.
그리고 [-] p*q == N 을 만족하는 후보를 찾지 못했다 를 봤다.
곧바로 recover() 만 따로 불러 후보를 열어 봤더니 이랬다.
후보수 1
p bits 1023 q bits 1023
p bytes: b'GoN{This_Flag_iS_cOnSTrUcTEd_wITh_pURe_A'
q tail : b'_but_i_tHINk_THIs_is_SUpEr_cOol_iSnT_it}'
p*q==N ? True인수분해는 이미 끝나 있었다. 이 문제의 플래그는 DH{ 가 아니라 GoN{ 로 시작한다.
드림핵에는 출제자에 따라 GoN{...} 형식을 쓰는 문제가 섞여 있는데, 그걸 접두사로
하드코딩해 두면 정답을 손에 쥔 채로 실패 메시지를 보게 된다.
고친 뒤에는 형식을 고정하지 않고 "여는 중괄호가 앞쪽 8글자 안에 있고 닫는 중괄호로 끝난다" 로
바꿨다. 이 조건은 p||q 와 q||p 중 어느 쪽이 올바른 순서인지 고르는 용도로만 쓰면 충분하다.
if "{" in flag[:8] and flag.endswith("}"):교훈은 단순하다. 플래그 형식은 검증에 쓰되 탐색의 종료 조건으로 쓰지 않는다.
종료 조건은 p * q == N 하나면 된다.
복원된 결과를 바이트로 보면 구조가 한눈에 들어온다.
xxd flag.txt
오프셋 0x80 이 p 와 q 의 경계다. 앞쪽 128바이트를 빅엔디언 정수로 읽으면
1023비트 소수가 되고, 뒤쪽도 마찬가지다. 플래그 문장이 소수 두 개로 잘려 있는데
문장 자체는 자연스럽게 이어진다. 출제자가 p 쪽 128바이트를 소수로 만들려고
aPelDKfjpNXi 로 끝맺고, q 는 AHIFudNEKsM 로 시작하게 맞춘 흔적이 경계에 그대로 남아 있다.
✅ 검증 — 서로 다른 두 구현으로 되짚기
p * q == N 이면 사실상 끝이지만, 인수분해 결과를 그대로 믿고 제출하기 전에
chal.py 가 걸었던 조건을 전부 다시 걸어 봤다.
특히 중요한 건 마스크 대조다. 복원한 p 에 공개된 마스크를 씌웠을 때
p_redacted 가 그대로 나와야 한다. 이게 어긋나면 N 의 다른 인수분해를 찾은 것이다.
#!/usr/bin/env python3
"""
복원한 flag 가 진짜인지 chal.py 의 조건을 그대로 되짚어 확인한다.
solve.py 와 독립적으로 — flag 문자열만 받아서 처음부터 다시 만든다.
"""
import string
import sys
from pathlib import Path
import sympy
HERE = Path(__file__).resolve().parent
FLAG = (HERE / "flag.txt").read_text().strip()
vals = {}
for line in (HERE / "extracted" / "out.txt").read_text().strip().splitlines():
k, _, v = line.partition(":")
vals[k.strip()] = int(v.strip(), 16)
N, e, ct = vals["N"], vals["e"], vals["ct"]
SIZE = 2048
ok = True
def check(label, cond):
global ok
ok &= bool(cond)
print(f" [{'OK' if cond else '실패'}] {label}")
print("chal.py 의 assert 를 그대로 다시 건다")
check(f"len(flag) == {SIZE // 8} (실제 {len(FLAG)})", len(FLAG) == SIZE // 8)
check("모든 문자가 ascii_letters + {}_ 안에 있다",
all(c in string.ascii_letters or c in ["{", "}", "_"] for c in FLAG))
p = int.from_bytes(FLAG[:SIZE // 2 // 8].encode(), byteorder="big")
q = int.from_bytes(FLAG[SIZE // 2 // 8:].encode(), byteorder="big")
print()
print("p, q 를 flag 조각에서 다시 만든다")
check(f"is_prime(p) ({p.bit_length()} bits)", sympy.isprime(p))
check(f"is_prime(q) ({q.bit_length()} bits)", sympy.isprime(q))
check("p * q == N", p * q == N)
print()
print("공개된 조각과 대조한다 — 여기서 어긋나면 다른 인수분해를 찾은 것이다")
check("p & p_mask == p_redacted", p & vals["p_mask"] == vals["p_redacted"])
check("q & q_mask == q_redacted", q & vals["q_mask"] == vals["q_redacted"])
print()
print("복원한 소인수로 개인키를 만들어 ct 를 푼다")
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(ct, d, N)
pt = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(f" 평문: {pt!r}")
check("ct 가 chal.py 의 가짜 평문으로 복호된다", pt == b"flag{this_is_fake_flag_:P}")
print()
print("전부 통과" if ok else "검증 실패")
sys.exit(0 if ok else 1)python3 verify.py
ct 가 flag{this_is_fake_flag_:P} 로 풀린다. chal.py 에 박혀 있던 그 문자열이다.
개인키까지 정확히 복원됐다는 뜻이라 여기서 의심의 여지가 없어진다.
sympy 한 구현만 믿기도 아까워서 SageMath 로 한 번 더 확인했다.
소수 판정 구현이 다르고, gcd 로 나눗셈 관계까지 직접 볼 수 있다.
# SageMath 로 한 번 더 — sympy 와 다른 구현으로 소수판정·인수분해를 확인한다.
# 실행: sage verify.sage
import re
txt = open("extracted/out.txt").read()
vals = {}
for line in txt.strip().split("\n"):
k, _, v = line.partition(":")
vals[k.strip()] = Integer(int(v.strip(), 16))
N = vals["N"]
flag = open("flag.txt").read().strip()
p = Integer(int.from_bytes(flag[:128].encode(), "big"))
q = Integer(int.from_bytes(flag[128:].encode(), "big"))
print("N.nbits() =", N.nbits())
print("p.nbits() =", p.nbits())
print("q.nbits() =", q.nbits())
print("p.is_prime() =", p.is_prime())
print("q.is_prime() =", q.is_prime())
print("N == p*q =", N == p * q)
print("N.gcd(p) == p =", N.gcd(p) == p)
print()
# 개인키를 실제로 만들어 서명/복호가 도는지
e = vals["e"]
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(vals["ct"], d, N)
print("ct^d mod N =", bytes.fromhex(hex(m)[2:]))
print()
print("p 앞 48바이트 =", bytes.fromhex(hex(p)[2:])[:48])
print("q 뒤 48바이트 =", bytes.fromhex(hex(q)[2:])[-48:])sage verify.sage
p.is_prime(), q.is_prime(), N == p*q, N.gcd(p) == p 가 모두 참이다.
두 시스템이 같은 결론을 내니 여기서 멈춘다.
🚀 재현
배포 파일과 스크립트만 있으면 다른 기계에서도 바로 돌아가게 재현 스크립트를 붙였다. 복원 → 플래그 대조 → 독립 검증까지 한 번에 한다.
#!/usr/bin/env bash
# pprintable (DreamHack #589, Platinum 4) — 한 방 재현.
# solve.py 로 p, q 를 복원해 flag 를 뽑고, verify.py 로 chal.py 조건까지 되짚는다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
# 기대값: 문제.json(NAS 백업이 붙여 준다) → flag.txt 순으로 찾는다
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null \
|| cat flag.txt 2>/dev/null || echo '')
OUT=$(timeout 600 python3 solve.py --quiet 2>&1) || true
echo "$OUT" | tail -8
FLAG=$(printf '%s' "$OUT" | grep -aoE 'GoN\{[^}]+\}' | head -1)
if [ -z "$FLAG" ]; then
echo; echo "❌ FAIL (flag 를 못 뽑았다)"; exit 1
fi
if [ -n "$EXPECT" ] && [ "$FLAG" != "$EXPECT" ]; then
echo; echo "❌ FAIL (얻은 값이 기대와 다르다)"; exit 1
fi
# 독립 검증 — 소수판정 · p*q==N · 마스크 대조 · ct 복호까지
printf '%s' "$FLAG" > flag.txt
timeout 300 python3 verify.py >/dev/null || { echo; echo "❌ FAIL (verify.py 불통과)"; exit 1; }
echo; echo "✅ PASS ${FLAG:0:40}...${FLAG: -20}"./reproduce.sh
환경: Ubuntu 25.10 · Python 3.13 · sympy 1.13.3 · SageMath 10.9.
solve.py 자체는 표준 라이브러리만 쓰므로 파이썬만 있으면 돈다.
verify.py 는 sympy, verify.sage 는 SageMath 가 필요한데 둘 다 검증용이라 없어도 플래그는 나온다.
배포본의 chal.py 는 gmpy2 를 임포트하지만 재현에는 필요 없다.
출제 시점에 소수 판정을 하려고 쓴 것이고, 우리는 그 반대 방향으로 가기 때문이다.
🧾 함정 정리
| 걸린 곳 | 증상 | 실제 원인 |
|---|---|---|
| 플래그 접두사 | p*q == N 인 후보가 나왔는데 "못 찾았다" 출력 | 이 문제는 GoN{...} 형식. DH{ 를 종료 조건에 하드코딩했다 |
| 마스크 정렬 | 마스크가 1025비트로 나온다 | 루프 끝의 p_mask <<= 1 때문에 bit0 이 비고 전체가 한 칸 밀린다 |
| N 의 비트 수 | 2048이 아니라 2045 | p, q 의 최상위 바이트가 ASCII 문자라 각각 1023비트다 |
| 접근 선택 | Coppersmith 로 시작하면 막힌다 | 아는 비트가 연속 블록이 아니라 전 구간에 흩어져 있다 |
📝 결론
부분 공개는 공개다.
키의 일부만 지우고 나머지를 내보내는 건 안전하지 않다. 이 문제는 65%를 지웠는데도
복원됐다. RSA 의 p, q 는 N = p*q 라는 등식으로 서로 묶여 있어서,
남은 조각이 절반이 안 돼도 등식이 나머지를 채워 준다.
로그에 개인키 일부를 마스킹해 남기거나, 메모리 덤프에서 키 영역을 부분적으로만
덮어쓰는 처리가 위험한 이유가 이것이다. Heninger-Shacham 논문 자체가 콜드부트 공격으로
비트가 일부 소실된 키를 복원하는 데서 출발했다.
평문의 구조가 곧 공격 표면이다.
이번 복원을 성립시킨 건 암호 기법이 아니라 "모든 바이트가 55종 중 하나" 라는 조건이었다. 바이트당 21.5% 라는 필터가 부족한 22%p 를 정확히 메웠다. 키 재료를 사람이 읽는 문자열에서 유도하면 엔트로피가 그 문자열의 것으로 떨어진다. 소수를 만들 때는 문장이 아니라 CSPRNG 에서 뽑아야 한다.
정보를 어떻게 겹치느냐가 전부다.
마스크만으로는 70비트에서 터졌고, printable 만으로는 37비트에서 터졌다. 둘을 같은 탐색 안에 겹쳐 놓으니 0.0초 만에 끝났다. 각각은 임계값에 못 미치는 조건이었는데 곱해지는 순간 임계값을 넘었다. 크립토 문제에서 조건이 여러 개 주어졌다면, 하나씩 시험하기 전에 한 탐색 안에서 동시에 걸 수 있는지 부터 보는 게 맞다.
종료 조건은 수학으로 잡는다.
플래그 형식 같은 관례를 탐색의 종료 조건으로 쓰면 답을 쥐고도 놓친다.
여기서 믿을 것은 p * q == N 하나뿐이고, 형식은 마지막에 출력 순서를 고르는 데만 썼다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…