查看“︁数字签名算法”︁的源代码

{{noteTA
|G1=IT
|T=zh:數字簽名算法;zh-hans:数字签名算法;zh-hk:數碼簽署演算法;zh-tw:數位簽章演算法;
|1=zh:數位簽章;zh-hans:数字签名;zh-hk:數碼簽署;zh-tw:數位簽章;
|2=zh:數位;zh-hans:数字;zh-hk:數碼;zh-tw:數位;
}}
{{expand english|Digital_Signature_Algorithm}}
'''数字签名算法'''（DSA）是用于[[数字签名]]的联邦信息处理标准之一，基于[[模算数]]和[[离散对数]]的复杂度。DSA是[[Schnorr签名|Schnorr]]和[[ElGamal加密算法|ElGamal]]签名方案的变体。

美国[[國家標準技術研究所]]（NIST）于1991年提出将DSA用于其数字签名标准（DSS），并于1994年将其作为FIPS 186采用。[2]已对初始规范进行了四次修订。DSA已获得专利，但NIST已将此专利在全球范围内[[買斷式授權]]。

DSA的[[椭圆曲线密码学]]版本是[[ECDSA]]。

==概述==
DSA算法工作在框架[[公开密钥加密|公钥加密]]、[[模算数]]和[[离散对数]]问题，这被认为是[[未解決的計算機科學問題|难解问题]]。该算法使用由'''公钥'''和'''私钥'''组成的'''密钥对'''。私钥用于生成消息的'''数字签名'''，并且可以通过使用签名者的相应公钥来'''验证'''这种签名。数字签名提供[[信息鉴定]]（接收者可以验证消息的来源），[[数据完整性|完整性]]（接收方可以验证消息自签名以来未被修改）和[[不可否认性]]（发送方不能错误地声称它们没有签署消息）。

==操作==
DSA 演算法包含了四種操作：金鑰生成、金鑰分發、簽章、驗證

===金鑰生成===
金鑰生成包含兩個階段。第一階段是''演算法參數''的選擇，可以在系統的不同使用者之間共享，而第二階段則為每個使用者計算獨立的金鑰組合。

====參數選擇====
* 選擇經核可的 [[密碼雜湊函式]] <math>H</math>，在原版的 DSS（Digital Signature Standard）中，<math>H</math> 總是使用 [[SHA-1]]，而目前的 DSS 已核可更為安全的 [[SHA-2]] 作為雜湊函式。<ref name="FIPS-186-4">{{cite web|url= http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf|title= FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013|website= csrc.nist.gov|access-date= 2021-05-01|archive-date= 2016-12-27|archive-url= https://web.archive.org/web/20161227093019/http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf|dead-url= no}}</ref><ref name="FIPS-180-4">{{cite web|url=http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf|title=FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012|website=csrc.nist.gov|access-date=2021-05-01|archive-date=2013-02-17|archive-url=https://web.archive.org/web/20130217190337/http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf|dead-url=no}}</ref> 假如長度 <math>|H|</math> 大於模數長度 <math>N</math>，則雜湊函式的輸出只有最左邊的 <math>N</math> 位元會被使用。
* 選擇金鑰長度 <math>L</math>，原版的 DSS 限制 <math>L</math> 必須為 512 到 1024 之間 64 的倍數，[[NIST]] 800-57 建議使用長度為 2048 的金鑰。<ref>{{cite web|url=http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf |title=NIST Special Publication 800-57 |website=csrc.nist.gov |url-status=dead |archive-url=https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf |archive-date=2014-06-06 }}</ref>
* 選擇模數長度 <math>N</math> 使得 <math>N < L</math> 且 <math>N \leq |H|</math>，[[聯邦資訊處理標準|FIPS]] 186-4 規定 <math>(L, N)</math> 必須為 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一種。<ref name="FIPS-186-4" />
* 選擇長度為 <math>N</math> 位元的質數 <math>q</math>。
* 選擇長度為 <math>L</math> 位元的質數 <math>p</math> 使得 <math>p - 1</math> 為 <math>q</math> 的倍數。
* 從 <math>\{ 2 \ldots p-2 \}</math> 隨機選擇 <math>h</math>。
* 計算 <math>g := h^{(p - 1)/q} \mod p</math>，當 <math>g=1</math> 時需要重新產生不同的 <math>h</math>，通常會使用 <math>h=2</math>，即使數值很大時仍然可以非常有效率的計算這個 [[模幂]]。
演算法參數為 (<math>p</math>, <math>q</math>, <math>g</math>)，可被不同的使用者共享。

====使用者金鑰====
給定一套演算法參數後，第二階段會為每位使用者計算獨立金鑰組合：
* 從 <math>\{ 1 \ldots q-1 \}</math> 選擇隨機整數 <math>x</math>
* 計算 <math>y := g^x \mod p</math>
其中 <math>x</math> 是私鑰、<math>y</math> 是公鑰。

===金鑰分發===
簽章者需要透過可信任的管道發佈公鑰 <math>y</math>，並且安全地保護 <math>x</math> 不被其他人知道。

===簽章流程===
訊息 <math>m</math> 簽名流程如下：
* 從 <math>\{ 1 \ldots q-1 \}</math> 隨機選擇整數 <math>k</math>
* 計算 <math>r := \left(g^{k}\bmod\,p\right)\bmod\,q</math>，當出現 <math>r=0</math> 狀況時重新選擇隨機數 <math>k</math>
* 計算 <math>s := \left(k^{-1}\left(H(m)+xr\right)\right)\bmod\,q</math>，當出現 <math>s=0</math> 狀況時重新選擇隨機數 <math>k</math>
簽章為 <math>(r, s)</math> 組合

計算 <math>k</math> 和 <math>r</math> 旨在為不同訊息建立獨立的金鑰，計算 <math>r</math> 的[[模幂]]是這個演算法中最耗資源的部分，但這可在不知道訊息的前提下進行計算。
第二耗運算資源的部分是計算 <math>k^{-1}\bmod\,q</math> [[模反元素]]，同樣也能在不知道訊息的前提下進行計算，這可以用[[擴展歐幾里得演算法]]或[[費馬小定理]] <math>k^{q-2}\bmod\,q</math> 求得。

===驗證簽章===
透過以下步驟可以驗證 <math>\left(r,s\right)</math> 是訊息 <math>m</math> 的有效簽章：
* 驗證 <math>0 < r < q</math> 且 <math>0 < s < q</math>
* 計算 <math>  w := s^{-1} \bmod\,q</math>
* 計算 <math>u_1 := H(m) \cdot w\, \bmod\,q</math>
* 計算 <math>u_2 := r \cdot w\, \bmod\,q</math>
* 計算 <math>  v := \left(g^{u_1}y^{u_2} \bmod\,p\right) \bmod\,q</math>
只有在 <math>v = r</math> 時代表簽章是有效的

==實作==
下列密碼學函式庫有提供 DSA 的支援：
* [[OpenSSL]]
* [[GnuTLS]]
* [[wolfCrypt]]
* [[Crypto++]]
* {{tsl|en|cryptlib|cryptlib}}
* {{tsl|en|Botan (programming library)|Botan}}
* {{tsl|en|Bouncy Castle (cryptography)|Bouncy Castle}}
* {{tsl|en|libgcrypt|libgcrypt}}
* {{tsl|en|Nettle (cryptographic library)|Nettle}}

==相關條目==
* [[模運算]]
* [[RSA加密演算法|RSA]]
* [[ECDSA]]

==參考文獻==
{{reflist|30em}}

{{公钥密码学}}

[[Category:1991年面世]]
[[Category:数字签名方案]]