기존 RSA나 Diffie-Hallman과 같은 공개키 시스템은 이산 로그 문제의 어려움을 바탕으로 공개적으로 비밀을 생성해냈다. 하지만 이 방법은 큰 수에 대한 연산이나 기약 다항식 위에서의 연산 등, 저장과 처리에 큰 부하가 있다.
타원 곡선 암호(ECC)는 기존 공개키 시스템과 동일한 매커니즘을 타원 곡선 위의 연산으로 옮겨 더 작은 크기의 bit로 비밀을 생성할 수 있다. 즉, 같은 수준의 보안을 더 적은 bit로 달성할 수 있다.
Real Elliptic Curve (실수체 위의 타원 곡선)
타원 곡선의 정의
타원 곡선은 다음과 같이 정의할 수 있다.
$$
y^2 = x^3 + ax + b
$$
이때 $a$와 $b$에 따라 타원 곡선의 모양이 달라진다. 예를 들어 아래 1번 곡선은 $a=-1, b=0$일 때의 타원 곡선이고, 2번 곡선은 $a=-1, b=1$일 때의 타원 곡선이다.
여기서 실수 체라는 것은, 각 숫자의 덧셈과 곱셈 연산이 실수에 대한 연산이라는 것이다. 다시 말해 우리가 일반적으로 생각하는 곱셈과 덧셈을 사용한다.
타원 곡선 상의 두 점의 덧셈
Elliptic curve에는 각 숫자에 대한 연산 뿐만아니라, 두 점간의 덧셈도 가능하다. 두 점간의 덧셈은 다음과 같이 정의한다.
두 점을 지나는 직선이 타원 곡선과 만나는 점을 x축 대칭시킨 점이 두 점의 덧셈 연산 결과 점이다.
$P_3 = P_1 + P_2$를 그림으로 표현하면 아래와 같다.
우선 $P_1$과 $P_2$를 지나는 직선과 타원 곡선이 만나는 점($P'$)을 구한다. 이를 $x$축 대칭 시킨 결과가 $P_3$가 된다.
두 점의 덧셈 연산 결과는 공식화할 수 있다. 두 점을 각각 $(x_1, y_1), (x_2, y_2)$라고 하고, 덧셈 결과를 $(x_3, y_3)$라고 하자.
$x$ 좌표.
이때 $x_3$는 두 점을 잇는 직선의 기울기($\frac{y_2 - y_1}{x_2 - x_1}$)를 제곱한 값에 두 점의 $x$좌표 ($x_1$, $x_2$)를 각각 빼주면 된다.
$$
x_3 = (\frac{y_2 - y_1}{x_2 - x_1})^2 - x_1 - x_2
$$
$y$ 좌표.
$P_3$의 y좌표는 $P'$의 y좌표에 마이너스를 붙여 구할 수 있다. $P_3$와 $P'$의 x좌표는 동일하므로 $P'$의 x좌표 또한 $x_3$이다.
$P'$의 y좌표를 $-y_3$라고 하자. 이를 구해 마이너스를 붙이면 $y_3$를 구할 수 있다. $-y_3$는 결국 $y_1$에 삼각형의 높이를 곱해주면 된다. 이 높이는 결국 $x_1$, $x_2$를 잇는 직선의 기울기에 밑변을 곱한 값이다. 여기서 밑변은 $x_3 - x_1$이 된다.
$$
-y_3 = y_1 + (\frac{y_2 - y_1}{x_2 - x_1}) \times (x_3 - x_1)
$$
따라서 $y_3$는 양변에 음수를 취해 구할 수 있다.
$$
y_3 = -y_1 + (\frac{y_2 - y_1}{x_2 - x_1}) \times (x_1 - x_3)
$$
두 점이 동일한 경우.
앞서 살펴본 경우는 모두 두 점이 서로 다를 경우이다. 만약 두 점이 서로 같다면 기울기로 사용하던 $\frac{y_2 - y_1}{x_2 - x_1}$를 접선의 기울기로 바꿔 사용해야 한다. $y^2 = x^3 + ax + b$ 곡선에서 $x = x_1$일 때의 접선의 기울기는 다음과 같이 구한다.
- 양 변에 $\frac{d}{dx}$를 적용한다.
$$
\frac{d}{dx}y^2 = \frac{d}{dx}(x^3 + ax + b)
$$ - 좌변은 연쇄 법칙을 적용한다. 우변은 $x$에 대해 미분한다.
$$
\frac{dx}{dy}\frac{d}{dy}y^2 = 3x^2 + a
$$
$$
\frac{dy}{dx}2y = 3x^2 + a
$$
$$
\frac{dy}{dx} = \frac{3x^2 + a}{2y}
$$
따라서 두 점이 같은 경우 기울기 항은 $\frac{3x^2 + a}{2y}$를 사용한다.
Finite Elliptic Curves (유한 타원 곡선)
이전에 살펴본 타원 곡선은 실수 체 위에서 정의되었다. 일반적으로 사용되는 타원 곡선은 다음 두 가지이다.
- Prime curve
- Binary curve
Prime curve는 연산을 모듈로 p에 대해 수행한다. 여기서 p는 소수이다. Binary curve는 덧셈은 XOR로, 곱셈은 기약 다항식 위에서의 연산으로 수행한다. 따라서 두 곡선 모두 유한한 원소를 갖는다.
Elliptic cuver는 $a$와 $b$가 정해지면 곡선이 정해지기 때문에 $E(a, b)$로 나타낼 수 있다. Prime curve는 여기에 모듈로가 되는 소수를 표현하여 $E_p(a, b)$로 표현할 수 있고, binary curve는 $E_{2^n}(a, b)$로 표현할 수 있다.
Prime curve는 소프트웨어 구현에 특화되어 있고, binary curve는 하드웨어 구현에 특화되어 있다.
Elliptic Curve Cryptography
ECC는 prime curve 위에서의 연산을 바탕으로 암호를 사용하는 암호체계이다.
ECC에서 덧셈은 모듈러 위에서의 곱셈과 같다. 따라서 ECC에서 같은 수를 반복해서 더하는 스칼라 곱셈은 모듈러 위에서의 지수 연산과 같다.
기존 모듈러 위에서의 연산에서 이산 로그 문제는 다음과 같다.
$$
y = a^x \bmod p
$$
- $a$, $x$가 주어졌을 때 $y$를 구하는 것은 쉽다.
- $y$, $a$가 주어졌을 때 $x$를 구하는 것은 어렵다.
앞서 살펴보았듯, ECC에서는 지수 연산이 스칼라 곱에 대응된다. 따라서 타원 곡선 이산 로그 문제는 다음과 같다.
$$
Q = kP
$$
- $k$, $P$를 통해 $Q$를 구하는 것은 쉽다.
- $Q$, $P$를 통해 $k$를 구하는 것은 어렵다.
ECC Diffie-Hellman
기존 디피-헬만 키 교환 알고리즘은 이산 로그 문제에 기반했다. 이산 로그 문제는 타원곡선 상에서도 타원곡선 이산 로그 문제로 유효하기 때문에, 이를 타원곡선 버전으로 변형할 수 있다.
서로 합의해야하는 파라미터는 어떤 곡선을 사용할지와 어떤 점을 시작점으로 잡을지이다. 이때 시작점은 기존의 생성자와 유사한 역할을 한다.
Alice와 Bob은 공개 파라미터인 $E_q(a, b)$와 $G = (x_1, y_1)$을 합의한다. 이때 $n$은 $nG = O$가 되는 수이다.
이후 Alice와 Bob은 각자 비밀 값인 $n_a$, $n_b$를 생성한다. 이때 각 비밀은 $n$보다 작아야 한다.
Alice와 Bob은 서로에게 $G$를 자신의 비밀번 곱한 수를 전달한다. 즉, Alice는 Bob에게 $n_aG$를 전달하고, Bob은 Alice에게 $n_bG$를 전달한다.
전달 과정에서 공개적인 채널을 이용하더라도 Alice와 Bob의 비밀인 $n_a$, $n_b$는 드러나지 않는다. 타원 곡선 이산 로그 문제가 어렵기 때문이다.
Alice와 Bob은 상대방으로부터 받은 값을 자신의 비밀번 더한다. 즉, Alice는 $n_bG$를 $n_a$번 더하고, Bob은 $n_aG$를 $n_b$번 더한다. 그 결과, Alice는 $n_an_bG$를 얻게 되고, Bob은 $n_bn_aG$를 얻게 된다. 서로 같은 값에 도달하게 된다.
ECC Encryption/Decryption
ECC Diffie-Hallman이 가능하므로, Diffie-Hallman을 활용한 공개키 암호화 기법인 ElGamal도 ECC로 가능하다.
수신할 사람은 자신의 공개키를 생성해 공개해야한다. 이때 공개해야할 정보는 어떤 곡선을 사용하는지($E_p(a, b)$), 시작점이 어디인지($G$), 송신자가 사용할 수신자의 공개키는 무엇인지($n_aG$)이다.
송신자는 자신의 일회용 비밀 값인 $k$를 정한다. 물론 $k$는 $n$보다 작아야 한다. 사용자의 공개 키($n_aG$)를 $k$번 더한 것이 이 세션에 사용되는 키이다($n_akG$). 이를 사용해 암호화를 수행한다.
암호화를 하려면 우선 메시지를 타원곡선 상에 인코딩해야 한다. 인코딩된 메시지를 $P_m$이라고 한다면 $P_m + n_akG$로 암호화를 수행할 수 있다.
송신자는 수신자가 메시지를 받아서 수신자의 개인 키로 세션 키를 생성할 수 있도록 자신의 개인 키가 담긴 $kG$를 같이 보낸다. 이를 받은 수신자는 $kG$를 $n_a$번 더하여 $n_akG$를 만들어낼 수 있다. 이 세션 키를 암호화된 메시지에서 빼주어 원본 메시지 $P_m$을 구한다.