타원 곡선 디피-헬먼 키 교환

개요

디피-헬먼 키 교환은 두 사람 사이에 사용될 공통의 암호 키를 암호화되지 않은 통신망을 통해 안전하게 공유할 수 있게 하는 방식이다.

기존의 디피-헬먼 키 교환은 모듈러 지수 연산을 이용해 이루어진다.

하지만 타원 곡선 디피-헬먼 키 교환은 타원 곡선 암호를 이용하기 때문에 키의 크기가 더 작아 속도가 빠르면서 기존과 동일한 수준의 보안을 달성할 수 있다고 한다.

타원 곡선 암호 간단한 설명

철수와 영희는 공통의 암호 키를 갖기 위해 타원 곡선 디피-헬먼 키 교환을 하고자 한다.

그러기 위해서는 이 둘은 각각 타원곡선 위의 생성점 $G$에 대해 $P = eG$를 만족하는 자신의 개인 키($e$)와 공개 키($P$)를 갖고 있어야 한다.

$P = eG$
$P: 공개\;키\;(공개)$
$e: 비밀\;키\;(비공개)$
$G: 타원곡선\;위의\;생성점\;(공개)$

위 식이 타원 곡선 암호의 전부는 아니지만 $P = eG$는 타원 곡선 이산 대수 문제이기 때문에 $P$와 $G$를 이용해 $e$를 구하는 빠른 방법이 없어서 공격자는 무작위적인 계산을 시도하는 수 밖에 없다는 사실만 알면 된다.

$e$가 $n$비트인 경우에는 최대 $2^n$번의 무작위적 연산을 수행해야 하며 보통 랜덤한 값과 해시 함수를 이용해 생성한 256비트 값을 사용하기 때문에 공격자는 최악의 경우에 $2^{256} ≒ 10^{77}$번의 연산을 수행해야 한다.

이를 통해 공격자가 연산을 통해 비밀 키를 얻을 수 없음을 알 수 있다.

참고로 재밌는 사실을 하나 알게 되었는데 우주에 존재하는 원자의 수가 총 $10^{80}$개라고 한다.

그러니 $10^{77}$은 실로 엄청난 숫자인 것이다.

키 교환 방법

철수는 공개 키 $P_A$와 비밀 키 $e_A$를 가지고 있으며 영희는 공개 키 $P_B$와 비밀 키 $e_B$를 가지고 있다.

키 교환을 위해서 철수는 자신의 공개 키를 안전하지 않은 통신망을 통해 영희에게 전송한다.

마찬가지로 영희는 철수에게 자신의 공개 키를 전송한다.

철수는 자신의 비밀 키와 영희의 공개 키를 곱하고 영희는 자신의 비밀 키와 철수의 공개 키를 곱함으로써 공통의 비밀 키(대칭 키)를 얻을 수 있다.

$대칭\;키_철 = e_A·P_B$
$대칭\;키_영 = e_B·P_A$
$대칭\;키_철 = 대칭\;키_영$

그런데 철수와 영희가 각각 생성한 대칭 키가 어째서 같을까?

앞서 본 $P = eG$라는 식을 이용하면 두 대칭 키가 같음을 증명할 수 있다.

$∴ e_A·P_B = e_A·(e_B·G) = e_B·(e_A·G) = e_B·P_A$

철수와 영희는 자신의 공개 키만을 통신망에 전송하기 때문에 공격자가 정보를 가로챈다 해도 비밀 키를 알 수 없어 공통의 비밀 키 역시 알 수 없다.

마치며

타원 곡선 암호를 이용한 프로그램을 만들고 있는데 여기서 통신을 할 때 보안과 데이터 무결성을 위해 종단간 암호화를 도입하려 했다.

처음에는 RSA와 AES를 사용하면 되겠거니 생각했었다.

이후 타원 곡선 암호를 복습하는 과정에서 타원 곡선 디피-헬먼 키 교환에 대해 알게되었고 프로그램을 한층 더 고도화시킬 수 있게 되었다.

ECDH의 존재를 알게 되었을 때 오랜만에 짜릿함을 느꼈다.