타원곡선 디지털서명 알고리즘 편집하기

'''타원곡선 디지털서명 알고리즘'''(ECDSA; Elliptic Curve Digital Signature Algorithm)은 [[타원곡선암호]]를 [[전자서명]]에 접목시킨 [[암호 알고리즘]]이다. 이는 [[비트코인]], [[이더리움]] 등의 [[암호화폐]] 거래 시 정당한 소유주만이 자금을 쓸 수 있도록 하기 위해 사용된다.

==개요==
타원곡선 디지털서명 알고리즘은 1985년 [[닐 코블리츠]](Neal Koblitz)와 [[빅터 밀러]](Victor Miller)가 제안한 [[타원곡선암호]](ECC; Elliptic Curve Cryptosystem)에 기반을 둔 전자서명 알고리즘이다. 이는 일반적인 인증 시스템에서 보안 [[키]]의 보호가 점점 어려워짐에 따라 이를 보완하기 위해 개발한 것으로서, 이 방식에서는 발신자에 의한 [[서명]] 시 사용되는 [[개인 키]]와 수신자가 발신자의 서명을 사용하는 [[공개 키]] 한 쌍을 갖는다. [[미국표준기술연구소]](NIST)에서 발표한 [[전자서명 표준]](DSS)은 적합한 [[타원곡선]]과 키 쌍의 계산, [[전자서명]]을 지정하고 있으며, 1998년 [[미국표준협회]](ANSI)에서 타원곡선 디지털서명 알고리즘을 미국 표준화해 [[연방 정보 처리 표준]](FIPS)에서 승인되었다. 타원곡선 디지털서명 인증에 필요한 계산은 개인 키와 공개 키의 생성, 서명과 서명 검증으로 이뤄지며 공개 문헌에서 대응하는 방정식을 확인할 수 있다.

[[블록체인]] [[네트워크]]에서 [[트랜잭션]]을 주고받을 때, 수신자가 인증자의 공개 키로 메시지가 진짜인지 검증하기 위해서는 전자서명을 필요로 한다. 이 전자서명은 개인 키로만 생성 가능하고 수신인이 트랜잭션에 쓰여있는 전자서명이 정말 발신인의 전자서명이 맞는지 확인할 수 있어야 하는데, 이 두 조건을 고루 만족시키는 기술이 타원곡선암호이다. 타원곡선 디지털서명 알고리즘을 통해 암호화폐 거래 시 정당한 소유자만이 자금을 쓸 수 있도록 할 수 있으며 대표적으로 [[비트코인]]과 [[이더리움]]에서 타원곡선 디지털서명 알고리즘을 사용한다.

==특징==
* 기존 전자서명보다 공개 키의 크기가 보안 수준의 1/2 크기로 작은 것에 비해 서명의 크기는 보안 수준의 4배 정도로 동일하다.
* 자유로이 배포 가능한 공개 키가 있으므로 인증하는 측에서 비밀 키를 관리, 보호하지 않아도 된다.

==활용==
대표적으로 [[비트코인]]과 [[이더리움]]에서 타원곡선 디지털서명 알고리즘을 사용한다. 이때 사용되는 타원곡선의 매개변수는 secp256k1으로 [[SEC]](Serticom Research)에 정의되어 있다. secp256k1은 비트코인이 인기를 끈 뒤, 급격히 사용되었으며 구현이 충분히 최적화되면 타곡선보다 30% 이상 속도가 빨라지는 경우가 많다. 정의된 것들은 이러하다.

 a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
 b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
 유한군 p값 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
 private key 값 = n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
 기준점 G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

이렇게 정의되었을 때 상수는 0이므로 곡선 방정식의 축 항 역시도 항상 0이다. 그러므로 곡선 방정식은 이러하다.

 y^2 = x^3 + 7

* '''송신자가 서명을 생성해 보내는 절차'''
:* Step1 : 트랜잭션 만들기
:* Step2 : 개인 키를 타원곡선이 지정하는 범위 내에서 정하기
::secp256k1에 정의되어 있는 범위 1 ~ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 내에서 고른다. 이때 유의해야 할 것은 1~n까지의 범위가 아닌, 1~n-1까지의 범위기 때문에 위에 적어둔 n 값의 마지막 D0364141까지가 아닌 -1을 해 준 값 D0364140까지라는 것이다.

:* Step3 : 서명 r 구하기
::기준점 G값 중 랜덤한 수를 하나 고르고 그 숫자에 G를 곱해 준다. 계산된 값이 서명 r이 된다.

:* Step4 : 서명 s 구하기
::서명 s를 구하는 공식은 이러하다.
 k^-1(z+r*private key) mod n

 k = 서명 r을 구할 때 고른 랜덤한 수
 z = 트랜잭션 정보를 직렬 정렬한 값
 r = 위에서 구한 서명 r값
 private key = 개인키 값

::이때 유의해야 할 것은 계산값은 0이 아닌 다른 값이어야 한다는 것이다. 만약 계산값이 0이 나오는 경우 난수 k를 새롭게 생성하고 다시 계산해야 한다.

* '''수신자가 서명을 받고 검증하는 절차'''

:서명 검증은 인증자의 공개 키를 사용해 메시지가 진짜인지 검증하는 목적을 갖는데, 서명을 생성할 때와 동일한 [[해시]] [[알고리즘]]을 사용해 인증자에 의해 서명된 메시지 다이제스트를 공개키 및 구성요소와 함께 계산한다. 서명을 확인하는 공식은 이러하다.

 U1 * G + U2 * public key

 U1 = z * w mod n
 U2 = r * w mod n
 w = s^-1 mod n
 publick key는 공개 키이자 복구 키로 이더리움에서는 서명값이 아닌 정수 27 또는 28을 사용한다.

