密码学安全

参考

从数学定理到工程实践，密码学和信息安全所涉及的知识体系十分繁杂。本章将介绍与区块链密切相关的安全知识，包括 Hash 算法与摘要、加密算法、数字签名和证书、PKI 体系、Merkle 树、布隆过滤器、同态加密等。通过本章，读者可以了解常见安全技术体系，以及如何实现信息安全的核心要素：机密性、完整性、可认证性和不可抵赖性，为后续理解区块链的设计奠定基础。

Hash 算法与数字摘要

常见算法

常见的 Hash 算法包括 MD5、SHA-1、SHA-2、SHA-3 和国产 SM3，其中 MD5 和 SHA-1 已被成功碰撞，不再适合商用，SHA-2/3 和 SM3 是当前主流安全算法。

目前常见的 Hash 算法包括国际上的 Message Digest（MD）系列和 Secure Hash Algorithm（SHA）系列算法，以及国内的 SM3 算法。

MD 算法主要包括 MD4 和 MD5 两个算法。MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，其输出为 128 位。MD4 已证明不够安全。MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位进行分组，其输出是 128 位。MD5 比 MD4 更加安全，但过程更加复杂，计算速度要慢一点。MD5 已于 2004 年被成功碰撞，其安全性已不足应用于商业场景。

SHA 算法由美国国家标准与技术院（National Institute of Standards and Technology，NIST）征集制定。首个实现 SHA-0 算法于 1993 年问世，1998 年即遭破解。随后的修订版本 SHA-1 算法在 1995 年面世，它的输出为长度 160 位的 Hash 值，安全性更好。SHA-1 设计采用了 MD4 算法类似原理。SHA-1 已于 2005 年被成功碰撞，意味着无法满足商用需求。

为了提高安全性，NIST 后来制定出更安全的 SHA-224、SHA-256、SHA-384 和 SHA-512 算法（统称为 SHA-2 算法）。新一代的 SHA-3 相关算法也正在研究中。

此外，中国密码管理局于 2010 年 12 月 17 日发布了 GM/T 0004-2012 《SM3 密码杂凑算法》，建立了国内商用密码体系中的公开 Hash 算法标准，已经被广泛应用在数字签名和认证等场景中。

注：MD5 和 SHA-1 算法的破解工作都是由清华大学教授、中国科学院院士王小云主导完成。

数字摘要

数字摘要是 Hash 算法重要用途之一。顾名思义，数字摘要是对原始的数字内容进行 Hash 运算，获取唯一的摘要值。

利用 Hash 函数抗碰撞性特点，数字摘要可以检测内容是否被篡改过。

细心的读者可能会注意到，有些网站在提供文件下载时，会同时提供相应的数字摘要值。用户下载原始文件后可以在本地自行计算摘要值，并与所提供摘要值进行比对，以确保文件内容没有被篡改过。

Hash 攻击与防护

hash 碰撞攻击，可以用加盐（Salt）的方法，Hash 结果和“盐”分别存放在不同的地方。

有时用户设置口令的安全强度不够，采用了一些常见的字符串，如 password、123456 等。有人专门搜集了这些常见口令，计算对应的 Hash 值，制作成字典。这样通过 Hash 值可以快速反查到原始口令。这一类型以空间换时间的攻击方法包括字典攻击和彩虹表攻击（只保存一条 Hash 链的首尾值，相对字典攻击可以节省存储空间）等。

为了防范这一类攻击，可以采用加盐（Salt）的方法。保存的不是原文的直接 Hash 值，而是原文再加上一段随机字符串（即“盐”）之后的 Hash 值。Hash 结果和“盐”分别存放在不同的地方，这样只要不是两者同时泄露，攻击者就很难进行破解。

加解密算法

对称加密

对称密码从实现原理上可以分为两种：分组加密和序列加密。前者将明文切分为定长数据块作为基本加密单位，应用最为广泛。后者则每次只对一个字节或字符进行加密处理，且密码不断变化，只用在一些特定领域（如数字媒介的加密）。

分组加密的代表算法包括 DES、3DES、AES、IDEA 等。

