RSA 암호화 수학적 원리 이해하기

- 목차

 

 

함께 보면 좋은 글.

https://westlife0615.tistory.com/411

CA (Certificate Authority) 알아보기

 

* 소개

RSA 는 Rivest-Shamir-Adleman 의 약자입니다.
암호화 방식의 하나로 Rivest, Shamir, Adleman 세 사람에 의해서 개발된 암호화 방식이라
세 사람의 이름의 첫 글자를 따서 RSA 라고 불립니다.
RSA 는 비대칭 암호화 알고리즘으로 소수 (Prime Number) 를 활용한 암호화 알고리즘입니다.
Prime Number, Modular Multiplicative Inverse, Euler's Totient Function 등
어려운 수학적 용어들이 많아서 해당 내용들에 대한 상세한 설명과 예시를 많이 추가하였습니다.
그래서 내용이 길어졌는데, 끝까지 읽어주셨으면 좋겠습니다.

* RSA 수학적 원리

먼저, RSA 의 public key 와 private key 를 생성하는 과정을 대략적으로 기술해보겠습니다.
 

* Euler's Totient Function

먼저 Public Key 와 Private Key 를 구하기 위해선 Euler's Totient Function 에 대한 지식이 필요합니다.
Euler's Totient Function 의 기호는 아래와 같습니다.
 

φ(n) or phi(n)

 
"파이" 로 표현되며, Euler's Totient Function 의 쓰임새는 특정 수가 소수인지 아닌지 판별하는 용도가 있습니다.
구체적인 정의는 어떤 숫자 n 이 주어졌을 때, 1 <= k <= n 인 k 중에
n 과 k 의 최대공약수가 1인 k의 갯수입니다.
 
말이 어렵기 때문에 예시를 들어보겠습니다.
 
n 이 5일때, φ(5)
 

φ(5)

k == 1 일 때, 5와 1의 최대공약수는 1
k == 2 일 때, 5와 2의 최대공약수는 1
k == 3 일 때, 5와 3의 최대공약수는 1
k == 4 일 때, 5와 4의 최대공약수는 1
k == 5 일 때, 5와 5의 최대공약수는 5

즉 최대공약수가 1이 되는 k 는 1,2,3,4 이므로 
φ(5) = 4

 
n 이 7일때, φ(7)
 

φ(7)

k == 1 일 때, 7와 1의 최대공약수는 1
k == 2 일 때, 7와 2의 최대공약수는 1
k == 3 일 때, 7와 3의 최대공약수는 1
k == 4 일 때, 7와 4의 최대공약수는 1
k == 5 일 때, 7와 5의 최대공약수는 1
k == 6 일 때, 7와 6의 최대공약수는 1
k == 7 일 때, 7와 7의 최대공약수는 7

즉 최대공약수가 1이 되는 k 는 1,2,3,4,5,6 이므로 
φ(7) = 6

 
즉, 어떤 소수 n의 Euler's Totient Function 은 n - 1 이 됩니다.
 

n 이 소수일 때, 
φ(n) or phi(n) = n - 1

 
만약 n 이 소수가 아닌 경우에는 소인수분해 (Prime Number Factorization) 이 필요합니다.
 
n 이 6일때, φ(6) 의 예를 들어보겠습니다.
먼저 6 는 2, 3 를 소수로 가지는 수입니다.
 

φ(12)

k == 1 일 때, 6와 1의 최대공약수는 1
k == 2 일 때, 6와 2의 최대공약수는 2
k == 3 일 때, 6와 3의 최대공약수는 3
k == 4 일 때, 6와 4의 최대공약수는 2
k == 5 일 때, 6와 5의 최대공약수는 1
k == 6 일 때, 6와 6의 최대공약수는 6

즉 최대공약수가 1이 되는 k 는 1,5 이므로 
φ(6) = 2

 
n 이 14일때, φ(14) 의 예를 들어보겠습니다.
먼저 14 는 2, 7 를 소수로 가지는 수입니다.

φ(14)

k == 1 일 때, 14와 1의 최대공약수는 1
k == 2 일 때, 14와 2의 최대공약수는 2
k == 3 일 때, 14와 3의 최대공약수는 1
k == 4 일 때, 14와 4의 최대공약수는 2
k == 5 일 때, 14와 5의 최대공약수는 1
k == 6 일 때, 14와 6의 최대공약수는 2
k == 7 일 때, 14와 7의 최대공약수는 7
k == 8 일 때, 14와 8의 최대공약수는 2
k == 9 일 때, 14와 9의 최대공약수는 1
k == 10 일 때, 14와 10의 최대공약수는 2
k == 11 일 때, 14와 11의 최대공약수는 1
k == 12 일 때, 14와 12의 최대공약수는 2
k == 13 일 때, 14와 13의 최대공약수는 1
k == 14 일 때, 14와 14의 최대공약수는 14

즉 최대공약수가 1이 되는 k 는 1,3,5,9,11,13 이므로 
φ(14) = 6

 
두개의 소수가 합쳐진 숫자의 경우에는 Euler's Totient Function 의 패턴이 있습니다.
φ(n) = (p - 1) * (q - 1) 로 표현됩니다.

n 은 2개의 소수 p 와 q 의 곱인 경우.
n = p * q
φ(n) = (p - 1) * (q - 1)

 
Euler's Totient Function 은 RSA 의 Public Key 와 Private Key 를 생성하는데에 사용되는 수학적 개념이라
시간을 내어 긴 설명을 해보았습니다.

 

 

* Public & Private Key 생성 과정

 

1) (Two Prime Numbers) 두개의 큰 소수를 만듭니다. *

