ECDSA Sign & Verify

ECDSA(Elliptic Curve Digital Signature Algorithm) : 타원 곡선을 이용한 전자 서명 검증 알고리즘

 

ECDSA Sign & Verify Pseudo Code

시나리오 : 앨리스는 그녀의 메시지를 개인키 $d_A$를 이용해 서명을 하고, 밥은 그녀의 공개키 $H_A$를 이용해 유효성 검증을 한다. 앨리스만이 유효한 서명을 할수 있고, 모두가 서명을 확인할 수 있다.

 

1) 서명 생성

전제 조건 : 도메인 파라미터(D)는 표준을 따른다.

 

입력 :

 - 랜덤 변수 $ k \in {1, ..., n-1} $ 혹은 ephemeral key, 혹은 ek.

 - 해쉬 메시지 z (혹은 4.29 그림에 의하면 $ e = H(m) $) , 혹은 hm.

 - 개인키 $ d_A $ (4.29 그림의 d), 혹은 pk1

 

출력 : (r, s)

1. 랜덤 정수 k를 선택 ${1, ... , n - 1}$ (n은 order of sub group)

2. $ P(x_{p}, y_{p}) = kG $를 계산

3. $ r = x_{p} \, mod \, n $을 계산 ($x_{p}$는 P점의 x좌표)

4. 만약 r = 0이라면 1로 돌아간다.

5. $ s = k^{-1}(z + rd_A) \, mod \, n $을 계산

6. 만약 s = 0이라면 다시 1로 돌아간다. 

 

ECDSA Sign & Verify

2) 서명 검증

입력 : 

 - 상대편(Alice)의 공개키 $ H_A $

 - 해쉬 메시지 z (혹은 4.29 그림에 의하면 $ e = H(m) $)

 - (r, s)

 

출력 : Bool 값 (Verified / Not Verified)

1. $ u_1 = s^{-1}z \, mod \, n $ 계산

2. $ u_2 = s^{-1}r \, mod \, n $ 계산

3. $ P = u_{1}G + u_{2}H_{A} $ 계산

4. $ r == x_{p} \, mod \, n $ 이라면 검증 완료

 

3) 알고리즘 검증

[2]의 Correctness of the algorithm을 참조 

 

[Reference]

[1] Guide to Elliptic Curve Cryptography, Darrel Hankerson.

[2] https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/