[🥈 Silver 1] 소수 p 의 하위 280비트만 지워졌다 — DreamHack tiny roots 풀이

문제: DreamHack — tiny roots 분류: Crypto 난이도: 🥈 Silver 1 FLAG: DH{yeaaaahhh!!_C00p3rsM1th_1s_G0d_><}

문제 설명은 이렇다. 드림이가 RSA 키를 만들다 커피를 쏟아 정보가 지워졌고, 새로 만들려던 중에 키 일부가 노출된 걸 발견했다는 것. 커피를 쏟았다는 게 곧 "비트가 지워졌다"는 뜻이고, 그 지워진 자리가 정확히 어디까지인지가 이 문제의 전부다.

DreamHack tiny roots 문제 페이지 — 크립토 실버 1, 커피를 쏟아 RSA 키 정보가 지워졌다는 설명과 문제 파일 받기 버튼이 보인다

문제 개요

항목	내용
문제명	tiny roots
난이도	🥈 Silver 1
분류	Crypto
제공 파일	`tiny roots.py` (생성 스크립트), `output.txt` (출력)
서버	없음 — 오프라인 문제
스택	Python 3 + PyCryptodome, RSA-2048
핵심 기법	Coppersmith known-MSB 인수분해 (May) + Howgrave-Graham 격자 + LLL

풀이 흐름은 짧다. p 의 상위 744비트가 그대로 공개돼 있으니 나머지 280비트를 미지수 x 로 두고 f(x) = MSB + x 의 작은 근을 격자로 찾는다. p 가 나오면 그다음은 교과서 RSA다.

🔬 배포본 정찰

파일은 딱 두 개다. 생성 스크립트와 그 출력.

ls -l extracted && file extracted/* && head -18 "extracted/tiny roots.py"

ls 와 file 로 확인한 배포본 — output.txt 1712바이트와 tiny roots.py 591바이트뿐이고, 소스 앞부분에 1024비트 소수 두 개와 128비트 지수 e 를 만드는 코드가 보인다

스크립트 전문은 이게 다다.

from Crypto.Util.number import *
 
FLAG = open('../../flag.txt','rb').read()
FLAG = bytes_to_long(FLAG)
 
p = getPrime(1024)
q = getPrime(1024)
assert p > q
 
n = p * q
e = getPrime(128)
 
beta = 0.4
epsilon = beta ** 2 / 7
 
upper_bound = p.bit_length()
lower_bound = int(n.bit_length() * (beta ** 2 - epsilon))
 
MSB = p & (pow(2,upper_bound) - pow(2,lower_bound))
 
# encryption
ciphertext = pow(FLAG,e,n)
 
print(f'Here is the flag : {ciphertext}\n')
print(f'I don\'t know the secret key... except some bits of p...\n{MSB}\n')
print(f'But I know the public key !! Can You make it??\n({n},{e})')

e 가 128비트 소수라 작은 지수 공격은 처음부터 막혀 있다. 소수 두 개도 독립적으로 뽑았으니 근접 소수 공격도 안 된다. 남는 건 MSB 한 줄뿐이다.

MSB = p & (2^upper_bound - 2^lower_bound) — 여기서 upper_bound 는 p.bit_length() 니까 1024고, lower_bound 는 n 의 비트수 2048에 beta^2 - epsilon 을 곱한 값이다. 마스크가 몇 비트를 살리고 몇 비트를 지우는지는 눈으로 세지 말고 직접 계산하는 게 빠르다.

#!/usr/bin/env python3
"""output.txt 에서 파라미터를 뽑고, 문제 코드의 마스크가 실제로 몇 비트를 지웠는지 센다."""
import re
 
txt = open('extracted/output.txt').read()
c = int(re.search(r'Here is the flag : (\d+)', txt).group(1))
msb = int(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
n, e = (int(v) for v in re.search(r'\((\d+),(\d+)\)', txt).groups())
 
beta = 0.4
epsilon = beta ** 2 / 7
upper_bound = 1024                       # p.bit_length()
lower_bound = int(n.bit_length() * (beta ** 2 - epsilon))
mask = pow(2, upper_bound) - pow(2, lower_bound)
 
print(f'n           : {n.bit_length()}비트')
print(f'e           : {e.bit_length()}비트  = {e}')
print(f'ciphertext  : {c.bit_length()}비트')
print(f'MSB         : {msb.bit_length()}비트')
print()
print(f'beta        = {beta}')
print(f'epsilon     = beta^2/7 = {epsilon:.9f}')
print(f'lower_bound = int({n.bit_length()} * ({beta**2:.2f} - {epsilon:.6f})) '
      f'= int({n.bit_length()*(beta**2-epsilon):.4f}) = {lower_bound}')
print()
print(f'mask        = 2^{upper_bound} - 2^{lower_bound}')
print(f'mask 안에서 1 인 비트 = {bin(mask).count("1")}개  (비트 {lower_bound}..{upper_bound-1})')
print(f'-> p 의 상위 {upper_bound-lower_bound}비트를 알고, 하위 {lower_bound}비트를 모른다')
print()
print(f'MSB 의 뒤쪽 0 비트 = {(msb & -msb).bit_length()-1}개  '
      f'(하위 {lower_bound}비트가 지워졌고, 마침 그 위 6비트도 0이었다)')
print(f'MSB % 2^{lower_bound} == 0 ?  {msb % (1 << lower_bound) == 0}')
print()
print(f'미지수 후보 = 2^{lower_bound} = {1 << lower_bound}')
print(f'초당 10^9 회 검사해도 {(1<<lower_bound)/1e9/3.15e7:.3e} 년 -> 전수는 불가능')

python3 recon.py

recon.py 실행 결과 — n 2048비트, e 128비트, lower_bound 가 int(2048 x 0.137142) = 280 으로 확정되고 마스크가 p 의 상위 744비트만 남긴다는 것이 숫자로 확인된다

숫자가 다 나왔다. lower_bound = 280, 즉 p 의 하위 280비트가 지워지고 상위 744비트가 그대로 공개됐다.

MSB 의 뒤쪽 0비트가 286개로 나오는 게 잠깐 눈에 걸리는데, 이건 지워진 280비트 위쪽 6비트가 우연히 0이었을 뿐이다. 마스크가 지운 건 정확히 280비트다.

p 의 비트 배치 — 상위 744비트는 MSB 로 공개되고 하위 280비트만 미지수 x 이며, 전수 탐색은 6.2x10^67 년이지만 Coppersmith 이론 한계인 512비트에는 232비트 여유가 있다

정리하면 이렇다.

p = MSB + x 이고 미지수 범위는 0 <= x < 2^280 이다.

2^280 은 대략 1.9x10^84 다. 전수는 논외다.

🧩 배경 — 인수의 상위 비트를 알면 뚫린다

Coppersmith 는 1996년에 "모듈러 다항식의 작은 근은 다항시간에 찾을 수 있다"는 결과를 냈고, May 가 그걸 인수분해 쪽으로 정리했다. 우리가 쓸 형태는 이거다.

N 의 미지 인수 p >= N^beta 와 차수 delta 인 monic 다항식 f(x) 에 대해, f(x0) 가 mod p 에서 0이 되는 x0 가 |x0| < N^(beta^2/delta) 를 만족하면 그 x0 는 N 만 알고도 다항시간에 찾을 수 있다.

여기 대입하면 f(x) = MSB + x, 차수 1, f(x0) = p 이므로 mod p 에서 0이다. p 와 q 가 둘 다 1024비트라 p 는 대략 N^0.5 이고, 그러면 감당 가능한 미지수는 N^0.25 = 512비트다. 지워진 건 280비트뿐이라 232비트나 남는다. 문제 이름 tiny roots 는 이 "작은 근"이자 SageMath 의 small_roots 를 가리킨다.

핵심 도구는 Howgrave-Graham 의 보조정리다. mod p 에서 근을 갖는 정수 다항식의 계수가 충분히 작으면, 그 근에서 정수 위에서도 값이 0이 된다는 것. 그래서 mod p 로 0이 되는 다항식들을 잔뜩 만들어 놓고, 그 정수 결합 중 계수가 작은 것을 찾으면 된다. 그 "계수가 작은 결합 찾기"가 곧 격자 최단벡터 문제고, LLL 이 그걸 근사로 풀어 준다.

Wikimedia Commons 의 격자 기저 축약 그림 — 길고 거의 평행한 기저 v1, v2 를 같은 격자를 생성하는 짧고 직교에 가까운 u1, u2 로 바꾸는 것이 LLL 이 하는 일이다

출처: Wikimedia Commons, public domain

그림의 v1, v2 처럼 길고 거의 평행한 기저를 u1, u2 처럼 짧고 직교에 가깝게 바꾸는 것이 LLL 이다. 같은 격자를 생성하되 벡터만 짧아진다. 우리가 원하는 "작은 계수 다항식"이 정확히 그 짧은 벡터다.

💣 핵심 — 3×3 격자면 충분하다

m = 1, t = 1 로 잡으면 mod p 에서 0이 되는 다항식이 셋 나온다.

다항식	`mod p` 에서 0인 이유
`g0(x) = n`	`p` 가 `n` 을 나눈다
`g1(x) = f(x)`	`f(x0) = p`
`h1(x) = x·f(x)`	위에 `x` 를 곱했을 뿐

이 셋을 x → X·x 로 치환해 계수 벡터로 늘어놓으면 삼각행렬이 된다. 대각 성분은 n, X, X^2 이고 행렬식은 n·X^3 이다.

Howgrave-Graham 조건은 LLL 최단벡터의 노름이 p^m / √dim 보다 작아야 한다는 것이고, LLL 은 최단벡터 노름이 2^((d-1)/4) * det^(1/d) 이하임을 보장한다. 숫자를 넣으면

log2(det) = 2048 + 3 x 280 = 2888 이고, 이걸 차원 3으로 나누면 962.7 이다.

여유가 2^60 이상 남는다. 이론값만 믿을 게 아니라 (m, t) 를 훑어 어디부터 조건이 서고 실제로 얼마나 걸리는지 재 봤다.

#!/usr/bin/env python3
"""격자 크기 (m, t) 를 바꿔 가며 Howgrave-Graham 조건이 성립하는지 계산하고,
작은 격자는 실제로 LLL 을 돌려 걸린 시간과 최단벡터 길이를 잰다.
 
  이론:  2^((dim-1)/4) * det^(1/dim) < p^m / sqrt(dim)
  여기서 det = X^(m(m+1)/2 + t*m + t(t+1)/2) * n^(m(m+1)/2)
"""
import math
import re
import sys
import time
 
from lll import lll
 
txt = open('extracted/output.txt').read()
msb = int(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
n = int(re.search(r'\((\d+),(\d+)\)', txt).group(1))
LOGX, LOGN, LOGP = 280, 2048, 1024        # X=2^280, n 2048비트, p 1024비트
 
 
def build(m, t):
    dim = m + t + 1
    fp = [[1]]
    for _ in range(m):
        a, b = fp[-1], [msb, 1]
        out = [0] * (len(a) + len(b) - 1)
        for i, x in enumerate(a):
            for j, y in enumerate(b):
                out[i + j] += x * y
        fp.append(out)
    polys = [[c * pow(n, m - i) for c in fp[i]] for i in range(m + 1)]
    polys += [[0] * j + fp[m] for j in range(1, t + 1)]
    X = 1 << LOGX
    return [[polys[r][k] * pow(X, k) if k < len(polys[r]) else 0
             for k in range(dim)] for r in range(dim)]
 
 
print(f'{"m":>2} {"t":>2} {"dim":>4} {"log2(det)":>10} {"LLL 상한":>9} '
      f'{"필요 p^m":>9}  판정   실측')
print('-' * 68)
for m in range(1, 5):
    for t in range(0, 4):
        dim = m + t + 1
        logdet = LOGX * (m * (m + 1) // 2 + t * m + t * (t + 1) // 2) + LOGN * (m * (m + 1) // 2)
        lhs = logdet / dim + (dim - 1) / 4 + 0.5 * math.log2(dim)
        rhs = LOGP * m
        ok = '통과' if lhs < rhs else '미달'
        measured = ''
        if dim <= 4 and lhs < rhs:
            st = time.time()
            R = lll(build(m, t))
            el = time.time() - st
            norm2 = sum(c * c for c in R[0])
            measured = f'{el:6.2f}s  ||v||=2^{(norm2.bit_length()-1)/2:.0f}'
        print(f'{m:>2} {t:>2} {dim:>4} {logdet:>10} {lhs:>9.1f} {rhs:>9} '
              f'  {ok}   {measured}')
        sys.stdout.flush()

python3 lattice_scan.py

lattice_scan.py 실행 결과 — m=1 t=0 인 2차원 격자는 1164.8 이 필요치 1024 를 넘겨 미달이고, m=1 t=1 인 3차원부터 통과하며 실측 0.36초에 최단벡터 노름이 2^931 로 나온다

표에서 읽히는 게 두 가지다.

첫째, t = 0 인 줄은 m 이 아무리 커도 전부 미달이다. x 를 곱한 이동 다항식이 하나는 있어야 조건이 선다.

둘째, 조건이 서는 가장 작은 격자가 (m, t) = (1, 1) 의 3차원이다. dim 을 키우면 최단벡터는 더 짧아지지만(2^931 → 2^900) 어차피 필요한 건 2^1023 이하라 의미가 없고, 순수 파이썬 LLL 로는 비용만 급격히 는다. 이 문제에서 tiny 는 근만이 아니라 격자에도 해당한다.

Coppersmith 파이프라인 도식 — f(x)=MSB+x 로 시작해 p 로 나누어떨어지는 다항식 셋을 X 로 스케일한 3x3 삼각행렬로 만들고, LLL 로 뽑은 짧은 벡터가 Howgrave-Graham 조건을 넘겨 정수근 x0 를 주면 n 이 쪼개진다

🧱 LLL 을 직접 짜기

fpylll 이 이 머신에 없었고, 어차피 3차원이라 굳이 붙일 이유도 없었다. 표준 라이브러리만으로 짰다.

주의할 게 하나 있다. 그람-슈미트를 부동소수점으로 하면 안 된다. 성분이 2900비트짜리라 float 로는 유효숫자가 통째로 날아간다. Fraction 으로 정확히 계산해야 한다.

#!/usr/bin/env python3
"""표준 라이브러리만으로 만든 LLL(Lenstra-Lenstra-Lovasz) 격자 축약.
 
Fraction 으로 그람-슈미트를 정확히 계산한다. 부동소수점을 쓰면 2000비트가 넘는
성분에서 유효숫자가 통째로 날아가므로 정수/유리수 산술이 필수다.
차원이 10 이하라 O(n^4) 재계산이어도 충분히 빠르다.
"""
from fractions import Fraction
 
 
def _dot(u, v):
    return sum(a * b for a, b in zip(u, v))
 
 
def _gram_schmidt(B):
    n = len(B)
    Bs, mu = [], [[Fraction(0)] * n for _ in range(n)]
    for i in range(n):
        v = [Fraction(x) for x in B[i]]
        for j in range(i):
            mu[i][j] = _dot(B[i], Bs[j]) / _dot(Bs[j], Bs[j])
            v = [v[k] - mu[i][j] * Bs[j][k] for k in range(len(v))]
        Bs.append(v)
    return Bs, mu
 
 
def lll(basis, delta=Fraction(99, 100)):
    """행 벡터 리스트를 받아 LLL 축약된 기저를 돌려준다."""
    B = [list(map(int, row)) for row in basis]
    n = len(B)
    Bs, mu = _gram_schmidt(B)
    k = 1
    while k < n:
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > Fraction(1, 2):
                r = int(round(mu[k][j]))
                B[k] = [B[k][i] - r * B[j][i] for i in range(len(B[k]))]
                Bs, mu = _gram_schmidt(B)
        lhs = _dot(Bs[k], Bs[k])
        rhs = (delta - mu[k][k - 1] ** 2) * _dot(Bs[k - 1], Bs[k - 1])
        if lhs >= rhs:
            k += 1
        else:
            B[k], B[k - 1] = B[k - 1], B[k]
            Bs, mu = _gram_schmidt(B)
            k = max(k - 1, 1)
    return B

직접 짠 걸 그대로 믿고 2000비트 격자에 밀어 넣기 전에, 답을 아는 작은 입력에서 확인했다. Cohen 의 교과서 예제와, 거의 평행해서 축약 효과가 뚜렷한 2차원 기저 하나.

#!/usr/bin/env python3
"""자작 lll.py 가 정말 LLL 축약을 하는지 확인한다.
Cohen 의 교과서 예제 기저와, 그 기저가 실제로 축약 조건(size-reduced + Lovasz)을
만족하는지까지 같이 검사한다.
"""
from fractions import Fraction
 
from lll import lll, _gram_schmidt
 
 
def check(B):
    Bs, mu = _gram_schmidt(B)
    size_ok = all(abs(mu[i][j]) <= Fraction(1, 2)
                  for i in range(len(B)) for j in range(i))
    lovasz_ok = all(sum(x * x for x in Bs[k]) >=
                    (Fraction(99, 100) - mu[k][k - 1] ** 2) * sum(x * x for x in Bs[k - 1])
                    for k in range(1, len(B)))
    return size_ok, lovasz_ok
 
 
for name, B in [('Cohen 예제', [[1, 1, 1], [-1, 0, 2], [3, 5, 6]]),
                ('거의 평행한 2차원 기저', [[201, 37], [140, 26]])]:
    R = lll(B)
    s, l = check(R)
    before = min(sum(x * x for x in r) for r in B)
    after = min(sum(x * x for x in r) for r in R)
    print(f'{name}')
    print(f'  입력  {B}')
    print(f'  출력  {R}')
    print(f'  최단벡터 노름^2  {before} -> {after}')
    print(f'  size-reduced {s},  Lovasz 조건 {l}')

python3 lll_check.py

lll_check.py 실행 결과 — Cohen 교과서 예제가 알려진 축약 기저로 떨어지고, 거의 평행한 2차원 기저는 최단벡터 노름 제곱이 20276 에서 50 으로 줄며 size-reduced 와 Lovasz 조건이 둘 다 True 로 나온다

교과서 예제는 알려진 축약 기저 그대로 나왔고, 두 번째는 노름 제곱이 20276에서 50으로 떨어졌다. 축약 조건 두 개도 사후 검사로 통과한다.

🐛 삽질

▶🐛 삽질 1 — 격자는 클수록 좋은 줄 알았다

처음엔 (m, t) = (3, 2) 로 6차원 격자를 짰다. Coppersmith 설명에 항상 "m 을 충분히 크게"가 붙으니 여유를 두는 게 안전하다고 생각했다.

2분이 지나도 안 끝났다. 순수 파이썬 Fraction 그람-슈미트를 매 단계 다시 계산하는 구현이라 차원이 오르면 비용이 폭발한다. 위의 lattice_scan.py 로 실측한 게 그래서였다.

m  t  dim  log2(det)    LLL 상한    필요 p^m  판정   실측
 1  1    3       2888     964.0      1024   통과     0.36s
 1  2    4       3728     933.8      1024   통과     1.28s
 2  1    4       7824    1957.8      2048   통과     5.50s
 2  2    5       8944    1791.0      2048   통과    77.53s
 3  1    5      15088    3019.8      3072   통과    28.49s

m 을 키우면 조건은 더 여유롭게 서지만 이 문제엔 이미 여유가 충분하다. 미지수가 280비트로 이론 한계 512비트의 절반 남짓이라, 최소 격자에서 바로 조건이 선다. "m 을 크게"는 미지수가 한계에 바짝 붙었을 때 하는 얘기다.

▶🐛 삽질 2 — 다항식 GCD 가 상수에서 무한루프에 빠졌다

LLL 은 0.36초에 끝나는데 solve.py 가 5분 타임아웃까지 안 돌아왔다. 범인은 내가 짠 poly_gcd 였다.

처음 구현은 나눗셈 한 단계를 반복하면서 while len(b) > 1 or b[0] != 0 로 돌았다. 그런데 두 다항식이 서로소면 나머지가 0이 아닌 상수로 떨어진다. 그때 a 는 매번 0이 되고 b 는 그대로라 종료 조건에 영영 못 닿는다.

LLL 결과 행 세 개 중 조건을 만족하지 못하는 행이 섞여 있으면 그 조합의 GCD 가 상수가 된다. 즉 이 경로는 정상 동작에서도 반드시 밟는다.

고친 건 교과서 유클리드 형태로 되돌린 것뿐이다.

while not (len(b) == 1 and b[0] == 0):
    a, b = b, poly_mod(a, b)

poly_mod 안에서도 나누는 쪽이 상수면(차수 0) 나머지를 바로 [0] 으로 돌려준다. 이 두 줄로 5분이 0.42초가 됐다.

▶🐛 삽질 3 — 조용히 틀리는 세 가지

격자 풀이는 틀렸을 때 예외를 안 낸다. LLL 은 멀쩡히 돌고 시간도 짧은데 근만 안 나온다. 그래서 "이론이 안 맞나" 를 의심하게 되는데, 실제로는 셋 다 사소한 구현 실수였다. 재현 스크립트로 남겨 뒀다.

#!/usr/bin/env python3
"""풀이 도중 실제로 밟았던 세 가지 함정을 그대로 재현한다.
셋 다 '조용히 틀린다' - 예외도 없고 오래 걸리지도 않는데 근이 안 나온다.
"""
import re
 
from lll import lll
from solve import coppersmith_known_msb, poly_gcd, poly_trim, _newton_int_root
 
txt = open('extracted/output.txt').read()
msb = int(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
n = int(re.search(r'\((\d+),(\d+)\)', txt).group(1))
TRUE_X0 = 781182359928297838659720821147531543713572092829500480647209554762229923863457600593
 
 
def report(tag, roots):
    ok = [r for r in roots if n % (msb + r) == 0]
    print(f'  -> 찾은 근 {len(roots)}개, n 을 나누는 것 {len(ok)}개'
          f'{"  <== 성공" if ok else "  <== 실패"}')
 
 
print('[함정 1] x -> X*x 스케일링을 빼먹고 격자를 짜면')
dim = 3
polys = [[n], [msb, 1], [0, msb, 1]]
B = [[polys[r][k] if k < len(polys[r]) else 0 for k in range(dim)] for r in range(dim)]
R = lll(B)
cand = [poly_trim(list(row)) for row in R]
roots = []
for i in range(dim):
    for j in range(i + 1, dim):
        g = poly_gcd(cand[i], cand[j])
        if len(g) == 2 and (-g[0] / g[1]).denominator == 1:
            roots.append(int(-g[0] / g[1]))
    r = _newton_int_root(cand[i], 1 << 280)
    if r is not None:
        roots.append(r)
print(f'  LLL 최단벡터 = {[hex(v)[:12] + ".." if abs(v) > 2**40 else v for v in R[0]]}')
report('scale', roots)
 
print()
print('[함정 2] t=0 - x 를 곱한 이동 다항식을 넣지 않으면 (격자 2x2)')
print('  Howgrave-Graham 조건: 2^1164.8 < 2^1024 이어야 하는데 미달')
try:
    roots = coppersmith_known_msb(n, msb, 1 << 280, m=1, t=0, verbose=False)
except Exception as exc:
    roots = []
    print(f'  예외: {exc!r}')
report('t0', roots)
 
print()
print('[함정 3] lower_bound 를 n(2048비트) 이 아니라 p(1024비트) 기준으로 읽으면')
wrong = int(1024 * (0.4 ** 2 - 0.4 ** 2 / 7))
print(f'  X = 2^{wrong} 인데 참값 x0 는 {TRUE_X0.bit_length()}비트다')
roots = coppersmith_known_msb(n, msb, 1 << wrong, m=1, t=1, verbose=False)
report('smallX', roots)
 
print()
print('[대조] 제대로 짠 경우')
roots = coppersmith_known_msb(n, msb, 1 << 280, m=1, t=1, verbose=False)
report('ok', roots)
print(f'  x0 = {roots[0] if roots else "-"}')

python3 traps.py

traps.py 실행 결과 — 스케일링 누락, t=0 인 2x2 격자, X 를 2^140 으로 잡은 경우 셋 다 예외 없이 근 0개로 조용히 실패하고 마지막 대조군만 x0 를 하나 찾는다

첫째, x → X·x 치환을 빼먹는 것. 이게 제일 헷갈린다. 스케일링 없이도 격자는 잘 짜이고 LLL 도 돈다. 하지만 LLL 이 줄이는 건 벡터의 유클리드 노름인데, Howgrave-Graham 이 요구하는 건 "근의 크기까지 감안한 계수 크기"다. X 를 곱해 두지 않으면 이 둘이 서로 다른 양을 재는 셈이라 짧은 벡터가 나와도 쓸모가 없다.

둘째, 이동 다항식 없이 t = 0. 2차원 격자로는 2^1164.8 < 2^1024 를 만족할 방법이 없다. 실행 시간이 짧아서 "빨리 끝났으니 뭔가 됐겠지" 하고 넘어가기 쉽다.

셋째, lower_bound 를 p 기준으로 읽는 것. 문제 코드는 n.bit_length() 를 쓰는데 습관적으로 p 의 1024로 읽으면 X = 2^140 이 된다. 참값 x0 는 279비트라 상한 밖이고, 격자 조건은 오히려 더 여유로워지니 아무 경고도 안 뜬다.

🚀 Full Exploit

위 조각들을 합친 자체완결 풀이다. 의존성은 표준 라이브러리와 같은 폴더의 lll.py 뿐이고, 배포본 output.txt 만 있으면 돌아간다.

#!/usr/bin/env python3
"""tiny roots (DreamHack, Silver 1, crypto) 자체완결 풀이.
 
p 의 하위 280비트만 지워진 RSA 공개키에서 p 를 통째로 복구한다.
Coppersmith 의 'known MSB of a factor'(May) 를 Howgrave-Graham 격자로 직접 구성했다.
외부 의존성 없음 - 표준 라이브러리와 같은 폴더의 lll.py 뿐이다.
 
    python3 solve.py extracted/output.txt
"""
import re
import sys
from fractions import Fraction
 
from lll import lll
 
 
# ---------------------------------------------------------------- 다항식 유틸
def poly_mul(a, b):
    out = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        if x:
            for j, y in enumerate(b):
                out[i + j] += x * y
    return out
 
 
def poly_eval(c, x):
    acc = 0
    for coeff in reversed(c):
        acc = acc * x + coeff
    return acc
 
 
def poly_trim(c):
    while len(c) > 1 and c[-1] == 0:
        c.pop()
    return c
 
 
def poly_mod(a, b):
    """a mod b (유리수 계수). b 는 0 이 아니어야 한다."""
    a, db = list(a), len(b) - 1
    if db == 0:
        return [Fraction(0)]
    while len(a) - 1 >= db:
        shift, factor = len(a) - 1 - db, a[-1] / b[-1]
        for i, coeff in enumerate(b):
            a[i + shift] -= factor * coeff
        poly_trim(a)
        if len(a) == 1 and a[0] == 0:
            break
    return a
 
 
def poly_gcd(a, b):
    """유리수 계수 다항식 GCD. 계수를 Fraction 으로 올려 정확히 계산한다."""
    a = poly_trim([Fraction(x) for x in a])
    b = poly_trim([Fraction(x) for x in b])
    while not (len(b) == 1 and b[0] == 0):
        a, b = b, poly_mod(a, b)
    return [c / a[-1] for c in a] if a[-1] != 0 else a
 
 
# --------------------------------------------------- Coppersmith (known MSB)
def coppersmith_known_msb(n, a0, X, m=1, t=1, verbose=True):
    """f(x) = a0 + x 가 n 의 미지 인수 p 로 나누어떨어지는 |x0| < X 를 찾는다."""
    dim = m + t + 1
 
    # g_i(x) = n^(m-i) * f(x)^i  (i = 0..m)  /  h_j(x) = x^j * f(x)^m  (j = 1..t)
    fpow = [[1]]
    for _ in range(m):
        fpow.append(poly_mul(fpow[-1], [a0, 1]))
    polys = [[c * pow(n, m - i) for c in fpow[i]] for i in range(m + 1)]
    polys += [[0] * j + fpow[m] for j in range(1, t + 1)]
 
    # x -> X*x 로 치환해 격자를 짠다. 이 스케일링이 없으면 LLL 이 "짧다"고 보는
    # 벡터와 Howgrave-Graham 이 요구하는 "작은 계수"가 서로 다른 뜻이 된다.
    B = [[polys[r][k] * pow(X, k) if k < len(polys[r]) else 0
          for k in range(dim)] for r in range(dim)]
 
    det = 1
    for r in range(dim):
        det *= B[r][r]
    if verbose:
        print(f'[lattice] dim={dim} (m={m}, t={t})')
        print(f'[lattice] log2(det)      = {det.bit_length()}')
        print(f'[lattice] log2(det)/dim  = {det.bit_length() / dim:.1f}')
        print(f'[lattice] 목표 p^m       = 2^{1024 * m}  (p 는 1024비트)')
 
    R = lll(B)
 
    roots = []
    cand = []
    for row in R:
        coeffs = [row[k] // pow(X, k) for k in range(dim)]
        norm2 = sum(c * c for c in row)
        if verbose:
            print(f'[lll] ||v|| = 2^{(norm2.bit_length() - 1) / 2:.1f}'
                  f'   (Howgrave-Graham 요구: < p^{m}/sqrt({dim}) = 2^{1024 * m - 1})')
        cand.append(poly_trim(coeffs))
 
    # 서로 다른 짧은 벡터 두 개의 최대공약다항식이 곧 (x - x0) 다.
    for i in range(len(cand)):
        for j in range(i + 1, len(cand)):
            g = poly_gcd(cand[i], cand[j])
            if len(g) == 2:
                r = -g[0] / g[1]
                if r.denominator == 1:
                    roots.append(int(r))
    # 보조 경로: 가장 짧은 벡터 하나만으로 정수 뉴턴법
    for c in cand[:2]:
        r = _newton_int_root(c, X)
        if r is not None:
            roots.append(r)
 
    out = []
    for r in roots:
        if 0 <= r < X and r not in out and n % (a0 + r) == 0:
            out.append(r)
    return out
 
 
def _newton_int_root(coeffs, X):
    d = len(coeffs) - 1
    if d < 1:
        return None
    dc = [i * coeffs[i] for i in range(1, d + 1)]
    x = X
    for _ in range(4000):
        fx = poly_eval(coeffs, x)
        if fx == 0:
            return x
        dfx = poly_eval(dc, x)
        if dfx == 0:
            return None
        nx = x - fx // dfx
        if nx == x:
            return None
        x = nx
    return None
 
 
# ------------------------------------------------------------------- 본 풀이
def main(path='extracted/output.txt'):
    txt = open(path).read()
    c = int(re.search(r'Here is the flag : (\d+)', txt).group(1))
    msb = int(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
    n, e = (int(v) for v in re.search(r'\((\d+),(\d+)\)', txt).groups())
 
    # 문제 코드가 지운 비트 수를 그대로 재현한다.
    beta = 0.4
    epsilon = beta ** 2 / 7
    lower_bound = int(n.bit_length() * (beta ** 2 - epsilon))
    X = 1 << lower_bound
 
    print(f'[param] n  {n.bit_length()}비트,  e  {e.bit_length()}비트')
    print(f'[param] 지워진 하위 비트 = {lower_bound}  ->  X = 2^{lower_bound}')
    print(f'[param] 알려진 p 의 비트 = {1024 - lower_bound}')
 
    roots = coppersmith_known_msb(n, msb, X, m=1, t=1)
    if not roots:
        print('실패: 근을 찾지 못했다')
        return 1
    x0 = roots[0]
    p = msb + x0
    q = n // p
    print(f'[root] x0 = {x0}')
    print(f'[root] x0 는 {x0.bit_length()}비트  (상한 {lower_bound}비트)')
    print(f'[check] n % p == 0  ->  {n % p == 0}')
    print(f'[check] p * q == n  ->  {p * q == n}')
 
    d = pow(e, -1, (p - 1) * (q - 1))
    m_int = pow(c, d, n)
    flag = m_int.to_bytes((m_int.bit_length() + 7) // 8, 'big')
    print(f'FLAG: {flag.decode()}')
    return 0
 
 
if __name__ == '__main__':
    sys.exit(main(*sys.argv[1:]))

근을 찾는 마지막 단계만 한 줄 덧붙인다. LLL 이 돌려준 세 행을 각각 X^k 로 되나눠 정수 다항식으로 되돌리고, 그중 두 개의 최대공약다항식을 잡으면 (x - x0) 만 남는다. 계수가 2000비트급이라 유리근 정리로 인수분해하는 건 현실적이지 않아서, GCD 로 1차 인자를 직접 뽑는 쪽을 택했다. 실패할 때를 대비해 정수 뉴턴법 경로도 하나 두고, 최종 판정은 n % p == 0 이 한다.

python3 solve.py

solve.py 실행 결과 — 3x3 격자의 log2(det) 2888, LLL 최단벡터 2^931 이 Howgrave-Graham 요구치 2^1023 을 통과하고, x0 279비트가 나와 n % p == 0 True 와 함께 플래그가 복호된다

0.42초. n % p == 0 이 True 로 떨어졌고 플래그가 그대로 나왔다.

DH{yeaaaahhh!!_C00p3rsM1th_1s_G0d_><}

✅ 교차검증 — 네 갈래로

직접 짠 격자와 직접 짠 LLL 로 나온 답이라 한 번 더 확인했다.

SageMath 의 small_roots

같은 일을 하는 표준 구현과 대조한다. Sage 의 small_roots 는 beta 와 epsilon 을 받아 내부에서 m, t 를 정하므로, 문제 코드가 쓴 값을 그대로 넘기면 된다.

# tiny roots (DreamHack, Silver 1, crypto) - SageMath cross-check
# p 의 상위 744비트가 공개 -> Coppersmith(May) 'known MSB of factor'
import re
from Crypto.Util.number import long_to_bytes
 
txt = open('extracted/output.txt').read()
c   = Integer(re.search(r'Here is the flag : (\d+)', txt).group(1))
msb = Integer(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
n, e = [Integer(v) for v in re.search(r'\((\d+),(\d+)\)', txt).groups()]
 
beta    = 0.4
epsilon = beta ** 2 / 7
X       = 2 ** int(n.nbits() * (beta ** 2 - epsilon))     # = 2^280, 미지 하위비트 상한
 
P.<x> = PolynomialRing(Zmod(n))
f = msb + x                                                # f(x0) = p = 0 mod p
roots = f.monic().small_roots(X=X, beta=beta, epsilon=epsilon)
print('small_roots ->', roots)
 
x0 = Integer(roots[0])
p  = msb + x0
print('p  =', p)
print('n % p == 0 ?', n % p == 0)
q = n // p
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print('FLAG:', long_to_bytes(int(m)).decode())

sage solve_sage.sage

SageMath 10.9 에서 solve_sage.sage 를 돌린 화면 — small_roots 가 자작 격자와 같은 x0 를 반환하고 p 전체 값과 n % p == 0 True, 동일한 플래그가 찍힌다

x0 가 자릿수까지 똑같이 나왔다.

openssl 이 인정하는 개인키인가

복구한 p, q 로 PKCS#1 개인키를 손으로 조립해 openssl 에게 판정을 맡겼다. openssl rsa -check 는 p 와 q 의 소수성, d, CRT 파라미터의 정합성까지 본다. 우리 파이썬 코드와 완전히 독립된 검증이다.

#!/usr/bin/env python3
"""복구한 p, q 로 PKCS#1 RSAPrivateKey(PEM)를 직접 조립한다.
DER 을 손으로 짜서 라이브러리 도움 없이 만들고, 검증은 openssl 에게 맡긴다.
"""
import base64
import re
 
from solve import coppersmith_known_msb
 
txt = open('extracted/output.txt').read()
msb = int(re.search(r'bits of p\.\.\.\s*\n(\d+)', txt).group(1))
n, e = (int(v) for v in re.search(r'\((\d+),(\d+)\)', txt).groups())
 
p = msb + coppersmith_known_msb(n, msb, 1 << 280, m=1, t=1, verbose=False)[0]
q = n // p
assert p * q == n and p > q
d = pow(e, -1, (p - 1) * (q - 1))
 
 
def der_len(l):
    if l < 0x80:
        return bytes([l])
    b = l.to_bytes((l.bit_length() + 7) // 8, 'big')
    return bytes([0x80 | len(b)]) + b
 
 
def der_int(v):
    b = v.to_bytes((v.bit_length() + 8) // 8, 'big') if v else b'\x00'
    return b'\x02' + der_len(len(b)) + b
 
 
body = b''.join(der_int(v) for v in
                (0, n, e, d, p, q, d % (p - 1), d % (q - 1), pow(q, -1, p)))
der = b'\x30' + der_len(len(body)) + body
b64 = base64.encodebytes(der).decode().replace('\n', '')
pem = ('-----BEGIN RSA PRIVATE KEY-----\n'
       + '\n'.join(b64[i:i + 64] for i in range(0, len(b64), 64))
       + '\n-----END RSA PRIVATE KEY-----\n')
open('tiny_roots_priv.pem', 'w').write(pem)
print(f'wrote tiny_roots_priv.pem  ({len(der)} bytes DER)')

#!/usr/bin/env bash
# 복구한 p, q 로 만든 개인키를 openssl 이 인정하는지 본다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
python3 make_key.py
openssl rsa -in tiny_roots_priv.pem -check -noout
echo "openssl modulus : $(openssl rsa -in tiny_roots_priv.pem -noout -modulus | cut -c9-88)"
python3 -c "
import re
n = int(re.search(r'\((\d+),(\d+)\)', open('extracted/output.txt').read()).group(1))
print('output.txt 의 n :', format(n, 'X')[:80])"

./verify_openssl.sh

verify_openssl.sh 실행 결과 — 손으로 조립한 1206바이트 DER 개인키에 대해 openssl rsa -check 가 RSA key ok 를 내고, openssl 이 읽은 modulus 와 output.txt 의 n 이 앞 80자리까지 동일하다

RSA key ok. 모듈러스도 output.txt 의 n 과 일치한다.

이 인스턴스에만 맞춘 풀이가 아닌가

문제 코드와 똑같은 방식으로 RSA 인스턴스를 새로 만들어 복구 루틴을 그대로 돌렸다. 이 문제 하나에 우연히 맞은 게 아니라는 확인이다.

#!/usr/bin/env python3
"""문제 코드와 똑같은 방식으로 RSA 인스턴스를 새로 만들어 solve.py 의 복구 루틴을 돌린다.
이 문제 하나에만 맞춘 풀이가 아니라는 것을 확인하는 용도다.
"""
import time
 
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
 
from solve import coppersmith_known_msb
 
ROUNDS = 5
ok = 0
for r in range(1, ROUNDS + 1):
    plain = f'DH{{selftest_round_{r}}}'.encode()
    m = bytes_to_long(plain)
 
    p = getPrime(1024)
    q = getPrime(1024)
    if p < q:
        p, q = q, p
    n, e = p * q, getPrime(128)
 
    beta = 0.4
    epsilon = beta ** 2 / 7
    upper_bound = p.bit_length()
    lower_bound = int(n.bit_length() * (beta ** 2 - epsilon))
    MSB = p & (pow(2, upper_bound) - pow(2, lower_bound))      # 문제 코드 그대로
    ct = pow(m, e, n)
 
    st = time.time()
    roots = coppersmith_known_msb(n, MSB, 1 << lower_bound, m=1, t=1, verbose=False)
    el = time.time() - st
 
    if not roots:
        print(f'round {r}: 실패 ({el:.2f}s)')
        continue
    pp = MSB + roots[0]
    qq = n // pp
    d = pow(e, -1, (pp - 1) * (qq - 1))
    got = long_to_bytes(pow(ct, d, n))
    good = (pp == p and got == plain)
    ok += good
    print(f'round {r}: {el:.2f}s  p 복구 {pp == p}  복호 {got.decode()}  '
          f'{"OK" if good else "NG"}')
 
print(f'\n{ok}/{ROUNDS} 성공')

python3 selftest.py

selftest.py 실행 결과 — 문제 코드와 같은 방식으로 새로 만든 RSA 인스턴스 5개에서 모두 0.4초 안에 p 를 정확히 복구하고 평문까지 되돌려 5/5 성공으로 끝난다

5회 전부 p 를 정확히 복구했고 평문도 그대로 나왔다. 회당 0.4초 안쪽이다.

폴더만 있으면 다시 나오는가

배포본과 스크립트만 있으면 한 번에 플래그까지 나오도록 재현 스크립트를 남겼다.

#!/usr/bin/env bash
# tiny roots (DreamHack Silver 1, crypto) — 한 방 재현.
# 배포본(extracted/output.txt)만 있으면 flag 까지 나온다. 서버·크레딧 불필요.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || echo '')
 
OUT=$(timeout 300 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

reproduce.sh 실행 결과 — solve.py 를 돌려 얻은 플래그를 문제 메타데이터의 기대값과 대조하고 PASS 로 끝나며 서버나 VM 크레딧 없이 오프라인에서 재현된다

📝 결론

노출 비트의 "비율"이 안전선을 정한다

RSA 소수의 상위 절반이 알려지면 그 순간 끝이다. p 가 대략 N^0.5 일 때 Coppersmith 가 감당하는 미지수는 N^0.25, 즉 1024비트 소수라면 하위 512비트까지 몰라도 복구된다. 이 문제는 280비트만 지웠으니 애초에 절반 이상 여유가 있었다.

부분 노출은 부분 피해가 아니다

키의 일부만 새는 사고는 흔하다. 로그에 찍힌 잘린 값, 백업에서 복구된 조각, 사이드채널로 얻은 상위 비트. 대칭키 감각으로는 "몇 비트 샜을 뿐"이지만 RSA 소수에서는 다르다. 절반이 새면 전부 샌 것이고, 절반보다 조금 덜 새도 격자가 나머지를 메운다. 소수의 일부라도 노출된 키는 폐기 대상으로 봐야 한다.

격자가 커야 한다는 감각을 의심할 것

Coppersmith 설명에는 늘 "충분히 큰 m"이 붙지만, 실제로 필요한 크기는 미지수가 이론 한계에 얼마나 가까운지로 정해진다. 이번 문제처럼 여유가 크면 3차원 격자로 끝난다. m 을 키우면 계산량만 폭증하고 답은 그대로다.

틀린 격자는 예외를 안 낸다

X 스케일링 누락, 이동 다항식 누락, 상한 오독 셋 다 실행은 정상이고 결과만 비어 나온다. 그래서 격자 풀이에서는 "왜 안 되지"를 오래 붙들기 전에, 격자 조건을 숫자로 먼저 확인하는 게 낫다. log2(det)/dim 과 p^m 을 나란히 찍어 보면 그 자리에서 갈린다.

[🥈 Silver 1] 소수 p 의 하위 280비트만 지워졌다 — DreamHack tiny roots 풀이

댓글

관련 글

[💠 Platinum 2] 플래그를 반으로 쪼개 세 번 암호화하면 — DreamHack fl and ag 풀이

[🥈 Silver 1] nonce 절반이 새면 ECDSA 개인키는 1.8초 만에 나온다 — DreamHack [LINE CTF 2021] babycrypto4 풀이

[💎 Diamond 4] 깃발 세 조각을 다항식 소거로 다시 맞추기 — DreamHack f, l and ag 풀이