• DES（Data Encryption Standard）：经典的分组加密算法，最早是美国联邦信息处理标准（FIPS）在 1977 年采用（FIPS-46-3），将 64 位明文加密为 64 位的密文，其密钥长度为 64 位（包括 8 位校验码），现在已经很容易被暴力破解；
• 3DES：三重 DES 操作：加密 –> 解密 –> 加密，处理过程和加密强度优于 DES，但现在也被认为不够安全；
• AES（Advanced Encryption Standard）：由美国国家标准研究所（NIST）采用，取代 DES 成为对称加密实现的标准，1997~2000 年 NIST 从 15 个候选算法中评选 Rijndael 算法（由比利时密码学家 Joan Daemon 和 Vincent Rijmen 发明）作为 AES，标准为 FIPS-197。AES 也是分组算法，分组长度为 128、192、256 位三种。AES 的优势在于处理速度快，整个过程可以数学化描述，目前尚未有有效的破解手段；
• IDEA（International Data Encryption Algorithm）：1991 年由密码学家 James Massey 与来学嘉共同提出，设计类似于 3DES，密钥长度增加到 128 位，具有更好的加密强度。

序列加密又称流加密。1949 年，Claude Elwood Shannon（信息论创始人）首次证明，要实现绝对安全的完善保密性（Perfect Secrecy），可以通过“一次性密码本”的对称加密处理。即通信双方每次使用跟明文等长的随机密钥串对明文进行加密处理。序列密码采用了类似的思想，每次通过伪随机数生成器来生成伪随机密钥串。代表算法包括 RC4 等。

总结一下，对称加密算法适用于大量数据的加解密过程，不能用于签名场景，并且需要提前安全地分发密钥。

注：分组加密每次只能处理固定长度的明文，因此对于过长的内容需要采用一定模式进行分割

非对称加密

非对称加密是现代密码学的伟大发明，它有效解决了对称加密需要安全分发密钥的问题。

非对称加密算法优点是公私钥分开，无需安全通道来分发密钥。缺点是处理速度（特别是生成密钥和解密过程）往往比较慢，一般比对称加解密算法慢 2~3 个数量级；同时加密强度也往往不如对称加密。

非对称加密算法的安全性往往基于数学问题，包括大数质因子分解、离散对数、椭圆曲线等经典数学难题。

代表算法包括：RSA、ElGamal、椭圆曲线、SM2 等系列算法。

• RSA：经典的公钥算法，1978 年由 Ron Rivest、Adi Shamir、Leonard Adleman 共同提出，三人于 2002 年因此获得图灵奖。算法利用了对大数进行质因子分解困难的特性，但目前还没有数学证明两者难度等价，或许存在未知算法可以绕过大数分解而进行解密。
  • 原理：大数分解
• ElGamal：由 Taher ElGamal 设计，利用了模运算下求离散对数困难的特性，比 RSA 产生密钥更快。被应用在 PGP 等安全工具中。
• 椭圆曲线算法（Elliptic Curve Cryptography，ECC）：应用最广也是强度最高的系列算法，基于对椭圆曲线上特定点进行特殊乘法逆运算（求离散对数）难以计算的特性。最早在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出。ECC 系列算法具有多种国际标准（包括 ANSI X9.63、NIST FIPS 186-2、IEEE 1363-2000、ISO/IEC 14888-3 等），一般被认为具备较高的安全性，但加解密过程比较费时。其中，密码学家 Daniel J.Bernstein 于 2006 年提出的 Curve25519/Ed25519/X25519 等算法（分别解决加密、签名和密钥交换），由于其设计完全公开、性能突出等特点，近些年引起了广泛关注和应用。
• SM2（ShangMi 2）：中国国家商用密码系列算法标准，由中国密码管理局于 2010 年 12 月 17 日发布，同样基于椭圆曲线算法，一般认为其安全强度优于 RSA 系列算法。

非对称加密算法适用于签名场景或密钥协商过程，但不适于大量数据的加解密。除了 SM2 之外，大部分算法的签名速度要比验签速度慢（1~2个数量级）。

RSA 类算法被认为已经很难抵御现代计算设备的破解，一般推荐商用场景下密钥至少为 2048 位。如果采用安全强度更高的椭圆曲线算法，256 位密钥即可满足绝大部分安全需求。

混合加密机制

混合加密机制同时结合了对称加密和非对称加密的优点。

该机制的主要过程为：先用非对称加密（计算复杂度较高）协商出一个临时的对称加密密钥（或称会话密钥），然后双方再通过对称加密算法（计算复杂度较低）对所传递的大量数据进行快速的加密处理。

典型的应用案例是网站中使用越来越普遍的通信协议 – 安全超文本传输协议（Hyper Text Transfer Protocol Secure，HTTPS）。

加密算法套件包括一组算法，包括交换、认证、加密、校验等：

