인터넷의 암호를 깨는 인류 최강의 수학 「일반 수체 체(GNFS)」란?

우리가 매일 사용하는 인터넷. LINE 메시지나 YouTube, Amazon에서의 쇼핑 등 모든 통신은 “암호"에 의해 보호받고 있습니다. 현재 전 세계에서 가장 많이 사용되는 암호의 대표가 “RSA 암호"입니다.

RSA 암호 방어의 핵심은 매우 간단합니다. 그것은 “거대한 수의 소인수분해는 컴퓨터로도 풀 수 없다” 는 수학적 성질을 이용하고 있다는 것입니다. 예를 들어 “15"라면 “3 × 5"라고 바로 알 수 있지만, 이것이 “270자리 숫자"가 되는 순간 전 세계의 슈퍼컴퓨터를 모두 모아도 푸는 데 수억 년이 걸리고 맙니다.

하지만 수학자들도 가만히 있지는 않습니다. 이 철벽같은 암호를 깨기 위해 인류는 “일반 수체 체(GNFS: General Number Field Sieve)” 라는 마법 같은 알고리즘(계산 절차)을 만들어 냈습니다.

이 글에서는 전문 용어를 전혀 사용하지 않고, 중학교에서 배우는 수학(소인수분해, 문자식, 최대공약수) 지식만으로 이 “인류 최강의 알고리즘"이 암호를 깨는 원리를 단계별로 완전 해설합니다!

제1장: 암호 해독의 목표는 “중학교 3학년 공식”

거대한 소인수분해에 맞서기 위한 최대의 필살기. 그것은 중학교 3학년 때 배우는 이 공식입니다.

$X^2 - Y^2 = (X + Y)(X - Y)$

“어, 이런 기초적인 공식으로 암호를 깰 수 있다고?“라고 생각할지 모릅니다. 하지만 이것이야말로 모든 것을 밝혀낼 마스터키입니다.

암호를 깨기 위한 최대의 목표는 거대한 수 $N$에 대해, "$X^2$과 $Y^2$을 $N$으로 나눈 나머지가 같아지는 수($X$와 $Y$)” 를 찾는 것입니다.

왜 “나머지가 같으면” 암호가 풀리는 걸까?

어떤 두 수 $X^2$과 $Y^2$의 “$N$으로 나눈 나머지가 같다"고 가정해 봅시다. 나머지가 같다는 것은 뺄셈을 한 “$X^2 - Y^2$“는 반드시 $N$으로 딱 나누어떨어진다($N$의 배수가 된다) 는 법칙이 있습니다.

여기서 암호에 사용되는 거대한 수 $N$은 두 개의 비밀 소수($p$와 $q$)의 곱셈으로 이루어져 있다고 합시다($N = p \times q$).

$X^2 - Y^2$를 인수분해하면 $(X - Y)(X + Y)$ 가 됩니다. 이것이 $N$의 배수라는 것은 이 곱셈의 어딘가에 비밀 소수 $p$와 $q$가 숨어 있다는 의미입니다.

여기서 기적이 일어납니다. 두 소수 $p$와 $q$가 "$p$는 $(X - Y)$의 방으로”, “$q$는 $(X + Y)$의 방으로” 서로 다른 방으로 나뉘어 들어갈 확률이 수학적으로 ** 50%(2분의 1)** 나 되는 것입니다.

소수 $p$만이 $(X - Y)$의 방에 들어간 상태에서 $(X - Y)$와 $N$의 “최대공약수(공통되는 가장 큰 부품)” 를 계산해 봅시다.

$(X - Y)$의 내용물 = $p \times$ 어떤 수
$N$의 내용물 = $p \times q$ 공통된 부품은 "$p$” 밖에 없죠!

