[🥇 Gold 2] 두 배점 x 좌표 하나로 키 두 개 되찾기 — DreamHack Elliptic Curve Basic 풀이

#!/usr/bin/env bash
# Elliptic Curve Basic — 배포본 정찰. 파일이 뭐가 왔고 얼마나 되는지부터 센다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
echo "== 배포본 =="
ls -la extracted/
sha256sum challenge_1881.zip extracted/*
 
echo
echo "== 줄 수 =="
wc -l extracted/chal.sage extracted/output.txt
 
echo
echo "== output.txt 앞 4줄 =="
head -4 extracted/output.txt | cut -c1-96
 
echo
echo "== 공개된 것: 계수 4개짜리 1차식이 쌍으로 =="
grep -c 'key1' extracted/output.txt
grep -c 'key2' extracted/output.txt

./recon.sh

# NIST P-256 Parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
 
Zp = Zmod(p)
P256 = EllipticCurve(Zp, [a, b])
 
key1 = Zp.random_element()
key2 = Zp.random_element()
 
for _ in range(10):
    P = P256.random_point()
    Q = P + P
 
    b = Zp.random_element()
    a = (P.xy()[0] - b) / key1
 
    d = Zp.random_element()
    c = (Q.xy()[0] - d) / key2
 
    print(f"P.x = {a} * key1 + {b}")
    print(f"Q.x = {c} * key2 + {d}")
 
with open('flag', 'w') as f:
    key = int(key1) ^^ int(key2)
    f.write(f"Flag is DH{{{key:064x}}}")

P.x = 27714350255388021111232531170591641212949833102971307193980499863801255688154 * key1 + 46284378768605864622170543556599427573485337746700029009471119922484581943469
Q.x = 60647595877197062890203383385574231236668829536178956561727275653380079298295 * key2 + 82566598899232397169905495928712993370226968781169912617729109115055982292654

#!/usr/bin/env bash
# chal.sage 맨 위 상수 세 개가 정말 NIST P-256 인지 openssl 로 대조한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
echo "== openssl 이 아는 prime256v1 (= NIST P-256) =="
openssl ecparam -name prime256v1 -param_enc explicit -text -noout | sed -n '1,16p'
 
echo
echo "== chal.sage 상수와 대조 =="
openssl ecparam -name prime256v1 -param_enc explicit -text -noout \
  | python3 cmp_params.py extracted/chal.sage

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""openssl ecparam 의 텍스트 출력(stdin)에서 Prime/A/B 를 뽑아 chal.sage 상수와 비교한다."""
import re
import sys
 
import sympy
 
text = sys.stdin.read()
 
 
def grab(label):
    m = re.search(rf'^{label}:\s*\n((?:\s+[0-9a-f:]+\n)+)', text, re.M)
    return int(re.sub(r'[^0-9a-f]', '', m.group(1)), 16)
 
 
src = open(sys.argv[1], encoding='utf-8').read()
mine = {k: int(v, 16) for k, v in re.findall(r'^(p|a|b) = (0x[0-9a-f]+)$', src, re.M)}
theirs = {'p': grab('Prime'), 'a': grab('A'), 'b': grab('B')}
 
for k in ('p', 'a', 'b'):
    same = mine[k] == theirs[k]
    print(f"[{'+' if same else '!'}] {k}: chal.sage {'==' if same else '!='} openssl   {mine[k]:#x}")
 
prime, curve_a = mine['p'], mine['a']
print(f"[+] a == p-3 ? {curve_a == prime - 3}")
print(f"[+] p 는 소수 ? {sympy.isprime(prime)}")
print(f"[+] p mod 4 = {prime % 4}   (오일러 판정·제곱근 지름길이 그대로 먹는다)")

./check_params.sh

b = Zp.random_element()
a = (P.xy()[0] - b) / key1

# chal.sage 의 루프는 곡선 계수와 같은 이름의 a, b 를 덮어쓴다.
# 그래도 P256 은 루프 전에 만들어졌으니 계수가 안 바뀐다는 것을 Sage 로 직접 본다.
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
 
Zp = Zmod(p)
P256 = EllipticCurve(Zp, [a, b])
print("[before] P256.a4() ==", hex(Integer(P256.a4())))
print("[before] P256.a6() ==", hex(Integer(P256.a6())))
 
set_random_seed(7)
for i in range(3):                      # chal.sage 루프가 하는 그대로
    b = Zp.random_element()
    a = Zp.random_element()
    print(f"  루프 {i}: 지역 a, b 가 난수로 덮였다  a={hex(Integer(a))[:18]}...")
 
print("[after ] 파이썬 변수 a ==", hex(Integer(a))[:18], "...  (완전히 다른 값)")
print("[after ] P256.a4() ==", hex(Integer(P256.a4())))
print("[after ] P256.a6() ==", hex(Integer(P256.a6())))
print("[check ] 곡선 계수가 그대로인가 ?", P256.a4() == Zp(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc))
 
# 출력 줄에 실린 a, b 는 곡선과 아무 상관이 없는 "그 줄의 1차식 계수" 다
P = P256.random_point()
bb = Zp.random_element()
aa = (P.xy()[0] - bb) / Zp(12345)
print(f"[what  ] 출력의 'a * key1 + b' 에서 a 는 (P.x - b)/key1 — 곡선 계수가 아니다")
print(f"          예: a = {str(aa)[:40]}...")

sage shadow_check.sage

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
한 쌍(P.x 한 줄 + Q.x 한 줄)만으로는 아무것도 정해지지 않는다는 것을 수로 확인한다.
아무 key1 을 골라도 그에 맞는 key2 가 따라오기 때문이다.
 
    python3 one_pair.py
"""
 
import random
 
import solve as S
 
pairs = S.parse('extracted/output.txt')
U0, V0 = S.uv(pairs[0])
TRUE_K1 = 0x73634a17f599c4121843466d8f3c166eff3c3623445123cd2660754804f9ec76
 
 
def k2_for(k1):
    v = S.peval(V0, k1)
    return None if v == 0 else S.peval(U0, k1) * pow(v, S.P - 2, S.P) % S.P
 
 
def hits(k1, k2):
    n = 0
    for (A, B), (C, D) in pairs:
        xp = (A * k1 + B) % S.P
        xq = (C * k2 + D) % S.P
        m = (pow(xp, 3, S.P) + S.CA * xp + S.CB) % S.P
        if (S.peval(S.N_POLY, xp) - 4 * m * xq) % S.P == 0:
            n += 1
    return n
 
 
print("[1] 1번 쌍만 놓고 아무 key1 이나 넣어 본다")
for k1 in (1, 2, 0xdeadbeef, TRUE_K1):
    k2 = k2_for(k1)
    label = " <= 진짜 key1" if k1 == TRUE_K1 else ""
    disp = hex(k1) if len(hex(k1)) <= 20 else hex(k1)[:20] + "..."
    print(f"    k1={disp:<23}  ->  k2 가 항상 존재,  10쌍 중 {hits(k1, k2)}쌍 만족{label}")
 
print("\n[2] 무작위 k1 200개로 같은 실험")
rng = random.Random(20260819)
on_curve = 0
for _ in range(200):
    k1 = rng.randrange(S.P)
    k2 = k2_for(k1)
    assert hits(k1, k2) >= 1, "1번 쌍은 언제나 만족한다"
    xp = (pairs[0][0][0] * k1 + pairs[0][0][1]) % S.P
    on_curve += S.is_on_curve_x(xp)
print(f"    1번 쌍을 만족한 k1: 200 / 200")
print(f"    그중 x_P 가 실제 곡선 위인 것: {on_curve} / 200  (약 절반)")
print(f"    -> 한 쌍이 남기는 해는 대략 p/2 = 2^255 개다. 정보가 없는 것과 같다")
 
print("\n[3] 두 쌍을 겹치면")
U1, V1 = S.uv(pairs[1])
R = S.psub(S.pmul(U0, V1), S.pmul(U1, V0))
print(f"    R = U0*V1 - U1*V0 의 근: {len(S.roots_mod_p(R))}개")

python3 one_pair.py

곡선   y^2 = x^3 + a*x + b
접선   lambda = (3*x^2 + a) / (2*y)
두 배점 x_2P = lambda^2 - 2*x

lambda^2 = (3x^2+a)^2 / (4*y^2)
         = (3x^2+a)^2 / (4*(x^3+a*x+b))

x_Q = [ (3x^2+a)^2 - 8x*(x^3+a*x+b) ] / [ 4*(x^3+a*x+b) ]
    = ( x^4 - 2a*x^2 - 8b*x + a^2 ) / ( 4*(x^3 + a*x + b) )

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
두 배점의 x 가 x_P 만의 유리함수라는 것을 sympy 로 기호 전개해 확인하고,
NIST P-256 위의 실제 점으로 수치까지 맞춰 본다.
 
    python3 derive.py
"""
 
import sympy as sp
 
x, y, a, b, xq = sp.symbols('x y a b x_Q')
 
# lambda = (3x^2+a)/(2y),  x_{2P} = lambda^2 - 2x,  y^2 = x^3+ax+b
lam2 = (3 * x**2 + a)**2 / (4 * (x**3 + a * x + b))          # y^2 를 대입해 y 를 지운다
num = sp.expand(sp.simplify(lam2 * 4 * (x**3 + a * x + b) - 8 * x * (x**3 + a * x + b)))
 
print("[1] lambda^2 의 분자에서 8x*(x^3+ax+b) 를 뺀 것")
print("    ", sp.factor_terms(num))
 
target = x**4 - 2 * a * x**2 - 8 * b * x + a**2
print("[2] 예상한 N(x) = x^4 - 2a x^2 - 8b x + a^2")
print("    차이 =", sp.expand(num - target), " (0 이면 일치)")
 
rel = sp.expand(xq * 4 * (x**3 + a * x + b) - target)
print("[3] 최종 관계식  x_Q*4*(x^3+ax+b) - N(x) = 0")
print("    x 에 대한 차수 =", sp.Poly(rel, x).degree(), ", x_Q 에 대한 차수 =", sp.Poly(rel, xq).degree())
 
# ---- 진짜 P-256 점으로 수치 확인 -------------------------------------------
P = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
CA = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
CB = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
# P-256 의 표준 생성점 G (SEC 2)
GX = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
GY = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
 
 
def dbl(px, py):
    lam = (3 * px * px + CA) * pow(2 * py, P - 2, P) % P
    rx = (lam * lam - 2 * px) % P
    return rx, (lam * (px - rx) - py) % P
 
 
gx2, _ = dbl(GX, GY)
rhs = (pow(GX, 4, P) - 2 * CA * GX * GX - 8 * CB * GX + CA * CA) % P
lhs = gx2 * 4 * (pow(GX, 3, P) + CA * GX + CB) % P
print("[4] 생성점 G 로 수치 확인")
print("    2G.x            =", hex(gx2))
print("    N(G.x)/(4M(G.x)) =", hex(rhs * pow(4 * (pow(GX, 3, P) + CA * GX + CB) % P, P - 2, P) % P))
print("    좌변 == 우변 ?", lhs == rhs)

python3 derive.py

x_Q * 4*M(x_P)  -  N(x_P)  =  0

U(k) = N(A*k + B) - 4*D*M(A*k + B)     (4차)
V(k) = 4*C*M(A*k + B)                  (3차)
key2 = U(k) / V(k)

R(k) = U_i(k)*V_j(k) - U_j(k)*V_i(k) = 0     (4+3 = 7차)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
소거가 실제로 어떤 모양인지 눈으로 본다.
key2 가 1차라서 U/V 로 떨어지고, 두 쌍을 교차하면 7차 한 개만 남는다.
 
    python3 build_polys.py
"""
 
import solve as S
 
pairs = S.parse('extracted/output.txt')
print(f"쌍 {len(pairs)}개, 미지수는 key1, key2 둘")
 
U0, V0 = S.uv(pairs[0])
U1, V1 = S.uv(pairs[1])
print(f"\n1번 쌍:  U0 차수 {len(U0)-1}  V0 차수 {len(V0)-1}   ->  key2 = U0(k)/V0(k)")
print(f"2번 쌍:  U1 차수 {len(U1)-1}  V1 차수 {len(V1)-1}   ->  key2 = U1(k)/V1(k)")
 
R = S.psub(S.pmul(U0, V1), S.pmul(U1, V0))
print(f"\nR = U0*V1 - U1*V0   차수 {len(R)-1}  (4+3)")
print(f"  최고차 계수 {R[-1]:#x}")
print(f"  상수항     {R[0]:#x}")
print(f"  0 다항식인가 ? {R == []}")
 
# 세 번째 쌍으로 만든 R' 이 같은 근을 공유하는지 (독립 확인)
U2, V2 = S.uv(pairs[2])
R2 = S.psub(S.pmul(U0, V2), S.pmul(U2, V0))
r1 = set(S.roots_mod_p(R))
r2 = set(S.roots_mod_p(R2))
print(f"\n1-2 쌍의 근 {len(r1)}개, 1-3 쌍의 근 {len(r2)}개, 공통 {len(r1 & r2)}개")
for k in sorted(r1 & r2):
    print(f"  공통근 {k:#066x}")

python3 build_polys.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
DreamHack / Elliptic Curve Basic (Gold 2, crypto) — 자체완결 풀이
 
무엇을 푸는가
--------------
chal.sage 는 NIST P-256 위에서 랜덤 점 P 와 그 두 배점 Q = 2P 를 10쌍 만들고,
두 점의 x 좌표를 각각 key1 / key2 에 대한 1차식으로만 흘린다.
 
    P.x = A*key1 + B      (A, B 공개)
    Q.x = C*key2 + D      (C, D 공개)
 
flag 는 key1 XOR key2 다. 점 자체는 하나도 공개되지 않지만, "Q 는 P 의 두 배점" 이라는
사실이 x 좌표 둘을 하나의 대수 관계로 묶는다.
 
    y^2 = x^3 + a*x + b  이므로  lambda = (3x^2+a)/(2y),  x_Q = lambda^2 - 2*x_P
    => x_Q = ( x_P^4 - 2a*x_P^2 - 8b*x_P + a^2 ) / ( 4*(x_P^3 + a*x_P + b) )
 
y 는 제곱으로만 등장해서 사라진다. 즉 x_Q 는 x_P 만의 유리함수다.
여기에 위 1차식을 대입하면 미지수가 key1, key2 둘뿐인 방정식이 한 쌍마다 하나 나온다.
게다가 key2 에 대해 1차라서 곧바로 소거된다.
 
    U_i(k) = N(A_i*k + B_i) - 4*D_i*M(A_i*k + B_i)      (4차)
    V_i(k) = 4*C_i*M(A_i*k + B_i)                        (3차)
    key2 = U_i(key1) / V_i(key1)
 
서로 다른 두 쌍 i, j 의 key2 표현이 같아야 하므로
 
    R(k) = U_i(k)*V_j(k) - U_j(k)*V_i(k) = 0            (7차)
 
7차 다항식의 GF(p) 근을 전부 구해 나머지 8쌍으로 걸러내면 key1 이 유일하게 남는다.
 
의존성
-------
파이썬 표준 라이브러리만 쓴다. sage / sympy / gmpy2 불필요.
GF(p)[x] 위의 근 찾기(gcd(x^p - x, R) + Cantor-Zassenhaus)도 직접 구현했다.
 
사용법
-------
    python3 solve.py [output.txt]
"""
 
import re
import random
import sys
 
# ---------------------------------------------------------------- 곡선 파라미터
# NIST P-256. chal.sage 의 루프가 같은 이름의 지역변수 a, b 를 덮어쓰지만
# 곡선은 그 전에 이미 만들어졌으므로 여기서 쓰는 값은 언제나 아래 상수다.
P  = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
CA = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
CB = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
 
 
# ------------------------------------------------------- GF(p)[x] 다항식 유틸
# 계수 리스트는 리틀엔디언이다. [c0, c1, c2] == c0 + c1*x + c2*x^2
def trim(f):
    while f and f[-1] == 0:
        f.pop()
    return f
 
 
def padd(f, g):
    n = max(len(f), len(g))
    return trim([((f[i] if i < len(f) else 0) + (g[i] if i < len(g) else 0)) % P
                 for i in range(n)])
 
 
def psub(f, g):
    n = max(len(f), len(g))
    return trim([((f[i] if i < len(f) else 0) - (g[i] if i < len(g) else 0)) % P
                 for i in range(n)])
 
 
def pmul(f, g):
    if not f or not g:
        return []
    r = [0] * (len(f) + len(g) - 1)
    for i, fi in enumerate(f):
        if fi:
            for j, gj in enumerate(g):
                r[i + j] = (r[i + j] + fi * gj) % P
    return trim(r)
 
 
def pscale(f, c):
    c %= P
    return trim([(x * c) % P for x in f])
 
 
def pdivmod(f, g):
    """f = q*g + r"""
    f = f[:]
    if len(f) < len(g):
        return [], f
    inv_lead = pow(g[-1], P - 2, P)
    q = [0] * (len(f) - len(g) + 1)
    while len(f) >= len(g) and f:
        d = len(f) - len(g)
        c = (f[-1] * inv_lead) % P
        q[d] = c
        for i, gi in enumerate(g):
            f[i + d] = (f[i + d] - c * gi) % P
        trim(f)
    return trim(q), f
 
 
def pmod(f, g):
    return pdivmod(f, g)[1]
 
 
def pgcd(f, g):
    f, g = f[:], g[:]
    while g:
        f, g = g, pmod(f, g)
    if f:
        f = pscale(f, pow(f[-1], P - 2, P))   # monic
    return f
 
 
def ppow_mod(base, e, mod):
    """base^e mod (mod) in GF(p)[x]"""
    r = [1]
    base = pmod(base, mod)
    while e:
        if e & 1:
            r = pmod(pmul(r, base), mod)
        base = pmod(pmul(base, base), mod)
        e >>= 1
    return r
 
 
def peval(f, x):
    acc = 0
    for c in reversed(f):
        acc = (acc * x + c) % P
    return acc
 
 
def pcompose_linear(f, A, B):
    """f(A*x + B) — Horner 로 전개한다"""
    inner = [B % P, A % P]
    acc = []
    for c in reversed(f):
        acc = padd(pmul(acc, inner), [c % P])
    return trim(acc)
 
 
# --------------------------------------------------- GF(p) 위의 근 전부 찾기
def _cz_split(g, rng):
    """g 는 서로 다른 1차 인수들의 곱(square-free, 전부 GF(p)에 근이 있음)"""
    if len(g) <= 1:
        return []
    if len(g) == 2:                       # c1*x + c0
        return [(-g[0] * pow(g[1], P - 2, P)) % P]
    while True:
        delta = rng.randrange(P)
        w = ppow_mod([delta, 1], (P - 1) // 2, g)      # (x+delta)^((p-1)/2) mod g
        h = pgcd(psub(w, [1]), g)
        if 0 < len(h) - 1 < len(g) - 1:
            q, _ = pdivmod(g, h)
            return _cz_split(h, rng) + _cz_split(q, rng)
 
 
def roots_mod_p(f, seed=0xC0FFEE):
    """f 의 GF(p) 근(중복 제거)을 전부 돌려준다"""
    f = trim(f[:])
    if not f:
        raise ValueError("영다항식")
    f = pscale(f, pow(f[-1], P - 2, P))
    xp = ppow_mod([0, 1], P, f)                # x^p mod f
    g = pgcd(psub(xp, [0, 1]), f)              # gcd(x^p - x, f) = 모든 1차 인수의 곱
    return sorted(_cz_split(g, random.Random(seed)))
 
 
# ------------------------------------------------------------------- 문제 파싱
LINE = re.compile(r'^([PQ])\.x = (\d+) \* key([12]) \+ (\d+)$')
 
 
def parse(path):
    pairs, cur = [], {}
    for line in open(path, encoding='utf-8'):
        m = LINE.match(line.strip())
        if not m:
            continue
        which, coef, keyno, const = m.group(1), int(m.group(2)), m.group(3), int(m.group(4))
        assert (which, keyno) in (('P', '1'), ('Q', '2')), "P는 key1, Q는 key2 여야 한다"
        cur[which] = (coef % P, const % P)
        if 'P' in cur and 'Q' in cur:
            pairs.append((cur['P'], cur['Q']))
            cur = {}
    return pairs
 
 
# --------------------------------------------------------------------- 풀이
# x_Q = N(x_P) / (4*M(x_P))
N_POLY = [CA * CA % P, (-8 * CB) % P, (-2 * CA) % P, 0, 1]   # x^4 - 2a x^2 - 8b x + a^2
M_POLY = [CB % P, CA % P, 0, 1]                              # x^3 + a x + b
 
 
def uv(pair):
    """한 쌍에서 U(k), V(k) 를 만든다.  key2 = U(key1) / V(key1)"""
    (A, B), (C, D) = pair
    Nc = pcompose_linear(N_POLY, A, B)          # 4차
    Mc = pcompose_linear(M_POLY, A, B)          # 3차
    U = psub(Nc, pscale(Mc, 4 * D % P))
    V = pscale(Mc, 4 * C % P)
    return U, V
 
 
def is_on_curve_x(x):
    """x 가 곡선 위 점의 x 좌표인가 (오일러 판정)"""
    rhs = (pow(x, 3, P) + CA * x + CB) % P
    return rhs == 0 or pow(rhs, (P - 1) // 2, P) == 1
 
 
def solve(pairs):
    U0, V0 = uv(pairs[0])
    U1, V1 = uv(pairs[1])
    R = psub(pmul(U0, V1), pmul(U1, V0))
    print(f"[*] 소거 다항식 R(k1) 차수 = {len(R) - 1}")
 
    cands = roots_mod_p(R)
    print(f"[*] GF(p) 근 {len(cands)}개")
 
    good = []
    for k1 in cands:
        v0 = peval(V0, k1)
        if v0 == 0:
            continue
        k2 = peval(U0, k1) * pow(v0, P - 2, P) % P
        ok = True
        for (A, B), (C, D) in pairs:                    # 10쌍 전부로 검증
            xp = (A * k1 + B) % P
            xq = (C * k2 + D) % P
            m = (pow(xp, 3, P) + CA * xp + CB) % P
            if m == 0 or not is_on_curve_x(xp):
                ok = False
                break
            if (peval(N_POLY, xp) - 4 * m % P * xq) % P != 0:
                ok = False
                break
        if ok:
            good.append((k1, k2))
    return good
 
 
def main():
    path = sys.argv[1] if len(sys.argv) > 1 else 'extracted/output.txt'
    pairs = parse(path)
    print(f"[*] {path}: (P.x, Q.x) 쌍 {len(pairs)}개")
    good = solve(pairs)
    if not good:
        print("[!] 후보 없음")
        return 1
    for k1, k2 in good:
        key = k1 ^ k2
        print(f"[+] key1 = {k1:#066x}")
        print(f"[+] key2 = {k2:#066x}")
        print(f"[+] FLAG = DH{{{key:064x}}}")
    return 0
 
 
if __name__ == '__main__':
    sys.exit(main())

python3 solve.py extracted/output.txt

DH{805f461baa9ee08b66191f9309e976aedf28cff9d130ce19941ff6b3a19ad634}

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Elliptic Curve Basic — 오독 4종을 실제로 돌려 본다.
 
"이렇게 읽으면 틀린다" 를 말로만 적으면 확인이 안 된다. 네 가지 오독을 각각 코드로 구현해
같은 output.txt 에 돌리고, 무엇이 나오는지 숫자로 남긴다. solve.py 의 다항식 유틸을 그대로
가져다 쓰므로 차이는 "관계식을 어떻게 세웠는가" 뿐이다.
 
    python3 traps.py
"""
 
import solve as S
 
TRUE_FLAG = "DH{805f461baa9ee08b66191f9309e976aedf28cff9d130ce19941ff6b3a19ad634}"
P, CA, CB = S.P, S.CA, S.CB
pairs = S.parse('extracted/output.txt')
 
 
def flag_of(k1, k2):
    return f"DH{{{(k1 ^ k2):064x}}}"
 
 
def survivors(U0, V0, relation):
    """R 의 근마다 key2 를 뽑고, 10쌍 전부를 만족하는지 센다"""
    U1, V1 = relation(pairs[1])
    R = S.psub(S.pmul(U0, V1), S.pmul(U1, V0))
    if not R:
        return None, []
    out = []
    for k1 in S.roots_mod_p(R):
        v0 = S.peval(V0, k1)
        if v0 == 0:
            continue
        k2 = S.peval(U0, k1) * pow(v0, P - 2, P) % P
        hit = 0
        for (A, B), (C, D) in pairs:
            xp = (A * k1 + B) % P
            xq = (C * k2 + D) % P
            m = (pow(xp, 3, P) + CA * xp + CB) % P
            if (S.peval(S.N_POLY, xp) - 4 * m * xq) % P == 0:
                hit += 1
        out.append((k1, k2, hit))
    return len(R) - 1, out
 
 
# ---------------------------------------------------------------- 함정 1
def trap1():
    """두 쌍만 쓰고 나머지 8쌍으로 거르지 않는다"""
    print("[함정1] 두 쌍만 세우고 검증을 생략하면")
    deg, out = survivors(*S.uv(pairs[0]), S.uv)
    print(f"        R 차수 {deg}, 근 {len(out)}개 — 셋 다 64자리 hex flag 가 나온다")
    for k1, k2, hit in out:
        mark = "  <= 정답" if flag_of(k1, k2) == TRUE_FLAG else ""
        print(f"        {flag_of(k1, k2)}  (10쌍 중 {hit}쌍 만족){mark}")
    print("        -> 눈으로는 못 고른다. 남은 8쌍이 유일한 판별기다\n")
 
 
# ---------------------------------------------------------------- 함정 2
def trap2():
    """(2y)^2 = 4(x^3+ax+b) 의 4 를 빠뜨린다"""
    print("[함정2] lambda^2 의 분모에서 4 를 빠뜨리면  (x_Q*(x^3+ax+b) = N(x))")
 
    def uv_no4(pair):
        (A, B), (C, D) = pair
        Nc = S.pcompose_linear(S.N_POLY, A, B)
        Mc = S.pcompose_linear(S.M_POLY, A, B)
        return S.psub(Nc, S.pscale(Mc, D)), S.pscale(Mc, C)
 
    deg, out = survivors(*uv_no4(pairs[0]), uv_no4)
    good = [o for o in out if o[2] == 10]
    print(f"        R 차수 {deg}, 근 {len(out)}개, 10쌍 전부 만족 {len(good)}개")
    print(f"        -> 후보가 {'전멸' if not good else '남는다'}. 4 는 장식이 아니다\n")
 
 
# ---------------------------------------------------------------- 함정 3
def trap3():
    """출력 줄의 상수 이름이 곡선 계수와 겹친다 (a, b)"""
    print("[함정3] 출력 줄의 b, d 를 곡선 계수로 착각하면 (chal.sage 가 루프에서 a, b 를 덮어쓴다)")
    lastA, lastB = pairs[-1][0]
    lastC, lastD = pairs[-1][1]
    fakeA, fakeB = lastA, lastB      # 마지막 반복이 남긴 a, b
    Nf = [fakeA * fakeA % P, (-8 * fakeB) % P, (-2 * fakeA) % P, 0, 1]
    Mf = [fakeB % P, fakeA % P, 0, 1]
 
    def uv_fake(pair):
        (A, B), (C, D) = pair
        Nc = S.pcompose_linear(Nf, A, B)
        Mc = S.pcompose_linear(Mf, A, B)
        return S.psub(Nc, S.pscale(Mc, 4 * D % P)), S.pscale(Mc, 4 * C % P)
 
    deg, out = survivors(*uv_fake(pairs[0]), uv_fake)
    good = [o for o in out if o[2] == 10]
    print(f"        R 차수 {deg}, 근 {len(out)}개, 10쌍 전부 만족 {len(good)}개")
    print(f"        -> {len(good)}개. 곡선은 루프 전에 이미 만들어졌으므로 계수는 NIST 값 그대로다\n")
 
 
# ---------------------------------------------------------------- 함정 4
def trap4():
    """P 와 Q 를 맞바꿔 P = 2Q 로 세운다"""
    print("[함정4] 배점 방향을 뒤집어 P = 2Q 로 세우면")
 
    def uv_rev(pair):
        (A, B), (C, D) = pair
        Nc = S.pcompose_linear(S.N_POLY, C, D)     # 이번엔 x_Q 가 안쪽
        Mc = S.pcompose_linear(S.M_POLY, C, D)
        return S.psub(Nc, S.pscale(Mc, 4 * B % P)), S.pscale(Mc, 4 * A % P)
 
    U0, V0 = uv_rev(pairs[0])
    U1, V1 = uv_rev(pairs[1])
    R = S.psub(S.pmul(U0, V1), S.pmul(U1, V0))
    cnt = 0
    for k2 in S.roots_mod_p(R):
        v0 = S.peval(V0, k2)
        if v0 == 0:
            continue
        k1 = S.peval(U0, k2) * pow(v0, P - 2, P) % P
        hit = 0
        for (A, B), (C, D) in pairs:
            xq = (C * k2 + D) % P
            xp = (A * k1 + B) % P
            m = (pow(xq, 3, P) + CA * xq + CB) % P
            if (S.peval(S.N_POLY, xq) - 4 * m * xp) % P == 0:
                hit += 1
        if hit == 10:
            cnt += 1
    print(f"        R 차수 {len(R) - 1}, 10쌍 전부 만족 {cnt}개")
    print(f"        -> {cnt}개. 두 배점 관계는 방향이 있다\n")
 
 
if __name__ == '__main__':
    print(f"정답 flag = {TRUE_FLAG}\n")
    trap1(); trap2(); trap3(); trap4()

python3 traps.py

# solve.py 와 완전히 다른 경로로 같은 답이 나오는지 본다.
#  (1) Sage 의 그뢰브너 기저(lex, k2 > k1)로 key2 를 소거해 key1 을 독립 계산
#      - Singular 은 characteristic > 2^29 에서 resultant 를 거부하지만 std 는 된다
#  (2) 복원한 key 로 x 좌표를 되살려, 진짜 P256 위의 점 P 를 세우고 2*P 의 x 가 맞는지 확인
#      - 이쪽은 내 대수 유도를 하나도 안 쓴다. Sage 자신의 군 연산으로만 판정한다
import re, sys
 
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Fp = GF(p)
P256 = EllipticCurve(Fp, [a, b])
print(f"[sage] {P256}")
print(f"[sage] #E = {P256.order()}")
 
path = sys.argv[1] if len(sys.argv) > 1 else 'extracted/output.txt'
pat = re.compile(r'^([PQ])\.x = (\d+) \* key([12]) \+ (\d+)$')
pairs, cur = [], {}
for line in open(path):
    m = pat.match(line.strip())
    if not m:
        continue
    cur[m.group(1)] = (Integer(m.group(2)), Integer(m.group(4)))
    if 'P' in cur and 'Q' in cur:
        pairs.append((cur['P'], cur['Q'])); cur = {}
print(f"[sage] {path}: 쌍 {len(pairs)}개 파싱")
 
R.<k2, k1> = PolynomialRing(Fp, 2, order='lex')       # lex 로 k2 를 먼저 없앤다
 
def rel(pair):
    (A, B), (C, D) = pair
    xP = A*k1 + B
    xQ = C*k2 + D
    #  x_Q * 4*(x^3 + a x + b)  ==  x^4 - 2a x^2 - 8b x + a^2
    return xQ*4*(xP^3 + a*xP + b) - (xP^4 - 2*a*xP^2 - 8*b*xP + a^2)
 
gb = Ideal(rel(pairs[0]), rel(pairs[1])).groebner_basis()
elim = [g for g in gb if k2 not in g.variables()]
print(f"[sage] 그뢰브너 기저 원소 {len(gb)}개, k2 가 사라진 것 {len(elim)}개")
poly = elim[0].univariate_polynomial()
print(f"[sage] 소거 다항식 차수 = {poly.degree()}")
cands = [Integer(r) for r, _ in poly.roots()]
print(f"[sage] GF(p) 근 {len(cands)}개")
 
found = 0
for c in cands:
    g = rel(pairs[0]).subs(k1=Fp(c)).univariate_polynomial()
    for r2, _ in g.roots():
        c2 = Integer(r2)
        if not all(rel(pr).subs(k1=Fp(c), k2=Fp(c2)) == 0 for pr in pairs):
            continue
        print(f"[sage] key1 = {c:#066x}")
        print(f"[sage] key2 = {c2:#066x}")
        for i, ((A, B), (C, D)) in enumerate(pairs):     # 여기부터는 순수 군 연산
            xP = Fp(A)*Fp(c) + Fp(B)
            xQ = Fp(C)*Fp(c2) + Fp(D)
            pt = P256.lift_x(xP)                          # 진짜 곡선 위로 올린다
            assert (2*pt).xy()[0] == xQ, f"쌍 {i}: 2P 의 x 가 Q.x 와 다르다"
        print(f"[sage] 10쌍 전부 lift_x(P.x) 의 2배점 x 가 Q.x 와 일치")
        print(f"[sage] FLAG = DH{{{(int(c) ^^ int(c2)):064x}}}")
        found += 1
print(f"[sage] 조건을 만족하는 (key1,key2) = {found}쌍")

sage verify_sage.sage extracted/output.txt

# chal.sage 를 그대로 두고 "정답을 아는 새 인스턴스"만 더 찍어내는 오라클.
# 배포본과 다른 곳은 세 군데뿐이다: set_random_seed / 파일로 출력 / key 를 같이 기록.
import sys
 
seed = int(sys.argv[1]) if len(sys.argv) > 1 else 1337
set_random_seed(seed)
 
# NIST P-256 Parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
 
Zp = Zmod(p)
P256 = EllipticCurve(Zp, [a, b])
 
key1 = Zp.random_element()
key2 = Zp.random_element()
 
lines = []
for _ in range(10):
    P = P256.random_point()
    Q = P + P
 
    b = Zp.random_element()
    a = (P.xy()[0] - b) / key1
 
    d = Zp.random_element()
    c = (Q.xy()[0] - d) / key2
 
    lines.append(f"P.x = {a} * key1 + {b}")
    lines.append(f"Q.x = {c} * key2 + {d}")
 
open(f'oracle_output_{seed}.txt', 'w').write("\n".join(lines) + "\n")
key = int(key1) ^^ int(key2)
open(f'oracle_key_{seed}.txt', 'w').write(
    f"key1 = {int(key1):#066x}\nkey2 = {int(key2):#066x}\nFlag is DH{{{key:064x}}}\n")
print(f"[oracle] seed={seed} 새 인스턴스 생성 완료 -> oracle_output_{seed}.txt")

#!/usr/bin/env bash
# 문제 자체를 오라클로 쓴다. chal.sage 와 같은 절차로 "정답을 아는" 새 인스턴스를 만들고,
# solve.py 가 그 key1/key2 를 그대로 되찾는지 대조한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
SEED="${1:-1337}"
 
sage oracle.sage "$SEED"
 
echo
echo "== 오라클이 아는 정답 (seed $SEED) =="
cat "oracle_key_${SEED}.txt"
 
echo "== solve.py 가 복원한 값 =="
python3 solve.py "oracle_output_${SEED}.txt"
 
WANT=$(grep -o 'DH{[0-9a-f]*}' "oracle_key_${SEED}.txt")
GOT=$(python3 solve.py "oracle_output_${SEED}.txt" | grep -o 'DH{[0-9a-f]*}')
echo
if [ "$WANT" = "$GOT" ]; then
  echo "✅ 왕복 일치  $GOT"
else
  echo "❌ 불일치  기대 $WANT / 실제 $GOT"; exit 1
fi

./oracle_roundtrip.sh 1337

#!/usr/bin/env bash
# Elliptic Curve Basic (DreamHack, Gold 2) — 한 방 재현.
# 배포본만 있으면 파이썬 표준 라이브러리로 flag 까지 나온다. sage 는 교차검증용(있으면 같이 돈다).
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 extracted/output.txt 2>&1) || true
echo "$OUT"
 
if command -v sage >/dev/null 2>&1; then
  echo
  echo "-- sage 교차검증 (그뢰브너 소거 + 실제 곡선에서 2P 확인) --"
  timeout 900 sage verify_sage.sage extracted/output.txt 2>&1 | tail -6
fi
 
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
echo
if [ -n "$FLAG" ] && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo "✅ PASS  $FLAG"; exit 0
fi
echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh