우리가 매일 쓰는 인터넷 뱅킹, 로그인, 메신저는 전부 암호화되어 있어요. 그 암호화의 핵심에는 아주 단순한 수학적 사실이 있어요 — "두 소수를 곱하는 건 쉽지만, 그 곱을 다시 두 소수로 나누는 건 아주 어렵다"는 거예요. 작은 숫자로 그 원리를 직접 체험해봐요 (일부 내용은 고등학교 수준이에요).
15 = 3×5라는 걸 확인하는 건 순식간이에요. 그런데 거꾸로 "15를 소인수분해하면?"이라는 질문도 여전히 쉬워요. 문제는 숫자가 커질 때예요. 두 소수를 곱해서 600자리가 넘는 큰 수를 만드는 건 컴퓨터로 순식간이지만, 그 큰 수만 보고 원래 두 소수를 찾아내는 건 슈퍼컴퓨터로도 사실상 불가능해요. RSA 암호는 이 "곱하기는 쉽지만 나누기(인수분해)는 어렵다"는 비대칭성을 열쇠로 사용해요.
숫자를 고르고, 그 수를 나누어떨어지게 하는 약수를 직접 입력해서 찾아보세요. 몇 번 만에 찾는지 세어보면 숫자가 커질수록 얼마나 힘들어지는지 몸으로 느낄 수 있어요.
진짜 RSA는 수백 자리 소수를 쓰지만, 원리를 보기 위해 p=5, q=11이라는 아주 작은 소수로 키를 만들어봐요.
메시지를 숫자 하나(m)라고 생각해봐요. 공개키(e)로 암호화하고, 나만 아는 비밀키(d)로 다시 원래 숫자로 복호화해봐요.
암호화에 쓰는 공개키(n과 e)는 누구나 볼 수 있어요. 그런데 이걸로 원래 메시지를 알아내려면 n을 소인수분해해서 p와 q를 찾아야 해요. 우리가 쓴 예제(n=55)는 5×11로 3초면 풀리지만, 실제 RSA는 n이 600자리가 넘는 수예요.
이런 크기의 수는 지금 있는 모든 컴퓨터를 다 동원해도 우주의 나이보다 오랜 시간이 걸릴 거라고 추정돼요. 그래서 n을 공개해도 안전해요 — 소인수분해가 어렵다는 "수학적으로 증명되진 않았지만 실제로 아무도 빠른 방법을 못 찾은" 사실이 우리의 온라인 보안을 지켜주고 있는 셈이에요.
타원곡선 암호(ECC)는 소인수분해 대신 "타원곡선 위의 이산로그 문제"라는 또 다른 어려운 수학 문제를 이용해요. 원리는 다르지만 목적은 같아요 — 한쪽 방향(계산)은 쉽고 반대 방향(역산)은 아주 어려운 수학 문제를 찾는 거죠. ECC는 RSA보다 훨씬 짧은 키로 비슷한 수준의 안전성을 낼 수 있어서, 배터리와 처리 능력이 부족한 스마트폰이나 IoT 기기, 비트코인 같은 암호화폐 지갑에 특히 많이 쓰여요.
양자컴퓨터라는 새로운 위협도 있어요. 쇼어 알고리즘이라는 양자 알고리즘은 이론적으로 소인수분해와 이산로그 문제를 훨씬 빠르게 풀 수 있다고 알려져 있어요. 지금 수준의 양자컴퓨터로는 아직 실제 RSA를 깰 수 없지만, 앞으로 크고 안정적인 양자컴퓨터가 만들어지면 RSA와 ECC 둘 다 위험해질 수 있어요.
그래서 양자컴퓨터로도 풀기 어려운 새로운 수학 문제(예: 격자 문제)를 기반으로 한 "포스트 양자 암호"가 활발히 연구되고 있어요. 미국 표준기술연구소(NIST)는 2024년에 이런 포스트 양자 암호의 첫 공식 표준을 발표했고, 앞으로 점차 지금의 RSA·ECC를 대체하거나 함께 쓰일 걸로 예상돼요.