노트북 10 — KEM은 절반의 이야기: signature와 동료들

내용

노트북 10 — KEM은 절반의 이야기: signature와 동료들#

지금까지 우리는 FIPS 2024 세 가지 표준 중 하나 인 ML-KEM (KEM) 을 구현했습니다. 이 노트북에서는 나머지 둘 — ML-DSA와 SLH-DSA — 을 개괄하고, 각각이 더 넓은 post-quantum 지형 어디에 자리하는지 살펴봅니다.

목표는 방향 잡기이지 구현이 아닙니다: lattice KEM을 내부에서 구축해 봤다면, 대부분의 아이디어는 자연스럽게 일반화됩니다.

왜 두 가지일까? KEM vs signature#

기능	KEM (ML-KEM)	Signature (ML-DSA / SLH-DSA)
목표	두 당사자 사이에 공유 비밀 합의	이 메시지가 특정 서명자로부터 변조 없이 왔음을 증명
키 쌍	`(ek, dk)` — encapsulation / decapsulation	`(vk, sk)` — verification / signing
핵심 연산	`Decaps(dk, ct) -> K`	`Verify(vk, msg, sig) -> ok?`
TLS에서의 용도	키 교환 (X25519 대체)	인증서 서명 (RSA/ECDSA 대체)

실제 TLS 1.3 핸드셰이크는 두 가지를 모두 사용합니다: 키에 합의하기 위한 KEM과, 서버의 인증서를 인증하기 위해 핸드셰이크 transcript에 대한 signature. Q-Day 이후에는 양쪽 모두 양자 안전이어야 합니다 — 그래서 FIPS 203 (KEM) 과 FIPS 204/205 (signature) 가 함께 필요합니다.

FIPS 2024 세 표준 한눈에 보기#

표준	이름	계열	역할	안전성 근거
FIPS 203	ML-KEM (Kyber)	Module-LWE (lattice)	Key encapsulation	MLWE 난해성
FIPS 204	ML-DSA (Dilithium)	Module-LWE + Module-SIS (lattice)	Signature	MLWE + MSIS
FIPS 205	SLH-DSA (SPHINCS+)	Hash 기반	Signature	Hash 충돌 저항성만

ML-DSA (Dilithium) — 같은 수학, 다른 모양#

ML-DSA와 ML-KEM은 같은 산술을 공유합니다: R_q = Z_q[x]/(x^n+1), n=256, q=8380417 (ML-KEM의 3329와는 다른 q), Module-LWE + Module-SIS, NTT 친화적.

Signing은 Fiat-Shamir with aborts를 사용합니다:

랜덤 nonce y를 생성하고 w = A·y를 계산합니다.
Challenge c = H(message || w) — hash로부터 유도한 작은 polynomial.
Response z = y + c·s, 여기서 s는 비밀입니다.
만약 z가 s에 대해 너무 많이 드러내면 중단하고 재시도합니다. 그렇지 않으면 (z, c) 를 출력합니다.

검증은 s를 보지 않고도 A·z - c·t = A·y 관계를 확인합니다. “aborts” 때문에 Dilithium의 signing은 상수 시간이 아니지만, 출력은 안전합니다.

크기 비교 (Level 3 / 128-bit PQ 안전성):

ML-DSA: vk ≈ 2 KB, sig ≈ 3.3 KB
ECDSA P-256 (참고용): vk 32 B, sig 64 B — ML-DSA가 약 50배 큽니다.

SLH-DSA (SPHINCS+) — “따분한” 백업 플랜#

Hash 기반 signature는 오직 hash function의 안전성에만 의존합니다 (number theory 없음, lattice 가정 없음). 다른 모든 PQC 방식 — lattice, code, multivariate, isogeny — 이 무너지더라도 SHA-2/SHA-3 가 충돌 저항성을 유지하는 한 SPHINCS+는 여전히 서 있습니다.

직관적인 동작 방식:

많은 one-time signature (OTS) 로 이루어진 Merkle tree.
각 메시지는 새로운 OTS leaf로 서명됩니다; Merkle tree를 따라 올라가는 경로가 그 leaf가 공개 루트에 속함을 증명합니다.
Stateless 버전 (SPHINCS+, NIST가 표준화한 것): 어떤 leaf가 사용되었는지 추적할 필요를 없애기 위해 hyper-tree (tree들의 tree) 를 사용합니다.

Trade-off:

