[💠 Platinum 4] 이진체 위의 RSA는 다항식 인수분해로 무너진다 — DreamHack Red-Black Christmas Tree 풀이

문제: DreamHack — Red-Black Christmas Tree 분류: Crypto 난이도: 💠 Platinum 4 FLAG: DH{finite_field_factorization_is_easy_and_sagemath_is_god}

출제자 RBTree가 붙인 설명은 두 줄이다. "Red or Black. 0 or 1. So the binary fields." 그리고 "Here's my Christmas gift." 레드-블랙 트리를 떠올리게 하는 제목은 미끼고, 진짜 힌트는 binary fields — 이진체 GF(2) 위에서 벌어지는 일이라는 뜻이다.

제공되는 건 gift.py와 그 출력 output.txt 둘뿐이다. 코드를 열어 보면 생김새는 영락없는 RSA인데, 숫자를 곱하는 자리에 묘한 비트 연산이 들어 있다. 이게 바로 정수 곱셈이 아니라 다항식 곱셈이라는 신호고, 거기서부터 문제 전체가 풀린다.

문제 개요

풀이 흐름은 한 줄로 요약된다. 암호문 c = flag^65537이 정수 모듈러가 아니라 GF(2)[X]/(n)이라는 다항식 환에서 계산됐음을 간파하고, 정수 인수분해 대신 다항식 인수분해로 n을 쪼갠 뒤 그 환의 유닛군 위수 N을 구해 복호 지수 d를 만든다.

🧩 배경 — 숫자처럼 보이는 다항식

gift.py의 핵심 세 함수를 그대로 본다.

cat extracted/gift.py

하나씩 뜯어보면 이렇다.

n — 법(modulus). os.urandom으로 4096비트 난수를 뽑고 n |= 1 << 4096으로 4096번 비트를 세운다. 정수로 보면 그냥 큰 수지만, 각 비트를 다항식 계수로 읽으면 GF(2) 위의 4096차 다항식이다. 최고차항 X^4096은 항상 1, 나머지 계수는 난수다.

f(x, y) — 곱셈. r ^= t(덧셈이 XOR), t <<= 1(자리 올림 없는 시프트), 그리고 t >> 4096이면 t ^= n(법으로 축약). 이건 정수 곱셈이 아니라 올림 없는(carryless) 다항식 곱셈 mod n이다. 즉 f(x, y) = x(X)·y(X) mod n(X) in GF(2)[X]. CPU의 CLMUL/PCLMULQDQ가 하는 바로 그 연산이고, AES-GCM의 GHASH와 같은 종류다.

g(x, y) — 거듭제곱. f를 곱셈으로 쓰는 전형적인 square-and-multiply다. 결국 g(flag, 0x10001) = flag^65537 in GF(2)[X]/(n).

정리하면 이 환은 R = GF(2)[X] / (n(X))이고, 암호화는 공개지수 e = 0x10001 = 65537로 하는 거듭제곱이다. 정수 RSA의 모든 구조를 다항식으로 그대로 옮긴 것. 공개된 건 n과 c = flag^e 둘뿐이다.

python3 -I inspect_params.py

output.txt에는 딱 두 줄, n과 c의 16진수만 들어 있다. n의 앞부분을 잘라 보면 이렇다.

head -c 240 extracted/output.txt

f가 정말 다항식 곱셈인지 확인하기

"f는 carryless 다항식 곱셈 mod n"이라는 해석은 추측이 아니라 검증할 수 있다. gift.py의 f()는 곱셈과 축약을 한 비트씩 번갈아 하는 interleaved 방식인데, 이것을 전혀 다른 순서 — 먼저 전체 carryless 곱을 구한 뒤 한꺼번에 n으로 축약 — 로 독립 구현해 같은 입력에 같은 값이 나오는지 본다. 두 구현이 일치하면 f의 정체가 확정된다.

# verify_structure.py — gift.py f()  vs  (전체 곱 → 사후 축약)
def f_gift(x, y, n):             # (A) gift.py 원본: interleaved
    t, r = x, 0
    while y:
        if y & 1:
            r ^= t
        y >>= 1
        t <<= 1
        if t >> 4096:
            t ^= n
    return r
 
def clmul(a, b):                 # 올림 없는 다항식 곱 (축약 없음)
    r = 0
    while b:
        if b & 1:
            r ^= a
        b >>= 1
        a <<= 1
    return r
 
