ツンデレで学ぶECDSA署名

[!WARNING]

この記事は現在編集中です。章立てなどが不完全なので、あてにしないでください。

ふん、別にアンタのために書くわけじゃないんだからね！勘違いしないでよね！

この文書は、楕円曲線暗号について解説したものよ。

最初は「なんだか難しそう…」って思うかもしれないけど、大丈夫。

アンタみたいな初心者でも、ちゃんと理解できるように、噛み砕いて説明してあげるから。

ただし！

ただ読み進めるだけじゃダメよ。

ちゃんと頭を使って、真剣に理解しようとしないと、置いていくからね！

…ま、まぁ、頑張って読んでみなさい。

別に期待してるわけじゃないんだから！

レジュメ

楕円曲線暗号とは:
- 楕円曲線の方程式と、その上での特殊な足し算（加算）の定義
- 剰余系における楕円曲線のスカラー倍算が公開鍵暗号に利用される理由
- Bitcoin で用いられる secp256k1 楕円曲線のパラメータ
ECDSA デジタル署名の署名方法:
- デジタル署名 r, s を導出する手順
- 一時的な秘密鍵（乱数）の生成と、署名 r, s の計算方法
ECDSA デジタル署名の検証:
- 受信したデータが改竄されていないか検証する方法
ECDSA デジタル署名のエンコーディング:
- ASN.1 という共通の方法でエンコードする必要性
ECDSA デジタル署名生成の際の注意点:
- 署名生成時に使用する乱数の重要性
- 同じ乱数を二度使用してはいけない理由

楕円曲線暗号とは

グループ（群）ってなんですか？

べ、別にアンタのために教えてあげるわけじゃないんだからね！勘違いしないでよね！

今回は暗号を計算する方法を覚えるんだけど…基本的には、足し算をするだけなの。でも、紙に書いて計算するのとは違う、限りある数字で行う足し算なわけ。すると、私たちがふだん使っている足し算とはべつの足し算を考えなきゃいけないの。

限りある数字で足し算をするってことはね…そうね、アナログ時計を見てみなさい。時計は時間が経つごとに足し算をする機械よね？たとえば、1 時間経ったら短針が目盛りひとつぶんずれていくわけ。

でも、目盛りは無限にあるわけじゃないから、無限に数え上げるわけにはいかないの。扱える値の数は決まっているわけ。アナログ時計の場合、1 から 12 までね。

じゃあ、11 時のとき 3 時間あとを考えることはできないのかしら…って、そんなわけないわよね。11 時の 3 時間あとは、針が 12 を飛び越えて回って、2 時になるでしょ。

これがグループ（群）なの。無限の値を扱わなくても、時計の針みたいにぐるっと回る工夫をすることで、足し算をすることができるの。

実際にはどんなふうに計算するのですか？

さっきのアナログ時計のたとえで考えるわね。11 時に 3 時間を足したいけれど、扱える値の限界「12」を飛び越えてしまう状態ってこと。

まずはふつうの足し算をしてしまうの。11 + 3 = 14 ね。これくらいはわかるでしょ？

でも、このままでは扱える限界の数「12」を超えてしまっているから、12 で割ったあまりを求めるの。14 ÷ 12 = 1 あまり 2 になるわね。これで、11 時の 3 時間あとは 2 時だってわかるわけ。

これを数式では「14 ≡ 2 (mod 12)」って書くの。「14 は 2 になる（12 で割るとね）」ってこと。

暗号分野ではこういう、割り算した余りをよく使うの。なぜそんなことするかって？それはね…

計算が複雑になるから！ 普通の数の世界で計算するよりも、余りの世界で計算する方が、計算がぐちゃぐちゃになって、元の数を推測するのがめっちゃ難しくなるのよ！
でも、計算自体はできる！ 複雑だけど、足し算とか掛け算とか、必要な計算はちゃんとできるの。

「割り算した余りの世界」を「余剰系」って呼ぶわ。よく使うから覚えておきなさいよね！

割り算の結果として出てきた 1 は、今回は使わないわ。あくまで時計の針がどこを指すかが問題で、一回転したかは関係ないの。

特殊な足し算について教えてください。

えーと、その特殊な足し算ってのは、楕円曲線ってやつで使うの。数式は $y^2 = x^3 + ax + b$ ってなってて、グラフにすると何かこう、丸っこい不思議な形になるのよ。

で、この曲線の上で「足し算」をするんだけど、普通の足し算とは全然違うの。

まず、曲線の上に 2 つの点 P と Q があるとするわ。
その 2 つの点 P と Q を直線で結ぶの。P と Q が同じ点だったら、その点での接線を引くのよ。
そうすると、その直線がまた楕円曲線とどこかで交わるでしょ？
その交わった点を x 軸に対してひっくり返した点（x 軸対称な点）が、P + Q の結果になるってわけ。

…ま、まぁ、簡単に言うと、そんな感じよ。

