d라이브러리

우리 주변에서 소수의 힘을 가장 크게 느낄 수 있는 분야는 암호다. 고대부터 전쟁에서 많이 쓰였던 암호는 오늘날 그 쓰임새가 더 다양해졌다. 인터넷 쇼핑, 이메일, 스마트폰, 신용카드 등 보안이 필요한 곳 어느 하나에도 암호가 안 쓰이는 곳이 없다. 

암호는 오가는 정보의 내용을 안전하게 보관하고 그 정보가 원본 그대로 조작되지 않았음을 증명한다. 또 사이버공간에서 신분을 확인하는 ‘주민등록증’ 역할도 한다. 우리가 흔히 사용하는 공인인증서를 생각하면 된다. 

이때 가장 많이 쓰이는 암호가 공개키 암호 중 하나인 ‘RSA 암호’인데, 그  원리의 핵심이 바로 소수다. 공개키 암호는 암호화하는 열쇠(공개키)와 암호를 푸는 열쇠(개인키)가 서로 달라 암호화하는 열쇠를 공개해도 아무런 문제가 없는 암호다. 

RSA 암호의 원리를 단순히 말하면 소인수분해다. 예를 들어 6은 1과 6 또는 2와 3의 곱으로 이뤄지는데, 6을 2 × 3처럼 소인수의 곱으로 표현하는 것이 소인수분해다. 

여기서 질문. ‘11 곱하기 13은?’이라고 물으면 143이라는 답을 금방 낸다. 그러나 반대로 ‘143은 어떤 소수의 곱으로 이뤄졌나?’라고 물으면 바로 답할 수 있을까? 조금 더 수의 크기를 키워보자. 소수 1031과 5119를 곱하는 것은 쉽게 할 수 있지만, 이 수를 곱한 5277689를 소인수분해 하면 몇이 되는지 빠르게 말할 수 있을까? 

아마 답을 낼 때까지 시간이 오래 걸린다. 수가 커질수록 어려워진다. 이런 현상은 사람이든 컴퓨터든 똑같다. 소인수분해를 쉽게 하는 알고리듬이 아직 발견되지 않았기 때문이다. 기본적으로 작은 소수부터 차례로 나눠떨어지는지 확인하는 수밖에는 다른 도리가 없다. 

즉 두 개의 소수를 곱하기는 쉽지만, 반대로 어떤 수를 소인수분해 하는 것은 어렵다는 말인데, RSA 암호는 정확히 이 성질을 이용한다. 암호는 푸는 데 시간이 오래 걸릴수록 강력해진다. 

현재 인터넷에서 사용하는 정보는 140자리 이상의 소수를 이용해 암호화하는데 이를 해독하려면 슈퍼컴퓨터로도 약 1만 년이 걸린다고 한다. 이 때문에 RSA 암호체계는 가장 안전한 암호체계로 불리고 있다.

대칭키 암호와 비대칭키 암호란?

고대 로마 시대 때부터 쓰였던 암호는 암호를 만드는 암호화키와 암호를 푸는 복호화키가 같은 ‘대칭키 암호시스템’이었다. 예를 들어 알파벳 순서에 따라 다섯 칸씩 미뤄서 문장을 암호화시키는 방식은 같은 방식으로 되돌려 원래 문장을 알아낼 수 있다. 

이 암호 시스템은 한두 사람이 사용할 때는 문제가 되지 않는다. 하지만 20세기 들어 통신 기술이 비약적으로 발전하면서 문제가 생겼다. 다자간 통신으로 확대되면서 비밀키가 유출되지 않도록 관리하는 일이 어려워졌고, 사전에 비밀키를 공유하기 어려운 상황도 많았다. 

미국 암호학자이자 수학자인 휫필드 디피와 마틴 헬먼은 이를 해결하는 새로운 암호시스템을 1976년 개발했다. 이른바 ‘공개키 암호시스템’이다. 공개키 암호시스템은 암호화키와 복호화키가 서로 다른 ‘비대칭키 암호시스템’으로, 암호화키를 공개해도 복호화를 위한 개인키를 알아낼 수 없고, 복호화키가 있어야만 암호를 풀 수 있는 구조다. 

공개키는 암호 방식을 담은 암호키, 즉 잠그는 역할을 하는 키다. 외부에 공개하기 때문에 공개키라고 한다. 비밀키는 암호를 푸는 키로 쓰는데, 자신만 가지기 때문에 비밀키 또는 개인키라고 한다.

예를 들어 RSA 암호는 두 소수(예로 11과 19)를 암호를 푸는 비밀키로 이용하고 두 소수를 곱해서 나온 수(209)를 공개키로 이용한다. 그러면 비밀키에서 공개키를 구하는 건 쉽지만, 공개키에서 비밀키를 구하는 건 어려운 일방향성이 생긴다. 물론 실제 RSA 암호에서는 조금 더 어려운 계산을 한다.

공개키 암호시스템은 키 관리의 어려움을 해소하고 비밀키를 공유할 수 없는 환경에 있는 사용자들이 서로 안전하게 정보를 주고받을 수 있게 해주는 매우 혁신적인 암호체계로 평가받는다.