[호평동 수학학원] 소수(素數)는 왜 인터넷 보안을 지킬까

중학교 수학에서 소수를 처음 배울 때는 1과 자기 자신만을 약수로 가지는 수라고 외우고 넘어가는 경우가 많습니다. 2, 3, 5, 7, 11처럼 더는 쪼갤 수 없는 수라는 정도로 기억하고, 소인수분해 문제를 풀 때 잠깐 쓰고 지나갑니다. 그런데 이 소수라는 개념이 우리가 매일 쓰는 인터넷 보안의 뼈대를 이루고 있다는 사실은 의외로 잘 알려져 있지 않습니다.

먼저 소인수분해가 왜 어려운 일인지부터 생각해 보겠습니다. 어떤 수를 소수들의 곱으로 나타내는 것, 즉 소인수분해는 중학교 1학년 과정에서 배우는 내용입니다. 예를 들어 60을 소인수분해하면 60 = 2² × 3 × 5가 됩니다. 이 정도 크기의 수는 암산으로도 금방 됩니다.

그런데 숫자가 커지면 이야기가 완전히 달라집니다. 가령 두 자리 소수 두 개, 53과 61을 곱해 보겠습니다. 53 × 61 = 3233입니다. 이 곱셈은 몇 초면 끝납니다. 하지만 반대로 3233이라는 숫자 하나만 주어졌을 때, 이것이 어떤 두 소수의 곱인지 거꾸로 찾아내는 일은 훨씬 오래 걸립니다.

2로도 나누어 보고 3으로도 나누어 보고, 7, 11, 13, 17 하며 하나씩 시도해야 53과 61을 찾아낼 수 있습니다.

여기서 핵심은 곱하는 것과 쪼개는 것 사이의 비대칭입니다. 곱셈은 쉽고 빠르지만, 그 역방향인 소인수분해는 어렵고 느립니다. 두 자리 수끼리의 곱 정도는 사람이 손으로도 찾아낼 수 있지만, 자릿수가 100자리, 200자리로 커지면 이야기가 완전히 달라집니다. 아무리 빠른 컴퓨터를 쓰더라도 아주 큰 합성수를 소인수분해하는 데에는 현실적으로 감당하기 어려운 시간이 걸립니다. 반면 두 개의 큰 소수를 골라 곱하는 계산은 컴퓨터에게는 순식간에 끝나는 일입니다.

바로 이 비대칭성을 이용한 것이 RSA라는 암호 방식입니다. 인터넷에서 비밀번호나 카드 정보를 주고받을 때, 두 개의 아주 큰 소수를 곱해서 만든 수를 공개된 열쇠로 사용합니다. 이 공개된 수를 다른 사람이 보더라도, 원래 어떤 두 소수를 곱해서 만들었는지 거꾸로 알아내기가 현실적으로 매우 어렵기 때문에 정보가 안전하게 지켜지는 것입니다.

열쇠를 만드는 사람은 두 소수를 알고 있으니 쉽게 암호를 풀 수 있지만, 그 수만 가로챈 사람은 소인수분해라는 어려운 문제 앞에서 막히게 됩니다.

중학교 수학 시간에 소인수분해를 배울 때는 보통 36이나 72처럼 작은 수로 연습합니다. 이런 수는 나무 모양으로 가지를 치며 2로 나누고 3으로 나누다 보면 금방 끝이 납니다. 그래서 소인수분해가 원래 어려운 작업이라는 느낌을 받기가 쉽지 않습니다. 작은 수에서는 쉬운 일이, 수백 자리 큰 수에서는 세상에서 가장 믿을 만한 자물쇠가 된다는 사실이 흥미로운 부분입니다.

소수가 몇 개나 있는지도 생각해 볼 만한 질문입니다. 소수는 2, 3, 5, 7, 11처럼 끝없이 이어지는데, 소수의 개수가 유한하지 않고 무한히 많다는 사실은 고대 그리스 수학자 유클리드가 증명했다고 알려져 있습니다. 소수가 무한히 많기 때문에, 암호를 만들 때 쓸 수 있는 큰 소수의 재료도 무한히 많습니다. 같은 소수를 자꾸 재사용할 걱정 없이 늘 새로운 소수 쌍을 골라 쓸 수 있다는 뜻입니다.

결국 교과서 한 귀퉁이에서 배우는 소수의 정의가, 전혀 다른 분야인 통신 보안의 기초 원리로 이어지는 셈입니다. 지금 풀고 있는 소인수분해 문제가 당장 실생활에 쓸모없어 보일 수 있지만, 같은 원리가 규모만 커지면 우리가 매일 쓰는 인터넷 결제와 로그인을 지켜 주는 도구가 된다는 점은 기억해 둘 만합니다.