数字签名算法
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此条目可参照英语维基百科相应条目来扩充。 |
数字签名算法(DSA)是用于数字签名的联邦信息处理标准之一,基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。
美国国家标准技术研究所(NIST)于1991年提出将DSA用于其数字签名标准(DSS),并于1994年将其作为FIPS 186采用。[2]已对初始规范进行了四次修订。DSA已获得专利,但NIST已将此专利在全球范围内买断式授权。
概述
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.0 1.1 FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 (PDF). csrc.nist.gov. [2021-05-01]. (原始内容存档 (PDF)于2016-12-27).
- ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012 (PDF). csrc.nist.gov. [2021-05-01]. (原始内容存档 (PDF)于2013-02-17).
- ^ NIST Special Publication 800-57 (PDF). csrc.nist.gov. (原始内容 (PDF)存档于2014-06-06).
|