타원곡선 DSA 문서 원본 보기

{{위키데이터 속성 추적}}
'''타원곡선 DSA'''(Elliptic Curve Digital Signature Algorithm, ECDSA)는 타원곡선을 이용한 전자서명 알고리즘이다.

== 정의역 매개변수 ==

* 모두 정의역 매개변수(domain parameter)로 (CURVE, g, n) 을 사용하기로 합의한다.
** CURVE : 타원곡선 체(field)와 여기에 사용된 수식이다.
** g : 타원곡선의 기준점(base point)이다. 해당 타원곡선의 생성원(generator)이다.
** n : g의 차수이다. n X g = 0이며, 반드시 소수이어야 한다. 보통 충분히 큰 소수를 사용한다.

== 절차 ==
앨리스는 키쌍<math>(d_A,Q_A)</math>를 만든다.

* d는 무작위로 선택된 1부터 n-1사이의 정수로서, 개인키이다.
* Q는 Q=dg를 만족하는 정수로서, 공개키이다.

=== 서명 ===

* 앨리스가 메시지m을 다음 절차를 따라 서명한다.
*# e=H(m)이고, H는 암호학적 해쉬함수이다.
*# z는 e의 이진 값에서 왼쪽으로부터 <math>L_n</math>번째 까지를 잘라낸 값(<math>L_n</math>leftmost bits of e)이다.  <math>L_n</math>는 n의 비트 길이(bit length)이다.
*# 암호학적으로 안전한 난수 k를 [1, n-1] 사이에서 무작위로 선택한다.
*# 곡선 위의 점 <math>(x_1,y_1)=k*g</math>를 계산한다.
*# <math>r=x_1 \pmod{n}</math>을 계산한다. 만약 r=0이면 3으로 되돌아가 다른 k를 다시 선택하여 순서대로 진행한다.
*# <math>s=k^{-1}(z+rd_A) \pmod{n}</math>을 계산한다. 만약 s=0이면 3으로 되돌아가 다른 k를 다시 선택하여 순서대로 진행한다.
* 완성된 서명은 (r, s)이다.

=== 검증 ===
밥이 앨리스의 서명을 인증하려면, 앨리스의 공개키를 미리 알아야 한다.

==== 곡선 위의 점 인증 ====
* <math>Q_A \neq O(identity \ element)</math>인지 확인한다.
* <math>Q_A</math>가 곡선 위의 점(curve point)인지 확인한다.
* <math>n \times Q_A=O</math>인지 확인한다.

==== 서명 유효성 인증 ====
* r,s가 1부터 n-1사이의 정수인지 확인한다. 아니면 서명은 무효이다.
* e=H(m)을 계산한다. H는 앨리스가 서명 생성에 썼던 해쉬함수이다.
* z는 e의 이진 값에서 왼쪽으로부터 <math>L_n</math>번째 까지를 잘라낸 값이다.
* <math>w=s^{-1} \pmod{n}</math>을 계산한 다음, <math>u_1=zw,\ u_2=rw \pmod{n}</math>를 계산한다.
* Shamir’s trick을 사용해서<math>(x_1,y_1)=u_1 \times g +u_2 \times Q_A </math>을 계산한다. 만약 <math>(x_1,y_1)= O </math>이면 서명은 무효이다.
* <math>r \equiv x_1 \pmod{n}</math>일때만 유효하다. 아니면 모두 무효이다.
== 같이 보기 ==
* [[RSA 암호]]

{{공개 키 암호 방식}}
{{비트코인}}

[[분류:암호학]]
[[분류:타원곡선 암호]]