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

개념 소개

오늘날 인터넷 보안의 근간인 RSA와 타원곡선 암호(ECC)는 대형 정수의 소인수분해 또는 이산 로그 문제의 계산적 난이도에 의존한다. 고전 컴퓨터로는 수백 비트 크기의 이 문제를 풀려면 우주 나이보다 긴 시간이 걸린다.

그러나 양자 컴퓨터가 실용 규모로 구현된다면, 쇼어(Shor) 알고리즘이 다항 시간 안에 소인수분해와 이산 로그를 해결해 기존 공개키 암호를 무력화한다. 이에 대한 해법으로 등장한 것이 **포스트양자암호(Post-Quantum Cryptography, PQC)**다. PQC는 양자 컴퓨터 환경에서도 고전 컴퓨터 위에서 실행되면서 안전성을 유지하도록 설계된 암호 알고리즘이다. 즉, 양자 컴퓨터를 사용하는 것이 아니라 양자 컴퓨터의 공격을 버티도록 만든 고전 알고리즘이다.

---

핵심 원리

양자 알고리즘의 위협 정도

공격 알고리즘	대상	영향
쇼어 알고리즘	RSA, ECC, DH	완전 파괴
그로버(Grover) 알고리즘	AES 등 대칭키	유효 키 길이 절반 감소

그로버 알고리즘은 $N$개의 후보 중 답을 $O(\sqrt{N})$ 연산으로 찾으므로, AES-128의 보안 강도가 약 64비트 수준으로 낮아진다. 대칭키 암호는 키 길이를 두 배로 늘리는 것으로 대응 가능하지만, 공개키 암호는 근본적 교체가 필요하다.

PQC의 수학적 기반

PQC 알고리즘은 다음과 같은 양자 컴퓨터로도 효율적으로 풀기 어려운 문제들을 기반으로 한다.

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

가장 활발히 연구되는 분야로, LWE(Learning With Errors) 문제가 핵심이다.

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

여기서 $\mathbf{A}$는 공개 행렬, $\mathbf{s}$는 비밀 벡터, $\mathbf{e}$는 작은 오류 벡터다. 공격자가 $\mathbf{A}$와 $\mathbf{b}$만 알 때 $\mathbf{s}$를 복원하는 것이 계산적으로 어렵다는 성질을 활용한다. 이 문제는 최단 벡터 문제(SVP)의 어려움에 환원되며, 현재 알려진 양자 알고리즘으로도 지수 시간이 필요하다.

2. 해시 기반 암호 (Hash-based)

일방향 해시 함수의 난이도만을 가정하므로 안전성 근거가 가장 단순하다. 주로 디지털 서명에 사용된다 (예: SPHINCS+).

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

오류 정정 부호에서 신드롬 디코딩 문제의 NP-난이도를 활용한다. 역사가 길어 신뢰도가 높으나 키 크기가 크다.

4. 다변수 다항식 기반 (Multivariate)

유한체 위의 다변수 2차 방정식 계의 해를 구하는 MQ 문제를 기반으로 한다.

---

예시·응용

NIST PQC 표준화

미국 국립표준기술연구소(NIST)는 2016년부터 PQC 표준화 공모를 진행해 왔으며, 최종적으로 다음 알고리즘들을 표준으로 선정했다.

알고리즘	용도	기반 문제
ML-KEM (Kyber)	키 캡슐화(KEM)	격자 (Module-LWE)
ML-DSA (Dilithium)	디지털 서명	격자 (Module-LWE/SIS)
SLH-DSA (SPHINCS+)	디지털 서명	해시 함수
FN-DSA (FALCON)	디지털 서명	격자 (NTRU)

하이브리드 접근법

현재 전환 기간에는 기존 알고리즘과 PQC를 병렬로 사용하는 하이브리드(hybrid) 방식이 권장된다. TLS 핸드셰이크에서 X25519(ECC)와 ML-KEM을 동시에 사용하면, 어느 한쪽이 안전한 한 전체 세션이 보호된다.

# 개념 예시: LWE 기반 암호화 간략 구현 (교육 목적)
import numpy as np

def lwe_keygen(n=256, q=3329):
    """ML-KEM에서 영감을 받은 단순화된 LWE 키 생성"""
    A = np.random.randint(0, q, size=(n, n))
    s = np.random.randint(0, 3, size=n) - 1  # 비밀 벡터 (작은 값)
    e = np.random.randint(0, 3, size=n) - 1  # 오류 벡터 (작은 값)
    b = (A @ s + e) % q                       # 공개키 일부
    return (A, b), s  # (공개키, 비밀키)

pub, sec = lwe_keygen()
print("공개키 A 크기:", pub[0].shape)
print("비밀 벡터 s (처음 5개):", sec[:5])

현실 보안 고려사항

"지금 수집, 나중에 복호화(Harvest Now, Decrypt Later)" 공격에 주의해야 한다. 공격자가 현재 암호화된 트래픽을 저장해 두었다가, 미래 양자 컴퓨터로 복호화할 수 있으므로, 장기 기밀 데이터는 지금 당장 PQC로 전환할 필요가 있다.

---

정리

PQC는 양자 컴퓨터의 연산 능력에도 안전성을 유지할 수 있도록 격자, 해시, 코드 등 다양한 수학적 난제를 기반으로 설계된 암호 알고리즘 집합이다. 쇼어 알고리즘에 의한 공개키 암호의 붕괴 위협에 대응하며, NIST 표준화 완료로 실용화 단계에 접어들었다. 기존 인프라와의 하이브리드 적용이 현실적인 전환 경로이며, 데이터의 장기 기밀성을 고려할 때 조기 전환이 권장된다.