RSA는 공개 키 암호화를 위한 암호 시스템이며 특히 인터넷을 포함한 안전하지 않은 네트워크를 통해 전송되는 경우 민감한 정보를 보호하는 데 널리 사용됩니다.
RSA 알고리즘은 가장 널리 사용되는 비대칭 키 암호화 알고리즘으로, 단순히 큰 소수를 발견하고 곱하는 것이지만 곱을 인수분해하기는 복잡하다는 수학적 사실에 의존합니다. 개인 키와 공개 키가 모두 필요합니다.
RSA 알고리즘의 예
개념을 배우기 위해 이 절차의 예를 들어 보겠습니다. 읽기 쉽도록 알고리즘 단계와 함께 예제 값을 작성할 수 있습니다.
-
두 개의 큰 소수 P와 Q 선택
P =47, Q =17
-
계산 N =P x Q
N =7 x 17 =119입니다.
-
(P -1) x (Q - 1)
의 요소가 아닌 공개 키(즉, 암호화 키) E를 선택합니다.-
(7 - 1) x (17 -1) =6 x 16 =96을 구해 봅시다.
-
96의 인수는 2, 2, 2, 2, 2, 3입니다(96 =2 x 2 x 2 x 2 x 2 x 3이기 때문에).
-
따라서 E의 인수가 2와 3이 되지 않도록 E를 선택할 수 있습니다. E를 4(2를 인수로 하기 때문에), 15(3을 인수로 하기 때문에), 6(그것 때문에 요인으로 2와 3이 있습니다.
-
E를 5로 선택하겠습니다(2와 3의 인수가 아닌 다른 숫자일 수 있음).
-
-
다음 방정식을 포함하여 개인 키(즉, 복호화 키) D를 선택합니다.
(D x E) 모드 (P – 1) x (Q – 1) =1
-
방정식에서 E, P, Q의 값을 대입합시다.
-
(D x 5) mod (7 – 1) x (17 – 1) =1입니다.
-
즉, (D x 5) mod (6) x (16) =1입니다.
-
즉, (D x 5) mod (96) =1
-
몇 가지 계산을 한 후 D =77로 가정합니다. 그러면 다음이 참입니다. (77 x 5) mod (96) =385 mod 96 =1, 이것이 우리가 원하는 것입니다.
-
-
암호화의 경우 다음과 같이 일반 텍스트(PT)에서 암호 텍스트(CT)를 계산합니다.
CT =PT E 모드 N
일반 텍스트 10을 암호화한다고 가정해 보겠습니다. 그러면
CT =10 5 모드 119 =100000 모드 119 =40.
-
CT를 암호문으로 수신자에게 보냅니다.
수신자에게 암호문으로 40을 보냅니다.
-
복호화를 위해 다음과 같이 암호문(CT)에서 평문(PT)을 계산합니다.
PT =CT D 모드 N
다음을 수행합니다.
PT =CT D 모드 N
즉,
PT =40 77 mod 119 =10, 이것은 5단계의 원래 평문이었습니다.