ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

楕円曲線入門 (4)

Cryptography

前回(第3話)までで基本的な楕円曲線の解説を終えた(多分).

本稿では, 楕円曲線を用いた署名アルゴリズムについて解説する.


Elliptic Curve Digital Signature Algorithm

楕円曲線を使ったデジタル署名(DSA)のアルゴリズム.
まずはデジタル署名とは何か, また何のために使われるのかを解説する.


デジタル署名

先にデジタル署名の役割を言うと, 送り主が誰であるかとデータが改ざんされていないことを証明する.

データの送り主について着目し, 次のようなシナリオを考える.
AliceがBobになにか重要なファイル(データ)を送信したとする. この例ではファイルが暗号化されているかどうかは考慮しない.

Bobが受け取ったファイルが, Aliceから送られてきたものなのかを本人に確認すると,

Bob 「これお前が送ったデータやんな？」

Alice 「ちゃうでw(違わない)」

違うと言われてしまった. どうやら違うようだ.

このような否認がインターネット上で自由に行われることは, 到底許されるべきではない. そこでデジタル署名を用いることで, 否認の対策を行うこととした.
これで, Aliceがいくら自分が送ったファイルではないと言い張っても, デジタル署名がAliceのものであると立証してくれているので嘘がつけなくなった. めでたしめでたし.
実際に使われる署名アルゴリズムとしてはRSAなどが有名である.

ECDSA

さて, 話を楕円曲線に戻す.
これより楕円曲線を使ってデジタル署名を行う手順を解説する.

準備

利用する楕円曲線 \(EC := y^{2} = x^{3} + Ax + B\) を定義.
\(EC\)上の点を\(G\), \(G\)の位数を\(n\)とする. 位数が\(n\)なので, \([n]G = O\)が成り立つ.

ただし, \(n\)は素数である必要がある. \(Modulus\)でなく位数が素数である点に注意.
つまり, \(Modulus\)と\(n\)が両方とも素数である楕円曲線(とベースポイント\(G\))を選択する必要がある.

次にAliceは\([1, .., n-1]\)の中から適当な\(d_{A}\)を選択して, \(Q_{A} := [d_{A}]G\) を計算しておく.

\((Curve, G, n, Q_{A})\)が公開されている情報である.

署名

mをメッセージとする.

\begin{eqnarray} e &:=& SHA256(m) \newline k &:=& randint(1, n-1) \newline (x_{1}, \, y_{1}) &:=& [k]G \newline r &:=& x_{1} \, mod \, n \end{eqnarray} \(r\)は楕円曲線上の計算の時点で\(x_{1} < n\)だが念の為.

$$ s := k^{-1}(e + rd_{A}) \, mod \, n $$

\((r, s)\)が署名となる.

\(e\)の導出にSHA256を使用しているが, 署名/検証で同じハッシュ関数を使用するのであれば他のものを利用しても良い.

検証

受け取ったメッセージを復号したものをmとする.

\begin{eqnarray} e &:=& SHA256(m) \newline w &:=& s^{-1} \, mod \, n \newline u &:=& ew \, mod \, n \newline v &:=& rw \, mod \, n \newline \end{eqnarray}

\((u, v)\), ベースポイント\(G\)とAliceが署名した\(Q_{A}\)を使って $$ (x_{2}, \, y_{2}) := [u]G + [v]Q_{A} $$

\(r \equiv x_{2} \, mod \, n\)であれば署名は有効である.

正当性

以上の手順で正しく検証ができることを確かめる.
先ほどの式を変形していこう.

\begin{eqnarray} [u]G + [v]Q_{A} &=& [u]G + [v][d_{A}]G \newline &=& [u + vd_{A}]G \newline &=& [ew + rwd_{A}]G \newline &=& [w(e + rd_{A})]G \newline &=& [s^{-1}(e + rd_{A})]G \newline &=& [(k^{-1})^{-1}(e + rd_{A})^{-1}(e + rd_{A})]G \newline &=& [k(e + rd_{A})^{-1}(e + rd_{A})]G \newline &=& [k]G \newline &=& (x_{2}, \, y_{2}) \end{eqnarray}

以上より, 署名と検証とで\(e\)が同じならば \(r \equiv x_{1} \equiv x_{2} \, mod \, n \) なので, 正しく署名の検証ができていることが示せた.

以下のコードでは\((e, d)\)を自分で作為的に選んでいるが, 署名については正しく検証できている.

ここではsageMathを使ったコードを載せているが, Golangで実行したものもあるので併せて載せておく. ECDSA by Golang (曲線や演算の定義により, 少し長いのでリンクだけ)

参考文献


To Be Continued..

乱数を使わない場合のECDSA -> 番外編
次->まだ