RSA 해설

브라우저에 자물쇠가 표시될 때, 메시지에 서명할 때, 소프트웨어가 업데이트를 확인할 때마다 공개 키 암호가 작동하고 있으며, RSA는 그중 가장 잘 알려진 형태입니다. 그 아이디어는 메시지를 잠그는 키는 공개해도 되고, 여는 키만 비공개로 간직한다는 것입니다. 놀랍게도 이 체계 전체는 학교에서 배우는 산수, 즉 소수, 곱셈, 나머지 위에 서 있습니다.

비밀 소수 61과 53이 공개 법 3233이 된다. HELLO의 글자는 공개 지수 17로 3000, 28, 2726, 2726, 1307이 되고, 개인 지수 2753이 3000을 다시 72로 되돌린다
비밀 소수 61과 53이 공개 법 3233이 된다. HELLO의 글자는 공개 지수 17로 3000, 28, 2726, 2726, 1307이 되고, 개인 지수 2753이 3000을 다시 72로 되돌린다

RSA가 해결하는 문제

카이사르의 자리 이동 암호부터 현대의 AES까지, 기존의 암호는 잠글 때와 열 때 같은 키를 쓰므로 양쪽은 먼저 비밀 키를 몰래 공유해야 합니다. 공개 키 암호는 그 단계를 없앱니다. 각 사람은 키를 두 개 가집니다. 누구나 그 사람에게 보낼 메시지를 암호화하는 데 쓸 수 있는 공개 키와, 그 사람만 가지고 있으며 그것만이 메시지를 복호화할 수 있는 개인 키입니다. 휫필드 디피와 마틴 헬먼이 1976년에 이 아이디어를 제시했고, 1년 뒤 MIT의 론 리베스트, 아디 샤미르, 레너드 애들먼이 이를 실현하는 방법을 찾아내 세 사람의 이름 첫 글자를 따서 RSA라고 이름 붙였습니다.

마틴 헬만(왼쪽)과 휘트필드 디피(오른쪽), 1977년
마틴 헬만(왼쪽)과 휘트필드 디피(오른쪽), 1977년

키 만들기

큰 소수 p와 q를 골라 곱합니다: n = p × q. 오일러 피 함수 φ(n) = (p − 1)(q − 1)을 계산합니다. 이는 n보다 작으면서 n과 서로소인 수의 개수입니다. φ(n)과 서로소인 공개 지수 e를 고릅니다. 보통 65537을 씁니다. 그런 다음 e × d를 φ(n)으로 나눈 나머지가 1이 되는 개인 지수 d를 구합니다. 확장 유클리드 호제법을 쓰면 빠르게 구할 수 있습니다. 공개 키는 쌍 (e, n)이고, 개인 키는 d입니다. p = 61, q = 53이면 n = 3233, φ(n) = 3120, e = 17, d = 2753이 됩니다.

암호화와 복호화

메시지는 먼저 n보다 작은 수 m으로 바뀝니다. 암호화하려면 c = mᵉ mod n, 즉 mᵉ을 n으로 나눈 나머지를 계산합니다. 복호화하려면 cᵈ mod n을 계산합니다. e × d는 φ(n)의 배수보다 1 크므로, 오일러 정리에 따라 이 계산은 m을 돌려줍니다. 위의 키로 하면 문자 A(코드 65)는 65¹⁷ mod 3233 = 2790이 되고, 2790²⁷⁵³ mod 3233 = 65로 다시 돌아옵니다. 이렇게 큰 거듭제곱은 결코 다 적지 않습니다. 반복 제곱법이 지수의 비트마다 한 번씩 제곱하고 단계마다 나머지를 취해 계산합니다.

디지털 서명

RSA는 거꾸로도 작동합니다. 메시지를 개인 지수로 거듭제곱한 s = mᵈ mod n은 키의 소유자만 만들 수 있는 서명이 됩니다. 누구나 공개 키로 이를 확인할 수 있습니다. sᵉ mod n이 m을 돌려주면, 메시지는 d를 가진 사람에게서 왔고 도중에 바뀌지 않은 것입니다. 실제로 서명하는 것은 메시지 자체가 아니라 메시지의 짧은 해시입니다. 이런 서명이 소프트웨어 업데이트, 보안 웹사이트, 전자 문서를 보호합니다.

안전한 이유

