포스트양자암호(PQC): 양자컴퓨터 시대의 새로운 암호 체계

개념 소개

현대 인터넷 보안의 근간을 이루는 RSA 암호는 큰 수의 소인수분해가 고전 컴퓨터로는 사실상 불가능하다는 사실에 의존한다. 그런데 1994년 Peter Shor가 제안한 양자 알고리즘(Shor 알고리즘)은 충분히 큰 양자컴퓨터를 사용하면 이 문제를 다항 시간 안에 풀 수 있음을 보였다. 타원곡선 암호(ECC) 역시 이산로그 문제에 기반하므로 동일한 위협에 노출된다.

포스트양자암호(Post-Quantum Cryptography, PQC) 는 양자컴퓨터로도 풀기 어렵다고 알려진 수학적 난제에 기반한 암호 방식을 총칭한다. '양자암호(QKD)'와는 달리, PQC는 기존의 고전 통신 인프라 위에서 소프트웨어만으로 구현할 수 있다는 장점이 있다.

---

핵심 원리

왜 양자컴퓨터에 안전해야 하는가

Grover 알고리즘은 비대칭 탐색 문제에서 $O(\sqrt{N})$의 가속을 제공하므로, AES-128 같은 대칭키 암호는 키 길이를 두 배로 늘리면(AES-256) 어느 정도 방어가 가능하다. 그러나 Shor 알고리즘은 소인수분해와 이산로그를 지수적으로 가속하기 때문에 RSA·ECC는 키 길이를 늘리는 것만으로는 대응이 불충분하다.

주요 PQC 난제 유형

1. 격자(Lattice) 기반 암호

격자란 $n$차원 공간에서 기저 벡터의 정수 선형결합으로 이루어진 점들의 집합이다. 핵심 난제는 다음 두 가지다.

• SVP(Shortest Vector Problem): 격자에서 가장 짧은 벡터를 찾는 문제
• LWE(Learning With Errors): 잡음이 섞인 선형 방정식 시스템을 푸는 문제

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

여기서 $A$는 공개 행렬, $\mathbf{s}$는 비밀 벡터, $\mathbf{e}$는 소규모 오차 벡터다. $\mathbf{b}$와 $A$만 주어졌을 때 $\mathbf{s}$를 복원하는 것이 계산적으로 어렵다는 가정이 암호의 안전성 근거가 된다.

NIST 표준 후보인 CRYSTALS-Kyber(키 캡슐화)와 CRYSTALS-Dilithium(전자서명)이 격자 기반 암호의 대표 사례다.

2. 해시(Hash) 기반 서명

해시 함수의 충돌 저항성과 단방향성만을 안전성 근거로 삼는다. 수학적 가정이 단순하여 신뢰도가 높으나, 서명 크기가 크다는 단점이 있다. SPHINCS+ 가 NIST 표준으로 채택됐다.

3. 코드(Code) 기반 암호

선형 오류 정정 부호에서 임의 선형 코드의 **디코딩 문제(Syndrome Decoding)**가 NP-난해임을 이용한다. 1978년 제안된 McEliece 암호가 원형이며, PQC 시대에도 안전한 것으로 평가받는다.

4. 다변수(Multivariate) 다항식 암호

유한체 위의 다변수 이차 다항식 시스템 풀기(MQ 문제)에 기반한다. 일반적으로 전자서명에 특화된다.

NIST PQC 표준화

미국 국립표준기술연구소(NIST)는 2016년부터 PQC 표준화 공모를 진행했으며, 2024년 FIPS 203(ML-KEM, Kyber 기반), FIPS 204(ML-DSA, Dilithium 기반), FIPS 205(SLH-DSA, SPHINCS+ 기반)를 공식 표준으로 발표했다.

---

예시·응용

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

import numpy as np

def lwe_keygen(n=4, q=97):
    """단순화된 LWE 키 생성 예시 (교육용)"""
    # 공개 행렬 A (무작위)
    A = np.random.randint(0, q, size=(n, n))
    # 비밀 벡터 s (작은 값)
    s = np.random.randint(0, 3, size=n)
    # 오차 벡터 e (작은 노이즈)
    e = np.random.randint(0, 2, size=n)
    # 공개키 b = As + e mod q
    b = (A @ s + e) % q
    return A, b, s  # (공개: A, b) / (비밀: s)

A, b, s = lwe_keygen()
print("공개 행렬 A:\n", A)
print("공개 벡터 b:", b)
print("비밀 벡터 s:", s)
# 실제 복호화는 s를 알 때만 가능

실제 응용 사례

• TLS/HTTPS 전환: 구글 Chrome·Cloudflare 등은 이미 Kyber 기반 하이브리드 키 교환을 실험 배포하고 있다.
• 암호화 민감 문서 보호: "지금 저장하고 나중에 해독(Harvest Now, Decrypt Later)" 공격에 대비해 장기 보존 데이터에 PQC 적용이 권고된다.
• 전자서명 인프라: PKI 인증서 체계에서 RSA를 Dilithium으로 교체하는 마이그레이션 작업이 진행 중이다.

---

정리

PQC는 양자컴퓨터의 위협으로부터 기존 통신 인프라를 보호하기 위한 현실적인 대안이다. 격자·해시·코드 기반 등 다양한 수학적 난제를 활용하며, NIST 표준화를 통해 실용 단계에 진입했다. 현재는 기존 암호와 PQC를 병행하는 하이브리드 방식으로 전환이 권장된다. 양자암호(QKD)와 PQC는 상호 보완 관계에 있으며, 함께 활용하면 더욱 강력한 보안 체계를 구성할 수 있다.