[암호학] 4. 타원곡선암호

RSA와 ElGamal 암호는 여러 단점들이 존재했고, 시간이 지날수록 컴퓨터의 계산 성능이 좋아지고 암호 체계를 깨는 알고리즘이 만들어졌습니다. 그러한 알고리즘에 의해 암호가 공격자에게 노출될 가능성이 커졌고, 그런 공격으로부터 안전성을 확보하기 위해서 암호문의 길이를 늘리거나 RSA에 패딩을 도입한 RSA-OAEP 등과 같이 복잡한 계산 과정이 더해졌습니다. 따라서 암호화 연산에 시간이 더 걸리게 되었고, 키 길이 또한 길어졌습니다.
따라서 기존 암호화 방식의 대안의 필요성이 부각되었습니다.

1985년, RSA 암호의 대안으로 고안된 타원곡선암호(Elliptic Curve Cryptography, ECC)는 짧은 키 길이와 빠른 연산, 동일한 보안 강도를 제공합니다. 타원곡선암호라는 개념은 이전에 없던 새로운 문제를 암호학에 도입한 결과 나오게 된 것은 아니고, DLP 문제를 타원곡선 상에서 풀 때 더 어렵다는 점을 이용해 만들어진 것입니다.

이번 글에서는 타원 곡선과 그것을 이용한 암호 시스템에 대해 알아보겠습니다.

타원곡선

타원곡선은 3차 곡선의 일반형인 $Ax^3 + Bx^2y + Cxy^2 + Dy^3 + Ex^2 + Fxy + Gy^2 + Hx + Iy + J = 0$ 에서 바이어슈트라스 방정식인 $y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_5$ 형태를 가지는 곡선을 말합니다. 체의 표수 $p$가 2와 3이 아닐 때 $y^2 = x^3 + Ax + B$ 형태를 가지게 되는데, 이를 바이어슈트라스 표준형이라고 합니다. 타원곡선을 암호학에서 사용할 때 $x^3 + Ax + B$는 중근을 갖지 않아야 한다는 제약조건도 있습니다 ($4a^3 + 27b^2 \ne 0$). 만약 중근을 가진다면 특이점(singular point)를 갖게 되는데, 이러한 특이점에서는 덧셈과 곱셈이 정해지지 않아, 타원곡선 위의 점들을 다른 체로 변환할 수 있는 가능성이 있어 타원곡선 위에서 문제를 푸는 것보다 훨씬 쉬운 문제로 바뀌게 될 수 있습니다.

어떤 환 $R$에 대해 $R$의 임의의 원소 $a$에 대해 $m \cdot a = 0$ 인 자연수 $m$ 중 가장 작은 자연수 $n$을 환 $R$의 표수(characteristic)라고 정의합니다.
한 예로, 모듈러 연산에 대해 정의된 $\mathbb{Z}_n$의 모든 원소에 $n$을 곱하면 $n$에 대해 나머지가 0이 될 것입니다. 따라서 모든 환 $\mathbb{Z}_n$의 표수는 $n$입니다. 또한 단위원 1을 가진 환에 대해서는 $n \cdot 1 = 0$을 만족하기만 하면 $n$을 표수로 볼 수 있습니다.

왜 타원암호에서 타원곡선의 표수는 2와 3을 제외할까요?
표수가 2와 3이 될 수 없는 것에는 식의 복잡함을 줄이려는 의도가 포함되어 있음과 동시에 암호학적으로 표수 2와 3에 대해서 유의미한 공격법 (Weil descent attack)이 존재한다는 점이 이유가 됩니다. 현재 $\mathbb{F}_{2^n}$ 위의 타원곡선의 DLP에 대하여 준지수시간 알고리즘이 나올 것으로 예측하고 있습니다.
유한체의 위수는 그 유한집합의 원소의 개수를 의미합니다. 따라서 표수 $p$의 후보 중 2와 3을 제외하겠다는 말은 위수 $2^n$ 또는 $3^n$을 가지는 체를 제외하겠다는 말과 같습니다.
만약 최소 표수를 5로 둔다면, 모든 타원곡선 식을 바이어슈트라스 표준형으로 표현할 수 있으며 알려진 확실한 공격법 또한 존재하지 않습니다.

