양자내성암호(Post-Quantum Cryptography, PQC)
1. 개요
가. 정의
양자내성암호(PQC)는 대규모 범용 양자컴퓨터가 등장하더라도 안전성이 유지되도록, 격자·부호·해시·다변수 등 양자 알고리즘으로 효율적으로 풀리지 않는 수학 문제에 기반해 설계한 공개키 암호·전자서명 알고리즘의 총칭이다. 기존 디지털 컴퓨터(고전 컴퓨터) 위에서 그대로 동작한다는 점에서, 양자 물리 현상으로 키를 분배하는 양자키분배(QKD)와는 근본적으로 다르다.
오늘날 인터넷의 신뢰는 RSA와 타원곡선암호(ECC)에 깊이 의존한다. TLS의 키 교환, 전자서명과 인증서(PKI), 코드 서명, 블록체인의 지갑 서명이 모두 "큰 수의 소인수분해"나 "이산대수 문제"가 현실적인 시간 안에 풀리지 않는다는 가정 위에 서 있다. 그러나 1994년 쇼어(Shor) 알고리즘은 충분히 큰 결함허용(fault-tolerant) 양자컴퓨터가 있으면 이 두 문제를 다항시간에 풀 수 있음을 보였다. 즉 양자컴퓨터는 RSA·ECC를 사실상 무력화한다. 양자내성암호는 이 위협에 맞서, 고전 암호의 운영 체계는 유지하되 수학적 기반 자체를 양자 공격에 견디는 문제로 교체하려는 접근이다.
나. 등장 배경 및 필요성
양자내성암호가 "미래의 대비책"이 아니라 "지금 당장의 과제"가 된 결정적 이유는 하베스트 나우, 디크립트 레이터(Harvest Now, Decrypt Later, HNDL) 위협 때문이다. 공격자는 아직 양자컴퓨터가 없더라도, 지금 네트워크를 흐르는 암호문을 그대로 수집·저장해 두었다가 훗날 양자컴퓨터가 완성되면 복호화할 수 있다. 따라서 "보호 기간이 긴 데이터"(국가기밀·의료기록·금융거래·지식재산)는 양자컴퓨터가 나오기 전에 이미 위험에 노출되어 있는 셈이다. 보호 필요 기간(X) + 전환 소요 기간(Y)이 양자컴퓨터 등장 시점(Z)보다 크면 위험하다는 모스카(Mosca)의 부등식(X+Y>Z)이 이 긴급성을 압축적으로 설명한다.
대칭키 암호와 해시는 사정이 다르다. 그로버(Grover) 알고리즘은 탐색 문제에 제곱근 수준의 가속만 주므로, AES-128의 실효 강도는 약 64비트로 떨어지지만 AES-256을 쓰면 여전히 안전하고, 해시도 출력 길이를 늘리면 대응된다. 반면 공개키 암호는 쇼어 알고리즘에 지수적으로 붕괴하므로 대체 외에는 길이 조정으로 버틸 수 없다. 이 비대칭성이 "공개키 체계(키 교환·전자서명)를 먼저, 전면적으로 교체해야 한다"는 PQC의 핵심 과제로 이어진다.
제도적으로도 전환은 이미 시작되었다. 미국 NIST는 2016년부터 공개 공모 방식의 표준화를 진행해 2024년 8월 최초의 표준을 확정했고, 미국 NSA의 CNSA 2.0은 2035년 전후를 목표로 국가안보시스템의 PQC 전면 적용 일정을 제시했다. 우리나라도 국가정보원 주도로 2035년까지 국가 암호체계를 양자내성암호로 전환하는 마스터플랜(2023.7)을 발표하고, 한국형 공모전(KpqC)으로 자체 알고리즘을 확보하고 있다. 요컨대 PQC는 "언젠가의 기술"이 아니라 지금 이행 계획을 세워야 하는 규제·운영상의 현안이다.
다. 특징
- 고전 하드웨어 호환: 양자컴퓨터 없이 기존 CPU에서 동작하며, 기존 PKI·TLS 운영 모델을 대체로 재사용한다.
- 수학 기반의 다양화: 격자·부호·해시·다변수·아이소제니 등 서로 다른 난제에 분산 투자해 특정 문제가 깨져도 대안을 남긴다.
- 크기·성능 트레이드오프: 기존 RSA·ECC보다 공개키·서명·암호문 크기가 크고(수백 B~수 KB 이상), 대역폭·메모리 제약 환경에서 부담이 된다.
- 크립토 애자일 요구: 알고리즘 교체가 쉬운 구조(crypto-agility)와 하이브리드 전환이 사실상 필수다.
2. PQC의 분류 체계와 전체 구조
양자내성암호는 "어떤 수학 난제에 안전성을 거는가"에 따라 계열이 나뉜다. 아래 구조도는 대표 계열과 NIST가 표준으로 채택했거나 탈락시킨 알고리즘을 함께 정리한 것이다.
flowchart TB
PQC["양자내성암호(PQC)"] --> L["격자 기반(Lattice)"]
PQC --> C["부호 기반(Code)"]
PQC --> H["해시 기반(Hash)"]
PQC --> M["다변수 기반(Multivariate)"]
PQC --> I["아이소제니(Isogeny)"]
L --> LK["ML-KEM(Kyber) · 키설정"]
L --> LS["ML-DSA(Dilithium) · 서명"]
L --> LF["FN-DSA(Falcon) · 서명"]
C --> CM["Classic McEliece"]
C --> CH["HQC(백업 KEM, 2025 선정)"]
H --> HS["SLH-DSA(SPHINCS+) · 서명"]
M --> MR["Rainbow(2022 공격으로 탈락)"]
I --> IS["SIKE(2022 공격으로 탈락)"]
style PQC fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style L fill:#e9f8ee,stroke:#1f9d55,stroke-width:1px
style M fill:#fdecec,stroke:#d64545,stroke-width:1px
style I fill:#fdecec,stroke:#d64545,stroke-width:1px
격자 기반(Lattice-based) 암호는 현재 PQC의 주류다. 격자에서 "가장 가까운 벡터 찾기(CVP)"나 그 변형인 LWE(Learning With Errors)·Module-LWE 문제가 양자·고전 모두에서 어렵다는 가정에 기반한다. 연산이 주로 다항식 곱과 모듈러 덧셈이라 구현이 비교적 빠르고 키·암호문 크기가 균형을 이루기 때문에, NIST가 키설정(ML-KEM)과 서명(ML-DSA·FN-DSA)의 주력으로 모두 격자 계열을 택했다. 다만 모든 핵심 알고리즘을 한 계열에 집중하면 "그 난제가 깨지면 동시다발로 무너진다"는 단일 실패점 우려가 있어, 백업 계열의 병행이 중요해진다.
부호 기반(Code-based) 암호는 "오류정정부호의 복호화가 일반적으로 NP-난해"라는 사실을 이용한다. 1978년 맥엘리스(McEliece) 암호로 거슬러 올라갈 만큼 역사가 길어 안전성 신뢰가 높다는 장점이 있으나, 공개키가 수십만 바이트에 달해 실무 적용이 까다롭다. NIST가 2025년 3월 HQC를 ML-KEM의 백업으로 추가 선정한 것은, 주력(격자)과 다른 수학적 토대를 확보해 위험을 분산하려는 의도다. 해시 기반(Hash-based) 서명(SLH-DSA, XMSS, LMS)은 해시 함수의 안전성만 가정하므로 가장 보수적으로 안전하지만 서명이 크고 느리다. 반면 다변수(Rainbow)와 아이소제니(SIKE) 계열은 각각 2022년에 치명적 공격이 발표되어 사실상 탈락했는데, 이는 "새 수학 난제는 충분한 공개 검증을 거치기 전까지 섣불리 신뢰할 수 없다"는 PQC 특유의 리스크를 상징한다.
| 계열 | 대표 난제 | 표준/대표 알고리즘 | 강점 | 약점 |
|---|---|---|---|---|
| 격자 | Module-LWE/LWR, NTRU | ML-KEM, ML-DSA, FN-DSA | 속도·크기 균형, 범용성 | 비교적 최신, 단일 집중 위험 |
| 부호 | 신드롬 복호화 | Classic McEliece, HQC | 오랜 검증, 높은 신뢰 | 큰 공개키 |
| 해시 | 해시 충돌 저항성 | SLH-DSA, XMSS/LMS | 가장 보수적 안전성 | 큰 서명, 상태관리(stateful) |
| 다변수 | MQ 문제 | (Rainbow — 탈락) | 짧은 서명 | 안전성 붕괴 사례 |
| 아이소제니 | 초특이 아이소제니 | (SIKE — 탈락) | 매우 작은 키 | 2022년 공격으로 파기 |
3. NIST 표준과 알고리즘 구성
NIST는 2016년 공모를 시작해 70여 종 후보를 수차례 라운드로 좁혔고, 2024년 8월 13일 최초의 PQC 표준 세 건을 공식 발표했다. 이 표준들은 이전 후보명(Kyber·Dilithium·SPHINCS+)에서 표준 명칭(ML-KEM·ML-DSA·SLH-DSA)으로 바뀌었다는 점을 답안에서 정확히 구분해야 한다.
| 표준 | 알고리즘(원 후보) | 용도 | 계열 | 상태 |
|---|---|---|---|---|
| FIPS 203 | ML-KEM(CRYSTALS-Kyber) | 키 캡슐화(KEM, 키설정) | 격자 | 2024.8 확정 |
| FIPS 204 | ML-DSA(CRYSTALS-Dilithium) | 전자서명(주력) | 격자 | 2024.8 확정 |
| FIPS 205 | SLH-DSA(SPHINCS+) | 전자서명(해시 기반 백업) | 해시 | 2024.8 확정 |
| FIPS 206 | FN-DSA(Falcon) | 전자서명(소형 서명) | 격자 | 개발 중(초안 단계) |
| (예정) | HQC | 키 캡슐화 백업 | 부호 | 2025.3 선정, 표준화 진행 |
각 알고리즘은 보안강도에 따라 여러 파라미터셋을 제공한다. 예컨대 ML-KEM은 ML-KEM-512·768·1024를 두어 각각 AES-128·192·256에 상응하는 강도를 목표로 하며, 숫자가 클수록 안전하지만 공개키·암호문이 커진다. 실무에서는 "보호 기간과 위협 수준에 맞춰 과도하지도 부족하지도 않은 파라미터"를 고르는 것이 비용·보안의 균형점이며, 구글·클라우드플레어의 하이브리드 TLS 배포가 ML-KEM-768을 기본값으로 택한 것도 이런 절충의 결과다. 보안강도 레벨(NIST Level 1/3/5)과 파라미터셋의 대응 관계를 혼동하지 않는 것이 답안에서 중요하다.
세 표준의 역할 분담에는 분명한 설계 의도가 있다. ML-KEM은 TLS처럼 "통신 세션 키를 상대와 안전하게 합의"하는 키 캡슐화 메커니즘(KEM)으로, 과거 RSA/ECDH 키 교환을 대체한다. KEM은 송신자가 공개키로 대칭키를 캡슐화해 보내고 수신자가 개인키로 꺼내는 방식으로, 쇼어 알고리즘에 취약한 디피-헬먼류 키 교환을 격자 난제로 치환한다. ML-DSA는 범용 전자서명의 기본값이며, FN-DSA(Falcon)는 서명 길이가 짧아 대역폭이 중요한 곳에, SLH-DSA는 격자가 아닌 해시에 안전성을 거는 보수적 백업으로 포지셔닝된다. 즉 "서명은 격자(ML-DSA)를 기본으로 하되, 격자가 흔들릴 경우를 대비해 해시(SLH-DSA)를 남겨 둔다"는 다계열 분산 전략이 표준 구성 자체에 녹아 있다.
4. 전환(마이그레이션) 절차와 하이브리드 방식
PQC 전환의 실무 핵심은 "한 번에 교체"가 아니라 점진적·하이브리드 전환이다. 아래 다이어그램은 조직이 거치는 전환 단계와, TLS에서 널리 쓰이는 하이브리드 키 교환의 흐름을 함께 보여 준다.
flowchart LR
subgraph MIG["전환 로드맵"]
A["1.암호 인벤토리<br/>(어디서 무엇을 쓰는가)"] --> B["2.위험 우선순위화<br/>(보호기간·민감도)"]
B --> C["3.크립토 애자일 확보<br/>(교체 가능한 구조)"]
C --> D["4.하이브리드 적용"]
D --> E["5.순수 PQC 전환"]
end
subgraph HYB["하이브리드 키 교환(TLS)"]
CH["ClientHello: X25519 + ML-KEM"] --> SH["ServerHello: 두 공유키 생성"]
SH --> KDF["두 공유비밀 결합(KDF)"]
KDF --> KEY["세션키 확정"]
end
E -.참조.-> HYB
style A fill:#e8f0fe,stroke:#2f6fed,stroke-width:1px
style KEY fill:#e9f8ee,stroke:#1f9d55,stroke-width:1px
전환의 출발점은 역설적으로 암호 그 자체가 아니라 가시성이다. 대부분의 조직은 자신이 "어디서, 어떤 알고리즘·키 길이·인증서를, 어떤 수명으로" 쓰는지 정확히 모른다. 따라서 암호 인벤토리와 CBOM(Cryptographic Bill of Materials)을 통해 사용 현황을 식별하고, 보호 기간이 길고 민감한 자산(장기 보존 문서, 코드 서명 루트키, 금융 거래)부터 우선순위를 매긴다. 이 단계 없이 알고리즘만 교체하면, 임베디드 장비 펌웨어나 외주 라이브러리 깊숙이 박힌 RSA가 그대로 남아 전환이 "구멍 뚫린 상태"가 된다.
다음으로 크립토 애자일(crypto-agility), 즉 알고리즘을 설정으로 쉽게 바꿀 수 있는 구조를 확보한 뒤 하이브리드 방식을 적용한다. 하이브리드는 기존 알고리즘(예: X25519)과 PQC(예: ML-KEM-768)를 동시에 수행해 두 공유비밀을 KDF로 결합하는 방식으로, "둘 중 하나만 깨지지 않으면 안전"하다. 실제로 구글 크롬과 클라우드플레어는 2023~2024년 TLS 1.3에 X25519+ML-KEM 하이브리드를 대규모로 적용했는데, 이는 PQC 알고리즘의 구현 결함이나 아직 드러나지 않은 취약점 위험을 기존 검증된 알고리즘으로 보험 처리하려는 현실적 선택이다. 전환의 마지막 단계에서야 순수 PQC로 넘어간다.
5. 기존 공개키·QKD와의 비교
PQC의 위치를 정확히 이해하려면 두 축의 비교가 필요하다. 첫째는 "무엇을 대체하는가"(기존 RSA/ECC 대비), 둘째는 "흔히 혼동되는 양자키분배(QKD)와 무엇이 다른가"이다. 특히 시험 답안에서 PQC와 QKD를 같은 것으로 서술하면 감점 요인이 되므로 그 차이의 이유까지 설명할 수 있어야 한다.
| 구분 | RSA-2048/ECC | PQC(ML-KEM 등) | QKD(양자키분배) |
|---|---|---|---|
| 안전성 근거 | 소인수분해·이산대수 | 양자 난공 수학 문제 | 양자역학(측정 교란) |
| 양자컴퓨터 내성 | 없음(쇼어에 붕괴) | 있음 | 있음 |
| 동작 기반 | 고전 컴퓨터 | 고전 컴퓨터 | 전용 양자 하드웨어·광통신 |
| 키/서명 크기 | 작음(수백 B) | 큼(수 KB) | 해당 없음(키만 분배) |
| 거리·인프라 | 인터넷 전역 | 인터넷 전역(SW 교체) | 거리 제한·전용망 필요 |
| 전자서명 지원 | 지원 | 지원 | 미지원(키분배 전용) |
기존 RSA/ECC 대비 PQC의 본질적 차이는 안전성의 근거를 바꾼다는 데 있다. RSA는 소인수분해가, ECC는 타원곡선 이산대수가 어렵다는 가정에 서 있지만 둘 다 쇼어 알고리즘에 다항시간으로 붕괴한다. PQC는 소프트웨어만 교체하면 기존 인터넷·PKI 위에서 그대로 쓸 수 있다는 운영상의 연속성이 가장 큰 강점이다. 대신 키·서명·암호문이 커지는 대가가 따른다. 예컨대 ECDSA 서명이 64바이트 수준인 데 비해 ML-DSA 서명은 2KB를 넘고, SLH-DSA는 수 KB~수십 KB에 이른다. 이 크기 증가는 인증서 체인이 긴 TLS 핸드셰이크나 IoT 펌웨어 서명처럼 대역폭·저장공간이 빠듯한 환경에서 실질적 병목이 된다.
QKD와의 차이는 더 근본적이다. QKD는 광자의 측정이 상태를 교란한다는 물리 법칙으로 도청을 탐지하며 키를 분배하지만, 전용 양자 하드웨어와 광통신 인프라가 필요하고 거리 제약이 크며 전자서명을 제공하지 못한다. 반면 PQC는 순수 소프트웨어로 인터넷 전역에서 동작하고 서명·인증까지 포괄한다. 이 때문에 각국 보안기관(미국 NSA 등)은 "범용 보안 체계의 중심은 QKD가 아니라 PQC"라는 입장을 명확히 해 왔다. 둘은 경쟁 관계라기보다, QKD가 특수 고보안 구간에 보조적으로 쓰일 수 있는 상호 보완 관계로 보는 것이 정확하다.
6. 심화 — 국내외 표준화 동향과 KpqC
표준화의 글로벌 지형은 2024~2025년을 기점으로 "선정"에서 "이행"으로 무게중심이 옮겨 갔다. NIST가 2024년 8월 FIPS 203/204/205를 확정한 데 이어 2025년 3월 11일 HQC를 다섯 번째 알고리즘(부호 기반 백업 KEM)으로 선정했고, FN-DSA(Falcon) 표준(FIPS 206)은 개발 중이다. 이는 "격자 주력 + 이종 계열 백업"이라는 분산 철학이 표준 수준에서 굳어졌음을 보여 준다. 산업계에서도 OpenSSL·BoringSSL·liboqs 같은 라이브러리가 ML-KEM/ML-DSA를 탑재했고, 애플은 iMessage에 PQ3라는 PQC 기반 프로토콜을 도입하는 등 적용이 가속되고 있다.
국내는 국가정보원 주도의 KpqC(한국형 양자내성암호) 공모전을 통해 자체 알고리즘을 확보했다. 2021년 11월 공모를 시작해 2022년 16종을 접수, 2023년 11월 1라운드에서 8종을 추렸고, 2025년 1월 최종 4종을 확정했다. 확정 알고리즘은 전자서명 2종(AIMer, HAETAE)과 공개키암호·키설정 2종(NTRU+, SMAUG-T)으로 알려져 있다. 특히 AIMer 전자서명 기술은 국내 기업(삼성SDS)이 관여해 채택된 사례로 소개되었다. 다만 세부 규격·명칭·일정은 공모전 진행에 따라 갱신될 수 있으므로, 실제 적용 시에는 국정원·양자내성암호연구단의 공식 규격서를 확인하는 것이 안전하다.
표준화 주체도 NIST에 국한되지 않는다. 키 교환·서명을 실제 프로토콜에 녹이는 작업은 IETF가 TLS 1.3 하이브리드, X.509 인증서, SSH 등에 대한 규격으로 진행하고, 유럽 ETSI와 국제 ISO/IEC JTC1 SC27도 PQC 관련 표준화를 병행한다. 즉 "알고리즘 표준(NIST)"과 "프로토콜·운영 표준(IETF·ETSI·ISO)"이 서로 다른 층위에서 맞물려 돌아가며, 실제 제품에 적용하려면 두 층위를 모두 추적해야 한다. 국내에서도 KpqC 알고리즘을 TTA 단체표준과 국가표준으로 반영하고, 암호모듈 검증제도(KCMVP)와의 정합을 맞추는 후속 작업이 전환의 실효성을 좌우한다.
정책 측면에서 우리나라는 2023년 7월 2035년까지 국가 암호체계를 PQC로 전환하는 마스터플랜을 발표했고, 이후 종합 추진계획을 통해 공공·금융·국방 등 분야별 전환 로드맵을 구체화하고 있다. 이는 미국 CNSA 2.0이 제시한 2035년 전후 전면 전환 일정과 궤를 같이한다. 정보관리기술사 관점에서 보면, PQC는 단순 암호 기술 문제가 아니라 국가·기업 수준의 다년 전환 프로그램으로서 거버넌스·예산·조달·인력 문제를 동반하는 과제로 출제될 가능성이 높다.
7. 고려사항 및 시사점
단일 계열 집중 리스크와 분산 전략: 주력 표준이 모두 격자 계열이라는 점은 효율과 일관성을 주지만, 격자 난제에 근본적 돌파구가 나올 경우 동시 붕괴 위험이 있다. 따라서 해시(SLH-DSA)·부호(HQC) 백업을 함께 지원하는 다계열 준비와, 알고리즘을 설정으로 교체 가능한 크립토 애자일 아키텍처가 전략적 필수다.
성능·크기 트레이드오프 관리: PQC는 키·서명·암호문이 커서 TLS 핸드셰이크 지연, 인증서 체인 팽창, IoT·스마트카드 등 제약 장비의 메모리 부담을 유발한다. 적용 전 대역폭·레이턴시·전력 영향을 측정하고, 파라미터셋(예: ML-KEM-512/768/1024) 선택으로 보안강도와 비용을 균형 있게 조정해야 한다.
하이브리드와 점진 전환의 불가피성: 아직 공개 검증 기간이 상대적으로 짧은 PQC의 구현·설계 결함 위험을 고려하면, 당분간 기존 알고리즘과 결합한 하이브리드가 현실적 정답이다. 다만 하이브리드는 핸드셰이크 비용을 늘리고 상호운용성 테스트를 복잡하게 하므로, 표준 성숙도에 따라 순수 PQC로 넘어가는 출구 전략을 함께 설계해야 한다.
지금 시작해야 하는 선제적 자산 보호(HNDL 대응): 보호 기간이 긴 데이터는 양자컴퓨터가 없는 현재에도 수집·저장 위협에 노출되어 있다. 모스카 부등식(X+Y>Z)에 따라 암호 인벤토리·CBOM 작성 → 민감 자산 우선 전환을 즉시 착수해야 하며, 전환은 수년이 걸리는 장기 프로그램임을 조직 거버넌스 차원에서 인식해야 한다.
연계 기술과 공급망 고려: PQC 전환은 PKI·HSM·TLS 라이브러리·코드서명·전자서명 제도, 그리고 상용 솔루션 공급망 전반과 맞물린다. 외주 라이브러리·펌웨어에 박힌 암호까지 추적하지 못하면 전환이 무력화되므로, 공급업체의 PQC 로드맵 확인과 국내 KpqC·검증대상 암호모듈(KCMVP) 정합성을 조달·계약 단계에서 요건화하는 것이 바람직하다.
참고자료
- NIST, "Post-Quantum Cryptography Standardization" — https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
- NIST, "NIST Releases First 3 Finalized Post-Quantum Encryption Standards" (FIPS 203/204/205, 2024.8) — https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
- Wikipedia, "NIST Post-Quantum Cryptography Standardization" — https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization
- 보안뉴스, "[기고] KpqC 공모전 알고리즘 선정과 활용" — https://m.boannews.com/html/detail.html?idx=135674
- 삼성SDS 인사이트, "미래 전장의 새로운 방패, 양자내성암호로의 대전환" — https://www.samsungsds.com/kr/insights/the-great-transition-to-pqc.html
한 줄 요약: 양자내성암호(PQC)는 쇼어 알고리즘으로 붕괴하는 RSA·ECC를 격자·부호·해시 등 양자 난공 문제 기반 알고리즘으로 대체하는 고전 컴퓨터용 공개키·서명 기술로, NIST FIPS 203/204/205 확정과 국내 KpqC·2035 전환 마스터플랜을 배경으로 하며, HNDL 위협에 맞서 암호 인벤토리·크립토 애자일·하이브리드를 통한 선제적·점진적 전환이 핵심이다.