친구에게 중요한 이메일을 보낼 때, 혹은 아마존에서 결제를 하기 위해 신용카드 정보를 적어야 할 때 우리는 어떻게 하면 정보의 보안을 지킬 수 있을까?
간단한 상황을 보자.
영희는 철수에게 비밀 쪽지를 보내고 싶어 한다. 하지만 문제가 있다. 철수를 짝사랑하는 순대는 이 둘의 쪽지 대화가 오가는 도중에 몰래 훔쳐본다.
이런 경우에 영희는 원본을 encrypt(암호화) 해 철수에게 전달할 수 있다. 예를 들어 영희는 철수에게 내일 “832번지”에서 만나자는 내용을 보내고 싶어 한다. 동시에, 영희와 철수가 처음 만났던 장소의 번지수인 11번가는 둘만이 아는 사실이라고 가정하자.
영희는 쪽지에 이렇게 적는다: “우리가 처음 만난 장소의 번지수에서 721을 더한 값을 구해봐. 그 값은 우리가 내일 만날 장소의 번지수야!”
이렇게 쪽지를 주고받는다면 순대는 영희와 철수가 만나는 장소에 대해서 알 수 있는 방법이 없다.
하지만 이 방법은 언제나 유용하진 않다. 이유는 영희와 철수가 쪽지를 보내기 전 서로 사전동의가 된 공유 키(shared key)가 있다는 가정하에만 쓸 수 있는 방법이기 때문이다. 위에 상황에서의 공유키는 “11번지”이다.
만약 영희와 철수가 한 번도 본 적도 없고, 메시지를 주고받은 적도 없다면 어떻게 해야 insecure channel을 통해 대화함과 동시에 이 둘만 메시지를 해독할 수 있게 원본을 변조해야 할까? (앞서 이메일과 신용카드 정보에 대해 언급을 했었다. 인터넷에서는 라우터(router)라 불리는 수많은 컴퓨터를 거쳐 메시지가 전달되기에 라우터에 액세스만 가능하다면 누구나 메시지를 볼 수가 있다. 이런 경우같이 안전하지 않은 전달 경로를 insecure channel이라고 지칭한다.)
디피-헬먼 키 교환(Diffie–Hellman key exchange) 프로토콜은 이와 같은 상황에 유용한 해결책으로, 모든 사람들이 볼 수 있는 공개키(public key)와 자신만이 볼 수 있는 개인키(private key)를 만들어 이로부터 영희와 철수만 서로 아는 공유키(shared key)를 생성하는 일종의 알고리즘이다.
복잡한 수학적 접근을 피해서 다양한 색깔 혼합을 통해 영희와 철수만 알 수 있는 공유키를 만들어보자.
Step 1 : 영희와 철수는 각각 개인키로 쓸 색깔을 하나씩 고른다.
영희의 개인키- 빨강
철수의 개인키- 노랑
여기서 한 가지 조건이 있는데, 영희와 철수는 자신이 무슨 색을 골랐는지 자신 말고는 아무에게도 알려선 안 된다.
Step 2 : 영희와 철수가 같이 색깔 하나를 고른 뒤 모든 사람들 (순대 포함) 앞에서 공개를 한다. 이 색깔은 공개키가 된다.
공개키- 보라
Step3 : 영희와 철수는 각자 자신의 개인키 색에 공개키인 보라색을 혼합한다.
영희 : 빨강 + 보라 = 자홍
철수 : 노랑 + 보라 = 브라운
Step 4 : 영희와 철수는 이제 자기가 가지고 있는 혼합된 색을 insecure channel을 통해 서로 바꾼다.
이때 모든 사람들은 영희와 철수가 색을 뒤바꾸는 장면을 목격한다.
영희 : 브라운
철수 : 자홍
Step 5 : 영희는 이제 철수에게 받은 혼합된 색에서 자신의 개인키 색을 한 번 더 혼합한다.
똑같이, 철수도 영희에게 전달받은 색에서 자신의 개인키 색을 한 번 더 혼합한다. 결과를 보자:
영희: 브라운 + 빨강 = (노랑 + 보라) + 빨강 = 벽돌색
철수: 자홍 + 노랑 = (빨강 + 보라) + 노랑 = 벽돌색
이렇게 과정을 거치면 영희와 철수는 결국에 같은 컬러인 벽돌색을 얻게 되고, 이것은 둘만이 아는 공유키가 되는 것이다. 그렇다면 어떻게 옆에서 엿듣고 있는 순대는 공유키 색을 알 수 없는 걸까?
이유는 순대가 영희와 철수의 개인 색을 모르기 때문이다.
순대가 아는 정보를 간단한 방정식으로 표현하자면 다음과 같다:
1. 공유키 = 보라
2. 보라 + x = 브라운
3. 보라 + y = 자홍
4. 공유키 = 브라운 + y = 자홍 + x
순대가 공유 키를 알기 위해선 x와 y를 알아야 하는데, 이는 무척 어려운 일이다.
그 이유는 수학적 일방향 행위(one-way action) 때문이다.
두 색을 섞으면 어떤 색이 나오는지는 쉽게 알 수 있지만 특정한 색을 두고 이 색을 혼합한 두 색을 찾는 것은 상당히 어렵고 많은 시간이 소모되기 때문이다. (물론 위에 예시는 색깔에 대해서 잘 안다면 쉽게 풀 수 있는 문제일 만큼 간단하다.)
이같이 영희와 철수는 한 번도 대화를 해본 적이 없어도 디피-헬먼 키 교환 알고리즘을 이용해 쉽게 공유키를 만들어낼 수 있고, 이 공유키는 순대가 쉽게 알아낼 수 있는 방법이 없다.
하지만 앞서 언급했듯이 색깔 혼합 트릭은 대중에게 콘셉트 이해를 위해 만들어낸 예시일 뿐이다. 디피-헬먼의 실체는 다소 큰 소수(prime number)를 이용한 나머지 연산(modular arithematic)을 통해 키 교환을 하는데, 이는 생각보다 어렵지 않다. 수학적 연산이 궁금한 독자는 아래 링크를 참고하길 바란다.
