차세대 암호
정보보호의 기반 암호기술 및 정책에 대한 다양한 정보전달
양자내성암호
양자내성암호란
양자내성암호(Post-Quantum Cryptography)는 양자컴퓨팅 환경에서 안전하게 암호기술을 이용할 수 있도록 하는 새로운 공개키암호입니다. 1994년 피터 쇼어(Peter Shor)에 의해 양자 컴퓨팅을 이용한 연산으로 인수분해, 이산로그 등 기존 공개키암호의 기반문제를 이론적으로 해독할 수 있는 알고리즘이 개발된 이후, 이러한 양자컴퓨팅 환경에서 해독 위협에 대응하는 새로운 공개키암호를 양자내성암호라고 합니다.
배경
양자 컴퓨터(Quantum computer)는 양자 중첩(superposition), 얽힘(entanglement)과 같은 양자 물리학적 현상을 활용하여 데이터를 처리하는 연산 장치입니다. 2017년 IBM에서 5 큐비트 수준의 범용 양자컴퓨터 'Q'를 개발한 이후 각 기업에서는 고성능의 양자 컴퓨터를 개발하기 위한 노력을 계속하고 있으며, IBM의 Condor(1,121큐비트)와 Heron(133큐비트), Google의 2세대 Sycamore(70큐비트) 등 향상된 성능의 양자컴퓨터가 개발되었습니다. 최근 결과값에 영향을 미치는 양자 오류가 대두됨에 따라 양자 오류 수정(Quantum Error Correction, QEC) 기술 개발이 활발하게 이루어지고 있습니다.
추후 양자 오류 문제가 해결되고 공개키 암호를 해독할 수 있는 수준의 양자컴퓨터(Cryptanalytically Relevant Quantum Computer, QRQC)가 개발될 경우, 현재 사용 중인 공개키 암호는 양자 컴퓨터에 의해 해독될 수 있습니다. 이러한 양자 취약성(Quantum vulnerability)에 대한 대안으로 제시되고 있는 솔루션이 바로 양자내성암호(Post-Quantum Cryptography, PQC)입니다.
알고리즘 공모 및 표준화
미국의 NIST(국가표준기술연구소)에서는 양자컴퓨터의 공개키 암호 해독 위협에 대비하기 위해 2016년부터 공개키를 이용한 암호(PKE), 키 캡슐화(KEM) 및 서명(Signature) 기능을 보유한 새로운 알고리즘의 표준화를 위한 공모를 진행하고 있습니다. 해당 공모전에서는 쇼어(Shor)의 알고리즘으로 해독이 되는 인수분해, 이산로그 문제와 달리 양자 컴퓨팅으로도 해결하기 어렵다고 여겨지는 격자(Lattice), 코드(Code), 다변수 방정식(Multivariate) 등 여러 기반문제를 활용하여 새로운 알고리즘들이 개발되어 참여하였습니다. 이러한 배경에서 NIST는 알고리즘의 안전성, 성능, 취약점 대응, 적용 유연성 등을 평가하여 2022년 4종의 표준화 알고리즘과 4종의 대체 후보 알고리즘(BIKE, Classic McEliece, HQC, SIKE*)을 발표하였습니다. 이후 추가 평가를 통해 2025년 3월, 대체 후보군 중 하나였던 HQC가 표준화 대상 알고리즘으로 최종 선정되었습니다.
표준화 대상 알고리즘이 선정된 이후, NIST는 2023년 8월 양자내성암호 ML-KEM(Crystals-Kyber), ML-DSA(Crystals-Dilithium), SLH-DSA(SPHINCS+)에 대한 표준 초안 3종(FIPS-203, FIPS-204, FIPS-205)을 공개하였고, 2024년 8월 최종 표준 문서가 공개되었습니다. FN-DSA(Falcon)에 대한 표준화 작업또한 2024년 8월에 시작하여 현재 진행 중이며, 추가 선정된 HQC에 대한 표준화 작업은 2025년 중에 시작될 예정입니다.
* 2022년 7월, SIKE(아이소제니 기반) 알고리즘은 보안 취약점 문제가 발견되어 대체 후보군에서 제외
美 NIST 공모전 최종 선정된 양자내성암호 표준화 대상 알고리즘
| 상태 | 알고리즘명 | 기반문제 | 기능 |
|---|---|---|---|
| 최종선정 | CRYSTALS-KYBER (ML-KEM) | 격자 | PKE/KEM |
| HQC | 코드 | ||
| CRYSTALS-Dilithium (ML-DSA) | 격자 | 전자서명 | |
| FALCON (FN-DSA) | |||
| SPHINCS+ | 해시 |
양자내성암호 전자서명 표준화 알고리즘 추가 공모전
| 상태 | 기반문제 | 알고리즘명 |
|---|---|---|
| 2라운드 진출 | 코드(6개) | CROSS |
| LESS | ||
| 아이소제니(1개) | SQIsign | |
| 격자(7개) | HAWK | |
| 영지식 MPC-in-the-Head(7개) | MiRitH | |
| MOOM | ||
| PERK | ||
| RYDE | ||
| SDitH | ||
| 다변수(10개) | MAYO | |
| QR-UOV | ||
| SNOVA | ||
| UOV | ||
| 대칭키(4개) | FAEST |
NIST는 2022년 다양성을 위해 추가적으로 격자 기반 외에 다른 기반 문제 알고리즘을 대상으로 하는 새로운 전자서명 표준화 알고리즘 공모를 시작하였습니다. 2023년 7월, 다양한 문제를 기반으로 하는 40개의 알고리즘이 1라운드에 선정되었고, 2024년 10월 14개의 알고리즘이 2라운드를 통과하여 현재 평가 진행 중에 있습니다. NIST 공식 문서(1라운드 상태보고서)에 따르면 2026년에 최종 후보를 공개할 계획입니다.
2025년 선정된 국내 양자내성암호 표준 대상 알고리즘
| 알고리즘명 | 기반문제 | 기능 |
|---|---|---|
| NTRU+ | 격자 | PKE/KEM |
| SMAUG-T | ||
| HAETAE | 격자 | 전자서명 |
| AIMer | 영지식+대칭키 |
국내에서는 한국형 양자내성암호(KpqC) 확보를 위해 2021년 11월, 양자내성암호연구단을 주축으로 ‘양자내성암호 국가공모전(KpqC 공모전)’을 시작하였습니다. 16개의 알고리즘으로 시작하여 2023년 12월, 8개의 알고리즘이 1라운드 진출 알고리즘으로 발표되었고, 2025년 1월에 4개의 알고리즘이 최종적으로 선정되었습니다. 선정된 알고리즘은 「汎국가 양자내성암호 전환 마스터플랜」에 따라 표준화 작업을 추진할 예정입니다.
공개키암호의 양자내성암호 전환
양자컴퓨팅 및 양자암호 업계에서는 2035년경이 되면 현재 사용 중인 RSA, ECC 등의 공개키암호를 해독할 수 있는 수준의 양자컴퓨터(CRQC)가 등장할 것으로 예상하고 있습니다. 이에 미국, 유럽, 한국 등 주요 국가들은 기존의 공개키 암호의 취약성의 선제적 대응을 위해 양자내성암호로의 전환을 추진하고 있습니다.
미국은 국가사이버안보센터(NCCoE)를 통해 기업들과 협력하여 양자내성암호 전환 프로젝트(Migration to Post-Quantum Cryptography)를 추진하고 있으며, 산업 분야에서 양자내성암호가 원활하게 적용될 수 있도록 성능 평가, 상호운용성 검증, 암호기술 탐색 및 평가 방법 연구 등을 수행하고 있습니다. 유럽 역시 유럽전기통신표준화기구(ESTI)를 중심으로 기술 가이드라인을 제공하고 있으며 양자내성 하이브리드 키 설정 관련 표준 개발 프로젝트를 진행하고 있습니다. 이외에도 독일, 프랑스, 네덜란드 등 각국 정부 차원에서 전환 계획을 수립하고 있습니다.
국내에서는 2023년 7월, 과학기술정보통신부, 국가정보원을 주축으로 행정안전부, 한국인터넷진흥원 등 관계 부처와 협력하여 「汎국가 양자내성암호 전환 마스터플랜」을 공표하였으며, 2025년부터는 「양자내성암호 시범전환 지원사업」을 추진하며 에너지, 의료, 행정 등 전환이 필요한 산업 분야의 양자내성암호 도입을 지원하고 있습니다.
양자내성암호 전환관련 발간 문서
| 발간일 | 발간기관 | 문서명 |
|---|---|---|
| 2017년 2월 | 유럽 ETSI | Quantum Safe Cryptography; Case Studies and Deployment Scenarios (양자내성암호 사례 연구 및 적용 시나리오) |
| 2020년 7월 | 유럽 ETSI | Migration strategies and recommendations to Quantum Safe schemes (양자내성암호 전환 전략 및 요구사항) |
| 2020년 8월 | 미국 NIST | Towards PQC Standardization and Migration (양자내성암호 표준화 및 전환) |
| 2020년 10월 | 미국 NIST | Considerations in Migrating to Post-Quantum Cryptographic Algorithms (양자내성암호 알고리즘 전환을 위한 고려사항) |
| 2021년 4월 | 미국 NIST | Getting Ready for Post-Quantum Cryptography: Exploring Challenges Associated with Adopting and Using Post-Quantum Cryptographic Algorithms (양자내성암호 전환준비: 양자내성암호 적용을 위한 도전과제 탐색) |
| 2021년 8월 | 미국 NIST | Migration to Post-Quantum Cryptography (양자내성암호 전환 시나리오) |
| 2021년 10월 | 미국 DHS | PREPARING FOR POST-QUANTUM CRYPTOGRAPHY (양자내성암호 전환준비 로드맵) |
| 2022년 1월 | 프랑스 ANSSI | ANSSI views on the Post-Quantum Cryptography transition (양자내성암호 전환 정책 및 로드맵) |
| 2022년 5월 | 미국 백악관 | NSM-10, National Security Memorandum on Promoting United States Leadership in Quantum Computing While Mitigating Risks to Vulnerable Cryptographic Systems (양자내성암호 전환 준비 관련 보안 각서) |
| 2022년 11월 | 미국 OMB | M-23-02, MEMORANDUM FOR THE HEADS OF EXECUTIVE DEPARTMENTS AND AGENCIES (양자내성암호 전환 세부 지침서) |
| 2022년 12월 | 미국 의회 | H.R.7535 - Quantum Computing Cybersecurity Preparedness Act (양자내성암호 전환 관련 법안) |
| 2023년 7월 | 한국 | 汎국가 양자내성암호 전환 마스터플랜 |
| 2023년 8월 | 미국 | Quantum-Readiness: Migration to Post-Quantum Cryptography (양자 준비: 양자내성암호로 전환) |
| 2023년 8월 | 독일 | Handlungskonzept Quantentechnologien (독일연방정부의 양자기술액션플랜) |
| 2024년 7월 | 미국 OMB | REPORT ON POST-QUANTUM CRYPTOGRAPHY (양자내성암호 전환 전략 보고서) |
| 2024년 12월 | 네덜란드 | The PQC Migration Handbook v2 (양자내성암호 전환 지침서) |
| 2025년 2월 | 유럽 ETSI | CYBER; Quantum-Safe Cryptography; Efficient Quantum-Safe Hybrid Key Exchanges with Hidden Access Policies (양자안전 하이브리드 키 교환 및 접근 제어 정책 연구) |
향후 추진 과제
KISA를 비롯한 정부부처, 연구 기관, 국내 기업 등에서는 양자내성암호 전환을 위해 다양한 연구와 시험, 개발 등을 진행하고 있습니다. 양자컴퓨터 기술발전에 따른 현 암호체계 안전성 위협에 대비하기 위해 한국형 양자내성암호 알고리즘 표준화 진행, 안전성·성능 기준 마련, 양자내성암호 시범전환 지원사업 운영, 암호체계 전환 가이드 개발 등 국가 암호체계 전환을 위해 노력하고 있습니다.
