양자내성암호(PQC, Post-Quantum Cryptography)란?

1. 개요

가. 정의

• 양자내성암호(PQC, Post-Quantum Cryptography)는 충분한 성능의 양자컴퓨터가 등장한 이후에도 안전성을 유지하도록 설계된 차세대 공개키 암호기술이다.
• 기존 RSA·DH·ECC가 의존하는 소인수분해(Integer Factorization), 이산로그(Discrete Logarithm) 문제 대신, 양자컴퓨터에서도 효율적인 해법이 알려지지 않은 격자(Lattice), 오류정정부호(Code), 해시(Hash) 등 새로운 수학적 난제를 이용한다.
• PQC 자체는 양자컴퓨터에서 실행하는 것이 아니라 현재의 일반 CPU·서버·네트워크·보안장비에서도 구현 가능한 Classical Cryptography라는 점이 핵심이다. KISA도 PQC를 양자컴퓨팅 환경에서 안전하게 암호기술을 사용할 수 있도록 하는 새로운 공개키암호로 정의한다.

나. 등장 배경

현재 인터넷과 정보시스템의 공개키 암호는 주로 다음 문제의 계산적 어려움에 기반한다.

• RSA → 소인수분해
• DH / DSA → 이산로그
• ECC / ECDH / ECDSA → 타원곡선 이산로그

그러나 충분한 규모의 오류보정 양자컴퓨터가 등장하면 Shor Algorithm을 이용하여 이들 문제를 고전컴퓨터보다 획기적으로 빠르게 해결할 수 있다.

따라서

RSA·ECC 기반 공개키암호 → Quantum Vulnerable

이라는 근본적인 문제가 발생한다.

---

2. 양자컴퓨터가 기존 암호에 미치는 영향

가. Shor Algorithm

• Peter Shor가 1994년 제안
• 양자컴퓨터를 이용해
  • Integer Factorization
  • Discrete Logarithm
    을 Polynomial Time에 해결할 수 있는 알고리즘

충분한 규모의 CRQC(Cryptographically Relevant Quantum Computer)가 실현될 경우 다음이 직접적인 영향을 받는다.

• RSA Encryption / Signature
• Diffie-Hellman
• ECDH
• DSA
• ECDSA

즉, 현재 Internet PKI·TLS·VPN·전자서명의 핵심 공개키 기반이 위협받는다.

나. Grover Algorithm

Grover Algorithm은 대칭키·Hash 탐색 문제에 약 제곱근 수준의 가속효과를 제공한다.

예를 들어 이상적인 공격모델에서는

2ⁿ 탐색 → 약 2ⁿ⁄²

수준으로 복잡도가 감소할 수 있다.

따라서 AES 등 대칭키 알고리즘은 RSA·ECC처럼 구조적으로 붕괴하는 것이 아니라 충분한 Key Length를 선택하여 대응하는 방식이 가능하다.

대표적으로 장기 보안성을 고려하면 AES-256과 같은 충분한 Key Size 활용이 중요하다.

---

3. Harvest Now, Decrypt Later 위협

PQC 전환이 양자컴퓨터 완성 이후가 아니라 지금부터 필요한 가장 중요한 이유이다.

가. 개념

HNDL(Harvest Now, Decrypt Later)은 공격자가 현재 해독할 수 없는 암호화된 통신을 미리 수집·보관한 후,

현재 암호문 수집 → 미래의 양자컴퓨터 등장 → 과거 데이터 복호화

하는 공격전략이다.

나. 위험대상

장기간 기밀성이 유지되어야 하는 정보는 특히 위험하다.

• 국가기밀
• 국방정보
• 의료정보
• 금융정보
• 핵심기술
• 개인정보
• 장기 연구자료

따라서 CRQC가 언제 등장할지를 정확하게 예측하지 못하더라도 데이터의 보호기간이 길다면 미리 PQC 전환을 시작해야 한다.

---

4. PQC의 기본 구조

PQC의 핵심 기능은 크게 두 가지로 구분한다.

가. KEM(Key Encapsulation Mechanism)

두 당사자가 Public Channel을 통해 안전한 Shared Secret Key를 설정하기 위한 방식이다.

대표적으로:

ML-KEM

이 사용된다.

중요한 점은 ML-KEM이 대용량 데이터를 직접 암호화하는 알고리즘이 아니라는 것이다.

실제 통신은 일반적으로

ML-KEM → Shared Secret 생성 → AES 등의 대칭키 암호 → 실제 Data 암호화

구조를 사용한다.

NIST SP 800-227 역시 KEM을 Public Channel에서 Shared Secret을 설정하고, 이후 해당 Secret을 대칭키 암호에 사용하는 구조로 정의한다.

