ECDSA 이해하기

ECDSA는 EC + DSA로 볼 수 있다. EC는 Elliptic curve, DSA는 RSA와 비슷한 암호화 기법이다.
EC에 대한 내용은 내 이전 벨로그에도 기록이 있고, 꽤 많이 다뤄진다.
https://velog.io/@jakeweb3/6.-Elliptic-Curves-ECC
하지만 ECDSA는 생각외로 정리된 글이 없어 아래와 같이 메모 해 두려 한다.

Elgamal -> DSA (ECDSA)

ECDSA를 이해하기 위해서는 배경지식이 필요하다.
일단 DSA를 알아야 한다. EC는 Elliptic Curve 이므로 DSA를 알고 EC를 적용하면 이해가 쉽다. 또 DSA를 알기 위해서는 Elgamal을 알면 이해에 도움이 된다. 차근 차근 밟고 올라가는 계단과 같다.

아래 링크를 참조하자. 중요한 부분만 가져와 보았다.

https://blog.humminglab.io/posts/tls-cryptography-9-dsa/

여기에서는 RSA, Elgamal, DSA에 대해서 정리한다.
(해당 글에서 Notation 이 헷갈릴 수 있는데, 예를 들어 $\overline k$ 는 $k^{-1}$ 과 같은 의미다. )

Elgamal Signature 핵심

페르마의 소정리 Fermat's Little Theorem

$k^{p-1} \equiv 1 \pmod {p}$

여기서 $p$ 는 소수, $k$는 $0<k<p$ 이다. 나중에 나온다.

Alice : 메시지 송신자,
Bob : 메시지 수신자

1. Bob은 다음을 공유한다.

   $(p, \alpha, \beta) \\ p = 큰 소수 \\ \alpha = primitive\ root\ (given)\\ \beta \leftarrow \beta \equiv \alpha^z \pmod {p}\\ (z\ is\ secret\ key)$

즉 Secret Key $z$ 를 이용해 세번째 공개키를 만들어 총 세가지 공개키를 공유한다.

2. Alice는 평문을 암호화한다.
   즉, $r, s$를 계산하여 Bob에게 재전송

$(r,\ s)\\ r \equiv \alpha^k \pmod {p} \\ s \equiv m \beta^k \pmod {p} \\ k\ is\ Random,\ (p-1)과\ 서로소$

3. Bob은 암호문을 받고 본인의 비밀키 z를 이용, 해독 (복호화) 한다.

$\beta^k \equiv (\alpha^z)^k \equiv >(\alpha^k)^z \equiv r^z \pmod {p}\\ \rightarrow \beta^k \equiv r^z \pmod {p}\\ \rightarrow s*(r^z)^{-1} = m \pmod {p}\\ \because s \equiv m \beta^k \equiv mr^z \pmod {p} \\$

DH -> ECDH

앞선 내 블로그 글에서 DH (Diffie Helman) 을 정리한 바 있다. 이것을 응용해 ECDH를 만들 수 있다. DH란 결국 지수의 곱 연산을 응용하는 것이다.

즉 a와 b를 알고 있지 못하면, 공개된 $g^a$ 혹은 $g^b$ 만 가지고는 절대로 $(g^a)^b$를 알아낼 수 없다. ($(g^b)^a$도 마찬가지)

이것을 아래 글에서 ECDH로 정리 해 주었다.

https://blog.humminglab.io/posts/tls-cryptography-12-ecc2/

Generator $G$ 에 대해서 $kG$로 표기하는 것은, 단순 곱셈이 아닌 Elliptic Curve 연산이다. 앞선 글 Elliptic Curve 에서 정리 해 두었다.

Alice 와 Bob은 다음에 대해 교환한다. 이는 모두에게 공개된 것이다.

$(p,\ G,\ a,\ b)\\ \rightarrow the\ "Domain\ Parameters"$

여기서
$p$: 모듈러 값 ,
$G$: Generator ,
$a$, $b$: 타원 곡선의 $a$, $b$ 값

Alice : $H_a = d_a G$ 를 계산 ($d_a$는 Random)
Bob : $H_b = d_b G$ 를 계산
공통의 Secret Key :
$S = d_a H_b = d_a(d_b G) = d_b (d_a G) = d_b H_a$

