はじめに
30分で理解するシリーズが職場で人気です（読者１名）。職場とはブロックチェーンの会社。その30分で理解するシリーズで特に需要の高そうなやつを外出ししていこうと思います。
ECDSAとは
ECDSAは、Elliptic Curve Digital Signature Algorithmの略で、楕円曲線暗号を用いたデジタル署名アルゴリズムです。ECDSAは、暗号技術の一つであり、RSA暗号と並んで代表的な暗号技術の一つとして知られています。
ECDSAの動作は、まず署名者が自分の秘密鍵を用いて署名を生成し、署名を受信者に送信します。受信者は、送信された署名と公開鍵を用いて署名の正当性を検証します。署名が正当である場合、受信者はメッセージの送信者が署名者であることを確認できます。
ECDSAは、RSA暗号と比べて同じレベルの安全性を確保する鍵の長さが短くて済みます。
ECDSAで署名する
ECDSAによる署名に必要なもの
・ $ q $ ： 一時的な秘密鍵（暗号学的に安全な乱数）。
・ $ Q $ ：$ q $ と楕円曲線生成元 $ G $ から生成された一時的な公開鍵。
・ $ r $ ：$ Q $ の$ x $ 座標
・ $ v $ ：$ Q $ の$ y $ 座標が正の場合$ v $は偶数、負の場合$ v $は奇数に設定
・ $ k $ ：Signer（送信者、EOA所有者）の秘密鍵
・ $ m $ ：署名する対象のデータ。例えばトランザクションデータ。
・ $ p $ ：楕円曲線が存在する有限体の素数位数（この素数位数の有限体上に2つの値があって各々をこの素数で割った余りが同じならこの2つの値を同じ値とみなします）。
イーサリアムでは
$
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
= 2^{256} - 2^{32} -977
$
とします。きわめて大きな値であるのが大事です。楕円曲線上において$p$の値が大きくなるほど$G$と$k*G$から値$k$を求めることが難しくなるからです。
また，受信者が検証に必要となる公開鍵
$$
K = k * G
$$
も生成しておきます。ここで，$ G $は楕円曲線生成元で以下のような座標で表されます。
$$G=\left( \begin{array}{c} x_g \\ y_g \end{array} \right)=\left( \begin{array}{c} 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179 \\ 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 \end{array} \right)$$
これで準備完了。
さあ署名しましょう。まず$ s $という値を次式で算出します。
$$
s = \frac{Keccak256(m)+r * k}{q}{\quad(mod\quad p)}
$$
この$ s $と、上記の$ m $、$ r $、$ v $、Signerの公開鍵$ K $をVerifier（署名検証者）に託せば、そのVerifierは署名の検証をしてくれます。
ECDSAで署名を検証する
VerifierがSigner A氏に託されたのはデータ本体$ m $と$ s $と$ r $、$ v $とSigner A氏の公開鍵$ K $。
これからVerifierはデータにされた署名が本当にSigner A氏のものかどうかを検証します。
検証の手順は以下の通りです。
１. 次の式で$ Q' $を算出します。
$$
Q' = \frac{Keccak256(m) * G}{s} + \frac{r*K}{s}\quad{(mod\quad p)}
$$
２. Signer A氏にVerifierが託された$ r $を楕円曲線の方程式
$$
y^2 = x^3 + 7 \quad(mod\quad p)（Ethereumの場合）
$$
の$ x $に代入し、$ y $を求め、$ Q $を計算します。この時、$ v $を用いて$ y $を一意に決定します。
３. 上の１.と２.で求めた$ Q' $と$ Q $を比較して$ Q'=Q $であれば、次節の証明のようにデータ$ m $にされた署名$ s $が公開鍵$ K=k*G $の持ち主Signer A氏による署名であることを検証したことになります。
Q'=Q ならば K=k*G であることの証明
$ Q $ は$ q $ と楕円曲線生成元 $ G $ から生成された一時的な公開鍵なので、
$$
Q= q*G
$$
のはずです。したがってもし$ Q'=Q $だとすると前節の式の$ Q'$に$ q*G$を入れて
$$
q*G = \frac{Keccak256(m) * G}{s} + \frac{r*K}{s}\quad{(mod\quad p)}
$$
となるはずです。また、前述のように、
$$ s = \frac{Keccak256(m)+r * k}{q} $$
なので、この$ s $を上の式に入れ整理すると
$$ K=k*G $$
という式が得られます。つまり、$ Q'=Q $ならば$ K=k*G $が得られ，$ K $は確かにSigner A氏の秘密鍵$ k $から得られた公開鍵であることが導かれます。これでデータにされた署名が本当にSigner A氏のものであることが検証できたことになります。
Appendix
EIP-155以降、from addressを$ s $から求める前に$ v $を検証することでTransactionが自分のNetworkに対して送られたものかを判別できます。
リカバリー時に公開鍵を一意に決めるためという元々の$ v $値の目的にリプレイアタック対策のため（EIP-155）という目的を加えたための変更です。
v = ChainID * 2 + 8 + 27\\
or\\
v = ChainID * 2 + 8 + 28
List of Chain ID's:
Chain ID |
Chain(s) |
|---|---|
| 1 | Ethereum mainnet |
| 2 | Morden (disused), Expanse mainnet |
| 3 | Ropsten |
| 4 | Rinkeby |
| 5 | Goerli |
| 42 | Kovan |
| 1337 | Geth private chains (default) |
Find more chain ID's on chainid.network and contribute to ethereum-lists/chains.