나. Digital Signature

전자문서·Software·Certificate 등에 대해

• Authentication
• Integrity
• Non-repudiation

을 제공한다.

대표 표준:

• ML-DSA
• SLH-DSA

---

5. NIST PQC 표준

NIST는 2016년부터 전 세계 연구진을 대상으로 PQC 표준화 경쟁을 수행하였다.

그 결과 2024년 8월 13일 최초의 PQC FIPS 표준 3종을 공식 발표하였다.

가. FIPS 203 — ML-KEM

ML-KEM(Module-Lattice-Based Key-Encapsulation Mechanism)

기존 명칭:

CRYSTALS-Kyber

기반:

Module Lattice Problem

역할:

Key Establishment / KEM

대표 Parameter Set:

• ML-KEM-512
• ML-KEM-768
• ML-KEM-1024

현재 NIST의 범용 PQC Key Establishment의 핵심 표준이다.

---

나. FIPS 204 — ML-DSA

ML-DSA(Module-Lattice-Based Digital Signature Algorithm)

기존 명칭:

CRYSTALS-Dilithium

기반:

Module Lattice Problem

역할:

Digital Signature

대표 Parameter:

• ML-DSA-44
• ML-DSA-65
• ML-DSA-87

높은 성능과 비교적 균형 잡힌 Key·Signature 크기로 일반적인 PQC Signature의 핵심 표준이다.

---

다. FIPS 205 — SLH-DSA

SLH-DSA(Stateless Hash-Based Digital Signature Algorithm)

기존 명칭:

SPHINCS+

기반:

Hash Function

역할:

Digital Signature

격자문제와 전혀 다른 보안가정에 기반한다는 것이 장점이다.

NIST는 SLH-DSA를 Stateless Hash-based Signature Standard로 정의하고 있다.

---

6. 아직 최종 표준이 아닌 알고리즘

시험에서는 선정(Selected)과 표준화 완료(Standardized)를 반드시 구분해야 한다.

가. FN-DSA

기존 명칭:

FALCON

격자기반 Digital Signature Algorithm이다.

NIST는 FALCON을 표준화 대상으로 선정했으며 향후

FIPS 206 — FN-DSA

로 표준화할 계획이다.

그러나 2026년 현재 FIPS 206은 아직 최종 표준으로 발행되지 않았다.

나. HQC

• Hamming Quasi-Cyclic 기반
• Code-based Cryptography
• KEM

NIST는 2025년 3월 HQC를 추가 KEM 표준화 대상으로 선정하였다.

HQC의 중요한 의미는 ML-KEM을 대체하기 위한 것이 아니라,

ML-KEM과 다른 수학적 문제를 기반으로 한 Backup KEM

이라는 점이다.

ML-KEM에 구조적인 취약성이 발견될 경우를 대비하여 Cryptographic Diversity를 확보하는 목적이다. NIST도 ML-KEM을 범용 기본 선택으로 유지하면서 HQC를 제2의 방어선으로 설명한다.

---

7. PQC 알고리즘의 주요 계열

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

대표:

• ML-KEM
• ML-DSA
• FN-DSA
• NTRU 계열

기반문제:

• LWE(Learning With Errors)
• Module-LWE
• SIS(Short Integer Solution)

장점

• 비교적 우수한 성능
• 다양한 암호 Primitive 구현 가능
• 현재 NIST PQC의 중심 기술

단점

• 기존 RSA/ECC보다 Key·Ciphertext·Signature가 커질 수 있음
• 구현 오류 및 Side-channel 대응 필요

---

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

대표:

• SLH-DSA

기반:

Cryptographic Hash Function의 안전성

장점

• 매우 보수적인 보안가정
• 격자 기반과 다른 Security Assumption 제공

단점

• Signature Size가 상대적으로 큼
• 일부 환경에서 성능 부담

---

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

대표:

• HQC
• Classic McEliece

기반:

Error-Correcting Code Decoding Problem

장점

• 오랜 연구역사
• Lattice와 다른 보안가정

단점

• 일부 방식은 Public Key Size가 매우 큼

NIST는 2025년 4라운드 평가에서 HQC를 최종 추가 KEM 표준화 대상으로 선택했다.

---

라. 다변수 기반(Multivariate Cryptography)

• 다변수 다항식 시스템을 푸는 어려움을 이용
• Signature 분야에서 오랫동안 연구

그러나 일부 후보가 Cryptanalysis로 탈락한 사례가 있어 지속적인 검증이 필요하다.

---

마. 아이소제니 기반(Isogeny-based Cryptography)

