양자컴퓨터 시대의 자물쇠: 포스트양자암호 표준화 경쟁

왜 지금 포스트양자암호인가

공개키 암호 체계는 크게 두 가지 수학적 난제에 의존한다. RSA는 큰 수의 소인수 분해, 타원곡선 암호(ECC)는 이산로그 문제다. 1994년 피터 쇼어가 고안한 알고리즘은 충분한 큐비트를 갖춘 양자컴퓨터가 이 두 문제를 다항식 시간 안에 풀 수 있음을 보였다. 현재 상용 양자컴퓨터는 아직 그 수준에 미치지 못하지만, "지금 수집해 나중에 해독(Harvest Now, Decrypt Later)" 공격이 현실적 위협으로 거론된다. 암호화된 트래픽을 지금 저장해 두었다가 강력한 양자컴퓨터가 등장하는 시점에 복호화하는 전략이다. 기밀 유효 기간이 10~20년인 정부 문서나 금융 계약이라면 지금 당장 대응이 필요하다는 논리다.

NIST 표준화 경쟁: 8년간의 여정

NIST는 2016년 PQC 후보 알고리즘 공모를 시작해 4라운드에 걸친 공개 분석을 진행했다. 수십 개국 암호학자들이 제출 알고리즘에 대해 공격·검증·반박을 반복하는 과정에서 상당수 후보가 탈락했다. 가장 극적인 사례는 4라운드까지 생존했던 SIKE(초특이 타원곡선 키 캡슐화)로, 2022년 단일 코어 CPU로 한 시간 만에 깨지는 고전 공격이 발표되면서 퇴출됐다.

최종 선정된 표준은 세 종이다. ML-KEM(구 CRYSTALS-Kyber)은 키 캡슐화 메커니즘으로 격자(lattice) 기반 수학에 의존한다. ML-DSA(구 CRYSTALS-Dilithium)와 SLH-DSA(구 SPHINCS+)는 디지털 서명 알고리즘이다. ML-DSA 역시 격자 기반, SLH-DSA는 해시 함수만을 원시로 사용하는 스테이트리스 해시 기반 서명이다. NIST는 추가 다양성을 위해 격자 기반이 아닌 코드 기반 알고리즘인 HQC를 5라운드 후보로 유지하고 있다.

격자 기반 독점과 다양성 논쟁

확정된 주요 표준 두 개가 모두 격자 문제(모듈 격자 위의 LWE 변종)에 기반한다는 점은 암호학계에서 꾸준히 논의되는 사안이다. 격자 문제 자체에 예상치 못한 고전 알고리즘 취약점이 발견될 경우 두 표준이 동시에 흔들릴 수 있기 때문이다. SLH-DSA가 해시 기반으로 포함된 이유도 이 다양성 확보 논리다. 코드 기반(HQC, Classic McEliece)·다변수 다항식 기반 알고리즘들은 일반적으로 공개키 크기가 크거나 서명 크기가 불리해 실용성 측면에서 격자 기반에 뒤처진다. 이 트레이드오프가 표준 포트폴리오 구성의 핵심 긴장이다.

국가별 독자 행보와 상호운용성

미국 NIST 표준과 별개로 각국이 독자 알고리즘을 추진하고 있다. 중국은 SM 계열 국가 암호 표준을 운영하며 PQC 영역에서도 독자 알고리즘 연구를 진행 중이다. 유럽 ETSI와 ISO/IEC도 별도 표준화 트랙을 운영하나, 실질적으로 NIST 알고리즘을 준용하는 방향으로 수렴하는 흐름이다. 한국 국가정보원과 KISA는 국내 암호 모듈 검증 체계(KCMVP)에 PQC 알고리즘을 어떻게 편입할지 검토 중이며, 금융·공공 분야의 인증서 체계 전환이 중기 과제로 부상해 있다.

TLS 1.3, SSH, IPsec 등 기존 프로토콜에 PQC를 통합하는 하이브리드 방식도 표준화 논의가 진행 중이다. 고전 암호와 PQC를 병렬로 협상해 둘 다 안전할 때만 연결을 수립하는 방식으로, 이행 과도기의 현실적 선택지로 꼽힌다. Google, Cloudflare 등은 이미 일부 서비스에서 하이브리드 키 교환을 시험 운영하고 있다.

이행의 현실: 기술 부채와 암호 민첩성

표준이 나왔다고 전환이 즉각 이루어지지는 않는다. 수십 년 된 레거시 시스템에는 하드코딩된 알고리즘 식별자, 고정 크기 키 버퍼, 하드웨어 보안 모듈(HSM) 펌웨어 제약이 산재한다. ML-KEM의 공개키(1184바이트)는 RSA-2048(256바이트)보다 훨씬 크며, 이는 핸드셰이크 지연과 패킷 단편화 문제를 유발할 수 있다. 특히 IoT·임베디드 환경에서 메모리·전력 제약이 심각한 걸림돌이다. 암호학계가 강조하는 '암호 민첩성(cryptographic agility)'—알고리즘을 소프트웨어처럼 교체 가능하게 설계하는 원칙—이 이 맥락에서 재조명받고 있다.