🔐나의 신용카드 암호가 위험하다. (RSA, 공개키, 양자컴퓨터)

 

소인수분해와 암호화

 

몇 십년 전까지만 해도 숫자 이론,

다른말로 소수, 소인수 분해 그리고 정수를 다루는 수론은

실생활에 적용하기에는 너무나 먼 순수 수학의 영역이었다.

수학이 세상에서 가장 중요하다고 생각하는 수학자들 마저도

수론은 실생활이랑 상관 없다고 여겼는데

라마누잔의 멘토로 잘 알려진 영국의 수학자 G.H.Hardy는

자신은 유익한 일을 해본 적이 없다고 하며 나의 어떤 발견도 좋든 나쁘든 세상의 안락함에 직간접적으로 큰 차이를 만들지 못할 것이라고 보았다.

 

하지만 현실은 그렇게 되지 않았다.

오늘날 숫자 이론은 디지털 경제의 핵심이 되었다.

특히, 정수의 소인수 분해와 다른 수론과의 관련 기술들은 현대 암호화의 열쇠이다.

이것은 우리가 전자 상거래 사이트에서 물건을 구입하거나

극장 좌석을 예약하거나 SNS에서 가입을 인증하기 위해

매일 여러번 사용하고 있다.

어떻게 보면 수학의 그 어떤 주제와 분야보다도

수론이 우리들의 일상에 제일 밀접하게 연관되어져 있다.

 

 

RSA 암호와 수학

RSA는 암호체계를 디자인한 Ron Rivest, Adi Shamir, Leonard Adleman의 이름에서

한 글자씩 따와서 만든 이름이다. 이 암호는 현재 가장 많이 사용되는 암호체계 중 하나이다. RSA에 대한 많은 유튜브 영상이 있겠지만 여기는 수학채널이다보니 좀 더 수학적인 면에서 설명하면 다음과 같다. 여러분들도 그렇고 나도 그렇고 영어가 힘들다보니 간단한 숫자로 예시를 들어보면 여기 77이란 숫자가 있다. 77은 7곱하기 11처럼 두 소수의 곱으로 나타낼 수 있다. 이제 람다 77의 값을 구해보자. 어려운말 써서 어려워 보이지만 사실 간단한데

7과 11에서 각각 1을 뺀 후 최소공배수를 구하면 된다. 어렵지 않게 람다 77은 30이라는 것을 구할 수 있다. 이제 30보다 작은 서로소 중 아무거나 하나 골라보자. 난 17을 고르겠다. 그렇다면 17과 무엇을 곱하면 30으로 나누었을 때 나머지가 1이 나올까?...

나같은 수학 천재들은 보자마자 답을 찾아.. 미안하다 여기서는 대학교떄 배우는 유클리드 알고리즘을 이용하면 23이라는 답을 찾게 된다.

RSA암호는 여기서 23을 비밀키로 갖고 앞에 있던 77, 30, 17 중 한 숫자만 우리에게 알려준다. 그렇다면 여러분은 저 세 숫자 중 단 하나의 숫자만 보고 23을 찾을 수 있을까?

이런 어려운 과정으로 만든 암호가 바로 RSA암호이다.

그런데 지금 예시로 든 77은 두자리 숫자지만 실제로 현재 RSA암호에서 쓰고 있는 숫자는 길이가 최소 100자리가 넘어간다.

우리의 생각보다 암호가 더 어렵게 만들어져 있다.

 

 

소인수분해 알고리즘

RSA 암호체계는 큰 수가 분해가 어렵다는 사실로 부터 출발한다.

그렇다면 큰 수를 분해하는 것은 얼마나 어려울까?

RSA 암호가 1977년에 처음 발표된 직후,

Scientific American 독자들에게

129자리 암호문을 해독하는 문제를 냈다.

그당시 무려 100달러를 걸고말이다.

아 물론 그 당시 100달러는 조금 큰 돈이었다.

Rivest는 당시 알려진 정수 인수 분해 체계를 고려할 때

129 자리 정수를 인수 분해하려면 그 당시 가장 빠른 컴퓨터에서

40 조 년이 필요할 것이라고 추정했다.

하지만 수학자들은 100달러를 벌기 위해 미친듯이 연구 했고

1994년 4월 RSA로 숨겨진암호문은

마법의 주문은 까다로운 수염수리(The Magic Words are Squeamish Ossifrage)

.라는 것을 찾아내며 100달러를 거머쥐었다.

1994년에 말이다.. 1994년에 10만원 벌려고..

쨋든 중요한건 이런 암호를 해독하기 위하여 수학자들은

우리가 아는 평범한 소인수 분해가 아닌 큰 수를 효과적으로 다양한 소인수분해를 개발하기 시작했다.

 

예를 들면 다음과 같은 4개의 소인수 분해를 하는 알고리즘이 있는데 궁금한 분들은 아래 링크를 달아놓을테니 보길 바란다.

