7. 공개키 암호 : RSA

 

저번 시간에는 Diffie-Hellman 알고리즘에 대하여 공부하였다.

이번 시간에는 공개키 암호 중 RSA에 대하여 공부할 것이다.

 

---

1. RSA 

RSA 암호 알고리즘에서는 모든 사용자에게 공개되는 공개키로 평문을 암호화하고, 타인에게 노출되어서는 안되는 개인키로 암호문을 복호화한다. 

RSA 암호 알고리즘의 안정성은 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는 인수분해 문제의 어려움에서 나온다. 따라서 암호화할 때는 합성수의 소인수분해가 어려워지도록 각 인자를 적절히 설정해야한다.

1) 오일러 정리

오일러 정리는 n과 서로소인 양의 정수 m이 다음 식을 만족한다는 정리이다.

mφ(n) ≡ 1 (mod n)

φ(n) : 오일러 파이 함수이다. 오일러 파이함수는 n 이하의 양의 정수 중에서 n과 서로소인 수의 개수를 의미한다. 예를 들어 φ(6)은 6과 서로소인 수는 1,5이므로 φ(6) = 2이다. 소수 p의 경우 1부터 p-1까지 모두 p와 서로소이기 때문에 φ(p) = p-1이다.

2) 키 생성

공개키 암호 알고리즘에서는 공개키와 개인키를 생성하는 키 생성 과정이 필요하다. RSA는 인수분해를 어렵게 만들기 위해 복잡한 연산을 거쳐 키를 생성한다. n은 modulus, e는 공개지수, d는 비밀 지수이다. 

1. 서로 다른 두 소수 p와 q를 선택한다.
   => 일반적으로 1024비트 이상에서 비트 길이가 같은 수로 선택한다.
   
   
2. n을 구한다.
   => n = p × q
   
   
3. φ(n)을 구한다.
   => p와 q가 소수이기 때문에, φ(n)은 n보다 작은면서 p와 q의 배수가 아닌 수들의 개수이다.
   => φ(n) = p × q - p - q + 1
   => φ(n) = (p - 1)(q - 1)
   
   
4. 공개 지수 e를 선택한다.
   => φ(n)보다 작은 수 중 φ(n)과 서로소인 e를 선택한다.
   
   
5. 비밀 지수 d를 구한다.
   => d ≡ e^-1 (mod φ(n))
   
   

3) 암호화

공개키 (n, e)로 n보다 작은 평문 m을 암호화할 때, 암호문 c는 
c ≡ m^e (mod n)
으로 구해진다.

4) 복호화

암호문 c를 개인키 d로 복화화할 때, 평문 m은 
m ≡ c^d (mod n)
c^d ≡ (m^e)^d ≡ m^ed (mod n)
으로 구해진다.

 

---

 

이번 시간에는 공개키 암호 중 RSA에 대하여 공부하였다.

다음 시간에는 hash에 대하여 공부할 것이다.