数字签名算法

数字签名算法(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 的支持:

相关条目

  • 模运算
  • RSA
  • ECDSA

参考文献

  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).