Digital Signature Algorithm

Digital Signature Algorithm（デジタル シグネチャー アルゴリズム、DSA）は、デジタル署名のための連邦情報処理標準である。1991年8月にアメリカ国立標準技術研究所 (NIST) によってDigital Signature Standard (DSS) での利用を目的として提唱され、1993年にFIPS 186として標準化された。2013年までに4度の改訂を経ている（1996年：FIPS 186-1、2000年：FIPS 186-2、2009年：FIPS 186-3、2013年：FIPS 186-4）。FIPS 186-5では、DSAは新たにデジタル署名を行うことには推奨されないが、標準策定以前に行われた署名の検証には引き続き利用可能とされる。DSAはElGamal署名の改良版の一つであり、それと同様に離散対数問題の困難性に基づく電子署名方式である。

DSAは、かつてNSAに勤めていたDavid W. Kravitzによる1991年7月26日の特許（アメリカ合衆国特許第 5,231,668号）によってカバーされている。この特許は「ワシントンD.C.に所在する、商務長官に代表されるアメリカ合衆国」に提供され、NISTが全世界にロイヤリティフリーで開放した。Claus P. Schnorrは、DSAは彼の特許（アメリカ合衆国特許第 4,995,082号、失効済み）によってカバーされていると主張したが、この主張に対しては異議が唱えられている。

鍵生成

鍵生成は2つのフェイズに分けられる。1つ目は他者と共有されるパラメータの選択であり、2つ目は公開鍵および秘密鍵の生成である。

署名

ハッシュ関数を ${\displaystyle H}$、署名したいメッセージを ${\displaystyle m}$ とする。

• ${\displaystyle 0<k<q}$ なる ${\displaystyle k}$ をメッセージごとにランダムに決定する。
• ${\displaystyle r=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$ を計算する
• もし ${\displaystyle r=0}$ である場合には ${\displaystyle k}$ を選択し直す。
• ${\displaystyle s=k^{-1}\left(H\left(m\right)+xr\right){\bmod {\,}}q}$ を計算する(${\displaystyle k^{-1}}$ は有限体${\displaystyle F_{q}}$ における ${\displaystyle k}$ の逆元である)。
• もし ${\displaystyle s=0}$ である場合には ${\displaystyle k}$ を選択し直す(これは ${\displaystyle H\left(m\right)+xr}$ が ${\displaystyle q}$ の倍数の場合に起こる、非常なレアケースであり、${\displaystyle k}$ を変えることにより ${\displaystyle r}$ が変わり、${\displaystyle s}$ が 0 でなくなる可能性が高い)。
• ${\displaystyle \left(r,s\right)}$ が ${\displaystyle m}$ に対する署名となる。

最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。${\displaystyle k^{-1}{\bmod {\,}}q}$ が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは ${\displaystyle k^{q-2}{\bmod {\,}}q}$ としてフェルマーの小定理を用いて計算されることがある。

検証

メッセージ ${\displaystyle m}$ と署名 ${\displaystyle \left(r,s\right)}$ の検証は以下のように行われる。

• ${\displaystyle 0<r<q}$ かつ ${\displaystyle 0<s<q}$ を満たさない場合には拒否する。
• ${\displaystyle w=s^{-1}{\bmod {\,}}q}$ を計算する。
• ${\displaystyle u_{1}=H\left(m\right)\cdot w\,{\bmod {\,}}q}$ を計算する。
• ${\displaystyle u_{2}=r\cdot w\,{\bmod {\,}}q}$ を計算する。
• ${\displaystyle v=\left(\left(g^{u_{1}}y^{u_{2}}\right){\bmod {\,}}p\right){\bmod {\,}}q}$ を計算する。
• ${\displaystyle v=r}$ であれば署名は正当なものである。

DSAはElGamal署名の改良版であり、類似している。

アルゴリズムの正当性

DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。

署名者は次式を計算する。

${\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}$

ゆえに

${\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}$

前述のように g^q ≡ 1 (mod p) であるから

${\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u1}y^{u2}{\pmod {p}}\end{aligned}}}$

