Digital Signature Algorithm

出典: フリー百科事典『ウィキペディア(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])。DSAはElGamal署名の改良版の一つであり、それと同様に離散対数問題の困難性に基づく電子署名方式である。

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

鍵生成[編集]

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

パラメータ生成[編集]

  • 適切な暗号学的ハッシュ関数 H を選択する。当初のDSSでは HSHA-1であったが、FIPS 186-4ではSHA-2も選択可能となった[5][7]。ハッシュの出力値は鍵ペアのサイズに切り詰められる。
  • 鍵長 L および N を決定する。これらが主に暗号強度に影響する。当初のDSSでは、L は512から1024の間の64の倍数であった。NIST 800-57においては、L を2048あるいは3072とすることで、2010年あるいは2030年まで安全が保たれると推奨された。FIPS 186-3では、LN の組み合わせは (1024, 160)、(2048, 224)、(2048, 256)、(3072, 256) の4つと規定された[4]
  • N ビットの素数 q を選択する。N はハッシュの出力長以下でなければならない。
  • p–1 が q の倍数となるような L ビットの素数法 p を選択する。
  • 1 < h < p−1 なる h に対して g = h(p–1)/q mod p なる g を求める。もし g が1となる場合には h を選択し直す。h = 2がよく用いられる。

パラメータ (p, q, g) は他者との間で共有される。

鍵ペアの生成[編集]

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

  • 0 < x < q なる x をランダムに選択する。
  • y = gx mod p を計算する。
  • 公開鍵は (p, q, g, y)、秘密鍵は x である。

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

署名[編集]

ハッシュ関数を H、平文を m とする。

  • 0 < k < q なる k を平文ごとにランダムに決定する。
  • r=\left(g^{k}\bmod\,p\right)\bmod\,q を計算する
  • もし r=0 である場合には k を選択し直す。
  • s=k^{-1}\left(H\left(m\right)+xr\right)\bmod\,q を計算する。
  • もし s=0 である場合には k を選択し直す。
  • \left(r,s\right)m に対する署名となる。

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

検証[編集]

平文 m と署名 \left(r,s\right) の検証は以下のように行われる。

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

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

アルゴリズムの正当性[編集]

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

g = h(p − 1)/q mod p であるとき、フェルマーの小定理より gqhp − 1 ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は次数 q でなければならない。

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

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

ゆえに


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

g は次数 q (mod p) であるから


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

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

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

機密性[編集]

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

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

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

関連項目[編集]

脚注[編集]

  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. ^ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board
  7. ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012
  8. ^ The Debian PGP disaster that almost was
  9. ^ DSA k-value Requirements
  10. ^ Bendel, Mike (2010年12月29日). “Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access”. Exophase.com. http://exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/ 2011年1月5日閲覧。 

外部リンク[編集]