PQC(포스트양자암호) 기초: 양자 위협에 대응하는 암호 체계
양자컴퓨터의 발전으로 RSA·ECC 등 기존 공개키 암호 체계가 쇼어 알고리즘에 의해 근본적으로 위협받고 있다. 포스트양자암호(PQC)는 양자컴퓨터로도 효율적으로 공격하기 어려운 수학 난제에 기반한 새로운 암호 패러다임이다. 기존 고전 통신 인프라 위에서 동작하므로 도입 장벽이 낮고, NIST 표준화를 통해 실용화 단계에 접어들었다.
개념 소개
현재 인터넷 보안의 근간인 공개키 암호는 두 가지 수학적 난제에 의존한다. RSA는 큰 수의 소인수분해의 어려움을, ECC(타원곡선 암호)는 이산 로그 문제의 어려움을 이용한다. 고전 컴퓨터로 2048비트 RSA를 인수분해하려면 현실적으로 불가능한 수준의 시간이 필요하다.
그러나 피터 쇼어(Peter Shor)가 제안한 쇼어 알고리즘은, 충분한 오류 정정 큐비트를 갖춘 양자컴퓨터라면 소인수분해와 이산 로그 문제를 다항 시간 내에 풀 수 있음을 보였다. 이는 현재의 RSA·ECC 기반 공개키 암호 전체가 강력한 양자컴퓨터 앞에서 무력화될 수 있음을 의미한다.
포스트양자암호(Post-Quantum Cryptography, PQC) 는 양자컴퓨터의 연산 능력으로도 효율적으로 공격하기 어렵다고 알려진 수학 문제에 기반한 암호 체계를 통칭한다. 양자 채널을 사용하는 양자키분배(QKD)와 달리, PQC는 기존 고전 통신 인프라 위에서 소프트웨어적으로 동작하므로 현실적 전환 비용이 낮다.
핵심 원리
PQC의 주요 접근법은 수학적 기반에 따라 아래와 같이 분류된다.
격자 기반 암호 (Lattice-based Cryptography)
현재 가장 활발히 연구·표준화된 분야다. 격자(lattice) 위에서의 계산 어려움에 근거하며, 핵심 난제는 LWE(Learning With Errors) 문제다.
비밀 벡터 , 무작위 행렬 , 작은 오차 벡터 에 대해
가 주어졌을 때, 오차 없이는 로부터 를 복구하는 것이 계산적으로 매우 어렵다. 비밀키 를 아는 정당한 수신자만 복호화가 가능하다.
해시 기반 암호 (Hash-based Cryptography)
단방향 해시 함수의 보안성만을 가정하며, 가정이 가장 단순하고 보수적인 방식이다. SPHINCS+가 대표적이며, 상태 없는(stateless) 전자서명을 지원한다.
코드 기반 암호 (Code-based Cryptography)
선형 오류 정정 부호의 복호화 어려움을 이용한다. McEliece 체계가 원조로, 수십 년간 양자 공격에 대한 저항성이 유지되고 있다.
다변수 다항식 기반 암호
다변수 연립방정식 풀기의 어려움(MQ 문제)을 이용하며, 서명 알고리즘에 주로 적용된다.
예시·응용
NIST PQC 표준 (2024년 최초 확정)
| 표준 명칭 | 기반 | 용도 |
|---|---|---|
| ML-KEM (Kyber) | 격자(Module-LWE) | 키 캡슐화(KEM) |
| ML-DSA (Dilithium) | 격자(Module-LWE) | 전자서명 |
| SLH-DSA (SPHINCS+) | 해시 | 전자서명 |
| FN-DSA (FALCON) | 격자(NTRU) | 전자서명 |
LWE 연산 단순 시뮬레이션
import numpy as np
q, n = 17, 4 # 소수 모듈러스, 차원
# 비밀 벡터 (작은 값)
s = np.array([1, 0, -1, 1])
# 무작위 공개 행렬 A
A = np.array([[3, 1, 4, 1],
[5, 9, 2, 6],
[5, 3, 5, 8]])
# 작은 오차 벡터 e
e = np.array([1, -1, 0])
# LWE 암호화: b = As + e (mod q)
b = (A @ s + e) % q
print("LWE 출력 b:", b)
# 비밀키 s 없이 b에서 s를 복구하는 것은 계산적으로 어렵다
하이브리드 전환 전략
전환 기간 동안 RSA/ECDH와 PQC 알고리즘을 병행(하이브리드)하는 방식이 권장된다. 두 알고리즘 중 하나라도 안전하면 전체 세션이 보호되므로, 아직 PQC 구현의 신뢰도가 완전히 검증되지 않은 상황에서도 기존 보안 수준을 유지할 수 있다. Google, Cloudflare 등은 이미 TLS 연결에 PQC 하이브리드 모드를 시험 적용 중이다.
정리
PQC는 양자컴퓨터의 암호 해독 위협에 대응하기 위해, 고전 컴퓨터와 양자컴퓨터 모두가 효율적으로 풀기 어렵다고 알려진 수학 문제를 기반으로 설계된 암호 체계다. 격자 기반(LWE), 해시 기반, 코드 기반 등 다양한 설계 원리가 존재하며, NIST 표준화를 통해 실용화가 본격화되고 있다. PQC는 QKD와 경쟁 관계가 아니라 상호 보완적 역할을 수행하며, 기존 인터넷 인프라 위에서 점진적 전환이 가능하다는 점이 핵심 장점이다.
연습문제
Q1.현재 RSA-2048 암호가 충분한 큐비트를 갖춘 양자컴퓨터에 의해 위협받는 이유를 쇼어 알고리즘과 연결지어 설명하라.
힌트 보기
RSA의 보안 근거가 무엇인지, 쇼어 알고리즘이 그 문제를 어떤 복잡도로 해결하는지 비교해 보라.
해설 보기
RSA의 보안은 큰 수의 소인수분해가 고전 컴퓨터로 지수적 시간이 걸린다는 사실에 근거한다. 그러나 쇼어 알고리즘은 양자 병렬성과 양자 푸리에 변환을 이용해 소인수분해를 $O((\log N)^3)$의 다항 시간 내에 수행할 수 있음을 보인다. 따라서 충분한 오류 정정 큐비트를 갖춘 양자컴퓨터가 실현되면 RSA-2048의 소인수분해가 현실적 시간 안에 가능해지며 기존 암호 체계의 보안 가정이 붕괴된다.
Q2.LWE 문제를 수식과 함께 설명하고, 이것이 암호에 활용되는 이유를 서술하라.
해설 보기
LWE 문제는 비밀 벡터 $\mathbf{s}$, 무작위 행렬 $A$, 작은 오차 벡터 $\mathbf{e}$에 대해 $\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod{q}$가 주어졌을 때 $\mathbf{s}$를 복구하는 것이 계산적으로 어렵다는 성질에 기반한다. 오차 $\mathbf{e}$가 없다면 연립방정식으로 $\mathbf{s}$를 쉽게 구할 수 있지만, 작은 무작위 오차가 더해지면 최단 벡터 문제(SVP)와 동등한 난이도를 가진다. 이 어려움은 고전 컴퓨터뿐 아니라 알려진 양자 알고리즘으로도 다항 시간 내 해결이 불가하므로 암호의 보안 근거로 적합하다.
Q3.PQC와 QKD(양자키분배)의 보안 근거와 적용 환경의 차이를 비교하라.
해설 보기
QKD는 양자역학의 물리 법칙(측정이 양자 상태를 교란함)을 보안 근거로 하며, 전용 양자 채널과 하드웨어가 필요하다. 반면 PQC는 수학적 계산 어려움을 보안 근거로 하며 기존 고전 통신 인프라 위에서 소프트웨어 업데이트만으로 전환이 가능하다. QKD는 정보이론적 안전성을 제공하지만 전송 거리와 인프라 비용에 제약이 있고, PQC는 계산 복잡도 기반이므로 미래의 수학적 돌파구가 발견될 경우 취약해질 수 있다. 두 기술은 서로 다른 위협 모델에 대응하므로 보완적으로 함께 활용하는 것이 이상적이다.