디피-헬만 키 교환은 말 그대로 키를 교환하는 방식을 정의한 것이다. 키는 안전한 통신을 위해 암호화를 적용할 때 필요한데, 디피-헬만 키 교환 방식에 의해 통신 당사자들은 하나의 키를 공유할 수 있다. 따라서 암호화/복호화에 동일한 키를 사용하는 대칭 키 암호화 방식(symmetric key cryptography algorithm)에 주로 사용한다.

암호화 알고리즘과 키

예를 들어, Alice가 Bob에게 “abcd"라는 메시지를 보낼 때 다른 사람은 이 메시지를 볼 수 없도록 암호화한다고 가정해 보자.

가장 간단한 방법으로 각 문자를 알파벳 순서 상 바로 다음 문자로 변경(+1)해 보내는 것을 생각해 볼 수 있다. 즉, “bcde"라고 보내는 것이다.

Bob은 Alice에게서 “bcde"라는 메시지를 받으면 각 문자를 알파벳 순서 상 바로 전 문자로 변경(-1)해 원문을 확인할 수 있다.

이 방식이 가능하려면 Alice와 Bob은 다음 정보를 공유하고 있어야 한다.

• 알파벳 상 일정 순서 뒤의 문자로 치환하는 방식으로 암호화했다.
• 일정 순서는 1이다.

이 중 첫 번째에 해당하는 정보가 바로 암호화 알고리즘이며, 두 번째에 해당하는 정보가 암호화 키이다. 예의 암호화 알고리즘은 암호화와 복호화에 동일한 키를 사용하기 때문에 대칭 키 암호화 알고리즘이다.

Alice와 Bob이 안전한 통신을 하기 위해서는 이 두 가지 정보를 모두 제3자로부터 숨기는 것이 좋다. 하지만 나머지 하나의 정보를 모르면 한 가지 정보만으로는 암호화된 정보를 해독할 수 없기 때문에 둘 중 하나의 정보만 숨겨도 된다.

하나만 숨기고 나머지 하나를 공개한다면 어떤 것을 숨기는 것이 더 좋을까? 이는 둘 중 어떤 것이 더 경우의 수가 많은지를 생각하면 답이 자명하다. 경우의 수가 많아야 제3자가 암호를 해독하기 더 어려워지기 때문이다. 암호화 알고리즘 보다는 암호화 키의 경우의 수가 훨씬 다양하므로 대부분의 암호화 통신은 다음과 유사한 절차로 진행된다.

디피-헬만 키 교환

이제 Alice와 Bob이 안전하게 키만 교환할 수 있으면 Alice, Bob 간 암호화 통신이 가능하다. 가장 쉽게 생각할 수 있는 방법은 별도의 수단을 이용해 Alice와 Bob이 키를 사전에 공유하는 것이다. 문자메시지를 암호화하고 싶다면, 문자메시지와 다른 수단인 이메일이나 쪽지에 키를 적어 전해주는 것이다. 이렇게 공유한 키를 사전 공유키(PSK, Pre-Shared Key)라 한다.

PSK 사용은 키 교환 절차가 번거롭고, 별도의 수단이 안전하다는 보장이 없다는 문제점을 가지고 있다. 디피-헬만 키 교환은 별도의 수단을 이용하지 않고도 간단하고, 안전한 키 교환을 가능하게 한다.

아래에 등장하는 기호 중 \(\bmod\)는, 교과 과정에는 등장하지 않지만 개발자들에게는 매우 친숙한, 나머지를 구하는 연산을 나타낸다. 즉, \(a \bmod b\)는 \(a\)를 \(b\)로 나눈 나머지를 의미한다.

교환 절차

1. Alice는 충분히 큰 소수 \(p\)와 적당한 \(g\)를 하나씩 정한다.
2. Alice는 무작위로 정수 \(a\)를 하나 고른다.
3. Alice는 \(A = g ^ a \bmod p\)를 구한다.
4. Alice는 \(p, g, A\)를 Bob에게 전달한다.
5. Bob은 무작위로 정수 \(b\)를 하나 고른다.
6. Bob은 \(B = g ^ b \bmod p\)를 구한다.
7. Bob은 Alice에게 \(B\)를 전달한다.

이상을 도식화하면 아래와 같고, 화살표 위에 표시된 정보들은 Alice, Bob 외에 제3자도 볼 수 있다. 즉, Alice만 알고 있는 \(a\), Bob만 알고 있는 \(b\)가 이 과정에서 숨겨져 있는 정보의 전부이다.

키 생성 방법과 증명

이상의 정보들을 이용해 Alice와 Bob은 공통의 키를 만들 수 있고 그 방법은 다음과 같다.

• Alice의 키 \(k _ {Alice} = B ^ a \bmod p\)
• Bob의 키 \(k _ {Bob} = A ^ b \bmod p\)