なんでこんなことするのかって？それは…その方が色々都合がいいからよ！特に暗号とかでね。

わ、わかった？別にアンタが理解できたかどうか、気にしてないんだからね！

剰余系における…なんですかこれは？

剰余系ってのは、簡単に言うと「割り算した余りの世界」のことよ。例えば、7 を 3 で割った余りは 1 でしょ？これを「7 ≡ 1 (mod 3)」って書くの。

で、楕円曲線ってのはさっき言った通り、特殊な足し算ができる曲線なわけ。この足し算を何回も繰り返すことを「スカラー倍算」って言うの。つまり、ある点 G を何回も足し合わせるってこと。

ここで重要なのは、この計算を「剰余系の世界」で行うってこと！つまり、計算結果をある数（素数）で割った余りで考えるの。

なぜそんなことするかって？それはね…

計算が複雑になるから！ 普通の数の世界で計算するよりも、余りの世界で計算する方が、計算がぐちゃぐちゃになって、元の数を推測するのがめっちゃ難しくなるのよ！
でも、計算自体はできる！ 複雑だけど、足し算とか掛け算とか、必要な計算はちゃんとできるの。

つまり、ある数 n と点 G から、nG（G を n 回足したもの）を計算するのは簡単だけど、nG と G から n を逆算するのは、ほぼ不可能になるの！これが「楕円曲線上の離散対数問題」ってやつよ。

この性質を利用して、n を秘密鍵、nG を公開鍵にする公開鍵暗号が作れるってわけ。秘密鍵から公開鍵を作るのは簡単だけど、公開鍵から秘密鍵を割り出すのは超難しい！だから安全に暗号通信ができるのよ。

ビットコインで用いられるパラメータを教えてください。

ビットコインで使われてる secp256k1 って楕円曲線は、さっき言った $y^2 = x^3 + ax + b$ の形をしてるんだけど、ちょっと特殊で、 $a$ が 0、 $b$ が 7 なの。つまり、式は $y^2 = x^3 + 7$ ってことになるわ。

で、この曲線の上で計算するための基準点 G ってのがあって、これはものすごーく大きな数なのよ。

G の座標 (x, y) は、こんな感じ。

$x = 55066263022277343669578718895168534326250603453777594175500187360389116729240$

$y = 32670510020758816978083085130507043184471273380659243275938904335757337482424$

…って、こんなの覚えられるわけないでしょ！

あと、この計算は「余りの世界」で行うって言ったわよね？その時に使う素数 p も決まってて、これもまたとんでもなく大きな数なの。

$p = 115792089237316195423570985008687907853269984665640564039457584007908834671663$

さらに、G を何回足したら「無限遠点」っていう特別な点になるかっていう回数 n も決まってて、これもまたまた大きな数。

$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

…もういいでしょ？こんなの全部覚える必要ないわよ！

要するに、ビットコインでは、こういう複雑なパラメータを使って、安全な暗号を実現してるってこと。

無限遠点

無限遠点っていうのは、楕円曲線上の特別な点のことで、記号では $\mathcal{O}$ （オー）って書くことが多いわ。

この点は、普通の座標 (x, y) で表すことができないの。だって、無限の彼方にある点だから！

で、何が特別かって言うと、楕円曲線上の足し算で、この無限遠点を足すと、何も変わらないのよ。つまり、どんな点 P に対しても、

$P + \mathcal{O} = P$

が成り立つってわけ。足し算の世界で言うと、0 みたいな存在ね。

あと、ある点 P とその逆元（x 軸対称な点）を足すと、必ず無限遠点になるの。

$P + (-P) = \mathcal{O}$

この無限遠点があるおかげで、楕円曲線上の点がグループ（群）っていう数学的な構造になるのよ。

ECDSA デジタル署名の署名方法

デジタル署名 r, s を導出する手順を教えてください。

デジタル署名 r と s を導出する手順ね…別に難しくないわよ。

まず、メッセージを用意するの。 これは、送りたい内容のことね。
そのメッセージをハッシュ関数に通すわ。 ハッシュ関数ってのは、どんなデータでも一定の長さのめちゃくちゃな文字列（ハッシュ値）に変える魔法の箱みたいなものよ。
次に、秘密鍵を用意するわ。 これは、自分だけが知ってる秘密の数字ね。
そして、一時的な秘密鍵（乱数）を生成するの！ これが超重要！絶対に他の署名で使っちゃダメよ！
一時的な秘密鍵を使って、楕円曲線上の点を計算するわ。 さっき言った基準点 G を一時的な秘密鍵の回数だけ足し合わせるの。
その点の x 座標が、署名 r になるわ。
最後に、署名 s を計算するの。 これはちょっと複雑な計算式を使うんだけど…まぁ、いいわ。

要するに、

一時的な秘密鍵（さっき作った乱数）を k とするわ。
楕円曲線上の点 kG を計算するの。G は基準点ね。

