/ MATH, CRYPTOGRAPHY, BLOCKCHAIN

리만 가설과 공개키 암호화, 그리고 블록체인에 관하여

[DISCLAIMER] 저는 수학, 정수론 또는 관련 학문의 전공자가 아니며, 그에 관련하여 제대로 배워본 적도 없는 일명 ‘수알못’입니다. 수학을 그리 잘 하는 편은 아니지만, 관련한 자료들을 읽어보는 것을 좋아하는 정도랄까요. 때문에 저는, 잘 알지도 못하는 정수론이나 수학에서의 ‘최종 보스’라 불리는 리만 가설에 관한 내용을 공개적으로 논하기에는 자격 조건이 한참 모자랍니다. 다만, 수학자 마이클 아티야 (Michael Atiyah) 경의 리만 가설 증명 발표를 앞두고 ‘리만 가설이 증명되면 현대 암호체제가 완전히 무너질 것이다’ 같은 괴담을 바로잡을 필요성을 느껴, 제가 이해하는 한도 내에서 최대한 관련한 내용을 서술한 것입니다. 혹시 관련 분야 전공자분, 혹은 수학에 내공이 깊으신 분께서 본 글의 오류를 발견하신다면, 댓글로 지적해 주시면 빠른 시일 내에 바로잡겠습니다.

리만 가설과 수학계 최대 난제의 탄생

1859년 11월, 베를린 학술원에 8페이지 길이의 짧은 논문이 발표됩니다. 제목은 ‘주어진 수보다 작은 소수의 개수에 관하여’ (Über die Anzahl der Primzahlen unter einer gegebenen Größe) .  비록 짧은 길이의 논문이었지만, 이 논문은 현대 수학에서 중요한 이정표라 할 만한 몇 가지 중요한 정의와 증명, 그리고 기법들을 선보였습니다. 이 논문의 저자는 독일의 수학자 베른하르트 리만 (Bernhard Riemann). 비록 그는 이 논문이 발표된 후 약 7년 뒤 39세의 젊은 나이로 숨을 거두었지만, 그가 짧은 시간 동안 수학을 연구하면서 남긴 업적은 어마어마하다라는 말이 모자랄 정도로 중요한 것들이었죠. 그 중에는 현재까지 와서도 풀리지 않는, 소수의 분포와 관련된 하나의 가설도 포함되어 있었습니다. 바로 리만의 이 짧은 논문에서 처음으로 제시된, ‘리만 가설’입니다. 리만 가설의 주요 내용을 간단하게 한마디로 요약하자면, 다음과 같습니다:

제타 함수 $\zeta \left({s}\right)$의 자명하지 않은 모든 근*의 실수부는 $\frac{1}{2}$이다.

(주: 상기의 ‘자명하지 않은 모든 근’이라는 표현은 ‘음의 짝수를 제외한 모든 근’이라는 뜻입니다. 제타 함수는 모든 음의 짝수를 근으로 갖는데, 이는 규칙성이 ‘자명’하므로 ‘자명한 근’이라고 합니다. 반면, 음의 짝수를 제외한 근들은 규칙성이 분명하지 않으므로 (즉, ‘자명하지 않으’므로) ‘자명하지 않은 근’이라고 표현합니다.)

리만의 이 추측을 수학적으로 엄밀하게 증명하기 위하여 수많은 천재들이 이 문제에 도전했지만, 1859년부터 현재에 이르기까지 160년이라는 긴 시간 동안 그 누구도 이 가설을 증명해내지 못했습니다. 애초에 리만 자신도 본인의 추측을 증명할 생각은 없었던 것 같기도 합니다. 이 논문 중 리만 가설을 처음 제기하는 부분에서, 다음과 같은 설명이 달려 있기 때문입니다:

(함수 $\zeta \left({s}\right)$에 대하여) 이 범위 (실수 부분이 $0$과 $T$ 사이이고 허수 부분이 $\frac{1}{2}i$와 $-\frac{1}{2}i$ 사이) 내에서 근사적으로 이 정도 개수 ($\frac{T}{2\pi}\log\frac{T}{2\pi}-\frac{T}{2\pi}$개)의 실근을 찾을 수 있고, 모든 근이 실수일 가능성이 매우 높다. 이에 관해서는 더 엄밀한 증명을 필요로 하겠지만 이 탐구의 목적을 달성하는 데에는 의미가 없어 보이기 때문에, 몇 번의 일시적이고 의미 없는 시도 끝에 이에 관한 연구는 잠시 미루어 두기로 하였다. (One now finds indeed approximately this number of real roots within these limits, and it is very probable that all roots are real. Certainly one would wish for a stricter proof here; I have meanwhile temporarily put aside the search for this after some fleeting futile attempts, as it appears unnecessary for the next objective of my investigation.)

