1978년 알고리즘이 ISO 국제 표준이 되기까지: Classic McEliece와 양자내성암호의 현재

양자내성암호(PQC) 분야에 중요한 이정표가 세워졌습니다. 2026년 6월, 국제표준화기구(ISO)가 1978년에 처음 발표된 암호 알고리즘인 Classic McEliece를 공식 양자내성 암호 국제 표준으로 채택했습니다. 이 소식은 구글이 2029년 PQC 전환 완료를 선언하고, 새로운 미국 행정명령이 발효되는 등 예상보다 빠르게 다가오는 '큐데이(Q-Day, 양자컴퓨터가 현 암호 체계를 위협하는 시점)'를 배경으로 합니다.

이번 표준화가 왜 중요한지, Classic McEliece는 어떤 알고리즘이며, 그리고 지금 PQC 전환이 왜 더욱 시급해졌는지 자세히 알아보겠습니다.

ISO, Classic McEliece를 국제 암호 표준에 공식 편입

2026년 6월 5일, ISO는 비대칭 암호화 국제 표준인 ISO/IEC 18033-2를 개정하여, 양자컴퓨터에도 안전한 최초의 부호 기반(code-based) 알고리즘으로 Classic McEliece를 공식 추가했습니다. 같은 개정안에는 FrodoKEM도 함께 포함된 것으로 알려졌습니다.

이 표준은 ISO의 177개 회원국 모든 조직이 활용할 수 있게 되었으며, 이는 국제적으로 인정된 프레임워크 하에서 PQC를 도입할 수 있는 길을 열어준 것입니다. 국제 표준은 서로 다른 시스템 간의 비호환성 위험을 줄이고, 조달 부서와 규제 기관, 감사 담당자에게 공통된 기준점을 제공한다는 점에서 큰 의미를 가집니다.

Classic McEliece: 기원, 트레이드오프, 표준화에서의 역할

기원 (1978년)

로버트 J. 맥엘리스(Robert J. McEliece)는 1978년에 이 암호 시스템을 처음 발표했습니다. 이 시스템은 무작위 이진 Goppa 부호를 복호화하는 문제의 어려움에 기반을 두는데, 이 문제는 NP-난해(NP-hard)로 알려져 있으며 양자컴퓨터로도 효율적으로 풀 수 있는 방법이 아직 발견되지 않았습니다. 현재의 Classic McEliece는 원래 방식보다 개선된 니더라이터(Niederreiter) 방식을 사용하지만, 핵심 보안 가정은 동일합니다. 이 때문에 "현재까지 안전한 것으로 간주되는 가장 오래된 공개키 암호 방식" 으로 불립니다.

핵심 트레이드오프: 거대한 공개키

Classic McEliece의 가장 큰 약점은 공개키 크기입니다. 키 크기는 약 261KB에서 1.3MB에 달하며(일부 매개변수는 1,047,319바이트), 이는 수백 바이트 수준인 RSA나 ECC 키보다 수천 배나 큽니다. 따라서 IoT 기기, 스마트 카드, 제한된 대역폭을 가진 TLS 핸드셰이크 등에는 부적합합니다.

그러나 이러한 단점을 상쇄하는 강점은 그 안전성이 비할 데 없이 잘 입증되었다는 점입니다. 45년이 넘는 연구 기간 동안 실질적인 암호 분석적 개선이 발견되지 않았으며, McEliece 시스템의 보안 수준은 수많은 공격 시도에도 불구하고 놀랍도록 안정적으로 유지되어 왔습니다.

국제 표준화 과정에서의 역할

Classic McEliece는 현재 여러 표준화 기구에서 각기 다른 역할로 인정받고 있습니다.

기구	조치	일자
ISO	ISO/IEC 18033-2에 Classic McEliece 추가	2026년 6월 5일
NIST (美표준기술연구소)	4차 라운드 후보로 유지; 가장 보수적인 백업으로 간주	2026년 7월 보고서
IETF	IND-CCA2 보안 KEM으로 Classic McEliece 명시한 초안 발행	2026년 6월 23일
BSI (獨연방정보보안청)	기밀 데이터 장기 보호에 적합하다고 승인	2026년 6월
Mullvad VPN	이미 알고리즘 통합 완료	2026년 6월

Classic McEliece는 보수적인 백업 또는 2차 방어선으로 자리 잡았습니다. 만약 NIST가 이미 표준화한 격자 기반 방식(ML-KEM / CRYSTALS-Kyber)이 미래에 돌파될 경우, 부호 기반 암호는 수학적으로 독립적인 대안을 제공하기 때문입니다.

NIST가 먼저 표준화하지 않은 이유

흥미롭게도 NIST는 2025년에 Classic McEliece 표준화를 명시적으로 연기했습니다. 당시 NIST는 "NIST와 ISO의 동시 표준화는 호환되지 않는 표준을 만들 위험이 있다"고 밝히며, ISO 절차가 완료된 후 ISO 표준에 기반한 표준 개발을 고려하겠다고 언급했습니다. NIST는 다른 부호 기반 알고리즘인 HQC를 표준화 대상으로 선택했지만, Classic McEliece는 4차 라운드 후보로 남아 향후 표준화 가능성을 열어두고 있습니다.

