공개키 암호 원리 쉽게 이해하기: 소인수분해의 비대칭성과 RSA 계산 예시로 보는 보안의 기초

핵심 메시지

• 대칭키 암호는 키를 먼저 공유해야 하는데, 그 키를 보낼 안전한 통로가 없다는 것이 근본적인 딜레마다.
• 두 소수를 곱하는 것은 순식간이지만 그 곱을 다시 소인수로 되돌리는 것은 극단적으로 느리다는 비대칭성이 공개키 암호의 재료다.
• 공개키는 누구나 채울 수 있는 열린 자물쇠이고, 그 자물쇠를 열 수 있는 열쇠는 오직 개인키뿐이다.
• 작은 숫자로 직접 계산해 보면 원리가 드러난다. 두 소수 5와 11로 만든 55를 써서 메시지 7을 13으로 바꾸고, 개인키로 다시 7을 복원할 수 있다.
• 실제 시스템에서 쓰는 수는 약 2000비트 규모라 소인수분해에 우주의 나이보다 긴 시간이 걸리며, HTTPS와 메신저, 서명된 소프트웨어 업데이트가 모두 이 원리 위에 서 있다.

쉽게 이해하기

앨리스가 밥에게 비밀 메시지를 보내려는데, 둘을 잇는 유일한 선은 모든 바이트를 엿보는 이브 앞을 지나간다. 흔한 해법은 같은 열쇠로 메시지를 잠그는 것이지만 여기엔 함정이 있다. 두 사람이 한 번도 만난 적이 없다면, 그 열쇠 자체를 이브가 듣고 있는 바로 그 선으로 보내야 한다. 비밀을 나누기 위해 이미 비밀 통로가 필요해지는 셈이다.

돌파구는 컴퓨터가 잘하는 일과 못하는 일의 격차에 있다. 꽤 큰 소수 두 개를 곱하는 계산은 마이크로초 단위로 끝나지만, 반대로 큰 수를 받아 그것을 만든 두 소수를 찾아내는 일은 지독하게 느리다. 한쪽 방향은 순식간이고 반대 방향은 우주가 존재한 시간보다 오래 걸릴 수 있다는 이 비대칭이 바로 필요한 재료다.

그래서 앨리스는 열쇠를 한 쌍으로 만든다. 그중 하나는 열린 자물쇠에 가깝다. 복제해서 세상에 뿌려 두면 밥을 포함해 누구나 주워 갈 수 있다. 밥은 앨리스에게 비밀 메시지를 보낼 때 그 자물쇠로 상자를 잠가 돌려보내기만 하면 된다. 그 자물쇠에 맞는 개인 열쇠는 앨리스만 가지고 있으므로, 통로가 완전히 공개돼 있어도 내용은 봉인된 채 남는다.

실제 숫자로 따라가 보면 이렇다. 앨리스가 작은 소수 5와 11을 골라 곱하면 55가 나오고, 여기서 40이라는 값을 계산한다. 공개 지수로 3을 고르면 짝이 되는 개인 지수는 27이 된다. 앨리스가 55와 3을 공개하면, 밥은 메시지 7을 세 제곱해 55로 나눈 나머지인 13을 보낸다. 앨리스는 13을 27제곱해 55로 나눈 나머지를 구해 원래의 7을 되찾는다.

이브가 이 구조를 깨려면 공개된 정보에서 개인 지수를 복원해야 하고, 그러려면 40을 알아야 하며, 그러려면 원래의 두 소수를 알아야 하고, 결국 55를 소인수분해해야 한다. 작은 수에서는 쉬운 일이다. 하지만 실제 시스템의 수는 약 2000비트 길이라 같은 작업에 인류 역사 전체보다 긴 시간이 든다. 벽이 정확히 그 지점에 서 있기 때문에 자물쇠가 버틴다.

주요 인사이트

• 암호의 안전성은 '계산이 불가능하다'가 아니라 '계산이 현실적인 시간 안에 끝나지 않는다'에 기대고 있다. 벽의 위치는 수학적 절대성이 아니라 계산 비용의 격차로 정해진다.
• 키 배포 문제를 정면으로 푸는 대신 우회한 것이 공개키 암호의 발상이다. 비밀 통로 없이 비밀을 만드는 것이 아니라, 애초에 공개돼도 무해한 절반을 분리해 낸 것이다.
• 작은 소수로 직접 계산해 보면 원리를 손에 잡히게 이해할 수 있지만, 같은 계산이 안전해지는 것은 오직 수가 충분히 클 때뿐이다. 원리의 이해와 실제 안전성은 다른 층위의 문제다.
• HTTPS, 메신저, 서명된 소프트웨어 업데이트, 암호화폐 지갑이 전부 같은 비대칭 하나에 기대고 있다. 소인수분해를 빠르게 푸는 방법이 나온다면 흔들리는 범위도 그만큼 넓다는 뜻이다.

자주 묻는 질문

관련 AI 소식