(주: 상기의 설명에서 리만이 언급하고 있는 함수 는 원래의 제타 함수가 아니라, 임계선 (Critical Line) 위의 복소수 근 대신 실근을 갖도록 변형된 형태의 함수입니다. 이 임계선은 실수부가 인 복소수들의 집합으로 이루어진 직선이며, 따라서 위의 함수 에서 모든 근이 실수라는 표현은 원래의 제타 함수에서 음의 짝수를 제외한 모든 근의 실수부가 라는 의미와 같습니다.)

‘몇 번의 일시적이고 의미 없는 시도 끝에’라는 표현은, 리만 자신도 이 논문을 작성할 당시 본인의 추측을 증명하려고 시도했으나 결국 실패했다는 사실을 암시합니다. 리만이 본인의 이 가설을 결국 증명했는지, 혹은 최소한 획기적인 진전을 이뤄냈는지는 확실치 않습니다. 리만이 사망한 이후 그의 가정부가 유품을 정리하던 과정에서, 아직 발표되지 않았던 리만의 연구 성과 중 절반 이상을 불에 태워버렸기 때문입니다. (이 일로 그 가정부는 160여 년이 지난 현재에 이르러서도 수많은 학자들의 원성을 사고 있습니다. 그 연구 성과가 보존되었다면 리만 가설이 훨씬 더 빠르게 증명되었을지도 모르는 일이니까요.)

소문과 괴담, 그리고 억측들

그렇게 8페이지에 불과한 논문 중 단 몇 문장에 의해 제기된 가설은, 리만 자신도 예상하지 못하게 수많은 학자들을 괴롭힌 난공불락의 난제가 되었습니다. 그런데…

…하이델베르크 수상자 포럼이 게시한 이 트윗 하나가 수학계뿐 아니라 전 세계를 발칵 뒤집어 놓았습니다. 수학자로서 가장 명예로운 상인 필즈 상과 아벨 상을 모두 수상한 전설적인 수학자 마이클 아티야 경 (Sir Michael Atiyah)이 리만 가설에 대한 증명을 이 자리에서 발표하겠다고 예고했기 때문입니다. 이전에도 리만 가설에 대한 증명을 찾아냈다고 주장한 학자들은 많았지만 그 중 아티야 경만큼의 명예나 실력을 갖춘 학자는 없었을 뿐더러, 자신의 증명에 연계된 기반 이론들을 이 정도로 초록에 상세하게 기재한 경우도 없었습니다. 다만, 아티야 경이 89세의 고령인 데다 최근 그의 정신 건강에 문제가 있다는 소문이 돌고 있어 단순한 해프닝으로 끝날 가능성도 여전히 있습니다.

하지만, 160년 동안 풀리지 않은 난제에 대한 증명을 공개 석상에서 발표하겠다는 것은 사실상 학자로서의 인생 전체를 건 것이나 다름이 없는 만큼 조심스럽게 해당 발표를 지켜보아야 하는 상황입니다. 만약 해당 증명이 거짓이거나 심각한 오류가 포함되어 있는 것으로 드러날 경우, 쏟아지는 학계의 비난과 조롱, 그리고 명예의 손상을 감수해야 하기 때문입니다. 저 또한 발표를 지켜본 이후, 본 글을 상황에 맞게 업데이트하도록 하겠습니다.

이 리만 가설과 관련하여 언젠가부터 사람들 사이에서 퍼지고 있는 괴담이 하나 있는데, 바로 ’리만 가설이 증명되면 현대의 모든 암호 체제가 한꺼번에 무너진다’라는 소문입니다. 이 소문은 난데없이 블록체인 업계로까지 퍼져나가, ’리만 가설의 증명은 블록체인 기술의 종말을 불러올 것’이라는 주장으로까지 발전했습니다. 블록체인 기술 자체가 소인수분해를 기반으로 하는 공개키 암호화에 의존하고 있는 만큼, 리만 가설의 증명으로 인해 공개키 암호화 체제가 무너진다면 블록체인 기술 또한 무사하지 못할 것이라는 주장입니다.

과연 이러한 주장은 신빙성이 있을까요? 그리고, 리만 가설이란 대체 무엇이길래 이런 극단적인 주장이 나올 만큼의 파급력을 가지고 있을까요? 차근차근 하나씩 짚어보겠습니다.

공개키 암호화와 리만 가설

