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

먼저 읽으면 좋은 용어

개념 소개

현대 공개키 암호는 두 가지 수학적 난제에 의존한다. RSA는 정수 인수분해, 타원곡선 암호(ECC)는 이산 로그 문제를 안전성 근거로 삼는다. 고전 컴퓨터에서는 두 문제 모두 지수 시간이 필요하므로 사실상 해독이 불가능하다.

그러나 피터 쇼어(Peter Shor)가 제안한 쇼어 알고리즘은 충분한 큐비트를 갖춘 양자 컴퓨터에서 정수 인수분해를 $O ((lo g N)^{3})$ 다항 시간에 해결할 수 있음을 보였다. 이는 현재 인터넷 보안 기반 구조 전체를 위협하는 결과다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 이에 대응하기 위해, 양자 알고리즘으로도 효율적으로 풀기 어렵다고 알려진 수학적 구조를 기반으로 설계된 암호 방식이다. 고전 컴퓨터에서도 실행 가능하다는 점에서 양자키분배(QKD)와 본질적으로 다르다. QKD는 물리적 채널을 요구하는 반면, PQC는 기존 디지털 인프라 위에서 소프트웨어 업데이트만으로 배포할 수 있다.

핵심 원리

PQC의 보안 근거는 크게 네 가지 수학적 난제 계열로 분류된다.

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

고차원 격자에서 특정 벡터를 찾는 문제—최단 벡터 문제(SVP), 최근 벡터 문제(CVP)—는 양자 알고리즘으로도 지수 시간이 필요하다고 알려져 있다.

실용적 구현에서는 LWE(Learning With Errors) 문제가 핵심이다. 임의 행렬 $A \in Z_{q}^{m \times n}$ , 비밀 벡터 $s \in Z_{q}^{n}$ , 작은 오류 벡터 $e$ 에 대해

$b = As + e (mod q)$

주어진 $(A, b)$ 로부터 $s$ 를 복원하는 것이 어렵다는 가정에 기반한다. NIST 표준으로 선정된 CRYSTALS-Kyber(키 캡슐화)와 CRYSTALS-Dilithium(전자서명)이 이 계열에 속한다.

2. 코드 기반 암호 (Code-based)

선형 오류 정정 코드에서 신드롬 디코딩 문제를 안전성 근거로 삼는다. McEliece 암호 체계가 대표적이며, 가장 오랜 연구 역사를 갖는다. 그러나 공개키 크기가 수십~수백 KB에 달한다는 단점이 있다.

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

암호학적 해시 함수의 단방향성만을 보안 근거로 삼는다. 다른 수학적 가정이 없으므로 보수적 신뢰성이 높다. **SPHINCS+**가 NIST 표준으로 선정되었다.

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

유한체 위의 연립 다변수 다항 방정식 풀기(MQ 문제)가 NP-완전임을 이용한다. 서명 생성 속도가 빠르나 공개키 크기가 매우 크다.

예시·응용

NIST PQC 표준화 결과

NIST는 장기간의 공모·분석 과정을 거쳐 다음 알고리즘을 표준(FIPS 시리즈)으로 선정하였다.

용도	알고리즘(표준명)	기반 난제
키 캡슐화	ML-KEM (Kyber)	격자(모듈-LWE)
전자서명	ML-DSA (Dilithium)	격자(모듈-LWE)
전자서명	FN-DSA (FALCON)	격자(NTRU)
전자서명	SLH-DSA (SPHINCS+)	해시

Python 개념 예시: LWE 키 생성 흐름

# 실제 구현은 liboqs 등 검증된 라이브러리를 사용할 것
import numpy as np

def lwe_keygen(n=256, q=3329, sigma=1.0):
    """LWE 기반 공개키/비밀키 생성 (개념적 구현)"""
    A = np.random.randint(0, q, (n, n))            # 공개 행렬
    s = np.random.randint(0, 2, n)                 # 비밀키 (작은 값)
    e = np.round(np.random.normal(0, sigma, n)).astype(int)
    b = (A @ s + e) % q                            # 공개키 벡터
    pk, sk = (A, b), s
    return pk, sk