타원곡선의 형태는 위 그림과 같습니다. 타원과는 크게 연관이 없어보이는 형태인데, 타원곡선의 방정식이 타원의 둘레를 구하는 적분 과정에서 유래한 식으로 만들어졌기 때문에 타원곡선이라는 이름이 붙었습니다.

타원곡선의 성질

먼저 일반적인 실수체에서의 타원곡선에서 타원곡선의 성질에 대해 알아보겠습니다. 먼저 무한원점이라는 특수한 개념을 추가해야 합니다. 무한원점은 $\mathcal{O}$로 표기하며 $y$좌표가 $\infty$인 점입니다.

타원곡선에서 점의 덧셈은 새롭게 정의됩니다. 타원곡선 위 두 점의 덧셈을 기하학적으로 살펴보겠습니다. 타원곡선에서 점의 덧셈은 점을 직선으로 이었을 때 나오는 모양에 따라 정의됩니다.
타원곡선을 지나는 모든 직선의 타원곡선과의 교점을 모두 더하면 $\mathcal{O}$이 됩니다. 타원곡선 위의 두 점 $P$과 $Q$를 잇는 직선이 보여주는 모양은 다음과 같은 4가지 경우로 정리할 수 있습니다.

점 $P$와 $Q$를 더하면 $-R$이 된다는 것을 1번 그림에서 알 수 있습니다. $-R$은 $R$을 $(x, y)$이라는 점으로 보았을 때 $(x, -y)$로 정의됩니다.

$P_3 = P_1 + P_2$를 나타낸 그림입니다. 타원곡선에서 두 점의 덧셈은 다음과 같은 과정으로 진행됩니다.
1. 더하려고 하는 점 $P_1$, $P_2$를 잇는 직선을 그립니다.
2. 그 직선이 타원과 만나는 또 다른 점을 $P'$이라고 합니다.
3. $P'$를 $x$축에 대해 대칭이동 시킨 다른 점이 $P_3 = P_1 + P_2 = -P'$가 됩니다.

직관적이지 않은 연산이지만 이렇게 복잡하게 더하기 연산을 정하면 다음과 같은 성질을 가지게 됩니다.

• 덧셈에 대해 닫힘
  점 $P$와 $Q$가 타원곡선 위에 있을 때, $P + Q$ 또한 타원곡선 위에 있습니다.
• 항등원의 존재
  타원곡선 위의 임의의 점 $P$에 대해 $P + \mathcal{O} = P$ 가 성립합니다.
• 덧셈의 교환법칙, 결합법칙
  타원곡선 위의 임의의 점 $P, Q, R$에 대해 $P+(Q+R)=(P+Q)+R$ 이 성립하고,
  타원곡선 위의 임의의 점 $P, Q$에 대해 $P+Q=Q+P$ 이 성립합니다.
• 역원의 존재
  모든 점 $P$에 대해 $-P$가 존재하고 $P + (-P) = \mathcal{O}$ 이 성립합니다.

이 특성들을 기억하신다면 이러한 성질들을 가지는 이항연산구조를 가환군으로 정의했던 것을 떠올릴 수 있을 것입니다. 덧셈을 정의했으니 스칼라 곱셈 또한 정의할 수 있습니다.

타원곡선 위의 로그

점 $Q$가 타원곡선 위의 점일 때, $Q = nP$ 를 만족하는 점 $P$가 있다고 하겠습니다. 여기서 $n$의 값을 구하는 문제는 앞서 살펴보았던 이산로그문제와 비슷한 형태를 가지고 있고(정확히는 이 문제는 로그문제에 속합니다), 이를 통해 타원곡선암호를 정의할 수 있게 됩니다. 하지만 실수체 위에서의 연산은 매우 복잡해 오랜 시간이 걸리면서도 부동소수점 연산이 있을 경우 오류가 발생할 가능성이 커 실제 암호로서의 사용 가능성이 떨어집니다.

유한체 $\mathbb{F}_p$ 위의 타원곡선

앞서 정의했던 타원곡선 식에서 $x$와 $y$를 정수로 한정짓고, $N$으로 나눈 나머지에 대해서 합동방정식 $E: y^2 \equiv x^3 + Ax + B\pmod{N}$의 해 집합 $E(N)$을 생각해봅시다. 이 때 $E(N)$은 다음과 같은 집합으로 볼 수 있습니다.

이러한 유한체 위의 타원곡선은 여전히 가환군으로서 덧셈, 곱셈, 나눗셈까지 모두 정의 되어있습니다.