n과 e는 누구나 볼 수 있습니다. d를 찾으려면 공격자는 φ(n)이 필요하고, φ(n)을 찾으려면 p와 q가 필요하므로, RSA를 깨는 일은 결국 n을 소인수분해하는 일이 됩니다. 컴퓨터가 두 소수를 곱하는 데는 1마이크로초도 걸리지 않지만, 그 곱을 다시 두 소수로 나누는 것은 극도로 어렵다고 여겨집니다. 지금까지 소인수분해된 가장 큰 RSA 챌린지 수는 2020년의 RSA-250으로, 829비트이며 컴퓨터 시간으로 약 2700년이 걸렸습니다. 오늘날 쓰이는 키는 최소 2048비트, 약 617자리입니다.

두 번 발견된 비밀

RSA보다 4년 앞선 1973년, 영국의 수학자 클리퍼드 콕스는 정보기관 GCHQ에서 일하면서 동료 제임스 엘리스의 아이디어를 바탕으로 같은 방식을 찾아냈습니다. 이 연구는 기밀로 분류되어 1997년에야 공개되었습니다. RSA 자체는 1983년 미국에서 특허를 받았으며, 특허는 2000년 9월에 만료되었는데, 그보다 2주 전에 알고리즘이 퍼블릭 도메인으로 공개되었습니다.

론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)
론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)

실제로 쓰이는 RSA

실제 RSA는 텍스트를 직접 암호화하지 않습니다. OAEP 같은 방식으로 메시지를 무작위 바이트로 패딩해, 같은 메시지라도 매번 다르게 암호화되고 패턴이 새어 나가지 않게 합니다. RSA는 느리기 때문에 주로 AES 같은 빠른 대칭 암호의 짧은 키를 교환하거나 보호하는 데, 또는 서명에 쓰입니다. 충분히 큰 양자 컴퓨터는 1994년의 쇼어 알고리즘으로 n을 빠르게 소인수분해할 수 있으며, 그래서 새로운 양자 내성 방식이 RSA와 함께 도입되고 있습니다.

직접 탐구해 보세요

RSA 암호화 데모를 열어 직접 고른 소수나 2~8자리의 무작위 소수로 키를 만들고, 확장 유클리드 호제법이 한 행씩 d를 찾는 과정을 보고, 메시지를 한 글자씩 암호화하거나 서명하고, 원하는 글자의 반복 제곱 과정을 따라가 보세요. 그런 다음 이브가 n을 소인수분해하게 하고, 이브에게 필요한 시간이 소수의 크기에 따라 어떻게 늘어나는지 지켜보세요.

자주 묻는 질문

RSA에는 왜 소수가 필요한가요?

φ(n)은 n이 어떤 소수들로 나뉘는지 알 때만 쉽게 계산할 수 있기 때문입니다. p와 q가 소수일 때 n = p × q이면 φ(n) = (p − 1)(q − 1)입니다. 또한 소수를 쓰면 n에 작은 인수가 전혀 없으므로, 같은 크기의 수 중에서 n을 가능한 한 소인수분해하기 어렵게 만듭니다.

e는 왜 흔히 65537인가요?

65537 = 2¹⁶ + 1은 소수이고 2진수로 1이 두 개뿐이므로, 이것으로 암호화하면 제곱 16번과 곱셈 한 번이면 됩니다. 또한 3처럼 아주 작은 지수의 약점을 피할 만큼 충분히 큽니다.

RSA와 디피-헬먼은 어떻게 다른가요?

디피-헬먼은 두 사람이 공개 채널로 공유 비밀 키를 정하게 해 줄 뿐, 그 자체로는 아무것도 암호화하거나 서명하지 않습니다. RSA는 키 쌍으로 직접 암호화하고 서명합니다. 둘 다 한쪽 방향은 쉽고 반대 방향은 어려운 문제에 기반합니다. RSA는 소인수분해, 디피-헬먼은 이산 로그입니다.

데모의 키를 실제 암호화에 쓸 수 있나요?

아니요. 소수가 최대 12자리 정도라서 이 데모가 만드는 키는 모두 몇 초 이내에 소인수분해할 수 있고, 각 글자를 패딩 없이 하나씩 따로 암호화합니다. RSA의 원리를 보기 위한 것이지 무언가를 보호하기 위한 것이 아닙니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

RSA 암호화 데모 열기