양자 내성 암호에 대해

토스페이먼츠에서 2026년 4월에 양자 내성 암호화를 도입하는 것을 보고, 이번 기회에 양자 내성 암호에 대해 공부한 것을 공유하고자 한다.

기존 암호 체계

기존의 공개키 기반 암호 체계는 대부분 아래와 같은 전제 하에서 만들어져 있다.

특정 계산 문제를 현실적인 시간 안에 풀어낼 수 있는 알고리즘이 없다.

즉 특정한 타원곡선 위에서 정의된 값을 역산하거나 매우 큰 수를 소인수분해하는 것이 현실적으로 불가능하다는 것이다. 아마 가장 많이 알고 있을 RSA나 ECDSA 등이 있다.

좀 어려운 말로 들리겠지만 쉽게 말하자면 "풀려면 풀 수 있지만 시간이 비현실적으로 오래 걸린다" 라고 볼 수 있다. 암호 하나 풀겠다고 몇 천년을 컴퓨터가 계산할 수는 없으니 현실적으로 불가능하다는 것이다.

Q-DAY

위에 있던 기존 공개키 기반 암호 체계가 양자 컴퓨터로 인해 완전히 무력화되는 그 날을 Q-DAY라고 부른다. 그렇다면 양자 컴퓨터와 그 알고리즘은 뭐길래 무력화가 된다는 걸까.

양자의 특성

그걸 설명하기 위해서는 양자의 특성을 우선 알아야 한다.

양자는 특이하게도 파동이자 입자인 상태를 동시에 지닌다. 그 유명한 이중 슬릿 실험에서는 입자를 이중 슬릿에 발사했을 때 반대편 벽에 파동의 간섭무늬가 남았다. 그리고 또 특이하게 입자를 직접 관측하니 이번에는 파동의 흔적이 없이 입자처럼 움직였다는 것이다.

양자는 이렇듯 두 가지 성질을 동시에 지니는 이중성을 가지고 있다. 관측이 이루어지기 전에는 우린 양자의 상태를 정확히 알 수가 없고 오로지 확률, 즉 파동으로서만 알 수 있다.

이러한 특징으로 인해서 슈뢰딩거의 고양이로 유명한 중첩이 생긴다. 관측하기 전의 양자는 여러 상태를 동시에 확률적으로 지니는 중첩 상태에 있고, 관측하는 순간 그 중 하나의 상태로 확정된다.

Shor 알고리즘

위에서 설명한 양자의 특성과 함께 필요한 것이 바로 Shor 알고리즘이다. 깊게 들어가면 너무 어렵고 필자도 이를 완벽히 이해하고 있지는 않기에 간단하게 설명해 보겠다.

RSA 암호 체계를 예시로 해보자. RSA는 두 큰 소수 a와 b를 곱한 N이라는 수를 다시 두 소수 a와 b로 소인수분해하는 것은 어렵다는 것을 바탕으로 만들어졌다.

예를 들어서 61 × 53 = 3233 처럼 곱하는 건 금방이지만, 누군가 3233 이라는 숫자만 딱 주고 두 소수의 곱으로 쪼개라고 한다면 이걸 하나씩 나눠봐야 한다. 숫자가 작다면 금방 하겠지만 실제로 RSA에서는 600자리가 넘는 숫자를 이용하고, 이를 하나하나 계산하려면 현재의 일반 컴퓨터로는 우주 나이보다 오래 걸린다.

그래서 나온 것이 바로 Shor 알고리즘이다.

Shor 알고리즘은 하나하나 나눠보면서 소인수분해를 직접 하는 것이 아니라, 문제 자체를 다르게 치환해서 다룬다. 바로 어떤 수 N을 소인수분해하는 문제를, 특정한 함수가 몇 번마다 같은 값으로 반복되는가, 즉 그 주기를 찾는 문제로 치환하는 것이다.

쉽게 말하자면 N과 관련된 수열을 쭉 나열했을 때 그 값들이 일정한 주기로 반복이 된다. 이러한 주기와 그 패턴을 알아내면 쉽게 그 N의 소인수를 알아낼 수 있다.

