타원곡선 DSA

3. 키 생성

앨리스는 개인키와 공개키 쌍을 생성한다. 개인키는 1부터 n-1 사이의 무작위로 선택된 정수 $d\_A$이고, 공개키는 $Q\_A\; =\; d\_A\; \backslash times\; G$를 만족하는 정수이다. 여기서 $\backslash times$는 타원 곡선 점의 스칼라 곱셈을 나타낸다.

$d\_A$와 $Q\_A$의 대응은 1대1이며, $d\_A$에서 $Q\_A$를 계산하는 것은 비교적 용이하지만, $Q\_A$에서 $d\_A$를 계산하는 것은 실질적으로 불가능하다(이산대수 문제). 즉, $d\_A$와 $Q\_A$의 대응은 일방향 함수가 된다.^[20]

4. 서명 생성

앨리스가 메시지 ''m''에 서명하는 과정은 다음과 같다.

# 암호화 해시 함수(예: SHA-2)를 사용하여 $e\; =\; \backslash textrm\{HASH\}(m)$을 계산하고, 그 출력을 정수로 변환한다.

# $e$의 왼쪽부터 $L\_n$ 비트를 취하여 $z$를 계산한다. 여기서 $L\_n$은 군 차수 $n$의 비트 길이이다. ($z$는 $n$보다 '''클 수 있지만''' 길이는 더 '''길 수 없다''').^[2]

# $[1,\; n-1]$ 구간에서 '''암호학적으로 안전한 무작위''' 정수 $k$를 선택한다.

# 타원 곡선 점의 스칼라 곱셈을 통해 곡선 점 $(x\_1,\; y\_1)\; =\; k\; \backslash times\; G$를 계산한다.

# $r\; =\; x\_1\backslash ,\backslash bmod\backslash ,n$을 계산한다. $r\; =\; 0$이면 3단계로 돌아간다.

# $s\; =\; k^\{-1\}(z\; +\; r\; d\_A)\backslash ,\backslash bmod\backslash ,n$을 계산한다. $s\; =\; 0$이면 3단계로 돌아간다.

# 서명은 쌍 $(r,\; s)$이다. ($(r,-s\backslash ,\backslash bmod\backslash ,n)$도 유효한 서명이다.)

