Digital Signature Algorithm

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つ目は公開鍵および秘密鍵の生成である。

• 適切な暗号学的ハッシュ関数 H を選択する。当初のDSSでは H はSHA-1であったが、FIPS 186-4ではSHA-2も選択可能となった^[5][8]。ハッシュの出力値は鍵ペアのサイズに切り詰められる。
• 鍵長 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つと規定された^[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がよく用いられる)。フェルマーの小定理より g^q ≡ h^p − 1 ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は有限体${\displaystyle F_{p}}$ の乗法群${\displaystyle F_{p}^{*}}$(位数 p-1) の位数 q の元である(つまり 0 < a < q である任意の整数 a について、g^a ≢ 1 (mod p)である)。

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

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

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

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

ハッシュ関数を ${\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つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい^[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つの異なるメッセージ 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 を用いていなかったためである^[11]。

唯一性の問題は、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