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

デジタル署名アルゴリズム（DSA）は、公開鍵暗号システムであり、デジタル署名のための連邦情報処理標準（FIPS）です。これは、べき乗剰余と離散対数問題という数学的概念に基づいています。デジタル署名システムでは、秘密鍵と公開鍵からなる鍵ペアが使用されます。このシステムでは、公開鍵を宣言した署名者は、秘密鍵を使用して署名を生成することができ、検証者は、宣言された公開鍵を使用して署名を正しく検証することで、その署名の出所を主張することができます。DSAは、シュノア署名方式とエルガマル署名方式の派生です。^{[1] : 486}

米国国立標準技術研究所（NIST）は、1991年にデジタル署名標準（DSS）にDSAを採用することを提案し、1994年にFIPS 186として採択しました。 ^[2]初期仕様から5回の改訂がリリースされています。最新の仕様は、2023年2月から適用されるFIPS 186-5です。^[3] DSAは特許取得済みですが、NISTはこの特許を世界中でロイヤリティフリーで利用できるようにしています。FIPS 186-5仕様では、DSAはデジタル署名の生成には承認されなくなりますが、この標準の実装日より前に生成された署名の検証には使用できることが示されています。

概要

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

歴史

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

DSAは、1991年7月26日に出願され、現在は失効している米国特許5,231,668号で保護されており、 NSA元職員のデイビッド・W・クラヴィッツ氏^{[9]に帰属しています。この特許は「ワシントンD.C.の}商務長官を代表とするアメリカ合衆国」に付与され、NISTはこの特許を世界中で無償で公開しています。^[10]クラウス・P・シュノア氏は、自身の米国特許4,995,082号（これも現在は失効）がDSAをカバーしていると主張していますが、この主張には異議があります。^[11]

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

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

手術

DSA アルゴリズムには、キー生成 (キー ペアの作成)、キー配布、署名、署名検証の 4 つの操作が含まれます。

1. 鍵生成

鍵生成には2つのフェーズがあります。最初のフェーズでは、システムの異なるユーザー間で共有できるアルゴリズムパラメータを選択し、2番目のフェーズでは、1人のユーザーに対して1つの鍵ペアを計算します。

パラメータ生成

• 出力長 ビットの承認済み暗号ハッシュ関数 を選択します。元のDSSでは、は常にSHA-1でしたが、現在のDSSではより強力なSHA-2ハッシュ関数の使用が承認されています。 ^{[3] [15]}が法長 より大きい場合、ハッシュ出力の左端のビットのみが使用されます。${\displaystyle H}$ ${\displaystyle |H|}$ ${\displaystyle H}$ ${\displaystyle |H|}$ ${\displaystyle N}$ ${\displaystyle N}$
• 鍵の長さを選択します。オリジナルのDSSでは、512から1024までの64の倍数に制限されていました。NIST 800-57では、セキュリティ有効期間が2010年（または2030年）を超える鍵については、2048（または3072）の長さを推奨しています。^[16]${\displaystyle L}$ ${\displaystyle L}$
• となるような係数の長さを選択します。FIPS 186-4では、およびが(1024, 160)、(2048, 224)、(2048, 256)、または(3072, 256)のいずれかの値を取るように規定されています。^[3]${\displaystyle N}$ ${\displaystyle N<L}$ ${\displaystyle N\leq |H|}$ ${\displaystyle L}$ ${\displaystyle N}$
• ビット素数を選択します。${\displaystyle N}$ ${\displaystyle q}$
• が の倍数となるようなビットの素数を選択します。${\displaystyle L}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle q}$
• からランダムに整数を選択します。${\displaystyle h}$ ${\displaystyle \{2\ldots p-2\}}$
• を計算します。まれに、異なる で再試行してください。一般的にが使用されます。この剰余指数は、値が大きい場合でも効率的に計算できます。${\displaystyle g:=h^{(p-1)/q}\mod p}$ ${\displaystyle g=1}$ ${\displaystyle h}$ ${\displaystyle h=2}$

アルゴリズムパラメータは( , , )です。これらはシステムの異なるユーザー間で共有できます。 ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle g}$

ユーザーごとのキー

一連のパラメータが指定されると、第 2 フェーズでは単一のユーザーのキー ペアを計算します。

• からランダムに整数を選択します。${\displaystyle x}$ ${\displaystyle \{1\ldots q-1\}}$
• 計算します。${\displaystyle y:=g^{x}\mod p}$

${\displaystyle x}$ は秘密鍵で、は公開鍵です。 ${\displaystyle y}$

2. 鍵配布

署名者は公開鍵を公開する必要があります。つまり、信頼できる（ただし必ずしも秘密である必要はない）メカニズムを介して受信者に鍵を送信する必要があります。署名者は秘密鍵を秘密に保持する必要があります。 ${\displaystyle y}$ ${\displaystyle x}$

3. 署名

メッセージは次のように署名されます。 ${\displaystyle m}$

