키
d를 구하는 방법: 확장 유클리드 호제법
각 행은 바로 위 두 행의 나눗셈으로 얻습니다. 나머지가 1인 행에서 마지막 열이 d입니다(음수이면 φ(n)을 더합니다).
| 몫 | 나머지 | e의 계수 |
|---|
메시지
네트워크로 전송
| 비트 | 제곱 | m 곱하기 |
|---|
키 깨뜨리기
RSA 암호화 데모
RSA를 사용하면 누구나 여러분의 공개 키로 메시지를 잠글 수 있지만, 그것을 열 수 있는 사람은 개인 키를 가진 여러분뿐입니다. 그 뒤에 있는 것은 학교에서 배우는 몇 줄의 산수입니다. 소수 두 개, 곱셈 한 번, 나머지, 그리고 영리한 역원입니다. 직접 고른 소수로 키 쌍을 만들고, 메시지를 한 글자씩 암호화하고 복호화하고, 여러분이 보냈다는 것을 누구나 확인할 수 있도록 서명한 다음, 공격자가 되어 n을 소인수분해해 보면서 실제 키에 왜 수백 자리가 필요한지 알아보세요. 소수 p와 q를 고르거나 ‘새 소수’를 누르세요. 앱이 공개 키 (e, n)과 개인 키 d를 만들고, 확장 유클리드 호제법이 d를 찾는 과정을 보여 줍니다. 메시지를 입력하면 각 글자가 공개 키로 암호화되고 개인 키로 복호화됩니다. 행을 클릭하면 반복 제곱법으로 계산한 거듭제곱을 볼 수 있습니다. ‘서명’으로 바꾸면 대신 개인 키로 서명하고, ‘n 소인수분해’를 누르면 작은 키가 얼마나 빨리 깨지는지 볼 수 있습니다.
작동 원리
- 소수 p와 q를 입력하거나, 크기를 고르고 ‘새 소수’를 누르세요. 앱이 n, φ(n), e, d를 계산하고 d를 구하는 과정을 보여 줍니다.
- 메시지를 입력하고 ‘암호화’나 ‘서명’을 고르세요. 각 글자는 숫자로 바뀐 뒤 mod n으로 거듭제곱됩니다. 행을 클릭하면 반복 제곱 과정을 볼 수 있습니다.
- ‘n 소인수분해’를 눌러 이브가 n을 두 소수로 나누고 개인 키를 알아내게 하세요.
키의 원리
두 소수를 곱합니다: n = p × q. p = 61, q = 53이면 n = 3233입니다. φ(n) = (p − 1)(q − 1) = 3120은 n보다 작으면서 n과 서로소인 수의 개수이며, p와 q를 아는 사람만 계산할 수 있습니다. 3120과 서로소인 e = 17을 고르고, e × d가 φ(n)의 배수보다 1 크게 되는 d를 구합니다. 여기서는 d = 2753입니다. 17 × 2753 = 46801 = 15 × 3120 + 1이기 때문입니다. (e, n)을 공개하고 d는 간직합니다. 메시지 m은 c = mᵉ mod n이 되고, 오일러 정리에 따라 cᵈ mod n을 계산하면 m이 다시 나옵니다.
깨뜨리기 어려운 이유
공격자에게 필요한 모든 것은 n의 인수 속에 숨어 있습니다. n = 3233이라면 전혀 보호가 되지 않습니다. 홀수 약수를 차례로 시도하면 스무 번 남짓 만에 53을 찾습니다. 하지만 필요한 노력은 n의 제곱근에 따라 늘어납니다. 2048비트 모듈러스는 약 617자리이며, 알려진 어떤 방법으로도, 오늘날 존재하는 어떤 컴퓨터로도 쓸모 있는 시간 안에 소인수분해할 수 없습니다. 서명은 RSA를 거꾸로 실행합니다. s = mᵈ mod n은 개인 키로만 만들 수 있고, sᵉ mod n이 m을 돌려주는지는 누구나 확인할 수 있습니다.
자주 묻는 질문
왜 아무도 공개 키에서 d를 계산할 수 없나요?
d를 찾으려면 φ(n) = (p − 1)(q − 1)이 필요하고, φ(n)을 얻으려면 p와 q가 필요합니다. n에서 이들을 알아내는 것은 n을 소인수분해하는 것을 뜻하며, 수백 자리 수에 대해서는 빠른 방법이 알려져 있지 않습니다. 이 데모에서는 장난감 키를 순식간에 소인수분해할 수 있는데, 바로 그 점이 실제 키가 그렇게 큰 이유를 보여 줍니다.
왜 메시지를 한 글자씩 암호화하나요?
장난감 키가 작기 때문입니다. RSA는 n보다 작은 수만 암호화할 수 있습니다. n = 3233이면 모든 문자 코드가 들어가지만, 문장 전체는 들어가지 않습니다. 실제 RSA는 2048비트 이상의 모듈러스를 사용하고, 같은 메시지가 두 번 다시 같은 방식으로 암호화되지 않도록 메시지를 무작위 바이트로 패딩하며, 실제로는 AES 같은 더 빠른 암호에 쓸 짧은 키만 암호화합니다.
반복 제곱법은 무엇을 하나요?
거대한 수를 한 번도 적지 않고 m²⁷⁵³ mod n 같은 거대한 거듭제곱을 계산합니다. 지수를 2진수로 쓴 다음 비트를 차례로 살펴봅니다. 비트마다 지금까지의 결과를 제곱하고, 1인 비트에서는 m을 곱하며, 매번 mod n의 나머지를 취합니다. 2048비트 지수라도 제곱은 약 2048번이면 됩니다.
암호화와 서명은 어떻게 다른가요?
암호화는 받는 사람의 공개 키를 사용하므로, 받는 사람의 개인 키로만 되돌릴 수 있습니다. 서명은 보내는 사람의 개인 키를 사용하므로, 누구나 보내는 사람의 공개 키로 확인해 메시지가 그 키의 소유자에게서 왔고 바뀌지 않았음을 알 수 있습니다.
제 메시지가 어딘가로 전송되나요?
아니요. 모든 것은 브라우저에서 계산되며, 소수와 메시지는 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동