포스트양자암호(PQC) 기초: 양자 위협에 맞서는 차세대 암호학

개념 소개

현대 인터넷 보안의 근간인 RSA와 타원곡선 암호(ECC)는 소인수분해와 이산대수 문제의 계산적 어려움에 의존한다. 고전 컴퓨터로는 수천 년이 걸릴 이 문제들을 Shor의 양자 알고리즘은 다항 시간 안에 풀 수 있다. 충분히 큰 양자 컴퓨터가 실현되면 현행 공개키 인프라(PKI) 전체가 무력화될 수 있다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 양자 컴퓨터를 포함한 모든 알려진 공격에 대해 안전하도록 설계된, 고전 컴퓨터 기반의 암호 알고리즘 집합이다. 양자 채널을 사용하는 양자키분배(QKD)와 달리, PQC는 기존 디지털 기기에서 소프트웨어·하드웨어 업데이트만으로 배포할 수 있다는 현실적 장점이 있다.

핵심 원리

양자 위협의 두 축

Shor 알고리즘은 RSA(소인수분해)와 ECC(이산대수)를 다항 시간에 해결한다. $n$-비트 RSA 키는 $O(n^3)$ 양자 게이트 연산으로 해독된다. 반면 Grover 알고리즘은 대칭키 암호와 해시함수에 대해 제곱근 속도 향상만 제공하므로, AES-128의 실효 보안강도를 64비트 수준으로 낮추는 데 그친다. 대칭키는 길이를 두 배로 늘려 대응할 수 있지만, 공개키 암호는 수학적 기반 자체를 바꿔야 한다.

PQC의 주요 수학적 기반

분류	핵심 난제	대표 알고리즘
격자 기반	LWE, MLWE	CRYSTALS-Kyber, CRYSTALS-Dilithium
해시 기반	해시함수 단방향성	SPHINCS+
부호 기반	선형부호 복호화	Classic McEliece

현재 가장 유망한 분야는 격자 기반 암호다. 핵심 난제인 **LWE(Learning With Errors)**는 다음과 같이 정의된다.

비밀 벡터 $\mathbf{s}\in {\mathbb{Z}}_q^n$와 작은 오류 벡터 $\mathbf{e}$에 대해,

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

주어진 $(\mathbf{A},\mathbf{b})$로부터 $\mathbf{s}$를 복원하는 것은 양자 컴퓨터로도 다항 시간에 불가능하다고 알려져 있다. 오류 벡터 $\mathbf{e}$의 존재가 격자 최단벡터 문제(SVP)와 동등한 난이도를 부여하는 것이 핵심이다.

NIST PQC 표준

미국 국립표준기술연구소(NIST)는 공개 경쟁을 거쳐 다음 표준을 확정했다.

• ML-KEM (CRYSTALS-Kyber 기반): 키 캡슐화 메커니즘, TLS 키 교환 등에 사용
• ML-DSA (CRYSTALS-Dilithium 기반): 범용 디지털 서명
• SLH-DSA (SPHINCS+ 기반): 해시 기반 서명, 격자 기반의 대안
• FN-DSA (FALCON 기반): 소형 서명이 필요한 제약 환경

예시·응용

ML-KEM 키 교환 개념 흐름

# ML-KEM 키 교환 개념 (실제 구현은 liboqs 등 라이브러리 사용)

# 1. 수신측: 키 쌍 생성
public_key, secret_key = ml_kem_keygen()

# 2. 송신측: 공유 비밀 캡슐화
shared_secret_enc, ciphertext = ml_kem_encapsulate(public_key)

# 3. 수신측: 역캡슐화로 동일한 공유 비밀 복원
shared_secret_dec = ml_kem_decapsulate(secret_key, ciphertext)

assert shared_secret_enc == shared_secret_dec  # 양측이 동일한 키 공유

하이브리드 키 교환

현재 전환 기간에는 기존 ECDH와 ML-KEM을 병렬 운용하는 하이브리드 키 교환이 권장된다. 두 키 교환 결과를 함께 해시하여 최종 세션 키를 파생시키면, 어느 한쪽이 안전한 한 전체 보안이 유지된다.

$$K_{\text{session}}=\text{KDF}(K_{\text{ECDH}}\Vert K_{\text{ML-KEM}})$$

이 방식은 TLS 1.3 확장 규격과 일부 브라우저·CDN의 실험적 배포에서 이미 검증되고 있다.

"지금 수집, 나중에 복호화" 위협

적대적 행위자가 현재 암호화된 트래픽을 저장해 두었다가 미래의 양자 컴퓨터로 복호화하는 HNDL(Harvest Now, Decrypt Later) 공격이 실질적 위협으로 부각되고 있다. 기밀 유효기간이 긴 정부·금융·의료 데이터의 경우, 양자 컴퓨터 완성 이전이라도 지금 당장 PQC 전환을 시작해야 할 이유가 된다.

정리

PQC는 Shor 알고리즘의 위협에 대응하기 위해 격자·해시·부호 등 양자 내성 수학 난제를 활용한다. NIST는 ML-KEM·ML-DSA·SLH-DSA 등의 표준을 확정했고, 전환 기간에는 기존 알고리즘과 병렬 사용하는 하이브리드 방식이 권장된다. QKD와 달리 기존 인프라에 소프트웨어 업데이트로 적용 가능하며, HNDL 위협을 고려하면 전환 시기는 빠를수록 유리하다.