다만 그 주기가 매우 거대하기에, 고전 컴퓨터에서는 Shor 알고리즘을 이용한다고 한들 그 주기를 찾는 데 매우 오래 걸린다. 그렇기에 양자의 특성을 가진 양자 컴퓨터를 이용하는 것이다.

양자 컴퓨터

양자 컴퓨터에는 일반적인 비트가 아니라 양자의 중첩 상태를 이용한 '큐비트'라고 하는 것을 기본 연산 단위로 사용한다. 큐비트는 일반 비트와 다르게 0과 1이라는 상태를 동시에 지닌다. 즉 여러 후보를 한 상태에 겹쳐 담아 병렬로 계산할 수 있는 것이다.

다만 이 병렬성만으로는 이득이 없다. 그냥 측정하면 그 수많은 후보 중 무작위로 하나만 튀어나올 뿐이기 때문이다. 실제 속도의 비결은 바로 다음에 나올 간섭에 있다.

먼저 N과 관련된 수열을 모두 큐비트에 담는다. 그리고 Shor 알고리즘에서 나온 것처럼 그 수열의 주기가 패턴적으로 반복되게 된다. 마치 파동의 형태처럼 말이다.

그리고 여기서 간섭을 이용해 그 수많은 파동들의 확률을 재배치한다. 두 파동을 겹쳤을 때 서로 반대인(봉우리와 골이 만나는) 파동은 상쇄되어 사라지고(파괴적 간섭), 같은 위상의 파동들은 겹치면서 더욱 크게 증폭된다(보강적 간섭).

이를 통해 정답인 상태의 확률은 키우고, 오답인 상태의 확률은 상쇄시켜 없애는 것이다.

그런 다음 이를 측정하여 나온 수를 고전적 계산을 통해 처리하면 최종적으로 그 소인수를 알 수 있다. 사실 많은 계산과 수식들이 중간에 있지만 여기서는 그게 요지가 아니니 생략하겠다.

이러한 플로우와 알고리즘을 실현할 만큼 많은 물리 큐비트를 안정적으로 돌릴 수 있는 컴퓨터는 아직 없다. 다만 이론상 수십만에서 수천만 개의 물리 큐비트를 안정적으로 돌릴 수만 있게 된다면, 몇 시간에서 며칠 내로 풀 수 있게 되는 것이다.

이러한 날이 오는 것을 바로 Q-DAY라고 부르는 것이다.

출처

대칭키 쓰면 되는 거 아님?

대칭키는 공개키와 다르게 특정 수학 문제가 아니라 그냥 경우의 수 자체를 매우 거대하게 늘린 방식이라서, 양자 컴퓨터 공격에도 상대적으로 안전하다.

불안하다면 그냥 키 길이만 늘리면 된다. 양자 컴퓨터로도 실효 강도가 절반으로 줄어드는 정도에 그치고, 그렇게 절반이 된 값조차 여전히 현실적으로 깰 수 없는 수준이라 실질적인 위협이 되지 않는다.

다만 오늘날에는 대칭키 방식으로만 암호를 만들거나 통신하지 않는다. 보통은 공개키와 함께 하이브리드 방식으로 사용한다. 우선 통신할 때 대칭키를 상대방에게 어떻게 안전하게 전달할지부터가 문제인데, 이를 해결하기 위해 공개키로 대칭키를 안전하게 감싸서 전달하는 식으로 둘을 함께 쓰기 때문이다.

그래서 대칭키만 사용하는 것은 완벽한 대응 방안이 될 수 없다.

양자 내성 암호

서론이 다소 길고 복잡했지만 위와 같은 이유와 위험들로 인해서 새로운 암호 체계 도입이 필요했고, 이를 위해 나온 것이 양자 내성 암호이다.

우선 위에서 말한 Shor 알고리즘의 본질을 다시 보자면

소인수분해나 이산로그가 "주기 찾기"로 바뀔 수 있어서

