Double and Add Algorithm
Ecc는 타원곡선 상에서 정의된 스칼라 곱을 아래와 같이 정의한다.
$$
Q = nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}
$$
※ 참고로, 대칭키 교환 알고리즘인 ECDH에 의하면 여기서 Q가 공개키가 되고, n은 비밀키가 된다. 타원 곡선상의 기본점(Base Point) P는 주로 표준을 따른다(link1)(link2).
Scalar Multiplication을 Naive 하게 연산하게 되면 $O(M^2)$ 복잡도를 가진다. 여기서 M은 n을 표현하기 위한 이진 비트수를 뜻한다. (자세한건 링크[2] 참조)
Scalar Multiplication을 쉽게하는 알고리즘으로 double and add가 있고 오늘은 이를 구현하는 2가지 방법을 다룬다.
Double and Add 알고리즘은 다음과 같은 방식을 취한다.
- 먼저 P를 가진다
- P를 Double 하여 2P를 가진다
- 2P에 P를 Add하여 $2^1P + 2^0P$를 만든다
- 2P를 Double 하여 $2^2P$를 만든다.
- 결과 값에 Add하여 $2^2P$ + $2^1P + 2^0P$를 만든다.
- ...
혹은 다른 방법도 있다
- 먼저 P를 가진다
- P를 Double 하여 2P를 가진다.
- 2P에 P를 Add하여 $2^1P + 2^0P$를 만든다
- $2^1P + 2^0P$를 Double하여 $2^2P$ + $2^1P$를만든다.
- $2^2P$ + $2^1P$ 에 $P$를 Add 한다.
- ...
첫번째 연산은 더해줄 값(Addend, P)를 2제곱 해주면서 결과(Result)에 계속 더해주는 것이고,
두번째 연산은 결과(Result)를 2제곱하고, 더해주는 값(Addend, P)은 고정이다.
숫자를 예를 들어 두가지 연산 방식을 살펴본다.
n = 151이라고 하면, 151P가 된다. 이진수로 표현하면 $11101000_2$ 가 된다.
따라서 151P는 다음과 같이 나타낼 수 있다.
\begin{array}{rcl} 151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 \end{array}
즉, $151 \cdot P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P$ 가 된다
n=151일때 double and add 알고리즘을 두가지 연산 방식 모두를 이용해 계산해 볼 것이다.
코드로 표현하면 첫번째 연산은 방향이 LSB->MSB 이며, 두번째 연산은 방향이 MSB->LSB 이다.
#include <cstdio>
#include <cstdint>
int main()
{
uint8_t n = 151;
printf("151 as binary : ");
for (int i = 0; n; i++)
{
printf("%d ", n & 1);
n >>= 1;
}
printf("\n");
n = 151;
uint32_t result = 0;
uint32_t addend = 1;
uint32_t idx = 1;
while (idx < 256)
{
if (idx & n)
result += addend;
addend *= 2;
idx <<= 1;
}
printf("Double and add from LSB to MSB : %d \n", result);
result = 0;
idx = 256;
while (idx > 1)
{
result *= 2;
idx >>= 1;
if (idx & n)
result += 1;
}
printf("Double and add from MSB to LSB : %d \n", result);
return 0;
}
결과
1) 첫번째 연산은 LSB 부터 MSB 까지 검사하는 연산이다
- Result는 Addend 값을 더해주게 주고,
- Addend는 비트 1여부와 상관없이 2 제곱 해주게 된다.
2) 두번째 연산은 MSB 부터 LSB 까지 검사하는 연산이다.
- 첫번째 연산과는 다르게 Result를 매번 2 제곱 해준다.
- 첫번째 result *=2 , idx >>=1 연산은 결과에 영향을 미치는 단계는 아니다. 왜냐하면 result초기값은 0이기 때문이다.
idx는 비트 쉬프트를 해야 첫 시작지점인 128값을 가지게 된다.
- MSB에서 더한 P값은 연산 마지막 즈음 128P 값이 된다.
사실 포스팅을 하게 된 것도 두번째 알고리즘 때문이다.
첫번째 연산이 직관적으로 이해하기 쉽지만, MSB에서 시작해도 double and add 알고리즘이 가능함을 확인할 수 있다.
아래 링크[2]의 교수님도 MSB ~ LSB 연산을 하신다.
혹시나 ECC Scalar Multiplication 알고리즘을 두번째와 같이 설명했을 때 이해가 안가는 분께 도움이 되었으면 하는 바이다.
[20.09.10]
위키피디아[3]에 보니 이미 설명이 있었다.
1) Index Increasing : 첫번째 연산 방식
N ← P
Q ← 0
for i from 0 to m do
if di = 1 then
Q ← point_add(Q, N)
N ← point_double(N) # Addend(N) 를 doubling 해준다
return Q2) Index decreasing : 두번째 연산 방식
Q ← 0
for i from m down to 0 do
Q ← point_double(Q) # 결과값 Result(Q)를 doubling 해준다
if di = 1 then
Q ← point_add(Q, P)
return Q
[Reference]
[1] https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
[2] https://www.youtube.com/watch?v=u1VRbo_fhC8
[3] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
'보안(Security) > ECC( Elliptic curve cryptography)' 카테고리의 다른 글
| ECDSA Sign & Verify (0) | 2020.09.24 |
|---|