각각의 소수은 랜덤하게 결정하셔도 됩니다.
다만 수의 크기가 클수록 좋습니다.
 

n = p * q

 
권장하는 방식으로는 두개의 소수 p, q 의 곱이
2048 bits, 3072 bits, 4096 bits 로 표현될 수 있도록 p 와 q 를 큰 소수로 설정하는 것이 좋다고합니다.
 
 

2) (Modulus) 두 소수를 곱한 값을 구합니다. *

RSA 에서 두 소수의 곱은 modulus ( 또는 n ) 라고 부릅니다.
각각의 소수를 p 와 q 라고 한다면, modulus 는 아래와 같습니다.

n = p * q

 

3) Public Exponent 를 구합니다. *

Public Exponent 는 public key 를 생성하는 마지막 단계입니다.
Public Exponent 는 대개 3 또는 65537 (2^16 + 1) 의 값을 취합니다.
 
Public Exponent 를 구하는 수학적인 조건에는 modulus n 의 φ(n) 의 prime number 인 값을 구해야합니다.
말이 어렵죠 ? 그래서 일반적으로 3 또는 65537 (2^16 + 1) 를 사용한다고 하네요.

 
위 설명을 좀 더 구체적으로 풀어보면,
 
예를 들어 두 소수 127 과 131 이 존재하는 경우,
p = 127
q = 131
n = p * q = 16637
φ(n) = φ(16637) = (127 - 1) * (131 - 1) = 16380
Public Exponent 의 후보 값들은
아래와 같습니다.
 

[2,3,4,5,6,7,9,10,12,13,14,15,18,20,21,26,28,30,35,36,39,42,45,52,60,63,65,70,78,84,90,91,105,117,126,130,140,156,180,182,195,210,234,252,260,273,315,364,390,420,455,468,546,585,630,780,819,910,1092,1170,1260,1365,1638,1820,2340,2730,3276,4095,5460,8190,16380]

 
 

4) Private Exponent 를 구합니다.*

Private Exponent 는 Private Key 를 구성하는 구성요소입니다.

Private Exponent 를 생성하는 공식은 아래와 같습니다.
 
Private Exponent 의 값은 Modular Multiplicative Inverse 의 결과입니다.
 
수학적 표현으로는 아래와 같이 설명되는데요.

d ≡ e^(-1) (mod φ(n))

말이 어렵기 때문에 바로 예시로 들어가겠습니다.
 
p = 127
q = 131
n = p * q = 16637
φ(n) = φ(16637) = (127 - 1) * (131 - 1) = 16380
e = 65537
 
Private Exponent 는 보통 d 로 표현합니다.
d 는 e 과 φ(n) 의 Modular Multiplicative Inverse 입니다.

구하는 과정은 아래와 같습니다.
 
e 와 어떤 수 x 를 곱한 값을 φ(n) 와 나누었을 때, 나머지가 1인 어떤 수 x 가 바로 Private Exponent 입니다.

 

(65537 * 1) % 16380 => 17
(65537 * 2) % 16380 => 34
(65537 * 3) % 16380 => 51
(65537 * 4) % 16380 => 68
(65537 * 5) % 16380 => 85

...

(65537 * 14453) % 16380 => 1

 
그래서 d 의 값은 14453 이 됩니다.
위 과정을 계산하는 함수는 아래와 같습니다.
 

function modularMultiplicativeInverse(publicExpoment, phiN) {
    var x = 0;
    var remainder = 0;
    while (remainder != 1) {
        var remainder = (publicExpoment * x) % phiN;
        x++;
    }
    
    return x
}

이제 RSA 를 하기 위한 모든 구성요소들에 설명을 마쳤습니다.

Encryption 에 대한 설명을 이어가겠습니다.
 
 

* How To Encrypt

암호화되기 전의 상태를 Plaintext 라고 하고, 암호화된 상태는 Cyphertext 라고 합니다.
Plaintext <-> Cyphertext 의 과정을 설명해보겠습니다.
 
<Plaintext>

12345

 
12345 데이터를 가진 Plaintext 파일 하나가 있다고 가정하겠습니다.
이때, public key 를 생성하겠습니다.
 
두 개의 소수는  p = 127, q = 131 로 가정하겠습니다.

그리고
n = p * q = 16637

φ(n) = φ(16637) = (127 - 1) * (131 - 1) = 16380
e = 65537
d = 14453
입니다.
 

* 암호화 과정

12345 를 RSA 방식으로 암호화해야하므로
1, 2, 3, 4, 5 각각을 암호화합니다.
암호화 방식은 아래와 같습니다.
 
<암호화 공식>

C = M^e (mod n)

 
<복호화 공식>

 M = C^d (mod n)

 

1. 암호화하기 *

n 는 16637 입니다. 
e 는 65537 입니다. 

(12345 ^ 65537) % 16637 = 16354

 
12345 는 16354 로 암호화되었습니다.
 

2. 복호화하기 *

 

n 는 16637 입니다. 
d 는 14453 입니다. 

(16354 ^ 14453) % 16637 = 12345

 
12345 로 복호화되었습니다.
 
 

* Asymmetric Encription

RSA 는 비대칭 암호화 알고리즘 중의 한가지 방식입니다.
비대칭 암호화는 Public Key Encription 이라고도 불립니다.
Public Key 와 Private Key 2개의 키를 암-복호화에 사용하며, 2개의 키를 사용한다는 관점에서 비대칭이라고 일컬어집니다.
 

* Public Key

Public Key 는 공유키로써 데이터를 암호화하는데에 사용됩니다.
 

* Private Key

Private Key 는 비밀키로써 데이터를 복호화하는데에 사용됩니다.