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

먼저 읽으면 좋은 용어

개념 소개

현재 인터넷 보안의 근간을 이루는 RSA와 타원곡선암호(ECC)는 소인수분해 및 이산로그 문제의 계산적 어려움에 의존한다. 고전 컴퓨터로는 이 문제들을 지수적 시간 내에만 풀 수 있어 실질적으로 안전하지만, 충분히 강력한 양자컴퓨터가 등장하면 사정이 달라진다.

쇼어 알고리즘은 $n$ 비트 정수의 소인수분해를 $O (n^{3})$ 시간에 해결한다. 이는 현재 사용 중인 2048비트 RSA 키가 대형 양자컴퓨터 앞에서 수 시간 내에 해독될 수 있음을 의미한다. 또한 그로버(Grover) 알고리즘은 대칭키 암호의 유효 키 길이를 절반으로 줄이므로, AES-128은 AES-256으로 교체가 권장된다.

이 위협에 대응하는 **포스트양자암호(Post-Quantum Cryptography, PQC)**는 양자컴퓨터로도 효율적인 알고리즘이 알려져 있지 않은 수학 문제에 기반한 암호 알고리즘 집합이다. 물리적 양자 채널을 사용하는 양자키분배(QKD)와 달리, PQC는 기존 고전 통신 인프라 위에서 소프트웨어 업데이트만으로 배포할 수 있다는 점에서 즉각적인 실용화가 가능하다.

핵심 원리

PQC 알고리즘은 수학적 기반에 따라 크게 네 계열로 분류된다.

격자 기반 암호 (Lattice-based)

현재 표준화의 핵심을 차지하는 계열로, LWE(Learning With Errors) 문제가 기반이 된다.

비밀 벡터 $s \in Z_{q}^{n}$ , 무작위 행렬 $A \in Z_{q}^{m \times n}$ , 소량의 오류 벡터 $e$ 에 대해 다음을 정의한다.

$b = A s + e (mod q)$

$(A, b)$ 가 주어졌을 때 $s$ 를 복원하는 것이 LWE 문제다. 오류 $e$ 가 없으면 가우스 소거법으로 쉽게 풀리지만, 작은 무작위 오류가 더해지면 양자컴퓨터를 포함한 어떤 알고리즘도 현재까지 효율적으로 해결하지 못한다. 모듈 격자 변형인 **MLWE(Module Learning With Errors)**는 효율성과 보안성을 동시에 확보하여 실용적 표준 알고리즘의 기반이 된다.

해시 기반 서명 (Hash-based)

일방향 해시 함수의 보안성만을 가정하는 가장 보수적인 방식이다. **SPHINCS+**가 대표적이며, 머클 트리(Merkle tree) 구조를 활용해 일회성 서명을 계층적으로 쌓아 올린다. 키 크기와 서명 크기가 크고 속도가 느리지만, 가정하는 수학 구조가 단순하여 장기적 신뢰도가 높다.

코드 기반 암호 (Code-based)

선형 오류정정부호에서 오류를 복원하는 디코딩 문제의 어려움을 이용한다. McEliece 암호는 1970년대부터 연구되어 내구성이 가장 오래 검증되었으나, 공개키 크기가 수백 KB에 달하는 단점이 있다.

다변수 암호 (Multivariate)

유한체 위의 다변수 이차방정식 시스템을 푸는 것의 어려움을 이용한다. 서명 크기가 작아 자원 제약 환경에 유리하다.

예시·응용

NIST PQC 표준

NIST는 공모 및 검토 과정을 거쳐 다음 네 알고리즘을 연방 정보처리 표준(FIPS)으로 확정했다.

표준	알고리즘	용도	수학적 기반
FIPS 203	ML-KEM (Kyber)	키 캡슐화	MLWE
FIPS 204	ML-DSA (Dilithium)	전자서명	MLWE
FIPS 205	SLH-DSA (SPHINCS+)	전자서명	해시 함수
FIPS 206	FN-DSA (FALCON)	전자서명	NTRU 격자

ML-KEM 키 교환 개념 코드

# 개념적 의사 코드 — 실제 구현은 liboqs 등 공인 라이브러리 사용 권장
from oqs import KeyEncapsulation

# 수신자: 공개키/비밀키 쌍 생성
kem = KeyEncapsulation("ML-KEM-768")
public_key = kem.generate_keypair()

# 송신자: 공개키로 캡슐(ciphertext)과 공유 비밀 생성
with KeyEncapsulation("ML-KEM-768") as sender:
    ciphertext, shared_secret_enc = sender.encap_secret(public_key)