PQC 전환 시급성을 높이는 최근 개발 사항

ISO의 표준화 자체만으로도 중요한 사건이지만, 더 큰 그림에서 볼 때 PQC 전환의 시급성은 몇 가지 중대한 변화로 인해 더욱 현실적인 문제가 되었습니다.

구글의 2029년 PQC 전환 마감 시한

2026년 3월 25일, 구글은 보안 엔지니어링 부사장 헤더 앳킨스(Heather Adkins)와 수석 암호 엔지니어 소피 슈미크(Sophie Schmieg) 명의의 블로그 게시글 "양자 최전선은 보이는 것보다 더 가까울 수 있다(Quantum frontiers may be closer than they appear)"를 통해, 2029년까지 모든 구글 시스템의 PQC 전환을 완료하겠다는 내부 목표를 공개했습니다. 이는 NSA의 2031년이나 NIST의 2035년보다 약 6년 앞당겨진 일정입니다. 구글은 양자 하드웨어와 오류 정정 기술이 예상보다 빠르게 발전한 점을 주요 요인으로 꼽았습니다.

타원 곡선 암호 공격에 필요한 큐비트 수 추정치 하락

구글의 업데이트된 일정에는 쇼어 알고리즘(Shor's algorithm)을 이용한 타원 곡선 암호(ECC) 공격에 필요한 물리적 큐비트 수 추정치가 크게 낮아진 사실이 배경이 되었습니다. 새로운 회로 최적화 기술로 인해 256비트 ECC를 공격하는 데 필요한 큐비트 수가 수백만 개에서 수십만 개 수준으로 줄어들 것으로 예측되면서, 양자컴퓨터의 현실적 위협 시점이 앞당겨진 것입니다.

Cloudflare의 유사한 대응

Cloudflare 역시 구글의 2029년 목표와 유사한 시점에 PQC 전환을 완료할 계획을 공개하며 긴박감에 동참했습니다. Cloudflare는 일찍이 X25519Kyber768 하이브리드 키 합의 등 양자내성 TLS를 도입해 왔으며, 이제 전체 프로덕션 환경으로의 전환을 가속화하고 있습니다.

'지금 수확해 나중에 해독(HNDL)' 위협의 현실화

구글은 이른바 '지금 저장해두고 나중에 해독'(store-now, decrypt-later) 위협을 전환 가속의 핵심 이유로 명시했습니다. 국가 차원의 공격자를 포함한 적대 세력들은 이미 오늘날의 암호로 보호된 트래픽(VPN 연결, 금융 데이터, 국가 기밀, 가상자산 통신)을 수집하고 있습니다. 이들은 양자컴퓨터가 가용해지는 순간 이를 해독할 의도를 가지고 있습니다. 따라서 데이터가 RSA나 ECC로 암호화된 지금 이미 위험에 노출되어 있으며, 해독이 가능해진 이후가 아닌, 그 전에 전환을 완료해야 하는 이유가 됩니다.

2026년 6월 미국 행정명령

2026년 6월, 바이든 행정부는 모든 미국 연방 기관이 PQC 전환을 가속화하고, 목록 작성, 평가 및 전환 계획에 대한 구속력 있는 기한을 설정하는 행정명령을 발표했습니다. 이는 2022년 양자 컴퓨팅 사이버보안 대비법과 2024년 NIST PQC 표준(FIPS 203/204/205)을 기반으로, 기존의 권고 사항을 연방 차원의 의무로 전환한 것입니다.

시사점: 이제는 실행만이 남았다

ISO의 공식 표준(Classic McEliece, FrodoKEM), NIST의 확정된 주요 알고리즘(ML-KEM, ML-DSA, SLH-DSA), 구글의 2029년 목표, 큐비트 추정치 하락, Cloudflare의 동조, 이미 진행 중인 HNDL 위협, 그리고 미국 행정명령까지. 이 모든 요소가 결합되어 PQC 전환의 시급성에 대한 계산이 근본적으로 바뀌었습니다.

이제 표준화 인프라는 갖춰졌습니다. 대부분의 조직에게 남은 과제는 대규모 실행입니다. 즉, 암호 자산을 목록화하고, 위험도가 높은 시스템(인증, 장기 보관 데이터, VPN 등)에 우선순위를 두고, 2029년 이전에 하이브리드 또는 PQC 알고리즘으로의 전환을 시작하는 것입니다.

Classic McEliece는 대부분의 조직이 일상적인 TLS에 사용할 알고리즘은 아닐 것입니다. 키 크기 문제로 대부분의 사용 사례에 비실용적이기 때문입니다. 하지만 장기 데이터 보호, 고보안 정부 통신, 그리고 보안의 확실성이 대역폭보다 중요한 애플리케이션에 있어서, 이제 막 표준이 된 1978년의 이 알고리즘은 인터넷이 절실히 필요로 하는 '가장 안전한 백업' 역할을 톡톡히 해낼 것입니다.