NAWASHIRO

ツンデレで学ぶECDSA署名

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

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

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

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

ただし！

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

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

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

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

レジュメ

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

楕円曲線暗号とは

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x=55066263022277343669578718895168534326250603453777594175500187360389116729240x = 55066263022277343669578718895168534326250603453777594175500187360389116729240

y=32670510020758816978083085130507043184471273380659243275938904335757337482424y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

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

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

p=115792089237316195423570985008687907853269984665640564039457584007908834671663p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

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

n=115792089237316195423570985008687907852837564279074904382605163141518161494337n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

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

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

無限遠点

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

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

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

P+O=PP + \mathcal{O} = P

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

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

P+(−P)=OP + (-P) = \mathcal{O}

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

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

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

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

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

要するに、

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

r=(kG)xr = (kG)_x

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

s=Hash+d∗rk(modp)s = \frac{Hash + d * r}{k} \pmod{p}

…みたいな感じよ。

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

ECDSA デジタル署名の検証

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

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

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

Q=Hash∗Gs+r∗pubKeys(modp)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=Hash+d∗rk(modp)s = \frac{Hash + d * r}{k} \pmod{p}

で計算するでしょ？

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

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

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

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

おわりに

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

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

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

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

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

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

Back Link

Back to Home