\(a\)는 Alice만 알고 있는 값이고, \(p\)는 서로 공유한 값, \(B\)는 Bob에게서 받은 값이니 Alice는 \(k_{Alice}\)를 계산할 수 있다. Bob 역시 같은 방법으로 \(k _ {Bob}\)을 계산할 수 있다. 이제 이 두 값이 같음을 보이면 된다.

Alice와 Bob이 각각 생성한 \(A\), \(B\)는 \(g\)를 \(a\) 또는 \(b\) 제곱해 \(p\)로 나눈 나머지이므로 다음과 같이 정리할 수 있다.

$$ g ^ a = pm + A $$

$$ g ^ b = pn + B $$

Alice가 \(B\)가 아닌 \(b\)를 알 수 있어 \(k _ {Alice}\)를 구하는 공식에 \(B\) 대신 \(g ^ b\)를 넣는다고 가정해보자. 이렇게 얻어진 키를 \({k _ {Alice}} ^ {\prime} \)라 하겠다.

$$ {k _ {Alice}} ^ {\prime} = (g ^ b) ^ a \bmod p $$

여기에 위에서 정리한 \(g^b\)를 대입하면,

$$ (g ^ b) ^ a \bmod p = (pn + B) ^ a \bmod p $$

이 된다. \((pn + B) ^ a\)를 전개하면 다음과 같다.

$$ \begin{matrix} (pn + B) ^ a &=& & (pn) ^ a \\ & & + & \cdots \\ & & + & CpnB ^ {a-1} \\ & & + & B ^ a \end{matrix}$$

줄임표로 생략돼 있기는 하지만 마지막 항인 \(B ^ a\)를 제외하고는 모든 항이 \(p\)를 하나 이상 포함하고 있는 것을 알 수 있다. 이 값을 \(p\)로 나눈 나머지를 구하면 모든 항이 사라지고 \(B ^ a \bmod p\)만 남게 된다. 즉,

$$\begin{matrix} {k _ {Alice}} ^ {\prime} &=& (g ^ b) ^ a \bmod p \\ &=& B ^ a \bmod p \\ &=& k _ {Alice} \end{matrix}$$

의 관계를 만족한다

Bob의 경우도 같은 가정으로 풀이하면 다음 관계를 알 수 있다.

$$ \begin{matrix} {k _ {Bob}} ^ {\prime} &=& (g ^ a) ^ b \bmod p \\ &=& A ^ b \bmod p \\ &=& k _ {Bob} \end{matrix}$$

즉, \(k _ {Alice}\)는 \((g ^ b) ^ a\)를 \(p\)로 나눈 나머지와 같고, \(k _ {Bob}\)은 \((g ^ a) ^ b\)를 \(p\)로 나눈 나머지와 같다.

$$ (g ^ b) ^ a = g ^ {ba} = g ^ {ab} = (g ^ a) ^ b $$

이므로 \(k _ {Alice}\)와 \(k _ {Bob}\)는 같은 값이 된다.

선택 기준

교환 절차에서 조건만 제시한 \(p\)와 \(g\)의 선택 기준에 대해 알아보자.

키는 어떤 수를 \(p\)로 나눈 나머지이고 이 나머지는 \(p\)보다 크거나 같을 수 없다. 앞에서도 언급했듯 경우의 수가 많을수록 제3자가 해독하기 어려워지니 키의 경우의 수를 늘리는 것이 곧 보안성을 좋게 하는 것이다. 따라서 나머지가 0부터 \(p - 1\)까지 \(p\)가지 경우를 갖게 하는 것이 최상이다.

\(p\)가 소수인 이유

\(g\)가 2인 간단한 예를 통해 \(p\)가 소수일 때(=11)와 그렇지 않을 때(=12) 나머지들을 확인해보자.

$$ 2 ^ 0 \bmod 11 = 1 \bmod 11 = 1$$

$$ 2^1 \bmod 11 = 2 \bmod 11 = 2 $$

$$ 2 ^ 2 \bmod 11 = 4 \bmod 11 = 4 $$

$$ 2 ^ 3 \bmod 11 = 8 \bmod 11 = 8 $$

$$ 2 ^ 4 \bmod 11 = 16 \bmod 11 = 5 $$

$$ 2 ^ 5 \bmod 11 = 32 \bmod 11 = 10 $$

$$ 2 ^ 6 \bmod 11 = 64 \bmod 11 = 9 $$

$$ 2 ^ 7 \bmod 11 = 128 \bmod 11 = 7 $$

$$ 2 ^ 8 \bmod 11 = 256 \bmod 11 = 3 $$

$$ 2 ^ 9 \bmod 11 = 512 \bmod 11 = 6 $$

$$ 2 ^ {10} \bmod 11 = 1024 \bmod 11 = 1 $$

