[Discrete Mathematics] RSA 공개키 암호 시스템

---

공개키 암호 시스템

 

발신자와 수신자가 메시지를 외부에 노출하지 않으려면, 메시지를 은밀하게 보내는 방법도 사용할 수 있겠지만, 남들이 보더라도 무슨 말인지 알 수 없게 암호화하여 메시지를 보낼 수도 있을 것이다. 이때 발신자는 메시지를 암호화(encrypt)하여 수신자에게 보내야 할 것이고, 수신자는 받은 메시지를 복호화(decrypt)하여 확인해야 할 것이다.

이러한 암호 시스템 중 하나가 공개키 암호 시스템인데, 개인키를 숨김으로써 메시지를 아무나 복호화할 수 없도록 하고, 공개키를 통해 암호화를 한다. 즉 절차는 다음과 같다.

• 먼저 수신자가 공개키와 개인키를 만들어 발신자에게 공개키를 보낸다. 이때 개인키는 공개되지 않도록 하며 수신자만 확인할 수 있어야 한다.
• 발신자는 수신자가 보낸 공개키를 이용하여 메시지를 암호화한다.
• 암호화된 메시지를 수신자에게 발신한다.
• 수신자는 개인키를 이용하여 암호화된 메시지를 복호화한다.

 

---

RSA 암호화

 

RSA 암호화는 다음과 같다.

• 공개키($ n $, $ e $)와 개인키($ d $)를 수신자가 생성한다.
• $ n $ 선택은 다음과 같다. 소수 $ p $ 와 $ q $ 를 선택하면 $ n = pq $ 이다.
• $ e $ 선택은 다음과 같다. $ \phi(n) = (p-1)(q-1) $ 을 계산한 후 $ \gcd(e, \phi(n)) = 1 $ 인 정수 $ e $ 을 선택한다.
• $ d $ 계산은 다음과 같다. $ 0 < d < \phi(n) $ 이고 $ ed \bmod \phi(n) = 1 $ 인 유일한 $ d $ 를 계산한다.
• 발신자는 공개키를 이용하여 발신할 정수(메시지) $ m $ $( 0 < m \leq n - 1) $ 를 $ c = m^e \bmod n $ 로 암호화한다.
• 발신자는 암호화된 정수(메시지)를 수신자에게 보낸다.
• 수신자는 $ c^d \bmod n $ 를 계산하여 복호화된 정수(메시지) $ m $ 를 얻는다.

만약 개인키를 모르는 누군가가 개인키를 구하려 한다면 공개키인 $ n $ 을 인수분해해야 한다. 그러나 지금까지 알려진 효율적인 인수분해 알고리즘은 없기 때문에 큰 값의 $ n $ 에 대해서 인수분해를 시도하는 것은 굉장히 비효율적이다. 결국 개인키를 모를 때 복호화에 들어가는 비용이 막대하기 때문에 효율적인 암호 알고리즘이라 할 수 있다.

 

---

예시

 

$ A $ 가 발신자이고 $ B $ 가 수신자이며 $ p = 61 $, $ q = 53 $ 이라 가정하자.

$ n = p \times q = 61 \times 53 = 3233 $

$ \phi(n) = (p-1) (q-1) = 60 \times 52 = 3120 $

공개키 $ e $ 으로 $ 17 $ 을 선택한다. $ \gcd(3120, 17) = 1 $ 이다.

개인키 $ d $ 를 찾아야 한다. $ ed = 1 (\bmod \phi(n)) $ 이어야 한다. 여기서 $ d = 2753$ 이다.

$ B $ 는 $ e $ 와 $ n $ 을 $ A $ 에게 전달한다.

메시지 $ m $ 을 $ 65 $ 라 해보자. 암호문 $ c $ 는 다음과 같이 계산된다.

$ c = m^e \bmod n = 65^{17} \bmod 3233 = 2790 $

따라서 $ A $ 는 이렇게 계산된 $ c = 2790 $ 을 $ B $ 에게 전달한다.

$ B $ 는 암호 $ c $ 를 복호화한다.

$ c^d \bmod n = 2790^{2753} \bmod 3233 = 65 $

이렇게 메시지 $ m $ 이 안전하게 전달되었다.