内容简介
随着量子计算理论与技术的快速发展，向抗量子攻击密码算法迁移的紧迫性日益凸显。由于其可靠的安全性，较好的签名与验签性能，基于杂凑函数的数字签名是*先成为国际标准的一类抗量子攻击密码算法，它非常适合在软件、固件更新、操作系统安全启动、根CA及运营CA数字证书签名等场景中进行应用。《基于杂凑函数的抗量子计算攻击数字签名》系统地介绍了基于杂凑函数的有状态及无状态数字签名的基本原理、安全强度评估方法及主要国际标准。同时，为了便于初学者阅读，《基于杂凑函数的抗量子计算攻击数字签名》为相关内容匹配了大量图示并对典型杂凑函数及其通用攻击进行了详细的描述。
精彩书摘
第1章引言
数字签名可以确保数据的完整性（Integrity）和来源真实性（Authenticity）.在数字签名方案中，签名方拥有一个公私钥对（pk，sk），其中sk是私钥（签名方需对其保密），pk是公钥（可以公开签名者可以使用私钥sk对消息msg进行签名，任何知道公钥pk的实体都可以验证这个签名的真伪.可以公开验证真伪，是数字签名的一个重要性质，这意味着一个消息的签名可以出示给第三方，知道正确公钥的第三方可以正确地验证该签名的真伪.另外，由于只有知道私钥的实体才能进行签名，因此当一个实体给一个消息签名后，它也很难对其签名行为进行抵赖.这些特点与同样可以提供完整性和真实性保护的对称密码方案消息认证码（Message Authentication Code，MAC）有显著区别.消息认证码只能由私钥拥有者进行验证，且知道私钥的双方都可以计算任意消息的认证码，因此MAC也无法提供抗抵赖性.同时，数字签名也在一定程度上避免了消息认证码中密钥分配和管理的复杂性.但要注意，如何可靠地公布（和签名实体绑定的）公钥并不是一个平凡问题，错误的公钥信息可能带来灾难性的安全问题，公钥基础设施（PublicKey Infrastructure，PKI）体系就是一种系统地解决安全发布公钥的方案.
数字签名的应用极为广泛，在TLS协议、PKI、软件更新、操作系统安全启动、区块链等系统中发挥了重要作用.当前大规模部署和应用的数字签名包括国际标准RSA、ECDSA和我国商用密码标准SM2等.然而，由于Shor算法可以在量子计算模型下以多项式时间复杂度分解大整数和求解离散对数，一旦大规模通用量子计算机问世，现行的基于大整数分解和离散对数求解困难性的数字签名算法（如RSA、ECDSA和SM2等）的安全性将受到严重威胁W.尽管目前学术界和产业界对是否可以成功制造出大规模通用量子计算机还存在争议，但该领域的研究进展迅速，全球主要国家对向抗量子计算攻击密码算法迁移的必要性已达成广泛的共识.实际上，只要无法证明通用量子计算机不可实现，向抗量子计算攻击算法的迁移就是必要甚至紧迫的.其一，技术突破无法被预测，各国政府在量子计算领域投入了大量资源，由于量子计算的颠覆性，率先取得突破的国家有较高可能不会公布其相关成果.其二，密码算法的迁移需要较长的时间周期，向后量子密码算法的迁移必须远远早于量子计算机成功制造的时间.其三，将基于传统密码体系保护的加密流量保存起来并等待量子计算机成功制造后再解密的囤积攻击（Store Now Decrypt Later）进一步加剧了向后量子密码迁移的迫切性.*后，越来越多的企业将支持后量子算法作为可以进行大力宣传的产品优势，不具备抗量子计算攻击能力的产品将在未来产业竞争中处于劣势地位.
由于量子计算对对称密码的影响有限，我们目前所说的后量子密码主要是指抗量子计算攻击公钥密码.更具体地，主要是指密钥封装（KEM）/公钥加密（PKE）和数字签名（DSA）.本书主要关注数字签名算法.目前构造抗量子计算攻击数字签名的技术路线主要包括基于格的设计、基于编码的设计、基于同源的设计、基于多变量的设计、基于MPC-in-the-Head的设计和基于杂凑函数的设计.由于基于杂凑函数的数字签名算法不依赖于任何“结构化”的困难问题，其安全性是*保守的.
1.1基于杂凑函数的数字签名
基于杂凑函数的数字签名算法（Hash-Based Digital Signature Schemes，简称HBS）的研究历史悠久，*早可以追溯到1976年.在《密码学的新方向》M这篇里程碑式的论文中，Diffie和Heilman提出了一种利用单向函数对一比特数据进行签名的方案.在该方案中，我们随机选择一对n比特串Gx作为私钥，并令为相应的公钥，其中哎—哎为一个单向函数.那么，消息6G的签名为的原像xb.后来，Lamport对这一方案进行了推广，给出了一个适用于任意长度消息的一次性数字签名算法队一次性数字签名算法的一个公私钥对只能对一个消息进行签名，多次签名会破坏算法的安全性.通过将N个一次性数字签名的实例作为叶子节点组织在一个Merkle树中，可以构造一个N次签名算法.经过40余年的发展，这种设计数字签名的技术路线逐渐成熟.基于杂凑函数的数字签名包括带状态的数字签名和无状态数字签名两类，其中带状态的数字签名在每次签名后都需要对私钥状态进行更新，且确保正确的私钥状态更新对保证算法的安全性至关重要.
对比其他后量子签名体制的设计方法，基于杂凑函数的设计有很多优势.**，它是目前所有后量子签名体制中安全性*可靠的方案，这类方案的安全性本质上只依赖于底层杂凑函数的抗（第二）原像攻击的安全性（注意，根据目前的研究，即使是被破解了的MD5算法也是具备抗原像攻击的性质的），而不依赖其他结构性安全假设.并且，基于杂凑函数的签名体制的底层杂凑函数是可替换的，一旦发现当前使用的杂凑函数有安全问题，可以直接替换一个安全的杂凑函数.第二，基于杂凑函数的数字签名算法的公私钥尺寸较小，验签性能高.第三，基于杂凑函数的数字签名算法的参数选项丰富，可以根据应
目录
目录
第1章 引言 1
1.1 基于杂凑函数的数字签名 2
1.2 基于杂凑函数的数字签名的标准化现状 3
1.3章节安排和阅读建议 4
第2章 杂凑函数 6
2.1 杂凑函数的定义及其安全性质 6
2.2 Merkle-Damgard结构 7
2.2.1 针对MD结构的长消息第二原像攻击 10
2.2.2 针对MD结构的选择目标强制前缀第二原像攻击 12
2.2.3 针对MD结构的多碰撞攻击 15
2.2.4 消息认证码与MD结构的杂凑函数 16
2.3 海绵结构 16
2.4 杂凑函数SHA-1 22
2.5 杂凑函数SHA-2 24
2.5.1 SHA-224 24
2.5.2 SHA-256 27
2.5.3 SHA-384 28
2.5.4 SHA-512 30
2.5.5 SHA-512/224 32
2.5.6 SHA-512/256 33
2.6 杂凑函数SM3 35
2.7 杂凑函数SHA-3 37
2.7.1 Keccak-p[b，nr]置换的状态数组 37
2.7.2 Keccak-p置换的轮函数 40
2.7.3 SHA-3杂凑函数和可扩展输出函数 47
2.8 基于杂凑函数构造的伪随机函数 49
2.8.1 消息认证码HMAC 49
2.8.2 MGF1掩码生成函数 49
第3章 数字签名 51
3.1 数字签名的定义及安全性质 51
3.2 Hash-and-Sign范式 53
3.3 不依赖杂凑函数抗碰撞性的Hash-and-Sign范式 54
第4章 基于杂凑函数的一次性数字签名 57
4.1 Lamport-Diffie一次性数字签名 57
4.2 Winternitz一次性数字签名 58
4.3 WOTS+一次性数字签名 62
4.3.1 WOTS+公私钥对生成方法 62
4.3.2 WOTS+签名生成过程 63
4.4 降低WOTS型数字签名私钥和公钥尺寸 64
4.4.1 降低私钥尺寸 65
4.4.2 降低公钥尺寸 65
第5章 抗伪造攻击编码方案 68
5.1 Winternitz编码方案 69
5.2 常数和编码 70
5.3 Winternitz编码与常数和编码的关系 82
5.4 编码方案对WOTS型签名尺寸的影响 83
第6章 基于杂凑函数的FTS签名方案 85
6.1 HORS签名方案及其相关改进版本 86
6.2 FORS签名方案 88
6.3 FORC签名方案 92
第7章 基于杂凑函数的带状态数字签名 96
7.1 带状态的数字签名算法 LMS 97
7.1.1 LMS公私钥对的生成 97
7.1.2 LMS的签名算法 101
7.1.3 LMS的签名验证算法 103
7.2 HSS数字签名算法 104
7.2.1 HSS公私钥对生成方法 106
7.2.2 HSS签名生成与验证 107
7.3 带状态的数字签名算法XMSS 108
7.3.1 XMSS及XMSS-MT中使用的函数 109
7.3.2 ADRS数据结构 111
7.3.3 WOTS+一次性签名.114
7.3.4 XMSS公私钥对生成方法 117
7.3.5 XMSS数字签名生成方法 120
7.3.6 XMSS签名验证过程 121
7.4 带状态的数字签名算法XMSS-MT 123
7.4.1 XMSS-MT公私钥对生成方法 124
7.4.2 XMSS-MT签名生成方法 127
7.4.3 XMSS-MT签名验证过程 129
7.5 状态管理 130
第8章 树遍历算法.132
8.1 TreeHash算法 133
8.2 ** Merkle树遍历算法 141
8.2.1 算法描述 151
8.2.2 算法复杂度分析 162
8.3 对数Merkle树遍历算法 163
8.3.1 **树遍历算法和对数树遍历算法的比较 163
8.3.2 对数树遍历算法中栈更新的优先级 165
8.3.3 对数树遍历算法复杂度分析 181
8.4 分形 Merkle树遍历算法 182
8.4.1 算法描述 184
8.4.2 算法复杂度分析 194
第9章 无状态数字签名算法 SPHINCS+ 196
9.1 SPHINCS+中杂凑函数的使用 198
9.2 SPHINCS+的超树结构 200
9.3 ADRS数据结构 203
9.4 一次性签名算法WOTS+ 206
9.5 无状态多次签名算法 FORS 209
9.5.1 FORS的私钥和公钥 209
9.5.2 FORS的签名与验签 210
9.6 XMSS树的构造及XMSS签名的生成 213
9.7 超树签名的生成 214
9.8 SPHINCS+签名算法 216
9.9 预哈希及SLH-DSA签名生成 217
9.10 SPHINCS+组件参数与安全强度的关系 218
9.11 SPHINCS+的优化.220
9.11.1 SPHINCS-α 221
9.11.2 SPHINCS+C 221
参考文献 223
“密码理论与技术丛书”已出版书目 229
试读
第1章引言
数字签名可以确保数据的完整性（Integrity）和来源真实性（Authenticity）.在数字签名方案中，签名方拥有一个公私钥对（pk，sk），其中sk是私钥（签名方需对其保密），pk是公钥（可以公开签名者可以使用私钥sk对消息msg进行签名，任何知道公钥pk的实体都可以验证这个签名的真伪.可以公开验证真伪，是数字签名的一个重要性质，这意味着一个消息的签名可以出示给第三方，知道正确公钥的第三方可以正确地验证该签名的真伪.另外，由于只有知道私钥的实体才能进行签名，因此当一个实体给一个消息签名后，它也很难对其签名行为进行抵赖.这些特点与同样可以提供完整性和真实性保护的对称密码方案消息认证码（Message Authentication Code，MAC）有显著区别.消息认证码只能由私钥拥有者进行验证，且知道私钥的双方都可以计算任意消息的认证码，因此MAC也无法提供抗抵赖性.同时，数字签名也在一定程度上避免了消息认证码中密钥分配和管理的复杂性.但要注意，如何可靠地公布（和签名实体绑定的）公钥并不是一个平凡问题，错误的公钥信息可能带来灾难性的安全问题，公钥基础设施（PublicKey Infrastructure，PKI）体系就是一种系统地解决安全发布公钥的方案.
数字签名的应用极为广泛，在TLS协议、PKI、软件更新、操作系统安全启动、区块链等系统中发挥了重要作用.当前大规模部署和应用的数字签名包括国际标准RSA、ECDSA和我国商用密码标准SM2等.然而，由于Shor算法可以在量子计算模型下以多项式时间复杂度分解大整数和求解离散对数，一旦大规模通用量子计算机问世，现行的基于大整数分解和离散对数求解困难性的数字签名算法（如RSA、ECDSA和SM2等）的安全性将受到严重威胁W.尽管目前学术界和产业界对是否可以成功制造出大规模通用量子计算机还存在争议，但该领域的研究进展迅速，全球主要国家对向抗量子计算攻击密码算法迁移的必要性已达成广泛的共识.实际上，只要无法证明通用量子计算机不可实现，向抗量子计算攻击算法的迁移就是必要甚至紧迫的.其一，技术突破无法被预测，各国政府在量子计算领域投入了大量资源，由于量子计算的颠覆性，率先取得突破的国家有较高可能不会公布其相关成果.其二，密码算法的迁移需要较长的时间周期，向后量子密码算法的迁移必须远远早于量子计算机成功制造的时间.其三，将基于传统密码体系保护的加密流量保存起来并等待量子计算机成功制造后再解密的囤积攻击（Store Now Decrypt Later）进一步加剧了向后量子密码迁移的迫切性.*后，越来越多的企业将支持后量子算法作为可以进行大力宣传的产品优势，不具备抗量子计算攻击能力的产品将在未来产业竞争中处于劣势地位.
由于量子计算对对称密码的影响有限，我们目前所说的后量子密码主要是指抗量子计算攻击公钥密码.更具体地，主要是指密钥封装（KEM）/公钥加密（PKE）和数字签名（DSA）.本书主要关注数字签名算法.目前构造抗量子计算攻击数字签名的技术路线主要包括基于格的设计、基于编码的设计、基于同源的设计、基于多变量的设计、基于MPC-in-the-Head的设计和基于杂凑函数的设计.由于基于杂凑函数的数字签名算法不依赖于任何“结构化”的困难问题，其安全性是*保守的.
1.1基于杂凑函数的数字签名
基于杂凑函数的数字签名算法（Hash-Based Digital Signature Schemes，简称HBS）的研究历史悠久，*早可以追溯到1976年.在《密码学的新方向》M这篇里程碑式的论文中，Diffie和Heilman提出了一种利用单向函数对一比特数据进行签名的方案.在该方案中，我们随机选择一对n比特串Gx作为私钥，并令为相应的公钥，其中哎—哎为一个单向函数.那么，消息6G的签名为的原像xb.后来，Lamport对这一方案进行了推广，给出了一个适用于任意长度消息的一次性数字签名算法队一次性数字签名算法的一个公私钥对只能对一个消息进行签名，多次签名会破坏算法的安全性.通过将N个一次性数字签名的实例作为叶子节点组织在一个Merkle树中，可以构造一个N次签名算法.经过40余年的发展，这种设计数字签名的技术路线逐渐成熟.基于杂凑函数的数字签名包括带状态的数字签名和无状态数字签名两类，其中带状态的数字签名在每次签名后都需要对私钥状态进行更新，且确保正确的私钥状态更新对保证算法的安全性至关重要.
对比其他后量子签名体制的设计方法，基于杂凑函数的设计有很多优势.**，它是目前所有后量子签名体制中安全性*可靠的方案，这类方案的安全性本质上只依赖于底层杂凑函数的抗（第二）原像攻击的安全性（注意，根据目前的研究，即使是被破解了的MD5算法也是具备抗原像攻击的性质的），而不依赖其他结构性安全假设.并且，基于杂凑函数的签名体制的底层杂凑函数是可替换的，一旦发现当前使用的杂凑函数有安全问题，可以直接替换一个安全的杂凑函数.第二，基于杂凑函数的数字签名算法的公私钥尺寸较小，验签性能高.第三，基于杂凑函数的数字签名算法的参数选项丰富，可以根据应
