デジタル署名アルゴリズム

デジタル署名アルゴリズム（DSA）は、公開鍵暗号方式であり、モジュラーべき乗と離散対数問題という数学的概念に基づいた、デジタル署名のための連邦情報処理標準です。デジタル署名システムでは、秘密鍵と公開鍵からなる鍵ペアが用いられます。このシステムでは、公開鍵を宣言した署名主体は秘密鍵を用いて署名を生成でき、検証者は宣言された公開鍵を用いて署名が正しく検証されれば、その署名元を証明できます。DSAは、シュノール署名方式とエルガマル署名方式の派生形です。^[¹^]^：⁴⁸⁶

米国国立標準技術研究所（NIST）は、1991年にデジタル署名標準（DSS）で使用するためにDSAを提案し、1994年にFIPS 186として採用しました。^{[ 2 ]}初期仕様に対して5回の改訂版がリリースされています。しかし、最新の標準では、DSA署名生成に対するNISTの承認が削除されました。^{[ 3 ]}

概要

DSAは公開鍵暗号システムの枠組みで動作し、モジュラーべき乗の代数的性質と、計算上困難とされる離散対数問題に基づいています。このアルゴリズムは、公開鍵と秘密鍵からなる鍵ペアを使用します。秘密鍵はメッセージのデジタル署名を生成するために使用され、その署名は署名者の対応する公開鍵を使用して検証できます。デジタル署名は、メッセージの認証（受信者はメッセージの発信元を検証できる）、完全性（受信者は署名後にメッセージが変更されていないことを検証できる）、および否認防止（送信者はメッセージに署名していないと偽って主張できない）を提供します。

歴史

1982年、米国政府は公開鍵署名標準の提案を募集した。1991年8月、米国国立標準技術研究所（NIST）は、デジタル署名標準（DSS）で使用するためにDSAを提案した。当初は、特にRSA暗号システムに基づいたデジタル署名ソフトウェアの開発に既に投資していたソフトウェア企業から、大きな批判があった。 ^[¹^]^:⁴⁸⁴それにもかかわらず、NIST は 1994 年に DSA を連邦標準 (FIPS 186) として採用しました。最初の仕様の 5 つの改訂版がリリースされています。1998 年に FIPS 186-1、^[⁴^] 2000 年に FIPS 186-2 、 ^[⁵^] 2009 年にFIPS 186-3、 ^[⁶^] 2013 年に FIPS 186-4、^[³^]および 2023 年に FIPS 186-5です。 ^[⁷^]標準 FIPS 186-5 は DSA による署名を禁止していますが、標準の実装日以前に文書として生成された署名の検証は許可しています。これはEdDSAなどの新しい署名方式に置き換えられる予定です。^[⁸^]

DSAは、1991年7月26日に出願され、現在は失効している米国特許第5,231,668号でカバーされており、元NSA職員のDavid W. Kravitz氏^{[ 9 ]}に帰属しています。この特許は「商務長官が代表するアメリカ合衆国、ワシントンDC」に付与され、NISTはこの特許を世界中で無償で公開しています^[¹⁰^] 。Claus P. Schnorr氏は、自身の米国特許第4,995,082号（これも現在は失効）がDSAをカバーしていると主張していますが、この主張は争われています^[¹¹^{] 。}

1993年、デイブ・バニサーはFOIAの請求を通じて、DSAアルゴリズムはNISTではなくNSAによって設計されたものであるという確認を得ることに成功した。^{[ 12 ]}

2023年2月、NISTはFIPS 186-5をリリースし、新しい署名の生成にはDSAの使用を非推奨としたが、既存の署名の検証には使用を許可した。^{[ 3 ]}

OpenSSHはDSAが2025年に削除されることを発表しました。バージョン10.0ではサポートが完全に廃止されました。^{[ 13 ]}^{[ 14 ]}

手術

DSAアルゴリズムは、鍵生成（鍵ペアを作成する）、鍵配布、署名、署名検証の4つの操作から構成されます。

1. キー生成

Key generation has two phases. The first phase is a choice of algorithm parameters which may be shared between different users of the system, while the second phase computes a single key pair for one user.

Parameter generation

