RSA 암호화 프로그램(1) - 이론

이번 포스팅은 RSA 암호화 프로그램을 개발하고자 한다.

 

RSA 암호화 알고리즘은 공개키 암호화 알고리즘으로 개인키와 공개키를 만들어서,

개인키로 암호화를 하면 공개키로만 복호화를 할 수 있고

공개키로 암호화를 하면 개인키로만 복호화를 할 수 있다.

 

먼저 개인키와 공개키를 만들어보자 (간단하다!)

 

개인키와 공개키 만들기

1. 소수인 $ p, q $를 무작위로 뽑는다.

2. n을 구한다. $n = p \times q$ 

3. 오일러 수를 구한다. $\Phi = (p - 1)(q - 1)$

4. $\Phi$와 서로소인 정수 $e$를 구한다.

5. $e \times d \pmod{\Phi} = 1$ 인 $d$를 구한다.

 

여기서 개인키는 $(d, n)$, 공개키는 $(e, n)$이다.

 

암호화 복호화

개인키를 이용해 C를 암호화하는 방식은 다음과 같다.

$M = C^d \pmod{n}$ 이때, C < n이어야 한다.

 

공개키를 이용해 M를 C로 복호화 하는 방법은 아래와 같다.

$C = M^e \pmod{n}$

 

공개키로 암호화를 한 후, 개인키로 복호화를 할 수도 있다.

다음장에서 이 방식을 이용한 프로그램을 소개할 것이다.