EC-DLP

타원곡선의 이산로그문제, EC-DLP는 유한체 $\mathbb{F}_p$ 위의 타원곡선에 대해 다음과 같이 정의됩니다.

$P, Q \in E(p)$일 때, $Q = [d]P$에서 $d$의 값을 찾는 것

유한체 타원곡선 점의 덧셈

유한체 위에서 점의 덧셈도 앞서 정의한 덧셈과 같은 방식입니다. 실제로 점의 좌표를 구하기 위해서는 대수 연산이 필요합니다.

$\mathbb{F}_p$ 의 타원곡선 $y^2 \equiv x^3 + Ax + B \pmod{p}$ 위의 점 $P = (x_P, y_P), Q = (x_Q, y_Q)$ 가 있을 때, $P + Q + R = \mathcal{O}$ 를 만족하는 점 $R = (x_R, y_R)$ 은 다음과 같은 식을 통해 구할 수 있습니다.

$\begin{aligned} x_R & = (m^2 - x_P - x_Q) \bmod{p} \\ y_R & = [y_P + m(x_R - x_P)] \bmod{p} \\ & = [y_Q + m(x_R - x_Q)] \bmod{p} \end{aligned}$

기울기 $m$은 다음과 같습니다.

$\begin{aligned} m &= \cfrac{y_P - y_Q}{x_P - x_Q} \bmod{p}\ (P \ne Q)\\ m &= \cfrac{3 x_P^2 + A}{2 y_P} \bmod{p}\ (P = Q) \end{aligned}$

타원곡선의 도메인 파라미터

점의 덧셈이 어떤 방식으로 진행되는지를 살펴보았습니다. 타원곡선을 실제 암호에 활용하기 위해서는 연산을 하는 집합을 잘 정의해야 합니다. 이러한 집합을 정의하는 변수들을 도메인 파라미터라고 합니다. 도메인 파라미터에는 어떤 값들이 있고 이 값들이 어떻게 집합을 정의하는지 알아보겠습니다.

점의 개수와 순환 부분군

실제로 얼마나 많은 점들이 집합에 있는지는 위수로 나타냅니다. 타원곡선의 위수는 Schoof's algorithm을 통해 구할 수 있습니다.
타원곡선 암호에서는 어떤 하나의 점을 기준으로 새롭게 집합을 정의합니다. 하나의 예시를 보겠습니다.
$y^2 = x^3 + 2x + 3 \pmod{97}$ 이라는 타원곡선과 $P = (3, 6)$ 이라는 타원곡선 위의 점이 있다고 하겠습니다. 여기서 $P$의 곱셈을 계산하면 다음과 같습니다.

• $0P = \mathcal{O}$
• $1P = (3, 6)$
• $2P = (80, 10)$
• $3P = (80, 87)$
• $4P = (3, 91)$
• $5P = \mathcal{O}$
• $6P = (3, 6)$
• $\cdots$

여기서 총 5개의 점밖에 존재하지 않는다는 것을 알 수 있습니다. 아래의 그림을 보면 이해가 더 쉬울 것입니다.

이렇게 이 타원곡선의 점의 집합은 원래의 유한체에서 부분군을 이룬다는 것을 알 수 있습니다. 그리고 그 부분군은 생성원을 가지는 순환군이 됩니다. 생성원(Generator)은 위의 경우 점 $P$ 가 됩니다. 부분군의 원소의 개수는 라그랑주 정리를 통해 원래의 군의 원소의 개수의 약수라는 점이 알려져 있습니다. 그 때 원래 타원곡선의 위수를 $N$, 부분군의 위수를 $n$ 이라고 했을 때 $h = \frac{N}{n}$ 이 항상 정수라는 것을 알 수 있습니다. 새롭게 정의한 $h$ 를 보조인자(cofactor)라고 부릅니다. 지금까지 순환 부분군을 위해 도입한 변수들을 정리해보겠습니다.

• 유한체 $\mathbb{F}_p$의 $p$
• $y^2 \equiv x^3 + Ax + B \pmod{p}$의 $A$, $B$
• 생성원 $P$ (이제부터 $G$로 부르겠습니다)
• 부분군의 위수 $n = \text{ord}(G)$
• 부분인자 $h$

이 6가지 변수들을 도메인 파라미터라고 부릅니다.

