디피-헬만 알고리즘

디피-헬만 알고리즘이란?

미국 스탠퍼드 대학교의 휫필드 디피(Whitfield Diffie)와 마틴 헬만(Martin Hellman)이 공동 개발한 디피 헬만 키 교환 알고리즘에 대해 알아보겠습니다.

디피 헬만 알고리즘은 이산 대수의 어려움으로 탄생한 알고리즘입니다. 

$$ y = g^x \bmod p $$

이와 같은 공식이 있습니다. p는 소수이고 g는 정수로 엄청 큰 숫자 입니다. 이 두 수는 공개된 숫자입니다. 이 때 p, g, x를 알고 있다면 y는 구하기 쉽지만 p, g, y를 알고 있을 때에는 x를 구하기 어렵다는 점에 착안하여 만들어졌습니다. 4662라는 숫자가 있을 때 이 숫자가 어떤 두 수의 곱인지는 알기 쉽지 않습니다. 하지만 반대로 63이라는 숫자를 알고 있다면 4662 / 63으로 나머지 하나의 숫자가 74라는 것을 금방 알 수 있습니다. 이렇게 한쪽 계산은 쉽지만 반대쪽 계산이 어려운 이산 대수 문제로 암호화한 것입니다.

암호화 알고리즘을 왜 쓸까?

그럼 이렇게 복잡한 알고리즘을 쓰는 이유는 무엇일까요? 우리는 자연스럽게 사용하고 있는 이 인터넷이 보안에 너무 취약하기 때문입니다. 두 사람이 사람들이 엄청 많은 공원 한 가운데서 멀리 떨어져 큰 소리로 이야기를 하고 있다고 생각하면 됩니다. 보통 사람들은 시끄럽지만 두 사람의 대화 내용에 크게 관심을 두지 않겠지만, 너무 시끄럽게 말하다보니 의도치 않게 중요 정보를 알게되는 사람도 생기고, 일부 나쁜 의도를 가진 사람들은 두 사람의 이야기를 듣고 있다가 자신이 원하는 정보를 몰래 가져갈 수도 있습니다. 

 

이렇게 인터넷은 모든것이 공개되어 있고, 그 안에서 두 사람이 비밀스럽게 이야기 하기 위해서는 암호화를 해야 합니다. 둘만 알 수 있는 비밀스런 은어를 만들어 서로 교환하면 됩니다. 그 은어를 정하는 것부터가 문제입니다. 지금부터 어떤 숫자를 암호로 쓸꺼야 라고 말하는 순간 주변 사람들은 암호가 무엇인지 다 알게 됩니다. 서로 말하지 않고도 암호를 만들 방법이 필요 했습니다.

 

디피 헬만 알고리즘 원리

그럼 어떻게 만나지 않고 서로 암호를 공유할 수 있을지 알아보겠습니다. 기본적인 원리는 아까 설명한 수식에 있습니다. 두 사람이 각각 m과 n이라는 자신만 알고 있는 숫자를 생각합니다. 그럼 어떤 정수 g에 대해서 아래 식이 성립합니다.

$$ (g^m)^n = (g^n)^m = g^{mn} $$

이것은 3 * 5와 5 * 3이 같다는 것과 같이 간단한 식입니다. 위의 식이 모듈로 연산에서도 똑같이 동작 합니다.

$$ (g^m)^n = (g^n)^m = g^{mn} \bmod p,(p는 소수)$$

이처럼 p와 g는 서로 교환한 적이 있지만 m과 n은 서로 교환한 적이 없습니다. 이 때 p와 g 그리고 암호화된 값을 알아도 m, n을 찾기 힘들다는 것이 디피 헬만 알고리즘의 핵심 입니다.

디피 헬만 알고리즘의 예

공식으로 이해하기 힘들기 때문에 예를 들어 이해해 보겠습니다. 실제 알고리즘에는 2048bit의 큰 수를 선택하지만 우리는 계산의 편의를 위해 간단한 숫자로 만들겠습니다. 소수 p = 7, 정수 g = 2라고 해보겠습니다. 먼저 두 사람은 p, g 두 숫자를 서로 공유 합니다. 이 숫자는 공개된 숫자로 해커들도 충분히 알 수 있게 됩니다.

 

그럼 첫 번째 사람 Alice는 숫자 5을 비밀값 m으로 하고 두 번째 사람 Bob은 숫자 13을 비밀값 n으로 합니다. 

Alice의 값은 $g^m$ % p = $2^5$ % 7 = 4 가 됩니다.

Bob의 값은 $g^n$ % p = $2^13$ % 7 = 2가 됩니다. 

Alice와 Bob은 서로의 혼합값 4와 2을 교환 합니다.

Alice가 받은 혼합값 2로 $g^m$ % p를 계산하면 $2^5$ % 7 를 계한하여 4를 얻습니다.

Bob 역시 혼합값 4로 $4^13$ % 7로 똑같이 4라는 숫자를 비밀키를 얻게 됩니다.

디피 헬만 알고리즘의 한계

위의 예를 통해 4라는 비밀키를 공유하지 않았지만 서로가 생각한 숫자들로 4를 유추할 수 있었습니다. p와 g는 공개된 숫자로 상관 없지만 혼합값이었던 4와 2가 도청된다면 더이상 기밀성이 보장되지 않습니다. 특히나 해커가 중간에서 4와 2를 받아서 다른 값을 서로에게 전달한다면 두 사람은 해커의 존재를 모르는 상태에서 비밀키를 공유하게 됩니다. 이렇게 해커가 중간에서 장난치는 것을 중간자 공격(Man In The Middle attack)이라고 하고 줄여서 MITM 공격이라고 합니다. 디피 헬만 알고리즘은 이 MITM 공격에 취약합니다. 따라서 이 문제를 해결하고자 RSA 알고리즘이라는 것이 등장하게 됩니다. RSA 에 대해서는 다음 시간에 같이 알아보도록 하겠습니다.