개념 소개
현재 인터넷 보안의 근간을 이루는 RSA와 타원곡선 암호(ECC)는 수학적 난제에 의존한다. RSA는 큰 합성수의 소인수분해가 어렵다는 점을, ECC는 이산로그 문제가 어렵다는 점을 보안 근거로 삼는다. 고전 컴퓨터로는 RSA-2048을 푸는 데 천문학적 시간이 걸리지만, 충분히 큰 오류 정정 양자컴퓨터가 등장하면 Shor 알고리즘을 통해 다항식 시간 안에 해독될 수 있다.
포스트양자암호(Post-Quantum Cryptography, PQC) 는 이 위협에 대응하기 위해 양자컴퓨터로도 풀기 어려운 수학 문제를 기반으로 설계한 암호 체계다. 양자 채널이나 양자 하드웨어 없이 고전 서버에서 실행된다는 점에서, 물리 원리에 기반하는 양자키분배(QKD)와는 근본적으로 다른 접근이다.
핵심 원리
기존 암호의 취약점
Shor 알고리즘은 양자 푸리에 변환을 이용해 소인수분해와 이산로그 문제를 효율적으로 해결한다. Grover 알고리즘은 전수조사를 으로 단축해 대칭키 암호의 유효 보안 강도를 절반으로 낮춘다.
| 암호 | 기반 난제 | 양자 위협 |
|---|---|---|
| RSA | 소인수분해 | Shor (완전 파괴) |
| ECC | 이산로그 | Shor (완전 파괴) |
| AES-128 | — (대칭키) | Grover (64비트 수준으로 약화) |
| AES-256 | — (대칭키) | Grover (128비트 수준 유지) |
PQC의 수학적 기반
1. 격자 기반 암호 (Lattice-based)
가장 광범위하게 채택된 방식으로, LWE(Learning With Errors) 문제가 핵심이다.
는 공개 행렬, 는 비밀 벡터, 는 소규모 오차 벡터다. 와 를 알더라도 를 복원하는 것이 양자컴퓨터로도 어렵다고 알려져 있다. 이를 모듈 격자로 확장한 ML-KEM(CRYSTALS-Kyber) 은 키 캡슐화(KEM)에, ML-DSA(CRYSTALS-Dilithium) 은 디지털 서명에 사용된다.
2. 해시 기반 서명 (Hash-based)
암호학적 해시 함수의 단방향성만을 안전성 근거로 삼는다. SLH-DSA(SPHINCS+) 가 대표적이며, 수십 년 이상 연구된 가장 검증된 가정에 의존한다.
3. 코드 기반 암호 (Code-based)
오류 정정 부호의 신드롬 디코딩 문제를 기반으로 한다. Classic McEliece가 대표적이며 공개키 크기가 크다는 단점이 있다.
예시·응용
LWE 개념 시뮬레이션 (Python)
아래는 LWE 구조를 개념적으로 재현한 예시다(실제 암호 구현이 아님).
import numpy as np
n, q = 4, 97 # 격자 차원, 모듈러스
# 공개 행렬과 비밀 벡터
A = np.random.randint(0, q, (n, n))
s = np.array([3, 1, 4, 1]) # 비밀키 (수신자만 보유)
# 소규모 오차 (노이즈) 추가
e = np.array([1, 0, -1, 1])
# LWE 샘플: 공개 벡터 b = As + e (mod q)
b = (A @ s + e) % q
print("공개 벡터 b:", b)
# 공격자는 A, b를 알아도 s를 쉽게 복원할 수 없다
# 오차 벡터 e가 핵심 — 없으면 단순 선형계로 풀림
오차 벡터 가 없다면 는 선형 연립방정식이 되어 쉽게 풀린다. 노이즈가 추가됨으로써 양자 알고리즘도 통하지 않는 어려운 문제로 바뀐다.
표준화 현황과 하이브리드 전환
NIST는 FIPS 203(ML-KEM), FIPS 204(ML-DSA), FIPS 205(SLH-DSA)를 공표하며 PQC 표준화를 완료했다. 실무에서는 기존 ECC와 ML-KEM을 병행하는 하이브리드 방식이 TLS·PKI 인프라 전환 초기에 권장된다. 두 알고리즘 중 하나라도 안전하면 전체 시스템이 안전하므로, 전환 기간 중 위험을 최소화할 수 있다.
정리
PQC는 Shor·Grover 알고리즘의 위협에 맞서 양자컴퓨터로도 풀기 어려운 수학 문제를 기반으로 설계된 암호 체계다. 격자(LWE), 해시, 코드 기반 세 계열이 주요 후보이며, 격자 기반 알고리즘이 성능과 키 크기 균형 면에서 가장 폭넓게 채택되고 있다. QKD가 물리 법칙으로 안전성을 보장한다면, PQC는 수학적 어려움으로 안전성을 보장하며 두 접근은 상호 보완적으로 활용될 수 있다.
Exercises
연습문제
Q1Grover 알고리즘이 AES-128에 미치는 영향을 설명하고, 이를 보완하기 위한 실용적 대응 방법을 제시하라.
힌트 보기
Grover 알고리즘은 전수조사 복잡도를 $O(N)$에서 $O(\sqrt{N})$으로 단축한다. 128비트 키 공간 $N = 2^{128}$에 적용하면 어떻게 되는가?
해설 보기
Grover 알고리즘 적용 시 AES-128의 유효 보안 강도는 $\sqrt{2^{128}} = 2^{64}$ 수준으로 낮아져 현대 보안 기준에 미치지 못한다. AES-256을 사용하면 양자 공격 후에도 $2^{128}$ 수준의 보안 강도가 유지되므로, 대칭키 암호에 대한 대응은 키 길이를 두 배로 늘리는 것으로 충분하다.
Q2LWE 문제에서 오차 벡터 $\mathbf{e}$를 제거하면(즉, $\mathbf{b} = \mathbf{A}\mathbf{s} \pmod{q}$) 보안성이 어떻게 달라지는가?
해설 보기
오차 벡터가 없으면 $\mathbf{b} = \mathbf{A}\mathbf{s}$는 단순 선형 연립방정식이 되어, 가우스 소거법 등 고전 알고리즘으로 $O(n^3)$ 시간에 $\mathbf{s}$를 복원할 수 있다. 소규모 오차 $\mathbf{e}$의 추가가 문제를 양자컴퓨터도 효율적으로 풀 수 없는 어려운 문제로 만드는 핵심 장치다.
Q3PQC와 QKD를 보안 근거, 실행 환경, 확장성 측면에서 비교하라.
해설 보기
PQC는 수학적 난제(격자, 해시 등)를 안전성 근거로 삼으며 고전 하드웨어에서 실행되어 기존 인터넷 인프라에 바로 적용 가능하다. QKD는 양자역학의 물리 법칙(측정 불교란성, 복제 불가 정리)을 근거로 하며 전용 양자 채널과 장치가 필요해 대규모 확장이 어렵다. 두 방법은 상호 배타적이지 않으며, 물리적 보안 채널(QKD)로 키를 분배하고 PQC 알고리즘으로 데이터를 암호화하는 방식으로 함께 활용될 수 있다.
관련 용어