대표적으로 과거 SIKE가 연구되었다.

장점은 작은 Key Size였지만 SIKE는 2022년 심각한 공격이 발견되어 안전하지 않은 것으로 판명되어 사용해서는 안 된다.

이는 PQC에서도

새로운 수학적 구조 = 자동적으로 안전

한 것이 아니며 장기간의 공개 검증이 중요함을 보여준다. NIST 역시 SIKE가 안전하지 않다고 명시하고 있다.

---

8. QKD와 PQC의 차이

양자보안 기술에서 가장 혼동하기 쉬운 개념이다.

가. QKD

QKD(Quantum Key Distribution)

• 양자역학적 특성을 이용해 암호키를 전달
• 양자상태의 측정이 상태를 변화시키므로 도청 여부를 탐지
• 광자·Quantum Channel 등 별도 물리 Infrastructure 필요

대표:

• BB84

나. PQC

Post-Quantum Cryptography

• 수학적 난제 기반
• 기존 CPU·Network·Internet Infrastructure에서 실행
• Algorithm과 Software를 교체하는 방식

다. 핵심 차이

QKD = Quantum Physics 기반 Key Distribution

PQC = Quantum-resistant Mathematics 기반 Public-key Cryptography

따라서 PQC는 기존 Internet·Cloud·Mobile 환경 전체에 대규모로 적용하기 상대적으로 용이하다.

---

9. PQC와 기존 암호의 Hybrid 전환

PQC를 즉시 단독으로 적용하기보다 전환과정에서 기존 Classical Algorithm과 결합할 수 있다.

예:

ECDH + ML-KEM

가. Hybrid 방식

두 개의 Key Establishment 결과를 안전한 Combiner로 결합한다.

목표는

• Classical Algorithm이 안전하거나
• PQC Algorithm이 안전하면

최종 Session Key가 보호되도록 설계하는 것이다.

나. 장점

• 신규 PQC의 장기 안전성 불확실성 완화
• 기존 Algorithm과의 점진적 전환 가능

다. 고려사항

• Protocol Complexity 증가
• Packet Size 증가
• Implementation Error
• Downgrade Attack
• Key Combination 설계

등을 주의해야 한다.

NIST SP 800-227도 KEM Hybrid 사용 시 승인된 방식의 Combiner와 적절한 보안속성 유지가 필요함을 다룬다.

---

10. PQC 적용대상

가. TLS

기존:

ECDHE + ECDSA

PQC 전환:

ML-KEM 기반 Key Establishment + PQC/Hybrid Signature

나. VPN

• IPsec
• SSL VPN
• Remote Access VPN

등의 Key Exchange를 PQC로 전환

다. PKI

• Root CA
• Intermediate CA
• End-entity Certificate
• CRL
• OCSP

등의 Signature Algorithm 변경

라. Code Signing

• OS
• Firmware
• Application
• Container
• Software Update

의 Digital Signature를 PQC로 전환

마. IoT / Embedded

장기간 운영되는 장비는 특히 중요하다.

• 자동차
• 산업장비
• 의료장비
• Smart Meter
• 위성

등은 배포 후 10~20년 이상 사용될 수 있으므로 현재부터 PQC-ready Architecture를 고려해야 한다.

---

11. PQC 전환의 주요 문제점

가. Key·Ciphertext·Signature 크기 증가

ECC 대비 PQC는 일반적으로 Key·Signature Size가 커진다.

영향:

• TLS Handshake
• Certificate
• Network Packet
• Storage
• IoT Memory

나. 성능

Algorithm마다

• Key Generation
• Encapsulation
• Decapsulation
• Sign
• Verify

성능 특성이 다르다.

따라서 단순 Benchmark가 아니라 실제 Target System에서 검증해야 한다.

다. Legacy System

오래된

• HSM
• Smart Card
• TPM
• Embedded Device
• Network Appliance

는 새로운 PQC Algorithm을 지원하기 어려울 수 있다.

라. PKI 영향

PQC Certificate의 Public Key와 Signature 증가로

• Certificate Size
• Handshake Size
• CA Infrastructure

에 영향을 줄 수 있다.

마. 상호운용성

PQC 지원 Vendor와 미지원 Vendor가 공존하는 긴 Transition Period가 발생한다.

---

12. PQC 전환 전략

PQC 전환은 단순히

RSA → ML-KEM

으로 Algorithm 이름만 변경하는 작업이 아니다.

가. 1단계 — Cryptographic Discovery

조직 내 모든 암호자산을 식별한다.

• RSA
• ECC
• DH
• Certificate
• TLS
• VPN
• Library
• HSM
• Firmware
• Application