Signature 크기: 약 8–50 KB (못생김).
검증은 빠릅니다 (수백 번의 hash 평가).
Signing은 ML-DSA보다 느립니다.
그러나 안전성 논거는 지금까지 표준화된 어떤 signature 방식보다도 강력합니다.

import hashlib
import matplotlib.pyplot as plt

def H(a, b=b""):
    return hashlib.sha256(a + b).digest()

# 8 leaves, each a "one-time signature public key"
leaves = [H(str(i).encode()) for i in range(8)]

# Build the Merkle tree bottom-up
level = leaves
tree = [level]
while len(level) > 1:
    level = [H(level[i], level[i+1]) for i in range(0, len(level), 2)]
    tree.append(level)
root = tree[-1][0]

# Plot
fig, ax = plt.subplots(figsize=(10, 4))
n_levels = len(tree)
for lvl, nodes in enumerate(tree):
    y = n_levels - 1 - lvl
    for i, node in enumerate(nodes):
        x = (i + 0.5) * (8 / len(nodes))
        ax.scatter(x, y, s=300, c="steelblue", zorder=3)
        ax.text(x, y - 0.25, node[:4].hex(), ha="center", fontsize=8, family="monospace")
        if lvl > 0:
            for child in (2*i, 2*i+1):
                cx = (child + 0.5) * (8 / (2 * len(nodes)))
                cy = n_levels - lvl
                ax.plot([x, cx], [y, cy], "gray", lw=0.8, zorder=1)
ax.text(4, n_levels, "public root = " + root[:4].hex() + "...", ha="center", fontsize=10, weight="bold")
ax.set_xlim(-0.5, 8.5)
ax.set_ylim(-0.5, n_levels + 0.5)
ax.axis("off")
plt.title("Toy Merkle tree: SPHINCS+ binds one-time signature leaves under a single root")
plt.tight_layout()
plt.show()

../_images/36fe487363628b259abbc51d7d91f5a49a76b3b4f5daa6c0c98eb7b4c06a8ecd.png

Trade-off 치트시트#

Lattice (ML-DSA) 와 hash 기반 (SLH-DSA) signature 중 고르기:

새 설계의 기본 선택: ML-DSA. 더 작고, 더 빠르며, 잘 이해되어 있습니다.
Lattice 암호분석에 편집증적일 때: SLH-DSA. 크기는 감수합니다.
Signature 빈도는 낮지만 수명이 긴 경우 (예: 루트 CA에 대한 코드 서명): SLH-DSA의 강한 안전성 논거가 바이트 비용을 상쇄합니다.
Hybrid signature (ECDSA + ML-DSA, 또는 ECDSA + SLH-DSA) 는 심층 방어를 제공합니다 — hybrid KEM (노트북 08) 과 같은 패턴입니다.

FIPS 2024에는 없지만 알아둘 가치가 있는 계열#

Code-based KEM (Classic McEliece, BIKE, HQC): coding theory 기반. McEliece는 1978년에 등장해 지금까지 깨지지 않았지만, 공개키가 약 1 MB에 달합니다. NIST의 “alternate track” 우승자는 HQC와 BIKE 변형입니다 (2026–2027 경 표준화 예상).
Isogeny 기반 (SIKE): 2022년 고전 공격으로 완전히 깨졌습니다 — 이 수학의 일부가 얼마나 최근 것인지를 보여주는 경고 사례입니다.
Multivariate (Rainbow): 역시 2022년에 깨졌습니다.
FN-DSA (Falcon): Dilithium보다 빠르고 signature가 더 작은 lattice signature이지만, 상수 시간으로 구현하기가 더 까다롭습니다. NIST는 FIPS 206 (2025년 말 / 2026) 으로 표준화할 계획입니다.

직접 해보기: ML-DSA 한 줄로 (선택)#

Dilithium이 end-to-end로 동작하는 것을 — 처음부터 구현은 아니고, API만이라도 — 보고 싶다면 구현체를 설치하세요:

pip install pyspx-plus liboqs-python   # requires liboqs shared library

이 책은 의도적으로 ML-DSA를 처음부터 구축하지 않습니다; 그러면 책의 길이가 대략 두 배가 됩니다. 여기서의 목표는 여러분이 하나의 lattice 기반 PQC 방식 (ML-KEM) 을 내부에서부터 편안하게 이해하도록 만드는 것이었습니다 — 같은 수학이 ML-DSA에도 적용됩니다.

→ 다음: 실제 상황과 빠른 참조를 위해 11_deployment_and_faq_glossary 로.