0은 빠져 있지만 1부터 10까지 나머지들이 나온다. 즉, 경우의 수가 10가지이다. 위에서 제시한 최상의 조건보다는 나머지가 0인 경우가 빠져 있어 부족해 보이지만, 사실 이 경우가 최상이다. 왜냐하면 \(p\)가 소수이므로 \(p\)로 나누어 떨어지려면—나머지가 0이려면— \(g\)를 소인수분해 했을 때 \(p\)를 인수로 포함해야 한다. 그런데 \(g\)의 인수에 \(p\)가 포함되면 숨김 값—\(a\) 또는 \(b\)—으로 0을 제외한 어떤 값을 선택해도 \(p\)로 나눈 나머지는 0이 돼 버린다.

$$ 2 ^ 0 \bmod 12 = 1 \bmod 12 = 1$$

$$ 2^1 \bmod 12 = 2 \bmod 12 = 2 $$

$$ 2 ^ 2 \bmod 12 = 4 \bmod 12 = 4 $$

$$ 2 ^ 3 \bmod 12 = 8 \bmod 12 = 8 $$

$$ 2 ^ 4 \bmod 12 = 16 \bmod 12 = 4 $$

$$ 2 ^ 5 \bmod 12 = 32 \bmod 12 = 8 $$

$$ 2 ^ 6 \bmod 12 = 64 \bmod 12 = 4 $$

$$ 2 ^ 7 \bmod 12 = 128 \bmod 12 = 8 $$

나머지가 1, 2, 4, 8 네 가지 경우만 나온다. 심지어 뒤쪽에서는 4와 8만 반복된다. 따라서 제3자는 4나 8 중에 키를 고르면 암호를 해독할 확률이 굉장히 높아진다.

적당한 \(g\) ?

사실 위 예에서 \(g\)를 2, \(p\)를 11로 선택했을 때 모든 나머지가 나오는 이유는 2가 11에 대해 적당했기 때문이다.

이렇게 \(g ^ n\)을 \(p\)로 나눴을 때의 나머지가 1부터 \(p - 1\)까지 모든 경우를 갖게 하는 \(g\)를 primitive root modular p라 부르는데 자세한 사항은 중학교 수준을 벗어나기 때문에 넘어가도록 하자. 좀 더 상세한 내용은 여기를 참고하기 바란다.

\(g\)에 대한 내용을 건너뛰면 어떻게 적용하나 싶겠지만, 디피-헬만 키 교환을 사용할 때는 대부분 직접 \(p\)와 \(g\)를 계산하지는 않는다. 대신 잘 정해둔 후보들 중 하나를 골라서 사용한다. 어차피 \(p\)와 \(g\)는 제3자에게도 공개되는 값이고, 굉장히 큰 소수를 구하는 작업에 비용이 많이 들 뿐만 아니라 \(g\)를 잘못 고르면 보안성에 심각한 위협이 생기기 때문이다.

사전 정의된 값들은 아래 예에서 확인할 수 있다.

• RFC2539 Storage of Diffie-Hellman Keys in the Domain Name System (DNS)
• RFC3526 More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE)
• RFC5114 Additional Diffie-Hellman Groups for Use with IETF Standards

취약점

디피-헬만 키 교환은 중간자(MITM, Man-In-The-Middle) 공격에 취약하다. 공격자가 Alice와 Bob 사이에서, Alice에게는 Bob인 척, Bob에게는 Alice인 척 하는 공격이다.

이렇게 되면 Alice와 Middle 사이에는 \(a\)와 \(m\)을 이용해 계산한 키 \(k _ {AM}\)이 공유되고, Bob과 Middle 사이에는 \(b\)와 \(m\)을 이용해 계산한 키 \(k _ {BM}\)이 공유된다.

Alice는 Middle에게—Middle이 Bob이라 생각하며— \(k _ {AM}\)을 이용해 암호화한 정보를 보내고, Middle은 이 정보를 모두 해독해 볼 수 있게 된다. 이후 해독한 원문을 다시 \(k _ {BM}\)을 이용해 암호화한 후 Bob에게 보내주기만 하면 감쪽같이 Alice와 Bob을 속일 수 있다.

검열이 불가능한 메신저로 인기를 끈 텔레그램은 보안 채팅을 위해 디피-헬만 키 교환 방식을 사용하는데, 보안 채팅을 한다고 하더라도 암호화된 메시지들이 텔레그램 서버를 경유해 상대방에게 전달되기 때문에 텔레그램 서버에서 중간자 공격이 가능하다. 그래서 텔레그램은 자신들이 결백함을 증명하기 위해 Alice와 Bob이 서로 같은 키를 사용하고 있는지 비교해 볼 수 있는 수단을 마련했다. 중간에서 메시지를 모두 지켜보고 있다면 Alice와 Bob이 사용하고 있는 키 \(k _ {AM}\)과 \(k _ {BM}\)이 달라지기 때문에 여기에서 설명하고 있는 것처럼 각자의 키를 기반으로 그림(picture)을 만들어 줄테니 서로 비교해 보라는 것이다. Alice와 Bob이 직접 만나서 서로의 그림을 펼쳐두고 확인하지 않는 한 완벽한 방식이 아님은 확실하다.