포스트양자암호(PQC) 기초: 양자 위협에 맞선 새로운 암호 체계

개념 소개

현재 인터넷 보안의 근간인 RSA와 타원곡선 암호(ECC)는 각각 정수 인수분해와 이산 대수 문제의 계산적 어려움에 기반한다. 고전 컴퓨터로는 이 문제들을 풀기 위해 지수 시간이 필요하지만, 1994년 Peter Shor가 제안한 양자 알고리즘은 다항 시간 내에 두 문제를 모두 해결할 수 있음을 보였다. 충분한 오류 정정 큐비트를 갖춘 범용 양자 컴퓨터가 실현되면 현재의 공개키 암호 체계는 사실상 무력화된다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 양자 컴퓨터의 연산 능력으로도 해독하기 어렵다고 여겨지는 수학적 난제에 기반한 암호 체계이다. 양자 물리를 직접 이용하는 양자키분배(QKD)와 달리, PQC는 고전 컴퓨터에서 소프트웨어로 실행된다. 기존 통신 인프라와의 호환성을 유지하면서 양자 위협에 대응할 수 있다는 점에서 현실적 대안으로 주목받는다.

---

핵심 원리

PQC는 여러 수학적 난제군에 기반한다. 그 중 가장 활발히 채택된 것이 **격자 기반 암호(Lattice-based Cryptography)**이며, 핵심 난제는 **학습-에러 문제(Learning With Errors, LWE)**이다.

$n$차원 비밀 벡터 $\mathbf{s}\in {\mathbb{Z}}_q^n$에 대해, 임의 벡터 ${\mathbf{a}}_i\in {\mathbb{Z}}_q^n$와 작은 오류 $e_i$를 이용해 다음 샘플을 생성한다.

$$b_i=⟨{\mathbf{a}}_i,\mathbf{s}⟩+e_i(\mathrm{mod}q)$$

주어진 수많은 쌍 $({\mathbf{a}}_i,b_i)$로부터 $\mathbf{s}$를 복원하는 것이 LWE 문제이다. 오류 항 $e_i$가 없으면 선형 방정식으로 쉽게 풀리지만, 작은 오류가 더해지면 최적 양자 알고리즘을 포함해 어떤 효율적 방법으로도 풀기 어렵다는 것이 현재의 지배적 믿음이다.

실용 알고리즘에서는 다항식 환(polynomial ring) 위에 정의된 Ring-LWE와 모듈 구조를 결합한 Module-LWE를 사용해 연산 효율을 높인다.

PQC를 구성하는 주요 수학적 기반은 다음과 같다.

종류	핵심 난제	특징
격자 기반	LWE, Ring-LWE	빠른 연산, 작은 키 크기
해시 기반	일방향 해시 함수	가장 보수적 보안 가정
코드 기반	임의 선형 코드 디코딩	역사가 긴 난제
다변수 기반	연립 다변수 다항식	짧은 서명 가능

---

예시·응용

NIST 표준화 알고리즘

미국 표준기술연구소(NIST)는 다년간의 공모·분석 과정을 거쳐 PQC 표준 알고리즘을 확정하였다.

표준 명칭	원 알고리즘	용도	수학적 기반
ML-KEM	CRYSTALS-Kyber	키 캡슐화	Module-LWE
ML-DSA	CRYSTALS-Dilithium	전자서명	Module-LWE
SLH-DSA	SPHINCS+	전자서명	해시 기반
FN-DSA	FALCON	전자서명	NTRU 격자

LWE 샘플 생성 예시 (교육용)

import numpy as np

def lwe_sample(s, q, sigma=2.0):
    """단순 LWE 샘플 생성 (교육 목적)"""
    n = len(s)
    a = np.random.randint(0, q, size=n)
    e = int(np.round(np.random.normal(0, sigma)))  # 작은 오류
    b = (int(np.dot(a, s)) + e) % q
    return a, b, e

n, q = 8, 97
s = np.array([3, 1, 4, 1, 5, 9, 2, 6])  # 비밀 벡터

a, b, e = lwe_sample(s, q)
print(f"a  = {a}")
print(f"b  = {b}  (≡ <a,s> + {e}  mod {q})")
print(f"오류 없이 <a,s> mod q = {int(np.dot(a,s)) % q}")

수천 개의 $({\mathbf{a}}_i,b_i)$ 쌍을 관찰해도 $\mathbf{s}$를 효율적으로 복원할 수 없다. 이것이 ML-KEM과 ML-DSA의 보안 근거이다.

하이브리드 방식과 실용화 동향

Google, Cloudflare 등은 이미 TLS 핸드셰이크에 ML-KEM 기반 하이브리드 키 교환을 도입하였다. 하이브리드 방식은 기존 ECC와 ML-KEM을 병행 적용해, 하나가 안전하면 전체 세션이 보호되도록 설계한다. 이는 PQC 알고리즘에 대한 미발견 취약점에 대비한 전략이기도 하다.

특히 주목할 위협은 "지금 수집하고 나중에 복호화(Harvest Now, Decrypt Later)" 공격이다. 공격자가 암호화된 트래픽을 현재 수집하고, 미래의 양자 컴퓨터로 해독하는 시나리오로, 이에 대응하기 위해 충분한 양자 컴퓨터가 실현되기 이전에 PQC 전환이 요구된다.

---

정리

포스트양자암호는 쇼어 알고리즘이 초래하는 공개키 암호 위협에 대응하는 현실적 해법이다. LWE 기반 격자 암호를 중심으로, 해시 기반·코드 기반 등 다양한 수학적 난제를 활용하는 알고리즘들이 NIST 표준으로 확정되어 실용화 단계에 접어들었다. PQC는 고전 인프라 위에서 실행되면서도 양자 공격에 견딜 수 있어, 양자-고전 혼합 환경에서 통신 보안의 핵심 축을 담당할 것이다.