こんにちは。
前回は電子署名の基礎ということでRSA署名をご紹介しました。
今回は、それより少し難しいDSA署名についてご紹介します。
準備
法
前回、合同式\(a \equiv b \bmod m\)を説明しましたが、ここでの\(m\)のことを「法」といいます。英語でmodularといいます。modはここからきています。
位数
互いに素な整数\(a\)と正の整数\(m\)において、\(a^d \equiv 1 \bmod m\)となる中で最も小さい正の整数\(d\)のことを「位数」といいます。
元
集合の要素のことを元といいます。「整数」という集合があったとして、\(1,2,3\)などは元です。\(\frac{1}{2},\frac{1}{3}\)などは元ではありません。
群
集合があったとして、その中での演算が、
- 結合法則…\((a+b)+c=a+(b+c)\)のように、演算の順番が変わっても結果が同じになる
- 単位元…\(a+0=a\)における\(0\)とか、\(b \times 1=b\)における1みたいに、何回やっても結果が同じになる元
- 逆元…ある元とその逆元で演算すると単位元になる。\(a+(-a)=0\)や、\(b \times \frac{1}{b}=1\)のように。
これら3つの性質を満たすとき、群といいます。
例えば、整数\(\mathbb{Z}\)は加法\(+\)に関して群です。
群\((\mathbb{Z},+)\)のように表記します。
原始元
\(\bmod 5\)を考えます。「5未満の正の整数」という集合の元には例えば1,2がありますが、 \(\begin{eqnarray}
1^1 \bmod 5 &=& 1 \\
1^2 \bmod 5 &=& 1 \\
&\vdots & \\
\end{eqnarray}
\)
と、1の場合、答えは1しか出てきません。
一方で2の場合、
\(\begin{eqnarray}
2^1 \bmod 5 &=& 2 \\
2^2 \bmod 5 &=& 4 \\
2^3 \bmod 5 &=& 3 \\
2^4 \bmod 5 &=& 1 \\
&\vdots & \
\end{eqnarray}
\)
2の場合、1,2,3,4という「5未満の正の整数」という集合の元すべてが答えに出てきます。このような元を原始元といいます。
DSA署名の流れHをハッシュ関数とします。
\(H\)をハッシュ関数とします。鍵生成
- 鍵長\(L,N\)を決めます。
- \(N\)ビットの素数\(q\)をランダムに決めます。ハッシュ関数の出力長より小さくなければいけません。
- \(L\)ビットの素数\(p\)をランダムに決めます。ハッシュ関数の出力長より小さくなければいけません。
- \(h<p-1\)となるランダムな整数hを決めます。
- \(1≤x≤q-1\)となるランダムな数xを決めます。
- \(g=h^\frac{p-1}{q} \bmod p\)を求めます。
- \(y=g^x \bmod p\)を求めます。
この流れにより、公開鍵\(pk=(p,q,g,y)\)、秘密鍵\(sk=x\)が決められます。
公開鍵は検証鍵として、秘密鍵は署名鍵として使われます。
署名
- \(q\)未満の正の整数\(k\)をランダムに決めます。
- \(r=(g^k \bmod p) \bmod q\)を求めます。\(r=0\)になる場合は1.に戻ります。
- \(t=(H(m)+xr)k^{-1} \bmod q\)を求めます。\(t=0\)になる場合は1.に戻ります。
検証
- \(w=t^{-1} \bmod q\)を求めます。
- \(u_1=wH(m) \bmod q\)を求めます。
- \(u_2=rw \bmod q\)を求めます。
- \(v=(g^u_1y^u_2 \bmod p) \bmod q\)を求めます。
安全性
離散対数問題
例えば、\(2^{10} \bmod 19\)は簡単に解けますね。17です。逆に、\(2^x \equiv 17 \bmod 19\)となる\(x\)を求める（答えは10）ことはできるでしょうか？
これは、かなり時間がかかります。
正式に書くと、「\(p\)未満の正の整数」という集合を\(\mathbb{Z}_p\)として、素数\(p\)、群\((\mathbb{Z}_p,\times)\)の原始元\(g\)、群\((\mathbb{Z}_p,\times)\)の任意の元\(y\)に対して、\(y \equiv g^x \bmod p\)を満たす\(x\)が存在します。
この\(x\)を、\(y\)に対する離散対数といい、\(x\)を解くことを離散対数問題(Discrete Logarithm Problem, DLP)といいます。
これを多項式時間で解くアルゴリズムは見つかっていません。なので、離散対数問題は多項式時間で解けないという仮定を、離散対数仮定といいます。
この離散対数仮定が、DSA署名は安全だといえる根拠になります。
おわりに
群論の知識を必要としますが、本記事の「準備」節を読めばそれなりにわかってきたのではないでしょうか。
群論などの知識は前提としていきなり離散対数問題を紹介してる記事よりは、それなりにわかりやすくなるように書いたつもりなので、そうあってほしいです笑
次回はやっと、ブロックチェーンにも使われているECDSA署名についてご紹介します！
DSAとECDSAの関係はなんなのかと先にいうと、DSAに使っている群に、楕円曲線上の巡回群を使っているものこそがECDSA、ということになります。