• 密钥交换算法：负责协商对称密钥，常见类型包括 RSA、DH、ECDH、ECDHE 等；
• 证书签名算法：负责验证身份，常见类型包括 RSA、DSA、ECDSA 等；
• 加密数据算法：对建立连接的通信内容进行对称加密，常见类型包括 AES 等;
• 消息认证信息码（MAC）算法：创建报文摘要，验证消息的完整性，常见类型包括 SHA 等。

一个典型的 TLS 密码算法套件可能为 “TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384”，意味着：

• 协商过程算法是 ECDHE（Elliptic Curve Diffie–Hellman Ephemeral），基于椭圆曲线的短期 EH 交换，每次交换都用新的密钥，保障前向安全性；
• 证书签名算法是 ECDSA（Elliptic Curve Digital Signature Algorithm），基于椭圆曲线的签名；
• 加密数据算法是 AES，密钥的长度和初始向量的长度都是 256，模式是 CBC；
• 消息认证信息码算法是 SHA，结果是 384 位。

目前，推荐选用如下的加密算法套件：

• TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
• TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
• TLS_RSA_WITH_AES_256_GCM_SHA384
• TLS_ECDH_ECDSA_WITH_AES_256_GCM_SHA384
• TLS_ECDH_RSA_WITH_AES_256_GCM_SHA384
• TLS_DHE_RSA_WITH_AES_256_GCM_SHA384

消息认证码与数字签名

消息认证码

消息认证码（Hash-based Message Authentication Code，HMAC），利用对称加密，对消息完整性（Integrity）进行保护。

基本过程为对某个消息，利用提前共享的对称密钥和 Hash 算法进行处理，得到 HMAC 值。该 HMAC 值持有方可以向对方证明自己拥有某个对称密钥，并且确保所传输消息内容未被篡改。

典型的 HMAC 生成算法包括 K，H，M 三个参数。K 为提前共享的对称密钥，H 为提前商定的 Hash 算法（如 SHA-256），M 为要传输的消息内容。三个参数缺失了任何一个，都无法得到正确的 HMAC 值。

消息认证码可以用于简单证明身份的场景。如 Alice、Bob 提前共享了 K 和 H。Alice 需要知晓对方是否为 Bob，可发送一段消息 M 给 Bob。Bob 收到 M 后计算其 HMAC 值并返回给 Alice，Alice 检验收到 HMAC 值的正确性可以验证对方是否真是 Bob。

数字签名

类似在纸质合同上进行签名以确认合同内容和证明身份，数字签名既可以证实某数字内容的完整性，又可以确认其来源（即不可抵赖，Non-Repudiation）。

一个典型的场景是，Alice 通过信道发给 Bob 一个文件（一份信息），Bob 如何获知所收到的文件即为 Alice 发出的原始版本？Alice 可以先对文件内容进行摘要，然后用自己的私钥对摘要进行加密（签名），之后同时将文件和签名都发给 Bob。Bob 收到文件和签名后，用 Alice 的公钥来解密签名，得到数字摘要，与对文件进行摘要后的结果进行比对。如果一致，说明该文件确实是 Alice 发过来的（因为别人无法拥有 Alice 的私钥），并且文件内容没有被修改过（摘要结果一致）。

理论上所有的非对称加密算法都可以用来实现数字签名，实践中常用算法包括 1991 年 8 月 NIST 提出的 DSA（Digital Signature Algorithm，基于 ElGamal 算法）和安全强度更高的 ECDSA（Elliptic Curve Digital Signature Algorithm，基于椭圆曲线算法）等。

除普通的数字签名应用场景外，针对一些特定的安全需求，产生了一些特殊数字签名技术，包括盲签名、多重签名、群签名、环签名等。

签名算法

• RSA签名：基于加密/解密，通过私钥加密哈希值，公钥解密验证哈希一致性。
• ECDSA/DSA：基于椭圆曲线/离散对数，通过数学计算验证签名。
  • ECDSA 签名具有一定的延展性（同一交易的签名可以有多种合法表示）
  • 比特币的签名使用的是 椭圆曲线数字签名算法（ECDSA），具体基于 secp256k1 曲线。签名可以用来验证一个交易确实是由对应私钥持有者发起的。
• EdDSA：基于椭圆曲线，具有更高的安全性和效率，主要用于现代加密系统。
• HMAC：基于哈希的认证，不涉及公钥基础设施，依赖共享密钥。

验证过程

