메시지를 암호화 해서 상대방에게 전달할 때 암호화 하는 키와 복호화 하는 키가 같으면 (대칭키 방식) 문제가 생길 수 있다. 해당 키를 상대방에게 전달하는 과정에서 키가 노출이 되는 위험이 있을 수 있고 설령 키가 무사히 전달되더라도 다수의 사람이 키를 보관하는 과정에서 유출되기 쉽다.
그래서 1970년 대 이후, 대칭키 방식이 아닌 공개키 방식의 암호화&복호화 방식을 주로 사용하고 있다. 즉 암호화는 Public Key로 누구나 할 수 있지만 복호화는 메시지를 받는 사람, 즉, Private Key를 가지고 있는 사람만 할 수 있게 하는 방식이다. 공개키 방식의 암호화 방식의 대표적인 예가 RSA 알고리즘인데 일반적으로 두수의 곱은 구하기 쉽지만 그 수의 인수분해는 어렵다는 점을 이용한다. RSA 알고리즘은 아래의 세단계를 거쳐서 메시지를 생성하고 암호화 하고 복호화 한다.
1. Public Key & Private Key 생성
1) public key (e) 생성
두 소수 (p,q) 선택 |
p=5 , q=11 |
n= p x q |
n=5 x 11 = 55 |
phi = (p-1) x (q-1) |
phi = 4 x 10 = 40 |
phi 와 서로소 관계에 있는 임의의 수 e 산출 |
7 |
e -> Public Key로 결정 |
7-> Public Key |
2) pivate key (d) 생성
e x d mod phi =1 을 만족하는 d 산출 (유클리드 호제법 사용) |
d= 23 |
7 x '23' mod 40 = 1 |
23-> Private Key |
2. 암호화
철수(public key holder)가 영희(private key holder)에게 "9"라는 메시지를 보내려 한다. 철수는 메시지 M(=9)을 공개키 "e"와 "n"을 사용하여 암호화 한다.
Me mod n = C
97 mod 55 = 4,782,969 mod 55 = 4
3. 복호화
영희는 철수에게 받은 "9"라는 메시지를 "d"를 사용하여 복호화 하여 원래 메시지인 9를 알아낸다
Cd mod n = M
423 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)를 구하는데 상당한 시간이 걸린다는 점을 이용한 알고리즘이다.
'Coding Study > Python & Django' 카테고리의 다른 글
Django 배포 후 DNS 설정 Welcome to nginx 페이지만 나온다면? (0) | 2018.11.08 |
---|---|
(100-1)How to extract a random element from a python list. (0) | 2018.07.10 |
(100-1)파이썬 리스트에서 멤버 무작위 추출하기 (secret module) (0) | 2017.12.02 |
RSA 암호 알고리즘 정리 (0) | 2017.03.09 |
파이썬 프로젝트 1: 수열 직접 만들어 오름차수로 정렬하기 (0) | 2017.03.04 |