CPA and programming

메시지를 암호화 해서 상대방에게 전달할 때 암호화 하는 키와 복호화 하는 키가 같으면 (대칭키 방식) 문제가 생길 수 있다. 해당 키를 상대방에게 전달하는 과정에서 키가 노출이 되는 위험이 있을 수 있고 설령 키가 무사히 전달되더라도 다수의 사람이 키를 보관하는 과정에서 유출되기 쉽다.

그래서 1970년 대 이후, 대칭키 방식이 아닌 공개키 방식의 암호화&복호화 방식을 주로 사용하고 있다. 즉 암호화는 Public Key로 누구나 할 수 있지만 복호화는 메시지를 받는 사람, 즉,  Private Key를 가지고 있는 사람만 할 수 있게 하는 방식이다. 공개키 방식의 암호화 방식의 대표적인 예가 RSA 알고리즘인데 일반적으로 두수의 곱은 구하기 쉽지만 그 수의 인수분해는 어렵다는 점을 이용한다. RSA 알고리즘은 아래의 세단계를 거쳐서 메시지를 생성하고 암호화 하고 복호화 한다.

1. Public Key & Private Key 생성 

1) public key (e) 생성

2) pivate key (d) 생성
  

2. 암호화

철수(public key holder)가 영희(private key holder)에게 "9"라는 메시지를 보내려 한다. 철수는 메시지 M(=9)을 공개키 "e"와 "n"을 사용하여 암호화 한다.

M^e mod n = C

9⁷ mod 55 = 4,782,969 mod 55 = 4

3. 복호화

영희는 철수에게 받은 "9"라는 메시지를 "d"를 사용하여 복호화 하여 원래 메시지인 9를 알아낸다

C^d mod n = M

4²³ mod 55 = 70,368,744,177,664 mod 55 = 9

위의 예에서 대중에게 노출되선 절대 안되는 값이 p, q, 그리고 d이다. 이들이 private key 역할을 한다. p, q 중 하나만 공개 되도 누구나 d를 산출할 수 있어 암호 체계는 무너진다.  반면 n과 e는 대중에게 노출이 되는 public key이다.

RSA의 기본 원리는 누구나 n은 알고 있지만 n의 인수인 p와 q를 쉽게 찾을 수 없다는 점에 기인한다. 예시에서는 쉽게 만들기 위해 아주 작은 수를 사용하였지만 실제 p와 q는 상당히 큰 수들이다.  RSA는 p와 q의 곱(n)을 알고 있더라도 그 두 수 (p or q)를 구하는데 상당한 시간이 걸린다는 점을 이용한 알고리즘이다.