RSA와 ECC의 종말은 이미 시작됐다
우리가 수십 년간 믿어온 RSA와 ECC(타원곡선 암호)는 충분히 발전한 양자컴퓨터 앞에서 무너질 수밖에 없습니다. 문제는 '언젠가'가 아니라 '생각보다 빠른 시점'에 현실이 될 수 있다는 점이에요.
이미 Cloudflare는 전체 트래픽의 대부분을 양자내성암호(PQC)인 ML-KEM으로 전환했고, 2029년까지 서명 알고리즘까지 완전히 양자내성 체계로 바꾸는 것을 목표로 하고 있습니다. 이 말은 즉, 지금 당장 우리 서비스의 인증 체계도 바꿔야 한다는 뜻입니다.
핵심 포인트: NIST가 8년간의 경쟁 끝에 2024년 표준화한 ML-DSA(서명)와 ML-KEM(암호화)이 현재 유일한 실전 선택지다.
왜 ML-DSA만으로는 부족한가?
ML-DSA는 훌륭한 알고리즘이지만, RSA/ECC와 비교하면 두 가지 문제가 있습니다.
- 크기가 크다: 서명 크기가 2,420바이트로 RSA의 256바이트보다 약 10배 큽니다.
- 유연성이 부족하다: 기존에 RSA로 가능했던 여러 트릭(예: 블라인드 서명, 임계 서명)을 그대로 구현하기 어렵습니다.
그래서 NIST는 더 나은 대안을 찾기 위해 9개의 새로운 서명 알고리즘을 3차 라운드로 진행 중입니다. 이 글에서는 그 경쟁 후보들을 상세히 분석하고, 각각이 실무에서 어떤 가치가 있는지 살펴보겠습니다.
근거자료에서 원문의 전체 데이터를 확인할 수 있습니다.
포스트퀀텀 서명 알고리즘 전격 비교
아래 표는 TLS에 가장 적합한 128-bit 보안 수준의 주요 후보들을 비교한 것입니다.
| 계열 | 알고리즘 | 공개키 (bytes) | 서명 (bytes) | 서명 시간 | 검증 시간 |
|---|---|---|---|---|---|
| 타원곡선 | Ed25519 (취약) | 32 | 64 | 0.15 | 1.3 |
| 인수분해 | RSA 2048 (취약) | 272 | 256 | 80 | 0.4 |
| 격자 | ML-DSA 44 (표준) | 1,312 | 2,420 | 1 (기준) | 1 (기준) |
| 해시 | SLH-DSA 128s (표준) | 32 | 7,856 | 14,000 | 40 |
| 격자 | FN-DSA 512 (예정) | 897 | 666 | 3 ⚠️ | 0.7 |
| 등증 | SQIsign I (후보) | 65 | 148 | 300 ⚠️ | 50 |
| 다변수 | MAYO one (후보) | 1,420 | 454 | 2.1 | 0.4 |
| 다변수 | SNOVA (후보) | 1,016 | 248 | 1.2 | 1.7 |
핵심 해석
- SQIsign: 서명 크기가 148바이트로 가장 작지만, 서명 생성이 매우 느리고 타이밍 부채널 공격에 취약한 구현이 어렵습니다. 오프라인 서명(CA, DNSSEC) 용도로 적합합니다.
- MAYO / SNOVA: 다변수 기반으로 서명이 작고 빠르지만, 공개키가 크거나 구조적 공격에 대한 우려가 있습니다. 특히 SNOVA는 반복적인 구조 변경으로 인해 아직 신뢰를 주기 어렵습니다.
- FN-DSA (구 Falcon): 크기와 속도가 우수하지만, 부동소수점 연산을 사용하는 안전한 구현이 매우 까다롭습니다. 실전 배포까지는 오랜 시간이 걸릴 것입니다.
# 개념 예시: ML-DSA 키 생성 및 서명 (Python + cryptography 라이브러리)
from cryptography.hazmat.primitives.asymmetric import ml_dsa
from cryptography.hazmat.primitives import hashes
# 키 생성 (ML-DSA-44)
private_key = ml_dsa.MLDSA44.generate()
public_key = private_key.public_key()
# 서명 생성
message = b"중요한 거래 내역"
signature = private_key.sign(message)
# 서명 검증
public_key.verify(signature, message)
print("서명 검증 성공! (양자내성 보안 적용)")
참고: 위 코드는 개념 설명용이며, 실제 라이브러리 API는 버전에 따라 다를 수 있습니다. Spotify와 Anthropic의 에이전틱 개발 사례처럼, 새로운 기술을 도입할 때는 실제 워크플로우에 맞는 점진적 적용이 중요합니다.
현실적인 마이그레이션 전략과 주의사항
1. 지금 당장은 ML-DSA로
결론부터 말하면, 새 알고리즘을 기다리지 말고 ML-DSA로 지금 전환을 시작해야 합니다. Cloudflare의 목표인 2029년 완전 전환을 기준으로 봐도, 신규 알고리즘(FN-DSA, MAYO 등)의 실전 배포는 2033년 이후가 유력합니다.
2. 하이브리드 전략이 답이다
완전한 전환까지는 기존 RSA/ECC와 ML-DSA를 함께 사용하는 하이브리드 방식이 안전합니다. 다만, 이 경우 다운그레이드 공격(downgrade attack)에 취약해질 수 있으므로, 기존 알고리즘을 완전히 비활성화하는 단계까지 계획에 포함해야 합니다.
3. 국내 생태계에서의 적용 맥락
국내 공공기관이나 금융권은 아직 PQC 전환에 대한 구체적인 로드맵이 부족한 상황입니다. 하지만 2030년까지는 규제가 강화될 가능성이 높으므로, 지금부터 인증서 체계와 TLS 설정을 점검하고 내부 테스트를 시작하는 것이 좋습니다. 특히 한국인터넷진흥원(KISA)의 가이드라인을 주기적으로 확인하세요.
4. 이 기술의 한계 및 주의사항
- ML-DSA는 크기가 크다: 대역폭이 제한된 환경(IoT 등)에서는 비효율적일 수 있습니다.
- FN-DSA의 함정: 서명 생성 시 부동소수점 연산의 미세한 차이로 개인키가 노출될 수 있습니다. 반드시 안전한 고정소수점 구현을 사용해야 합니다.
- 다변수 기반 알고리즘의 불확실성: MAYO와 SNOVA는 아직 공격에 대한 충분한 검증이 이루어지지 않았습니다. 표준화가 되더라도 추가 라운드가 필요할 수 있습니다.
결론: 지금은 '전환'이 아닌 '준비'의 시간
포스트퀀텀 서명 알고리즘의 미래는 분명 밝습니다. SQIsign, MAYO, 그리고 증명 기반(FAEST, MQOM) 스킴들은 각자의 강점을 가지고 경쟁하고 있습니다. 하지만 현실적으로 2029년까지 우리가 쓸 수 있는 선택지는 ML-DSA뿐입니다.
따라서 지금 필요한 것은:
- ML-DSA로의 조기 전환 테스트 (하이브리드 모드 포함)
- NIST 3차 라운드 결과에 대한 지속적인 모니터링
- 내부 시스템의 암호화폐 '유연성' 확보 (알고리즘 교체가 용이하도록 설계)
양자컴퓨터의 위협은 더 이상 공상과학이 아닙니다. 우리가 선택할 수 있는 건 '미리 준비하는 것' 아니면 '급하게 대응하는 것'뿐입니다.