def polymod(p, n):               # p mod n  in GF(2)[X]
    nb = n.bit_length() - 1      # deg(n) = 4096
    while p.bit_length() - 1 >= nb:
        p ^= n << (p.bit_length() - 1 - nb)
    return p
 
# 랜덤 a,b 로 f_gift(a,b) == polymod(clmul(a,b), n) 을 5회 비교

python3 -I verify_structure.py

5/5 일치다. f는 틀림없이 GF(2)[X]/(n)의 곱셈이고, 따라서 c는 그 환에서의 flag^65537이다. 이제 n을 어떻게 다룰지가 전부다.

💣 핵심 — 정수 RSA와 이진체 RSA의 결정적 차이

정수 RSA가 안전한 이유는 하나다. 공개된 모듈러스 N = p·q를 소인수분해하는 게 어렵기 때문이다. 그걸 못 하면 φ(N) = (p-1)(q-1)을 모르고, 그러면 d = e⁻¹ mod φ(N)을 만들 수 없다.

그런데 이 문제의 "모듈러스"는 정수가 아니라 GF(2) 위의 다항식 n(X)다. 그리고 결정적으로 —

유한체 위 다항식 인수분해는 다항시간 알고리즘이 존재한다. (Berlekamp, Cantor–Zassenhaus)

정수 인수분해에는 다항시간 알고리즘이 없지만, 유한체 위에서는 있다. 4096차 다항식이라도 SageMath가 NTL을 통해 눈 깜짝할 사이에 쪼갠다. 이 하나의 차이가 문제 전체를 무너뜨린다.

n을 서로 다른 기약다항식들로 인수분해하면, 중국인의 나머지 정리(CRT)로 환이 분해된다.

R = GF(2)[X]/(n)  ≅  ∏ GF(2)[X]/(p_i)  =  ∏ GF(2^deg(p_i))

각 조각은 유한체 GF(2^dᵢ)이고, 그 곱셈군의 위수는 2^dᵢ - 1이다. 따라서 n이 제곱인수 없이(squarefree) 서로 다른 기약다항식 p₁…p_k로 쪼개지면, 환 R의 유닛군 위수는 N = ∏ (2^deg(p_i) - 1)이 된다.

이게 정수 RSA의 φ(N)에 대응한다. 이 N만 알면 복호 지수는 d = e⁻¹ mod N으로 바로 나오고, flag = c^d다.

그럼 실제로 쪼개 보자. 아래 factor_n.sage는 output.txt에서 n을 읽어 GF(2) 다항식으로 올린 뒤 .factor()를 부른다. 정수 비트 i를 X^i 계수로 해석하는데, 이건 gift.py가 int.from_bytes(..., 'big')로 바이트를 정수화한 방식과 비트 대응이 정확히 일치한다.

# factor_n.sage
import re, time
 
txt = open("extracted/output.txt").read()
n_int = int(re.search(r"n\s*=\s*(0x[0-9a-fA-F]+)", txt).group(1), 16)
c_int = int(re.search(r"c\s*=\s*(0x[0-9a-fA-F]+)", txt).group(1), 16)
print("n bitlen =", n_int.bit_length())
print("c bitlen =", c_int.bit_length())
 
P.<X> = PolynomialRing(GF(2))
 
def int_to_poly(v):
    return P([ (v >> i) & 1 for i in range(v.bit_length()) ])
 
n_poly = int_to_poly(n_int)
c_poly = int_to_poly(c_int)
print("deg(n) =", n_poly.degree())
 
t0 = time.time()
fac = n_poly.factor()
print("factor time = %.2fs" % (time.time()-t0))
print("num distinct factors =", len(fac))
degs = [(f.degree(), m) for f, m in fac]
print("factor (degree, multiplicity):")
for d, m in sorted(degs):
    print("   deg=%d  mult=%d" % (d, m))
print("sum deg*mult =", sum(d*m for d,m in degs))
print("squarefree =", all(m == 1 for _, m in fac))

sage factor_n.sage

0.16초다. 4096차 다항식이 차수 2, 9, 18, 25, 269, 437, 728, 2608짜리 기약다항식 8개로 쪼개졌고, 중복도는 전부 1 — squarefree다. 차수의 합이 정확히 4096으로 맞아떨어진다. 정수였다면 4096비트 반소수를 인수분해하는 셈이라 손도 못 댔을 일이, 다항식이라서 눈 깜짝할 사이에 끝났다.