用户私钥 + 交易摘要 ---> ECDSA签名 ---> (r,s)
                                ↓
            比特币网络节点使用交易公钥验证 (r,s)
                                ↓
                 如果验证成功 → 接收该交易

盲签名

盲签名（Blind Signature），1982 年由 David Chaum 在论文《Blind Signatures for Untraceable Payment》中提出。签名者需要在无法看到原始内容的前提下对信息进行签名。

盲签名可以实现对所签名内容的保护，防止签名者看到原始内容；另一方面，盲签名还可以实现防止追踪（Unlinkability），签名者无法将签名内容和签名结果进行对应。典型的实现包括 RSA 盲签名算法等。

多重签名

多重签名（Multiple Signature），即 n 个签名者中，收集到至少 m 个（n >= m >= 1）的签名，即认为合法。

其中，n 是提供的公钥个数，m 是需要匹配公钥的最少的签名个数。

多重签名可以有效地应用在多人投票共同决策的场景中。例如双方进行协商，第三方作为审核方。三方中任何两方达成一致即可完成协商。

比特币交易中就支持多重签名，可以实现多个人共同管理某个账户的比特币交易。

群签名

群签名（Group Signature），即某个群组内一个成员可以代表群组进行匿名签名。签名可以验证来自于该群组，却无法准确追踪到签名的是哪个成员。

群签名需要一个群管理员来添加新的群成员，因此存在群管理员可能追踪到签名成员身份的风险。

群签名最早在 1991 年由 David Chaum 和 Eugene van Heyst 提出。

环签名

环签名（Ring Signature），由 Rivest，Shamir 和 Tauman 三位密码学家在 2001 年首次提出。环签名属于一种简化的群签名。

签名者首先选定一个临时的签名者集合，集合中包括签名者自身。然后签名者利用自己的私钥和签名集合中其他人的公钥就可以独立地产生签名，而无需他人的帮助。签名者集合中的其他成员可能并不知道自己被包含在最终的签名中。

环签名在保护匿名性方面也具有很多用途。

数字证书

数字证书机制正是为了解决这个问题，它就像日常生活中的证书一样，可以确保所记录信息的合法性。比如证明某个公钥是某个实体（个人或组织）拥有，并且确保任何篡改都能被检测出来，从而实现对用户公钥的安全分发。

根据所保护公钥的用途，数字证书可以分为加密数字证书（Encryption Certificate）和签名验证数字证书（Signature Certificate）。前者往往用于保护用于加密用途的公钥；后者则保护用于签名用途的公钥。两种类型的公钥也可以同时放在同一证书中。

一般情况下，证书需要由证书认证机构（Certification Authority，CA）来进行签发和背书。权威的商业证书认证机构包括 DigiCert、GlobalSign、VeriSign 等。用户也可以自行搭建本地 CA 系统，在私有网络中进行使用。

一般的，一个数字证书内容可能包括证书域（证书的版本、序列号、签名算法类型、签发者信息、有效期、被签发主体、签发的公开密钥）、CA 对证书的签名算法和签名值等。

X.509 规范中一般推荐使用 PEM（Privacy Enhanced Mail）格式来存储证书相关的文件。证书文件的文件名后缀一般为 .crt 或 .cer，对应私钥文件的文件名后缀一般为 .key，证书请求文件的文件名后缀为 .csr。有时候也统一用 .pem 作为文件名后缀。

PEM 格式采用文本方式进行存储，一般包括首尾标记和内容块，内容块采用 base64 编码。

证书中记录了大量信息，其中最重要的包括 签发的公开密钥 和 CA 数字签名 两个信息。因此，只要使用 CA 的公钥再次对这个证书进行签名比对，就能证明所记录的公钥是否合法。比对过程就是：用 CA 的公钥去“解密”证书的签名部分，看看解密出来的摘要是否和用证书内容自己算出来的摘要一致。

读者可能会想到，怎么证明用来验证对实体证书进行签名的 CA 公钥自身是否合法呢？毕竟在获取 CA 公钥的过程中，它也可能被篡改掉。

实际上，CA 的公钥是否合法，一方面可以通过更上层的 CA 颁发的证书来进行认证；另一方面某些根 CA（Root CA）可以通过预先分发证书来实现信任基础。例如，主流操作系统和浏览器里面，往往会提前预置一些权威 CA 的证书（通过自身的私钥签名，系统承认这些是合法的证书）。之后所有基于这些 CA 认证过的中间层 CA（Intermediate CA）和后继 CA 都会被验证合法。这样就从预先信任的根证书，经过中间层证书，到最底下的实体证书，构成一条完整的证书信任链。

