양자컴퓨터 시대의 새로운 보안 기술|격자 기반 암호와 양자내성암호 쉽게 이해하기
양자컴퓨터가 등장하면 지금의 암호는 모두 깨질까?
양자컴퓨터가 등장하면 지금 사용하는 인터넷 암호가 모두 무너진다는 이야기를 한 번쯤 들어보셨을 겁니다.
그런데 이 이야기는 절반은 맞고, 절반은 설명이 더 필요합니다.
현재의 양자컴퓨터는 인터넷에서 사용되는 RSA나 ECC 암호를 마음대로 해독할 수 있는 수준이 아닙니다. NIST도 2026년 7월 현재 양자컴퓨터는 암호체계를 위협하기에는 너무 작고 불안정하다고 설명합니다. 실제 Shor 알고리즘을 이용해 현대적인 공개키 암호를 위협하려면 지금보다 훨씬 크고 안정적이며 오류 보정이 가능한 양자컴퓨터가 필요합니다.
그런데도 세계 각국이 벌써 새로운 암호기술을 준비하는 이유는 무엇일까요?
암호체계는 프로그램 하나를 업데이트하듯 하루아침에 교체할 수 없기 때문입니다. 금융망, 정부 시스템, 클라우드, VPN, 인증서, 스마트폰, 서버 등 수많은 시스템이 서로 연결돼 있어 전환에 오랜 시간이 걸립니다. NIST는 과거 암호 전환도 10~20년이 걸릴 수 있었다고 설명합니다.
여기에 또 하나 중요한 문제가 있습니다.
바로 ‘Harvest Now, Decrypt Later’, 우리말로 풀면 ‘지금 수집해 두고 나중에 해독한다’는 공격 가능성입니다.
공격자가 현재 암호화된 중요한 데이터를 저장해 두었다가 미래에 충분히 강력한 양자컴퓨터가 등장하면 그때 해독하려 할 수 있다는 뜻입니다. 오랫동안 비밀로 유지해야 하는 의료정보, 국가기밀, 기업 기술자료 등이 특히 이런 위험과 관련됩니다.
지금 인터넷은 무엇으로 정보를 지키고 있을까?
우리가 인터넷뱅킹이나 쇼핑몰에 접속하면 보이지 않는 곳에서 여러 암호기술이 함께 작동합니다.
대표적인 공개키 암호가 RSA와 ECC입니다.
쉽게 비유하면 공개키 암호는 누구에게나 보여줄 수 있는 자물쇠와 자신만 가지고 있는 열쇠를 이용하는 방식과 비슷합니다.
RSA의 안전성은 큰 수의 소인수분해가 매우 어렵다는 사실과 관련되어 있고, ECC는 타원곡선에서의 이산로그 문제와 관련된 수학적 어려움을 이용합니다.
현재의 일반 컴퓨터로는 적절한 크기의 이러한 문제를 현실적인 시간 안에 해결하기 매우 어렵습니다.
문제는 충분히 강력한 양자컴퓨터가 등장했을 때입니다.
Shor 알고리즘이 왜 문제가 될까?
1990년대 피터 쇼어가 제안한 Shor 알고리즘은 충분히 큰 범용 양자컴퓨터에서 정수 소인수분해와 이산로그 문제를 기존 컴퓨터보다 훨씬 효율적으로 풀 수 있는 방법을 제시했습니다.
따라서 미래에 암호학적으로 의미 있는 대규모 양자컴퓨터가 만들어진다면 RSA와 ECC 같은 일부 공개키 암호가 영향을 받을 수 있습니다.
여기서 중요한 것은 ‘양자컴퓨터가 모든 암호를 똑같이 공격한다’는 뜻은 아니라는 점입니다.
예를 들어 AES 같은 대칭키 암호는 RSA·ECC와 영향이 다릅니다. 양자컴퓨터의 위협을 고려해야 하지만 공개키 암호처럼 Shor 알고리즘으로 같은 방식의 근본적인 공격을 받는 것은 아닙니다. NIST의 PQC 전환 작업도 특히 양자에 취약한 공개키 암호를 중요한 전환 대상으로 다루고 있습니다.
그래서 등장한 양자내성암호
이 문제를 해결하기 위해 준비하는 기술이 양자내성암호, 영어로 Post-Quantum Cryptography, 줄여서 PQC입니다.
여기에서 많이 혼동하는 것이 있습니다.
양자내성암호는 ‘양자컴퓨터로 만드는 암호’가 아닙니다.
일반 컴퓨터, 스마트폰, 서버와 기존 네트워크에서도 사용할 수 있도록 설계된 새로운 수학 기반 암호기술입니다. 목표는 기존 컴퓨터뿐 아니라 미래의 양자컴퓨터를 이용한 공격에도 견디기 어려운 수학 문제를 사용하는 것입니다.
또한 양자암호(Quantum Cryptography), 대표적으로 양자키분배(QKD)와도 다른 개념입니다.
PQC는 기존 인터넷과 컴퓨터 환경에서 소프트웨어 형태로 적용할 수 있다는 점 때문에 대규모 정보시스템 전환에서 중요한 기술로 주목받고 있습니다.
격자 기반 암호에서 ‘격자’란 무엇일까?
격자 기반 암호는 영어로 Lattice-based Cryptography라고 합니다.
‘격자’라고 하면 바둑판이나 모눈종이를 떠올리기 쉽습니다.
2차원 공간에 일정한 규칙으로 점들이 반복해서 놓여 있다고 생각해 보겠습니다.
점이 몇 개 되지 않는다면 원하는 점이나 가까운 점을 찾기가 쉽습니다. 그런데 이것을 수백 차원의 복잡한 공간으로 확장하면 이야기가 완전히 달라집니다.
사람이 그림으로 볼 수도 없을 만큼 복잡한 고차원 공간에서 특정 조건을 만족하는 점을 찾아내는 것은 매우 어려운 계산 문제가 됩니다.
실제 격자 기반 암호는 이런 고차원 수학 구조와 관련된 어려운 문제를 보안의 기반으로 사용합니다.
NIST가 표준화한 ML-KEM과 ML-DSA도 구조화된 격자 문제를 이용하는 대표적인 방식입니다.
일부러 작은 오류를 섞는다? LWE의 아이디어
격자 기반 암호를 이해할 때 자주 등장하는 것이 LWE, 즉 Learning With Errors입니다.
수학식을 사용하지 않고 아주 단순하게 생각해 보겠습니다.
누군가 정확한 숫자 규칙을 알려주는 대신 계산 결과마다 아주 작은 오차를 일부러 섞어서 수많은 결과를 보여준다고 가정해 보겠습니다.
규칙을 알고 있는 사람은 필요한 정보를 처리할 수 있지만, 아무 정보도 없는 사람에게는 원래 규칙을 찾아내기가 훨씬 어려워집니다.
LWE는 이런 직관과 관련된 수학적 문제입니다.
다만 실제 LWE는 단순히 ‘노이즈를 넣으면 암호가 된다’는 뜻이 아니라 선형 관계에 작은 오류가 포함된 관측값에서 숨겨진 값을 찾아내는 계산 문제가 어렵다는 점을 이용합니다.
ML-KEM에는 그 구조를 확장한 Module-LWE 계열의 수학적 문제가 사용됩니다. NIST FIPS 203도 ML-KEM의 안전성이 Module Learning With Errors 문제의 계산적 어려움과 관련돼 있다고 명시하고 있습니다.
왜 격자 기반 암호가 주목받을까?
격자 기반 암호에는 몇 가지 중요한 장점이 있습니다.
- 현재 알려진 고전 및 양자 공격을 고려한 PQC 설계가 가능하다.
- 키 설정과 디지털 서명 등 다양한 용도로 활용할 수 있다.
- 특별한 양자통신 장비 없이 기존 컴퓨터와 네트워크에 구현할 수 있다.
- 비교적 높은 처리 성능을 기대할 수 있는 알고리즘이 있다.
하지만 장점만 있는 것은 아닙니다.
기존 ECC보다 공개키, 암호문 또는 서명의 데이터 크기가 커질 수 있고 네트워크 대역폭과 인증서 크기, 하드웨어 구현, 기존 시스템 호환성을 고려해야 합니다.
실제로 Google은 2026년 양자내성 HTTPS 인증서를 검토하면서 커진 PQC 서명과 인증서가 TLS와 Certificate Transparency 인프라에 새로운 성능·대역폭 문제를 가져올 수 있다고 설명했습니다.
즉, ‘더 안전한 알고리즘으로 바꾸면 끝’이 아니라 인터넷 생태계 전체가 함께 바뀌어야 하는 작업입니다.
ML-KEM과 ML-DSA는 무엇일까?
2024년 8월 13일은 PQC 분야에서 중요한 날입니다.
NIST가 첫 3개의 최종 양자내성암호 표준을 발표했습니다.
그중 격자 기반 방식이 두 가지입니다.
ML-KEM
ML-KEM은 Module-Lattice-Based Key-Encapsulation Mechanism의 약자입니다.
NIST FIPS 203으로 표준화되었으며 두 통신 주체가 공개된 네트워크에서 이후 대칭키 암호에 사용할 공동 비밀값을 안전하게 설정하도록 돕는 기술입니다.
쉽게 말하면 HTTPS 통신을 시작하면서 ‘앞으로 우리끼리 사용할 비밀 열쇠를 어떻게 안전하게 마련할 것인가’와 관련된 기술입니다.
과거 NIST 공모 과정에서는 CRYSTALS-Kyber 또는 Kyber라는 이름으로 알려졌습니다. 표준화되면서 FIPS 203의 알고리즘 명칭이 ML-KEM으로 정리됐습니다.
ML-DSA
ML-DSA는 Module-Lattice-Based Digital Signature Algorithm입니다.
NIST FIPS 204로 표준화됐으며 전자서명에 사용됩니다.
전자서명은 문서나 소프트웨어가 변조되지 않았는지 확인하거나 ‘정말 이 사람이 또는 이 시스템이 서명했는가’를 확인하는 데 사용됩니다.
ML-DSA의 기반이 된 공모 알고리즘은 CRYSTALS-Dilithium입니다. 즉, Dilithium이 표준화 과정에서 ML-DSA라는 표준 명칭으로 정리됐다고 이해하면 쉽습니다.
또 다른 최종 표준 FIPS 205의 SLH-DSA는 SPHINCS+에서 나온 해시 기반 디지털 서명으로 격자 기반이 아닙니다.
NIST PQC 표준화는 끝난 걸까?
아직 관련 작업은 계속되고 있습니다.
2026년 9월 기준으로 FIPS 203의 ML-KEM, FIPS 204의 ML-DSA, FIPS 205의 SLH-DSA는 최종 표준입니다.
NIST는 FALCON 기반의 추가 전자서명 알고리즘을 FN-DSA라는 이름으로 FIPS 206에 담기 위한 작업도 진행하고 있습니다. 또한 추가 디지털서명 방식에 대한 별도 평가 과정도 계속되고 있습니다.
키 설정 분야에서는 2025년 3월 HQC가 추가 표준화 대상으로 선정됐습니다. HQC는 격자가 아니라 오류정정부호 계열의 다른 수학적 접근을 사용하는 알고리즘으로, ML-KEM에 문제가 발견될 경우를 대비한 별도의 선택지를 확보하려는 목적이 있습니다. NIST는 HQC 최종 표준을 2027년경 발표하는 일정을 제시했습니다.
기존 RSA·ECC와 비교하면?
| 구분 | RSA | ECC | 격자 기반 PQC |
|---|---|---|---|
| 보안 기반 | 큰 정수 소인수분해 문제 | 타원곡선 이산로그 문제 | LWE·Module-LWE 등 격자 관련 난제 |
| 현재 활용 | 인증서, 서명, 기존 시스템 등 | TLS, 인증서, 모바일·서명 등 | PQC 전환 및 신규 시스템 도입 확대 |
| 대규모 양자컴퓨터 영향 | Shor 알고리즘 위협 대상 | Shor 알고리즘 위협 대상 | 알려진 양자 공격에 견디도록 설계 |
| 주요 특징 | 오랫동안 사용된 공개키 암호 | 작은 키로 높은 효율 | PQC 목적, 비교적 큰 데이터 크기 고려 필요 |
| 대표 활용 | 암호화·서명 | 키 합의·서명 | ML-KEM 키 설정, ML-DSA 전자서명 |
여기서 ‘양자내성’도 ‘영원히 절대 깨지지 않는다’는 의미는 아닙니다.
암호 알고리즘은 지속적으로 분석되며 새로운 공격법이 발견될 가능성도 있습니다. NIST가 ML-KEM 외에 다른 수학적 기반의 HQC까지 준비하는 이유 역시 암호기술을 하나의 수학 문제에만 의존하지 않기 위해서입니다.
실제 우리 생활에는 어디에 적용될까?
PQC가 적용될 가능성이 높은 분야는 매우 넓습니다.
- HTTPS와 TLS 인터넷 통신
- 금융서비스
- 클라우드 서비스
- 기업 내부망과 VPN
- 전자서명과 인증서
- 소프트웨어·펌웨어 업데이트 서명
- 정부·공공기관 시스템
- 오랜 기간 보호해야 하는 개인정보와 기밀정보
이미 실험 단계만 있는 것도 아닙니다.
Cloudflare는 2026년 기준 자사 엣지와 원본 서버 사이 TLS 연결에서 X25519와 ML-KEM-768을 함께 사용하는 양자내성 하이브리드 키 합의를 지원하고 있으며 일부 환경에서는 ML-DSA도 지원하고 있습니다.
Google 역시 Chrome과 Android 등을 포함한 여러 환경에서 PQC 전환을 추진하고 있으며 2026년에는 자체 PQC 마이그레이션 목표 시점을 2029년으로 제시했습니다.
한국에서도 과학기술정보통신부와 KISA가 2025년에 이어 2026년에도 양자내성암호 시범전환 사업을 진행하고 있습니다. KISA 공고에는 산업 분야 정보시스템의 PQC 전환과 시험을 지원하는 내용이 포함돼 있습니다.
기존 암호를 한꺼번에 바꾸게 될까?
현실적으로는 어렵습니다.
새로운 암호기술을 전 세계 시스템에 한 번에 적용하면 호환성 문제가 생길 수 있기 때문입니다.
그래서 전환기에는 기존 암호 방식과 PQC를 함께 사용하는 ‘하이브리드 방식’이 중요한 전략으로 사용되고 있습니다.
예를 들어 기존 X25519 키 교환과 ML-KEM을 결합하면 두 기술 가운데 하나에 문제가 생겨도 다른 쪽에서 보안을 유지할 가능성을 확보할 수 있습니다. 실제 인터넷 서비스에서도 이러한 하이브리드 방식이 이미 활용되고 있습니다.
결국 중요한 것은 ‘암호 민첩성’, 즉 앞으로 암호 알고리즘이 바뀌더라도 전체 시스템을 새로 만들지 않고 비교적 유연하게 교체할 수 있는 구조를 마련하는 것입니다.
양자컴퓨터와 격자 기반 암호, 핵심만 정리하면
양자컴퓨터가 내일 당장 인터넷 암호를 무너뜨리는 상황은 아닙니다.
현재의 양자컴퓨터는 RSA와 ECC를 실용적으로 공격할 만큼 크고 안정적이지 않습니다.
하지만 충분히 강력한 양자컴퓨터가 등장하면 현재 널리 사용하는 일부 공개키 암호가 위협받을 가능성이 있기 때문에 세계는 이미 전환을 시작했습니다.
그 중심에 양자내성암호가 있고, 그중 대표적인 기술이 격자 기반 암호입니다.
ML-KEM과 ML-DSA가 NIST 정식 표준으로 등장했다는 것은 이 기술이 단순한 미래 연구 주제를 넘어 실제 인터넷과 정보시스템에 적용되는 단계로 들어가고 있다는 의미입니다.
지금 필요한 것은 ‘양자컴퓨터가 곧 모든 암호를 깬다’는 공포가 아니라 암호체계의 교체에는 오랜 시간이 걸리기 때문에 미리 준비하고 있다는 사실을 이해하는 것입니다.
5. 자주 묻는 질문 FAQ
Q1. 양자컴퓨터가 나오면 RSA 암호는 바로 사용할 수 없게 되나요?
아닙니다. 현재 양자컴퓨터는 RSA를 실용적으로 해독할 수 있는 수준이 아닙니다. 다만 충분히 크고 오류 보정이 가능한 양자컴퓨터에서 Shor 알고리즘이 실행될 수 있게 되면 RSA와 ECC 같은 공개키 암호가 위험해질 가능성이 있기 때문에 미리 PQC로 전환하는 것입니다.
Q2. 격자 기반 암호는 양자컴퓨터를 사용하는 기술인가요?
아닙니다. 일반 컴퓨터와 기존 네트워크에서도 사용할 수 있는 수학 기반 암호입니다. 미래 양자컴퓨터 공격에도 견디기 어렵도록 설계하는 것이 목표입니다.
Q3. ML-KEM과 Kyber는 서로 다른 기술인가요?
완전히 별개의 기술은 아닙니다. NIST가 선정한 CRYSTALS-Kyber를 기반으로 표준화한 알고리즘이 FIPS 203의 ML-KEM입니다. 표준화 과정에서 명칭과 세부 사양이 정리됐기 때문에 현재 표준을 이야기할 때는 ML-KEM이라는 이름을 사용하는 것이 정확합니다.
Q4. Dilithium과 ML-DSA의 관계는 무엇인가요?
CRYSTALS-Dilithium을 바탕으로 NIST가 표준화한 디지털 서명 알고리즘이 ML-DSA이며 FIPS 204에 규정돼 있습니다.
Q5. 일반 사용자도 지금 PQC를 직접 준비해야 하나요?
일반 사용자가 직접 암호 알고리즘을 설치할 필요는 거의 없습니다. 브라우저, 운영체제, 클라우드, 금융기관, 통신사 등이 업데이트하면서 사용자에게 자연스럽게 적용되는 경우가 많습니다. 반면 기업과 공공기관은 현재 어떤 암호를 어디에서 사용하는지 파악하고 장기적인 전환 계획을 준비할 필요가 있습니다. NIST도 암호 자산을 파악하는 ‘cryptographic inventory’를 PQC 전환의 중요한 준비 단계로 설명합니다.