數字簽名算法

数字签名算法(DSA)是用于数字签名的联邦信息处理标准之一,基于模算数离散对数的复杂度。DSA是SchnorrElGamal签名方案的变体。

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

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

概述

DSA算法工作在框架公钥加密模算数离散对数问题,这被认为是难解问题。该算法使用由公钥私钥组成的密钥对。私钥用于生成消息的数字签名,并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定(接收者可以验证消息的来源),完整性(接收方可以验证消息自签名以来未被修改)和不可否认性(发送方不能错误地声称它们没有签署消息)。

操作

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

金鑰生成

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

參數選擇

  • 選擇經核可的 密碼雜湊函式  ,在原版的 DSS(Digital Signature Standard)中,  總是使用 SHA-1,而目前的 DSS 已核可更為安全的 SHA-2 作為雜湊函式。[1][2] 假如長度   大於模數長度  ,則雜湊函式的輸出只有最左邊的   位元會被使用。
  • 選擇金鑰長度  ,原版的 DSS 限制   必須為 512 到 1024 之間 64 的倍數,NIST 800-57 建議使用長度為 2048 的金鑰。[3]
  • 選擇模數長度   使得   FIPS 186-4 規定   必須為 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一種。[1]
  • 選擇長度為   位元的質數  
  • 選擇長度為   位元的質數   使得    的倍數。
  •   隨機選擇  
  • 計算  ,當   時需要重新產生不同的  ,通常會使用  ,即使數值很大時仍然可以非常有效率的計算這個 模幂

演算法參數為 ( ,  ,  ),可被不同的使用者共享。

使用者金鑰

給定一套演算法參數後,第二階段會為每位使用者計算獨立金鑰組合:

  •   選擇隨機整數  
  • 計算  

其中   是私鑰、  是公鑰。

金鑰分發

簽章者需要透過可信任的管道發佈公鑰  ,並且安全地保護   不被其他人知道。

簽章流程

訊息   簽名流程如下:

  •   隨機選擇整數  
  • 計算  ,當出現   狀況時重新選擇隨機數  
  • 計算  ,當出現   狀況時重新選擇隨機數  

簽章為   組合

計算    旨在為不同訊息建立獨立的金鑰,計算  模幂是這個演算法中最耗資源的部分,但這可在不知道訊息的前提下進行計算。 第二耗運算資源的部分是計算   模反元素,同樣也能在不知道訊息的前提下進行計算,這可以用擴展歐幾里得演算法費馬小定理   求得。

驗證簽章

透過以下步驟可以驗證   是訊息   的有效簽章:

  • 驗證   
  • 計算  
  • 計算  
  • 計算  
  • 計算  

只有在   時代表簽章是有效的

實作

下列密碼學函式庫有提供 DSA 的支援:

相關條目

參考文獻

  1. ^ 1.0 1.1 FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 (PDF). csrc.nist.gov. [2021-05-01]. (原始内容存档 (PDF)于2016-12-27). 
  2. ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012 (PDF). csrc.nist.gov. [2021-05-01]. (原始内容存档 (PDF)于2013-02-17). 
  3. ^ NIST Special Publication 800-57 (PDF). csrc.nist.gov. (原始内容 (PDF)存档于2014-06-06).