양자 컴퓨터가 깨기도 전에, 암호는 이미 바뀌었다

아직 존재하지 않는 컴퓨터를 막기 위해, 전 세계의 웹은 조용히 새 자물쇠로 갈아 끼우고 있다. 포스트퀀텀 암호의 논리와 현주소를 정리한다.

포스트퀀텀 암호(post-quantum cryptography)라는 말은 종종 공포의 언어로 소비된다. "양자 컴퓨터가 모든 암호를 깬다"는 헤드라인이 주기적으로 돌고, 그때마다 당장 무언가를 해야 할 것 같은 긴장이 흐른다. 그러나 이 분야의 실제 논리는 패닉과 거리가 멀다. 핵심은 단순하다. 충분히 큰 양자 컴퓨터는 아직 존재하지 않지만, 언젠가 등장할 작지만 무시할 수 없는 가능성이 있다. 그 가능성 하나만으로도 지금 행동할 이유는 충분하다.

01패닉 버튼은 아직 누르지 않아도 된다

오늘날 우리가 인터넷에서, 그리고 거의 모든 컴퓨터 시스템에서 하는 일의 바탕에는 암호가 깔려 있다. 그리고 그 암호의 상당 부분은, 만약 충분히 큰 양자 컴퓨터가 만들어진다면 특정한 공격에 취약하다. 여기서 두 단어가 중요하다. 만약, 그리고 충분히 큰이다.

그런 컴퓨터는 지금 없다. 그리고 그것이 20년 뒤든 30년 뒤든 등장할지, 아니면 영영 등장하지 않을지는 아무도 단언하지 못한다. 보수적으로 잡아도, 심지어 야심차게 잡아도 그 시간 척도는 '수십 년' 단위로 이야기된다. 그러니 적절한 질문은 "언제 깨지는가"가 아니라 "언제, 얼마나 대비할 것인가"이다.

02양자 컴퓨터는 지금 어디까지 왔나

오늘날 가장 큰 양자 컴퓨터들이 안정적으로 다루는 오류 정정(error-corrected) 큐비트는 한 줌에 불과하다. 물리 큐비트 수백 개를 늘어놓은 기계는 있지만, 잡음을 견디고 실제 계산에 쓸 수 있는 '논리 큐비트(logical qubit)'로 환산하면 그 수는 급격히 줄어든다.

반면 현재 널리 쓰이는 2048비트 RSA 키를 깨려면 이상적인 양자 컴퓨터 기준으로 약 4,000개 수준의 논리 큐비트가 필요하다는 것이 고전적인 추정이다. 이 숫자는 2003년 스테판 보르가르(Stéphane Beauregard)가 제시한 회로(2n+3큐비트)에서 나온 것으로, 2048비트라면 4,099개가 된다. 물리 큐비트로 환산하면 규모는 훨씬 커진다. 2019년 크레이그 기드니(Craig Gidney)와 마르틴 에케로(Martin Ekerå)는 약 2,000만 개의 물리 큐비트로 8시간이면 가능하다고 추정했고, 2025년 기드니는 같은 가정 아래 100만 개 미만으로 약 일주일이면 된다며 추정치를 끌어내렸다. 추정이 6년 사이 스무 배 줄었다는 사실 자체가 시사적이다. 오늘 도달 불가능해 보이는 수치가 내일도 그러리라는 보장은 없다.

요지는 이렇다. 지금 우리는 필요한 규모에서 한참 멀리 있다. 그러나 그 거리는 고정된 벽이 아니라, 알고리즘과 오류 정정 기술이 매년 갉아먹고 있는 거리다.

03두 개의 칼 — 그로버와 쇼어

양자 컴퓨터가 암호에 위협이 되는 통로는 사실상 두 개의 알고리즘이다. 그리고 이 둘이 우리 암호 체계에 미치는 영향은 전혀 다르다. 이 차이를 이해하는 것이 포스트퀀텀 논의의 절반이다.