이제 ECDSA는 쉽게 이해할 수 있다. 위 글에서도 나와 있지만, 아래 도훈님 블로그에도 잘 설명되어 있다. 내용은 대동소이하다.

https://velog.io/@dohoon8/Cryptography-4.-ECDH와-ECDSA에-대하여-pgbr3e5a

여기에 더해, 특히 비트코인에 사용된 Secp256k1 곡선에 대해 ECDSA를 "돌리는" 과정을 간략히 정리한다.

Secp256k1 곡선은 미국 NIST에서 권장하는 안전하고 효율적인 곡선이다.

이 곡선을 선택하는 순간 다음의 Spec, 상수 혹은 "Domain Parameter"가 설정된다.

$(p,\ G,\ a,\ b)$

• $p=2^256−2^32−977$
• $G$ : Given
• $a=0, b=7$ in the curve equation $y^2=x^3+ax+b$
• $Order (n)$: The number of points on the elliptic curve, including the point at infinity:
  $n=115792089237316195423570985008687907852837564279074904382605163141518161494337$
• Cofactor (h): For SECP256k1, h=1h=1.

여기서 $n$은 $Order$라고 나와 있지만 ,다항식의 차수 (2차항, 3차항 등)이 아니라, Elliptic Curve에서 Generator $G$를 1번에서 N번까지 "돌리면" 다시 1*$G$로 돌아오는 차수이다. Plonk-by-hand 예제를 보면 알 수 있다. (해당 예제에서는 16번 돌고 1번 더 돌리면 즉 17번 돌리면 원래 자리로 돌아옴)

• Key Generation

  • Private Key $(d)$: Randomly chosen integer in the range $[1,n−1]$
  • Public Key $(Q)$: Calculated by multiplying the private key with the base point GG on the elliptic curve:
    $Q=d×G$

여기서 $d$는 내 비밀키 이므로 절대 유출하지 않는다. $Q$는 Bob에게 전달한다.

여기서 $k$값의 개념이 등장한다. 이는 랜덤 값으로, 매 서명마다 반드시 랜덤으로 Generate 해야 하는 값이다. 위의 $d$는 재사용이 되지만, $k$는 재사용 하는 순간 모든 비밀이 풀린다.

To sign a message $m$:

1. Hash the message: Compute the hash of the message$m$, often using SHA-256.
2. Select random integer$k$: Randomly select$k$from the range$[1, n-1]$.
3. Compute point$R = (x_R, y_R) = k \times G$: Calculate a point on the elliptic curve.
4. Compute$r = x_R \mod n$: Take the x-coordinate of$R$modulo$n$.
5. Compute$s = k^{-1}(z + rd) \mod n$: Where$z$is the hashed message and$d$is the private key. Here,$k^{-1}$is the multiplicative inverse of$k$modulo$n$.
6. Signature: The signature for the message is the pair$(r, s)$.

다음 값을 Bob에게 전달한다.

$Q, r, s$

Verification Process

To verify a signature$(r, s)$for a message$m$and public key$Q$:

1. Hash the message: Compute the hash$z$of the message$m$.
2. Compute$w = s^{-1} \mod n$: Calculate the modular inverse of$s$.
3. Compute$u_1 = zw \mod n$and$u_2 = rw \mod n$: Calculate two values used in the verification.
4. Compute point$P = u_1 \times G + u_2 \times Q$: Use the base point $G$ and the public key $Q$ to compute a new point $P$ on the elliptic curve.
5. Compute $v = x_P \pmod {n}$: Take the x-coordinate of point $P \pmod{n}$.
6. Check if $v = r ?$
   $\rightarrow$If equal, the signature is valid; otherwise, it is invalid.

4. Security Properties of SECP256k1 in ECDSA

• High Security: The 256-bit key size provides a high level of security against brute-force attacks.
• Efficiency: Due to the simplicity of its equation and the smaller key size compared to RSA, SECP256k1 allows for faster computations and reduced storage requirements, making it suitable for systems with limited resources like cryptocurrencies.
• Widely Used: SECP256k1’s application in Bitcoin has led to widespread adoption, making it a well-tested and scrutinized elliptic curve.