인터넷 결제를 지키는 큰 수의 소인수분해

인터넷 결제가 안전한 이유는 '큰 수를 소인수로 쪼개기는 매우 어렵다'는 사실 하나에 크게 기대고 있다. 두 개의 큰 소수를 곱하는 것은 컴퓨터로 순식간에 끝나지만, 그렇게 얻은 수에서 원래의 두 소수를 거꾸로 찾아내는 것은 현재의 컴퓨터로 현실적인 시간 안에 할 수 없다. 공개키 암호는 이 비대칭을 자물쇠로 쓴다.

왜 '공개'키가 필요했나

오래된 암호는 대부분 대칭키 방식이다. 잠그는 열쇠와 여는 열쇠가 같다. 문제는 그 열쇠를 상대에게 어떻게 안전하게 건네느냐다. 처음 거래하는 온라인 쇼핑몰과 미리 비밀번호를 나눠 가질 방법이 없다. 열쇠를 인터넷으로 보내면 중간에서 누군가 가로챌 수 있다.

1970년대에 이 문제를 뒤집는 생각이 나왔다. 잠그는 열쇠와 여는 열쇠를 다르게 만드는 것이다. 잠그는 열쇠는 누구에게나 공개해도 된다. 그 열쇠로 잠근 상자는 여는 열쇠를 가진 사람만 열 수 있다. 누구나 넣을 수 있지만 주인만 꺼낼 수 있는 우체통과 비슷하다. 이것이 공개키 암호다. 1977년 리베스트, 샤미르, 애들먼이 발표한 RSA는 그 대표적인 방식이며, 세 사람의 이름 머리글자를 땄다.

곱셈과 소인수분해는 얼마나 다르게 어렵나

소수는 1과 자기 자신으로만 나누어지는 수다. 모든 자연수는 소수들의 곱으로 단 한 가지 방식으로 나타낼 수 있다. 15는 3과 5의 곱이고, 91은 7과 13의 곱이다.

작은 수는 쪼개기 쉽다. 그러나 수가 커지면 이야기가 달라진다. 수백 자리짜리 두 소수를 곱하는 계산은 일반 컴퓨터로 눈 깜짝할 사이에 끝난다. 반대로 수백 자리짜리 곱에서 두 소수를 찾으려면, 알려진 가장 좋은 방법을 써도 필요한 계산량이 수의 자릿수가 늘어날수록 가파르게 불어난다. 실제 암호에 쓰이는 크기의 수라면 현존하는 컴퓨터를 모두 모아도 사실상 끝낼 수 없다고 여겨진다.

계산	방향	어려움
두 소수 곱하기	소수 → 곱	매우 쉬움
곱을 소인수분해	곱 → 소수	수가 크면 사실상 불가능
큰 소수 찾기	—	판별법이 있어 쉬운 편

큰 소수를 새로 찾는 일 자체는 생각보다 어렵지 않다는 점도 중요하다. 어떤 수가 소수인지 판별하는 효율적인 방법이 있어서, 암호에 쓸 새 소수를 필요할 때마다 만들어 낼 수 있다.

RSA 자물쇠는 어떻게 만들어지나

원리를 단순하게 정리하면 이렇다. 먼저 아주 큰 소수 두 개를 몰래 고르고 곱한다. 이 곱이 공개키의 핵심이 된다. 곱은 세상에 공개해도 된다. 메시지를 보내려는 사람은 이 공개된 수를 이용해 메시지를 일정한 방식으로 거듭제곱하고 나머지를 구해 암호문을 만든다.

암호문을 풀려면 이 계산을 되돌려야 하는데, 되돌리는 데 필요한 수를 구하려면 원래의 두 소수를 알아야 한다. 두 소수를 아는 주인은 쉽게 풀고, 곱만 아는 다른 사람은 소인수분해라는 벽에 막힌다. 수학적으로는 나머지 연산의 성질과 오일러가 정리한 정수론의 정리가 이 과정을 떠받친다.

실제 인터넷 통신에서는 공개키 암호를 처음 연결할 때만 쓰는 경우가 많다. 공개키 방식은 계산이 무거워서, 이것으로 대칭키 하나를 안전하게 주고받은 뒤 본격적인 데이터는 빠른 대칭키로 암호화한다. 주소창의 자물쇠 표시 뒤에서 이런 과정이 매번 일어난다.

남은 과제

RSA의 안전성은 '소인수분해가 어렵다'는 믿음 위에 서 있지만, 그 어려움이 수학적으로 증명된 것은 아니다. 지금까지 아무도 빠른 방법을 찾지 못했을 뿐이다. 누군가 획기적인 방법을 찾아낸다면 지금의 많은 암호가 한꺼번에 흔들린다.

더 구체적인 위협은 양자 컴퓨터다. 1994년 피터 쇼어는 충분히 큰 양자 컴퓨터가 있다면 소인수분해를 빠르게 해낼 수 있는 방법을 제시했다. 아직 그만한 규모의 양자 컴퓨터는 없지만, 대비는 이미 시작되었다. 양자 컴퓨터로도 풀기 어렵다고 여겨지는 다른 수학 문제에 기반한 새로운 암호 표준이 정해지고, 기존 체계를 이것으로 옮기는 작업이 진행되고 있다.