양자컴퓨터 시대의 암호학, 격자 기반 암호가 새 표준이 된 이유

양자컴퓨터가 RSA를 깬다고?

우리가 지금 인터넷에서 쓰는 거의 모든 보안 — HTTPS 통신, 공인인증서, 비밀번호 저장, 메신저 종단간 암호화 — 의 밑바닥에는 RSA나 타원곡선 암호(ECC) 같은 공개키 암호 시스템이 깔려 있어요. 이 암호들이 안전한 이유는 "엄청나게 큰 수의 소인수분해"나 "타원곡선 위의 이산로그 문제"가 현재 컴퓨터로는 사실상 풀 수 없을 만큼 어렵기 때문이에요.

그런데 1994년 피터 쇼어(Peter Shor)라는 수학자가 충격적인 알고리즘 하나를 발표했어요. 충분히 큰 양자컴퓨터만 있다면 이 두 문제를 다항시간 안에 풀 수 있다는 거였죠. 다항시간이라는 게 뭐냐면, 입력이 커져도 계산 시간이 "감당 가능한 속도"로만 늘어난다는 뜻이에요. 즉, 양자컴퓨터가 실용화되는 순간 지금의 RSA와 ECC는 한순간에 무너집니다.

물론 아직은 그런 양자컴퓨터가 없어요. 하지만 미국 NIST(국립표준기술연구소)는 "몇 년 뒤 양자컴퓨터가 등장한 뒤에 대응하면 늦다"고 보고 이미 2016년부터 포스트 양자 암호(PQC, Post-Quantum Cryptography) 표준화 프로젝트를 진행해 왔어요. 그리고 2024년 8월, 드디어 첫 번째 표준들이 확정됐는데 그중 세 개가 모두 격자 기반 암호(Lattice-based Cryptography) 였습니다. 이번에 공유된 "A Gentle Introduction to Lattice-Based Cryptography" 문서는 바로 이 격자 암호를 수학 비전공자도 따라갈 수 있게 풀어 쓴 입문서예요.

격자가 도대체 뭔가

격자(Lattice)라는 단어가 좀 낯설죠. 수학에서 격자는 간단히 말해 "점들이 규칙적으로 찍힌 무한한 격자무늬" 예요. 2차원에서 떠올리면 모눈종이 위의 교차점들 같은 모습이고, 3차원이면 결정 구조처럼 격자점들이 공간에 쫙 펼쳐진 모양이에요. 암호학에서 쓰는 격자는 보통 수백, 수천 차원이라 머릿속으로 그리기는 어렵지만 원리는 같습니다.

격자에는 "기저(basis)"라는 게 있어요. 격자의 모든 점을 만들어내는 출발 벡터들이라고 보면 돼요. 그런데 신기한 점은, 같은 격자를 만들어내는 기저가 여러 개 존재한다는 거예요. "좋은 기저"는 짧고 거의 직각에 가까운 벡터들이라 계산이 쉽고, "나쁜 기저"는 길고 비스듬한 벡터들이라 같은 격자인데도 분석이 무지 어려워져요.

격자 암호의 핵심 아이디어가 여기서 나옵니다. 비밀 키를 "좋은 기저"로 두고, 공개 키를 "나쁜 기저"로 두는 거예요. 메시지를 암호화할 때는 격자점 근처에 약간의 노이즈를 섞어 보내고, 비밀 키(좋은 기저)를 가진 사람만 그 노이즈를 제거하고 원래 점을 복원할 수 있죠.

어떤 문제가 어렵길래 안전한가

격자 암호의 안전성은 크게 두 가지 "어려운 문제"에 기댑니다. 하나는 SVP(Shortest Vector Problem, 최단 벡터 문제) 예요. 격자 안에서 가장 짧은 벡터를 찾는 문제인데, 차원이 높아지면 양자컴퓨터로도 효율적으로 푸는 방법이 알려져 있지 않아요. 다른 하나는 LWE(Learning With Errors, 오류가 있는 학습) 문제예요. "선형 방정식들을 주는데, 각 방정식의 우변에 작은 랜덤 노이즈를 더해서 줄게. 원래 해를 찾을 수 있어?" 라는 거예요. 노이즈가 없으면 가우스 소거법으로 금방 풀리지만, 노이즈가 끼면 갑자기 풀기가 엄청나게 어려워집니다.

