포스트양자암호(PQC) 기초: 양자 위협에 대비하는 암호 체계

개념 소개

현재 인터넷 보안의 근간을 이루는 RSA, 타원곡선암호(ECC), Diffie-Hellman 키 교환은 소인수분해나 이산로그 문제의 계산적 어려움에 의존한다. 고전 컴퓨터로는 수백 자리 수의 소인수분해에 우주 나이를 웃도는 시간이 걸리지만, **쇼어 알고리즘(Shor's algorithm)**이 동작하는 범용 양자 컴퓨터가 실현되면 이 문제들은 다항식 시간 내에 풀린다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 양자 컴퓨터로도 효율적으로 풀 수 없다고 알려진 수학 문제에 안전성을 두는 암호 알고리즘의 총칭이다. 중요한 점은 PQC가 양자 하드웨어가 아닌 고전 컴퓨터에서 실행된다는 것으로, 양자 채널을 필요로 하는 양자키분배(QKD)와 근본적으로 다른 접근이다.

'지금 수집, 나중 복호화(Harvest Now, Decrypt Later)' 공격도 PQC 전환을 서두르는 중요한 이유다. 공격자가 현재 암호화된 트래픽을 저장해 두었다가 대규모 양자 컴퓨터가 등장한 뒤 복호화하는 전략으로, 이 위협은 양자 컴퓨터 실현 이전에 PQC 전환이 완료되어야 함을 의미한다.

---

핵심 원리

쇼어 알고리즘의 위협

RSA 2048비트를 고전 컴퓨터로 공격하는 데 준지수(sub-exponential) 복잡도가 필요하지만, 쇼어 알고리즘은 $O((\log n{)}^3)$의 다항식 복잡도로 인수분해를 수행한다. ECC와 Diffie-Hellman의 이산로그 문제도 동일하게 쇼어 알고리즘에 취약하다.

한편 대칭키 암호(AES)와 해시 함수는 **그로버 알고리즘(Grover's algorithm)**의 공격을 받아 효과적 키 길이가 절반으로 줄어드는 데 그친다. 따라서 AES-256은 128비트 보안 수준을 유지하며, 대칭키 암호는 키 길이 확장만으로 대응이 가능하다.

격자 기반 암호와 LWE 문제

현재 PQC의 주류는 **격자 기반 암호(Lattice-based Cryptography)**다. 안전성의 핵심은 LWE(Learning With Errors) 문제다.

$$\mathbf{b}=A\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$$

• $A\in {\mathbb{Z}}_q^{m\times n}$: 공개 행렬
• $\mathbf{s}\in {\mathbb{Z}}_q^n$: 비밀 벡터
• $\mathbf{e}$: 작은 오류 벡터 (가우시안 분포)

$(A,\mathbf{b})$가 주어졌을 때 $\mathbf{s}$를 복원하는 것은 고전·양자 컴퓨터 모두에게 어렵다는 것이 현재의 수학적 합의다. LWE는 최악의 경우(worst-case) 격자 문제인 SVP(Shortest Vector Problem)로 환원되어 안전성 근거가 탄탄하다.

NIST 표준 알고리즘

미국 국립표준기술연구소(NIST)는 다년간의 공개 평가 과정을 통해 다음 표준을 확정하였다.

알고리즘	표준명	기반 문제	용도
CRYSTALS-Kyber	ML-KEM	모듈 격자 (LWE)	키 캡슐화
CRYSTALS-Dilithium	ML-DSA	모듈 격자	디지털 서명
FALCON	FN-DSA	NTRU 격자	디지털 서명
SPHINCS+	SLH-DSA	해시 함수	디지털 서명

ML-KEM과 ML-DSA는 모듈 격자 위에 정의되어 성능과 안전성의 균형이 뛰어나다. SPHINCS+는 해시 함수의 충돌 저항성만을 근거로 삼는 가장 보수적인 선택지로, 격자 암호에 아직 신뢰를 두기 어려운 경우 대안이 된다.

---

예시·응용

Python 개념 코드: LWE 구조 스케치

import numpy as np

# 간소화된 LWE 파라미터 (교육용)
n, m, q = 4, 8, 97
rng = np.random.default_rng(seed=42)

# 비밀 벡터 s (Alice의 개인키)
s = rng.integers(0, q, size=n)

# 공개 행렬 A
A = rng.integers(0, q, size=(m, n))

# 작은 오류 벡터 e
e = rng.integers(-2, 3, size=m)

# 공개키 b = A·s + e (mod q)
b = (A @ s + e) % q

print("비밀키 s :", s)
print("공개키 b :", b)
# b와 A를 공개해도 s를 복원하기 어렵다는 것이 LWE의 핵심

이 코드는 LWE의 구조를 이해하기 위한 교육용 스케치다. 실제 암호 구현에는 반드시 검증된 라이브러리(예: liboqs, pqcrypto)를 사용해야 한다.

하이브리드 키 교환

Google, Cloudflare 등은 TLS 1.3 핸드셰이크에 하이브리드 키 교환 방식을 실험적으로 적용하고 있다. ECDH와 ML-KEM을 병행하여 공유 비밀을 결합함으로써, 두 알고리즘 중 하나가 안전하면 전체 통신이 안전하도록 보장한다. 이는 PQC의 장기 안전성이 완전히 검증되기 전까지의 과도기 전략이다.

---

정리

PQC는 쇼어 알고리즘으로 인한 공개키 암호 붕괴에 대비하여 격자, 해시, 코드 등 양자-내성 수학 문제를 기반으로 설계된 암호 체계다. NIST가 선정한 ML-KEM, ML-DSA, FN-DSA, SLH-DSA는 현재 전 세계 인프라에 점진적으로 통합되고 있다. 'Harvest Now, Decrypt Later' 위협을 감안하면 PQC 전환은 대규모 양자 컴퓨터가 실현되기 이전에 완료되어야 한다.