NIST의 PQC Migration Project 역시 첫 번째 핵심 작업으로 Cryptographic Visibility와 Risk Management, 즉 전체 암호 Inventory 확보를 강조한다.

나. 2단계 — 위험평가

다음 기준으로 전환 우선순위를 결정한다.

• Data Lifetime
• Business Criticality
• Exposure
• System Lifetime
• Migration Difficulty

장기간 비밀성이 필요한 데이터일수록 우선순위를 높인다.

다. 3단계 — 전환대상 우선순위화

우선 적용 대상:

• 국가·국방
• 금융
• 의료
• 장기간 개인정보
• 외부 노출 TLS/VPN
• 장기운영 Embedded System

라. 4단계 — Pilot

실제 환경에서

• TLS
• VPN
• PKI
• Code Signing

등에 PQC 또는 Hybrid Mode를 적용한다.

평가항목:

• Latency
• CPU
• Memory
• Network Size
• Compatibility
• Stability

마. 5단계 — Migration

검증된 영역부터 단계적으로

• ML-KEM
• ML-DSA
• SLH-DSA

등으로 전환한다.

바. 6단계 — 지속관리

Algorithm이 향후 다시 변경될 수 있음을 전제로

• Inventory
• Policy
• Version
• Vendor
• Certificate
• Algorithm Lifecycle

을 지속적으로 관리한다.

---

13. Crypto Agility

PQC 전환의 궁극적인 목표 중 하나이다.

가. 정의

Crypto Agility는 새로운 취약점·표준·Algorithm이 등장했을 때 Application과 Infrastructure 전체를 재개발하지 않고도 암호 Algorithm과 Key·Protocol을 빠르게 교체할 수 있는 능력이다.

NIST는 2026년 업데이트된 CSWP 39에서 Crypto Agility를 Software·Hardware·Firmware·Protocol·Infrastructure의 암호 Algorithm을 운영을 유지하면서 변경·적응할 수 있는 역량으로 정의한다.

나. 구현원칙

• Algorithm Hard-coding 금지
• Crypto API 추상화
• Algorithm Policy 분리
• Centralized Crypto Inventory
• Version 관리
• Key Lifecycle 관리
• Automated Certificate Rotation

다. 필요성

이번에는

RSA/ECC → PQC

전환이지만,

향후 새로운 Cryptanalysis가 등장하면 다시 다른 Algorithm으로 전환해야 할 수 있다.

따라서

PQC Migration → Crypto Agile Architecture

로 확장해야 한다.

---

14. 국내 KpqC

우리나라 역시 독자적인 PQC 표준체계를 구축하고 있다.

가. KpqC 공모전

국내에서는 2021년부터 한국형 양자내성암호 국가공모전(KpqC)을 추진하였다.

2025년 1월 최종 4개 Algorithm이 선정되었다.

나. KEM / PKE 분야

NTRU+

• 격자 기반
• 공개키암호 / Key Establishment

SMAUG-T

• 격자 기반
• 공개키암호 / KEM

다. Digital Signature 분야

HAETAE

• 격자 기반
• Digital Signature

AIMer

• 영지식·대칭키 기반
• Digital Signature

따라서 국내 최종 선정 알고리즘은

NTRU+ + SMAUG-T + HAETAE + AIMer

로 정리할 수 있다. KISA는 이들 4종을 2025년 국내 양자내성암호 표준 대상 알고리즘으로 명시하고 있다.

---

15. 국내 PQC 전환 동향

국내도 이제 Algorithm 선정단계를 넘어 실제 Infrastructure 전환 단계로 이동하고 있다.

과학기술정보통신부와 KISA는 2026년 양자내성암호 시범전환 사업을 추진하고 있으며, 실제 산업 IT Infrastructure에서 기존 공개키 암호를 PQC로 전환하여

• 적용방법
• 절차
• 제약조건
• 성능
• 운영 고려사항

을 검증하고 있다.

따라서 국내 PQC 정책도

Algorithm Competition → Standardization → Pilot Migration → 산업확산

단계로 발전하고 있다고 볼 수 있다.

---

16. NIST 최신 동향

2026년 현재 NIST PQC 포트폴리오는 다음처럼 기억하면 명확하다.

가. 최종 표준

• FIPS 203 — ML-KEM
• FIPS 204 — ML-DSA
• FIPS 205 — SLH-DSA

2024년 8월 공식 발행되었으며 실제 시스템에 사용할 수 있는 PQC 표준이다.

나. 추가 표준화

• FN-DSA(FALCON) → FIPS 206 개발 중
• HQC → 2025년 추가 KEM으로 선정, 최종 표준 준비 중