某些时候用户在使用浏览器访问某些网站时，可能会被提示是否信任对方的证书。这说明该网站证书无法被当前系统中的证书信任链进行验证，需要进行额外检查。另外，当信任链上任一证书不可靠时，则依赖它的所有后继证书都将失去保障。

可见，证书作为公钥信任的基础，对其生命周期进行安全管理十分关键。后面章节将介绍的 PKI 体系提供了一套完整的证书管理的框架，包括生成、颁发、撤销过程等。

Merkle 树结构

todo: 学习https://nicodechal.github.io/2019/03/03/ethereum-mpt-2/

默克尔树（又叫哈希树）是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出，曾广泛用于文件系统和 P2P 系统中。

其主要特点为：

• 最下面的叶节点包含存储数据或其哈希值；
• 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。

进一步地，默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。

默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。

目前，默克尔树的典型应用场景包括如下几种。

证明某个集合中存在或不存在某个元素

通过构建集合的默克尔树，并提供该元素各级兄弟节点中的 Hash 值，可以不暴露集合完整内容而证明某元素存在。

另外，对于可以进行排序的集合，可以将不存在元素的位置用空值代替，以此构建稀疏默克尔树（Sparse Merkle Tree）。该结构可以证明某个集合中不包括指定元素。

元素存在性证明（Merkle Proof）

通过对集合构建一棵默克尔树（Merkle Tree），可以在不暴露集合全部内容的情况下，证明某个元素属于该集合。 具体做法是：提供该元素对应叶子节点到根节点路径上，各层级兄弟节点的哈希值。验证方只需利用这些哈希值逐层计算，即可还原并验证最终的 Merkle Root，从而确认该元素的存在性。

元素不存在性证明（Sparse Merkle Tree）

对于可排序、键空间固定的集合，可以使用稀疏默克尔树（Sparse Merkle Tree，SMT）来证明某个元素不存在。 SMT 会为整个键空间预定义叶子位置，未被占用的位置使用空值（如默认哈希）填充。 当需要证明某元素不存在时，只需证明该元素对应位置的叶子节点为“空值”，并提供从该叶子到根节点的默克尔路径，即可完成不存在性证明。

快速比较大量数据

对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时，则意味着所代表的两组数据必然相同。否则，必然不同。

由于 Hash 计算的过程可以十分快速，预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势。

                    Root
                     │
            ┌────────┴────────┐
            │                 │
           N4                N5
            │                 │
      ┌─────┴─────┐     ┌─────┴─────┐
      │           │     │           │
     N1          N2    N3          N6
      │           │     │           │
   ┌──┴──┐     ┌──┴──┐ ┌──┴──┐   ┌──┴──┐
   │     │     │     │ │     │   │     │
  D0    D1    D2    D3 D4    D5  D6    D7

快速定位修改

基于数据 D0……D3 构造默克尔树，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。

因此，一旦发现某个节点如 Root 的数值发生变化，沿着 Root –> N4 –> N1，最多通过 O(lgN) 时间即可快速定位到实际发生改变的数据块 D1。

零知识证明

仍以上图为例，如何向他人证明拥有某个数据 D0 而不暴露其它信息。挑战者提供随机数据 D1，D2 和 D3，或由证明人生成（需要加入特定信息避免被人复用证明过程）。

证明人想向验证者证明：

我确实拥有数据 D0，并且 D0 已经参与了某个承诺（Root）

同时满足两个约束：

• 不暴露除 D0 以外的任何原始数据
• 验证者无法伪造这个证明

目标 证明：自己确实拥有数据 D0，且不泄露其它数据。

前提

• 使用 Hash + Merkle Tree
• Hash 不可逆、不可伪造

挑战（防作弊）

• 验证者提供随机数据 D1, D2, D3
• 防止提前构造或复用证明

构造

N1 = H(D0 || D1)
N2 = H(D2 || D3)
Root = H(N1 || N2)

证明人公开

• D0
• N2
• Root

验证方式

N1'   = H(D0 || D1)
Root' = H(N1' || N2)

验证：Root' == Root

能证明什么

• D0 真实参与了 Root 的构造（存在性）
• Root 未被伪造

不会泄露

• D1 / D2 / D3
• 其它数据内容或结构

说明

• 属于 Merkle Proof / Hash Commitment
• 非严格 zk-SNARK