# 수신자: 캡슐을 비밀키로 복호화하여 동일한 공유 비밀 복원
shared_secret_dec = kem.decap_secret(ciphertext)

assert shared_secret_enc == shared_secret_dec  # 키 교환 성공

ML-KEM의 보안 파라미터는 ML-KEM-512(NIST 레벨 1), ML-KEM-768(레벨 3), ML-KEM-1024(레벨 5) 세 가지로 제공된다.

PQC와 QKD의 상호 보완

PQC는 계산적 안전성(Computational Security), QKD는 정보이론적 안전성(Information-theoretic Security)을 제공한다. 두 방식은 대립적이지 않으며, 전용 광섬유 인프라가 구축된 고보안 환경에서는 PQC와 QKD를 조합한 하이브리드 방식이 검토된다. QKD가 마련한 대칭키를 PQC 보호 채널을 통해 갱신하는 구조가 그 예다.

정리

PQC는 양자컴퓨터 시대를 대비하는 가장 현실적인 암호 솔루션이다. 격자 기반 LWE 문제가 효율성과 보안성 균형으로 표준화의 중심을 차지하며, 해시 기반·코드 기반 방식이 보수적 대안으로 공존한다. 기존 시스템을 PQC로 전환할 때는 알고리즘을 쉽게 교체할 수 있는 설계 원칙인 암호 민첩성(Crypto Agility) 확보가 핵심 전략이 된다. 표준이 확정된 현 시점에서 전환 계획 수립과 테스트가 실무적으로 중요하다.

Exercises

연습문제

Q1RSA는 고전 컴퓨터에는 안전하지만 양자컴퓨터에는 취약하다. 그 이유를 쇼어 알고리즘과 연계하여 설명하라.
힌트 보기
RSA 보안의 근거인 소인수분해의 계산 복잡도를 고전 컴퓨터와 양자컴퓨터 관점에서 각각 생각해 보라.
해설 보기
RSA는 큰 정수 $N = p \cdot q$의 소인수분해가 고전 컴퓨터로는 지수적 시간($O(\exp(n^{1/3}))$ 수준)이 걸린다는 사실에 보안 근거를 둔다. 반면 쇼어 알고리즘은 양자 푸리에 변환을 이용해 소인수분해를 $O(n^3)$의 다항식 시간에 해결하므로, 충분히 큰 양자컴퓨터가 존재하면 RSA 키를 현실적 시간 내에 해독할 수 있다. 즉, 양자컴퓨터는 RSA가 의존하는 계산적 어려움 가정 자체를 붕괴시킨다.
Q2LWE 문제에서 오류 벡터 $\mathbf{e}$의 역할은 무엇인가? $\mathbf{e} = \mathbf{0}$이면 어떤 일이 발생하는가?
해설 보기
오류 벡터 $\mathbf{e}$는 LWE 문제를 어렵게 만드는 핵심 요소다. $\mathbf{e} = \mathbf{0}$이면 $\mathbf{b} = A\mathbf{s} \pmod{q}$가 되어 선형 연립방정식이 성립하므로, 가우스 소거법으로 $O(n^3)$ 시간에 비밀 벡터 $\mathbf{s}$를 쉽게 복원할 수 있다. 반면 소량의 무작위 오류가 더해지면 방정식 구조가 흐트러져 양자컴퓨터를 포함한 현재 알려진 어떤 알고리즘도 효율적으로 $\mathbf{s}$를 복원하지 못한다. 즉, $\mathbf{e}$의 존재가 LWE를 NP-hard 문제로 만드는 것으로 추정된다.
Q3PQC와 QKD는 각각 어떤 유형의 보안성을 제공하며, 두 기술을 조합하는 이유는 무엇인가?
해설 보기
PQC는 계산적 안전성을 제공한다. 즉, 현재까지 알려진 알고리즘(양자 알고리즘 포함)으로 공격이 비효율적임을 보장하지만, 미래에 새로운 알고리즘이 등장하면 보안이 깨질 수 있다. QKD는 양자역학의 물리적 법칙에 기반한 정보이론적 안전성을 제공하여 계산 능력에 무관하게 도청을 원천 탐지할 수 있으나, 전용 광학 인프라와 거리 제한이 따른다. 두 기술의 조합은 QKD의 물리적 안전성과 PQC의 인프라 유연성을 동시에 활용하기 위함으로, 상호 약점을 보완하는 고보안 하이브리드 구조를 실현할 수 있다.