$p$, $A$, $B$는 직접 정해주면 된다는 것을 쉽게 알 수 있지만 $G$, $n$, $h$는 어떻게 구해야 할까요?
이 세 변수를 정하기 위해서는 먼저 충분히 큰 위수 $n$을 정하고 적절한 $G$를 찾습니다. $n$을 정한다는 말은 $h$ 또한 정한다는 말과 같습니다.
타원곡선의 모든 점 $P$에 대해 $NP = \mathcal{O}$ 입니다. $N$은 모든 $n$ 이 될 수 있는 수의 곱이기 때문입니다. 위에서 정의한 보조인자의 정의를 사용하면 다음과 같이 쓸 수 있습니다.

$\begin{aligned} NP = n(hP) = \mathcal{O} \end{aligned}$

$n$이 소수라고 하면 $G = hP$ 인 점 $G$는 위수 $n$의 부분군을 생성한다는 것을 알 수 있습니다.

도메인 파라미터를 정하는 과정을 정리하면 다음과 같습니다.

1. Schoof의 알고리즘을 통해 타원곡선의 위수 $N$을 구합니다.
2. 부분군의 $n$을 정합니다. ($N$의 약수면서 소수여야 합니다)
3. $h = \frac{N}{n}$을 구합니다.
4. 타원곡선 위 무작위 점 $P$를 정합니다.
5. $G = hP$를 계산합니다.
6. 만약 $G$가 $\mathcal{O}$라면, 4번 과정으로 돌아가 다시 무작위 점을 정합니다.

실제 암호로 쓰기 위해 타원곡선을 선택할 때는 NIST(미국 국립표준연구소)에서 표준으로 제정한 타원곡선을 쓰거나 secp256k1(비트코인이 사용하는 타원곡선) 등 이미 검증된 타원곡선을 쓰기를 권장하고 있습니다.

ECDH

타원곡선을 활용한 타원곡선 위의 디피-헬만 알고리즘(ECDH, Elliptic Curve Diffie-Hellman)에 대해 알아보겠습니다.
디피-헬만 알고리즘은 송신자와 수신자가 각각 임의의 정수를 선택하고 생성원에 지수 연산을 해 서로만 아는 값을 복호화에 사용하는 알고리즘이었습니다. 타원곡선 위에서도 동일한 과정이 됩니다.

앨리스와 밥은 서로 동일한 타원곡선과 생성원 $G$, 생성원의 위수 $\text{ord}(G) = n$을 알고 있다고 가정합니다.

1. 앨리스와 밥은 각각 $1 \le \alpha \le n - 1$ 를 만족하는 $\alpha$, $1 \le \beta \le n - 1$ 를 만족하는 $\beta$를 선택합니다.
2. 앨리스와 밥은 각각 $A = \alpha G$, $B = \beta G$ 를 계산해서 공개합니다. 이 두 값이 각각 앨리스의 공개키, 밥의 공개키가 됩니다.
3. 앨리스와 밥은 자신의 개인키와 상대의 공개키를 이용해 복호화 함수에 쓰이는 $K = \alpha\beta G$를 구할 수 있습니다.

EC-ElGamal

타원곡선 위의 ElGamal도 비슷한 과정을 통해 구현됩니다.

앨리스와 밥은 서로 동일한 타원곡선과 생성원 $G$, 생성원의 위수 $\text{ord}(G) = n$을 알고 있다고 가정합니다. 앨리스가 밥에게 평문 $M$을 암호화해서 보내는 과정입니다.

1. 앨리스와 밥은 각각 $1 \le \alpha \le n - 1$ 를 만족하는 $\alpha$, $1 \le \beta \le n - 1$ 를 만족하는 $\beta$를 선택합니다.
2. 앨리스와 밥은 각각 $A = \alpha G$, $B = \beta G$ 를 계산해서 공개합니다. 이 두 값이 각각 앨리스의 공개키, 밥의 공개키가 됩니다.
3. 앨리스는 무작위 정수 $k$를 선택하고 $kG$, $M + kB$ 를 계산해 밥에게 보냅니다.
4. 밥은 $(M + kB) - \beta(kG) = (M + k(\beta G)) - \beta(kG) = M$ 을 통해 $M$을 얻을 수 있습니다.

여기까지 현재 많이 쓰이고 있는 공개키 암호 시스템을 알아보았습니다. 다음으로는 해시 함수, 디지털 서명에 대해 다루겠습니다.