ja.wikipedia.org

Digital Signature Algorithm - Wikipedia

  • ️Thu May 19 1994

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

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

パラメータ (p, q, g) を基に鍵ペアを生成する。

  • 0 < x < q なる x をランダムに選択する。
  • y = gx mod p を計算する。x と y の対応は1対1であり、x から y を計算することは比較的容易だが、y から x を計算することは実質的に不可能(離散対数問題)である。つまり x と y の対応は一方向性関数になっている。
  • 公開鍵は (p, q, g, y)、秘密鍵は x である。

冪剰余 h(p–1)/q mod p および gx mod p の効率的な計算法が存在する。冪乗#効率的な演算法を参照のこと。

パラメータ (p, q, g, y) は他者との間で共有される。例えば、公開鍵基盤(PKI)を用いる場合は、これらは認証局(CA) において署名者の情報と関連付けられて公開される。

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

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

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

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}}}

前述のように gq ≡ 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つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい[9]。k として同じ値を二度用いること（k を秘密にしていたとしても）、予測可能な値を用いること、複数の署名に対するそれぞれの k が数ビットであっても漏洩することは、DSAを破るには十分である[10]。

  • エントロピー(情報理論的エントロピー)：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つの異なるメッセージ mA と mB に対して同じ k を用いて署名 (r, sA) と (r, sB) を計算および送信し、攻撃者が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 を用いていなかったためである[11]。

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

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

  1. ^ FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19
  2. ^ FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15
  3. ^ FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27
  4. ^ a b FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009
  5. ^ a b FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013
  6. ^ “FIPS 186-5: Digital Signature Standard (DSS)”. NIST (2023年2月3日). doi:10.6028/NIST.FIPS.186-5. 2024年3月3日閲覧。
  7. ^ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board
  8. ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012
  9. ^ The Debian PGP disaster that almost was
  10. ^ DSA k-value Requirements
  11. ^ Bendel, Mike (2010年12月29日). “Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access”. Exophase.com 2011年1月5日閲覧。
カテゴリ カテゴリ