RSA는 공개키 기반의 암호 시스템으로, 인터넷처럼 보안이 취약한 네트워크를 통해 민감한 정보를 안전하게 전송해야 할 때 가장 널리 사용되는 암호화 기술입니다.
RSA 알고리즘이란?
RSA는 대표적인 비대칭키(공개키) 암호 알고리즘입니다. 이 알고리즘은 '두 개의 큰 소수를 찾아 곱하는 것은 매우 쉬지만, 그 곱을 다시 원래의 소수들로 분해(소인수분해)하는 것은 극도로 어렵다'는 수학적 특성에 기반합니다. 바로 이 비대칭성이 RSA 보안성의 핵심입니다.
RSA는 공개키(Public Key)와 개인키(Private Key), 두 개의 키를 함께 사용합니다. 공개키로 암호화한 데이터는 오직 해당 개인키로만 복호화할 수 있기 때문에, 안전하지 않은 경로로도 키를 교환할 수 있다는 장점이 있습니다.
RSA 알고리즘 계산 예제
아래 예제를 통해 RSA 알고리즘의 전체 동작 과정을 단계별로 살펴보겠습니다.
두 개의 큰 소수 P와 Q를 선택합니다.
예제에서는 P = 7, Q = 17로 설정합니다.N을 계산합니다.
N = P × Q = 7 × 17 = 119공개키(암호화 키) E를 선택합니다.
E는 (P − 1) × (Q − 1)과 서로소(공통 약수가 없는 수)가 되어야 합니다.
(P − 1) × (Q − 1) = (7 − 1) × (17 − 1) = 6 × 16 = 96
96의 소인수는 2와 3입니다(96 = 2 × 2 × 2 × 2 × 2 × 3). 따라서 E는 2나 3으로 나누어떨어지지 않는 수여야 합니다. 예를 들어 4(2의 배수), 15(3의 배수), 6(2와 3 모두의 배수)은 선택할 수 없습니다.
여기서는 조건을 만족하는 E = 5를 선택합니다.개인키(복호화 키) D를 선택합니다.
D는 다음 식을 만족해야 합니다.
(D × E) mod [(P − 1) × (Q − 1)] = 1
E, P, Q의 값을 대입하면:
(D × 5) mod (6 × 16) = 1, 즉 (D × 5) mod 96 = 1
D = 77을 대입하면 (77 × 5) mod 96 = 385 mod 96 = 1이 되어 조건을 만족합니다. 따라서 D = 77입니다.암호화: 평문(PT)으로부터 암호문(CT)을 계산합니다.
CT = PTE mod N
평문이 10이라고 가정하면:
CT = 105 mod 119 = 100000 mod 119 = 40암호문 전송: 계산된 암호문 CT = 40을 수신자에게 전송합니다.
복호화: 암호문(CT)으로부터 원래의 평문(PT)을 복원합니다.
PT = CTD mod N
값을 대입하면:
PT = 4077 mod 119 = 10
결과적으로 5단계에서 암호화했던 원래 평문 10이 정확히 복원됩니다.
정리
이 예제에서 공개키는 (E, N) = (5, 119), 개인키는 (D, N) = (77, 119)입니다. 실제 환경에서는 훨씬 큰 소수를 사용하기 때문에 N을 소인수분해하여 개인키를 유추하는 것이 사실상 불가능하며, 이것이 RSA가 오랫동안 신뢰받아 온 이유입니다.