우리가 매일 쓰는 인터넷 뱅킹, 로그인, 메신저는 전부 암호화되어 있어요. 그 암호화의 핵심에는 아주 단순한 수학적 사실이 있어요 — 두 소수를 곱하는 건 쉽지만, 그 곱을 다시 두 소수로 나누는 건 아주 어렵다는 거예요.
15 = 3×5라는 걸 확인하는 건 순식간이에요. 거꾸로 '15를 소인수분해하면?'이라는 질문도 여전히 쉽죠. 문제는 숫자가 커질 때예요. 두 소수를 곱해서 600자리가 넘는 큰 수를 만드는 건 컴퓨터로 순식간이지만, 그 큰 수만 보고 원래 두 소수를 찾아내는 건 슈퍼컴퓨터로도 사실상 불가능해요. RSA 암호는 이 '곱하기는 쉽지만 인수분해는 어렵다'는 비대칭성을 열쇠로 사용해요.
작은 숫자로 원리를 체험해볼 수 있어요. 소수 p=5, q=11을 고르면 n=p×q=55가 돼요. 메시지를 숫자 하나(m)라고 생각하면, 공개키(e)로 암호화한 뒤 나만 아는 비밀키(d)로 다시 원래 숫자로 복호화할 수 있어요. 암호화에 쓰는 n과 e는 누구나 볼 수 있지만, 이걸로 원래 메시지를 알아내려면 n을 소인수분해해서 p와 q를 찾아야 해요. 우리 예제(n=55)는 5×11로 순식간에 풀리지만, 실제 RSA는 n이 600자리가 넘는 수라서 지금 있는 모든 컴퓨터를 다 동원해도 우주의 나이보다 오랜 시간이 걸릴 거라고 추정돼요.
RSA는 1977년 리베스트, 샤미르, 애들먼(이름의 첫 글자를 따서 RSA) 세 사람이 만들었어요. '소인수분해가 어렵다는 게 수학적으로 완전히 증명된 사실은 아니지만, 실제로 아무도 빠른 방법을 찾지 못했다'는 현실이 지금 우리의 온라인 보안을 지켜주고 있는 셈이에요.
다른 방식의 암호도 있어요. 타원곡선 암호(ECC)는 소인수분해 대신 타원곡선 위의 이산로그 문제라는 또 다른 어려운 수학 문제를 이용해요. RSA보다 짧은 키로 비슷한 안전성을 낼 수 있어서 스마트폰이나 암호화폐 지갑에 많이 쓰여요. 한편 양자컴퓨터라는 새로운 위협도 있어요. 쇼어 알고리즘이라는 양자 알고리즘은 이론적으로 소인수분해를 훨씬 빠르게 풀 수 있다고 알려져 있어서, 크고 안정적인 양자컴퓨터가 등장하면 RSA와 ECC 둘 다 위험해질 수 있어요. 그래서 양자컴퓨터로도 풀기 어려운 새로운 수학 문제를 기반으로 한 '포스트 양자 암호'가 활발히 연구되고 있고, 미국 표준기술연구소(NIST)는 2024년에 이런 포스트 양자 암호의 첫 공식 표준을 발표했어요. 저희 체험 페이지에서는 작은 숫자로 소인수분해의 어려움을 직접 체험하고, RSA 키를 만들어 암호화·복호화 과정을 단계별로 따라가 볼 수 있어요.