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

개념 소개

현대 인터넷 보안의 근간을 이루는 RSA와 타원곡선암호(ECC)는 소인수분해와 이산로그 문제의 어려움에 의존한다. 충분히 큰 두 소수의 곱에서 원래 소수를 역산하는 일이 고전 컴퓨터로는 사실상 불가능하다는 전제가 바탕이다.

그러나 **쇼어 알고리즘(Shor's algorithm)**은 양자컴퓨터를 이용해 소인수분해와 이산로그 문제를 다항 시간 내에 풀 수 있음을 이론적으로 보였다. 충분히 강력한 양자컴퓨터가 실현되는 순간, 현재의 공개키 암호 체계 전체가 붕괴할 수 있다.

대칭키 암호 역시 안전하지만은 않다. **그로버 알고리즘(Grover's algorithm)**은 비정렬 데이터베이스 탐색을 $O(\sqrt{N})$ 복잡도로 수행해, AES-128과 같은 대칭키 암호의 유효 보안 강도를 절반으로 줄인다. 즉 양자 공격자에게 AES-128은 AES-64 수준의 보안만을 제공하게 된다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 이러한 양자 공격에도 안전하도록 설계된 새로운 암호 알고리즘 체계를 말한다. 양자 하드웨어 없이 고전 컴퓨터에서 동작하면서도 양자 공격에 견딘다는 점에서, 양자 채널을 활용하는 양자키분배(QKD)와 구별된다.

---

핵심 원리

PQC 알고리즘은 양자컴퓨터도 효율적으로 풀 수 없다고 알려진 수학적 난제를 기반으로 분류된다.

1. 격자 기반 암호 (Lattice-based Cryptography)

현재 가장 활발히 연구되는 분야로, **격자 위의 오류 학습 문제(LWE, Learning With Errors)**의 어려움에 의존한다.

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

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

형태의 샘플 $(A,\mathbf{b})$만으로 $\mathbf{s}$를 복원하는 문제가 LWE다. 양자 알고리즘으로도 지수 시간이 소요된다고 알려져 있으며, 보안 증명을 최단 벡터 문제(SVP)라는 격자 난제로 환원할 수 있다.

2. 해시 기반 서명 (Hash-based Signatures)

단방향 해시 함수의 보안성에만 의존한다. 가정이 최소화되어 이론적 신뢰도가 높고, XMSS·SPHINCS+ 등이 대표적이다. 단, 서명 크기가 상대적으로 크다.

3. 부호 기반 암호 (Code-based Cryptography)

일반적인 선형 부호 복호화 문제(신드롬 복호화 문제)의 어려움을 이용한다. McEliece 암호가 고전적 사례로, 1978년 제안 이후 수십 년간 공격이 없어 보안 신뢰성이 높다. 다만 공개키 크기가 매우 크다는 단점이 있다.

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

유한체 위에서 다변수 이차 다항식 연립방정식의 해를 구하는 MQ 문제의 어려움에 기반한다. 주로 전자서명 용도로 사용된다.

---

예시·응용

NIST PQC 표준화

미국 NIST는 2016년부터 PQC 표준화 공모를 진행하였고, 다음 알고리즘들을 표준으로 선정하였다.

알고리즘(공식 명칭)	원래 이름	유형	용도
ML-KEM	Kyber	격자 기반	키 캡슐화(KEM)
ML-DSA	Dilithium	격자 기반	전자서명
SLH-DSA	SPHINCS+	해시 기반	전자서명
FN-DSA	FALCON	격자 기반	전자서명

하이브리드 운용

현실적 전환 전략으로 기존 알고리즘과 PQC를 병렬로 사용하는 하이브리드 방식이 권장된다. 두 키 교환 결과를 키 유도 함수(KDF)로 결합함으로써, 어느 한 쪽이 안전하다면 전체 세션도 안전함이 보장된다.

# 개념적 의사코드: 하이브리드 키 교환
def hybrid_key_exchange(peer_ecdh_pub, peer_pqc_pub):
    # 고전 ECDH 키 교환
    ecdh_shared = ecdh_key_exchange(peer_ecdh_pub)

    # PQC(ML-KEM) 키 캡슐화
    pqc_shared, ciphertext = ml_kem_encapsulate(peer_pqc_pub)

    # 두 공유 비밀을 결합해 세션 키 생성
    session_key = kdf(ecdh_shared + pqc_shared)
    return session_key, ciphertext

지금 수집, 나중에 복호화 (Harvest Now, Decrypt Later)

현재 암호화된 트래픽을 저장해 두었다가 미래의 강력한 양자컴퓨터로 복호화하는 공격 시나리오다. 장기 기밀을 다루는 시스템—정부 문서, 의료 기록, 금융 데이터—은 PQC로의 조기 전환이 권고된다.

---

정리

포스트양자암호는 쇼어 알고리즘과 그로버 알고리즘으로 대표되는 양자 위협에 대응하기 위해 설계된 차세대 암호 기술이다. 격자 기반(LWE), 해시 기반, 부호 기반 등 다양한 수학적 난제를 토대로 하며, NIST 표준화를 통해 ML-KEM·ML-DSA 등이 실용 단계에 진입했다. 현재는 기존 시스템과의 하이브리드 운용을 통한 점진적 전환이 현실적인 보안 전략으로 권장된다.