[암호학]비대칭키 암호와 RSA 과정 설명

 

 

비대칭키 암호(Asymmetric Key Cryptography)

대칭키 암호가 양쪽 통신 당사자가 같은 키를 공유하는 암호화 방식이라면 비대칭 키는 대충 느낌이 오시지 않나요? 비대칭 키 암호는 양쪽이 다른 키를 가지고 있습니다.

 

비대칭키에서 타인 모두에게 공개하는 키를 공개키(public key), 그리고 자기 자신만이 갖고 있는 키가 개인키(private key)라고 합니다. 따라서 공개키는 누구나 다 알 수 있고 누구나 다 암호화할 수 있지만 푸는 사람은 그에 맞는 개인키를 가지고 있는 사용자가 됩니다.

 

기본 아이디어

아이디어는 다음의 그림과 같습니다.

은밀한 데이터를 보내는 A는 B의 공개키로 데이터를 암호화한 후 B에게 보냅니다. B는 이 데이터를 풀어야하는데 개인키를 통해서 암호화된 데이터를 풀게 되지요. 

 

여기서 비대칭키 암호의 특징 몇가지가 있습니다.

1) public key는 모두에게 공개해야하는데 이 public key를 가지고 private key를 구해내기가 상당히 어려워야합니다. 

2) public key와 private key는 짝이 맞아야합니다. 그래야지 암복호화를 정상적으로 할 수 있게되죠.

3) 대칭키는 통신 주체들이 각각 키를 갖고 있어야하므로 당사자가 n명이 있다고 할때 필요한 키의 개수는 n(n-1)/2개가 됩니다. 하지만 비대칭키 암호는 2개만 있으면 됩니다. 바로 공개키와 개인키가 그것이 되겠죠.

4) 비대칭키의 암호화 과정과 복호화 과정은 상당히 느립니다. 그렇기 때문에 보통의 데이터를 암호화할 수 없죠. 아주 중요한 데이터를 암호화할때 쓰이는데 바로 대칭키의 키 교환할때 쓰입니다.

 

RSA(Rivest, Shamir, Adleman)

비대칭키 암호의 가장 대표적인 알고리즘은 바로 RSA 알고리즘입니다. RSA는 고안자들의 앞 약자입니다. 그 중에서도 Rivest형이 가장 실세인가 보네요.

 

RSA는 소인수 분해의 어려움을 기반으로 하는 알고리즘인데 수학을 좀 많이 알아야만 제대로 이해할 수 있습니다. 저와 같은 일반인 수준에서는 아~~ 그렇게 되는가보다 하고 끝내는게 정신건강에 좋습니다. 여기서는 그냥 아~ 그렇게 되는가 보다 하고 맘편히 읽어주세요.

 

- 오일러 토션 함수(Euler's totiont function)

RSA를 이해하기 전에 우리는 오일러 토션 함수에 대해서 알아야합니다. 저도 모르니 그냥 필요한 식만 적도록 하겠습니다. 함수의 기호를 찾을 수 없으므로(능력 부족..) t라고 표시하도록 하겠습니다.

오일러 토션 함수는 n보다 작은 수 중 n과 서로소인 수의 갯수를 구하는 함수입니다. 서로소라함은 두 수의 공약수가 1외에는 없는 수를 말합니다. 

 

오일러 토션 함수 공식

1. t(1)=0 2. t(p)=p-1, p는 소수 3. t(m*n)=t(m)*t(n) 4. t(p^e)= p^e - p^(e-1) (^는 제곱을 의미합니다. p^e= p의 e제곱)

 

예제)

1. 15보다 작은 수 중에 15와 서로소는 몇개일까요? 

1, 2, 4, 7, 8, 11, 13, 14 로 8개입니다. 우리가 위의 공식을 적용하여 구한다면 아래와 같습니다.

t(15) = t(3*5) = t(3) * t(5) = 2*4 = 8

 

2. t(14)는 얼마일까요? 

t(14) = t(7*2) = t(7) * t(2) = 6*1 =6 , 실제로 1, 3, 5, 9, 11, 13이 있습니다.

 

 

 

 

RSA 암복호화 과정

RSA는 두 소수 p와 q를 선택하여 곱한 n을 구합니다. 이 수는 소수이기 때문에 오일러 토션 함수를 이용해서 t(n) = t(p)*t(q) = (p-1)*(q-1) 이 성립이 됩니다. 이제 이 안에서 두개의 지수 e와 d를 고르는데요. 이 e와 d는 t(n)과 서로소이며 mod t(n) 연산에서 서로 역원 관계입니다. t(n)과 서로소라면 e와 d는 t(n)보다 작은 수 중 소수를 선택하면 무조건 t(n)과 서로소가 되지요.

만약 소수 t(n)보다 작은 e를 선택했다면 (e*d)mod t(n)=1를 만족하는 d를 구하면 됩니다. e는 d의 역원이라하여 e=(d^-1)mod t(n)으로 표현하기도 합니다. 

 

아래에서는 실제 어떻게 RSA를 통해 암복호화가 되는지 살펴보도록 합니다. 최대한 구별가능하게 컬러로 하고 e와 d를 쉽게 구하는 공식도 소개합니다.

 

1) p와 q를 소수 7과 11로 선택합니다.

2) 그리고 n을 구하죠. n=7*11이므로 77이 됩니다. t(77) = t(7) * t(11) = 60이 됩니다.

3) 이제 e와 d를 선택하는데 만약 e를 13으로 선택하면 d는 37입니다. (e*d)mod60=(13*37)mod60=1이기 때문에 서로 역원이죠. e는 t(77) = 60보다 작은 수 중 60과 서로소입니다. 13은 소수이기 때문에요.

 

* 여기서 한가지 공식이 있는데, e를 13을 골랐다면 e의 역원은 다음과 같습니다.

(13^(t(77)-1)) mod t(77) = 13^(59) mod 60 = 37

 

번외)

자, 그렇다면 e를 다른 수를 골라보도록 하지요. e를 23을 고른다면 d는 아래와 같이 구해지겠네요.

d = 23^(t(77)-1) mod t(77) = 23^(60-1) mod 60 = 23^59 mod 60 = 47

암호화 이제 평문 5를 RSA로 암호화 한다면  (5^13)mod 77 = 26이 되어 암호문이 됩니다.

복호화 다시 복호화하게 되면 (26^37)mod 77 = 5가 되므로 복호화가 됩니다.

여기서 d는 나의 private key로 쓰이고, e는 n과 함께 공개되며 공개키로 쓰입니다.

 

여기서 e와 n을 가지고 d를 구하는것이 아주 상당히 어렵습니다. 수식은 있긴한데 쓰지 않는게 멘탈에 좋을 것 같습니다.