목차
우리가 매일 인터넷에 접속하고, 메신저로 대화를 나누고, 온라인 쇼핑을 할 때 우리 눈에는 보이지 않지만 쉼 없이 일하고 있는 존재가 있습니다. 바로 ‘암호(Cryptography)’입니다.
복잡한 정보의 숲에서 우리의 소중한 개인정보를 지켜주는 이 든든한 자물쇠의 핵심 재료는 놀랍게도 ‘소수(Prime Number)’를 이용합니다.
오늘은 소수가 어떻게 디지털 세계의 보안관이 되었는지, 그리고 미래의 기술이 이 자물쇠를 어떻게 위협하고 있는지 그 흥미로운 이야기들을 살펴보겠습니다.
1. 소수의 특별한 성질을 이용한 암호화 방법
소수는 1과 자기 자신만으로 나누어떨어지는 수입니다.
소수는 ‘수의 DNA’라고 할 수 있습니다. 모든 자연수는 소수들의 곱으로 쪼개질 수 있기 때문입니다. 이를 소인수분해라고 합니다.
암호 체계에서 소수가 선택된 이유는 아주 단순하면서도 강력한 특징 때문입니다.
“곱하기는 아주 쉽지만, 거꾸로 나누는 것은 상상을 초월할 정도로 어렵다.”
이것이 바로 현대 암호학의 가장 중요한 원리 중 하나인 ‘일방향 함수(One-Way Function)‘의 개념입니다.
암호화의 핵심 원리인 ‘일방향 함수’는 말 그대로 “한쪽 방향으로는 가기 쉽지만, 반대 방향으로는 돌아오기 매우 어려운 함수”를 말합니다.
우리 주변에서도 일방향성을 쉽게 발견할 수 있습니다.
요리를 할 때 생각해봅시다. 소고기를 갈아서 햄버거 패티를 만드는 것은 쉽지만, 갈린 패티를 다시 원래의 소고기 덩어리로 완벽하게 되돌리는 것은 불가능에 가깝습니다.
또, 깨끗한 물에 소금을 타서 소금물을 만드는 것은 한순간이지만, 그 물에서 소금 알갱이 하나하나를 원래 모양대로 다시 분리해내는 것은 훨씬 많은 에너지가 필요하죠.
종이를 문서 분쇄기에 넣는 것은 1초면 충분하지만, 수만 조각으로 나뉜 종이를 원래 문서로 완벽하게 이어 붙이는 데는 엄청난 시간이 걸립니다.
2. 곱하기는 1초, 소인수분해는 1억 년?
예를 들어 볼까요?
두 소수 13과 17을 곱하는 것은 초등학생도 금방 할 수 있습니다. 답은 221이죠.
하지만 반대로 누군가에게 “221은 어떤 소수 두 개의 곱일까?”라고 묻는다면, 아까보다는 시간이 조금 더 걸릴 겁니다.
이제 숫자를 아주 크게 키워보겠습니다. 53,248,231은 어떤 두 수의 곱일까요?
이 질문에 우리는 쉽게 답할 수 없습니다.
$$ 7841 \times 6791 = 53248231 $$
하지만 이 정도 수는 컴퓨터를 이용하면 시간은 조금 걸리겠지만, 빠른 시간에 해결할 수 있습니다.
만약 300자리가 넘는 거대한 소수 두 개(p, q)를 곱한 수는 어떨까요? 두 소수를 곱해서 나온 수 N이 있다고 가정해 봅시다.
$$ N = p \times q $$
컴퓨터는 p와 q를 곱해서 N을 만드는 데 1초도 걸리지 않습니다.
하지만 오직 결과물인 N만 알고 있는 해커가 p와 q가 무엇인지 찾아내려면(소인수분해), 현재 가장 빠른 슈퍼컴퓨터를 총동원해도 수억 년 이상의 시간이 걸립니다.
우리가 사용하는 비밀번호 체계는 바로 이 ‘시간의 벽’을 자물쇠로 사용합니다.
우리가 로그인을 할 때 서버는 우리가 가진 ‘열쇠(p, q)’가 ‘자물쇠(N)’와 맞는지 확인하는 것이죠.
3. 디지털 금고의 설계도: RSA 암호
이 원리를 이용해 만든 대표적인 암호 방식이 바로 RSA 암호입니다.
RSA암호는 1977년, 미국 매사추세츠 공과대학교(MIT)에 다니던 세 명의 천재 수학자가 힘을 합쳐 발명되었습니다.
- Ronald Rivest (로널드 리베스트)
- Shadi Shamir (아디 샤미르)
- Adleman, Leonard (레너드 애들먼)
이 세 사람의 이름 앞글자를 합쳐서 RSA가 되었죠.
이 방식은 두 가지 열쇠를 사용합니다.
1) 누구나 잠글 수 있는 ‘공개 자물쇠’ (공개키)
여러분이 친구에게 비밀 편지를 보내고 싶다고 해볼게요.
저는 세상 모든 사람에게 “누구든 나한테 편지 쓸 때는 이 자물쇠를 사용해서 상자를 잠가줘!”라고 말하며 자물쇠 수천 개를 뿌립니다. 이 자물쇠는 누구나 가질 수 있고, 상자를 넣고 딸깍! 잠그는 것도 아주 쉬워요.
바로 누구나 볼 수 있도록 공개된 아주 큰 수 N이 자물쇠 역할을 합니다. 정보를 보낼 때 이 숫자를 이용해 상자를 잠급니다.
2) 나만 가진 ‘비밀 열쇠’ (개인키)
하지만 이 자물쇠를 열 수 있는 열쇠는 세상에 딱 하나뿐이고, 그건 제가 주머니에 쏙 넣고 있어요. 자물쇠를 잠근 사람조차도 열쇠가 없으면 다시 열 수 없답니다. 오직 나만이 그 비밀 편지를 읽을 수 있는 것이죠.
N을 만드는 데 사용된 원래의 두 소수 p와 q가 비밀 열쇠 역할을 합니다. 오직 나만 알고 있으며, 잠긴 상자를 열 수 있는 유일한 도구입니다.
누구나 자물쇠를 채울 수는 있지만, 그 자물쇠를 부수지 않고 빠른 시간에 열 수 있는 사람은 원래의 재료인 두 소수를 알고 있는 주인뿐입니다.
4. 새로운 도전자의 등장: 양자 컴퓨터의 위협
그런데 최근 이 튼튼한 방벽에 금이 가기 시작했다는 소식이 들려옵니다. 바로 양자 컴퓨터(Quantum Computer)의 등장 때문입니다.
기존의 컴퓨터가 0과 1을 순서대로 계산하는 방식이라면, 양자 컴퓨터는 ‘양자 중첩’이라는 현상을 이용해 수많은 계산을 동시에 처리합니다. 마치 미로에서 한 길씩 가보는 것이 아니라, 수천 명의 분신이 동시에 모든 길을 가보는 것과 비슷하죠.
1994년 피터 쇼어는 양자 컴퓨터가 실용화되면 아주 큰 수의 소인수분해를 순식간에 해낼 수 있다는 것을 증명했습니다.
만약 성능이 충분한 양자 컴퓨터가 완성된다면, 현재 우리가 사용하는 소수 기반의 암호 체계는 순식간에 무력화될 수 있습니다. 우리가 사용하는 은행 계좌, 국가 기밀, 개인 메시지가 모두 양자컴퓨터의 계산능력으로 암호가 뚫릴 수도 있다는 뜻입니다.
마치며: 수학은 멈추지 않는다
그렇다면 우리는 이제 무방비 상태가 되는 걸까요?
다행히 인류는 이미 다음 단계를 준비하고 있습니다. 양자 컴퓨터로도 풀기 어려운 더 복잡한 수학 문제를 이용한 ‘양자 내성 암호(PQC)’ 연구가 활발히 진행 중이죠.
결국 암호의 역사는 ‘더 단단한 자물쇠를 만들려는 수학자’와 ‘그것을 깨려는 도전자’ 사이의 끝없는 지략 대결입니다. 학교 교과서에서 만난 작은 소수가 실은 거대한 디지털 제국을 지탱하는 가장 강력한 기둥이었다는 사실, 정말 놀랍지 않나요?