150. 코드 기반 PQC (BIKE / HQC / Classic McEliece)

⚠️ 이 문서는 양자 내성 암호(PQC)의 주류인 '격자(Lattice)' 수학이 훗날 박살 날 경우를 대비하여, 1970년대부터 증명된 "오류 정정 코드(Error-Correction Code)에 일부러 노이즈를 섞고 숨겨서 해커가 복구하지 못하게 만드는 수학"을 활용한 든든한 플랜 B(백업 KEM 알고리즘)인 코드 기반 암호들을 다룹니다.

핵심 인사이트 (3줄 요약)

본질: 코드 기반 암호(Code-Based Cryptography)는 CD나 통신망에서 데이터가 깨졌을 때 복구하기 위해 쓰는 '오류 정정 부호(Error-Correcting Code)' 이론을 역이용하여, 일부러 평문에 복잡한 규칙의 에러(노이즈)를 섞어 암호문을 만드는 키 교환(KEM) 메커니즘이다.

가치: 1등 표준인 격자 기반(Kyber)이 수학적으로 무너졌을 때(단일 실패 점)를 대비한 가장 유력한 예비 후보(Alternate Candidate) 그룹이다. 특히 Classic McEliece는 1978년에 발명되어 무려 40년 넘게 온갖 해커들의 공격을 버텨낸 암호학계의 가장 검증된 '초고대 콘크리트 벙커'다.

한계/융합: 방어력은 미쳤지만, 공개키 크기가 자그마치 **수백 킬로바이트(KB)에서 1메가바이트(MB)**에 달하는 경악스러운 뚱뚱함(Fat Key)을 자랑한다. 인터넷 통신(TLS)엔 도저히 쓸 수 없으므로, 아주 가벼운 후발주자들(BIKE, HQC)이 치열하게 성능 최적화를 융합하며 NIST 4라운드 결승전에서 마지막 남은 티켓을 다투고 있다.

Ⅰ. 개요 및 왜 또 다른 KEM이 필요한가? (Context & Necessity)

NIST는 2024년에 KEM(키 교환) 분야의 최종 1등 왕좌를 **ML-KEM(Kyber, 격자 기반)**에게 씌워주었다. 하지만 아키텍트들의 뺨에는 식은땀이 흘렀다. "KEM 1등이 격자 기반 딱 하나뿐이야? 만약 5년 뒤에 러시아의 천재 수학자가 격자 수학 푸는 지름길을 뚫어버리면, 전 세계 인터넷 통신이 단 하루 만에 다 붕괴하는 거 아냐?"

서명(Signature) 쪽에는 격자가 무너지면 쓸 해시 기반 백업(SPHINCS+)이 준비되어 있었지만, 키 교환(KEM) 쪽에는 믿을 만한 비-격자(Non-Lattice) 백업이 없었다. 그래서 NIST는 공모전을 종료하지 않고, **"격자 수학을 쓰지 않는 완전히 다른 원리의 KEM(키 교환) 알고리즘들을 추가로 모아 4라운드 패자부활전을 열겠다!"**고 선언했다. 이 패자부활전 무대를 휩쓸고 있는 유력한 다크호스들이 바로 '코드(Error-Correction Code) 기반 암호' 3형제인 Classic McEliece, BIKE, HQC다.

📢 섹션 요약 비유: 왕(NIST)이 "전투기(Kyber)를 1등 무기로 뽑았지만, 만약 적군이 대공 미사일을 발명해 전투기 부대가 전멸하면 어쩌지?" 고민하다가, 하늘을 날지 않고 땅으로 뚫고 들어가는 완전히 다른 원리의 '땅굴 굴착 로봇(코드 기반 암호)'들을 비밀 지하 창고에 플랜 B 무기로 몰래 개발시키고 있는 상황입니다.

Ⅱ. 코드 기반 암호의 원리: 오류 정정 부호의 역발상

코딩 이론(Coding Theory)에서, 통신 중 데이터에 잡음(에러)이 섞이면 수신자는 '패리티 비트(Parity Bit)' 같은 힌트를 통해 원래 글자를 유추해 복원(Decoding)한다.

코드 기반 암호는 이 복원 규칙을 해커의 머리를 부수는 미로로 개조했다.

