포스트양자암호(PQC) 기초: 양자 위협에 대비하는 암호 설계

개념 소개

현재 인터넷 보안의 근간을 이루는 RSA와 타원곡선 암호(ECC)는 큰 수의 소인수분해, 혹은 이산 로그 문제의 계산적 어려움에 안전성을 근거한다. 고전 컴퓨터로는 이 문제들을 현실적인 시간 안에 풀 수 없다. 그러나 대규모 양자컴퓨터가 실현되면, 쇼어(Shor) 알고리즘을 통해 RSA와 ECC가 다항시간 내에 해독될 수 있다.

포스트양자암호(Post-Quantum Cryptography, PQC)는 이러한 양자컴퓨터의 위협에도 안전한 암호 체계를 설계하는 분야이다. '포스트양자'란 양자컴퓨터 이후 시대를 대비한다는 의미이며, 양자역학 자체를 이용하는 양자키분배(QKD)와는 근본적으로 구별된다. PQC는 고전 컴퓨터에서 동작하되, 알려진 최선의 고전·양자 알고리즘으로도 효율적으로 풀기 어려운 수학 문제에 보안을 기댄다.

핵심 원리

기존 암호가 취약해지는 이유

RSA의 안전성은 $N=p\times q$ 형태의 큰 합성수 소인수분해의 어려움에 있다. 쇼어 알고리즘은 양자 퓨리에 변환(QFT)을 이용해 이를 $O((\log N{)}^3)$ 시간에 해결한다. 대칭키 암호(AES 등)는 그로버(Grover) 알고리즘에 의해 유효 키 길이가 절반으로 줄어들지만, 키 길이를 두 배로 늘려 실용적으로 대응 가능하다.

PQC의 수학적 기반

PQC 알고리즘은 크게 네 가지 수학적 어려움을 활용한다.

분류	핵심 어려움
격자 기반 (Lattice-based)	LWE, NTRU 문제
해시 기반 (Hash-based)	해시함수 일방향성
코드 기반 (Code-based)	선형 오류 정정 코드 복호화
다변수 다항식 (Multivariate)	연립 다변수 방정식 풀기

가장 주목받는 것은 격자 기반 암호이다. 핵심 난제인 LWE(Learning With Errors) 문제를 살펴보자. $n$차원 비밀 벡터 $\mathbf{s}$, 임의 행렬 $A\in {\mathbb{Z}}_q^{m\times n}$, 작은 오류 벡터 $\mathbf{e}$에 대해

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

를 관측할 때 $\mathbf{s}$를 복원하는 문제가 LWE이다. 오류 $\mathbf{e}$가 없다면 선형대수로 즉시 풀리지만, 작은 오류가 더해지면 현재까지 알려진 최선의 고전·양자 알고리즘 모두 지수적 시간이 필요하다. 이 어려움이 격자 기반 암호의 안전성 근거가 된다.

NIST 표준화

미국 국립표준기술연구소(NIST)는 2016년부터 PQC 표준화 작업을 진행하였으며, 2024년 세 가지 알고리즘을 연방 표준(FIPS)으로 확정하였다.

• FIPS 203 (ML-KEM): CRYSTALS-Kyber 기반 키 캡슐화 메커니즘
• FIPS 204 (ML-DSA): CRYSTALS-Dilithium 기반 디지털 서명
• FIPS 205 (SLH-DSA): SPHINCS+ 기반 해시 기반 서명

예시·응용

ML-KEM (Kyber) 키 교환 흐름

Kyber는 키 캡슐화 메커니즘(KEM) 방식으로 동작한다. 아래는 개념을 설명하는 의사코드이다.

# 개념적 의사코드 (실제 구현은 liboqs 등 라이브러리 사용)

# 수신자: 공개키(pk)·비밀키(sk) 생성
pk, sk = kyber_keygen()

# 송신자: 공개키로 세션키(K)를 캡슐화하여 암호문(ct) 생성
ct, K_sender = kyber_encapsulate(pk)

# 수신자: 비밀키로 암호문 복호화 → 동일한 세션키 복원
K_receiver = kyber_decapsulate(sk, ct)

# 두 당사자가 동일한 세션키를 공유하여 이후 대칭 암호화에 사용
assert K_sender == K_receiver

Kyber-768 기준으로 공개키 크기는 1,184바이트, 암호문은 1,088바이트이다. RSA-2048의 공개키(256바이트)보다 크지만, 연산 속도는 유사하거나 더 빠르다. Google과 Cloudflare는 이미 TLS 1.3 핸드셰이크에 ML-KEM을 실험적으로 통합한 바 있다.

하이브리드 마이그레이션 전략

현재 산업계에서는 기존 알고리즘(예: ECDH)과 PQC 알고리즘을 병렬로 사용하는 하이브리드 방식이 권장된다. PQC 알고리즘에 아직 발견되지 않은 취약점이 존재할 가능성을 감안한 이중 안전 장치이며, IETF는 TLS와 SSH 표준에 이 방식을 반영하고 있다.

또한 "지금 수집, 나중 해독(Harvest Now, Decrypt Later)" 공격, 즉 현재 암호화 데이터를 저장해 두었다가 양자컴퓨터가 완성된 후 해독하려는 시나리오에 대비하여, 민감 데이터를 다루는 기관은 PQC 전환을 시급한 과제로 다루고 있다.

정리

PQC는 쇼어 알고리즘 등 양자 공격으로부터 디지털 통신 인프라를 보호하기 위한 핵심 기술이다. 격자 기반(LWE), 해시 기반, 코드 기반 등 양자컴퓨터로도 풀기 어려운 수학 문제에 안전성을 근거하며, NIST 표준 확정으로 실용 단계에 진입하였다. QKD가 물리적 채널 보안을 제공하는 반면, PQC는 소프트웨어 수준에서 기존 네트워크 인프라에 점진적으로 통합할 수 있다는 실용적 장점이 있다.