RSA 암호화 알고리즘 작은 숫자로 쉽게 이해하기

 

두 소수 p, q가 있다. p와 q의 곱 N을 구하는 것은 매우 쉽다. 하지만 N이라는 값이 주어졌을 때, 소수인 p와 q를 구하는 것은 매우 어렵다. 이를 Trapdoor라고 부른다.

 

Bob이 Alice에게 자신의 나이(42)를 보내는 시나리오를 생각해보자.

 

Public key 생성

먼저 Alice가 Public Key를 생성해야 한다.

p=17, q=29로 두 소수를 정했다.

두 수의 곱 N을 계산한다. p x q = N = 493

 

또 다른 수 e를 생성한다.

(p-1) x (q-1) = 448

448이 e는 아니다. e는 448의 인수와 관련이 없다면 어떤 값이라도 될 수 있다.

448을 소인수분해하면 448 = 2 x 2 x 2 x 2 x 2 x 2 x 7이다.

즉, e를 소인수분해를 했을 때, 2와 7을 인수로 갖고 있지 않으면 된다.

e를 5로 설정하자.

 

Public Key가 (N, e) = (493, 5)로 완성된다.

 

Encryption

Public Key: (N, e) = (493, 5)

 

Bob의 나이는 42다. 먼저 42의 e(5)제곱을 구한다. 42 x 42 x 42 x 42 x 42 = 130,691,232

130,691,232 을 N(493)으로 나누어 나머지 383을 얻는다.

 

42를 383으로 Encryption했다.

 

Decryption

Alice는 Bob에게 383이라는 암호문을 받았다. 이제 Decryption을 해야한다.

 

Public key를 생성할 때 만들었던 숫자 (p-1) x (q-1) = 448과 e(5)를 사용할 것이다.

5의 배수 중에서 448의 배수의 값보다 1이 더 큰 값을 찾을 것이다.

수식으로 설명하면 5i = 448j + 1을 만족하는 i를 찾을 것이다. (i, j는 자연수)

 

5의 배수

5, 10, 15, 20, 25, 30, 35, 40 …

 

448의 배수

448, 896, 1344, 1792, 2240, 2688 …

 

5 x 269 = 1345이고, 이는 448 x 3보다 1 많은 값이다. Alice가 필요한 값 d는 269이다.

 

Alice가 전달받은 암호문 383의 d(269)제곱을 한 뒤, N(493)으로 나누면 42라는 값을 얻게 된다.

 

 

출처

https://theconversation.com/the-rsa-algorithm-or-how-to-send-private-love-letters-13191

The RSA algorithm (or how to send private love letters)