はじめに
個人的に、前からDSAの計算内容は知っていたものの、ECDSAはややこしそうなので敬遠していたのですが、名前が共通である以上、仕組みも似たようなものだろうと思って調べたらその通りだったので、整理してみます。
事前知識
mod nの世界
今回の話にはmod nの世界での計算が出てきます。というか、そればかりです。
当然知っているよ、ということであれば次まで読み飛ばして頂いて構いません。
mod nの世界というのは、要は計算結果を全て n で割った余りで見ましょう、というものです。
このことを明示する場合、等号を $\equiv$ ( 否定なら $\not\equiv$ ) で書きます。
例えば、13, 35 はどちらも 11で割って余りが同じ2になる数なので、次のように表現します。
13 \equiv 35~mod~11
実際には「余りが同じ」と見ると「マイナスの数どうすんの?」という点が不安になるかも知れないので、差がnの倍数と考えた方がすっきりします。
例えば 8, -6 は mod 7 でどうか? と言われたら $8-(-6)=14$ が7の倍数であるため、両者は mod 7 の世界では等しい、つまり $8\equiv -6~mod~7$と言うことです。
##mod nでの演算
さて、重要なのは演算です。が、足し算・引き算・掛け算はそのまま結果の余りを見れようにすれば済みます。
例えば mod 10 での足し算ですが、$5+8\equiv 3~mod~10$です。なぜならば$5+8=13$を10で割った余りは3だから。
が、これにはもっと強い主張が含まれています。それは余りが5である数、8である数の組み合わせならば、なんであれ足し合わせれば余りが3の数になるということです。これは、引き算・掛け算でも同様です。
ここで問題になるのは割り算です。「余りが2になる数を余りが3になる数で割って、その余りが…??」と。余りだけで考えていては訳が分かりません。
なので、割り算は掛け算の逆演算であるという考えに立ち返って、$a\times b\equiv c\Leftrightarrow c/a\equiv b$ と見做します。
或いは、小学校での分数の掛け算で「割り算は逆にしてかけるんや!」と習ったように、$a\times a^{-1}\equiv 1$ となる数、mod の世界での逆数$a^{-1}$を掛けるということで、
a\times b\equiv c\Leftrightarrow c/a\equiv b \Leftrightarrow c\times a^{-1}\equiv b
というようにします。割り算記号 / だと、素の割り算なのか、mod での割り算なのか区別が付け辛いので$a^{-1}$を使う書き方も分かり易いかと思います。
実際の例として、$4\times 3\equiv 5~mod~7,~~4\times 2\equiv 1~mod~7$ですから、割り算の結果が次のようになります。
\begin{eqnarray}
&~&4\times 3&\equiv& 5&mod~7& \\
&\Leftrightarrow&5/4&\equiv&5\times 4^{-1}\equiv 5\times 2\equiv 3&mod~7&
\end{eqnarray}
ただし、割り算の場合には1つ大事な注意事項があります。
それは、mod n の n の数によっては、割り算の結果が一意に定まらなかったり、或いは結果がなかったりするケースが出てくるということです。
例えば mod 6 の場合、$2\times 2\equiv 2\times 5\equiv 4~mod~6$ と、掛け算の結果が同じになるパターンがあるので、じゃあ$4/2\equiv 2,~4/2\equiv 5$のどっちなの? と。或いは、両辺の偶奇を比較すれば$x\times 2\equiv 1~mod~6$になるxは明らかに存在しないわけで、つまり$1/2$は計算できません。
なので、mod n での割り算を定義するのは、このような「一意に定まらない」「結果がない」ということがない n の場合に限ります。これはn が素数である場合に限るということが分かっています。
もちろん、それでも「0 による割り算」、mod n の場合なら「nの倍数による割り算」ができないという性質だけは一般の数に対する割り算と同じなので、そこは除外しておきます。
なお、じゃあ割り算だけは足し算・引き算・掛け算のように単純に行かないところ、どうやって計算するの? という話になるわけですが、そこはユークリッドの互除法を拡張することで逆数が計算できることが分かっています。
ユークリッドの互除法は2数の最大公約数を求めるアルゴリズムですが、これを拡張することで、「$ax+by=gcd(a,b)$を満たす(x,y)を1組求める」ことができます。
$a\not\equiv 0~mod~p$であれば$gcd(a,p)=1$ですから、$ax+py=1\Leftrightarrow ax\equiv 1~mod~p\Leftrightarrow x\equiv a^{-1}~mod~p$と、$b=p$とした場合のxがそのままmod p におけるaの逆数になっているということです。
この拡張については拡張ユークリッド互除法等をご参照ください。
有限体
以上のように mod の世界での演算を定めると、素数 p に対して 0～p-1 という p要素の有限の集合が、加減乗除の演算を備えた体という構造になります。
有限なので有限体 ( Finite field )、或いはガロア体 ( Galois Field ) の一種ということです。なので、これを$F_p$或いは$GF(p)$という記号で表します。
体になると何が嬉しいかというと、高校までで習った数、これらも有理数体$Q$や実数体$R$、場合によっては複素数体$C$といった何らかの体に所属する要素なわけですが、そういった数に対する計算を ( 全部ではないにせよ ) そっくりそのまま引き継げる、というところです。
ということで、以下の話では、普通の数に対する計算のように書いていても、この$GF(p)$に対する計算なんだ、と。そう見て頂ければ、と思います。
DSA/ECDSAの数的構造
有限群とべき乗
DSA/ECDSAを考えるにあたり、何かしらの有限群というものがベースになります。
事前知識で出てきた有限体と被るところではあるのですが、求められる条件はもっと少なくいです。が、詳しいことはここでは触れません。
ただここで、演算 $\circ$ とその演算に対する単位元が$\epsilon$である有限群$(G,\circ,\epsilon)$を考えます。
なお、単位元というのは$\alpha\circ\epsilon=\epsilon\circ\alpha=\alpha$というように、演算結果が相方の要素そのものになる特殊な要素ですね。この$\epsilon$に限らず、群の要素に関しては以降ギリシア文字で表現します。整数やらと区別がつくようにです。
このとき$\circ$を複数回適用する、いわば通常の数に対するべき乗に相当する計算もできるはずです。べき乗の表現をそのまま借りて書くことにします。
\omega^n=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}_{n個}
これを、( 群が有限なので ) 離散べき乗ということもあるらしいのですが、単にべき乗と呼んでおきます。
…ちなみに、右肩に乗っている数、幾つの要素を演算につぎ込んでいるかを表す**整数 ( 群の要素ではなく )**なのですが、これは指数と呼んでおきます。
特別なケースとして、$\omega^0=\epsilon,~\omega^1=\omega$ です。
指数が負の整数の場合の演算も考えることはできるのですが、今回は割愛します。
べき乗の性質
さて、べき乗を考えると何が嬉しい、といいますか都合のいいことがあるかというと、$\circ$による演算と指数部分の整数の足し算・掛け算とをリンクして考えることができる、ということです。
中学か高校で ( 掛け算に基づくべき乗の ) 指数法則というのを習わなかったでしょうか。
x^n\times x^m=x^{n+m} \\
(x^n)^m=x^{n\times m}
つまり、
(\underbrace{x\times\cdots\times x}_{n個})\times(\underbrace{x\times\cdots\times x}_{m個})=\underbrace{x\times x\times \cdots \times x}_{n+m個} \\
(\underbrace{\underbrace{x\times \cdots\times x}_{n個})\times\cdots\times(\underbrace{x\times\cdots\times x}_{n個})}_{m組}=\underbrace{x\times x\times\cdots x}_{n\times m個}
と、丁度個数をまとめられるような内容です。
これと同じことが、演算$\circ$でも言えて、次のように$\circ$の演算が指数の足し算・掛け算に置き換わっています。
\omega^n\circ\omega^m=\omega^{n+m} \\
(\omega^n)^m=\omega^{n\times m}
実際にこの性質というのは、公開鍵暗号の中でも鍵交換と呼ばれる方式、DH/ECDH法で使われています。DH/ECDHも内部的に有限群の演算を活用しているのです。
A,Bの両者が秘密裡に整数a,bをそれぞれ用意して、公開しても良い共通の要素$\gamma$に対して、$\alpha=\gamma^a,~\beta=\gamma^b$を ( 公に ) 交換すれば、互い違いの情報の組み合わせにも関わらず、
- A: ${\sigma}_A=\beta^a=(\gamma^b)^a=\gamma^{b\times a}$
- B: ${\sigma}_B=\alpha^b=(\gamma^a)^b=\gamma^{a\times b}$
と、両者がそれぞれ計算した${\sigma}_A,~{\sigma}_B$が一致し、結果両者だけで秘密の情報を共通できている、という寸法です。
離散対数問題
ということで、有限群に対するべき乗が以降、演算の中心となっていくのですが、その逆についても注意を払う必要があります。
\omega^n=\alpha \Rightarrow n=??
つまり、べき乗の結果が分かっている時にさて指数は何だったんだろうかという、べき乗の逆演算に相当するものです。
高校では、実際に掛け算ベースのべき乗の逆演算として**対数 ( log )**という演算が出ていたかと思います。例えば次のように。
2^5=2\times 2\times 2\times 2\times 2=32 \Rightarrow log_{2}{32}=5
それになぞらえて、有限群に対するべき乗の逆演算は離散対数と呼ばれます。
問題は、この離散対数が、高校で習う log のように簡単に計算できてしまうと困るということです。
これは先ほど紹介したDH/ECDHにしてもそうです。a,bをそれぞれ秘密にして$\alpha=\gamma^a,~\beta=\gamma^b$を公にしている以上、逆演算でa,bがバレてしまうと秘密もなにもなくなってしまうのです。
幸いなことに、世の中使われている有限群というのは、離散対数の計算が困難である ( 少なくとも現時点で平易に解く方法がない )、すなわち離散対数問題が困難であるものです。これが暗号としての計算の一方通行性を担保しているということにご留意ください。
※べき乗はバイナリ法という方法が知られているので、平易に計算できる。
DSA/ECDSAのパラメータ
さて、いよいよDSA/ECDSAについてです。
DSA/ECDSAの場合、有限群$(G,\circ,\epsilon)$に加え、$G$の$\epsilon$でない要素$\gamma$と素数 q を用意します。
ただし、$\gamma^q=\epsilon$ と、q乗した結果が単位元に等しくなるように、です。加えて、素数 q がなるべく大きくなる方が好ましいです。
そんなの都合よく見つかるの? という懸念もあるかもしれませんが、どんな要素であっても何乗かすれば、特にその指数を$G$の要素数 ( 位数と言います ) と一致させれば、必ず単位元$\epsilon$になります ( これは有限群の特徴です ) から、そこから作り出すことができます。
例えば、ある要素に対して $\omega^{582}=\epsilon$と分かったとすれば、$582=97\times 6$の 97 が素数ですから、$\gamma=\omega^6$に対して $\gamma^{97}=(\omega^6)^{97}=\omega^{97\times 6}=\epsilon$と、$(\gamma=\omega^6,q=97)$という組が作り出せます。
このような$\gamma$を作っておけば、$q$周期でべき乗が同じ値を繰り返します。もっと言うと、
a\equiv b~mod~q\Leftrightarrow \gamma^a=\gamma^b
と、べき乗にリンクする指数は mod q の世界、つまり事前知識で取り上げた有限体$GF(q)$の計算になります。
その上で、2つの関数を準備します。
- 1つはメッセージを変換する関数$f_z:M\rightarrow GF(q)$
なお、$M$は署名対象のメッセージの集合を表します。
と言っても、実態がなんであるかは特に今回気にしません。ただ、区別できるように名前をつけただけです。
これはメッセージのハッシュをとり、$GF(q)$の範囲に収めて計算対象にする処理に相当します。ただハッシュ値が容易に衝突すると問題なので、現実にはSHA系の暗号学的ハッシュを計算し、結果の上位桁を抽出するようになっています。 - もう1つは有限群の要素を射影する関数$f_p:G\rightarrow GF(q)$
こちらについての詳細は後で触れます。
以上がDSA/ECDSAの処理の前提となるパラメータです。再度整理すると、
- 有限群$(G,\circ,\epsilon)$
- $G$の要素$\gamma$および素数 q ただし、$\gamma^q=\epsilon$
- 2つの関数 $f_z:M\rightarrow GF(q),~~f_p: G\rightarrow GF(q)$
なお、これらは全て公開パラメータです。
DSA/ECDSAの処理
では、実際に署名に関わる処理です。
署名に必要な処理は3つあります。鍵ペアの生成、署名作成、署名検証です。それぞれ次のような計算を行います。
- 鍵ペア作成
$GF(q)$のランダムな数$x$を作成し、$\chi=\gamma^x$ とする。
以降、$x$は署名鍵として秘匿し、$\chi$は検証鍵として公開する。 - 署名作成
メッセージ$m$毎に、都度$GF(q)$のランダムな数$k$を作成し、署名鍵$x$を用いて次のように計算した$(r,s)$を署名とする。- $r=f_p(\gamma^k)$
- $s=(f_z(m)+x\times r)/k$
- 署名検証
元のメッセージ$m$と署名$(r,s)$と検証鍵$\chi$から以下のように$r'$を計算し、$r=r'$であることをもって検証成功と判断する。- $u_1=f_z(m)/s$
- $u_2=r/s$
- $r'=f_p(\gamma^{u_1}\circ \chi^{u_2})$
これらの処理で、検証鍵$\chi$から署名鍵$x$の推測が困難であること、$\gamma,\chi$のべき乗の計算をいじって署名$(r,s)$を偽造するのが困難であること、これらは全て離散対数問題の困難さを拠り所にしています。
なお、作成した署名が正しく検証されることは、関数$f_p$に通す前の$\gamma^{u_1}\circ \chi^{u_2}$が$\gamma^k$に一致するようにできていることから確かめられます。
\begin{eqnarray}
&~&\gamma^{u_1}\circ \chi^{u_2} \\
&=&\gamma^{u_1}\circ (\gamma^x)^{u_2} \\
&=&\gamma^{u_1+x\times u_2} \\
&=&\gamma^{f_z(m)/s+x\times r/s} \\
&=&\gamma^{(f_z(m)+x\times r)/s} \\
&=&\gamma^{(s\times k)/s}~~~\because s=(f_z(m)+x\times r)/k\Rightarrow f_z(m)+x\times r=s\times k\\
&=&\gamma^k
\end{eqnarray}
有限群での演算の内容
ここまで、DSA/ECDSA共に、有限群の演算を元に同じ計算を行っていることを整理したわけですが、では両者で異なるところ、その元となる有限群の演算の内容についても軽く触れてみたいと思います。
DSA
DSAの元となる有限群は、ある素数 p ( q より必ず大きい ) に対する、mod p での掛け算の群となります。端的に言えば$GF(p)$から数 0 を除いた $p-1$要素を、掛け算のみに限定したものと同じです。
ECDSA
ECというのがElliptic Curve ( 楕円曲線 ) を意味し、つまり楕円曲線上の点を要素とし、楕円曲線上の加算を演算とした群を使います。
ただ、一般に楕円曲線というとウナギめいた曲線なのですが、ECDSAでは座標に使う数を有限体の要素とし、有限個の点で有限群を構成します。
有限体としては、これまで出てきた、素数 p に対する有限体$GF(p)$も使われるのですが、それ以外にも$GF(2^n)$や$GF(p^n)$といったものも使われるようです。が、ちょっとそこまで手が回らないので、ここでは$GF(p)$での話とします。
つまり、方程式としては、$y^2\equiv x^3+a\times x+b~mod~p$と、mod p の世界を考えることになります。グラフにプロットすると見事にバラバラです。
ただそれでも、**無限遠点$O$**と呼ばれる特殊な要素が出てくるのは同じです。これが単位元、今回の話での$\epsilon$に相当します。
※ちなみに、$\gamma$に相当するのは基準点 ( ベースポイント ) G と呼ばれます。
さて、演算に関しては、( 無限遠点が絡まない場合 ) 楕円曲線上で同一直線上にある点同士を使って加算を定義します。これが$\circ$に相当します。
※ちなみに「べき乗」だと加算というイメージにそぐわないのか、楕円曲線でのべき乗に相当する演算は「スカラー倍算」
と呼ばれます
つまり、点$(x_1,y_1),(x_2,y_2)$があり、この2点を結ぶ直線が$y=u(x-x_1)+y_1$であるとき、もう1つの交点$(x_3,y_3)$に対して$(x_1,y_1)+(x_2,y_2)=(x_3,-y_3)$ と加算を定義します。y座標にマイナスが付くところに注意が必要です。
実際には$GF(p)$上の計算なので、視覚的には全くもって直線でもなんでもないのですが、数式的に直線の計算をそのまま流用しているわけです。
なお、この計算は3次方程式の解と係数の関係を利用することで、$x_3=u^2-x_1-x_2, -y_3=u(x_1-x_3)-y_1$ のように行えます。
直線の傾きに相当する$u$は、以下の計算で行います。
u=(y_1-y_2)/(x_1-x_2)=(x_1^2+x_1\times x_2+x_2^2+a)/(y_1+y_2)
なぜ2通りの形で表しているかというと、同じ点同士の加算 ( 2倍算と呼びます ) で$x_1=x_2$ の時に発生するゼロ除算の対策です。
もう1つの式でも、$y_1+y_2=0$ならやはりゼロ除算になってしまうのですが、その場合はゼロ除算にならない方を採用します。両方ゼロ除算になるとしても、それは結果が無限遠点になるケースですから、特に心配はいりません。
補足～関数fpの意味～
さて、詳細を保留にしていた関数$f_p$ですが、これも有限群の実態に沿って変わります。
- DSAの場合
$f_p(\omega)=mod(\omegaをそのまま数字として扱ったもの,q)$
※$GF(p)$の非ゼロ要素、$1\sim p-1$をそのまま数字とし、余りを計算する - ECDSAの場合
$f_p(\omega)=mod(\omegaのx座標の数値,q)$
※x座標もDSAの場合と同様に$GF(p)$の数だが、それをそのまま数字として扱い、余りを計算する
この$f_p$、作成する署名の中の$r$、署名検証の時に照らし合わせる$r'$の計算に使っているわけですが、なぜ有限群$G$の要素をそのまま比較せずにわざわざ$f_p$を通すのかと疑問に感じなかったでしょうか。
実はこの処理は、DSAの元となったElgamal署名から工夫されている部分でもあります。
どういうことかと言うと、$f_p:G\rightarrow GF(q)$この通す前後の集合では要素数がかなり少なくなっている、それによってデータを保持するのに必要な容量を節約するようにしているのです。
例えばオリジナルのDSAでは、$GF(q)$の数が、メッセージのハッシュSHA-1の160bit分しか情報量がない、つまり署名データの片割れ r も同様であるところに対し、有限群の要素は1,024bit の整数です。有限群の要素をそのままデータ化すると、本質的に必要でない部分に容量を喰われてしまうわけです。
ということで、$f_p$は署名データを作る時に$GF(q)$への変換で容量を節約する意図で設けられています。ただ、ECDSAの場合は$G$と$GF(q)$の要素数の違いはDSA程ではありませんし、技術的に絶対に必要か? というとそうでもないように思います。実際、後発の電子署名であるEdDSA(ed25519)では、同じ有限群の離散対数問題をベースにしていながら、$f_p$に相当する処理が含まれていないように見えます。
補足～乱数kの扱い～
ところで、署名作成の際に出てきた乱数$k$ですが…。「乱数」と言われると、じゃあ適当な数を選んでも良いのかと思われるかもしれませんが、実はこれも署名鍵$x$並みに秘匿すべきで、かつ乱数パターンを読まれてはならないデータだったりします。
というのも、$k$の漏洩は即座に署名鍵$x$の漏洩に繋がるからです。
署名作成時の$s$の計算式から、次のように$x$を計算できることが分かります。
\begin{eqnarray}
&~&s=(f_z(m)+x\times r)/k \\
&\Rightarrow& x=(s\times k-f_z(m))/r
\end{eqnarray}
なお、直接$k$が漏洩しなくとも、同じ$k$を使い回すのでもN.G.です。固定の$k$ ( 必然的に $r$も固定 ) によって生み出された2通りの署名から$k$を割り出すことができ、そこから先ほどと同様に署名鍵を計算することができます。
\begin{eqnarray}
&~&s_1=(f_z(m_1)+x\times r)/k, s_2=(f_z(m_2)+x\times r)/k \\
&\Rightarrow&s_1-s_2=(f_z(m_1)-f_z(m_2))/k \\
&\Rightarrow&k=(f_z(m_1)-f_z(m_2))/(s_1-s_2)
\end{eqnarray}
ということで、$k$には単なる乱数以上のものが求められます。そのためか、先ほども出たEdDSAでは$k,r$に相当するデータとして単純な乱数ではなく、メッセージや署名鍵のデータを混合してハッシュを通したものを使うようにして、この点を改良しているようです。
終わりに
ということで、DSA/ECDSAとも、群の内容の違いはあれど、本質的には同じ処理を行うものであることを説明してきました。
それぞれの署名の方式の説明にはもっと詳しいものがあると思いますが、あまりこういう観点で説明しているのはないのではないかと思います。
本当は、今回紹介した内容をデモンストレーションするちょっとしたコードも載せようと思ったのですが、予想より分量が膨らんでしまったため、改めて別記事にしようと思います。
→ 別記事は電子署名DSA/ECDSAの数的構造(2/2)