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

개념 소개

현대 공개키 암호의 두 기둥인 RSA와 타원곡선 암호(ECC)는 각각 큰 수의 소인수분해와 이산 로그 문제의 계산적 어려움에 안전성을 의존한다. 고전 컴퓨터로는 수천 비트 키를 가진 RSA를 우주 수명 규모의 시간이 없으면 풀 수 없다.

그런데 1994년 피터 쇼어가 제안한 양자 알고리즘은 이 두 문제를 다항식 시간 $O((\log N{)}^3)$ 안에 해결한다. 충분한 규모의 내결함성 양자 컴퓨터가 실현되는 순간, 현재 인터넷 통신·전자서명·공개키 기반구조(PKI) 전체가 일시에 무력화된다.

더 심각한 위협은 "지금 수집하고 나중에 해독한다(Harvest Now, Decrypt Later)" 전략이다. 적대적 행위자가 현재 암호화된 트래픽을 저장해 두었다가, 미래의 양자 컴퓨터로 소급 해독하는 시나리오는 군사·외교·금융 분야에서 이미 현실적 위협으로 다뤄지고 있다.

포스트양자암호(PQC) 는 이에 대응하여 고전 컴퓨터로만 구동되지만, 알려진 양자 알고리즘에도 깨지지 않는 수학 문제를 기반으로 설계된 암호 체계이다. 양자 하드웨어를 요구하지 않으므로, 현재의 소프트웨어·네트워크 인프라에 비교적 용이하게 통합된다.

---

핵심 원리

격자 기반 암호 (Lattice-based)

고차원 격자(lattice)에서 짧은 벡터 찾기(SVP) 나 가장 가까운 벡터 찾기(CVP) 는 고전·양자 컴퓨터 모두에게 지수 시간이 걸리는 것으로 알려져 있다. 실용적 구현에는 오류 학습 문제(LWE, Learning With Errors) 와 그 변형인 모듈-LWE(Module-LWE, MLWE) 가 쓰인다.

LWE 문제의 핵심:

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

공개된 행렬 $\mathbf{A}\in {\mathbb{Z}}_q^{m\times n}$과 벡터 $\mathbf{b}$가 주어질 때, 작은 오류 $\mathbf{e}$와 비밀 $\mathbf{s}$를 동시에 복원하는 문제는 현존하는 최선의 양자 알고리즘으로도 지수 시간이 소요된다.

NIST가 2024년 최종 표준으로 채택한 ML-KEM(구 CRYSTALS-Kyber)은 MLWE에 기반한 키 캡슐화 메커니즘(KEM)이며, ML-DSA(구 CRYSTALS-Dilithium)는 같은 수학 구조 위의 전자서명 방식이다.

해시 기반 서명 (Hash-based)

일방향 해시 함수의 안전성만을 가정하므로 수학적 근거가 가장 단순하다. SPHINCS+(표준명 SLH-DSA)는 상태(state)를 보관할 필요 없는 무상태 해시 기반 서명으로, 장기 보존이 필요한 문서 서명에 적합하다.

부호 기반 암호 (Code-based)

맥엘리스(McEliece) 암호는 일반 선형 부호에서 오류 정정 문제의 어려움을 이용하며, 1978년 제안 이후 지금까지 실질적 공격이 알려지지 않았다. 단, 공개키 크기가 수백 KB에 달해 통신 효율이 낮다는 단점이 있다.

---

예시·응용

ML-KEM 키 교환 개념 코드

아래는 표준 API 구조를 단순화한 의사 코드(pseudocode)이다.

# 실제 구현은 liboqs, pqcrypto 등의 검증된 라이브러리를 사용해야 한다.
from pqcrypto.kem.kyber768 import generate_keypair, encrypt, decrypt

# 수신자: 공개키/비밀키 생성
public_key, secret_key = generate_keypair()

# 송신자: 공개키로 공유 비밀(shared_secret) 캡슐화
ciphertext, shared_secret_sender = encrypt(public_key)

# 수신자: 비밀키로 복호화하여 동일한 공유 비밀 복원
shared_secret_receiver = decrypt(secret_key, ciphertext)

assert shared_secret_sender == shared_secret_receiver  # 키 교환 성공

하이브리드 모드

현재 TLS 1.3에서는 기존 X25519 ECDH와 ML-KEM-768을 결합한 하이브리드 키 교환이 권장된다. 어느 한쪽이 안전하면 전체 통신이 보호되므로, 전환 기간의 이중 보험 역할을 한다.

$$\text{공유 비밀}=\text{KDF}(K_{\text{ECDH}}\Vert K_{\text{ML-KEM}})$$

---

정리

PQC는 양자 컴퓨터 위협에 대응하는 고전 소프트웨어 기반 암호 체계이다. NIST는 격자·해시·부호 기반 알고리즘을 표준화했으며, 각 계열은 서로 다른 수학적 난제를 근거로 삼아 다양한 시나리오에 대비한다. 현시점에서 가장 실용적인 접근은 기존 알고리즘과 PQC를 병용하는 하이브리드 모드이며, 인프라 전환은 장기적 관점에서 단계적으로 이루어져야 한다.