검수요청.png검수요청.png

타원곡선 디지털서명 알고리즘

위키원
Asadal (토론 | 기여)님의 2019년 7월 31일 (수) 21:16 판 (같이 보기)
이동: 둘러보기, 검색

타원곡선 디지털서명 알고리즘(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의 값이 같다면 송신자의 서명이 맞다는 의미로 확인이 끝난다.[1][2]
  • 난수생성기와 'K'값의 중요성
타원곡선암호는 개인 키의 비트 수가 적기 때문에 난수 생성기의 난이도가 낮다면 개인 키를 예측할 수 있는 확률이 증가한다. 또한 비트코인 거래 시 암호화되지 않은 난수 생성기를 사용해 같은 'K'값으로 디지털서명을 한다면, 그것은 곧 (R, S) 중 R 값이 동일하다는 의미가 되며 그럴 경우 타인이 비트코인 지갑의 개인 키를 알아낼 수 있기 때문에 제대로 된 난수 'K'값을 만드는 것은 몹시 중요하다.[3]

규격

다음은 한국인터넷진흥원(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 }

각주

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

참고자료

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

같이 보기


  검수요청.png검수요청.png 이 타원곡선 디지털서명 알고리즘 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.