인수분해가 정확한지도 한 번 되짚어 본다. 8개 기약다항식의 곱이 원래 n과 같아야 하고, 실제로 낮은 차수 인수들이 어떻게 생겼는지도 눈으로 보고 싶다.

# verify_factors.sage
fac = n_poly.factor()
prod_back = prod([p**m for p, m in fac])
print("product of factors == n :", prod_back == n_poly)
for p, m in sorted(fac, key=lambda t: t[0].degree())[:3]:
    print(f"   deg {p.degree():2d} :  {p}")

sage verify_factors.sage

곱이 n과 정확히 일치하고, 가장 작은 인수는 X^2 + X + 1(= GF(4)를 만드는 기약다항식)이다. 인수분해가 믿을 만하다는 걸 확인했으니, 이 조각들로 유닛군 위수를 조립할 차례다.

🎯 지수 역산 — gcd가 1이어야 유일하다

위수 N을 손에 넣었으니 d = e⁻¹ mod N을 구하면 된다. 단, 한 가지 조건을 확인해야 한다. e와 N이 서로소여야 e제곱 사상이 전단사가 되어 e제곱근이 유일하게 결정된다.

N은 ∏(2^dᵢ - 1) 꼴이다. e = 65537은 소수(페르마 소수 F4)이므로, gcd(e, N) ≠ 1이 되려면 어떤 2^dᵢ - 1이 65537을 인수로 가져야 한다. 65537이 2^dᵢ - 1을 나누는 것은 2의 65537에 대한 위수가 dᵢ를 나눌 때뿐이다.

2의 65537에 대한 위수는 32다. 2^16 = 65536 ≡ -1 (mod 65537)이므로 2^32 ≡ 1, 즉 ord₆₅₅₃₇(2) = 32. 따라서 어떤 기약인수의 차수가 32의 배수이면 거기서 e와 위수가 충돌한다. 인수들의 차수는 2, 9, 18, 25, 269, 437, 728, 2608인데 — 2608 = 32·81 + 16, 728 = 32·22 + 24 … 어느 것도 32로 나누어떨어지지 않는다.

말로만 하면 믿기 어려우니 직접 계산해 확인한다. check_coprime.py는 ord₆₅₅₃₇(2)를 2를 반복 제곱해 구하고, 각 인수 차수가 그 값의 배수인지, 그리고 gcd(65537, 2^dᵢ - 1)을 직접 계산한다.

# check_coprime.py
from math import gcd
 
e = 65537
degs = [2, 9, 18, 25, 269, 437, 728, 2608]   # factor_n.sage 결과
 
o = 1                      # ord_65537(2)
v = 2 % e
while v != 1:
    v = (v * 2) % e
    o += 1
print(f"ord_{e}(2) = {o}   (2^{o} ≡ 1 mod {e})")
 
bad = []
for d in degs:
    g = gcd(e, (pow(2, d) - 1))
    print(f"deg={d:5d}  d % {o} = {d % o:2d}   gcd(e, 2^d-1) = {g}")
    if g != 1:
        bad.append(d)
print("충돌하는 인수:", bad if bad else "없음 → gcd(e, N) = 1, e제곱근 유일")

python3 -I check_coprime.py

모든 gcd(e, 2^dᵢ - 1)이 1이므로 gcd(65537, N) = 1이고, e제곱근은 유일하다. 복호는 그냥 d = e⁻¹ mod N, flag = c^d로 끝난다. 만약 32의 배수 차수가 섞여 있었다면 그 조각에서만 따로 e제곱근을 뽑아 CRT로 붙여야 했을 것이다.

아래가 자체 완결 풀이 solve.sage다. 인수분해 → 위수 계산 → gcd 확인 → d = e⁻¹ → c^d → m^e == c 자체검산까지 한 번에 한다.

# solve.sage
import re
 
txt = open("extracted/output.txt").read()
n_int = int(re.search(r"n\s*=\s*(0x[0-9a-fA-F]+)", txt).group(1), 16)
c_int = int(re.search(r"c\s*=\s*(0x[0-9a-fA-F]+)", txt).group(1), 16)
e = 0x10001
 
P.<X> = PolynomialRing(GF(2))
def int_to_poly(v):
    return P([ (v >> i) & 1 for i in range(v.bit_length()) ])
