포스트양자암호(PQC) 기초: 양자 위협에 대응하는 수학적 암호 설계

개념 소개

현재 인터넷 보안의 근간인 RSA와 타원곡선암호(ECC)는 각각 큰 수의 소인수분해와 이산로그 문제의 계산 난이도에 의존한다. 그런데 쇼어 알고리즘(Shor's algorithm)을 충분히 큰 양자컴퓨터에 적용하면 이 두 문제를 모두 다항 시간(polynomial time) 안에 풀 수 있다. 즉, 대규모 양자컴퓨터가 실용화되는 시점에 현행 공개키 암호 체계는 원칙적으로 붕괴된다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 양자컴퓨터에서도 지수 시간이 걸리는 수학 문제를 안전성 근거로 삼는 암호 알고리즘을 통칭한다. 양자 키 분배(QKD)가 양자역학 자체를 통신 채널로 활용하는 것과 달리, PQC는 순수하게 고전 컴퓨터에서 실행되는 소프트웨어·알고리즘이다. 기존 네트워크 인프라를 그대로 유지하면서 배포할 수 있어 실용적 이점이 크다.

---

핵심 원리

PQC는 크게 네 가지 수학적 난제 군으로 분류된다.

격자 기반 암호 (Lattice-based Cryptography)

현재 가장 활발히 표준화된 분야다. 핵심은 LWE(Learning With Errors) 문제로, 노이즈가 섞인 선형 방정식 계에서 비밀 벡터를 복원하는 것이다.

$$\mathbf{b}\equiv \mathbf{As}+\mathbf{e}(\mathrm{mod}q)$$

여기서 $\mathbf{A}$는 공개 행렬, $\mathbf{s}$는 비밀 벡터, $\mathbf{e}$는 소량의 오차 벡터다. $\mathbf{A}$와 $\mathbf{b}$만으로 $\mathbf{s}$를 복원하는 것은 양자컴퓨터에서도 지수 시간이 걸린다고 알려져 있다. NIST가 확정한 ML-KEM(구 CRYSTALS-Kyber, FIPS 203)과 ML-DSA(구 CRYSTALS-Dilithium, FIPS 204)가 이 계열에 속한다.

해시 기반 서명 (Hash-based Signature)

일방향 해시 함수의 충돌 저항성에만 의존하는 서명 방식이다. 가정이 최소화된 만큼 양자 공격에 대한 안전성 분석이 가장 명확하다. NIST 표준 SLH-DSA(구 SPHINCS+, FIPS 205)가 대표적이다. 서명 크기가 상대적으로 크지만, 보수적 안전 요구 환경에 적합하다.

부호 기반 암호 (Code-based Cryptography)

오류 정정 부호(error-correcting code)에서, 랜덤 선형 부호의 신드롬 디코딩 문제(Syndrome Decoding Problem)의 NP-난이도를 안전성 근거로 삼는다. McEliece 암호가 원형으로, 1978년 제안 이후 수십 년간 고전·양자 공격 모두에 안전성이 유지되고 있다.

다변수 암호 (Multivariate Cryptography)

유한체 위의 다변수 이차 방정식 계(MQ 문제)를 푸는 어려움에 기반한다. 주로 서명 알고리즘에 사용되며, NIST가 추가 선정한 UOV 등이 이 계열이다.

---

예시·응용

LWE 소규모 직관 예시

import numpy as np

q = 97          # 소수 모듈러스
n = 3           # 차원

# 비밀 벡터 (수신자만 알고 있음)
s = np.array([3, 1, 4])

# 공개 행렬 A (무작위)
A = np.array([[2, 7, 5],
              [1, 3, 9]])

# 작은 오차 벡터
e = np.array([1, -1])

# 공개값 b 생성
b = (A @ s + e) % q
print("공개값 b:", b)
# → b와 A만으로 s를 복원하는 것이 LWE의 어려움

$\mathbf{A}$와 $\mathbf{b}$를 아는 공격자는 $\mathbf{s}$를 효율적으로 구할 수 없다. 실제 ML-KEM에서는 수백 차원의 행렬과 다항식 환(polynomial ring) 구조를 활용하여 효율성과 안전성을 동시에 확보한다.

하이브리드 배포 전략

전환 기간 동안 기존 알고리즘(예: X25519)과 PQC 알고리즘(예: ML-KEM-768)의 공유 비밀을 결합하는 하이브리드 방식이 권장된다. 어느 한쪽이 취약해지더라도 전체 세션은 보호된다. TLS 1.3, SSH, 이메일 암호화 프로토콜에서 ML-KEM 통합 작업이 진행 중이다.

"지금 수집, 나중에 해독" 위협

공격자가 현재의 암호화 트래픽을 저장해 두었다가, 미래에 양자컴퓨터가 실용화된 시점에 해독하는 전략을 "Harvest Now, Decrypt Later(HNDL)" 이라 한다. 장기 기밀성이 요구되는 국방·금융·의료 분야에서는 양자컴퓨터 실용화 이전에 PQC로 전환해야 하는 이유가 여기 있다.

---

정리

PQC는 양자컴퓨터 위협으로부터 디지털 통신을 보호하기 위한 수학 기반 암호 기법이다. 격자 문제(LWE), 해시 함수, 오류 정정 부호, 다변수 이차 방정식 등 다양한 난제를 안전성 근거로 삼으며, 고전 인프라 위에서 실행된다는 점에서 QKD와 상호 보완 관계를 이룬다. NIST 표준(ML-KEM, ML-DSA, SLH-DSA 등)이 확정된 이후 실제 시스템 통합이 빠르게 진행되고 있으며, HNDL 위협을 고려하면 장기 기밀 데이터를 다루는 시스템부터 우선적 전환이 필요하다.