PQC(포스트양자암호) 기초: 양자 시대의 암호 보안

개념 소개

현재 인터넷 보안의 근간인 RSA와 타원곡선 암호(ECC)는 소인수분해 또는 이산로그 문제의 계산적 어려움에 의존한다. 고전 컴퓨터로는 수천 년이 걸릴 이 문제들을 충분히 큰 양자 컴퓨터는 **쇼어 알고리즘(Shor's Algorithm)**을 이용해 다항 시간 내에 풀 수 있다. 이 시나리오는 흔히 'Q-Day'라고 불린다.

**포스트양자암호(Post-Quantum Cryptography, PQC)**는 이 위협에 대응하기 위해 설계된 고전적 알고리즘 집합이다. 양자 컴퓨터를 포함한 어떤 컴퓨터로도 효율적으로 풀 수 없다고 여겨지는 수학적 난제를 보안의 근거로 삼는다. PQC는 양자 채널이 아닌 기존 통신 인프라 위에서 동작하므로, 양자역학적 원리로 키를 분배하는 QKD와는 근본적으로 다른 접근법이다.

---

핵심 원리

PQC의 보안성은 다음과 같은 수학적 난제 계열에 기반한다.

격자 기반 암호 (Lattice-Based Cryptography)

현재 가장 주목받는 방향으로, 최단 벡터 문제(SVP)와 최근 벡터 문제(CVP)의 어려움을 활용한다. 실용적 구현에는 LWE(Learning With Errors) 문제가 핵심으로 쓰인다.

비밀 벡터 $\mathbf{s}\in {\mathbb{Z}}_q^n$, 공개 행렬 $A\in {\mathbb{Z}}_q^{m\times n}$, 작은 오류 벡터 $\mathbf{e}$가 있을 때, 다음을 만족하는 $\mathbf{b}$로부터 $\mathbf{s}$를 복구하는 문제다:

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

오류 항 $\mathbf{e}$로 인해 연립방정식으로 직접 풀 수 없으며, 격자 축소 알고리즘으로도 $n$이 클 때 현실적인 시간 내에 풀리지 않는다. 이 어려움이 암호 체계의 안전성 근거가 된다.

해시 기반 암호 (Hash-Based Cryptography)

충돌 저항성이 있는 암호학적 해시 함수만을 기반으로 전자서명을 구성한다. 일회용 서명인 Lamport 서명을 일반화·트리 구조로 확장한 방식으로, 해시 함수의 안전성만 보장되면 전체 체계가 유지된다는 장점이 있다.

코드 기반 암호 (Code-Based Cryptography)

오류 정정 부호 이론에서 유도된 난제를 사용한다. 일반 선형 부호의 신드롬 디코딩 문제(Syndrome Decoding Problem)는 NP-완전으로 알려져 있어 고전·양자 컴퓨터 모두에 강인한 것으로 분석된다.

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

유한체 위의 다변수 이차 다항식 연립방정식을 푸는 것이 NP-완전임을 이용한다. 주로 전자서명 방식에 응용된다.

---

예시·응용

NIST PQC 표준

미국 국립표준기술연구소(NIST)는 장기간의 공개 검토 과정을 통해 PQC 표준 알고리즘을 확정했다.

표준 이름	기반 수학	주요 용도
ML-KEM (Kyber)	격자 (MLWE)	키 캡슐화(KEM)
ML-DSA (Dilithium)	격자 (MLWE)	전자서명
SLH-DSA (SPHINCS+)	해시 함수	전자서명
FN-DSA (FALCON)	격자 (NTRU)	전자서명

ML-KEM은 TLS 등 키 교환 프로토콜에, ML-DSA·SLH-DSA는 코드 서명·인증서 등에 우선 적용이 권장된다.

개념 데모: LWE 암호화 스케치

import numpy as np

def lwe_encrypt_demo(n=8, q=97, noise_bound=2):
    """LWE 기반 암호화의 개념적 데모 (실제 보안 파라미터 아님)"""
    # 비밀 키
    s = np.random.randint(0, q, size=n)
    # 공개 행렬 A
    A = np.random.randint(0, q, size=(2*n, n))
    # 작은 오류
    e = np.random.randint(-noise_bound, noise_bound + 1, size=2*n)
    # 공개키: b = A·s + e (mod q)
    b = (A @ s + e) % q

    # 1-bit 메시지 m 암호화
    m = 1
    r = np.random.randint(0, 2, size=2*n)  # 랜덤 부분집합 선택
    c1 = (r @ A) % q
    c2 = (int(r @ b) + m * (q // 2)) % q
    print(f"암호문 c2: {c2}")
    # 복호화: c2 - c1·s mod q ≈ m*(q//2)
    dec = (c2 - int(c1 @ s)) % q
    decoded = 1 if abs(dec - q // 2) < q // 4 else 0
    print(f"복호화 결과: {decoded} (원본: {m})")

lwe_encrypt_demo()

'Harvest Now, Decrypt Later' 위협

당장 충분한 양자 컴퓨터가 없더라도, 공격자는 현재 암호화된 트래픽을 대량 수집한 뒤 미래의 양자 컴퓨터로 복호화할 수 있다. 이 때문에 장기 기밀 데이터를 다루는 시스템은 지금부터 PQC로의 전환 계획을 수립해야 한다.

---

정리

PQC는 격자, 해시, 코드 등 다양한 수학적 난제를 기반으로 양자 컴퓨터의 공격에 대한 내성을 갖춘 암호 체계다. NIST의 표준화로 ML-KEM, ML-DSA 등 실용 알고리즘이 확정되어 현재 시스템에 단계적으로 통합되고 있다. PQC는 기존 인터넷 인프라와 호환되며, 양자키분배(QKD)와 함께 사용할 경우 수학적 가정과 물리적 보안을 동시에 제공하는 계층적 보안 구조를 구성할 수 있다.