def poly_to_int(p):
    return sum(int(co) << i for i, co in enumerate(p.list()))
 
n_poly = int_to_poly(n_int)
c_poly = int_to_poly(c_int)
 
fac = n_poly.factor()
print("[*] factors (deg, mult):", [(f.degree(), m) for f, m in fac])
 
# 유닛군 위수 (squarefree 가정; 아니면 2^(deg*(mult-1)) 항 추가)
N = 1
for f, m in fac:
    d = f.degree()
    N *= (2**d - 1)
    if m > 1:
        N *= 2**(d * (m - 1))
 
g = gcd(e, N)
print("[*] gcd(e, N) =", g)
assert g == 1, "e 와 유닛군 위수가 서로소가 아님 — per-factor 근 추출 필요"
 
d = inverse_mod(e, N)
print("[*] d bitlen =", int(d).bit_length())
 
Q = P.quotient(n_poly, 'x')
m_poly = (Q(c_poly) ** d).lift()
 
# 검산: m^e == c ?
assert (Q(m_poly) ** e).lift() == c_poly, "복호 검산 실패"
print("[*] self-check m^e == c : OK")
 
m_int = poly_to_int(m_poly)
mb = int(m_int).to_bytes((int(m_int).bit_length() + 7) // 8, 'big')
print("[*] recovered leading bytes:", mb[:48])
 
import re as _re
mt = _re.search(rb"DH\{[^}]*\}", mb)
print("[+] FLAG =", (mt.group().decode() if mt else "(DH{...} 못 찾음) raw=" + mb[:64].hex()))

sage solve.sage

d는 4094비트, 자체검산 m^e == c가 OK로 통과한다. 복원된 평문의 앞부분이 DH{...로 바로 읽히고, 뒷부분은 gift.py가 os.urandom으로 채운 패딩이다.

DH{finite_field_factorization_is_easy_and_sagemath_is_god}

플래그 문구 자체가 이 풀이의 요약이다 — 유한체 인수분해는 쉽다, 그리고 SageMath는 신이다.

🚀 재현 — 백업만으로 flag까지

reproduce.sh는 solve.sage를 돌려 나온 플래그를 기대값과 대조해 PASS/FAIL을 스스로 판정한다. 백업 폴더만 있으면 한 줄로 끝까지 재현된다.

#!/usr/bin/env bash
# Red-Black Christmas Tree — 한 방 재현.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
EXPECT='DH{finite_field_factorization_is_easy_and_sagemath_is_god}'
 
OUT=$(timeout 300 sage solve.sage 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

bash reproduce.sh

📝 결론

다항식 RSA는 RSA가 아니다.

겉모습은 완벽한 RSA다. 공개지수 65537, square-and-multiply 거듭제곱, 공개된 모듈러스와 암호문. 하지만 모듈러스를 정수에서 GF(2) 위 다항식으로 바꾸는 순간, RSA의 안전성을 떠받치던 유일한 기둥 — 인수분해의 어려움 — 이 사라진다. 유한체 위 다항식 인수분해는 Berlekamp·Cantor–Zassenhaus로 다항시간에 풀리기 때문이다.

유닛군 위수가 곧 φ다.

n이 squarefree로 쪼개지면 환은 CRT로 유한체들의 곱이 되고, 유닛군 위수는 ∏(2^dᵢ - 1)로 바로 계산된다. 정수 RSA에서 소인수를 알면 φ를 알듯, 다항식 RSA에서는 기약인수를 알면 위수를 안다. 이후 d = e⁻¹ mod N은 기계적이다.

서로소 조건은 공짜가 아니다.

이 문제는 운 좋게(혹은 출제자가 그렇게 설계해서) 어떤 기약인수의 차수도 ord₆₅₅₃₇(2) = 32의 배수가 아니라 gcd(e, N) = 1이 성립했다. 만약 32의 배수 차수가 섞였다면 그 조각에서는 e제곱근이 유일하지 않아, 해당 유한체에서만 따로 근을 뽑아 CRT로 결합하는 추가 작업이 필요했을 것이다. 복호 전에 gcd를 확인하는 습관이 그래서 중요하다.

GHASH·AES-GCM이 쓰는 이진체 산술은 실제로 쓰이는 암호의 일부지만, 거기에 공개키 지수 연산을 얹는 순간 전혀 다른 취약성이 생긴다는 걸 보여주는 문제였다.