• ランダムに整数を選択する${\displaystyle k}$ ${\displaystyle \{1\ldots q-1\}}$
• を計算します。 という可能性は低いですが、その場合は別のランダム からやり直してください。${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$ ${\displaystyle r=0}$ ${\displaystyle k}$
• を計算します。 という可能性は低いですが、その場合は別のランダム からやり直してください。${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$ ${\displaystyle s=0}$ ${\displaystyle k}$

署名は${\displaystyle \left(r,s\right)}$

との計算は、メッセージごとに新しい鍵を作成することに相当します。 の計算におけるモジュラー指数演算は、署名操作の中で最も計算コストの高い部分ですが、メッセージが既知になる前に計算できる場合があります。モジュラー逆数の計算は2番目に計算コストの高い部分ですが、これもメッセージが既知になる前に計算できる場合があります。これは、拡張ユークリッド互除法、またはフェルマーの小定理を用いてとして計算できます。 ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle k^{-1}{\bmod {\,}}q}$ ${\displaystyle k^{q-2}{\bmod {\,}}q}$

4. 署名検証

次のようにして、署名がメッセージに対して有効な署名であるかどうかを確認できます。 ${\displaystyle \left(r,s\right)}$ ${\displaystyle m}$

• および を検証します。${\displaystyle 0<r<q}$ ${\displaystyle 0<s<q}$
• 計算します。${\displaystyle w:=s^{-1}{\bmod {\,}}q}$
• 計算します。${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}$
• 計算します。${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}$
• 計算します。${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}$
• 署名は次の場合にのみ有効です。${\displaystyle v=r}$

アルゴリズムの正確性

署名スキームは、検証者が常に真正な署名を受け入れるという意味で正しいと言えます。これは次のように示せます。

まず、 なので、フェルマーの小定理により が成り立ちます。と は素数なので、 の位数は でなければなりません 。 ${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}$ ${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$ ${\displaystyle g>0}$ ${\displaystyle q}$ ${\displaystyle g}$ ${\displaystyle q}$

署名者は計算する

${\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}}}$

順序があるので 、${\displaystyle g}$ ${\displaystyle q}$

${\displaystyle {\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の正しさは、

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

感度

DSAでは、ランダム署名値のエントロピー、機密性、そして一意性が極めて重要です。これら3つの要件のいずれかに違反すると、秘密鍵全体が攻撃者に漏洩される可能性があります。^[17]同じ値を2回使用した場合（たとえ秘密を保持したままであっても）、予測可能な値を使用した場合、あるいは複数の署名のそれぞれにおいて数ビットでも漏洩した場合、秘密鍵が漏洩する可能性があります。^[18]${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x}$

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

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

さらに、DSAやECDSAの悪意ある実装は、署名を介して潜在的に情報を漏洩させるために利用される可能性があります。例えば、一見無害に見える署名のみを配信する完全なオフラインデバイスから、オフラインの秘密鍵が漏洩する可能性があります。^[20]${\displaystyle k}$

実装

以下は、DSA をサポートする暗号化ライブラリの一覧です。

• 牡丹
• バウンシーキャッスル
• 暗号ライブラリ
• 暗号++
• libgcrypt
• イラクサ
• オープンSSL
• ウルフクリプト
• GnuTLS

参照

• モジュラー演算
• RSA（暗号システム）
• ECDSA

参考文献

1. Schneier, Bruce (1996). 応用暗号学. Wiley. ISBN 0-471-11709-9。
2. 「FIPS PUB 186: デジタル署名標準（DSS）、1994年5月19日」。qcsrc.nist.gov 。 2013年12月13日時点のオリジナルよりアーカイブ。
3. 「FIPS PUB 186-4: デジタル署名標準 (DSS)、2013 年 7 月」(PDF) . csrc.nist.gov .
4. 「FIPS PUB 186-1: デジタル署名標準 (DSS)、1998年12月15日」(PDF) . csrc.nist.gov . 2013年12月26日時点のオリジナル(PDF)からアーカイブ。
5. 「FIPS PUB 186-2: デジタル署名標準 (DSS)、2000-01-27」(PDF) . csrc.nist.gov .
6. 「FIPS PUB 186-3: デジタル署名標準 (DSS)、2009 年 6 月」(PDF) . csrc.nist.gov .
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日アーカイブ、Wayback Machine
10. ヴェルナー・コッホ「DSAと特許」
11. “1994 Annual Report of CSSPAB”. 2009年8月26日. オリジナルより2009年8月26日時点のアーカイブ。
12. Neumann, Peter G. (2020年2月29日). “The RISKS Digest Volume 14 Issue 59”. 2020年2月29日時点のオリジナルよりアーカイブ。2023年10月3日閲覧。
13. 「OpenSSHがDSA削除のタイムラインを発表 [LWN.net]」lwn.net . 2024年1月11日閲覧。
14. 「OpenSSHバージョン10.0リリースノート」 。 2025年4月21日閲覧。
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 {\displaystyle k} 値要件
19. Bendel, Mike (2010年12月29日). 「ハッカーがPS3のセキュリティを大失敗と表現、無制限のアクセスを獲得」Exophase.com . 2011年1月5日閲覧。
20. Verbücheln, Stephan (2015年1月2日). 「完璧なオフラインウォレットでもビットコインの秘密鍵が漏洩する可能性がある理由」arXiv : 1501.00447 [cs.CR].

外部リンク

• FIPS PUB 186-4: デジタル署名標準 (DSS)、公式 DSA 仕様の 4 番目の (現在の) 改訂版。
• 鍵管理に関する推奨事項 - パート1：一般、NIST特別出版物800-57、p.62～63