포스트양자암호(PQC): 양자컴퓨터 시대의 암호 설계
포스트양자암호(PQC)는 양자컴퓨터의 공격에도 안전한 암호 체계를 설계하는 분야다. 기존 RSA·ECC 암호가 쇼어 알고리즘에 의해 무력화될 수 있음을 출발점으로, 격자·해시·부호 기반 등 새로운 수학적 난제를 활용한 암호 설계 원리를 다룬다. NIST의 표준화 과정과 주요 알고리즘 계열을 함께 살펴본다.
개념 소개
현대 인터넷 보안의 근간인 RSA 암호는 "큰 수의 소인수분해가 어렵다"는 수학적 사실에 의존한다. 1024비트 정수를 소인수분해하는 데 고전 컴퓨터로는 수십억 년이 걸리지만, 양자컴퓨터에서 쇼어(Shor) 알고리즘을 실행하면 동일한 문제를 다항 시간 안에 풀 수 있다.
타원곡선 암호(ECC)도 마찬가지다. 이산로그 문제 역시 쇼어 알고리즘에 취약하다. 즉, 충분한 규모의 양자컴퓨터가 등장하면 현재 통용되는 공개키 암호 인프라 전체가 위협받는다.
포스트양자암호(Post-Quantum Cryptography, PQC) 는 이러한 위협에 대응하기 위해, 양자컴퓨터로도 효율적으로 풀 수 없는 수학적 난제에 기반한 암호 알고리즘을 연구·설계하는 분야다. 양자키분배(QKD)가 물리적 채널을 이용한 접근이라면, PQC는 순수하게 수학적 구조를 이용한 소프트웨어적 접근이다.
핵심 원리
양자 안전성의 기준
PQC 알고리즘은 다음 두 조건을 충족해야 한다.
- 고전 컴퓨터로도 풀기 어려울 것 (기존 보안 요건 유지)
- 양자컴퓨터로도 지수적 속도 향상을 얻기 어려울 것
그로버(Grover) 알고리즘은 비대칭키가 아닌 대칭키·해시 함수에 속도 향상을 준다. 이는 키 길이를 두 배로 늘리는 것으로 대응 가능하다. 예를 들어 AES-128 → AES-256으로 전환하면 그로버 공격에 대해 128비트 보안 수준을 유지한다.
공개키 암호에 대한 쇼어 공격은 지수적 위협이므로 단순한 키 길이 확장으로는 대응이 불가능하며, 근본적으로 다른 수학적 기반이 필요하다.
주요 수학적 기반
1. 격자(Lattice) 기반 암호
현재 가장 유망한 접근법이다. 핵심 난제는 최단벡터문제(SVP) 와 학습 오류 문제(LWE) 다.
LWE 문제를 간략히 표현하면, 비밀 벡터 에 대해 다음과 같은 쌍 이 주어졌을 때 를 복원하는 것이다.
여기서 는 작은 오류 벡터다. 오류 없이는 단순한 선형방정식이지만, 오류가 추가되면 고전·양자 컴퓨터 모두에서 효율적인 풀이법이 알려져 있지 않다.
NIST 표준으로 선정된 ML-KEM(Kyber) 과 ML-DSA(Dilithium) 이 대표적인 격자 기반 알고리즘이다.
2. 해시(Hash) 기반 서명
해시 함수의 단방향성(일방향성)만을 가정하므로, 수학적 가정이 가장 단순하고 보수적이다. XMSS, LMS, SLH-DSA(SPHINCS+) 가 대표적이다. 서명 크기가 크다는 단점이 있지만 보안 근거가 강하다.
3. 부호(Code) 기반 암호
오류 정정 부호에서 유도된 맥엘리스(McEliece) 암호가 1978년부터 연구되어 왔다. 무작위 선형 부호에서 오류 패턴을 복원하는 난제를 활용한다. 공개키 크기가 매우 크다는 점이 실용화의 걸림돌이다.
4. 다변수 다항식(Multivariate) 기반
위의 연립 이차방정식을 푸는 문제(MQ 문제)의 어려움을 이용한다. NIST 표준 후보로는 UOV 계열 등이 있다.
NIST 표준화 현황
NIST는 2016년부터 PQC 표준화 공모를 진행해, 수 라운드의 분석을 거쳐 2024년 기준 다음 알고리즘을 표준으로 확정했다.
| 표준명 | 유형 | 기반 수학 |
|---|---|---|
| ML-KEM (FIPS 203) | 키 캡슐화 | 격자 (Module-LWE) |
| ML-DSA (FIPS 204) | 전자서명 | 격자 (Module-LWE) |
| SLH-DSA (FIPS 205) | 전자서명 | 해시 |
| FN-DSA (FIPS 206) | 전자서명 | 격자 (NTRU) |
예시·응용
Python 예시: ML-KEM 개념적 흐름
아래는 키 캡슐화 메커니즘(KEM)의 논리적 흐름을 보여주는 의사 코드다. 실제 라이브러리는 liboqs(Open Quantum Safe 프로젝트)를 사용한다.
# pip install pyoqs (liboqs Python 바인딩)
import oqs
# 1. 키쌍 생성 (수신자)
with oqs.KeyEncapsulation("ML-KEM-768") as kem:
public_key = kem.generate_keypair()
# 2. 키 캡슐화 (송신자: 공개키로 공유 비밀 생성)
with oqs.KeyEncapsulation("ML-KEM-768") as kem_sender:
ciphertext, shared_secret_sender = kem_sender.encap_secret(public_key)
# 3. 키 역캡슐화 (수신자: 비밀키로 공유 비밀 복원)
shared_secret_receiver = kem.decap_secret(ciphertext)
assert shared_secret_sender == shared_secret_receiver
print("공유 비밀 일치:", shared_secret_sender.hex()[:32], "...")
이 과정에서 공유 비밀은 이후 AES 등 대칭키 암호의 세션 키로 활용된다. TLS 1.3 핸드셰이크에 ML-KEM을 통합하는 하이브리드 방식이 현재 업계 전환 전략의 표준으로 부상하고 있다.
하이브리드 암호화 전략
당장 PQC로 완전 전환하기 어려운 환경에서는, 기존 ECDH와 ML-KEM을 병렬로 실행하여 두 공유 비밀을 결합하는 하이브리드 KEM 방식을 쓴다. 둘 중 하나만 안전해도 전체 세션 키가 노출되지 않는다.
"지금 수집해 나중에 해독(Harvest Now, Decrypt Later)" 공격에 대비하기 위해, 장기 기밀 데이터를 다루는 정부·금융 분야에서는 이미 하이브리드 전환을 권고하고 있다.
정리
PQC는 양자컴퓨터의 쇼어 알고리즘이 기존 공개키 암호에 가하는 위협을 수학적으로 우회하는 접근이다. 격자, 해시, 부호, 다변수 다항식 등 다양한 난제 기반 알고리즘이 제안되었으며, NIST의 표준화를 통해 실용화 단계에 진입했다. 현실적인 전환 전략으로는 기존 암호와 PQC를 함께 사용하는 하이브리드 방식이 권장된다.
연습문제
Q1.AES-128을 사용하는 대칭키 시스템이 그로버 알고리즘의 공격을 받을 때, 동등한 보안 수준을 유지하려면 키 길이를 얼마로 늘려야 하는가? 이유를 설명하라.
힌트 보기
그로버 알고리즘은 키 탐색 복잡도를 $O(2^n)$에서 $O(2^{n/2})$로 줄인다.
해설 보기
AES-128의 고전적 보안 강도는 $2^{128}$이다. 그로버 알고리즘 적용 시 유효 강도는 $2^{128/2} = 2^{64}$로 감소한다. 128비트 양자 보안 수준을 유지하려면 키 길이를 256비트로 두 배 늘려야 한다. 즉 AES-256으로 전환하면 그로버 공격 후에도 $2^{128}$ 보안 수준이 유지된다.
Q2.LWE 기반 암호에서 오류 벡터 $\mathbf{e}$를 제거하면(즉, $\mathbf{b} = \mathbf{A}\mathbf{s} \pmod{q}$) 어떤 문제가 발생하는가?
해설 보기
오류 벡터가 없으면 $\mathbf{b} = \mathbf{A}\mathbf{s} \pmod{q}$는 단순한 연립 선형방정식이 된다. 가우스 소거법 등 다항 시간 알고리즘으로 $\mathbf{s}$를 쉽게 복원할 수 있어 암호로서 의미를 잃는다. 오류 벡터 $\mathbf{e}$의 존재가 정확한 역산을 막는 핵심 장치다.
Q3."Harvest Now, Decrypt Later" 공격이란 무엇이며, 어떤 종류의 데이터가 특히 위험한가?
해설 보기
현재 양자컴퓨터가 없더라도, 공격자가 암호화된 통신을 지금 대량 수집해 두었다가 미래에 충분한 양자컴퓨터가 등장했을 때 해독하는 전략이다. 따라서 기밀 유효 기간이 긴 데이터(국가 기밀, 의료 기록, 장기 금융 계약 등)는 당장 PQC로 전환하지 않으면 미래에 소급 노출될 위험이 있다.