인터넷 암호 통신을 지탱하는 거대 소수의 소인수분해

우리가 매일 사용하는 인터넷 뱅킹과 온라인 쇼핑, 그리고 메신저의 비밀 대화는 한 번도 만난 적 없는 상대방과 비밀 열쇠를 공유하지 않고도 완벽하게 암호화된 통신을 주고받는다. 이 기적 같은 안전망의 중심에는 수백 자리 거대 소수 두 개를 곱하는 계산과, 그 결과물로부터 원래 소수를 역추적해 찾아내는 계산 사이의 극단적인 난이도 불균형이 자리 잡고 있다. 고대 그리스의 에라토스테네스 이래 순수 수학자들의 지적 유희로 여겨졌던 소수가 인류 문명의 디지털 신경망을 지키는 가장 견고한 요새로 변모한 것이다.

곱셈의 쉬움과 분해의 불가능성이 만드는 비대칭 열쇠

암호학의 오랜 난제는 암호화하는 규칙과 복호화하는 규칙이 동일한 대칭키 방식에서 발생했다. 비밀 열쇠를 상대방에게 안전하게 전달할 통로가 없다면 도청 위험에 상시 노출될 수밖에 없었다. 이 모순을 해결한 혁신이 바로 공개키 암호 알고리즘이다. 누구나 열쇠를 잠글 수 있는 자물쇠는 공개하고, 잠긴 자물쇠를 열 수 있는 특수한 열쇠는 수신자 혼자만 간직하는 구조다.

이 자물쇠를 만드는 핵심 재료가 바로 소수다. 수백 자리의 소수 두 개를 무작위로 골라 서로 곱하는 연산은 일반적인 스마트폰 프로세서로도 일 초도 걸리지 않는 단순한 셈법이다. 그러나 그렇게 생성된 수천 자리 합성수 하나만 덩그라니 던져주고 원래 곱해졌던 두 소수를 찾아내라는 소인수분해 문제는 차원이 다른 영역으로 진입한다. 현존하는 가장 빠른 분해 알고리즘과 전 세계의 슈퍼컴퓨터를 총동원하더라도 우주의 나이보다 긴 시간이 소요될 만큼 연산 복잡도가 기하급수적으로 폭증하기 때문이다.

오일러의 정리와 모듈러 연산이 완성한 암호 공식

단순히 소수를 곱해두기만 해서는 정보를 복호화할 통로를 만들 수 없다. 여기서 십팔 세기 수학자 레온하르트 오일러가 발견한 정수론의 위대한 정리들이 투입된다. 오일러 파이 함수는 특정 수와 서로소인 자연수의 개수를 세어주는 도구인데, 두 소수의 곱으로 이루어진 합성수의 경우 원래 두 소수에서 각각 일씩 뺀 값을 곱하기만 하면 순식간에 계산된다.

수신자는 자신이 선택한 두 소수를 알고 있기에 오일러 파이 함수 값을 정확히 계산할 수 있고, 이를 바탕으로 암호화 지수를 거꾸로 되돌리는 유일한 복호화 지수를 유도해낼 수 있다. 송신자는 공개된 합성수와 공개키로 메시지를 거듭제곱한 뒤 모듈러 연산으로 암호문을 생성한다. 도청자는 공개된 합성수만 볼 수 있으므로 원래 소수를 알지 못해 역수를 계산할 수 없고, 오직 진짜 수신자만이 단 한 번의 지수 연산으로 원래 평문을 깨끗하게 복원해낸다.

구분	송신자 (공개 정보 활용)	도청자 (외부 관찰자)	수신자 (개인 비밀 정보)
보유 정보	공개키와 거대 합성수	공개키와 거대 합성수 및 암호문	원래의 두 소수와 개인 복호화키
수행 연산	평문의 지수 거듭제곱 모듈러 계산	거대 합성수의 소인수분해 시도	개인키를 이용한 지수 거듭제곱 복원
소요 시간	일 초 미만의 즉각적 연산	슈퍼컴퓨터로 수억 년 이상 소요	일 초 미만의 즉각적 복원 연산
성공 여부	암호문 생성 완료	해독 불가능한 수학적 장벽 직면	원본 평문 완벽 복원

양자 컴퓨터의 쇼어 알고리즘과 차세대 포스트 양자 암호

수학적 난공불락으로 여겨지던 소인수분해 기반 암호 체계는 양자 컴퓨팅이라는 새로운 물리학적 패러다임 앞에서 중대한 도전을 맞이하고 있다. 수학자 피터 쇼어가 고안한 양자 알고리즘은 양자 얽힘과 중첩 상태를 이용해 함수의 주기성을 극단적인 속도로 찾아냄으로써, 기존 컴퓨터로는 불가능했던 거대 합성수의 소인수분해를 다항식 시간 안에 풀어낼 수 있음을 이론적으로 증명했다.

실용적인 대규모 양자 컴퓨터가 등장하는 날 기존의 소인수분해 기반 보안망은 일순간에 무력화될 잠재적 위험을 안고 있다. 이에 따라 전 세계 암호학계는 소인수분해 대신 격자 기반 수학 문제나 다변수 이차 다항식, 아이소제니 등 양자 컴퓨터로도 단시간에 풀 수 없는 새로운 수학적 난제를 활용한 포스트 양자 암호 체계 표준화를 서두르고 있다. 소수의 신비에서 출발한 인류의 지적 방패는 이제 더 깊고 복잡한 수학적 우주로 그 전선을 넓혀가고 있으며, 수학적 난이도의 영원한 탐색은 디지털 문명의 생존과 직결된 최전선 과제로 남아 있다.