주인 (개인키): 복잡한 오리지널 오류 복원 규칙(수학 매트릭스)을 혼자만 가지고 있다.
주인 (공개키): 이 오리지널 규칙을 수만 번 섞고 꼬아서 엉망진창으로 만든 '가짜 복원 규칙(공개 매트릭스)'을 전 세계에 뿌린다.
송신자 (암호화): 주인의 엉망진창 규칙을 가져다가 평문 데이터에 일부러 무작위 오류(에러, $e$)를 잔뜩 추가해서 암호문을 만든 뒤 던진다.
해커 (역산 불가, 신드롬 디코딩 문제): 해커가 암호문을 가로채서 에러를 지우고 원본을 보려 한다. 하지만 주인이 뿌린 엉망진창 복원 규칙표로는 이 에러를 수정하는 것이 NP-Hard(우주가 멸망할 때까지 못 푸는 문제)라는 사실이 수학적으로 증명되어 있어 해독이 100% 불가능하다!
주인 (복호화): 암호문을 받으면, 엉망진창 표 대신 자기가 원래 숨겨둔 '깔끔한 오리지널 복원 규칙(개인키)'을 쓱 꺼내서, 섞인 에러를 1초 만에 깔끔하게 치료(디코딩)하고 원래 평문을 뽑아낸다.

Ⅲ. 코드 기반 PQC 3형제의 특징과 극한의 트레이드오프

현재 NIST 4라운드에서 피 터지게 심사받고 있는 세 가지 유망주다.

1. Classic McEliece (클래식 맥엘리스) - 40년 숙성 콘크리트

1978년 로버트 맥엘리스가 발명했다. RSA 탄생 1년 뒤에 나온 미친 고인물이다.
장점: 양자 컴퓨터 커녕 일반 컴퓨터 해커들에게 40년 넘게 두들겨 맞았는데도 수학적 뼈대(Goppa Code)가 단 한 번도 금이 간 적 없는 우주 최강의 신뢰성과 맷집을 자랑한다. 암호문 캡슐의 크기도 128바이트로 깃털처럼 가볍다.
치명적 단점 (공개키 비만증): 공개키(자물쇠)의 덩치가 무려 **1MB (1,000,000 바이트)**다! 접속할 때마다 서버가 1MB짜리 키를 던져주어야 한다. 일반 웹 트래픽(TLS)에 이걸 얹었다간 모바일 통신망이 그날로 마비된다. 따라서 통신보다는 한 번 다운로드해 두고 평생 쓰는 "펌웨어 칩 서명/키 세팅" 용도로만 쓰일 운명이다.

2. BIKE (Bit Flipping Key Encapsulation) - 밸런스형 차세대

맥엘리스의 미친 1MB 공개키 덩치를 줄여보려고 QC-MDPC라는 수학적 꼼수(순환 코드)를 동원했다.
장점: 1MB였던 공개키를 고작 1.5KB~3KB 수준으로 기적의 다이어트를 시켰다. 이 정도면 1등인 Kyber(800바이트)와 비벼볼 만해서 TLS 1.3 핸드셰이크에 올릴 수 있는 강력한 후보가 되었다.

3. HQC (Hamming Quasi-Cyclic) - 수학적 증명 철저형

BIKE와 비슷하게 키 크기를 2KB 수준으로 쥐어짰지만, 수학적 접근법(해독 에러율 증명)이 약간 다르다.
BIKE가 가끔(수백만 번 중 한 번) "어? 에러 복구가 안 돼서 암호가 안 풀리네?(복호화 실패)" 하는 미세한 에러 징후를 보이는 반면, HQC는 수학적 증명이 너무나 완벽하여 복호화 실패가 0%로 떨어지는 강박적인 안정성을 보장한다. (대신 통신 대역폭을 조금 더 많이 잡아먹는다.)

