실제 프로그램과 함께 보는 RSA 알고리즘

RSA == 공개키 암호화 방식 

은 PUBLIC, PRIVTAE 이 두 개의 키를 이용해서 암호화/복호화를 진행합니다. 

그렇다면 먼저 봐야할 것은 이러한 두 키가 어떻게 만들어지는가 입니다.

1. p, q 구하기 

2. N 구하기 

2. 그리고 p, q 를 서로 곱해서 N을 만듭니다.  N = p * q

앞에서 1과 3을 입력했으므로 N은 3이 됩니다. 

- RSA KEY 연산을 하는 프로그램에서도 실제로 p * q 연산을 하는 것을 확인할 수 있습니다.

 

3. e와 d구하기 

그리고 이 N 이 각각

3. 공개키 (e, N)  개인키 d, N) 으로 들어갑니다.

그렇다면 다음은 e와 d도 구해줘야합니다. 

<오일러 φ 함수 :  1부터 n 까지의 양의 정수 중에 n과 서로소 인 것의 개수를 나타낸다. >

φ(N) = (p-1)(q-1)

e :  φ(N) 와 서로소이면서 φ(N) 보다 작은 수 

d :  (d * e) % φ(N)  = 1    을 통해서 d를 구한다. 

4. 공개키와 개인키 생성 

공개키 ( e, n )   개인키 ( d , n)

5. 암호화와 복호화 과정 

암호화 과정

2라는 숫자를 암호화한다고 치면  

Encrypt = 2^e % n 이다. 

Decrypt = Encrypt^d % n