포스트양자암호(PQC) 기초: 양자 시대를 대비하는 암호 설계

개념 소개

현재 인터넷 보안의 근간인 RSA와 타원곡선 암호(ECC)는 큰 수의 소인수분해 또는 이산 로그 문제의 계산 난이도에 의존한다. 고전 컴퓨터로는 이 문제들을 풀기 위해 지수적인 시간이 필요하지만, 양자 컴퓨터에서 실행 가능한 쇼어 알고리즘(Shor's algorithm)은 다항 시간 내에 동일한 문제를 해결한다. 충분한 규모의 양자 컴퓨터가 실현되면 현행 공개키 인프라 전체가 위협받는다.

포스트양자암호(Post-Quantum Cryptography, PQC) 는 양자 컴퓨터의 공격에도 안전하도록 설계된 고전 알고리즘 기반 암호 체계다. 양자역학적 원리를 직접 활용하는 양자키분배(QKD)와는 구별되는데, QKD가 전용 양자 채널과 하드웨어를 요구하는 반면 PQC는 기존 디지털 인프라 위에서 소프트웨어로 구현 가능하다는 점에서 단기 배포 가능성이 훨씬 높다.

---

핵심 원리

PQC의 안전성은 양자 알고리즘으로도 효율적으로 풀기 어려운 수학적 난제에 기반한다. 대표적인 네 가지 계열을 살펴본다.

1. 격자 기반 암호 (Lattice-based)

현재 가장 활발하게 연구되는 분야로, $n$차원 격자 위에서 정의된 최단벡터문제(SVP)와 LWE(Learning With Errors)를 핵심 난제로 삼는다.

LWE 문제는 다음과 같다. 비밀 벡터 $\mathbf{s}\in {\mathbb{Z}}_q^n$와 임의 행렬 $\mathbf{A}\in {\mathbb{Z}}_q^{m\times n}$에 대해, 작은 오류 벡터 $\mathbf{e}$가 섞인 샘플로부터 $\mathbf{s}$를 복원하는 것은 계산적으로 매우 어렵다.

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

$\mathbf{A}$와 $\mathbf{b}$가 공개되어도 $\mathbf{e}$가 존재하는 한 $\mathbf{s}$를 역산하기 어렵다는 점이 암호학적 기반이 된다.

2. 해시 기반 암호 (Hash-based)

암호학적 해시 함수의 단방향성만을 가정하므로 보안 근거가 단순하고 분석이 용이하다. 서명 알고리즘에 주로 사용되며, 오랜 역사 덕분에 신뢰도가 높다.

3. 부호 기반 암호 (Code-based)

선형 오류정정부호에서 임의의 부호어를 복호화하는 일반 복호화 문제(Syndrome Decoding)의 난이도를 이용한다. 안전성 분석의 역사가 길다는 장점이 있다.

4. 다변수 다항식 기반 (Multivariate)

유한체 위의 연립 다변수 다항방정식 풀기의 NP-난이도를 활용한다. 주로 서명 스킴에 적용된다.

---

예시·응용

NIST PQC 표준

미국 표준기술연구소(NIST)는 수년간의 공모·심사 과정을 거쳐 2024년에 세 가지 연방 정보 처리 표준(FIPS)을 발표했다.

표준	기반 알고리즘	용도
FIPS 203 (ML-KEM)	CRYSTALS-Kyber	키 캡슐화 (KEM)
FIPS 204 (ML-DSA)	CRYSTALS-Dilithium	디지털 서명
FIPS 205 (SLH-DSA)	SPHINCS+	해시 기반 서명

ML-KEM과 ML-DSA는 모듈 격자(Module Lattice) 구조와 수론 변환(NTT)을 활용해 빠른 연산 속도를 달성한다.

Python으로 살펴보는 LWE 개념 (교육용 단순화)

import numpy as np

def lwe_keygen(n=4, q=97):
    """LWE 기반 키 생성 - 교육 목적 단순 구현"""
    s = np.random.randint(0, 3, size=n)          # 비밀 키 (소정수 벡터)
    A = np.random.randint(0, q, size=(2*n, n))   # 공개 행렬
    e = np.random.randint(0, 2, size=2*n)        # 작은 오류 벡터
    b = (A @ s + e) % q                          # 공개 벡터
    return (A, b), s  # (공개키, 비밀키)

pub, sec = lwe_keygen()
print("공개키 b:", pub[1])
print("비밀키 s:", sec)
# A와 b가 공개되어도 e 때문에 s 복원이 어렵다

수확 후 복호화 위협

현재 암호화된 데이터를 저장했다가 미래의 양자 컴퓨터로 해독하려는 "수확 후 복호화(Harvest Now, Decrypt Later)" 공격이 현실적 우려다. TLS, VPN, 코드 서명 등에 PQC를 조기에 도입해야 하는 이유가 여기에 있다.

---

정리

PQC는 격자·해시·부호·다변수 등 다양한 수학적 난제를 토대로 양자 컴퓨터의 공격을 방어하는 고전 암호 체계다. NIST FIPS 203~205 표준화로 실용화 단계에 접어들었으며, 기존 디지털 인프라와의 호환성 덕분에 QKD와 상호 보완적으로 활용될 전망이다. 현행 암호에서 PQC로의 마이그레이션은 알고리즘 교체를 넘어 전체 보안 아키텍처를 재검토하는 작업임을 유의해야 한다.