잘 알려져 있다시피, 공개키 암호화 (Public Key Cryptography)는 두 소수의 곱을 구하는 것은 쉽지만 그 결과를 다시 두 소수의 곱으로 표현하는 것은 매우 어렵다는 사실을 이용해 정보를 암호화합니다. 그 중 대표적인 알고리즘인 RSA 알고리즘을 대략적으로 설명하면 다음과 같습니다:

  1. 서로 다른 두 개의 소수 $p$와 $q$를 고릅니다 ($p \neq q$). 이 때, 이 소수들의 크기가 클수록 더 안전합니다.
  2. 위의 두 소수의 곱 $n = pq$를 구합니다. 이 값의 길이가 바로 Key의 길이가 됩니다. (현대에는 보통 1024비트 ($2^{1024}$) 이상 크기의 Key를 고르기 때문에, 무작위 대입 (Brute Force) 공격 등이 성공할 확률은 매우 낮습니다.)
  3. $n$에 대한 카마이클 토션트 함숫값 (즉, $1$과 $n$사이의 정수 중 $n$과 서로소인 정수 $a$에 대하여, $a^m\equiv1\mod n$을 만족하는 $m$의 최솟값) $\DeclareMathOperator{\lcm}{lcm}\lambda(n) = \lcm\left(\lambda\left(p\right),\lambda\left(q\right)\right)=\lcm\left(\left(p-1\right),\left(q-1\right)\right)$를 구합니다.
  4. $1<e<\lambda\left(n\right)$이고 $\DeclareMathOperator{\gcd}{gcd}\gcd\left(e,\lambda\left(n\right)\right)=1$을 만족하는 정수 $e$를 선택합니다. (즉, $1$과 $\lambda\left(n\right)$ 사이에 있으면서 $\lambda\left(n\right)$와 서로소여야 합니다.)
  5. $d\equiv e^{-1}\mod\lambda\left(n\right)$를 만족하는 값 $d$를 구합니다.

이 절차를 거치면 $e$의 값은 공개키, $d$의 값은 비밀키가 됩니다. 이것을 먼저 구한 $n$의 값과 함께 묶어서 사용하게 됩니다.

Alice가 Bob에게 위에서 생성된 키쌍을 이용하여 메시지를 암호화해 전송하고 싶다고 합시다. 이 비밀 메시지를 $S$라고 하면, 먼저 $n$보다 더 작은 값으로 $S$를 분할해 $s<n$을 만족하는 분할값 $s$를 만듭니다. (이 분할법은 여러 가지가 있을 수 있지만, 상대방 또한 이 분할법을 알고 있어야 메시지의 복호화가 가능합니다.) 그 후, 암호화된 메시지 $c$를 $c=s^e\mod n$를 계산해 구합니다. 이 의 값을 Bob에게 전송하면 됩니다.

$c$의 값을 수신한 Bob는 이제 원래 메시지인 $s$의 값을 알아내야 합니다. 이 때, Bob는 공개키 $e$가 아닌 비밀키 $d$를 사용해야 이 메시지를 복호화할 수 있습니다. 즉, $s$의 값은 $s=c^d\mod n$를 계산하여 구합니다. 이미 Bob는 메시지의 분할법을 알고 있으므로, 분할된 모든 $s$들을 복호화한 후 다시 결합해 원래 메시지인 $S$를 읽어낼 수 있습니다.

이 암호화 알고리즘은 수학적으로 매우 안전합니다. 키를 생성할 때 사용된 두 개의 소수를 알아낼 수 없는 상태에서, 무작위 대입을 통해서만 비밀키를 알아낼 수 있으므로 매우 큰 소수에 대해서는 아무리 성능이 좋은 컴퓨터라 하더라도 비밀키를 알아내는 것이 거의 불가능에 가깝습니다. (양자 컴퓨터가 등장한다면 또 이야기가 달라지지만, 아직까지 양자 컴퓨터의 상용화는 꽤나 먼 미래의 일로 보입니다.) 여기에서 중요한 것은 처음 두 개의 소수를쉽게 알아낼 수 없다는 사실입니다. 그 이유는 너무나도 간단한데, 바로 소수의 분포에는 규칙이 없다고 알려져 있기 때문입니다. 일정한 규칙이 존재하지 않으니, 키쌍의 생성에 어떤 소수를 사용했는지 알아내는 것은 사실상 불가능한 일일 것입니다.

