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）。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つ目は公開鍵及び秘密鍵の生成である。 適切な暗号学的ハッシュ関数 H を選択する。当初のDSSでは H はSHA-1であったが、FIPS 186-4ではSHA-2も選択可能となった。ハッシュの出力値は鍵ペアのサイズに切り詰められる。 鍵長 L および N を決定する。これらが主に暗号強度に影響する。当初のDSSでは、L は512から1024の間の64の倍数であった。NIST 800-57においては、L を2048あるいは3072とすることで、2010年あるいは2030年まで安全が保たれると推奨された。FIPS 186-3では、L と N の組み合わせは (1024, 160)、(2048, 224)、(2048, 256)、(3072, 256) の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 の効率的な計算法が存在する。冪乗#効率的な演算法を参照のこと。 ハッシュ関数を H {\displaystyle H} 、署名したいメッセージを m {\displaystyle m} とする。 0 < k < q {\displaystyle 0<k<q} なる k {\displaystyle k} をメッセージごとにランダムに決定する。 r = ( g k mod p ) mod q {\displaystyle r=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q} を計算する もし r = 0 {\displaystyle r=0} である場合には k {\displaystyle k} を選択し直す。 s = k − 1 ( H ( m ) + x r ) mod q {\displaystyle s=k^{-1}\left(H\left(m\right)+xr\right){\bmod {\,}}q} を計算する。 もし s = 0 {\displaystyle s=0} である場合には k {\displaystyle k} を選択し直す。 ( r , s ) {\displaystyle \left(r,s\right)} が m {\displaystyle m} に対する署名となる。 最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。 k − 1 mod q {\displaystyle k^{-1}{\bmod {\,}}q} が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは k q − 2 mod q {\displaystyle k^{q-2}{\bmod {\,}}q} としてフェルマーの小定理を用いて計算されることがある。 メッセージ m {\displaystyle m} と署名 ( r , s ) {\displaystyle \left(r,s\right)} の検証は以下のように行われる。 0 < r < q {\displaystyle 0<r<q} かつ 0 < s < q {\displaystyle 0<s<q} を満たさない場合には拒否する。 w = s − 1 mod q {\displaystyle w=s^{-1}{\bmod {\,}}q} を計算する。 u 1 = H ( m ) ⋅ w mod q {\displaystyle u_{1}=H\left(m\right)\cdot w\,{\bmod {\,}}q} を計算する。 u 2 = r ⋅ w mod q {\displaystyle u_{2}=r\cdot w\,{\bmod {\,}}q} を計算する。 v = ( ( g u 1 y u 2 ) mod p ) mod q {\displaystyle v=\left(\left(g^{u_{1}}y^{u_{2}}\right){\bmod {\,}}p\right){\bmod {\,}}q} を計算する。 v = r {\displaystyle v=r} であれば署名は正当なものである。 DSAはElGamal署名の改良版であり、類似している。 DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。 g = h(p − 1)/q mod p であるとき、フェルマーの小定理より gq ≡ hp − 1 ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は次数 q でなければならない。 署名者は次式を計算する。 s = k − 1 ( H ( m ) + x r ) mod q {\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q} ゆえに k ≡ H ( m ) s − 1 + x r s − 1 ≡ H ( m ) w + x r w ( mod q ) {\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}} g は次数 q (mod p) であるから g k ≡ g H ( m ) w g x r w ≡ g H ( m ) w y r w ≡ g u 1 y u 2 ( 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の正当性は以下に示される。 r = ( g k mod p ) mod q = ( g u 1 y u 2 mod p ) mod q = v {\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を破るには十分である。 2010年12月、fail0verflow と名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていた楕円曲線DSAの秘密鍵の回復に成功したと発表した。これは、ソニーが署名ごとに新しいランダムな k を用いていなかったためである。 この問題は、RFC 6979にあるように、秘密鍵とメッセージハッシュから決定論的に k を導くことで回避できる。これにより、k がそれぞれの H(m) に対して異なることと、秘密鍵 x を知らない攻撃者にとって予測不能であることが保証される。 DSAをサポートしているライブラリは以下のものがある。 Botan Bouncy Castle cryptlib Crypto++ libcrypt libsodium Nettle OpenSSL wolfSSL 楕円曲線DSA ElGamal署名 合同式 ^ FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19 ^ FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15 ^ FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27 ^ a b FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009 ^ a b FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 ^ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012 ^ The Debian PGP disaster that almost was ^ DSA k-value Requirements ^ 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日閲覧。  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