ECDSA

ECC (elliptic curve cryptography)를 사용한 digital signature 알고리즘. 

특히 TLS에서 디피힐먼 방식의 키교환 알고리즘을 채택했을 경우 서버 authentication(해당 서버가 ssl 인증서에 들어있는 public key의 counterpart인 private key를 진짜 가졌음을 검증)을 위해 함께 사용되는 알고리즘 중 하나이다.

(RSA를 키교환 알고리즘으로 채택했을 경우와 달리, 디피 힐먼은 키교환만 할 뿐 authentication을 하지는 못하기 때문에) 

 

 

* ECC

Elliptic Curve Cryptography Tutorial - Understanding ECC through the Diffie-Hellman key Exchange

 

 

파라미터 세팅

1. curve parameter = ( CURVE, G, n )

elliptic curve = $ E_p(a,b) : y^2 = x^3 + ax + b \; mod \; p $

$G$ = base point

$n$ = multiplicative order of G ($ n \times G \; = \; 0 $)

 

2. public key, private key

$d$ = private key. 

$Q$ = public key.

$ d \times G \; = \; Q $. 

"dot" 연산을 d번 했을 때 곡선 위의 한점이자 public Key인 좌표 Q가 나온다.

 

3. 메세지 $m$

 

 

서명 생성하기 (Signature)

1. $z$ 계산하기 

$ e $ = Hash ( message )

$z$ = $L_n$ leftmost bits of $ e $

 

2. 랜덤 integer $k$ 결정하고, 곡선 위의 좌표 $(x_1, y_1)$ 를 계산한다.

k는 1과 n-1 사이의 값이어야 한다.

$ (x_1, y_1) = k \times G $

 

3. 서명 $(r,s)$ 계산하기

$ r \; = \; x_1 \; mod \; n $

$ s \; = \; k^{-1}(z + rd) \; mod \; n$

 

 

이제 메세지 m과 서명인 (r,s) pair 가 상대방에게 전달된다.

 

* 이때 public하게 공유되는 값은 (Curve, $G$, $n$)와 공개키 $Q$,

서버만 알고 있는 private 값은 개인키 $d$와 값 $k$ 이다!

 

 

 

verify 하기 

1. $z$ 계산하기

$ e $ = Hash ( message )

$z$ = $L_n$ leftmost bits of $ e $

 

2. 중간값 $u_1$, $u_2$ 계산하기

$ u_1 $ = $ zs^{-1} \; mod \; n $

$ u_2 $ = $ rs^{-1} \; mod \; n $

 

3. 좌표 $(x_1, y_1)$ 를 계산하기

$(x_1, y_1)$ = $ u_1 \times G + u_2 \times Q $

 

* 이렇게 좌표 $(x_1, y_1)$ 를 구할 수 있는 이유는..

$ u_1 \times G + u_2 \times Q $

= $ u_1 \times G + u_2 \times d \times G $

= $ (u_1+u_2 \times d ) G $

= $ (zs^{-1}+rds^{-1}) G $

= $ (z+rd)s^{-1}G $

= $ (z+rd)(z+rd)^{-1}kG $.    (* $ s \; = \; k^{-1}(z + rd) \; mod \; n$ 이었으므로)

= $ kG $

 

4. 이때 구한 좌표 $(x_1, y_1)$ 이 valid 하다면 verify 통과이다.

$ r \; =? \; x_1 \; mod \; n $

 

 

 

참고 : ECDSA 위키피디아