리만 가설은 이러한 소수에 관한 가정을 일정 부분 깨트립니다. 현재 제타 함수의 자명하지 않은 모든 근의 실수 부분이 (리만 가설과 같이 항상 $\frac{1}{2}$인 것이 아니라) $1$보다 작다는 사실은 이미 증명되어 있고, 이 사실만 증명할 수 있다면 소수의 분포를 근사적으로 나타낼 수 있는 정리인 소수정리는 참이라는 사실이 이미 알려져 있습니다. 따라서, 리만의 논문이 본래 밝히고자 했던 목표인 소수정리는 이미 참임이 증명되었습니다. 하지만, 소수 정리를 통해 밝혀낼 수 있는 소수의 분포에 관한 정보에는 여전히 오차가 많습니다. 리만 가설은 이보다 훨씬 엄격한 가정(실수 부분이 항상 $\frac{1}{2}$)이 참임을 증명하는 문제이므로, 만약 이 문제의 증명에 성공한다면 그 과정에서 동원된 기법들과 리만 가설 그 자체가 소수의 분포에 관한 보다 정확하고 엄밀한 정보를 제공해 줄 것임에는 틀림이 없습니다.

다만, 이것만을 가지고 현대 공개키 암호화 시스템이 무너질 것이라고 말하는 것은 무리입니다. 예를 들어, 리만 가설이 참이라고 가정한다 해도 현재까지 그 개수를 정확하게 계산할 수 있는 소수의 범위는 $10^{24}$이하까지입니다. (리만 가설이 참임을 가정하면, 이하의 소수의 개수는 정확히 18,435,599,767,349,200,867,866개임을 계산할 수 있으며, 이 개수의 진위 여부는 아주 최근에 들어서야 리만 가설을 가정하지 않는 고성능 컴퓨터를 통한 계산을 통해 검증되었을 뿐입니다.) 반면, 앞서 서술했듯이 공개키 암호화에 사용되는 소수의 크기는 이보다도 훨씬 큽니다. (기본적으로 100자리가 넘어가는 수들입니다.) 이러한 사실만 보더라도, 리만 가설 그 자체만으로는 공개키 암호화 시스템에 그 어떠한 영향도 주지 못한다는 사실을 쉽게 알 수 있습니다. 이미 리만 가설은 공개키 암호화 시스템의 붕괴에 필요한 큰 수에 대한 빠른 소인수분해 방법을 제공하지 못한다는 사실이 널리 알려져 있기도 하고요.

또한, 리만 가설 그 자체는 함수의 근에 대한 ‘실수 부분’만 고정해놓을 뿐 나머지 ‘허수 부분’에 대해서는 그 어떠한 정보도 제공해주지 않습니다. 임계선 위의 근들이 허수축에 대하여 분포되어 있는 모습을 보면, 일직선상에 나열되어 있을 뿐 그 분포 자체에 관해서는 여전히 아무것도 알려져 있지 않기 때문입니다. 따라서, 절대 다수의 수학자들은 리만 가설이 참임이 밝혀지더라도 소수의 분포가 본질적으로 불규칙하다는 생각을 바꾸지 않을 것으로 보입니다.

문제가 될 수 있는 부분은 리만 가설 그 자체가 아니라, 그 증명 과정에서 밝혀질 수 있는 소수에 관한 새로운 성질들이나 리만 가설의 증명으로부터 파생될 수 있는 새로운 연구 성과들입니다. 이러한 새로운 성질들이나 파생 연구들이 ‘소수는 불규칙하다’라는 기존의 통념을 깨고 일정한 분포의 규칙성을 발견해 내거나, 현재의 것들보다 훨씬 더 빠른 소인수분해 알고리즘이 등장한다면 공개키 암호화 체제도 무너질 가능성이 있기는 합니다. 다만 이들은 리만 가설이나 그 증명 자체와는 큰 상관이 없으며, 완전히 새로운 카테고리의 연구로 보아야 할 것입니다. 이런 발견이 단기간 내에 일어날 가능성이 극도로 낮으며, 설사 일어난다 하더라도 그 시점에서는 컴퓨터 성능의 발전이나 양자 컴퓨터의 등장 등으로 인해 이미 기존 방식의 공개키 암호화 알고리즘은 소용이 없어질 가능성이 높다는 점 또한 염두에 두어야 할 것입니다.

참고 자료

The Riemann Hypothesis, Explained: https://medium.com/@JorgenVeisdal/the-riemann-hypothesis-explained-fa01c1f75d3f . 수알못들도 리만 가설의 대략적인 내용을 이해할 수 있도록 관련한 개념들을 쉽게 설명합니다. 리만 가설에 관하여 보다 자세하게 알아보고 싶다면 천천히 읽어보실 것을 권해드립니다.