다. KEM 운영 가이드

2025년 9월 NIST SP 800-227이 최종 발행되어 KEM의 정의·사용·구현에 관한 보안 가이드가 마련되었다.

라. Crypto Agility

NIST는 2026년 CSWP 39upd1을 통해 PQC 전환뿐 아니라 미래의 Algorithm 교체까지 고려한 Crypto Agility를 강조하고 있다.

즉, 표준화의 중심이

어떤 Algorithm을 선택할 것인가

에서

어떻게 실제 시스템을 안전하게 전환하고 향후 교체 가능하게 만들 것인가

로 이동하고 있다.

---

17. PQC의 장점

가. 기존 Infrastructure 활용

• 특별한 Quantum Channel 없이 적용 가능
• Internet·Cloud·Mobile·IoT에 Software Update 형태로 적용 가능

나. 대규모 확장성

• Global Internet Infrastructure에 적용 가능
• TLS·VPN·PKI 등 기존 Protocol과 통합 가능

다. Quantum Threat 대응

• Shor Algorithm에 취약한 RSA·ECC를 대체
• HNDL 위협 대응 가능

라. 다양한 Algorithm Family

• Lattice
• Hash
• Code

등 서로 다른 보안가정을 이용하여 Cryptographic Diversity 확보 가능

---

18. PQC의 한계

가. 큰 Key 및 Signature

기존 ECC 대비 통신·저장 부담 증가

나. 구현복잡성

• Side-channel
• Constant-time Implementation
• Random Number
• Failure Handling 등에 대한 주의 필요

다. Algorithm의 상대적으로 짧은 역사

RSA·ECC보다 연구·운영 역사가 짧기 때문에 지속적인 Cryptanalysis 필요

라. Migration 비용

• Application
• PKI
• HSM
• Network Device
• Embedded System까지 영향을 받기 때문에 장기간의 전환비용 발생

---

19. 발전 방향

가. Algorithm Standardization → Migration

연구 중심에서 실제 서비스 배포 중심으로 이동

나. Single PQC → Cryptographic Diversity

ML-KEM만 사용하는 것보다

• ML-KEM
• HQC
• 기타 독립적 보안가정

을 통해 장기적인 위험분산

다. PQC + Classical Hybrid

Migration 초기에는 기존 알고리즘과 PQC를 함께 사용하여 Risk를 완화

라. Crypto Agility

특정 Algorithm에 다시 종속되지 않도록 교체 가능한 Architecture 구축

마. Hardware Acceleration

• NPU
• FPGA
• ASIC
• HSM

등을 이용한 PQC 연산 최적화

바. PQC-ready PKI

Certificate·CA·HSM·Code Signing을 포함한 전체 Trust Infrastructure의 PQC 전환

---

20. 핵심 정리

• PQC = 양자컴퓨터와 고전컴퓨터 모두의 공격에 안전하도록 설계된 차세대 공개키 암호
• Shor Algorithm은 RSA·DH·ECC의 기반문제인 소인수분해·이산로그를 위협
• PQC는 양자컴퓨터가 아니라 현재의 Classical Computer에서 실행
• QKD는 양자물리 기반 Key Distribution, PQC는 수학적 난제 기반 암호
• 핵심 기능은 KEM + Digital Signature
• NIST 최종 표준:
  • FIPS 203 = ML-KEM
  • FIPS 204 = ML-DSA
  • FIPS 205 = SLH-DSA
• FN-DSA(FALCON)는 FIPS 206 개발 중
• HQC는 2025년 추가 Backup KEM으로 선정되었으나 최종 FIPS는 아직 아님
• 국내 KpqC 최종 선정:
  • NTRU+
  • SMAUG-T
  • HAETAE
  • AIMer
• 현재 가장 중요한 문제는 Algorithm 연구보다 Crypto Inventory → Risk Assessment → Pilot → Migration → Crypto Agility
• 장기 기밀데이터는 Harvest Now, Decrypt Later 때문에 양자컴퓨터 등장 전에 전환해야 함

기술사 관점 핵심 문장
양자내성암호(PQC)는 Shor Algorithm에 의해 위협받는 RSA·ECC 등의 기존 공개키암호를 대체하기 위해 격자·해시·오류정정부호 등 양자컴퓨터에서도 효율적인 해법이 알려지지 않은 수학적 난제를 활용하는 차세대 공개키 암호기술이며, 현재는 NIST의 ML-KEM·ML-DSA·SLH-DSA 표준화를 기반으로 암호자산 가시화, Hybrid 적용, 단계적 Migration 및 Crypto Agility 확보가 핵심 과제로 전환되고 있다.