노트북 00b — 고전 암호 복습

노트북 00b — 고전 암호 복습#

이 책이 대체하고자 하는 primitive들을 10분 동안 되짚어 봅니다. “RSA”라는 말은 들어봤지만 써 본 적은 없는 독자가 이 노트북을 마칠 때쯤에는 KEM이 무엇이며 어떤 역할을 하는지 알게 되어야 합니다.

암호의 세 가지 유형#

유형

역할

예시

Symmetric encryption

같은 키로 암호화/복호화합니다. 빠르지만 공유된 비밀이 필요합니다.

AES, ChaCha20

Asymmetric (public-key)

공개키 ≠ 개인키. 누구나 당신에게 비밀을 보낼 수 있지만, 읽을 수 있는 사람은 당신뿐입니다.

RSA, ECDH, ML-KEM

Hash / MAC / Signature

무결성과 인증 — “이것은 X로부터 왔고, 변조되지 않았다”.

SHA-256, HMAC, ECDSA, ML-DSA

핸드셰이크 문제#

대칭 암호는 빠르지만 공유 키가 필요합니다. 인터넷에서 처음 만나는 두 사람이 먼저 만나지 않고 어떻게 비밀 키에 합의할 수 있을까요? 이것이 바로 비대칭 암호가 푸는 문제입니다.

KEM — Key Encapsulation Mechanism#

KEM은 세 가지 연산으로 이루어진 특정한 비대칭 패턴입니다:

  • (ek, dk) = KeyGen() — encapsulation key(공개)와 decapsulation key(개인)를 생성합니다.

  • (K, ct) = Encaps(ek) — 누군가의 공개키를 사용해 공유 비밀 K와 암호문 ct를 생성합니다.

  • K = Decaps(dk, ct) — 개인키 보유자가 동일한 K를 복구합니다.

이제 양쪽 모두 같은 32바이트 비밀을 가지게 됩니다. 이를 대칭 암호(AES-GCM)에 넣어 실제 데이터를 전송합니다.

import os, hashlib

def toy_keygen():
    dk = os.urandom(32)                # "private"
    ek = hashlib.sha256(dk).digest()   # "public" — in a real KEM, ek can't reveal dk
    return ek, dk

def toy_encaps(ek):
    m = os.urandom(32)                 # random message
    ct = hashlib.sha256(ek + m).digest()
    K  = hashlib.sha256(b"secret" + m).digest()
    return K, ct

# ToyDecaps cannot actually work here (because ek is derived from dk via a one-way hash,
# so decaps has no way to recover m from ct). The point is the *shape* of the API:
ek, dk = toy_keygen()
K1, ct = toy_encaps(ek)
print("ek size:", len(ek), "ct size:", len(ct), "K size:", len(K1))
print("Both sides would now hold the same K — our toy can't decapsulate, but ML-KEM can.")

ek size: 32 ct size: 32 K size: 32
Both sides would now hold the same K — our toy can't decapsulate, but ML-KEM can.

KEM vs Public-Key Encryption vs Signature#

  • KEM: 랜덤 키에 합의합니다. 이 키는 이후 대칭 암호화에 사용됩니다. ML-KEM은 KEM입니다.

  • Public-Key Encryption (PKE): 공개키로 메시지를 직접 암호화합니다. ML-KEM은 내부에 PKE(K-PKE라 불림)를 포함하지만, 사용자 대상 API는 KEM입니다.

  • Signature: “나는 이 메시지에 서명했다”를 증명합니다. 비밀 유지가 아니라 인증이 목적입니다. ML-DSA는 signature입니다.

실제 TLS 1.3 핸드셰이크가 KEM을 사용하는 방식#

단순화하면, 브라우저가 서버에 연결할 때:

  1. 서버가 공개키 ek을 보냅니다.

  2. 브라우저가 Encaps(ek)을 호출 → (K, ct)을 얻습니다. ct를 보냅니다.

  3. 서버가 Decaps(dk, ct)을 호출 → 같은 K를 얻습니다.

  4. 양쪽 모두 K로부터 AES 키를 유도합니다. 이후 모든 트래픽은 AES-GCM입니다.

오늘날 ek은 ECDH (X25519) 공개키입니다. hybrid 배포(2023년 이후 Chrome) 에서는 X25519와 ML-KEM을 이어붙여 사용합니다 — 둘 중 하나라도 암호분석을 견디면 안전합니다. 노트북 08에서 hybrid 구현을 따라가 봅니다.

Shor가 깨뜨리는 것#

  • RSA는 다음에 의존합니다: 큰 정수의 인수분해가 어렵다. Shor는 이를 다항 시간에 수행 → RSA 깨짐.

  • ECDH/ECDSA는 다음에 의존합니다: elliptic-curve discrete logarithm이 어렵다. Shor는 discrete log를 다항 시간에 품 → ECC 깨짐.

  • 둘 다 악용 가능한 구조를 가진 대수적 문제입니다.

  • Lattice 문제 (LWE, SIS) 에는 알려진 다항 시간 양자 알고리즘이 없습니다 — 이것이 post-quantum의 베팅입니다.

수학 기초로 넘어갈 준비가 되었나요? → 00c_math_toolbox. 이미 mod-q 산술과 벡터에 익숙하다면 01_lattice_intro로 건너뛰세요.