> For the complete documentation index, see [llms.txt](https://whs3-doge5k.gitbook.io/smartcontract-security-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://whs3-doge5k.gitbook.io/smartcontract-security-docs/basics/undefined/ecdsa.md).

# ECDSA

### ECDSA(Elliptic Curve Digital Signature Algorithm)

ECDSA는 ECC(Elliptic Curve Cryptography)를 사용한 서명 방식이다.

* 메세지의 무결성과 인증을 검증하기 위해 사용된다.
  * **서명 생성**: 개인키를 사용해 메시지 해시값에 대한 서명
  * **서명 검증**: 공개키와 메시지, 서명을 사용해 서명의 유효성 확인

ECDSA는 RSA에 비해 **짧은 키 길이로도 높은 보안성을 제공**해 널리 사용된다.

***

### ECC란?

* ECC(Elliptic Curve Cryptography)는 타원 곡선 암호로  효율성 있는 암호화 방식이다.
* ECC는 $$y^2=x^3+ax+b(4a^3+27b^2 \not =0)$$을 만족하는 타원 곡선을 사용한다.
* ![](https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FSiNPdTEn9PCinw8asLGz%2F1.png?alt=media\&token=fefa907d-8617-4c00-85e5-e177fbdfcfbf)![](https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2F4OGqjbmdL17BFZM5eIxU%2F2.png?alt=media\&token=cde2e295-84ab-4480-a243-72053890e458)
  * $$4a^3+27b^2=0$$을 제외시키는 이유는 연산 과정에서 오류를 발생시킬 가능성이 있는 특이점을 제외하기 위해서이다.
  * ![](https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2Fms2u7C4GzcERbQTkAfFb%2F3.png?alt=media\&token=db3fea7b-d5d6-4f08-9a7a-47752c6a482e)

### ECC의 장점

* ECC 알고리즘은 다른 암호화 방식에 비해 연산 과정이 상당히 단순하고 효율적이기 때문에 컴퓨터나 핸드폰이 아닌 작은 라우터 등에서도 사용될 정도로 **속도가 매우 빠른 장점**이 있다.
* RSA에 비해 **매우 작은 bit의 키**(256bit << 3072bit)**로도 동일한 보안성을 제공**할 수 있다.

***

### ECC 연산

타원 곡선은 크게 세 가지 특징이 있다.

* 타원 곡선은 **x축을 중심으로 대칭** 형태를 유지한다.
* 한 점에 대해 **직각**인 직선을 긋는다면 어떠한 형태로든 **곡선에 2번 교차**한다.
  * 한 점에 대해 직각이 아닌 직선을 긋는다면 어떠한 형태로든 곡선에 3번 교차한다.
* 곡선 내 모든 덧셈 연산에 대해 결과가 닫혀있다.

이러한 특징을 활용해 연산을 수행한다.

대표적인 예로 두 번 교차하는 직선의 연산에 대해 설명하겠다.

2번 교차하는 임의의 직선 $$y=a\_2x+b\_2$$을 그어 점 P, rR에서 교차한다고 할 때 이 수식으로 R을 다음과 같이 정의한다.

$$
P+P=R
$$

![](https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FqPETiTGOYPrXokHwFkjn%2F4.png?alt=media\&token=3407e615-ebba-48bf-8b47-b5f10c386e36)

R은 직선이 두 번째로 교차하는 점의 **x축 대칭점**으로, 타원 곡선의 특성에 의해 이 점 역시 타원 곡선 내에 존재한다. 이후의 연산 역시 동일하게 연산 결과로 나온 한 점에 대해 직각인 직선을 그어 다음 점을 찾는다. 이러한 **연산 방식은 수식으로 정의**되어있고, 값을 대입함으로써 쉽게 다음 점을 찾을 수 있다.

***

### ECC 암호화 방식

타원 곡선 내의 공개된 생성점 G(generate point)에 대해 $$k\*G=Q$$를 연산하고 Q를 공개키로, k를 비밀 키로 사용한다.

### ECC의 안전성

암호의 안전성은 **수학적 어려움**에 의해 보장된다.

ECC는 **ECDLP(Elliptic Curve Discreate Logarithm Problem)**&#xC5D0; 의해 안전성이 보장된다.

* G와 Q가 공개되어 있을 때 **비밀 키인 k를 연산하는 것이 현실적으로 불가능하다**는 **수학적 증명**이다.

***

### ECDSA 서명 방식

#### 1. generate

공개 키

* 타원 곡선
* 생성점 G
* 점 Q(=k\*G)

비밀 키

* 난수 k (정수)

#### 2. signature

임의의 메세지 m에 대한 서명일 때,

* m을 해시하여 H(m)을 구함
* 정수 r을 랜덤 선택
  * ECC는 유한체를 사용하므로 1≤ r ≤ n (n은 유한체의 순환수이다)를 만족 해야 한다.
* 점 $$P(x\_1,y\_1) =r\*G$$계산
* $$R\equiv x\_1 (mod n)$$계산
* $$s \equiv r^{-1}(H(m)+k\*R) (mod n)$$계산
  * $$r^{-1}$$은 모듈러 역수이다.
* **최종 서명 : (R,s)**

#### 3. verify

받은 메세지 m과 서명 (R,s), 공개키로 검증 과정을 진행한다.

* m을 해시하여 H(m)을 구함
* $$P'(x\_2,y\_2)\equiv S^{-1}(H(m)G+RQ) (mod n)$$ 계산

  $$s \equiv r^{-1}(H(m)+k\*R) (mod n)$$

  $$r \equiv s^{-1}(H(m)+k\*R) (mod n)$$

  $$rG \equiv s^{-1}G(H(m)+kR) \equiv s^{-1}(H(m)G+RkG) (modn)$$

  $$rG = P, kG=Q$$

  $$P\equiv s^{-1}(H(m)G+RQ) (mod n)$$
* $$x\_2 \equiv R(mod n)$$이면 유효한 서명이다.