개념 소개
현대 공개키 암호는 두 가지 수학적 난제에 기반한다. RSA는 큰 정수의 소인수분해 어려움을, 타원곡선 디피-헬만(ECDH)은 이산로그 문제의 어려움을 이용한다. 고전 컴퓨터로 이를 푸는 데는 지수 시간이 걸리지만, 양자컴퓨터에서 쇼어(Shor) 알고리즘을 적용하면 다항 시간 내에 풀 수 있다.
이는 단순한 미래의 위협이 아니다. "지금 수집해 나중에 해독(Harvest Now, Decrypt Later)" 공격이 이미 실용적 위협으로 논의된다. 장기 기밀을 담은 암호문을 지금 수집해두고, 충분한 규모의 양자컴퓨터가 등장하면 해독하는 전략이다. 따라서 양자컴퓨터가 실용화되기 전에 암호 인프라를 전환해야 한다.
포스트양자암호(Post-Quantum Cryptography, PQC) 는 양자컴퓨터에서도 효율적인 알고리즘이 알려지지 않은 수학 문제를 기반으로 설계된 암호 체계다. 이름에 '양자'가 들어가지만, PQC 알고리즘 자체는 고전 하드웨어에서 동작한다는 점이 QKD(양자키분배)와의 근본적인 차이다.
핵심 원리
PQC의 주요 수학적 접근은 다음 네 가지로 분류된다.
1. 격자 기반 암호 (Lattice-based)
현재 가장 유력한 PQC 후보군이다. 핵심 난제는 LWE(Learning With Errors) 문제다.
여기서 은 공개 행렬, 은 비밀 벡터, 는 작은 오차 벡터다. 공개 정보 만으로 를 복원하는 것이 계산적으로 어렵다는 가정이 안전성의 근거다. 격자 차원 이 충분히 크면 양자 알고리즘으로도 효율적 풀이가 알려져 있지 않다.
모듈 격자(Module Lattice)로 확장한 MLWE는 키 크기와 연산 효율을 개선하여 실용적인 구현을 가능하게 한다.
2. 해시 기반 암호 (Hash-based)
암호학적 해시 함수의 일방향성만을 안전성 가정으로 삼는다. 구조가 단순하고 보수적이며, 전자서명에 주로 사용된다. 상태 비저장형(stateless) 방식의 SPHINCS+ 가 대표적이다.
3. 코드 기반 암호 (Code-based)
오류 정정 부호의 디코딩 문제를 기반으로 한다. 임의 선형 코드의 복호화가 NP-난해임이 알려져 역사가 길다(McEliece 암호, 1978). 다만 키 크기가 크다는 단점이 있다.
4. 다변수 다항식 기반 (Multivariate)
유한체 위에서의 연립 다변수 이차방정식 풀이(MQ 문제)를 활용한다. 현재 전자서명 분야에서 일부 후보가 연구되고 있다.
예시·응용
NIST PQC 표준화
미국 국립표준기술연구소(NIST)는 2024년 다음 알고리즘을 공식 표준(FIPS)으로 확정했다.
| 표준 | 알고리즘 | 기반 | 용도 |
|---|---|---|---|
| FIPS 203 | ML-KEM (Kyber) | MLWE | 키 캡슐화(KEM) |
| FIPS 204 | ML-DSA (Dilithium) | MLWE | 디지털 서명 |
| FIPS 205 | SLH-DSA (SPHINCS+) | 해시 | 디지털 서명 |
| FIPS 206 | FN-DSA (Falcon) | NTRU 격자 | 디지털 서명 |
LWE 구조 개념 시연 (Python)
import numpy as np
# LWE 문제 개념 시연 (교육용 단순화)
q = 97 # 모듈러스
n = 4 # 격자 차원
# 비밀 벡터 s (수신자만 보유)
s = np.array([3, 1, 4, 1])
np.random.seed(42)
A = np.random.randint(0, q, size=(8, n)) # 공개 행렬
e = np.random.randint(-2, 3, size=8) # 소규모 오차
# 공개 벡터: b = A·s + e (mod q)
b = (A @ s + e) % q
# 공격자는 (A, b)만으로 s를 복원해야 하지만
# 오차 e 때문에 단순 선형대수로는 불가능
print(f"공개 행렬 A:\n{A}")
print(f"공개 벡터 b: {b}")
print("s를 모르는 상태에서 b = A·s + e를 분리하는 것은 어렵습니다.")
QKD와의 비교
QKD는 정보이론적 안전성을 제공하지만 전용 양자 채널이 필요하다. PQC는 기존 인터넷 인프라에서 동작하며 계산적 안전성에 의존한다. 실용 측면에서 PQC가 단기 전환에 유리하며, 두 기술은 상호 보완적으로 사용될 수 있다.
정리
PQC는 양자컴퓨터 위협에 대응하기 위해 격자·해시·코드 등 새로운 수학적 난제를 활용하는 고전 암호 체계다. NIST의 표준화 완료로 실제 시스템 전환이 시작되었으며, 특히 격자 기반 알고리즘(ML-KEM, ML-DSA)이 효율성과 안전성 면에서 주목받고 있다. 암호 전환(Crypto Agility)은 단순한 알고리즘 교체가 아니라 프로토콜·인프라 전반의 재설계를 요구한다.
Exercises
연습문제
Q1RSA-2048이 고전 컴퓨터에서는 안전하지만 양자컴퓨터에서 취약한 이유를 쇼어 알고리즘의 관점에서 설명하라.
힌트 보기
쇼어 알고리즘의 시간 복잡도와 고전 알고리즘(일반 수체 체, GNFS)의 시간 복잡도를 비교해보라.
해설 보기
고전 알고리즘으로 RSA-2048을 해독하려면 지수 시간 $O(\exp(n^{1/3}))$ 수준의 연산이 필요하여 현실적으로 불가능하다. 반면 쇼어 알고리즘은 양자 푸리에 변환을 이용해 정수의 주기를 다항 시간 $O((\log N)^3)$ 내에 찾고, 이를 통해 소인수분해를 수행한다. 따라서 충분한 오류 정정 큐비트를 갖춘 양자컴퓨터가 등장하면 RSA-2048은 안전성을 잃는다.
Q2LWE 문제에서 오차 벡터 $\mathbf{e}$가 없다고 가정하면($\mathbf{b} = A\mathbf{s} \pmod{q}$), 비밀 벡터 $\mathbf{s}$를 쉽게 복원할 수 있는가? 그 이유를 설명하라.
해설 보기
오차가 없으면 $A\mathbf{s} \equiv \mathbf{b} \pmod{q}$는 단순한 연립 선형방정식이 된다. 행렬 $A$가 충분한 수의 방정식을 가지고 역행렬이 존재하면, 가우스 소거법 등의 고전 알고리즘으로 다항 시간에 $\mathbf{s}$를 복원할 수 있다. 즉 오차 $\mathbf{e}$의 존재가 LWE 문제를 계산적으로 어렵게 만드는 핵심 요소다.
Q3PQC와 QKD의 안전성 가정을 비교하고, 각각이 적합한 응용 시나리오를 하나씩 제시하라.
해설 보기
QKD는 물리 법칙(양자역학의 측정 불교란 원리)에 기반한 정보이론적 안전성을 제공하므로 계산 능력과 무관하게 안전하다. 반면 PQC는 특정 수학 문제가 효율적으로 풀리지 않는다는 계산적 가정에 의존한다. QKD는 장기 기밀이 요구되는 정부·군사 통신처럼 전용 광섬유 인프라를 구축할 수 있는 환경에 적합하다. PQC는 인터넷 TLS 인증서 교체처럼 기존 네트워크 인프라를 유지하면서 빠르게 전환해야 하는 범용 시나리오에 적합하다.
관련 용어
