디피–헬먼 키 교환(Diffie–Hellman key exchange)

한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통로로만 이야기해서 같은 비밀 열쇠를 가질 수 있을까요? 공개된 소수⁠(prime number)⁠ $p =$ , 밑 $g =$ (가장 작은 원시근⁠(primitive root)⁠)에서 시작합니다. 두 사람은 각자 비밀 수를 하나씩 고릅니다. 앨리스는 $a =$ , 밥은 $b =$ 입니다.

각자 $g$를 제 비밀 수만큼 거듭제곱해 p로 나눈 나머지⁠(remainder)⁠를 공개하고, 받은 수를 다시 제 비밀 수만큼 거듭제곱합니다. $(g^b)^a = g^{ab} = (g^a)^b$이니 두 사람의 결과는 같습니다. 도청자는 $p, g, A, B$를 모두 보았습니다. 하지만 $a$나 $b$를 모른 채 $A, B$만으로 $g^{ab}$를 만드는 빠른 방법은 알려져 있지 않습니다. 불가능하다고 증명된 것은 아니고, 수십 년의 공격을 버텨 온 믿음입니다. 1976년 미국의 암호학자 휫필드 디피와 마틴 헬먼이 이 방법을 발표했습니다. 그전까지 암호를 쓰려면 두 사람이 만나거나 믿을 만한 전달자를 통해 미리 열쇠를 나눠 가져야 했습니다. 이 방법은 열쇠를 미리 나누지 않고 공개된 정보만으로 암호를 쓰는 공개키 암호⁠(public-key cryptography)⁠의 문을 열었고, 이듬해 RSA 암호⁠(RSA cryptosystem)⁠가 뒤따랐습니다.

그림은 의 값을 모든 $k$에 대해 찍은 것입니다. 곱셈을 고르면 점들이 가지런한 줄무늬를 이루고, 높이 A에서 $a$를 되찾는 것은 $g$의 역수⁠(inverse)⁠를 한 번 곱하는 일입니다. 거듭제곱을 고르면 점들이 무작위처럼 흩어집니다.

거듭제곱에서 지수를 되찾는 문제를 이산로그라 합니다. 실수⁠(real number)⁠ 위의 지수함수⁠(exponential function)⁠는 매끄럽게 커지니 로그로 쉽게 되돌리지만, 나머지를 취하는 순간 값이 시계를 여러 바퀴 돌아 흩어집니다. 한편 $g^a$를 계산하는 쪽은 쉽습니다. $g, g^2, g^4, g^8, \dots$을 제곱을 거듭해 만들어 두고 필요한 것만 곱하면 됩니다($g^{13} = g^8 \cdot g^4 \cdot g$). 그러면 지수가 수백 자리여도 곱셈 수천 번이면 끝납니다. 영리한 공격도 있습니다. 생일 문제⁠(birthday problem)⁠에서 23명만 모여도 생일이 겹치기 쉬운 것처럼, 두 목록 사이에서 같은 값(충돌)을 노리면 $p$번이 아니라 약 $\sqrt p$번의 계산으로 로그를 찾을 수 있습니다. 또 $p-1$이 작은 소수들로만 소인수분해⁠(prime factorization)⁠되면 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠로 문제를 작은 소수마다의 쉬운 문제로 쪼갤 수 있습니다. 그래서 실제로는 수백 자리의 $p$를, $p-1$이 큰 소인수를 갖도록 고릅니다.

이어지는 곳. 페르마 소정리⁠(Fermat's little theorem)⁠ $g^{p-1} \equiv 1$ 때문에 $g^k$의 주기⁠(period)⁠는 언제나 $p-1$의 약수입니다. $g$가 원시근이면 그 주기가 $p-1$ 전체라서, $g^k$가 1부터 $p-1$까지 모든 값을 밟고 열쇠의 후보가 가장 많아집니다. 키 교환만으로는 중간에서 앨리스에게는 밥인 척, 밥에게는 앨리스인 척하는 공격자(중간자 공격⁠, man-in-the-middle attack⁠)를 막지 못합니다. 그래서 실제 통신에서는 RSA 같은 전자서명⁠(digital signature)⁠으로 상대를 확인합니다. 오늘날에는 같은 생각을 타원곡선⁠(elliptic curve)⁠ 위에서 쓰는 방식이 널리 쓰입니다. 타원곡선은 $y^2 = x^3 + ux + v$ 꼴 곡선($u, v$는 곡선을 정하는 상수)이고, 암호에서는 좌표도 소수로 나눈 나머지로 계산합니다. 그 위의 두 점에서 셋째 점을 만드는 "덧셈" 규칙이 있습니다. 거듭제곱 대신 한 점을 거듭 더하고, 몇 번 더했는지 되찾기가 어렵다는 데 기댑니다. 같은 안전도를 훨씬 짧은 열쇠로 얻을 수 있습니다. 곱셈이 원 위의 화살표가 되는 그림은 원 위의 곱셈표⁠(times tables on a circle)⁠에서 볼 수 있습니다.