먼저 그로버 알고리즘(Grover's algorithm)은 탐색 문제의 실행 시간을 제곱근으로 줄인다. 가령 128비트 AES 키를 무차별 대입으로 깨려면 고전 컴퓨터에서는 2의 128제곱 번의 시도가 필요한데, 그로버는 이를 2의 64제곱 수준으로 낮춘다. 2의 64제곱은 살짝 불편한 영역이다. 그러나 해법은 간단하다. AES에는 256비트 키 변형이 있고, 여기에 그로버를 적용해도 2의 128제곱에 그쳐 여전히 깰 수 없다. 키 길이를 늘리는 것만으로 방어가 끝난다. 대칭키 암호와 해시 함수가 양자에 견딘다고 보는 이유가 여기에 있다.

문제는 쇼어 알고리즘(Shor's algorithm)이다. 1994년 피터 쇼어가 발표한 이 알고리즘은 큰 정수를 다항 시간(polynomial time) 안에 인수분해하고, 이산로그(discrete logarithm) 문제까지 푼다. 큰 수 N이 두 소수 p와 q의 곱이라는 사실은 알아도, 고전 컴퓨터로 p와 q를 알아내기란 사실상 추측에 가깝다. RSA의 안전성은 바로 이 어려움에 기대고 있다. 그런데 쇼어가 이 인수분해를 빠르게 해치운다면, 인증서를 위조하고, 통신 세션을 가로채고, 그 키로 보호되던 데이터를 해독하는 일이 줄줄이 가능해진다. 타원곡선(elliptic curve) 문제나 디피-헬만(Diffie-Hellman) 키 교환처럼 이산로그에 기댄 방식도 함께 무너진다.

04오지도 않은 미래를 왜 지금 대비하나

여기서 자연스러운 반문이 나온다. 컴퓨터가 30년 뒤에야 나온다면, 30년 뒤에 바꾸면 되지 않나. 이 반문을 무너뜨리는 개념이 '지금 수집, 나중에 해독'(Harvest Now, Decrypt Later)이다.

어떤 공격자가 — 이를테면 한 국가가 — 다른 나라의 통신을 모두 들여다보고 싶다고 하자. 지금은 그 암호를 풀 수 없다. 큰 수를 인수분해할 수 없기 때문이다. 그러나 방법이 있다. 오늘 오가는 암호화된 트래픽을 통째로 가로채 거대한 저장소에 쌓아 두는 것이다. 그리고 20년 뒤, 그 수를 풀 수 있는 기계가 등장하면 한꺼번에 해독한다.

내 신용카드 번호나 여권 번호처럼 몇 년 안에 만료되는 정보라면 이런 수집은 무의미하다. 그러나 30년이 지나도 가치가 남는 비밀 — 정부의 전략 문서, 군사 기밀, 장기 산업 기술 — 을 다루는 쪽이라면 사정이 다르다. 그런 데이터는 지금 새는 순간 미래에 해독될 시한폭탄이 된다. 새 암호로 갈아 끼우는 것은 곧 미래의 어느 시점에 등장할 양자 컴퓨터 앞에서 "관심 없다"고 어깨를 으쓱할 수 있게 만드는 일이다.

05새 암호는 어디서 왔나 — 표준화 경쟁과 SIKE의 추락

그렇다면 취약한 방식들이 한결같이 인수분해나 이산로그에 기대고 있다면, 그 함정을 피하려면 어디로 가야 하나. 이 질문에 답하기 위한 작업이 2016년부터 본격화됐다. 미국 국립표준기술연구소(NIST)가 그해 포스트퀀텀 암호 표준화 경쟁을 선언하면서, 전 세계 연구자들이 후보 알고리즘을 제출하고 서로의 것을 깨뜨리며 검증하는 라운드가 거듭됐다.

그 결과 2024년 8월 13일, NIST는 첫 세 건의 표준을 확정했다. 일반 암호화를 위한 키 캡슐화 방식 FIPS 203 (ML-KEM), 전자서명을 위한 FIPS 204 (ML-DSA), 그리고 다른 안전성 가정을 쓰는 예비 서명 표준 FIPS 205 (SLH-DSA)이다. 각각 크리스털스-카이버(CRYSTALS-Kyber), 크리스털스-딜리시움(CRYSTALS-Dilithium), 스핑크스플러스(SPHINCS+) 제출안에서 유래했다. NIST는 현행 알고리즘을 2030년까지 폐기 단계로 두고 2035년까지 전환을 마치도록 권고하고 있다.

이 과정이 매끄럽기만 했던 것은 아니다. 한때 유력한 후보였던 SIKE(초특이 아이소제니 키 캡슐화)는 2022년 7월 보우터 카스트릭(Wouter Castryck)과 토마스 데크루(Thomas Decru)의 공격으로 무너졌다. 그것도 양자가 아닌 고전 컴퓨터로, 다항 시간 안에 깨졌다. 가장 약한 매개변수는 단일 코어에서 약 한 시간 만에 키가 복구됐다. 자칫 이 알고리즘이 표준으로 선택됐을 수도 있었는데, 누군가가 치명적 약점을 찾아낸 것이다. 이것이 시사하는 바는 분명하다. 이 새 알고리즘들은 매우 새롭고, 충분히 검증되지 않았을 수 있으며, 그래서 신중하게 굴려 봐야 한다.

06격자와 해시 — 살아남은 수학

살아남은 후보들은 인수분해도 이산로그도 쓰지 않는 두 갈래의 수학에 뿌리를 둔다.

하나는 격자(lattice) 기반이다. 격자는 균일한 점들이 격자무늬로 늘어선 구조다. 평면 위라면 "원점에서 가장 가까운 격자점이 무엇이냐"는 질문은 너무 쉽다. 눈으로 보면 바로 보이기 때문이다. 그러나 격자를 볼 수 없고 차원이 수백·수천에 이른다면 이야기가 달라진다. '격자에서 가장 짧은 벡터', '가장 가까운 점'을 찾는 문제, 그리고 이와 맞닿은 '오류를 동반한 학습(Learning With Errors, LWE)' 문제가 새 암호들의 토대다. 이들이 RSA나 타원곡선보다 본질적으로 우월해서가 아니다. 격자 문제를 단번에 푸는 양자 알고리즘이 아직 알려져 있지 않기 때문이다. ML-KEM이 기대는 것이 바로 이 격자 계열의 모듈-LWE 문제다.

다른 하나는 해시(hash) 기반이다. 해시 함수의 일방향 성질을 이용해 서명 방식을 짤 수 있다. 거칠게 말하면, 미리 해시 값들을 공개해 두었다가 서명할 때가 되면 원래 메시지를 드러내어 "이건 나였다"고 증명하는 식이다. 해시는 그로버에도 안전하다. 256비트나 512비트 해시를 쓰면 비구조적 탐색의 사정거리 밖으로 벗어나기 때문이다. 이들은 마법이 아니라, 단지 양자든 고전이든 이를 이길 알고리즘이 현재로선 알려져 있지 않은 방식일 뿐이다. 그래서 30년 뒤에도 여전히 서 있을 가능성이 높다. NIST의 예비 표준 SLH-DSA가 바로 이 해시 계열이다.

07당신은 이미 이 암호를 쓰고 있다

가장 흥미로운 대목은, 우리 대부분이 자각하지 못한 채 이미 포스트퀀텀 암호를 쓰고 있다는 사실이다. 최신 브라우저로 구글 같은 사이트에 접속해 보안 정보를 들여다보면 키 교환 방식에 X25519MLKEM768이 찍혀 있을 가능성이 높다.

이 이름은 두 알고리즘을 이어 붙인 것이다. 앞의 X25519는 지난 5~10년간 써 온 평범한 타원곡선 키 교환이고, 뒤의 ML-KEM-768은 격자 기반의 포스트퀀텀 방식(옛 카이버)이다. 흥미로운 점은, 우리가 이 격자 방식이 20~30년 뒤 양자 컴퓨터에 정말 버틸지 확신하지 못한다는 것이다. 앞서 본 SIKE의 추락이 보여 주듯, 새 알고리즘에 숨은 고전적 약점이 뒤늦게 발견될 수도 있다. 격자 역시 절대적으로 신뢰할 수는 없다.

그래서 택한 답이 하이브리드다. 키 교환을 두 번 동시에 한다. 하나는 검증된 고전 방식으로, 하나는 포스트퀀텀 방식으로. 그렇게 얻은 두 공유 비밀을 이어 붙여 거기서 세션 키를 도출한다. 둘 중 하나가 미래에 깨지더라도 나머지 하나가 통신을 지킨다.

이 방식은 이미 인터넷의 기본값에 가깝다. 크롬은 2024년 11월(131 버전)부터 X25519MLKEM768을 기본 활성화했고, 파이어폭스·엣지도 뒤따랐다. 클라우드플레어(Cloudflare)의 측정에 따르면 2025년 3월 기준 자사 망을 지나는 HTTPS 트래픽의 약 38%가 이미 하이브리드 포스트퀀텀 키 교환을 쓰고 있었다. 시그널(Signal)의 PQXDH, 애플의 PQ3 같은 메시징 프로토콜도 같은 하이브리드 발상을 택했다. 양자 컴퓨터가 이 규모로 존재하지 않는다는 말은 사실이지만, 우리는 이미 그것이 등장해도 깨지지 않기를 바라는 암호를 쓰고 있는 것이다.

포스트퀀텀 암호라는 말은 우리가 지금 양자 시대에 들어섰다는 뜻이 아니다. 그것은 우리가 언젠가 양자 시대에 들어설지도 모를 미래를 대비하고 있다는 뜻이다. 충분히 큰 양자 컴퓨터가 정말 올지, 온다면 언제일지는 여전히 안갯속이다. 그러나 거의 일어나지 않을 일에도 보험을 드는 것이 합리적이듯, 작지만 무시할 수 없는 가능성 앞에서 미리 자물쇠를 바꿔 두는 일은 패닉이 아니라 평범한 신중함이다. 그리고 그 신중함은 이미, 당신이 이 글을 읽는 동안에도, 조용히 작동하고 있다.