pk, sk = lwe_keygen()
# 복호화 시: A·s ≈ b 관계를 이용해 오류 e를 제거하고 메시지 복원

하이브리드 전환 전략

실제 시스템 전환에서는 기존 TLS 1.3에 PQC 알고리즘을 병렬로 추가하는 하이브리드 방식이 권장된다. 양자 컴퓨터 위협이 현실화되기 전까지 고전 암호와 PQC를 동시에 운용해 하위 호환성과 보안을 모두 확보하는 전략이다.

정리

PQC는 양자 컴퓨터 시대를 대비하는 소프트웨어 기반 암호 전환 전략이다. 격자·코드·해시·다변수 등 다양한 수학적 난제를 기반으로 하며, 현재는 격자 기반 알고리즘이 효율성과 보안성 면에서 주류를 이룬다. NIST 표준화 완료로 실제 인프라 도입이 본격화되고 있으며, 키 크기·연산 속도·보안 수준 사이의 트레이드오프가 실용적 구현의 핵심 과제다.

Exercises

연습문제

Q1RSA-2048이 충분한 큐비트를 가진 양자 컴퓨터에 취약한 이유를 쇼어 알고리즘과 연결하여 설명하시오.
힌트 보기
쇼어 알고리즘의 시간 복잡도와 고전 알고리즘의 시간 복잡도를 비교해 볼 것.
해설 보기
RSA의 안전성은 $N = p \times q$ 인수분해의 어려움에 기반한다. 고전 컴퓨터에서 최선의 알고리즘(일반 수체체)은 준지수 시간 $O(\exp(O((\log N)^{1/3}(\log\log N)^{2/3})))$이 걸린다. 반면 쇼어 알고리즘은 양자 푸리에 변환을 활용해 $O((\log N)^3)$ 다항 시간에 인수분해를 수행한다. 2048비트 키 기준으로도 이론적으로 수천~수백만 논리 큐비트면 해독 가능하므로, 결함 허용 양자 컴퓨터가 실현되면 RSA-2048은 안전하지 않다.
Q2LWE 문제에서 오류 벡터 $\mathbf{e}$의 역할은 무엇인가? $\mathbf{e} = \mathbf{0}$이라면 보안에 어떤 문제가 생기는가?
해설 보기
LWE 문제에서 $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}$의 오류 $\mathbf{e}$는 단순 선형 방정식이 되지 않도록 하는 핵심 장치다. $\mathbf{e} = \mathbf{0}$이면 $\mathbf{b} = \mathbf{A}\mathbf{s}$가 되어 가우스 소거법(Gaussian elimination)으로 $O(n^3)$ 시간 안에 비밀키 $\mathbf{s}$를 바로 복원할 수 있다. 오류가 작게 도입됨으로써 역행렬 계산이 불가능해지고, 문제가 NP-hard로 알려진 최근 벡터 문제(CVP)와 동등한 난이도를 갖게 된다.
Q3PQC와 QKD의 근본적인 차이를 보안 근거와 배포 방식 측면에서 비교하시오.
해설 보기
QKD는 양자역학의 측정 불교란 원리(측정 시 상태 붕괴)를 보안 근거로 삼으며, 광섬유 또는 자유공간 양자 채널을 통해 광자를 물리적으로 전송해야 한다. 보안이 물리 법칙에 기반하므로 정보 이론적 안전성을 갖지만, 전용 하드웨어와 인프라가 필요하다. 반면 PQC는 수학적 난제(격자, 코드 등)의 계산 복잡도를 보안 근거로 삼으며, 기존 인터넷·소프트웨어 인프라 위에서 알고리즘 교체만으로 배포할 수 있다. 다만 미래에 해당 수학 문제가 효율적으로 풀릴 가능성이 배제되지 않는다는 점에서 계산적 안전성에 머문다.