포스트양자암호(PQC) 기초: 양자 시대의 암호 체계

개념 소개

현대 공개키 암호 체계는 두 가지 수학적 어려움 가정 위에 세워져 있다. RSA는 큰 정수의 소인수분해, 타원곡선암호(ECC)는 이산 로그 문제의 어려움에 의존한다. 그런데 쇼어 알고리즘(Shor's Algorithm)은 이 두 문제를 양자 컴퓨터로 다항식 시간 안에 풀어낸다. 2048비트 RSA 기준으로 고전 컴퓨터에서는 우주 나이보다 긴 시간이 필요하지만, 충분한 큐비트를 갖춘 양자 컴퓨터라면 이론적으로 수 시간 내에 해독이 가능하다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 이 위협에 대응하기 위해 고전 컴퓨터와 양자 컴퓨터 모두에 대해 계산적으로 어려운 수학 문제에 기반을 두는 암호 체계다. 양자 채널이나 특수 하드웨어 없이 기존 소프트웨어 인프라 위에서 구현할 수 있다는 점이 핵심 장점이다.

---

핵심 원리

지금 수집, 나중에 해독(Harvest Now, Decrypt Later)

대규모 양자 컴퓨터가 아직 존재하지 않더라도, 공격자는 오늘 암호화된 트래픽을 대량으로 저장해 두었다가 미래에 해독하는 전략을 취할 수 있다. 기밀 유효 기간이 10년 이상인 정부·의료·금융 데이터에는 지금 당장 PQC 전환이 필요하다는 의미다.

PQC의 주요 수학적 기반

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

고차원 격자에서의 **학습 오류 문제(LWE, Learning With Errors)**를 핵심 어려움으로 삼는다.

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

$A$는 공개 행렬, $\mathbf{s}$는 비밀 벡터, $\mathbf{e}$는 소규모 오류 벡터다. $A$와 $\mathbf{b}$만으로 $\mathbf{s}$를 복원하는 것이 계산적으로 어렵다는 것이 안전성의 근거다. 현재 NIST 표준 ML-KEM, ML-DSA가 여기에 속한다.

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

일방향 해시 함수의 단방향성만을 가정한다. 수학적 가정이 단순해 신뢰도가 높지만 서명 크기가 크다. SPHINCS+가 대표적이며 NIST SLH-DSA로 표준화되었다.

3. 코드 기반 암호(Code-based)

임의의 선형 코드에서 오류를 복원하는 **일반 디코딩 문제(General Decoding Problem)**의 어려움을 이용한다. Classic McEliece가 대표적이다.

NIST PQC 표준 (2024년 최종 발표)

표준	기반	용도
ML-KEM (FIPS 203)	격자(MLWE)	키 캡슐화
ML-DSA (FIPS 204)	격자(MLWE)	전자서명
SLH-DSA (FIPS 205)	해시	전자서명

---

예시·응용

LWE 개념 시뮬레이션

import numpy as np

def lwe_demo(n=4, q=97, seed=42):
    rng = np.random.default_rng(seed)

    s = np.array([3, 1, 4, 1])           # 비밀 벡터 (수신자만 알고 있음)
    A = rng.integers(0, q, size=(6, n))   # 공개 행렬
    e = rng.integers(-2, 3, size=6)       # 소규모 오류

    b = (A @ s + e) % q                   # 공개 벡터

    print("공개 행렬 A:")
    print(A)
    print(f"\n공개 벡터 b: {b}")
    print(f"(비밀) s={s}, e={e}")
    print("\n→ A와 b만으로 s를 복원하는 것이 LWE 문제")

lwe_demo()

실제 ML-KEM은 $n=256$, $q=3329$의 다항식 환(Ring) 위에서 동작해 연산 효율을 크게 높인다.

실제 적용 사례

• TLS/HTTPS: 일부 브라우저는 X25519와 ML-KEM을 결합한 하이브리드 키 교환을 실험적으로 지원 중이다.
• QKD 보완: 양자키분배(QKD)는 인증 단계에서 고전 공개키를 사용하므로, PQC로 대체해야 완전한 양자 안전성을 달성할 수 있다.
• 마이그레이션 전략: 기존 시스템과 PQC 알고리즘을 병렬로 운용하는 하이브리드 방식이 전환 기간의 실용적 대안이다.

---

정리

PQC는 양자 컴퓨팅 시대에 대비해 기존 통신 인프라를 보호하는 소프트웨어 기반 해법이다. 격자 기반 암호(ML-KEM, ML-DSA)가 성능과 안전성 균형 면에서 현재 가장 주목받으며 NIST 표준으로 자리잡았다. QKD가 물리적 계층에서 키 분배 문제를 해결한다면, PQC는 응용·프로토콜 계층에서 보완적인 역할을 수행한다. 두 기술을 함께 고려하는 것이 장기적으로 견고한 양자 안전 보안 설계의 방향이다.