Choose an approved cryptographic hash function $H$ with output length $|H|$ bits. In the original DSS, $H$ was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS.^[3]^[15] If $|H|$ is greater than the modulus length $N$ , only the leftmost $N$ bits of the hash output are used.
Choose a key length $L$ . The original DSS constrained $L$ to be a multiple of 64 between 512 and 1024 inclusive. NIST 800-57 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030).^[16]
Choose the modulus length $N$ such that $N<L$ and $N\leq |H|$ . FIPS 186-4 specifies $L$ and $N$ to have one of the values: (1024, 160), (2048, 224), (2048, 256), or (3072, 256).^[3]
Choose an $N$ -bit prime $q$ .
Choose an $L$ -bit prime $p$ such that $p-1$ is a multiple of $q$ .
Choose an integer $h$ randomly from $\{2\ldots p-2\}$ .
Compute $g:=h^{(p-1)/q}\mod p$ . In the rare case that $g=1$ try again with a different $h$ . Commonly $h=2$ is used. This modular exponentiation can be computed efficiently even if the values are large.

The algorithm parameters are ( $p$ , $q$ , $g$ ). These may be shared between different users of the system.

Per-user keys

Given a set of parameters, the second phase computes the key pair for a single user:

Choose an integer $x$ randomly from $\{1\ldots q-1\}$ .
Compute $y:=g^{x}\mod p$ .

$x$ is the private key and $y$ is the public key.

2. Key distribution

The signer should publish the public key $y$ . That is, they should send the key to the receiver via a reliable, but not necessarily secret, mechanism. The signer should keep the private key $x$ secret.

3. Signing

A message $m$ is signed as follows:

Choose an integer $k$ randomly from $\{1\ldots q-1\}$
Compute $r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q$ . In the unlikely case that $r=0$ , start again with a different random $k$ .
Compute $s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q$ . In the unlikely case that $s=0$ , start again with a different random $k$ .

The signature is $\left(r,s\right)$

The calculation of $k$ and $r$ amounts to creating a new per-message key. The modular exponentiation in computing $r$ is the most computationally expensive part of the signing operation, but it may be computed before the message is known. Calculating the modular inverse $k^{-1}{\bmod {\,}}q$ is the second most expensive part, and it may also be computed before the message is known. It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as $k^{q-2}{\bmod {\,}}q$ .

4. Signature Verification

One can verify that a signature $\left(r,s\right)$ is a valid signature for a message $m$ as follows:

Verify that $0<r<q$ and $0<s<q$ .
Compute $w:=s^{-1}{\bmod {\,}}q$ .
Compute $u_{1}:=H(m)\cdot w\,{\bmod {\,}}q$ .
Compute $u_{2}:=r\cdot w\,{\bmod {\,}}q$ .
Compute $v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q$ .
The signature is valid if and only if $v=r$ .

Correctness of the algorithm

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:

First, since ${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}$ , it follows that ${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$ by Fermat's little theorem. Since $g>0$ and $q$ 素数です、 $g$ 注文が必要です $q$ 。

署名者は計算します

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

したがって

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

以来 $g$ 順序がある $q$ 我々は持っています

{\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}

最後に、DSAの正しさは以下から導かれる。

{\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}

感度

DSAでは、ランダム署名値のエントロピー、秘密性、および一意性が向上します。 $k$ は非常に重要です。これら 3 つの要件のいずれか 1 つでも違反すると、攻撃者に秘密鍵全体が漏洩する可能性があります。^{[ 17 ]}同じ値を 2 回使用する (たとえ保持しながらでも) $k$ 秘密情報）、予測可能な値を使用する、または数ビットでも漏洩する $k$ 複数の署名のそれぞれにおいて、秘密鍵を明らかにするのに十分である。 $x$ [ ¹⁸^]

この問題はDSAと楕円曲線デジタル署名アルゴリズム（ECDSA ）の両方に影響を及ぼします。2010年12月、 fail0verflowグループは、ソニーが PlayStation 3ゲーム機のソフトウェア署名に使用していたECDSA秘密鍵の復元を発表しました。この攻撃は、ソニーが新しい乱数を生成できなかったために可能になりました。 $k$ 署名ごとに。^{[ 19 ]}

この問題は、 $k$ RFC 6979で説明されているように、秘密鍵とメッセージハッシュから決定論的に。これにより、 $k$ それぞれ異なります $H(m)$ 秘密鍵を知らない攻撃者にとっては予測不可能 $x$ 。

さらに、DSAおよびECDSAの悪意のある実装は、次のような場合に作成できます。 $k$ 署名を介して情報を潜在的に漏洩させるために選択されます。たとえば、無害に見える署名のみをリリースする完璧なオフラインデバイスからオフラインの秘密鍵が漏洩する可能性があります。^{[ 20 ]}

実装

以下は、DSAをサポートする暗号ライブラリの例です（すべてを網羅しているわけではありません）。

参考文献

1 2シュナイアー、ブルース (1996).応用暗号学. ワイリー. ISBN 0-471-11709-9。
↑ "FIPS PUB 186: デジタル署名標準 (DSS)、1994-05-19" . qcsrc.nist.gov . 2013-12-13 のオリジナルからアーカイブ済み。
1 2 3 4 5 「FIPS PUB 186-4: デジタル署名標準 (DSS)、2013 年 7 月」(PDF) . csrc.nist.gov .
↑ 「FIPS PUB 186-1: デジタル署名標準 (DSS)、1998年12月15日」(PDF)。csrc.nist.gov 。2013年12月26日にオリジナル(PDF)からアーカイブされました。
↑ 「FIPS PUB 186-2: デジタル署名標準 (DSS)、2000-01-27」(PDF) . csrc.nist.gov .
↑ 「FIPS PUB 186-3: デジタル署名標準 (DSS)、2009 年 6 月」(PDF) . csrc.nist.gov .
↑ 「FIPS PUB 186-5: デジタル署名標準 (DSS)、2023年2月」(PDF) . csrc.nist.gov .
↑ 「デジタル署名標準（DSS）」。米国商務省。2019年10月31日。 2020年7月21日取得。
↑デビッド・W・クラヴィッツ博士2013年1月9日、ウェイバックマシンにアーカイブ済み
↑ヴェルナー・コッホ著「DSAと特許」
↑ 「1994年CSSPAB年次報告書」。2009年8月26日。 2009年8月26日のオリジナルからアーカイブ済み。
↑ Neumann, Peter G. (2020-02-29). "The RISKS Digest Volume 14 Issue 59" . 2020-02-29 のオリジナルからアーカイブ済み。2023-10-03に取得。{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)
↑ 「OpenSSHがDSA削除のタイムラインを発表[ LWN.net ]」。lwn.net 。2024年1月11日取得。
↑ 「OpenSSH バージョン 10.0 リリースノート」。2025年4 月 21 日に取得。
↑ 「FIPS PUB 180-4: セキュアハッシュ標準 (SHS)、2012年3月」(PDF) . csrc.nist.gov .
↑ 「NIST特別刊行物800-57」（PDF）。csrc.nist.gov 。2014年6月6日にオリジナル（PDF）からアーカイブされました。
↑ 「危うく起こりかけたDebian PGPの惨事」 . root labs rdist . 2009年5月18日。
↑ DSA $k$ -値要件
↑ベンデル、マイク (2010-12-29). 「ハッカーがPS3のセキュリティを大失敗と評し、無制限のアクセス権を獲得」。Exophase.com。2011-01-05に閲覧。
↑ Verbücheln, Stephan (2015年1月2日). "完璧なオフラインウォレットでもビットコインの秘密鍵が漏洩する可能性あり". arXiv : 1501.00447 [ cs.CR ].
↑ 「公開鍵暗号方式 — Botan」。botan.randombit.net。2025年12月15日取得。
↑ 「Bouncy CastleがJava 1.81とC# .NET 2.6.1をリリース」。Bouncycastle 。2025年12月15日取得。
↑ Gutmann, Peter (2024 年 10 月). "Cryptlib" (PDF) . cryptlib.com . 2026 年 5 月 27 日にオリジナルからアーカイブ(PDF) . 2026 年 5 月 27 日に取得.
↑ 「デジタル署名アルゴリズム - Crypto++ Wiki」。www.cryptopp.com。2025年12月15日取得。
↑ 「暗号化関数（Libgcryptリファレンスマニュアル）」。www.gnupg.org 。 2025年12月15日取得。
↑ 「Nettle: 低レベル暗号ライブラリ」。www.lysator.liu.se 。 2025年12月15日取得。
↑ "dsa - OpenSSL ドキュメント" . docs.openssl.org . 2025-12-15に取得.
↑ 「wolfSSLユーザーマニュアル｜第10章：wolfCrypt使用リファレンス｜ドキュメント」。wolfSSL （日本語）。 2025年12月15日取得。
↑ 「公開鍵アルゴリズム（GnuTLS 3.8.10）」。www.gnutls.org 。 2025年12月15日取得。

外部リンク

FIPS PUB 186-4: デジタル署名標準 (DSS) は、公式の DSA 仕様の第 4 版 (現行版) です。
鍵管理に関する推奨事項 ― パート 1：概要、NIST 特別刊行物 800-57、62～ 63ページ

[schneier-1] 1 2シュナイアー、ブルース (1996).応用暗号学. ワイリー. ISBN 0-471-11709-9。

[FIPS-186-2] "FIPS PUB 186: デジタル署名標準 (DSS)、1994-05-19" . qcsrc.nist.gov . 2013-12-13 のオリジナルからアーカイブ済み。

[FIPS-186-4-3] 1 2 3 4 5 「FIPS PUB 186-4: デジタル署名標準 (DSS)、2013 年 7 月」(PDF) . csrc.nist.gov .

[FIPS-186-1-4] 「FIPS PUB 186-1: デジタル署名標準 (DSS)、1998年12月15日」(PDF)。csrc.nist.gov 。2013年12月26日にオリジナル(PDF)からアーカイブされました。

[FIPS-186-2-5] 「FIPS PUB 186-2: デジタル署名標準 (DSS)、2000-01-27」(PDF) . csrc.nist.gov .

[FIPS-186-3-6] 「FIPS PUB 186-3: デジタル署名標準 (DSS)、2009 年 6 月」(PDF) . csrc.nist.gov .

[FIPS-186-5-7] 「FIPS PUB 186-5: デジタル署名標準 (DSS)、2023年2月」(PDF) . csrc.nist.gov .

[8] 「デジタル署名標準（DSS）」。米国商務省。2019年10月31日。 2020年7月21日取得。

[9] デビッド・W・クラヴィッツ博士2013年1月9日、ウェイバックマシンにアーカイブ済み

[10] ヴェルナー・コッホ著「DSAと特許」

[11] 「1994年CSSPAB年次報告書」。2009年8月26日。 2009年8月26日のオリジナルからアーカイブ済み。

[12] Neumann, Peter G. (2020-02-29). "The RISKS Digest Volume 14 Issue 59" . 2020-02-29 のオリジナルからアーカイブ済み。2023-10-03に取得。{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)

[13] 「OpenSSHがDSA削除のタイムラインを発表[ LWN.net ]」。lwn.net 。2024年1月11日取得。

[14] 「OpenSSH バージョン 10.0 リリースノート」。2025年4 月 21 日に取得。

[FIPS-180-4-15] 「FIPS PUB 180-4: セキュアハッシュ標準 (SHS)、2012年3月」(PDF) . csrc.nist.gov .

[16] 「NIST特別刊行物800-57」（PDF）。csrc.nist.gov 。2014年6月6日にオリジナル（PDF）からアーカイブされました。

[17] 「危うく起こりかけたDebian PGPの惨事」 . root labs rdist . 2009年5月18日。

[18] DSA $k$ -値要件

[19] ベンデル、マイク (2010-12-29). 「ハッカーがPS3のセキュリティを大失敗と評し、無制限のアクセス権を獲得」。Exophase.com。2011-01-05に閲覧。

[20] Verbücheln, Stephan (2015年1月2日). "完璧なオフラインウォレットでもビットコインの秘密鍵が漏洩する可能性あり". arXiv : 1501.00447 [ cs.CR ].

[21] 「公開鍵暗号方式 — Botan」。botan.randombit.net。2025年12月15日取得。

[22] 「Bouncy CastleがJava 1.81とC# .NET 2.6.1をリリース」。Bouncycastle 。2025年12月15日取得。

[23] Gutmann, Peter (2024 年 10 月). "Cryptlib" (PDF) . cryptlib.com . 2026 年 5 月 27 日にオリジナルからアーカイブ(PDF) . 2026 年 5 月 27 日に取得.

[24] 「デジタル署名アルゴリズム - Crypto++ Wiki」。www.cryptopp.com。2025年12月15日取得。

[25] 「暗号化関数（Libgcryptリファレンスマニュアル）」。www.gnupg.org 。 2025年12月15日取得。

[26] 「Nettle: 低レベル暗号ライブラリ」。www.lysator.liu.se 。 2025年12月15日取得。

[27] "dsa - OpenSSL ドキュメント" . docs.openssl.org . 2025-12-15に取得.

[28] 「wolfSSLユーザーマニュアル｜第10章：wolfCrypt使用リファレンス｜ドキュメント」。wolfSSL （日本語）。 2025年12月15日取得。

[29] 「公開鍵アルゴリズム（GnuTLS 3.8.10）」。www.gnutls.org 。 2025年12月15日取得。

[

[ 2 ]

[ 3 ]

[

[

[

[

[

[ 9 ]

[

[

[ 12 ]

[ 13 ]

[ 14 ]

[15]

[16]

[ 17 ]

18

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

デジタル署名アルゴリズム

概要

歴史

手術

1. キー生成

Parameter generation

Per-user keys

2. Key distribution

3. Signing

4. Signature Verification

Correctness of the algorithm

感度

実装

関連項目

参考文献

外部リンク

関連するトピック

公開鍵暗号方式

モジュラーべき乗

離散対数問題

デジタル署名