最終的に、DSAの正当性は以下に示される。

${\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u1}y^{u2}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}$

ランダム値の選択方法と安全性

DSAにとって、署名の際のランダム値 k のエントロピー、機密性、唯一性は決定的に重要である。これら3つのうちの1つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい。k として同じ値を二度用いること（k を秘密にしていたとしても）、予測可能な値を用いること、複数の署名に対するそれぞれの k が数ビットであっても漏洩することは、DSAを破るには十分である。

• エントロピー(情報理論的エントロピー)：k のエントロピーは kを 1 から q-1 の間から選ぶ際のランダムさの偏りのなさを表す値(単位はビット)であり、大きいほど好ましい。常に同一の kを使い続ける場合にエントロピーは最小値0となり、最も秘匿性が脆弱になる。全くランダムに選ぶ場合はエントロピーは最大値 ${\displaystyle \log _{2}(q-1)}$ (ビット)となり、これは鍵長Nにほぼ等しい。
• 機密性：k は署名者側のアルゴリズムでだけ使われる整数値であり、外部に送信してはならない。k の値が外部に漏れた場合、攻撃者は外部に送信される m, r, s から

${\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}$

によって秘密鍵 x の値 を計算可能になる。

• 唯一性：同一の署名者は同じ k を用いて2つ以上の異なるメッセージに対して r, s を計算し送信してはならない。${\displaystyle r=(g^{k}{\bmod {\,}}p){\bmod {\,}}q}$ により k が同じであれば、 r も同じであるので、攻撃者は同じ k を用いて計算された署名を容易に見破ることができる。今、同一の署名者が2つの異なるメッセージ m_A と m_B に対して同じ k を用いて署名 (r, s_A) と (r, s_B) を計算および送信し、攻撃者が2つのメッセージと署名を入手できたとすると、

${\displaystyle s_{A}=k^{-1}(H(m_{A})+xr){\bmod {\,}}q}$

${\displaystyle s_{B}=k^{-1}(H(m_{B})+xr){\bmod {\,}}q}$

であるから、上の2式の差を取ると xr の項が相殺されてしまい、

${\displaystyle s_{A}-s_{B}=k^{-1}(H(m_{A})-H(m_{B})){\bmod {\,}}q}$

となり、k の値が計算可能になる。k の値が分かれば上述のように秘密鍵 x の値も計算可能になる。

2010年12月、fail0verflow と名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていた楕円曲線DSAの秘密鍵の回復に成功したと発表した。これは、ソニーが署名ごとに新しいランダムな k を用いていなかったためである。

唯一性の問題は、RFC 6979にあるように、秘密鍵 x とメッセージハッシュ H(m) から決定論的に k を導くことで回避できる。これにより、k がそれぞれの H(m) に対して異なることと、秘密鍵 x を知らない攻撃者にとって予測不能であることが保証される。

実装ライブラリ

DSAをサポートしているライブラリは以下のものがある。

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• libcrypt
• libsodium
• Nettle
• OpenSSL
• wolfSSL
• GnuTLS

脚注

関連項目

• 楕円曲線DSA
• ElGamal署名
• 合同式

外部リンク

• FIPS PUB 186-4: Digital Signature Standard (DSS), the fourth (and current) revision of the official DSA specification.
• Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63

表 話 編 歴 公開鍵暗号 アルゴリズム Cramer-Shoup暗号 ディフィー・ヘルマン鍵共有 楕円曲線ディフィー・ヘルマン鍵共有 Digital Signature Algorithm 楕円曲線DSA（ecdsa） エドワーズ曲線DSA（Ed25519） ElGamal暗号（ElGamal署名） EPOC (暗号) Merkle-Hellmanナップサック暗号 NTRU暗号 Paillier暗号 Rabin暗号 RSA暗号 ランポート署名 理論 離散対数 素因数分解 楕円曲線暗号 標準化 CRYPTREC IEEE P1363（英語版） NESSIE NSA Suite B（英語版） CNSA 関連項目 デジタル署名 Optimal Asymmetric Encryption Padding 指紋 公開鍵基盤 ゼロ知識証明

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