양자 암호: 개발자가 실제로 알아야 할 것

찰스 베넷(Charles Bennett)과 질 브라사드(Gilles Brassard)는 양자 정보 과학에 대한 기초 연구로 튜링상을 받았습니다. 정확히는 1984년에 발표한 BB84 양자 키 분배 프로토콜 덕분입니다. 논문 발표부터 튜링상 수상까지 40년이 걸렸는데, 이는 양자 컴퓨팅의 이론 연구가 CS 커뮤니티에서 관련성을 인정받기까지 얼마나 오래 걸리는지를 잘 보여줍니다.

이들의 수상은 흥미로운 시점에 나왔습니다. RSA 암호를 깰 수 있는 양자 컴퓨터는 아직 존재하지 않으며, 앞으로 10년이 더 걸리거나 아예 나오지 않을 수도 있습니다. 그럼에도 암호 커뮤니티는 이미 전면적인 전환 모드에 들어갔습니다. NIST는 첫 번째 포스트 양자 암호 표준을 확정했고, 주요 브라우저들은 포스트 양자 키 교환을 테스트하고 있으며, Signal은 이미 실서비스에 도입했습니다. “언젠가 양자 컴퓨터가 암호를 깰 것이다”와 “지금 시스템을 바꿔야 한다” 사이의 간극은 이미 좁혀졌습니다.

양자 컴퓨터가 실제로 위협하는 것

양자 컴퓨팅과 암호학에 대한 대중적 보도는 대부분 “모든 암호가 뚫린다!”처럼 극단적으로 겁을 주거나, “절대 될 리 없다”처럼 무시하는 양극단입니다. 실제는 더 구체적이고 더 흥미롭습니다.

양자 컴퓨터는 비대칭 암호를 위협합니다. 큰 수의 소인수분해(RSA)나 이산 로그 계산(Diffie-Hellman, ECC)의 수학적 난이도에 기반한 시스템이 해당됩니다. 충분히 큰 양자 컴퓨터에서 실행되는 Shor 알고리즘은 이 문제들을 다항식 시간 안에 풀 수 있습니다. 즉, 고전 컴퓨터로는 수십억 년이 걸렸을 RSA-2048을 이론적으로는 양자 컴퓨터가 몇 시간 만에 깰 수 있다는 뜻입니다.

양자 컴퓨터는 대칭 암호에는 훨씬 덜 위협적입니다. Grover 알고리즘은 무차별 대입 검색에 제곱근 수준의 속도 향상을 주어, 사실상 키 길이를 절반으로 줄이는 효과가 있습니다. AES-256은 양자 공격자 기준으로 AES-128과 같아지며, 여전히 무차별 대입은 현실적이지 않습니다. AES-128은 64비트 보안 수준과 같아지는데, 우려되긴 하지만 재앙적인 수준은 아닙니다.

