포스트양자암호(PQC)의 기초: 양자시대의 암호 재설계

개념 소개

현재 인터넷 보안의 근간을 이루는 RSA, 타원곡선암호(ECC) 같은 공개키 암호 체계는 정수 인수분해나 이산로그 문제의 계산적 난이도에 의존한다. 고전 컴퓨터로 이 문제들을 푸는 데 천문학적 시간이 걸리지만, 충분히 큰 양자컴퓨터에서 쇼어(Shor) 알고리즘을 실행하면 수 시간 내로 해독이 가능해진다.

이러한 위협에 대비하여 등장한 것이 **포스트양자암호(Post-Quantum Cryptography, PQC)**다. PQC는 양자컴퓨터는 물론 고전 컴퓨터로도 현실적 시간 내에 풀 수 없는 수학적 난제를 기반으로 설계된 암호 알고리즘군을 가리킨다. "양자암호(Quantum Cryptography)"가 양자역학 원리 자체(광자의 측정 불가역성 등)를 활용하는 것과 달리, PQC는 기존 하드웨어와 네트워크 위에서 소프트웨어만으로 배포·운용할 수 있다는 점이 실용상 핵심 이점이다.

---

핵심 원리

양자 위협의 두 축

쇼어 알고리즘은 $O((\log N{)}^3)$ 복잡도로 정수 인수분해를 수행하여 RSA-2048, ECDSA 등을 사실상 무력화한다. 한편 그로버(Grover) 알고리즘은 비정형 탐색을 $O(\sqrt{N})$ 복잡도로 수행하므로, 128비트 대칭키 암호(AES-128 등)의 실효 보안 강도를 64비트 수준으로 절반으로 낮춘다. 대칭키 암호는 키 길이를 두 배로 늘리는 방식(AES-256 사용)으로 대응 가능하지만, 공개키 암호는 알고리즘 자체를 교체해야 한다.

주요 PQC 기반 수학 난제

분류	핵심 난제	대표 알고리즘
격자(Lattice) 기반	SVP, LWE, MLWE	ML-KEM, ML-DSA, FALCON
해시(Hash) 기반	단방향 해시함수 충돌 저항	SPHINCS+ (SLH-DSA)
코드(Code) 기반	선형 디코딩 문제	Classic McEliece
다변수 다항식	MQ 문제	HQC

격자 기반 암호가 현재 가장 주목받는다. 그 중심에 있는 LWE(Learning With Errors) 문제는 다음과 같이 표현된다.

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

공개 행렬 $A$와 벡터 $\mathbf{b}$가 주어져도, 작은 오차 벡터 $\mathbf{e}$가 섞인 상태에서 비밀 벡터 $\mathbf{s}$를 복원하는 것은 양자컴퓨터로도 다항 시간 알고리즘이 알려져 있지 않다. 이 오차 항이 격자 구조를 교란하여 단순 선형대수 기법(예: 가우스 소거)의 적용을 막는다.

NIST 표준화

미국 국립표준기술연구소(NIST)는 2016년부터 PQC 표준화 공모를 진행하여 2024년 최초 세 종의 표준을 확정했다.

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

---

예시·응용

Open Quantum Safe(OQS) 라이브러리 활용 예시

liboqs 파이썬 바인딩을 이용한 ML-KEM-768 키 캡슐화 흐름이다.

import oqs  # pip install liboqs-python

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

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

    # 수신자: 비밀키로 공유 비밀 복원
    ss_receiver = receiver.decap_secret(ciphertext)

    assert ss_sender == ss_receiver  # 양측 동일한 공유 비밀 확보
    print("키 합의 성공:", ss_sender.hex()[:32], "...")

실전 적용 사례

• TLS 1.3 하이브리드 모드: 기존 ECDH와 ML-KEM을 병행 사용하여 전환기 보안을 확보한다. 두 메커니즘 중 하나라도 안전하면 공유 비밀이 보호된다.
• '지금 수집, 나중 해독(Harvest Now, Decrypt Later)' 위협: 공격자가 현재의 암호화 통신을 저장해 두었다가 미래의 양자컴퓨터로 해독하는 시나리오다. 장기 기밀 데이터를 다루는 시스템은 양자컴퓨터 실현 전에 PQC로 전환해야 한다.
• OpenSSH 9.0 이후: 격자 기반 키 교환(sntrup761)을 기본 지원하여 SSH 세션을 보호한다.

---

정리

PQC는 양자컴퓨터 시대에 대비한 고전 소프트웨어 기반의 암호 패러다임 전환이다. 격자·해시·코드 기반 등 다양한 수학적 난제를 활용하며, NIST가 2024년 ML-KEM, ML-DSA, SLH-DSA 세 표준을 확정함으로써 실용화 단계에 진입했다. 대칭키 암호는 키 길이 확장으로 그로버 위협에 대응 가능하지만, 공개키 알고리즘은 전면 교체가 불가피하다. 특히 장기 기밀성이 요구되는 시스템에서는 '지금 수집, 나중 해독' 공격에 대비해 즉각적인 전환 계획 수립이 권고된다.