였다. 그렇다면 반대로 생각하면

주기 찾기로 변하지 않는 수학 문제 위에 공개키를 새로 세우자

라고 할 수 있는 것이다. 이것이 양자 내성 암호의 기본적인 베이스이다.

격자 문제

다양한 방식이 있지만 현재 NIST 표준에서 가장 주류이자 중심인 방법에 대해서 다루겠다.

격자 문제는 일단 수많은 점이 격자처럼 규칙적으로 찍힌 고차원의 공간에서, 임의의 한 점에서 가장 가까운 격자점을 찾아라 같은 문제이다.

쉽게 말하자면 2차원의 면이 있다고 했을 때, 격자점이 아닌 임의의 한 점을 찍고 그 점에서 가장 가까운 격자점이 무엇인지 알아내야 하는 것이다. 2차원에서는 눈으로 보고 금방 찾을 수 있지만, 실제로 활용될 때는 수백~수천 차원이기에 고전 컴퓨터는 물론 양자 컴퓨터로도 현실적인 시간 안에 풀지 못한다.

이를 응용해서 암호화를 진행한다. 여기서부터는 선형 방정식, 벡터 등 사전 수학 지식을 요구하기에 정말 간단하게 비유해서 설명하도록 하겠다.

지도

격자점을 찾는 문제를 지도에 비유해보자. 점을 찍으면 거기에서 가장 가까운 목표(격자점)를 찾아야 하는 지도가 두 장 있다.

한 지도는 매우 심플해서, 지도만 가지고 있으면 누구나 아무 데나 찍어도 바로 "동쪽으로 한 칸, 북쪽으로 한 칸" 이런 식으로 아주 쉽게 격자점을 찾을 수 있다.

그러나 다른 지도는 일부러 꼬아놓았다. "대각선으로 몇 걸음 가서 몇 도로 꺾은 뒤에 다시 몇 걸음..." 두 지도 모두 같은 점으로 안내하지만, 이 지도로는 가까운 점을 찾으려다가 길을 잃어버린다.

여기서 포인트는, 쉬운 지도를 어려운 지도로 만드는 건 매우 쉽지만 반대로 어려운 지도만 보고 쉬운 지도를 복원하는 건 불가능에 가깝다는 것이다. 이 한쪽으로만 쉬운 성질이 바로 자물쇠를 만든다.

이제 이 두 지도가 있을 때, 나는 쉬운 지도를 가지고 있어서 언제든지 간편하게 목표를 찾을 수 있다. 다만 밖에 공개하는 지도는 어려운 지도로 두고, 거기에 목표인 점도 살짝 흐릿하거나 어긋나게 찍는다. 이제 이걸 가져간 도둑은 이게 원래 이 점인지 아니면 그 옆의 점인지 헷갈리면서 확신을 가질 수가 없게 된다.

이렇게 두 지도를 각각 공개키와 개인키로 삼아 암호화하기 때문에, 쉬운 지도(개인키)가 없으면 풀리지가 않는 것이다.

그리고 가장 큰 장점은, 기존에 소인수분해를 이용한 암호 체계처럼 문제를 주기로 변환할 수 없다는 것이다. 그렇기에 소인수분해를 깨던 Shor 알고리즘이 무용지물이 되며, 풀 수가 없는 것이다.

마치면서

양자역학과 수학적 기호들이 난무하다 보니 이걸 이해하는데도 정말 많은 시간이 걸렸다. 그리고 이걸 다시 쉽게 풀어내려다 보니 오랜만에 머리가 아파오는 기분이었다.

매일 같이 보안 이슈가 올라오고 있다 보니 앞으로 이런 보안 관련 기술들을 미리 공부해 놓는 것도 좋은 듯 하다. 아직 Q-DAY가 오기에는 최소 10년은 걸릴거 같지만 미리 대비할 수 있다면 대비하는게 좋을 것 같다.

p.s 혹시라도 위에 글에 있던 비유나 설명이 부적절하거나 오해의 소지가 있다면 댓글로 피드백 남겨주세요!