What's threatened by quantum computers:
BROKEN (by Shor's algorithm):
├── RSA (all key sizes)
├── Diffie-Hellman key exchange
├── Elliptic Curve Cryptography (ECDSA, ECDH)
└── DSA
WEAKENED (by Grover's algorithm):
├── AES-128 → effectively 64-bit security (upgrade to AES-256)
├── AES-256 → effectively 128-bit security (still secure)
└── SHA-256 → effectively 128-bit preimage resistance (still secure)
NOT AFFECTED:
├── One-time pads
├── Hash-based signatures (SPHINCS+)
└── Symmetric encryption with sufficiently large keys

실무적인 의미는 이렇습니다. TLS 핸드셰이크, SSH 연결, 코드 서명, 암호화폐, 디지털 서명 등 공개키 암호를 쓰는 모든 것은 양자 내성 알고리즘으로 옮겨가야 합니다. 대칭 암호화는 주로 키 길이만 늘리면 됩니다.

‘지금 수집하고 나중에 해독한다(Harvest Now, Decrypt Later)’ 문제

양자 컴퓨터가 아직 아무것도 못 깨는데도 마이그레이션이 시급한 이유가 바로 이것입니다. 국가 단위의 공격자들은 암호화된 트래픽을 지금 이미 기록하고 있을 가능성이 매우 높습니다. 양자 컴퓨터가 등장하면 그때 해독하려는 목적입니다.

20년 넘게 기밀을 유지해야 하는 데이터를 생각해 보세요. 외교 통신, 정보 보고서, 영업 비밀, 의료 기록 같은 것들입니다. 이 데이터를 오늘 RSA나 ECDH로 암호화했는데 15년 뒤 쓸 만한 양자 컴퓨터가 등장한다면, 암호는 소급해서 무너집니다. 데이터는 처음부터 취약했지만 아무도 그걸 몰랐을 뿐입니다.

이건 추측에 그치는 위협 모델링이 아닙니다. NSA는 기밀 시스템에 대해 양자 내성 알고리즘으로의 전환을 명시적으로 권고했습니다. 정보기관 커뮤니티의 전제는 국가 행위자들이 이미 암호화된 트래픽을 쌓아두고 있다는 것입니다. 기밀 유지 기간이 긴 데이터라면, 마이그레이션은 어제 했어야 했습니다.

포스트 양자 암호: NIST의 선택

NIST는 AES를 선정했던 것과 비슷하게, 여러 해에 걸친 공모전을 열어 포스트 양자 암호 알고리즘을 표준화했습니다. 수십 개의 후보를 평가한 끝에 세 가지 주요 알고리즘을 표준으로 정했습니다:

ML-KEM (Kyber) — 키 교환을 위한 키 캡슐화 메커니즘입니다. 격자 암호의 Module Learning With Errors(MLWE) 문제에 기반합니다. TLS 핸드셰이크 등에서 Diffie-Hellman과 ECDH를 대체하며, 빠르고 키 크기가 비교적 작아 범용 키 교환의 기본 추천입니다.
ML-DSA (Dilithium) — 디지털 서명 알고리즘으로, 역시 격자 암호에 기반합니다. 서명에서 RSA와 ECDSA를 대체합니다. 서명 크기는 ECDSA보다 큽니다(ECDSA 64바이트 대비 약 2.5KB). 이는 인증서 체인과 많은 서명을 전송하는 프로토콜에 영향을 줍니다.
SLH-DSA (SPHINCS+) — 해시 기반 디지털 서명 방식입니다. 격자 문제가 아니라 해시 함수의 보안성에 기반합니다. ML-DSA보다 느리고 서명도 크지만, 보안이 비교적 새로운 격자 기반 가정 대신 잘 알려진 해시 함수 가정에 의존합니다. 보수적인 대안입니다.

격자 기반 알고리즘(ML-KEM, ML-DSA)은 성능 때문에 선호되지만, 이들이 기반한 수학 문제는 RSA와 AES가 수십 년간 분석을 받아온 것에 비하면 상대적으로 새롭습니다. 격자 암호 분석에서 돌파구가 나와 이들이 약해질 가능성이 작지만 0은 아닙니다. SPHINCS+는 일종의 보험입니다. 보안이 30년 넘게 연구된 해시 함수에 기반하기 때문입니다.

이미 배포된 것들

포스트 양자 암호는 더 이상 이론이 아닙니다. 지금 여러분이 쓰는 실서비스에 이미 들어가 있습니다.

Chrome과 Firefox는 TLS 연결에 하이브리드 키 교환(X25519 + ML-KEM-768)을 사용합니다. ‘하이브리드’란 기존 고전 키 교환과 포스트 양자 키 교환을 함께 쓴다는 뜻이라, 둘 중 하나가 깨져도 연결은 여전히 안전합니다. 이로 인해 TLS 핸드셰이크가 약 1KB 늘어납니다.
Signal은 초기 키 교환에 포스트 양자 키 합의 프로토콜인 PQXDH를 도입했습니다. 이제 새로 시작하는 모든 Signal 대화는 포스트 양자 순방향 기밀성을 갖습니다.
Apple iMessage는 주기적인 리키(rekeying)를 포함한 포스트 양자 키 교환 방식인 PQ3를 도입했습니다. Apple은 이것이 자사 프레임워크에서 최고 등급인 ‘Level 3’ 보안을 제공한다고 주장합니다.
Cloudflare는 CDN에서 포스트 양자 키 교환을 지원합니다. Cloudflare 뒤에 있는 서비스라면, 여러분도 모르는 사이에 이미 ML-KEM을 쓰고 있을 수 있습니다.
AWS KMS는 키 관리 작업에 하이브리드 포스트 양자 TLS를 지원합니다.

개발자가 마주할 마이그레이션 과제

암호학을 사용하는 소프트웨어(사실상 거의 모든 소프트웨어)를 만든다면, 실제 마이그레이션이 어떤 모습인지 살펴보겠습니다.

TLS: 대부분 알아서 처리됨

애플리케이션이 OpenSSL, BoringSSL, Go의 crypto/tls 같은 표준 라이브러리로 TLS를 쓴다면, 포스트 양자 지원은 라이브러리 차원에서 추가되고 있습니다. 의존성 업데이트를 통해 자연스럽게 적용받게 됩니다. 주로 할 일은 오래된 TLS 라이브러리 버전에 고정(pinning)해 두지 않았는지 확인하고, 핸드셰이크 크기가 약간 커진 것을 시스템이 감당할 수 있는지 점검하는 것입니다.

크기 증가는 생각보다 중요합니다. ML-KEM-768은 TLS ClientHello 메시지를 약 1,100바이트 늘립니다. 일부 미들박스, 방화벽, 구현이 허술한 TLS 스택은 약 512바이트를 넘는 ClientHello를 제대로 처리하지 못합니다. Google이 포스트 양자 키 교환을 롤아웃하면서 연결의 약 0.5%가 미들박스 비호환 때문에 실패하는 것을 확인했습니다. 사용자가 기업 방화벽 뒤에 있다면 반드시 테스트해 보세요.

디지털 서명: 더 큰 파급력

포스트 양자 서명은 기존 방식보다 확연히 큽니다. ECDSA 서명은 64바이트인 반면, ML-DSA-65 서명은 약 3,300바이트입니다. SLH-DSA 서명은 17,000바이트를 넘기도 합니다. 이는 다음과 같은 연쇄 효과를 낳습니다:

X.509 인증서 체인이 훨씬 커집니다. ML-DSA 서명을 쓰는 3개 인증서의 일반적인 체인은 ECDSA보다 약 10KB 더 큽니다. 대역폭이 제한된 연결에서는 이것이 문제가 됩니다.
컴팩트한 서명에 의존하는 블록체인과 암호화폐 시스템은 확장성 문제에 직면합니다. 포스트 양자 서명을 쓰는 거래 하나가 50배 더 많은 공간을 차지합니다.
코드 서명, 패키지 서명, 소프트웨어 업데이트 검증은 기존 도구들의 크기 가정을 깨지 않으면서 더 큰 서명을 처리할 수 있어야 합니다.
인증서 투명성 로그, OCSP 응답, CRL 배포 목록이 모두 커집니다.

애플리케이션 계층 암호: 여러분의 문제

애플리케이션이 자체 암호 프로토콜을 구현한다면, 즉 종단간 암호화, 커스텀 키 교환, 서명된 토큰, 암호화된 스토리지 등을 쓴다면 마이그레이션을 적극적으로 계획해야 합니다. 일반적인 전략은 다음과 같습니다:

암호 의존성을 전수 조사하세요. RSA, ECDSA, ECDH, Diffie-Hellman을 사용하는 모든 지점을 찾으세요. 라이브러리, 키 관리 시스템, 인증 기관, 하드웨어 보안 모듈(HSM)까지 포함됩니다.
먼저 하이브리드 방식을 도입하세요. 고전 알고리즘과 포스트 양자 알고리즘을 결합합니다. 포스트 양자 알고리즘에 약점이 드러나면 고전 보안으로 되돌아갈 수 있고, 양자 컴퓨터가 등장하면 포스트 양자 보호를 이미 갖추게 됩니다.
검증된 라이브러리를 사용하세요. 포스트 양자 알고리즘을 직접 구현하지 마세요. liboqs(Open Quantum Safe)를 쓰면 됩니다. OpenSSL과 연동되며 ML-KEM, ML-DSA, SPHINCS+의 검증된 구현을 제공합니다.
성능 영향을 테스트하세요. 포스트 양자 연산은 대체로 빠릅니다(ML-KEM 키 생성은 ECDH와 비슷합니다). 다만 서명 검증은 느리고, 키와 서명 크기는 대역폭과 저장 공간에 영향을 줍니다.
암호 민첩성(crypto agility)을 계획하세요. 프로토콜을 깨뜨리지 않고 암호 알고리즘을 교체할 수 있도록 설계하세요. 나중에 끼워 넣기는 어렵고, 처음부터 설계에 담는 편이 훨씬 쉽습니다.

양자 키 분배(QKD)는 어떨까?

베넷과 브라사드가 튜링상을 받은 연구인 BB84는 양자 키 분배(QKD)입니다. 이는 완전히 다른 접근법입니다. 양자 컴퓨터가 풀 수 없는 수학 문제에 기대는 대신, 양자역학의 물리적 성질을 이용해 암호 키를 분배합니다. 키 교환을 도청하려는 시도는 양자 상태를 교란시키므로 탐지할 수 있습니다.

QKD는 이론적으로 아름답고, 계산 가정이 아닌 물리학에 기반해 증명 가능한 수준으로 안전합니다. 하지만 실제로는 심각한 한계가 있습니다. 전용 광섬유 링크가 필요하고(인터넷으로는 돌릴 수 없습니다), 양자 중계기(아직 대규모로는 존재하지 않습니다) 없이는 최대 거리가 수백 킬로미터에 불과하며, 비용도 엄청납니다. 중국은 베이징과 상하이 사이에 QKD 네트워크를 구축했지만, 신뢰할 수 있는 중계 노드에 의존하고 있어 그 목적이 어느 정도 퇴색됩니다.

당분간 실용적인 길은 포스트 양자 암호(고전 컴퓨터에서 돌아가는 수학 알고리즘)입니다. QKD는 고보안이 필요한 정부와 군사 링크에는 의미가 있지만, 여러분의 웹 애플리케이션에서 TLS를 대체하지는 않을 것입니다.

타임라인: 이게 실제로 언제 중요해질까?

RSA-2048을 깰 만큼 큰 암호학적으로 유의미한 양자 컴퓨터(CRQC)가 언제 나올지는 아무도 모릅니다. 추정은 2030년부터 ‘영원히 안 나온다’까지 다양하며, 대부분의 전문가는 2035~2040년 사이에 몰려 있습니다. 현재 가장 큰 양자 컴퓨터는 물리 큐비트가 약 1,000개 수준이고, RSA-2048을 깨려면 수백만 개의 오류 정정 논리 큐비트가 필요하다고 추정됩니다.

하지만 핵심은 정확히 언제인지가 중요하지 않다는 점입니다. 마이그레이션 자체에 몇 년이 걸립니다. 대형 조직은 암호 사용 현황을 조사하고, 라이브러리를 업데이트하고, 호환성을 테스트하고, 키와 인증서를 교체하고, 프로토콜을 갱신해야 합니다. NIST는 2035년까지 전환을 완료할 것을 권고합니다. 기업 소프트웨어 마이그레이션이 보통 5~10년 걸린다는 점을 고려하면, 지금 시작하는 것도 이미 늦었다고 볼 수 있습니다.

실질적인 조언은 지루하지만 옳습니다. TLS 라이브러리를 업데이트하고, 서명 마이그레이션을 계획하고, 가능한 곳에는 하이브리드 방식을 도입하고, 새 시스템에는 암호 민첩성을 내장하세요. 공황에 빠질 필요는 없지만, 시작은 해야 합니다. 가장 힘들어질 조직은 포스트 양자 마이그레이션을 비상사태가 닥칠 때까지 미래의 문제로 미뤄두는 곳들입니다.