[암호학] 4. RSA 암호

RSA 암호는 다음 4단계의 준비가 필요하다.

1. $N$ 을 구한다.
   임의의 두 소수 $p,q$ 에 대해서 $N = pq$ 이다.
2. $\Phi(N)$ 을 구한다.
   $\Phi(N) = (p - 1)(q - 1)$ 이다.
3. $e$ 를 구한다. ($e$는 공개키 이다.)
   $gcd(e, Φ(N)) = 1$을 만족시키는 정수 $e$를 구한다. (단, $0 < e < \Phi(n)$)
   (즉, $p−1, q−1$과 각각 서로소인 정수 $e$를 준비한다.)
4. $d$ 를 구한다. ($d$는 개인키 이다.)
   $d\cdot e \equiv 1 \pmod{\Phi(N)}$ 을 만족시키는 정수 $d$를 구한다. (단, $0 < d < \Phi(n)$)

이러한 방법으로 4가지를 구하면 RSA 암호의 준비가 끝난다. 평문을 $x$, 암호문을 $y$라고 하자. 그러면 암호화 및 복호화 하는 방법은 다음과 같다.

\(\begin{equation} y \equiv x^{e} \pmod{N} \label{eq:series1} \end{equation}\) \(\begin{equation} x \equiv y^{d} \pmod{N} \label{eq:series2} \end{equation}\)

(1)을 통해 암호화를 하고 (2)를 통해 복호화를 한다.

왜 (2)는 참일까?

$x^{ed} \equiv x\pmod{N}$를 증명하면 충분하다. 앞서 언급했던 RSA암호의 4번째 성질인 d의 정의 때문에 다음을 만족한다. \(\begin{equation} ed \equiv 1 \pmod{\Phi(N)} \label{eq:series3} \end{equation}\) (3)을 이용하면 $ed = 1 + k\Phi(N)$를 만족시키는 정수 $k$가 존재한다.

\[\begin{equation*} x^{ed} = x^{1 + k\Phi(N)} \end{equation*}\]

정수론에서의 오일러 정리는 다음과 같다.

$a, n$이 서로소인 양의 정수일 때
$a^{\phi(n)} \equiv 1 \pmod{n}$

오일러 정리를 이용하면 다음과 같다.

\[\begin{align*} &x^{ed} = x^{1 + k\Phi(N)} = x \cdot x^{k\Phi(N)} \\ &\Rightarrow y^{d} \equiv x^{ed} \equiv x \pmod{N} \;□ \end{align*}\]