:계산해낸 p의 x 좌표값과 서명 r의 값이 같다면 송신자의 서명이 맞다는 의미로 확인이 끝난다.<ref>그래비티Grabity, 〈[https://blog.naver.com/grabityio/221497780327 타원곡선 암호과 이더리움 전자서명 ( feat. 우주를 줄게 )]〉, 《네이버 블로그》, 2019-03-26</ref><ref>김훈일, 〈[https://brunch.co.kr/@nujabes403/13 타원곡선과 블록체인]〉, 《네이버 brunch》, 2018-08-18</ref>

* '''난수생성기와 'K'값의 중요성'''

:타원곡선암호는 개인 키의 비트 수가 적기 때문에 [[난수 생성기]]의 난이도가 낮다면 개인 키를 예측할 수 있는 확률이 증가한다. 또한 비트코인 거래 시 [[암호화]]되지 않은 난수 생성기를 사용해 같은 'K'값으로 디지털서명을 한다면, 그것은 곧 (R, S) 중 R 값이 동일하다는 의미가 되며 그럴 경우 타인이 비트코인 지갑의 개인 키를 알아낼 수 있기 때문에 제대로 된 난수 'K'값을 만드는 것은 몹시 중요하다.<ref> snifikino,〈[https://www.instructables.com/id/Understanding-how-ECDSA-protects-your-data/ Understanding How ECDSA Protects Your Data]〉, 《instructables》</ref>

==알고리즘 규격==
다음은 [[한국인터넷진흥원]](KISA)에서 규정한 내용들이다.

* ECDSA에서 사용되는 ECC 커브에 대한 ASN.1의 형태
 ecpkParameters ::= CHOICE { 
 ecParameters ECParameters, 
 namedCurve OBJECT IDENTIFIER, 
 implicitlyCA NULL } 
 ecParameters ::= SEQUENCE { 
 version ECPVer, 
 fieldID FieldID, 
 curve Curve, 
 base ECPoint, 
 order INTEGER, 
 cofactor INTEGER OPTIONAL, }

* 무선 [[공인인증시스템]]은 sect163k1, c2pnb163v1, secp160r1을 모두 구현해야 한다. 각각의 [[OID]]는 이러하다.
 sect163k1 커브 (WTLS 3번 커브)     
 sect163k1 : { iso(1) identified-organization(3) certicom(132) curve(0) 1}
 c2pnb163v1 커브 (WTLS 5번 커브)     
 c2pnb163v1 : { iso(1) member-body(2) us(840) ANSI-X9-62(10045) curves(3) characteristicTwo(0) 1 } 
 secp160r1 커브 (WTLS 7번 커브)     
 secp160r1 : { iso(1) identified-organization(3) certicom(132) curve(0) 8 }

* 가입자 공인인증서의 전자서명키를 2048비트로 상향 조정한다면, 전자서명키 생성에 sect233k1, sect233r1, secp224r1 커브를 추가로 구현해야 한다. 각각의 OID는 이러하다.

 sect233k1 커브 (WTLS 10번 커브) 
 sect233k1 : { iso(1) identified-organization(3) certicom(132) curve(0) 26 } 
 sect233r1 커브 (WTLS 11번 커브) 
 sect233r1 : { iso(1) identified-organization(3) certicom(132) curve(0) 27 } 
 secp224r1 커브 (WTLS 12번 커브) 
 secp224r1 : { iso(1) identified-organization(3) certicom(132) curve(0) 33 }

* ECDSA 공개키 알고리즘에 포함된다면 OID는 이러하다.

 id-ecPublicKey OBJECT IDENTIFIER ::= { 
 iso(1) member-body(2) us(840) ANSI-X9-62(10045)
 id-public-key-type(2) 1 }

* [[SHA-1]]이나 [[SHA-256]] 해시 후 ECDSA를 사용한다면 OID는 이러하다.

 ecdsa-with-SHA1 OBJECT IDENTIFIER ::= {
 iso(1) member-body(2) us(840) ANSI-X9-62(10045) signature(4) 1 }
 ecdsa-with-SHA256 OBJECT IDENTIFIER ::= {
 iso(1) member-body(2) us(840) ansi-X9-62(10045) signatures(4) ecdsa-with-SHA2(3) 2 }

* 전자서명인증체계 내의 인증서나 [[CRL]]의 서명 필드의 구조체 구조는 이러하다.

 ECDSA-Sig-Value ::= SEQUENCE 
 { r INTEGER, s INTEGER }

{{각주}}

== 참고자료 ==
* 그래비티Grabity, 〈타원곡선 암호과 이더리움 전자서명 ( feat. 우주를 줄게 )〉, 《네이버 블로그》, 2019-03-26 
* 김훈일, 〈타원곡선과 블록체인〉, 《네이버 brunch》, 2018-08-18 
* snifikino, 〈Understanding How ECDSA Protects Your Data〉, 《instructables》

== 같이 보기 ==
* [[타원곡선]]
* [[타원곡선암호]]
* [[공개키 암호 알고리즘]]
* [[슈노르서명]]
* [[블록체인]]
* [[비트코인]]
* [[이더리움]]

{{암호 알고리즘|검토 필요}}