RSA 암호화: 4 단계

우리는 이제 파이를 푸는 트랩도어 하나가 생겼습니다 N에 대한 인수분해를 안다면 파이 N을 찾는 건 쉽습니다 예를들어 77의 소인수분해는 7*11이니까 파이 77은 6의 10배, 60입니다 3번째는 파이 함수와 지수 모듈 연산을 연결하는 방법입니다 이것을 위해선 파이와 모듈의 관계를 정리하는 오일러의 정리로 넘어갑니다 m의 파이 n제곱은 1 mod n과 합동입니다 이것은 공약수를 공유하지 않으면 아무 두 숫자나 고를 수 있다는 것을 의미하는데 m과 n이라 하고 m은 5, n은 8이라 해 봅시다 m을 파이 n 즉 4로 제곱하고 n으로 나누면 항상 1이 남을 것입니다 자, 이제 두 가지 간단한 규칙을 가지고 이 방정식을 수정해 봅시다 첫째, 1의 k제곱은 항상 1입니다 따라서 아무 숫자 k를 파이n이라는 지수에 곱할 수 있고 그래도 답은 1입니다 두 번째, 1에 아무 수 m을 곱하면 답은 항상 m입니다 이같은 방법으로 오른쪽에 m을 얻기 위해 왼쪽에 m을 곱할 수 있습니다 이는 m의 k 곱하기 파이 n 더하기 1의 거듭제곱으로 단순화시킬 수 있습니다 발전이 있군요 이제 파이 n에 종속되는 e 곱하기 d의 방정식을 찾는 일만 남았습니다 그러므로 오직 n의 인수분해를 알기만 한다면 d를 계산하는 건 쉽습니다 d가 앨리스의 열쇠가 될 것입니다 e의 효과를 취소하는 트랩도어가 될 것입니다 이 모두를 확인할 수 있는 간단한 예를 들어 봅시다 밥이 암호를 사용해서 메세지를 숫자로 변환했다고 해 봅시다 이것을 "m"이라고 부릅시다 그리고 앨리스는 공개 키와 개인 키를 다음과 같이 만듭니다 처음에 앨리스는 비슷한 크기의 무작위의 두 소수를 쓰고 곱해서 n 3,127을 얻습니다 그 후 n의 인수분해를 알기 때문에 값이 3016인 n 의 파이를 쉽게 계산 할 수 있습니다 다음으로 파이 n과 인수를 공유하지 않고 홀수라는 조건을 가지는 숫자인 작은 공개 지수 e를 뽑습니다 여기선 e=3을 뽑았습니다 마침내 n의 파이 곱하기 2 더하기 1의 나누기 3인 비공개 지수 d의 값 2,011을 구했습니다 이제 n과 e의 값을 제외한 모든 것을 숨겼습니다 n과 e가 공공 키가 되기 때문이죠 열린 자물쇠와 같다고 생각합시다 앨리스는 밥이 메시지를 잠글수 있게 이 자물쇠를 보냅니다 밥이 m의 e제곱 mod n을 계산하여 메세지를 잠급니다 c를 앨리스에게 되돌려보낼 암호화된 메세지라고 부릅시다 마침내 앨리스는 트랩도어를 통해 접근할 수 있는 개인 암호 d를 이용해 밥의 메세지를 해독했습니다 c의 d제곱 mod n이 밥의 원래 메세지였던 m과 같아집니다 c, n, e를 가지고있는 이브나 다른 누군가는 지수 d만 찾을 수 있고 그들이 파이 n을 계산할 수 있으려면 n의 소인수분해를 아는 것이 요구됩니다 n이 충분히 크면 앨리스는 이를 푸는데 가장 강력한 컴퓨터 네트워크로도 수 백년이 걸린다는 것을 확신할 수 있습니다 이 방법은 발표되자마자 기밀로 분류되었지만 1977년 론 리베스트, 에디 셰미어와 랜 애이들먼에 의해서 독립적으로 재발견 되었고 그것이 RSA 암호화라고 불리는 이유입니다 RSA는 세계에서 가장 넓게 사용되는 공공 키 알고리즘이고 역사상 가장 많이 복사된 소프트웨어입니다 세계의 모든 인터넷 사용자가 알게 모르게 RSA나 그 변형된 형태를 사용합니다 이것의 능력은 소인수분해의 난이도에 의존해 있고 그것이 소수의 분배에 대한 큰 의문점을 남깁니다 문제는 몇 천년 동안이나 풀리지 않은 채로 남아있습니다