즉, 최대공약수를 계산하는 순간 숨어 있던 소수 $p$가 툭 떨어져 나와 암호가 완전히 해독되어 버리는 것입니다. (※최대공약수는 “유클리드 호제법"을 사용하면 스마트폰으로도 순식간에 계산할 수 있습니다)

【잠깐 칼럼: 왜 제곱일까? 세제곱이나 2배는 안 될까?】

“$2X - 2Y$“라면 $2(X - Y)$가 되어 방이 하나밖에 없으므로 소수를 떼어놓을 수 없습니다. “$X^3 - Y^3$“라면 방의 크기가 불균형해져서 계산이 쓸데없이 무거워집니다. 소수를 두 개로 떼어놓기 위해서는 아름답게 두 개의 방으로 나뉘는 “제곱"이 가성비가 가장 좋습니다.

제2장: X와 Y를 어떻게 찾을까? “소수 카드 모으기 퍼즐”

목표는 알았습니다. 하지만 “나머지가 같아지는 $X^2$과 $Y^2$“를 무턱대고 찾아봤자 우주의 수명이 다할 때까지 찾을 수 없습니다. 그래서 수학자들은 “소수 카드 모으기 퍼즐” 이라는 천재적인 방법을 떠올렸습니다.

Step 1: 사금(매끄러운 수)만을 체로 걸러 모으기

먼저 적당한 수 $Z$를 준비하고, 제곱해서 $N$으로 나눈 나머지 $W$를 계산합니다. ($Z^2 = W$인 나머지의 세계)

나온 나머지 $W$를 소인수분해합니다. 여기서 “2, 3, 5, 7 등의 작은 소수로만 이루어진 $W$” 가 나왔을 때만 그 식을 “당첨 카드"로 남기고, 큰 소수가 섞여 있으면 버립니다. 강에서 큰 돌을 체로 걸러 버리고 사금만을 모으는 것과 같은 작업입니다.

Step 2: 모두 “짝수 개"로 만드는 퍼즐

예를 들어, 다음과 같은 3장의 사금 카드가 모였다고 합시다.

카드 A: $Z_1^2 = 2^3 \times 3^1$
카드 B: $Z_2^2 = 2^1 \times 5^1$
카드 C: $Z_3^2 = 3^1 \times 5^1$

이것을 모두 곱해 봅시다. 오른쪽은 $(2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)$이 되고, 한데 묶어 정리하면 "$2^4 \times 3^2 \times 5^2$” 가 됩니다.

놀랍게도 소수의 개수가 “4개, 2개, 2개"로 모두 짝수 개 가 되었습니다! 모두 짝수 개라는 것은 전체를 절반의 개수로 만들면 “어떤 수의 제곱"이 된다는 것입니다. 즉, $(2^2 \times 3^1 \times 5^1)^2 = (60)^2$입니다.

왼쪽은 $(Z_1 \times Z_2 \times Z_3)^2$이므로, 이것으로 마침내 $X = (Z_1 \times Z_2 \times Z_3)$ $Y = 60$ 이라는 기다리고 기다리던 “$X^2 = Y^2$“의 쌍이 완성된 것입니다!

컴퓨터에 있어 소수의 개수를 “짝수인가 홀수인가(0인가 1인가)“로 계산하는 퍼즐은 매우 능숙하므로, 이 방법이라면 빠르게 $X$와 $Y$를 찾을 수 있습니다.

제3장: 앞을 가로막는 절망의 벽

이제 어떤 암호라도 깰 수 있다!… 라고 생각했지만, 큰 문제가 발생합니다. 암호 숫자 $N$이 “100자리” 정도까지라면 이 방법(이차 체라고 합니다)으로 풀 수 있지만, $N$이 “200자리, 300자리"가 되면 계산 도중에 나오는 $W$가 너무 커집니다.

숫자가 너무 커지면 “작은 소수로만 이루어진 수(사금)“가 뚝 끊기고 맙니다. 사막에서 콘택트렌즈를 찾는 것보다 어려워져서, 퍼즐을 풀기 위한 카드가 전혀 모이지 않게 되는 것입니다.

여기서 마침내 인류의 최종 병기 “일반 수체 체(GNFS)” 가 등장합니다.

제4장: 인류 최강의 아이디어 “두 개의 세계” 만들기

GNFS의 천재적인 발상은 “현실 세계에서만 계산하니까 숫자가 커진다. 그렇다면 다항식(문자식)을 사용한 ‘이면의 세계’를 만들어서 계산의 무게를 둘로 분산시키자” 라는 것입니다.

문자식의 마법

GNFS는 거대한 수 $N$을 베이스가 되는 수 $m$을 사용하여 문자식으로 변환합니다. 예를 들어 $N=100$이라면, $m=4$로 하여 $100 = 4^3 + 2(4^2) + 4$. 이것을 문자 $x$를 사용하여 $f(x) = x^3 + 2x^2 + x$ 라는 식(이면의 세계)으로 만듭니다.

이 식의 재미있는 점은 “문자 $x$에 $m$(위의 예라면 4)을 대입하면 언제든지 현실의 수 $N$으로 워프해서 돌아올 수 있다” 는 성질을 가지고 있다는 것입니다.

두 세계에서 동시에 사금 찾기

GNFS는 적당한 정수 쌍 $(a, b)$를 많이 만들고, 다음 두 가지 계산을 동시에 수행합니다.

현실 세계: $a - b \times m$
문자식 세계: $a - b \times x$를 문자식의 규칙으로 계산한 값

문제를 두 개의 세계로 나눔으로써 다루는 숫자의 크기가 극적으로 작아집니다(가벼워집니다). 거대한 바위를 둘로 쪼개어 다루기 쉬운 돌멩이로 만든 이미지입니다.

그리고 “현실 세계에서도, 문자식 세계에서도 양쪽 모두 ‘작은 소수로만 이루어져 있는(사금)’” 기적의 쌍 $(a, b)$만을 체로 걸러내어 모읍니다. 이것이 “수체 체"라는 이름의 유래입니다.

마침내 암호가 깨지는 순간

양쪽 세계에서 수천만 장의 “사금 카드"가 모이면 슈퍼컴퓨터의 거대한 행렬 계산을 사용하여, 제2장에서 했던 “소수의 개수가 모두 짝수가 되는 조합"을 찾아냅니다.

조합을 찾으면,

현실 세계에서 만들어진 제곱 수를 $X^2$
문자식 세계에서 만들어진 제곱 식을 $Y(x)^2$ 로 둡니다.

마지막으로 문자식의 $Y(x)$의 $x$에 $m$을 대입하여 현실 세계로 워프시켜 합류시킵니다. 그러면 수학의 마법처럼 "$X^2$과 $Y^2$의 나머지가 같아진다” 는 상태가 엄밀하게 완성되는 것입니다!

이제 제1장에서와 같이 $X - Y$와 $N$의 최대공약수를 계산하면, 난공불락의 RSA 암호는 소리를 내며 무너져 내리고 비밀 소수가 모습을 드러냅니다.

맺음말: 수학은 끝나지 않는다

“좋아, GNFS를 사용하면 어떤 암호라도 깰 수 있겠구나!“라고 생각했을지도 모릅니다. 하지만 RSA 암호도 만만치 않습니다. 현재 인터넷에서 사용되는 것은 “RSA-2048(약 617자리)“이라는 괴물 같은 거대 수입니다.

GNFS가 아무리 인류 최강의 알고리즘이라 하더라도, 270자리(RSA-270)를 푸는 데만도 전 세계의 컴퓨터를 연결해도 수천 년, 수만 년이 걸린다고 합니다. 지금으로서는 우리의 LINE이나 은행 데이터는 안전합니다.

하지만 만약 “어떤 거대한 수라도 순식간에 $X$와 $Y$를 찾는 마법” 이 나타난다면 어떻게 될까요? 사실 거기에 가장 가까운 존재가 현재 개발 중인 “양자 컴퓨터(쇼어의 알고리즘)” 입니다. 양자 역학의 파동 성질을 사용하면 귀찮은 카드 모으기 퍼즐을 무시하고 단번에 답을 뽑아낼 수 있다고 수학적으로 증명되어 있습니다.

암호를 만드는 사람(방어)과 암호를 깨는 알고리즘을 만드는 사람(공격)의 끝없는 지혜 겨루기. 중학교에서 배우는 “소인수분해"나 “문자식"이 사실은 세계 보안의 최전선에서 치열하게 싸우고 있는 무기라는 것을 알면 수학 수업이 조금은 더 재미있어 보이지 않나요?

미래의 최강 알고리즘을 발견하는 것은 이 글을 읽고 있는 당신일지도 모릅니다!

(※본 기사는 암호 해독의 수학적 매력을 중학생용으로 개념화한 것입니다. 실제 GNFS는 대수체의 이데알 류군이나 준동형 사상 등의 고도화된 대학 수학을 이용하여 엄밀하게 계산됩니다)