┌──────────────────────────────────────────────────────────────────────────────┐
│           PQC 키 교환(KEM) 플랜 B 예비 후보들의 스펙 비교 시각화             │
├──────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│ [ 🚀 ML-KEM (Kyber) - 현재 부동의 1등 표준 (격자 기반) ]                     │
│   공개키 크기: 800 Bytes / 캡슐 크기: 768 Bytes                              │
│   평가: 가볍고 빠름! 완벽함. 단, 10년 뒤 격자 수학이 털릴 공포가 살짝 존재.  │
│                                                                              │
│ ───────────────── [ 패자부활전 플랜 B 후보들 (코드 기반) ] ───────────────── │
│                                                                              │
│ [ 🦖 Classic McEliece - 40년 묵은 화석 괴물 ]                                │
│   공개키 크기: ★ 1,000,000 Bytes (1MB) ★ / 캡슐 크기: 128 Bytes              │
│   평가: 절.대.안.뚫.림. 근데 열쇠가 너무 무거워서 인터넷 통신 불가 ☠️        │
│                                                                              │
│ [ 🚴 BIKE / 🛡️ HQC - 신형 다이어트 로봇 ]                                    │
│   공개키 크기: 1,500 ~ 2,200 Bytes / 캡슐 크기: 약 1,500 Bytes               │
│   평가: 어떻게든 열쇠를 작게 만들어서 1등(Kyber)이 털리는 날 그 자리를 즉시  │
│        꿰차고 들어가려고 칼을 갈고 있는 가장 완벽한 벤치 멤버!               │
└──────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 암호학에서 특정 수학 이론(예: 격자) 하나에 전 세계 시스템이 올인(All-in)하는 것은 국운을 건 도박이다. NIST가 BIKE나 HQC 같은 코드 기반 암호를 계속 밀어주며 표준화를 준비하는 이유는, 인프라 설계자들이 언제든 "Kyber와 BIKE를 동시에 섞어서 쓰는 하이브리드 모드"를 구성하여 0.001%의 재앙 확률마저 0%로 영원히 밀봉해 버릴 수 있는 '플랜 B(Backup)' 무기를 손에 쥐여주기 위함이다.

📢 섹션 요약 비유: 1번 자물쇠(Kyber)는 최신 디지털 도어락입니다. 빠르고 멋지지만 누군가 만능키를 발명할지 몰라 불안합니다. 2번 자물쇠(Classic McEliece)는 1톤짜리 강철 빗장입니다. 40년 동안 한 번도 안 털렸지만, 문을 열 때마다 허리가 부러집니다. 그래서 1톤 강철을 압축 기술로 줄여 가볍게 만든 신형 티타늄 빗장(BIKE, HQC)을 보조 자물쇠로 달기 위해 테스트 중인 겁니다.

Ⅳ. 결론

"가장 오래된 아이디어가 가장 파괴적인 위협 앞에서 마지막 피난처가 되다." Classic McEliece와 그 후손들(BIKE, HQC)이 쓰는 오류 정정 수학은 반세기 전 CD-ROM과 우주 탐사선 보이저호가 사진을 보낼 때 쓰던 낡은 통신 공학 이론이었다. 하지만 해커의 에러 유추를 역으로 틀어막는 이 천재적인 비대칭 구조 덕분에, 코딩 이론은 양자 컴퓨터라는 인류 최대의 괴물 앞에서도 흠집 하나 나지 않는 완벽한 방공호로 부활했다. 비록 지금 당장은 1등 단상의 자리를 Kyber(격자)에게 내주었지만, PQC 시대의 장기적인 신뢰 아키텍처를 그리는 엔지니어들의 머릿속에는 항상 이 견고한 코드 기반의 백업 플랜이 묵직하게 자리 잡고 있다.

📌 관련 개념 맵

전체 분류: PQC (Post-Quantum Cryptography) KEM (키 캡슐화 메커니즘) 플랜 B
기반 수학: 코드 기반 암호 (Code-based Cryptography), 신드롬 디코딩 (Syndrome Decoding)
대비 개념 (현재 1등): ML-KEM (Kyber - 격자 기반 수학)
극한의 트레이드오프: 해독의 절대 안전성(40년 검증) ↔ 극도로 거대한 공개키 크기(Classic McEliece의 한계)

👶 어린이를 위한 3줄 비유 설명

양자 로봇을 막기 위해 1등으로 뽑힌 '카이버' 자물쇠가 혹시라도 부서질까 봐 무서워서, 어른들은 창고에서 40년 된 엄청 무겁고 절.대. 안 부서지는 '맥엘리스'라는 거북이 자물쇠를 꺼내왔어요.
이 거북이 자물쇠는 너무 튼튼하지만 무게가 1톤(1MB)이나 돼서 도저히 들고 다니며 쓸 수가 없었죠.
그래서 마법의 압축 기계로 거북이의 튼튼함은 살리면서 깃털처럼 가볍게 찌부러뜨린 '바이크(BIKE)'와 'HQC'라는 새끼 거북이들을 만들어서, 카이버가 뚫리는 비상사태에 짠! 하고 쓰려고 훈련시키고 있답니다!