[Cryptography 1.] RSA system

이번 포스트에서는 public key system들 중, RSA system에 대해서 간략하게 설명하겠습니다.

RSA system이란 무엇인가

RSA system은 '매우 큰 수를 소인수 분해하기 어렵다'는 가정에서 출발합니다. RSA system을 build하는 방법은 다음과 같습니다.

1) 매우 큰 소수 $p, q$ 를 준비합니다.
2) 소수 p, q를 곱해 N을 만듭니다. $N = p * q$
3) N의 Euler totient function의 값, $\phi(N) = (p-1) * (q-1)$ 과 서로소인 수 $e$를 준비합니다.
4) $d \equiv e^{-1} \pmod {\phi(N)}$ 인 $d$ 값을 구합니다.

위와 과정을 거친 후, 다음과 같이 RSA system을 정의하겠습니다.

Public key는 $(e, N)$ 으로, private key는 $d$ 로 정의합니다.

암호화할 메시지 $M$ 이 있다고 하고, 이를 암호화하기 전 특정 규칙에 따라 일련의 수로 변환했다고 가정하겠습니다. 암호화는 다음과 같은 과정으로 이루어집니다. 암호화는 메시지를 전달할 대상의 public key를 이용합니다.

암호화된 메시지는 $C \equiv M^{e} \pmod {N}$ 으로 정의합니다.

복호화는 메시지를 전달받은 쪽의 private key를 통해 이루어집니다.

복호화는 $M \equiv C^{d} \pmod {N}$ 을 통해 이루어집니다.

RSA system의 정당성

위에서 소개한 복호화 방법으로 어떻게 원문을 얻어낼 수 있는 걸까요? 간단한 수학적 증명으로 보일 수 있습니다.

위와 같은 암호화 과정을 거친 후 나온 메시지 $C$에 대하여, $C^{d} \equiv M \pmod{N}$ 임을 증명하겠습니다.

위에서 두 가지 케이스를 생각할 수 있겠습니다.

두 번째 케이스는 $M$과 $N$이 서로소가 아닌 경우입니다.

RSA system에서 제시하는 복호화 방법으로 원문 $M$ 을 얻어낼 수 있음을 보였습니다.

RSA system의 안정성은 앞에서 설명했듯이, 큰 수를 소인수 분해하기 어렵다는 가정에서 출발합니다. 위에서 $N$ 이 어떤 소인수로 분해될지 알기 어렵다는 사실이, 어떻게 이 암호 체계의 안정성을 보장할 수 있을까요?

$N = p*q$ 일 때, $p, q$의 값을 빠르게 찾아낼 수 있다고 가정해 보겠습니다. $p, q$ 의 값을 통해 빠르게 Euler totient function의 값을 얻어낼 수 있고, $modulo \;\phi(n)$ 에 대한 public key( $e$ ) 의 inverse(private key)를 계산할 수 있을 것입니다.