$r = (kG)_x$

秘密鍵を d とするわ。
k はさっき出てきた一時的な秘密鍵ね。

$s = \frac{Hash + d * r}{k} \pmod{p}$

…みたいな感じよ。

これで、署名 r と s が完成！この 2 つをメッセージと一緒に送れば、相手はアンタが本当にそのメッセージを作った人だって証明できるってわけ。

ECDSA デジタル署名の検証

受信したデータが改竄されていないか検証する方法を教えてください。

データが改竄されていないか検証する方法ね…別に難しくないわよ。

まず、データと、その公開鍵を受け取るの。
次に、データからハッシュ値を計算するわ。これは、署名を作った時と同じハッシュ関数を使うのよ。
そして、そのデータの署名 r と s を取り出すの。
最後に、以下の式を計算するわ。ここで、計算した Q の x 座標が、署名 r と一致するかどうかを確認するの。

$Q=\frac{Hash * G}{s} + \frac{r * pubKey}{s} \pmod{p}$

Hash: データのハッシュ値
G: 楕円曲線上の基準点
s: 署名
r: 署名
pubKey: 公開鍵
p: 剰余系の素数

もし一致すれば、データは改竄されていないってこと。もし一致しなければ、誰かがデータを書き換えたか、署名が間違っているってことになるわ。

ECDSA デジタル署名のエンコーディング

ASN.1 ってなんですか？

ASN.1 っていうのは、データを整理して、誰が見ても同じように理解できるようにするための共通のルールみたいなものよ。

例えば、アンタが友達に「りんご 3 個とみかん 5 個買ってきて」って頼んだとするわ。でも、もし友達が「みかん 3 個とりんご 5 個」って間違えて買ってきたら困るでしょ？

ASN.1 は、この「りんご 3 個、みかん 5 個」っていう情報を、誰が見ても「りんご 3 個、みかん 5 個」ってわかるように、きちんと整理して表現するためのルールなの。

コンピュータの世界でも同じで、デジタル署名とか暗号鍵とか、いろんなデータをやり取りする時に、コンピュータの種類や OS が違っても、同じように理解できるようにする必要があるの。

もし、データの表現方法がバラバラだったら、あるコンピュータでは正しく署名できたのに、別のコンピュータでは署名が間違っているってことになっちゃうかもしれないわ。

だから、ASN.1 っていう共通のルールを使って、データをきちんと整理して表現することで、どんなコンピュータでも同じようにデータを理解できるようにしているのよ。

ECDSA デジタル署名生成の際の注意点

署名生成時に使用する乱数ってどんなものでもいいの？

ダメよ！

署名を作るときに使う乱数は、めちゃくちゃ重要なの！

例えるなら、秘密の宝箱を開けるための、一度しか使えない特別なカギみたいなものよ。

もし、このカギを誰かに知られちゃったり、同じカギを何度も使ったりしたら…どうなると思う？

そう、宝箱の中身を盗まれちゃうわよね！

デジタル署名の場合、宝箱の中身はアンタの秘密鍵よ。もし、乱数がバレちゃったり、同じ乱数を何度も使ったりすると、悪い人に秘密鍵を計算されちゃう可能性があるの！

秘密鍵がバレたら、アンタの代わりにトランザクションを作ったり、アンタのお金を盗んだり、何でもできちゃうわ。

だから、乱数は、

絶対に誰にも教えない！
絶対に同じ乱数を二度と使わない！
安全な方法で生成する！

この 3 つを絶対に守らないとダメよ！

なんで二度使ってはいけないのですか？

同じ乱数を二度使っちゃダメな理由ね…別に難しくないわよ。

もし、同じ乱数を 2 つの異なるトランザクションで使っちゃったとするわ。

そうすると、署名 r は同じになるの。

で、署名 s は、

$s = \frac{Hash + d * r}{k} \pmod{p}$

で計算するでしょ？

もし、悪い人が 2 つのトランザクションのハッシュ値と署名 r と s を知っていたら…

連立方程式を解くみたいにして、乱数と秘密鍵を計算できちゃうのよ！

秘密鍵がバレたら、アンタのお金を盗んだり、何でもできちゃうわ。

だから、同じ乱数を二度使うなんて、絶対にダメ！

おわりに

ふん、別にアンタのために書いたんじゃないんだからね！勘違いしないでよね！

この文書では、楕円曲線暗号の基本から、ECDSA デジタル署名の仕組み、そして署名生成時の注意点まで、幅広く解説したわ。

最初は難しいと感じたかもしれないけど、ちゃんと理解できたかしら？

特に、署名生成時に使用する乱数の重要性は絶対に忘れないでよね。

…ま、まぁ、この知識がアンタの役に立つなら、別に嬉しいわけじゃないんだから！

参考にしたのは ECDSAデジタル署名の仕組みよ。etaro 氏には感謝しなさいよね！