Elliptic Curve Diffie-Hellman Algorithm (ECDH Algorithm)
타원 곡선 디피-헬만 알고리즘
- 타원 곡선의 성질을 이용하여 키를 분배하거나 전자서명을 생성한다.
Mechanism (원리)
- 타원 곡선을 이용한 암호화 방식의 메커니즘은 아래와 같다.
Elliptic Curve \(E : y^2 = x^3 + ax + b \; (\mathrm{mod} \; p)\)
1. 타원 위를 지나는 점 \(P_1=(x_1, y_1), P_2=(x_2, y_2)\) 를 구한다.
2. \(P_3 = P_1 + P_2 = (x_3, y_3)\) 를 구한다.
이 때, 타원 위의 점들의 합은 아래와 같이 계산된다.
\(x_3 = m^2 - x_1 - x_2 \; (\mathrm{mod} \; p)\\ y_3 = m(x_1 - x_3) - y_1 \; (\mathrm{mod} \; p)\)
\(m = \begin{cases} {y_2 - y_1 \over x_2 - x_1} \; \mathrm{mod} \; p, \qquad \; \mathrm{if} \; P_1 \neq P_2\\\\ {3x_1^2 + a \over 2y_1} \; \mathrm{mod} \; p, \qquad \; \mathrm{if} \; P_1 = P_2 \end{cases}\)
3. 타원 위 점들을 위와같이 계속 더하여 좌표 간 중복 곱셈 연산을 수행하여 암호를 만든다.
* 타원 곡선에서의 덧셈
\(P_3 = P_1 + P_2\)
\(P_1\)과 \(P_2\)를 잇는 직선이 타원 곡선과 만나는 점을 \(x\)축 대칭시킨 점이 덧셈의 결과이다.
Example. Elliptic Curve Addition (타원 곡선에서의 덧셈)
\(E: y^2 = x^3 + 2x + 3 \; (\mathrm{mod} \; 5)\)
\((a = 2, b = 3)\)
| \(x\) | \(y^2\) | \(y\) |
| \(0\) | \(3 = 3 \; (\mathrm{mod} \; 5)\) | \(\mathrm{No \; Solution}\) |
| \(1\) | \(6 = 1 \; (\mathrm{mod} \; 5)\) | \(1, 4\) |
| \(2\) | \(15 = 0 \; (\mathrm{mod} \; 5)\) | \(0\) |
| \(3\) | \(36 = 1 \; (\mathrm{mod} \; 5)\) | \(1, 4\) |
| \(4\) | \(75 = 0 \; (\mathrm{mod} \; 5)\) | \(0\) |
구한 점들은 아래와 같다.
\((1, 1), (1, 4), (2, 0), (3, 1), (3, 4), (4, 0)\)
\((1, 4)\) 와 \((3, 1)\)을 더해보자.
\(P_1 = (1, 4)\\ P_2 = (3, 1)\)
\(m = {1 - 4 \over 3 - 1} = -1.5 \; (\mathrm{mod} \; 5) = 3.5\)
\(x_3 = 1.5^2 - 1 - 3 \; (\mathrm{mod} \; 5) = 3.25\)
\(y_3 = 1.5(1 - 3.25) - 4 \; (\mathrm{mod} \; 5) = 2.625\)
\(\therefore P_1 + P_2 = (1, 4) + (3, 1) = (3.25, 2.625)\)
Elliptic Curve Key Exchange Algorithm (ECDHE; 타원곡선 키 교환 알고리즘)
Public Curve: \(y^2 = x^3 + 7x + b \; (\mathrm{mod} \; 37)\)
Point: \((2, 5)\)
주어진 점\((2, 5)\)을 통해 \(b\)값을 구한다.
\(b = 3\)
\(A\)'s Private Key = \(d_A = 4\)
\(B\)'s Private Key = \(d_B = 7\)
\(A \to B\) : \(4*(2, 5) = (7, 32)\) (타원 덧셈)
\(B \to A\) : \(7*(2, 5) = (18, 35)\) (타원 덧셈)
\(A\) Computes: \(4*(18, 35) = (22, 1)\)
\(B\) Computes: \(7*(7, 32) = (22, 1)\)
\(A\)와 \(B\)에게 같은 키 \((22, 1)\)가 분배되었다.
Elliptic Curve Digital Signature Algorithm (ECDSA; 타원곡선 전자서명 알고리즘)
[Sign Process: Sender-Side]
| Legend | Description |
| \(m\) | 보내고자하는 메시지 |
| \(z = h(m)\) \(h\) : Hash Function |
m에 대한 해시값 |
| \(k\) | Random Number |
| \(G\) | Elliptic Curve Base Point (공개된 타원곡선위의 한 점) |
| \((x_1, y_1) = k * G\) | G를 k번 타원덧셈한 결과 좌표 |
| \(r = x_1 \; \mathrm{mod} \; n\) | |
| \(s = k^{-1}(z+rd_A) \; \mathrm{mod} \; n\) | |
| \((r, s)\) | Signature |
| \((m, r, s)\) | 전송 대상 (메시지 + 서명) |
[Verification Process: Receiver-Side]
| Legend | Description |
| \(m\) | 수신한 메시지 |
| \(z = h(m)\) \(h\) : Hash Function |
\(m\)에 대한 해시값 |
| \(u_1 = zs^{-1} \; \mathrm{mod} \; n\) | |
| \(u_2 = rs^{-1} \; \mathrm{mod} \; n\) | |
| \((x_1, y_1) = u_1G + u_2Q_A\) (where \(Q_A = d_AG\)) |
|
| \(r == x_1 \; \mathrm{mod} \; n\) | Signature is valid |
Reference: Information Security: Principles and Practice 2nd Edition
(Mark Stamp 저, Pearson, 2011)
Reference: 2022학년도 1학기 홍익대학교 네트워크 보안 강의, 이윤규 교수님