표준에서 언급하듯이, $k$를 비밀로 유지하는 것뿐만 아니라 서로 다른 서명에 대해 서로 다른 $k$를 선택하는 것도 매우 중요하다. 그렇지 않으면 6단계의 방정식을 풀어 개인 키 $d\_A$를 계산할 수 있다. 동일한 $k$ 값을 사용하고 알려진 서로 다른 메시지 $m$와 $m\text{'}$에 대해 생성된 두 서명 $(r,\; s)$와 $(r,\; s\text{'})$가 주어지면, 공격자는 $z$와 $z\text{'}$를 계산할 수 있다. $s\; -\; s\text{'}\; =\; k^\{-1\}(z\; -\; z\text{'})$(모든 연산은 modulo $n$으로 수행됨)이므로, 공격자는 $k\; =\; \backslash frac\{z\; -\; z\text{'}\}\{s\; -\; s\text{'}\}$를 찾을 수 있다. $s\; =\; k^\{-1\}(z\; +\; r\; d\_A)$이므로, 공격자는 개인 키 $d\_A\; =\; \backslash frac\{s\; k\; -\; z\}\{r\}$를 계산할 수 있다.

이러한 구현상의 오류는 플레이스테이션 3 게임 콘솔에 사용된 서명 키를 추출하는 데 사용되었다.^[3]

ECDSA 서명이 개인 키를 유출할 수 있는 또 다른 방법은 결함 있는 난수 생성기에 의해 $k$가 생성되는 경우이다. 2013년 8월, 안드로이드 비트코인 지갑 사용자들이 자금을 잃게 된 원인이 바로 이러한 난수 생성 오류였다.^[4]

각 메시지에 대해 $k$가 고유하도록 하려면, 난수 생성을 완전히 건너뛰고 메시지와 개인 키 모두에서 $k$를 도출하여 결정적 서명을 생성할 수 있다.^[5]

5. 서명 검증

밥은 앨리스의 공개키 Q|A^영어를 사용하여 서명을 검증한다. 우선 앨리스의 공개키 Q|A^영어가 유효한지 확인해야 한다.

# Q|A^영어가 항등원 ''O''와 같지 않은지 확인한다.

# Q|A^영어가 타원 곡선 위의 점인지 확인한다.

# n|n^영어 × Q|A^영어 = ''O''인지 확인한다.

그다음 메시지 ''m''에 대한 앨리스의 서명 (''r'', ''s'')의 진위를 확인하기 위해 다음 단계를 따른다.

# ''r'', ''s''가 1부터 ''n''-1 사이의 정수인지 확인한다. 아니면 서명은 무효이다.

# ''e'' = H(''m'')을 계산한다. 여기서 H는 앨리스가 서명 생성에 사용했던 해시 함수와 동일하다.

# ''z''는 ''e''의 이진 값에서 왼쪽으로부터 L|n^영어번째까지 잘라낸 값이다.

# w|w^영어 = s|s^영어⁻¹ mod ''n''을 계산한다.

# u|1^영어 = zw|zw^영어 mod ''n''과 u|2^영어 = rw|rw^영어 mod ''n''을 계산한다.

# 스트라우스 알고리즘(Shamir’s trick)을 사용하여 곡선점 (x|1^영어, y|1^영어) = u|1^영어 × G|G^영어 + u|2^영어 × Q|A^영어를 계산한다. 만약 (x|1^영어, y|1^영어) = ''O''이면 서명은 무효이다.

# r|r^영어 ≡ x|1^영어 mod ''n''일 때만 유효하다. 아니면 모두 무효이다.^[6][22]

6. 공개키 복구

주어진 메시지 와 해당 메시지에 대한 앨리스의 서명 $r,\; s$가 주어지면, 밥은 앨리스의 공개키를 복구할 수 있다.^[7]

# 과 가 $[1,\; n-1]$ 범위의 정수인지 확인한다. 그렇지 않으면 서명이 무효이다.

# $x\_1$이 $r$, $r+n$, $r+2n$ 등 중 하나(단, $x\_1$이 곡선의 체에 대해 너무 크지 않아야 함)이고 $y\_1$이 곡선 방정식을 만족하는 값인 곡선 점 $R\; =\; (x\_1,\; y\_1)$을 계산한다. 이러한 조건을 만족하는 여러 개의 곡선 점이 있을 수 있으며, 각기 다른 값은 서로 다른 복구된 키를 생성한다.

# 서명 생성에 사용된 것과 동일한 함수 HASH를 사용하여 $e\; =\; \backslash textrm\{HASH\}(m)$을 계산한다.

# 의 왼쪽에서부터 $L\_n$ 비트를 로 한다.

# $u\_1\; =\; -zr^\{-1\}\backslash ,\backslash bmod\backslash ,n$과 $u\_2\; =\; sr^\{-1\}\backslash ,\backslash bmod\backslash ,n$을 계산한다.

# 곡선 점 $Q\_A\; =\; (x\_A,\; y\_A)\; =\; u\_1\; \backslash times\; G\; +\; u\_2\; \backslash times\; R$을 계산한다.

# $Q\_A$가 앨리스의 공개키와 일치하면 서명이 유효하다.

# 모든 가능한 점을 시도했는데 앨리스의 공개키와 일치하는 점이 없으면 서명이 무효이다.

무효한 서명 또는 다른 메시지의 서명은 잘못된 공개키를 복구하게 된다는 점에 유의해야 한다. 서명자의 공개키(또는 해시값)를 미리 알고 있는 경우에만 이 복구 알고리즘을 사용하여 서명의 유효성을 검사할 수 있다.

7. 알고리즘의 정당성

검증 알고리즘의 정당성은 타원곡선 스칼라 곱셈의 분배 법칙과 서명 생성 과정의 수식을 통해 증명된다.

검증 단계 5에서 계산된 곡선 점을 $C$로 표시하면,

:$C\; =\; u\_1\; \backslash times\; G\; +\; u\_2\; \backslash times\; Q\_A$

공개 키 정의 $Q\_A\; =\; d\_A\; \backslash times\; G$를 대입하면,

:$C\; =\; u\_1\; \backslash times\; G\; +\; u\_2\; d\_A\; \backslash times\; G$

타원곡선 스칼라 곱셈의 분배 법칙에 의해,

:$C\; =\; (u\_1\; +\; u\_2\; d\_A)\; \backslash times\; G$

검증 단계 4의 $u\_1$과 $u\_2$ 정의를 대입하면,

:$C\; =\; (z\; s^\{-1\}\; +\; r\; d\_A\; s^\{-1\})\; \backslash times\; G$

공통 항 $s^\{-1\}$을 묶으면,

:$C\; =\; (z\; +\; r\; d\_A)\; s^\{-1\}\; \backslash times\; G$

서명 단계 6의 $s$ 정의를 대입하면,

:$C\; =\; (z\; +\; r\; d\_A)\; (z\; +\; r\; d\_A)^\{-1\}\; (k^\{-1\})^\{-1\}\; \backslash times\; G$

역원의 역원은 원래 원소이고, 원소와 그 역원의 곱은 항등원이므로,

:$C\; =\; k\; \backslash times\; G$

$r$의 정의에 따르면, 이것은 검증 단계 6과 일치한다.

이는 올바르게 서명된 메시지가 올바르게 검증됨을 보여준다. 하지만 안전한 서명 알고리즘은 암호 해독 공격에 대한 저항성 등 다른 속성도 필요하다.

8. 보안

ECDSA의 안전성은 타원곡선 이산 로그 문제(ECDLP)의 어려움에 기반한다.
키 및 서명 크기: ECDSA에서 권장되는 개인키의 비트 크기는 보안 비트 수의 약 두 배이다. 예를 들어, 80비트 보안 수준에서는 160비트 ECDSA 개인키가 필요하다. 서명 크기는 DSA와 ECDSA 모두 동일하며, 보안 수준의 약 4배이다.^[1]
취약점:

• 2010년 12월, "fail0verflow"라는 그룹이 소니가 플레이스테이션 3 게임 콘솔용 소프트웨어에 서명하는 데 사용한 ECDSA 개인 키 복구를 발표했다. 그러나 이 공격은 소니가 알고리즘을 제대로 구현하지 않았고, $k$ 값이 난수가 아닌 정적인 값이었기 때문에 가능했다.^[8][23]
• 2011년 3월 29일, 두 명의 연구원이 IACR 논문을 통해 OpenSSL을 사용하여 이중체 체 상에서 타원곡선 DSA로 인증하는 서버의 TLS 개인 키를 타이밍 공격을 이용하여 검색할 수 있음을 보여주었다.^[9][10][24] 이 취약점은 OpenSSL 1.0.0e에서 수정되었다.^[11][25]
• 2013년 8월, 일부 자바 클래스 [https://docs.oracle.com/javase/10/docs/api/java/security/SecureRandom.html SecureRandom] 구현의 버그로 인해 $k$ 값에 충돌이 발생하는 경우가 있다는 사실이 밝혀졌다. 이로 인해 안드로이드 앱 구현에서 비트코인 트랜잭션 제어 권한을 얻을 수 있었다.^[12][26] RFC 6979에서 설명한 대로, k를 결정적으로 생성하면 이 문제를 방지할 수 있다.
• NIST에서 정의한 타원곡선(P-256, P-384, P-521 등)^[27]이 주로 사용되는데, 시드 값의 근거가 불분명하고,^[28][29] NSA이 백도어를 심었다는 의혹^[30] 때문에 의심을 받기도 한다.^[31][32]

9. 구현 라이브러리

• 보탄
• 바운시캐슬
• 크립틀립
• 크립토플러스플러스
• 크립토 API (리눅스)
• GNU TLS
• 리브지크립트
• 리브레SSL
• 엠베드 TLS
• 마이크로소프트 크립토API
• 오픈SSL
• 울프크립트

참조

_[1] 논문 The Elliptic Curve Digital Signature Algorithm (ECDSA)
_[2] 문서 NIST FIPS 186-4, July 2013, pp. 19 and 26 http://nvlpubs.nist.[...]
_[3] 웹사이트 Console Hacking 2010 - PS3 Epic Fail https://events.ccc.d[...]
_[4] 웹사이트 Android Security Vulnerability https://bitcoin.org/[...] 2015-02-24
_[5] 기술보고서 RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) https://www.rfc-edit[...] 2015-02-24
_[6] 웹사이트 The Double-Base Number System in Elliptic Curve Cryptography http://www.lirmm.fr/[...] 2014-04-22
_[7] 문서 SEC 1: Elliptic Curve Cryptography (Version 2.0) https://www.secg.org[...] SECG
_[8] 뉴스 Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access http://exophase.com/[...] Exophase.com 2011-01-05
_[9] 웹사이트 Cryptology ePrint Archive: Report 2011/232 http://eprint.iacr.o[...] 2015-02-24
_[10] 웹사이트 Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack https://www.kb.cert.[...]
_[11] 웹사이트 ChangeLog http://www.openssl.o[...] OpenSSL Project 2014-04-22
_[12] 웹사이트 Android bug batters Bitcoin wallets https://www.theregis[...] The Register 2013-08-12
_[13] 웹사이트 The NSA Is Breaking Most Encryption on the Internet https://www.schneier[...] 2013-09-05
_[14] 웹사이트 SafeCurves: choosing safe curves for elliptic-curve cryptography http://safecurves.cr[...] 2013-10-25
_[15] 웹사이트 Security dangers of the NIST curves https://www.hyperell[...] 2013-05-31
_[16] 웹사이트 The Strange Story of Dual_EC_DRBG https://www.schneier[...] 2007-11-15
_[17] 웹사이트 NSA Efforts to Evade Encryption Technology Damaged U.S. Cryptography Standard http://www.scientifi[...] Scientific American 2013-09-18
_[18] 웹사이트 curve25519-sha256@libssh.org.txt\doc - projects/libssh.git https://git.libssh.o[...]
_[19] 웹사이트 How to design an elliptic-curve signature system http://blog.cr.yp.to[...] 2014-03-23
_[20] 문서 FIPS 186-3, pp. 19 and 26 http://csrc.nist.gov[...]
_[21] 웹사이트 Console Hacking 2010 - PS3 Epic Fail http://events.ccc.de[...]
_[22] 웹사이트 The Double-Base Number System in Elliptic Curve Cryptography http://www.lirmm.fr/[...]
_[23] 뉴스 Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access http://exophase.com/[...] Exophase.com 2013-12-26
_[24] 웹사이트 Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack https://www.kb.cert.[...]
_[25] 웹사이트 OpenSSL: News, ChangeLog http://www.openssl.o[...]
_[26] 웹사이트 Android bug batters Bitcoin wallets http://www.theregist[...] The Register 2013-12-26
_[27] 웹사이트 RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE http://csrc.nist.gov[...] 2015-07-11
_[28] 웹사이트 SafeCurves: Rigidity http://safecurves.cr[...] 2015-07-11
_[29] 문서 MD5와 SHA-2에서의 난수 생성 방법
_[30] 뉴스 Exclusive: Secret contract tied NSA and security industry pioneer http://www.reuters.c[...] Reuters 2015-07-11
_[31] 웹사이트 Security dangers of the NIST curves https://www.hyperell[...] 2015-07-11
_[32] 웹사이트 [tor-talk] NIST approved crypto in Tor? https://lists.torpro[...] 2015-07-11