ECDSA

ECDSA(Elliptic Curve Digital Signature Algorithm)는 DSA 의 서명 구조를 타원 곡선 위의 점 연산으로 옮긴 전자서명 알고리즘이다.

개요

1992년 스콧 밴스톤(Scott Vanstone)이 제안했고 ANSI X9.62(1999), NIST FIPS 186-2(2000)로 표준이 되었다. 타원 곡선 위에서 Q = dG 를 알 때 d 를 구하는 타원 곡선 이산대수 문제의 어려움에 기댄다. 같은 안전성을 RSA 보다 훨씬 짧은 키로 얻는다. 256비트 곡선이 3,072비트 RSA 와 비슷한 수준이다.

TLS 인증서, SSH 키(ecdsa-sha2-nistp256), 비트코인·이더리움의 거래 서명(secp256k1 곡선), FIDO 인증기에서 쓴다.

알고리즘

타원 곡선 E, 기준점 G, G 의 위수 n 을 공개 매개변수로 정한다.

키 생성 : 개인키 d 를 1 ~ n-1 에서 고르고 공개키 Q = dG 를 공개한다.

서명 (메시지 m, 해시 z = H(m))

난수 k 를 1 ~ n-1 에서 고른다
점 kG = (x₁, y₁) 을 구하고 r = x₁ mod n (0 이면 k 를 다시 고른다)
s = k^-1(z + r·d) mod n
서명은 (r, s)

검증

w = s^-1 mod n, u₁ = z·w, u₂ = r·w
점 u₁G + u₂Q = (x₁, y₁) 을 구한다
x₁ mod n 이 r 과 같으면 올바른 서명이다

주의할 점

난수 k 를 두 번 쓰면 개인키가 드러난다. 같은 k 로 만든 서명 두 개에서 k 와 d 를 계산할 수 있다. 2010년 플레이스테이션 3 의 펌웨어 서명 키가 k 를 고정값으로 써서 유출되었다
그래서 메시지와 개인키로 k 를 결정적으로 만드는 방식(RFC 6979)을 쓴다
곡선 매개변수를 잘못 고르면 약해진다. 표준 곡선(P-256, secp256k1)을 쓴다

비교

방식	군	비고
DSA	정수 나머지 군의 위수 q 부분군	ECDSA 의 원형. FIPS 186-5(2023)에서 새 서명 생성용으로는 빠졌다
ECDSA	타원 곡선 점의 군	키·서명이 짧다
Schnorr 서명	위수 q 부분군 또는 타원 곡선	서명식이 일차식이라 합치기 쉽다
Ed25519	에드워즈 곡선	Schnorr 계열의 EdDSA. k 를 결정적으로 만든다

같이 보기