포스트양자암호(PQC): 양자 컴퓨터 시대의 암호 기술

개념 소개

현대 인터넷 보안의 근간인 RSA 암호는 두 큰 소수의 곱을 인수분해하기 어렵다는 사실에 기반한다. 타원곡선 암호(ECC) 역시 이산로그 문제의 계산적 난이도를 활용한다. 고전 컴퓨터로는 이 두 문제를 현실적인 시간 안에 풀 수 없다.

그러나 1994년 피터 쇼어는 양자 컴퓨터가 다항 시간 내에 인수분해와 이산로그를 해결할 수 있는 알고리즘을 제시했다. 수천 개의 논리적 큐비트를 갖춘 범용 양자 컴퓨터가 실현되는 순간, 현재 인터넷 보안 체계 전체가 무력화될 수 있다.

포스트양자암호(Post-Quantum Cryptography, PQC) 는 이러한 위협에 대응하기 위해, 양자 컴퓨터로도 풀기 어려운 수학적 난제를 기반으로 설계된 암호 알고리즘군을 말한다. '양자 암호(Quantum Cryptography)'가 양자역학 물리 현상 자체를 이용하는 것과 달리, PQC는 고전 컴퓨터 위에서 동작하는 수학적 알고리즘이다.

---

핵심 원리

쇼어 알고리즘의 위협

쇼어 알고리즘은 양자 푸리에 변환(QFT)을 이용하여 주기 탐색 문제를 효율적으로 해결한다. $N$-비트 정수의 인수분해를 $O((\log N{)}^3)$ 복잡도로 수행하므로, $n=2048$비트 RSA 키도 충분한 큐비트가 있으면 수 시간 내 해독이 가능해진다.

그뿐만 아니라 그로버 알고리즘은 비정형 탐색을 $O(\sqrt{N})$으로 가속하여 대칭키 암호(AES 등)의 유효 키 길이를 절반으로 줄인다. 따라서 AES-128은 양자 환경에서 AES-64 수준으로 약화된다.

PQC의 주요 수학적 기반

1. 격자 기반(Lattice-based)

가장 활발하게 연구되는 분야이다. 핵심 난제는 다음 두 가지다.

• SVP (Shortest Vector Problem): 격자에서 가장 짧은 벡터를 찾는 문제
• LWE (Learning With Errors): 오류가 섞인 선형 연립방정식을 푸는 문제

LWE를 예로 들면, $n$차원 비밀 벡터 $\mathbf{s}\in {\mathbb{Z}}_q^n$에 대해

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

여기서 $A$는 공개 행렬, $\mathbf{e}$는 작은 오류 벡터이다. $(A,\mathbf{b})$만으로 $\mathbf{s}$를 복원하는 것이 계산적으로 어렵다는 것이 LWE의 핵심이다.

NIST 표준으로 선정된 ML-KEM(구 CRYSTALS-Kyber) 이 이 범주에 속한다.

2. 해시 기반(Hash-based)

해시 함수의 단방향성만을 안전성 근거로 삼기 때문에, 양자 알고리즘에 대한 저항성이 가장 보수적으로 분석된다. 대표 알고리즘으로 SPHINCS+ (NIST 표준: SLH-DSA)가 있다. 서명 크기가 크다는 단점이 있으나 안전성 가정이 단순하다.

3. 부호 기반(Code-based)

선형 오류 수정 부호에서 임의 부호의 복호화 문제(Syndrome Decoding)를 난제로 사용한다. McEliece 암호(1978)가 원형이며, 수십 년간 공격에 버텨왔다.

4. 다변수 다항식(Multivariate)

${\mathbb{F}}_q$ 위의 연립 다변수 이차 방정식

$$p_i(x_1,\dots ,x_n)=0,i=1,\dots ,m$$

의 해를 구하는 문제(MQ Problem)를 기반으로 한다. 주로 전자서명에 활용된다.

NIST PQC 표준화

NIST는 2016년 공모를 시작하여 수 라운드의 분석·검토를 거쳤으며, 다음 알고리즘들을 표준으로 확정·진행 중이다.

용도	표준명	기반
키 캡슐화(KEM)	ML-KEM	격자(MLWE)
전자서명	ML-DSA	격자(Dilithium)
전자서명	SLH-DSA	해시(SPHINCS+)
전자서명	FN-DSA	격자(Falcon)

---

예시·응용

Python 예시: ML-KEM 키 교환 개념 시뮬레이션

실제 ML-KEM 라이브러리(liboqs Python 바인딩 등)를 활용하면 다음과 같은 흐름으로 동작한다.

# pip install liboqs-python (oqs 래퍼)
import oqs

kem_alg = "ML-KEM-768"

# 송신자: 키 쌍 생성
with oqs.KeyEncapsulation(kem_alg) as sender:
    public_key = sender.generate_keypair()

    # 수신자: 공개키로 공유 비밀 캡슐화
    with oqs.KeyEncapsulation(kem_alg) as receiver:
        ciphertext, shared_secret_recv = receiver.encap_secret(public_key)

    # 송신자: 암호문으로 공유 비밀 복원
    shared_secret_send = sender.decap_secret(ciphertext)

assert shared_secret_send == shared_secret_recv
print("공유 비밀 일치:", shared_secret_send.hex()[:32], "...")

실제 도입 사례

• TLS 1.3 하이브리드 모드: X25519(기존 ECC)와 ML-KEM-768을 결합하여, 고전 컴퓨터 보안과 양자 저항성을 동시에 확보한다.
• 국가·금융 인프라: 미국 CISA, 국내 KISA 등 각국 보안 기관이 전환 가이드라인을 발표하고 있다.
• "지금 수집, 나중에 해독(HNDL)" 공격 대비: 현재의 암호화 트래픽을 저장한 후 미래 양자 컴퓨터로 해독하는 시나리오 때문에 전환이 시급하다.

---

정리

PQC는 양자 컴퓨터의 쇼어·그로버 알고리즘으로 인해 무력화될 기존 공개키 암호를 대체하기 위해 등장했다. 격자, 해시, 부호, 다변수 다항식 등 양자 알고리즘으로도 효율적으로 풀기 어려운 수학적 난제를 활용한다. NIST 표준화가 완료됨에 따라 TLS, PKI, 금융 인프라 등 실제 시스템으로의 이전이 본격화되고 있으며, 특히 HNDL 위협 때문에 조기 전환이 권고된다.