NIST가 선정한 표준 중 키 교환용인 ML-KEM(예전 이름 Kyber) 과 디지털 서명용인 ML-DSA(예전 이름 Dilithium), FN-DSA(Falcon) 가 모두 이 LWE나 그 변형(Module-LWE, NTRU 등)에 기반하고 있어요. 모두 격자 문제의 어려움을 안전성 근거로 삼는 거죠.

기존 암호와 뭐가 다른가

실무적으로 봤을 때 격자 암호의 가장 큰 차이는 키와 암호문 크기예요. RSA 2048비트 공개키가 256바이트 정도인 데 비해, ML-KEM의 공개키는 800바이트에서 시작해서 1568바이트까지 갑니다. 서명도 마찬가지로 ECDSA가 64바이트면 끝나는데 Dilithium은 2~4KB가 필요해요. 인증서 체인이 길어지는 TLS 핸드셰이크에서는 이 차이가 누적돼서 꽤 부담스러워집니다.

반면 연산 속도는 의외로 빨라요. RSA는 큰 수 모듈러 거듭제곱이 비싼데, 격자 암호는 작은 계수의 다항식 곱셈이 핵심이라 SIMD 최적화도 잘 먹고 하드웨어 가속도 비교적 쉬워요. Cloudflare나 Google이 실험한 결과를 보면 ML-KEM은 ECDH보다 오히려 빠른 경우도 있다고 합니다.

경쟁 후보였던 코드 기반 암호(McEliece 계열)나 해시 기반 서명(SPHINCS+), 다변수 다항식 기반 암호도 있었지만, 키 크기나 서명 크기, 속도 균형에서 격자 기반이 가장 실용적이라는 평가를 받아 표준의 중심에 자리 잡았어요. SPHINCS+는 보조 표준으로 같이 채택되긴 했는데 서명 크기가 수십 KB라 일반 용도로는 쓰기 부담스러워요.

한국 개발자에게 주는 시사점

"이거 나랑 무슨 상관이야, 난 그냥 웹 개발자인데" 싶을 수 있어요. 하지만 생각보다 빨리 다가오는 이슈입니다. 이미 Chrome과 Firefox는 2024년부터 TLS 핸드셰이크에 ML-KEM을 하이브리드 방식으로 도입하기 시작했어요. AWS, Cloudflare도 PQC 지원을 단계적으로 켜고 있고요. 한국 금융보안원과 KISA도 양자내성암호 전환 로드맵을 발표한 상태예요.

특히 위협이 되는 시나리오가 "지금 훔쳐서 나중에 푼다(Harvest Now, Decrypt Later)" 예요. 공격자가 지금 암호화된 통신을 그냥 저장만 해뒀다가, 10년 뒤 양자컴퓨터가 나오면 그때 풀어보는 거죠. 의료기록, 금융거래, 정부 기밀처럼 장기간 비밀 유지가 필요한 데이터를 다루는 시스템이라면 지금부터 PQC 도입을 고민해야 합니다.

실무 개발자 입장에서는 일단 암호 알고리즘을 직접 박아 쓰지 말고 추상화 레이어를 두는 것이 가장 현실적인 준비예요. OpenSSL 3.x, BoringSSL, libsodium 같은 라이브러리들이 PQC를 점진적으로 지원하고 있으니 추후 알고리즘 교체가 쉽도록 코드를 설계해두는 거죠. "crypto-agility(암호 민첩성)" 라는 용어를 기억해두면 좋아요.

마무리

격자 기반 암호는 더 이상 학계의 호기심이 아니라 곧 우리가 매일 쓰게 될 표준이에요. 한 줄로 정리하면 "양자컴퓨터 시대에도 안전한 새 자물쇠, 그 핵심 부품이 격자 수학" 입니다. 수학적 배경이 깊지만 입문 문서들이 점점 친절해지고 있으니 한 번쯤 훑어볼 가치가 충분해요.

여러분이 운영 중인 서비스 중에 "10년 뒤에도 비밀이어야 하는 데이터"가 있나요? 만약 있다면 그 데이터를 보호하는 TLS와 저장소 암호화에 PQC 전환 계획이 있는지 한번 점검해보시면 좋겠어요. 그리고 혹시 보안 쪽 진로를 고민 중인 분이라면, 지금이 격자 암호를 공부하기 정말 좋은 타이밍입니다.