Continued fraction factorization.

Quadratic sieve factorization.

Pollard’s rho algorithm.

General number field sieve factorization.

 

 

 

나의 카드 비밀번호는 안전한가?

1991년부터 2007년까지 RSA Security는 자신들의 암호체계의 발전을 위해 RSA챌린지라고 불리는 소인수분해문제를 제시하고 문제를 풀면서 다양한 소인수분해 솔루션들이 발전했다. 이제 더이상 상금을 주지는 않지만 그래도 수학자들은 꾸준히 암호를 풀기위해 도전하고 있으며 2019년 12월을 기준으로 54개의 문제 중에서 20문제가 풀렸고 그 중 가장 최근 문제는 240자리 정수를 인수분해한 결과는 다음과 같다. 너무 길어서 읽을 수는 없지만 이 숫자를 인수분해 하려면 최신 알고리즘을 사용하더라도 900개의 cpu를 가진 컴퓨터를 1년 내내 돌려야한다고 한다. RSA를 사용하는 현재 전자 상거래는 1024비트 또는 2048 비트 정수를 기반으로 한다. 아까 말한 240자리 정수는 795비트이므로 현재 최첨단 기술을 사용하더라도 우리가 사용하는 암호는 안전하다. 하지만 현장에서는 1024비트는 곧 위험해 질 수 있으므로 2048비트 암호가 표준이 되어야 한다고 권장한다.

하지만 수학자들은 인수분해를 연구하고 있으며 예전에 40조년이 걸린다는 문제들도 새로운 알고리즘으로 미친듯한 속도로 풀어내고 있다. 아직도 발견되지 않은 방법은 많을 것이며 컴퓨터 또한 엄청난 속도로 발전하면서 소인수분해를 기반으로 하는 은행계좌와 블록체인을 사용하는 비트코인마저도 위험해지기 시작했다.

 

 

 

양자 컴퓨터는 내 암호를 해독할 수 있을까?

1994년 미국의 수학자 피터 쇼어는 쇼어 알고리즘을 발표했다. 쇼어 알고리즘이란 양자 알고리즘을 통해 소인수 분해를 빠르게 처리할 수 있는 방법이다. 아직 양자컴퓨터는 초기단계지만 양자컴퓨터가 더 발전한다면 RSA암호를 무력화시킬 수 있는 방법은 이미 25년 전에 개발되어 있었다.

그러나 실제로 실용적인 양자 컴퓨터를 개발하는 것은 아직은 어렵다. 현재 프로토타입의 시스템은 일반적으로 절대 영도, 약 -273도에 가깝게 냉각된 상태에서 작동하며 캐나다의 D-wave사에서는 몇가지 성공을 거두었지만 아직까지 이러한 컴퓨터는 간단한 데모작업만 수행할 수 있다.

최근 google에서 발표하 양자 컴퓨터에서 양자우위를 달성했다고 발표했지만 IBM에서는 구글의 시연에서 결함이 있다고 주장하는 논문을 발표했다. 간단하게 요약하면 기존 컴퓨터와 비교했을 때 오늘날 슈퍼컴퓨터에서 이용할 수 있는 대용량 스토리지 시스템을 충분히 활용하지 못했기 때문이라는 것인데 여기는 수학보다는 컴퓨터 공학쪽이라 잠깐 접어두자.

그렇다면 이런 양자컴퓨터로 소인수분해가 가능할까? IBM에서는 쇼어알고리즘을 이용하여 인수분해하는 새로운 체계를 개발했으며 1조995억5147만3989을 인수분해 하여 104만8589 x 104만8601라는 결과를 얻어냈다. 그러나 이런 성과는 앞에 240자리를 인수분해한 슈퍼컴퓨터와 비교하면 아직은 차이가 심하다. 다른말로 아직 양자 컴퓨터는 갈 길이 멀다. 프랑스 물리학자 Mikhail Dyakonov는 아직 양자컴퓨터에는 해결되지 않은 문제들이 많이 남아있고, 어려운 문제를 풀어내기 위해서는 수백만 큐빗을 조작해야하는데 이 격차는 곧 끝나지 않을 것이라고 밝혔다.

 

최신 수학과 컴퓨터 공학으로는 아직 RSA암호체계를 무너뜨릴 수 없다. 하지만 수학에서는 계속 새로운 법칙과 알고리즘을 제시하고 양자컴퓨터도 아직은 초기단계지만 발전해나가고 있다. 아직은 먼 미래의 일이라고 하지만 40조년이 걸린다는 암호를 17년만에 풀어낸 우리는 생각보다 더 빨리 RSA암호체계를 무너뜨릴 수도 있다고 생각한다.(수학자들이 얼마나 잠을 안자느냐의 문제일 수도…)

 

오늘 수업은 여기까지

​

​

구글 논문 : https://www.nature.com/articles/s41586-019-1666-5

IBM논문 : https://arxiv.org/pdf/1910.09534.pd