Ecc Point Doubling/Addition 및 고찰

1. Ecc Point Doubling

Input : P

Output : 2P

 

If $ P =0 $ :

    then $2P = 0 $.

Else $ P = (x, y)$ :

    If $y = 0$ :

        then $2P = 0$

    Else $ y \ne 0 $ :

        then let $ s = (3x^2 + a)/(2y) $,

                        $ x_2 = s^2 - 2x $,

                        $ y_2 = s(x - x_2) - y $,

                        and $ 2P = (x_2, y_2)$ 

 

--> 6 multiplications, 4 additions/subtractions, and 1 division

 

2. Ecc Point Addition

Input : P, Q

Output : P + Q, $(P \ne Q) $

 

If $P = 0$ :

    then $P + Q = Q$. Likewise if $Q = 0$, then $ P + Q = P$ 

Else $P = (x_0, y_0)$ and $Q = (x_1, y_1) $ :

    If$x_0 = x_1$ (and necessarily $y_0 \ne y_1) $ :

        then $P + Q = 0 $

    Else $x_0 \ne x_1$

        then let $ s = (y_0 - y_1) / (x_0 - x_1) $,

                        $x_2 = s^2 - x_0 - x_1$,

                        $y_2 = s(x_0 - x_2) - y_0$

                        and $P + Q = (x_2, y_2) $

 

--> 2 multiplications, 6 additions/subtractions, and 1 division

 

3. 실무적인 관점

각 연산에서 등장하는 '1 division' 즉, Modular Inverse는 굉장히 부하가 많이 걸리는 연산이다.

따라서, Scalar Multiplication의 경우 Point double과 Point Addition이 다수 필요한데, 예를들어 256bit 길이의 Scalar 곱을 할 경우 512번 Modular Inverse가 들어가서 굉장히 시간이 오래 걸리게 된다.

 

따라서, Point double와 Point Addition은 Jacobian 도메인에서 연산을 하고(Jacobian 도메인에서는 Modular Inverse 연산를 사용하지 않는다) 마지막으로 Affine domain으로 형변환[3] 할때, Modular Inverse를 한번 거치게 하여 512번 Modular Inverse 연산을 총 2번으로 줄이기도 한다.

 

[Reference]

[1] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

[2] https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates

[3] https://crypto.stackexchange.com/questions/19598/how-can-convert-affine-to-jacobian-coordinates