工程领域从来没有黑科技；密码学不仅是工程。

密码学相关的安全技术在整个信息技术领域的重要地位无需多言。如果没有现代密码学和信息安全的研究成果，人类社会根本无法进入信息时代。区块链技术大量依赖了密码学和安全技术的研究成果。

实际上，密码学和安全领域所涉及到的知识体系十分繁杂，本章将介绍密码学领域中跟区块链相关的一些基础知识，包括 Hash 算法与摘要、加密算法、数字签名和证书、PKI 体系、Merkle 树、布隆过滤器、同态加密等。大家通过阅读本文，了解如何使用这些技术保护信息的机密性、完整性、认证性和不可抵赖性。

Hash 算法与数字摘要

定义

Hash（哈希或散列）算法是非常基础也非常重要的计算机算法。它能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash 值），并且不同的明文很难映射为相同的 Hash 值。

例如计算一段话 “hello blockchain world, this is yeasy@github” 的 SHA-256 hash 值。

$ echo "hello blockchain world, this is yeasy@github"|shasum -a 256
db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着对于某个文件，无需查看其内容，只要其 SHA-256 Hash 计算后结果同样为 db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90，则说明文件内容极大概率上就是 “hello blockchain world, this is yeasy@github”。

Hash 值在应用中又常被称为指纹（fingerprint）或摘要（digest）。Hash 的核心思想也经常被应用到基于内容的编址或命名算法中。

一个优秀的 Hash 算法，将能实现：

• 正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值；
• 逆向困难：给定（若干）Hash 值，在有限时间内很难（基本不可能）逆推出明文；
• 输入敏感：原始输入信息发生任何改变，新产生的 Hash 值都应该出现很大不同；
• 冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致（发生碰撞）。

冲突避免有时候又被称为“抗碰撞性”，分为“弱抗碰撞性”和“强抗碰撞性”。如果给定明文前提下，无法找到与之碰撞的其它明文，则算法具有“弱抗碰撞性”；如果无法找到任意两个发生 Hash 碰撞的明文，则称算法具有“强抗碰撞性”。

很多场景下，也往往要求算法对于任意长的输入内容，可以输出定长的 Hash 结果。

常见算法

目前常见的 Hash 算法包括 MD5 和 SHA 系列算法。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。

MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位进行分组，其输出是 128 位。MD5 比 MD4 更加安全，但过程更加复杂，计算速度要慢一点。MD5 已被证明不具备“强抗碰撞性”。

SHA（Secure Hash Algorithm）并非一个算法，而是一个 Hash 函数族。NIST（National Institute of Standards and Technology）于 1993 年发布首个实现。目前知名的 SHA-1 算法在 1995 年面世，它的输出为长度 160 位的 Hash 值，抗穷举性更好。SHA-1 设计时模仿了 MD4 算法，采用了类似原理。SHA-1 已被证明不具备“强抗碰撞性”。

为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

目前，MD5 和 SHA1 已经被破解，一般推荐至少使用 SHA2-256 或更安全的算法。

注：MD5 是一个经典的 Hash 算法，其和 SHA-1 算法都被认为安全性已不足应用于商业场景。

性能

一般情况下，Hash 算法多是计算敏感型。意味着计算资源是瓶颈，主频越高的 CPU 进行 Hash 的速度也越快。因此可以通过硬件加速来提升 Hash 计算的吞吐量。例如采用 FPGA 来计算 MD5 值，可以轻易达到数十 Gbps 的吞吐量。

也有一些 Hash 算法不是计算敏感型的。例如 scrypt算法，计算过程需要大量的内存资源，节点不能通过简单地增加更多 CPU 来获得 Hash 性能的提升。这样的 Hash 算法经常被应用到避免算力攻击的场景下。

数字摘要

顾名思义，数字摘要是对数字内容进行 Hash 运算，获取唯一的摘要值来指代原始完整的数字内容。

数字摘要是 Hash 算法最重要的一个用途。利用 Hash 函数的抗碰撞性特点，数字摘要可以解决确保内容未被篡改过的问题。

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

Hash 攻击与防护

Hash 算法并不是一种加密算法，不能用于对信息的保护。

但 Hash 算法常被应用到对口令的保存上。例如用户登录网站需要通过用户名和密码来进行验证。如果网站后台直接保存用户的口令明文，一旦数据库发生泄露后果不堪设想。大量用户倾向于在多个网站选用相同或关联的口令。

利用 Hash 的特性，后台可以仅保存口令的 Hash 值，这样每次比对 Hash 值一致，则说明输入的口令正确。即便数据库泄露了，也无法从 Hash 值还原回口令，只有进行穷举测试。

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

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

加解密算法

加解密算法是密码学的核心技术，从设计理念上可以分为下面两大基本类型。

算法类型	特点	优势	缺陷	代表算法
对称加密	加解密的密钥相同	计算效率高，加密强度高	需提前共享密钥，易泄露	DES、3DES、AES、IDEA
非对称加密	加解密的密钥不相关	无需提前共享密钥	计算效率低，仍存在中间人攻击可能	RSA、ElGamal、椭圆曲线系列算法

加解密系统基本组成

现代加解密系统的典型组件一般包括：加解密算法、加密密钥、解密密钥。

其中，加解密算法自身是固定不变的，并且一般是公开可见的；密钥则是最关键的信息，需要安全地保存起来，甚至通过特殊硬件进行保护。一般来说，对同一种算法，密钥需要按照特定算法每次加密前随机生成，长度越长，则加密强度越大。

加密过程中，通过加密算法和加密密钥，对明文进行加密，获得密文。

解密过程中，通过解密算法和解密密钥，对密文进行解密，获得明文。

根据加解密过程中所使用的密钥是否相同，算法可以分为对称加密（Symmetric Cryptography，又称公共密钥加密，Common-key cryptography）和非对称加密（Asymmetric Cryptography，又称公钥加密，Public-key Cryptography）。两种模式适用于不同的需求，恰好形成互补。某些时候可以组合使用，形成混合加密机制。

并非所有加密算法的安全性都可以从数学上得到证明。公认的高强度的加密算法和实现往往是在经过长时间各方面充分实践论证后，才被大家所认可，但不代表其绝对不存在漏洞。另一方面，自行设计和发明未经过大规模验证的加密算法是一种不太明智的行为。即便不公开算法加密过程，也很容易被攻破，无法在安全性上得到保障。

实际上，密码学实现的安全往往是通过算法所依赖的数学问题来提供，而并非通过对算法的实现过程进行保密。

对称加密算法

对称加密算法，顾名思义，加密和解密过程的密钥是相同的。

该类算法优点是加解密效率（速度快，空间占用小）和加密强度都很高。

缺点是参与方都需要提前持有密钥，一旦有人泄露则安全性被破坏；另外如何在不安全通道中提前分发密钥也是个问题，需要借助 Diffie–Hellman 协议或非对称加密方式来实现。

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

分组对称加密代表算法包括 DES、3DES、AES、IDEA 等：

• DES（Data Encryption Standard）：经典的分组加密算法，最早是 1977 年美国联邦信息处理标准（FIPS）采用 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 等。

对称加密算法适用于大量数据的加解密过程；不能用于签名场景；并且往往需要提前分发好密钥。

注：分组加密每次只能处理固定长度的明文，因此对于过长的内容需要采用一定模式进行分割加密，《实用密码学》一书中推荐使用密文分组链（Cipher Block Chain，CBC）、计数器（Counter，CTR）等模式。

非对称加密算法

非对称加密是现代密码学历史上一项伟大的发明，可以很好地解决对称加密中提前分发密钥的问题。

顾名思义，非对称加密算法中，加密密钥和解密密钥是不同的，分别被称为公钥（Public Key）和私钥（Private Key）。私钥一般需要通过随机数算法生成，公钥可以根据私钥生成。

其中，公钥一般是公开的，他人可获取的；私钥一般是个人自己持有，不能被他人获取。

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

非对称加密算法的安全性往往需要基于数学问题来保障，目前主要有基于大数质因子分解、离散对数、椭圆曲线等经典数学难题进行保护。

代表算法包括：RSA、ElGamal、椭圆曲线（Elliptic Curve Crytosystems，ECC）、SM2 等系列算法。

• RSA：经典的公钥算法，1978 年由 Ron Rivest、Adi Shamir、Leonard Adleman 共同提出，三人于 2002 年因此获得图灵奖。算法利用了对大数进行质因子分解困难的特性，但目前还没有数学证明两者难度等价，或许存在未知算法在不进行大数分解的前提下解密。
• Diffie-Hellman 密钥交换：基于离散对数无法快速求解，可以在不安全的通道上，双方协商一个公共密钥。
• ElGamal：由 Taher ElGamal 设计，利用了模运算下求离散对数困难的特性。被应用在 PGP 等安全工具中。
• 椭圆曲线算法（Elliptic Curve Cryptography，ECC）：现代备受关注的算法系列，基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。最早在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出。ECC 系列算法一般被认为具备较高的安全性，但加解密计算过程往往比较费时。
• SM2（ShangMi 2）：国家商用密码算法，由国家密码管理局于 2010 年 12 月 17 日发布，同样基于椭圆曲线算法，加密强度优于 RSA 系列算法。

非对称加密算法一般适用于签名场景或密钥协商，但不适于大量数据的加解密。

目前 RSA 类算法被认为可能在不远的将来被破解，一般推荐可采用安全强度更高的椭圆曲线系列算法。

选择明文攻击

细心的读者可能会意识到，在非对称加密中，由于公钥是公开可以获取的，因此任何人都可以给定明文，获取对应的密文，这就带来选择明文攻击的风险。

为了规避这种风险，现有的非对称加密算法（如 RSA、ECC）都引入了一定的保护机制。对同样的明文使用同样密钥进行多次加密，得到的结果完全不同，这就避免了选择明文攻击的破坏。

在实现上可以有多种思路。一种是对明文先进行变形，添加随机的字符串或标记，再对添加后结果进行处理。另外一种是先用随机生成的临时密钥对明文进行对称加密，然后再对对称密钥进行加密，即混合利用了多种加密机制。

混合加密机制

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

即先用计算复杂度高的非对称加密协商出一个临时的对称加密密钥（也被称为会话密钥，一般相对所加密内容来说要短的多），然后双方再通过对称加密算法对传递的大量数据进行快速的加解密处理。

典型的应用案例是现在越来越普遍的 Web 通信协议 — HTTPS （Hyper Text Transfer Protocol Secure）协议。

与以明文方式传输数据的 HTTP 协议不同，HTTPS 在传统的 HTTP 层和 TCP 层之间通过引入 Transport Layer Security/Secure Socket Layer（TLS/SSL）加密层来实现可靠的传输。

SSL 协议是初期实现 HTTPS 的标准协议，最早由 Netscape 于 1994 年设计实现，其两个主要版本（包括 v2.0 和 v3.0）曾得到大量应用。SSL 存在安全缺陷易受攻击（如 POODLE 和 DROWN 攻击），无法满足现代安全需求，已于 2011 和 2015 年被 IETF 宣布废弃。基于 SSL 协议（v3.1），IETF 提出了改善的安全标准协议 TLS，成为目前广泛采用的 HTTPS 方案。2008 年，TLS 发布了目前使用最广泛的 1.2 版本，修正了之前版本的不少漏洞，极大增强了安全性，推荐作为默认的 TLS 方案。除了 Web 服务外，TLS 协议也被广泛应用到 FTP、Email、实时消息、音视频通话等领域。

采用 HTTPS 建立安全连接（TLS 握手协商过程）的基本步骤如下：

• 客户端浏览器发送握手信息到服务器，包括随机数 R1、支持的加密算法套件（Cipher Suite）类型、协议版本、压缩算法等。注意该过程为明文。
• 服务端返回信息，包括随机数 R2、选定加密算法套件、协议版本，以及服务器证书。注意该过程为明文。
• 浏览器检查带有该网站公钥的证书。该证书需要由第三方 CA 来签发，浏览器和操作系统会预置权威 CA 的根证书。如果证书被篡改作假（中间人攻击），很容易通过 CA 的证书验证出来。
• 如果证书没问题，则客户端用服务端证书中公钥加密随机数 R3（又叫 Pre-MasterSecret），发送给服务器。此时，只有客户端和服务器都拥有 R1、R2 和 R3 信息，基于随机数 R1、R2 和 R3，双方通过伪随机数函数来生成共同的对称会话密钥 MasterSecret。
• 后续客户端和服务端的通信都通过协商后的对称加密（如 AES）进行保护。

可以看出，该过程是实现防止中间人窃听和篡改的前提下完成会话密钥的交换。为了保障前向安全性（Perfect Forward Secrecy），TLS 对每个会话连接都可以生成不同的密钥，避免某个会话密钥泄露后对其它会话连接产生安全威胁。需要注意，选用合适的加密算法套件对于 TLS 的安全性十分重要。要合理选择安全强度高的算法组合，如 ECDHE-RSA 和 ECDHE-ECDSA 等，而不要使用安全性较差的 DES/3DES 等。

示例中对称密钥的协商过程采用了 RSA 非对称加密算法，实践中也可以通过 Diffie–Hellman（DH）协议来完成。

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

• 密钥交换算法：负责协商对称密钥，常见类型包括 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

注：TLS 1.0 版本已被发现存在安全漏洞，NIST、HIPAA 于 2014 年公开建议停用该版本的 TLS 协议。

离散对数与 Diffie–Hellman 密钥交换协议

Diffie–Hellman（DH）密钥交换协议是一个经典的协议，最早发表于 1976 年，应用十分广泛。使用该协议可以在不安全信道完成对称密钥的协商，以便后续通信采用对称加密。

DH 协议的设计基于离散对数问题（Discrete Logarithm Problem，DLP）。离散对数问题是指对于一个很大的素数 p，已知 g 为 p 的模循环群的原根，给定任意 x，求解 X=g^x mod p 是可以很快获取的。但在已知 p，g 和 X 的前提下，逆向求解 x 目前没有多项式时间实现的算法。该问题同时也是 ECC 类加密算法的基础。

DH 协议的基本交换过程如下：

• Alice 和 Bob 两个人协商密钥，先公开商定 p，g；
• Alice 自行选取私密的整数 x，计算 X=g^x mod p，发送 X 给 Bob；
• Bob 自行选取私密的整数 y，计算 Y=g^y mod p，发送 Y 给 A；
• Alice 根据 x 和 Y，求解共同密钥 Z_A=Y^x mod p；
• Bob 根据 X 和 y，求解共同密钥 Z_B=X^y mod p。

实际上，Alice 和 Bob 计算出来的结果将完全相同，因为在 mod p 的前提下，Y^x =(g^y)^x =g^(xy) = (g^x)^y=X^y。而信道监听者在已知 p，g，X，Y 的前提下，无法求得 Z。

消息认证码与数字签名

消息认证码和数字签名技术通过对消息的摘要进行加密，可以被应用到消息防篡改和身份证明问题。

消息认证码

消息认证码，全称是 Hash-based Message Authentication Code（HMAC），即“基于 Hash 的消息认证码”。消息验证码基于对称加密，可以用于对消息完整性（Integrity）进行保护。

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

典型的 HMAC(K, H, Message) 算法包括三个因素，K 为提前共享的对称密钥，H 为提前商定的 Hash 算法（一般为公认的经典算法如 SHA-256），Message 为要处理的消息内容。如果不知道 K 或 H 的任何一个，则无法根据 Message 得到正确的 HMAC 值。

消息认证码一般用于证明身份的场景。如 Alice、Bob 提前共享和 HMCA 的密钥和 Hash 算法，Alice 需要知晓对方是否为 Bob，可发送随机消息给 Bob。Bob 收到消息后进行计算，把消息 HMAC 值返回给 Alice，Alice 通过检验收到 HMAC 值的正确性可以知晓对方是否是 Bob。注意这里并没有考虑中间人攻击的情况，假定信道是安全的。

消息认证码使用过程中主要问题是需要共享密钥。当密钥可能被多方拥有的场景下，无法证明消息来自某个确切的身份。反之，如果采用非对称加密方式，则可以追溯到来源身份，即数字签名。

数字签名

类似在纸质合同上签名确认合同内容和证明身份，数字签名基于非对称加密，既可以用于证实某数字内容的完整性，又同时可以确认来源（或不可抵赖，Non-Repudiation）。

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

知名的数字签名算法包括 DSA（Digital Signature Algorithm）和安全强度更高的 ECSDA（Elliptic Curve Digital Signature Algorithm）等。

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

盲签名

盲签名（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 年首次提出。环签名属于一种简化的群签名。

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

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

安全性

数字签名算法自身的安全性由数学问题进行保障，但在使用上，系统的安全性也十分关键。目前常见的数字签名算法往往需要选取合适的随机数作为配置参数，配置参数不合理的使用或泄露都会造成安全漏洞，需要进行安全保护。

2010 年，SONY 公司因为其 PS3 产品上采用安全的 ECDSA 进行签名时，不慎采用了重复的随机参数，导致私钥被最终破解，造成重大经济损失。

数字证书

对于非对称加密算法和数字签名来说，很重要的一点就是公钥的分发。理论上任何人可以公开获取到对方的公钥。然而这个公钥有没有可能是伪造的呢？传输过程中有没有可能被篡改掉呢？一旦公钥自身出了问题，则整个建立在其上的安全体系的安全性将不复存在。

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

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

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

X.509 证书规范

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

目前使用最广泛的标准为 ITU 和 ISO 联合制定的 X.509 的 v3 版本规范（RFC 5280），其中定义了如下证书信息域：

• 版本号（Version Number）：规范的版本号，目前为版本 3，值为 0x2；
• 序列号（Serial Number）：由 CA 维护的为它所颁发的每个证书分配的唯一的序列号，用来追踪和撤销证书。只要拥有签发者信息和序列号，就可以唯一标识一个证书。最大不能超过 20 个字节；
• 签名算法（Signature Algorithm）：数字签名所采用的算法，如 sha256WithRSAEncryption 或 ecdsa-with-SHA256；
• 颁发者（Issuer）：颁发证书单位的标识信息，如 “C=CN, ST=Beijing, L=Beijing, O=org.example.com, CN=ca.org.example.com”；
• 有效期（Validity）：证书的有效期限，包括起止时间；
• 主体（Subject）：证书拥有者的标识信息（Distinguished Name），如 “C=CN, ST=Beijing, L=Beijing, CN=person.org.example.com”；
• 主体的公钥信息（Subject Public Key Info）：所保护的公钥相关的信息；
  • 公钥算法（Public Key Algorithm）：公钥采用的算法；
  • 主体公钥（Subject Public Key）：公钥的内容；
• 颁发者唯一号（Issuer Unique Identifier）：代表颁发者的唯一信息，仅 2、3 版本支持，可选；
• 主体唯一号（Subject Unique Identifier）：代表拥有证书实体的唯一信息，仅 2、3 版本支持，可选；
• 扩展（Extensions，可选）：可选的一些扩展。v3 中可能包括：
  • Subject Key Identifier：实体的密钥标识符，区分实体的多对密钥；
  • Basic Constraints：一般指明是否属于 CA；
  • Authority Key Identifier：颁发这个证书的颁发者的公钥标识符；
  • CRL Distribution Points：撤销文件的发布地址；
  • Key Usage: 证书的用途或功能信息。

此外，证书的颁发者还需要对证书内容利用自己的私钥进行签名，以防止他人篡改证书内容。

证书格式

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

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

例如，一个示例证书文件的 PEM 格式如下所示。

-----BEGIN CERTIFICATE-----
MIICMzCCAdmgAwIBAgIQIhMiRzqkCljq3ZXnsl6EijAKBggqhkjOPQQDAjBmMQsw
CQYDVQQGEwJVUzETMBEGA1UECBMKQ2FsaWZvcm5pYTEWMBQGA1UEBxMNU2FuIEZy
YW5jaXNjbzEUMBIGA1UEChMLZXhhbXBsZS5jb20xFDASBgNVBAMTC2V4YW1wbGUu
Y29tMB4XDTE3MDQyNTAzMzAzN1oXDTI3MDQyMzAzMzAzN1owZjELMAkGA1UEBhMC
VVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDVNhbiBGcmFuY2lzY28x
FDASBgNVBAoTC2V4YW1wbGUuY29tMRQwEgYDVQQDEwtleGFtcGxlLmNvbTBZMBMG
ByqGSM49AgEGCCqGSM49AwEHA0IABCkIHZ3mJCEPbIbUdh/Kz3zWW1C9wxnZOwfy
yrhr6aHwWREW3ZpMWKUcbsYup5kbouBc2dvMFUgoPBoaFYJ9D0SjaTBnMA4GA1Ud
DwEB/wQEAwIBpjAZBgNVHSUEEjAQBgRVHSUABggrBgEFBQcDATAPBgNVHRMBAf8E
BTADAQH/MCkGA1UdDgQiBCBIA/DmemwTGibbGe8uWjt5hnlE63SUsXuNKO9iGEhV
qDAKBggqhkjOPQQDAgNIADBFAiEAyoMO2BAQ3c9gBJOk1oSyXP70XRk4dTwXMF7q
R72ijLECIFKLANpgWFoMoo3W91uzJeUmnbJJt8Jlr00ByjurfAvv
-----END CERTIFICATE-----

可以通过 openssl 工具来查看其内容。

# openssl x509 -in example.com-cert.pem -noout -text
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            22:13:22:47:3a:a4:0a:58:ea:dd:95:e7:b2:5e:84:8a
    Signature Algorithm: ecdsa-with-SHA256
        Issuer: C=US, ST=California, L=San Francisco, O=example.com, CN=example.com
        Validity
            Not Before: Apr 25 03:30:37 2017 GMT
            Not After : Apr 23 03:30:37 2027 GMT
        Subject: C=US, ST=California, L=San Francisco, O=example.com, CN=example.com
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub:
                    04:29:08:1d:9d:e6:24:21:0f:6c:86:d4:76:1f:ca:
                    cf:7c:d6:5b:50:bd:c3:19:d9:3b:07:f2:ca:b8:6b:
                    e9:a1:f0:59:11:16:dd:9a:4c:58:a5:1c:6e:c6:2e:
                    a7:99:1b:a2:e0:5c:d9:db:cc:15:48:28:3c:1a:1a:
                    15:82:7d:0f:44
                ASN1 OID: prime256v1
        X509v3 extensions:
            X509v3 Key Usage: critical
                Digital Signature, Key Encipherment, Certificate Sign, CRL Sign
            X509v3 Extended Key Usage:
                Any Extended Key Usage, TLS Web Server Authentication
            X509v3 Basic Constraints: critical
                CA:TRUE
            X509v3 Subject Key Identifier:
                48:03:F0:E6:7A:6C:13:1A:26:DB:19:EF:2E:5A:3B:79:86:79:44:EB:74:94:B1:7B:8D:28:EF:62:18:48:55:A8
    Signature Algorithm: ecdsa-with-SHA256
         30:45:02:21:00:ca:83:0e:d8:10:10:dd:cf:60:04:93:a4:d6:
         84:b2:5c:fe:f4:5d:19:38:75:3c:17:30:5e:ea:47:bd:a2:8c:
         b1:02:20:52:8b:00:da:60:58:5a:0c:a2:8d:d6:f7:5b:b3:25:
         e5:26:9d:b2:49:b7:c2:65:af:4d:01:ca:3b:ab:7c:0b:ef

此外，还有 DER（Distinguished Encoding Rules）格式，是采用二进制对证书进行保存，可以与 PEM 格式互相转换。

证书信任链

证书中记录了大量信息，其中最重要的包括 签发的公开密钥 和 CA 数字签名 两个信息。因此，只要使用 CA 的公钥再次对这个证书进行签名比对，就能证明某个实体的公钥是否是合法的。

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

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

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

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

PKI 体系

在非对称加密中，公钥可以通过证书机制来进行保护，但证书的生成、分发、撤销等过程并没有在 X.509 规范中进行定义。

实际上，如何安全地管理和分发证书可以遵循 PKI（Public Key Infrastructure）体系来完成。

PKI 体系核心解决的是证书生命周期相关的认证和管理问题，在现代密码学应用领域处于十分基础和重要的地位。

需要注意，PKI 是建立在公私钥基础上实现安全可靠传递消息和身份确认的一个通用框架，并不代表某个特定的密码学技术和流程。实现了 PKI 规范的平台可以安全可靠地管理网络中用户的密钥和证书。目前包括多个实现和规范，知名的有 RSA 公司的 PKCS（Public Key Cryptography Standards）标准和 X.509 相关规范等。

PKI 基本组件

一般情况下，PKI 至少包括如下核心组件：

• CA（Certification Authority）：负责证书的颁发和吊销（Revoke），接收来自 RA 的请求，是最核心的部分；
• RA（Registration Authority）：对用户身份进行验证，校验数据合法性，负责登记，审核过了就发给 CA；
• 证书数据库：存放证书，多采用 X.500 系列标准格式。可以配合LDAP 目录服务管理用户信息。

其中，CA 是最核心的组件，主要完成对证书信息的维护。

常见的操作流程为，用户通过 RA 登记申请证书，提供身份和认证信息等；CA 审核后完成证书的制造，颁发给用户。用户如果需要撤销证书则需要再次向 CA 发出申请。

证书的签发

CA 对用户签发证书实际上是对某个用户公钥，使用 CA 的私钥对其进行签名。这样任何人都可以用 CA 的公钥对该证书进行合法性验证。验证成功则认可该证书中所提供的用户公钥内容，实现用户公钥的安全分发。

用户证书的签发可以有两种方式。一般可以由 CA 直接来生成证书（内含公钥）和对应的私钥发给用户；也可以由用户自己生成公钥和私钥，然后由 CA 来对公钥内容进行签名。

后者情况下，用户一般会首先自行生成一个私钥和证书申请文件（Certificate Signing Request，即 csr 文件），该文件中包括了用户对应的公钥和一些基本信息，如通用名（common name，即 cn）、组织信息、地理位置等。CA 只需要对证书请求文件进行签名，生成证书文件，颁发给用户即可。整个过程中，用户可以保持私钥信息的私密性，不会被其他方获知（包括 CA 方）。

生成证书申请文件的过程并不复杂，用户可以很容易地使用开源软件 openssl 来生成 csr 文件和对应的私钥文件。

例如，安装 openssl 后可以执行如下命令来生成私钥和对应的证书请求文件：

$ openssl req -new -keyout private.key -out for_request.csr
Generating a 1024 bit RSA private key
...........................++++++
............................................++++++
writing new private key to 'private.key'
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:CN
State or Province Name (full name) [Some-State]:Beijing
Locality Name (eg, city) []:Beijing
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Blockchain
Organizational Unit Name (eg, section) []:Dev
Common Name (e.g. server FQDN or YOUR name) []:example.com
Email Address []:

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:

生成过程中需要输入地理位置、组织、通用名等信息。生成的私钥和 csr 文件默认以 PEM 格式存储，内容为 base64 编码。

如生成的 csr 文件内容可能为：

$ cat for_request.csr                                                                                                                                       
-----BEGIN CERTIFICATE REQUEST-----
MIIBrzCCARgCAQAwbzELMAkGA1UEBhMCQ04xEDAOBgNVBAgTB0JlaWppbmcxEDAO
BgNVBAcTB0JlaWppbmcxEzARBgNVBAoTCkJsb2NrY2hhaW4xDDAKBgNVBAsTA0Rl
djEZMBcGA1UEAxMQeWVhc3kuZ2l0aHViLmNvbTCBnzANBgkqhkiG9w0BAQEFAAOB
jQAwgYkCgYEA8fzVl7MJpFOuKRH+BWqJY0RPTQK4LB7fEgQFTIotO264ZlVJVbk8
Yfl42F7dh/8SgHqmGjPGZgDb3hhIJLoxSOI0vJweU9v6HiOVrFWE7BZEvhvEtP5k
lXXEzOewLvhLMNQpG0kBwdIh2EcwmlZKcTSITJmdulEvoZXr/DHXnyUCAwEAAaAA
MA0GCSqGSIb3DQEBBQUAA4GBAOtQDyJmfP64anQtRuEZPZji/7G2+y3LbqWLQIcj
IpZbexWJvORlyg+iEbIGno3Jcia7lKLih26lr04W/7DHn19J6Kb/CeXrjDHhKGLO
I7s4LuE+2YFSemzBVr4t/g24w9ZB4vKjN9X9i5hc6c6uQ45rNlQ8UK5nAByQ/TWD
OxyG
-----END CERTIFICATE REQUEST-----

openssl 工具提供了查看 PEM 格式文件明文的功能，如使用如下命令可以查看生成的 csr 文件的明文：

$ openssl req -in for_request.csr -noout -text
Certificate Request:
    Data:
        Version: 0 (0x0)
        Subject: C=CN, ST=Beijing, L=Beijing, O=Blockchain, OU=Dev, CN=yeasy.github.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:f1:fc:d5:97:b3:09:a4:53:ae:29:11:fe:05:6a:
                    89:63:44:4f:4d:02:b8:2c:1e:df:12:04:05:4c:8a:
                    2d:3b:6e:b8:66:55:49:55:b9:3c:61:f9:78:d8:5e:
                    dd:87:ff:12:80:7a:a6:1a:33:c6:66:00:db:de:18:
                    48:24:ba:31:48:e2:34:bc:9c:1e:53:db:fa:1e:23:
                    95:ac:55:84:ec:16:44:be:1b:c4:b4:fe:64:95:75:
                    c4:cc:e7:b0:2e:f8:4b:30:d4:29:1b:49:01:c1:d2:
                    21:d8:47:30:9a:56:4a:71:34:88:4c:99:9d:ba:51:
                    2f:a1:95:eb:fc:31:d7:9f:25
                Exponent: 65537 (0x10001)
        Attributes:
            a0:00
    Signature Algorithm: sha1WithRSAEncryption
        eb:50:0f:22:66:7c:fe:b8:6a:74:2d:46:e1:19:3d:98:e2:ff:
        b1:b6:fb:2d:cb:6e:a5:8b:40:87:23:22:96:5b:7b:15:89:bc:
        e4:65:ca:0f:a2:11:b2:06:9e:8d:c9:72:26:bb:94:a2:e2:87:
        6e:a5:af:4e:16:ff:b0:c7:9f:5f:49:e8:a6:ff:09:e5:eb:8c:
        31:e1:28:62:ce:23:bb:38:2e:e1:3e:d9:81:52:7a:6c:c1:56:
        be:2d:fe:0d:b8:c3:d6:41:e2:f2:a3:37:d5:fd:8b:98:5c:e9:
        ce:ae:43:8e:6b:36:54:3c:50:ae:67:00:1c:90:fd:35:83:3b:
        1c:86

需要注意，用户自行生成私钥情况下，私钥文件一旦丢失，CA 方由于不持有私钥信息，无法进行恢复，意味着通过该证书中公钥加密的内容将无法被解密。

证书的撤销

证书超出有效期后会作废，用户也可以主动向 CA 申请撤销某证书文件。

由于 CA 无法强制收回已经颁发出去的数字证书，因此为了实现证书的作废，往往还需要维护一个撤销证书列表（Certificate Revocation List，CRL），用于记录已经撤销的证书序号。

因此，通常情况下，当第三方对某个证书进行验证时，需要首先检查该证书是否在撤销列表中。如果存在，则该证书无法通过验证。如果不在，则继续进行后续的证书验证过程。

Merkle 树结构

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

其主要特点为：

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

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

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

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

快速比较大量数据

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

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

快速定位修改

例如图例中，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。

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

零知识证明

仍以上图为例，如何向他人证明拥有的某组数据（D0……D3）中包括给定某个内容 D0 而不暴露其它任何内容。

很简单，构造如图所示的一个默克尔树，公布 N1，N5，Root。D0 拥有者通过验证生成的 Root 是否跟提供的值一致，即可很容易检测 D0 存在。整个过程中验证者无法获知其它内容。

Bloom Filter 结构

布隆过滤器（Bloom Filter），1970 年由 Burton Howard Bloom 在论文《Space/Time Trade-offs in Hash Coding with Allowable Errors》提出。布隆过滤器是一种基于 Hash 的高效查找结构，能够快速（常数时间内）回答“某个元素是否在一个集合内”的问题。

该结构因为其高效性，被大量应用到网络和安全领域，例如信息检索（BigTable 和 HBase）、垃圾邮件规则、注册管理等。

基于 Hash 的快速查找

在布隆过滤器之前，先来看基于 Hash 的快速查找算法。在前面的讲解中，我们提到，Hash 可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很低。因此，这就构成了一个很好的“内容 -> 索引”的生成关系。

试想，如果给定一个内容和存储数组，通过构造 Hash 函数，让映射后的 Hash 值总不超过数组的大小，则可以实现快速的基于内容的查找。例如，内容 “hello world” 的 Hash 值如果是 “100”，则存放到数组的第 100 个单元上去。如果需要快速查找任意内容，如 “hello world” 字符串是否在存储系统中，只需要将其在常数时间内计算 Hash 值，并用 Hash 值查看系统中对应元素即可。该系统“完美地”实现了常数时间内的查找。

然而，令人遗憾的是，当映射后的值限制在一定范围（如总数组的大小）内时，会发现 Hash 冲突的概率会变高，而且范围越小，冲突概率越大。很多时候，存储系统的大小又不能无限扩展，这就造成算法效率的下降。为了提高空间利用率，后来人们基于 Hash 算法的思想设计出了布隆过滤器结构。

更高效的布隆过滤器

布隆过滤器采用了多个 Hash 函数来提高空间利用率。

对同一个给定输入来说，多个 Hash 函数计算出多个地址，分别在位串的这些地址上标记为 1。进行查找时，进行同样的计算过程，并查看对应元素，如果都为 1，则说明较大概率是存在该输入。

布隆过滤器相对单个 Hash 算法查找，大大提高了空间利用率，可以使用较少的空间来表示较大集合的存在关系。

实际上，无论是 Hash，还是布隆过滤器，基本思想是一致的，都是基于内容的编址。Hash 函数存在冲突，布隆过滤器也存在冲突。这就造成了两种方法都存在着误报（False Positive）的情况，但绝对不会漏报（False Negative）。

布隆过滤器在应用中误报率往往很低，例如，在使用 7 个不同 Hash 函数的情况下，记录 100 万个数据，采用 2 MB 大小的位串，整体的误判率将低于 1%。而传统的 Hash 查找算法的误报率将接近 10%。

同态加密

定义

同态加密（Homomorphic Encryption）是一种特殊的加密方法，允许对密文进行处理得到仍然是加密的结果。即对密文直接进行处理，跟对明文进行处理后再对处理结果加密，得到的结果相同。从抽象代数的角度讲，保持了同态性。

同态加密可以保证实现处理者无法访问到数据自身的信息。

如果定义一个运算符 ，对加密算法 E 和 解密算法 D，满足：

则意味着对于该运算满足同态性。

同态性来自代数领域，一般包括四种类型：加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态，则意味着是代数同态，即全同态（Full Homomorphic）。同时满足四种同态性，则被称为算数同态。

对于计算机操作来讲，实现了全同态意味着对于所有处理都可以实现同态性。只能实现部分特定操作的同态性，被称为特定同态（Somewhat Homomorphic）。

问题与挑战

同态加密的问题最早是由 Ron Rivest、Leonard Adleman 和 Michael L. Dertouzos 在 1978 年提出，同年提出了 RSA 加密算法。但第一个“全同态”的算法直到 2009 年才被克雷格·金特里（Craig Gentry）在论文《Fully Homomorphic Encryption Using Ideal Lattices》中提出并进行数学证明。

仅满足加法同态的算法包括 Paillier 和 Benaloh 算法；仅满足乘法同态的算法包括 RSA 和 ElGamal 算法。

同态加密在云计算和大数据的时代意义十分重大。目前，虽然云计算带来了包括低成本、高性能和便捷性等优势，但从安全角度讲，用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术，则大家就可以放心的使用各种云服务了，同时各种数据分析过程也不会泄露用户隐私。加密后的数据在第三方服务处理后得到加密后的结果，这个结果只有用户自身可以进行解密，整个过程第三方平台无法获知任何有效的数据信息。

另一方面，对于区块链技术，同态加密也是很好的互补。使用同态加密技术，运行在区块链上的智能合约可以处理密文，而无法获知真实数据，极大的提高了隐私安全性。

目前全同态的加密方案主要包括如下三种类型：

• 基于理想格（ideal lattice）的方案：Gentry 和 Halevi 在 2011 年提出的基于理想格的方案可以实现 72 bit 的安全强度，对应的公钥大小约为 2.3 GB，同时刷新密文的处理时间需要几十分钟。
• 基于整数上近似 GCD 问题的方案：Dijk 等人在 2010 年提出的方案（及后续方案）采用了更简化的概念模型，可以降低公钥大小至几十 MB 量级。
• 基于带扰动学习（Learning With Errors，LWE）问题的方案：Brakerski 和 Vaikuntanathan 等在 2011 年左右提出了相关方案；Lopez-Alt A 等在 2012 年设计出多密钥全同态加密方案，接近实时多方安全计算的需求。

目前，已知的同态加密技术往往需要较高的计算时间或存储成本，相比传统加密算法的性能和强度还有差距，但该领域关注度一直很高，笔者相信，在不远的将来会出现接近实用的方案。

函数加密

与同态加密相关的一个问题是函数加密。

同态加密保护的是数据本身，而函数加密顾名思义保护的是处理函数本身，即让第三方看不到处理过程的前提下，对数据进行处理。

该问题已被证明不存在对多个通用函数的任意多密钥的方案，目前仅能做到对某个特定函数的一个密钥的方案。

其它问题

密码学领域涉及到的问题还有许多，这里列出一些还在发展和探讨中的相关技术。

零知识证明

零知识证明（Zero Knowledge Proof），是这样的一个过程，证明者在不向验证者提供任何额外信息的前提下，使验证者相信某个论断是正确的。

例如，Alice 向 Bob 证明自己知道某个数字，在证明过程中 Bob 可以按照某个顺序提出问题（比如数字加上某些随机数后的变换）由 Alice 回答，并通过回答确信 Alice 较大概率确实知道某数字。证明过程中，Bob 除了知道 Alice 确实知道该数字外，自己无法获知或推理出任何额外信息（包括该数字本身），也无法用 Alice 的证明去向别人证明（Alice 如果提前猜测出 Bob 问题的顺序，存在作假的可能性）。

零知识证明的研究始于 1985 年 Shafi Goldwasser 等人的论文《The Knowledge Complexity of Interactive Proof-Systems》，目前一般认为至少要满足三个条件：

• 完整性（Completeness）：真实的证明可以让验证者成功验证；
• 可靠性（Soundness）：虚假的证明无法让验证者保证通过验证，但允许存在小概率例外；
• 零知识（Zero-Knowledge）：如果得到证明，无法从证明过程中获知除了所证明信息之外的任何信息。

可验证随机函数

 

量子密码学

量子密码学（Quantum Cryptography）随着量子计算和量子通信的研究而被受到越来越多的关注，被认为会对已有的密码学安全机制产生较大的影响。

量子计算的概念最早是物理学家费曼于 1981 年提出，基本原理是利用量子比特可以同时处于多个相干叠加态，理论上可以同时用少量量子比特来表达大量的信息，并同时进行处理，大大提高计算速度。量子计算目前在某些特定领域已经展现出超越经典计算的潜力。如基于量子计算的 Shor 算法（1994 年提出），理论上可以实现远超经典计算速度的大数因子分解。2016 年 3 月，人类第一次以可扩展的方式，用 Shor 算法完成对数字 15 的质因数分解。

这意味着目前广泛应用的非对称加密算法，包括基于大整数分解的 RSA、基于椭圆曲线随机数的 ECC 等将来都将很容易被破解。当然，现代密码学体系并不会因为量子计算的出现而崩溃。一方面，量子计算设备离实际可用的通用计算机还有较大距离，密码学家可以探索更安全的密码算法。另一方面，很多安全机制尚未发现能加速破解的量子算法那，包括数字签名（基于 Hash）、格（Lattice）密码、基于编码的密码等。

量子通信则可以提供对密钥进行安全协商的机制，有望实现无条件安全的“一次性密码”。量子通信基于量子纠缠效应，两个发生纠缠的量子可以进行远距离的实时状态同步。一旦信道被窃听，则通信双方会获知该情况，丢弃此次传输的泄露信息。该性质十分适合进行大量的密钥分发，如 1984 年提出的 BB84 协议，结合量子通道和公开信道，可以实现安全的密钥分发。

注：一次性密码：最早由香农提出，实现理论上绝对安全的对称加密。其特点为密钥真随机且只使用一次；密钥长度跟明文一致，加密过程为两者进行二进制异或操作。

社交工程学

密码学与安全问题，一直是学术界和工业界都十分关心的重要话题，相关的技术也一直在不断发展和完善。然而，即便存在理论上完美的技术，也不存在完美的系统。无数例子证实，看起来设计十分完善的系统最后被攻破，并非是因为设计上出现了深层次的漏洞。而问题往往出在事后看来十分浅显的一些方面。

例如，系统管理员将登陆密码贴到电脑前；财务人员在电话里泄露用户的个人敏感信息；公司职员随意运行来自不明邮件的附件；不明人员借推销或调查问卷的名义进入办公场所窃取信息……

著名计算机黑客和安全顾问 Kevin David Mitnick 曾在 15 岁时成功入侵北美空中防务指挥系统，在其著作《The Art of Deception》中大量揭示了通过社交工程学的手段轻易获取各种安全信息的案例。

小结

本文主要总结了密码学与安全领域中的一些核心问题和经典算法。

通过阅读本章内容，相信读者已经对现代密码学的发展状况和关键技术有了初步了解。掌握这些知识，对于帮助理解区块链系统如何实现隐私保护和安全防护都很有好处。

现代密码学安全技术在设计上大量应用了十分专业的现代数学知识，如果读者希望成为这方面的专家，则需要进一步学习并深入掌握近现代的数学科学，特别是数论、抽象代数等相关内容。可以说，密码学安全学科是没有捷径可走的。

另外，从应用的角度来看，一套完整的安全系统除了核心算法外，还包括协议、机制、系统、人员等多个方面。任何一个环节出现漏洞都将带来巨大的安全风险。因此，要实现高安全可靠的系统是十分困难的。

区块链技术中大量利用了现代密码学的已有成果，包括哈希、加解密、签名、Merkle 树数据结构等。另一方面，区块链系统和诸多新的场景也对密码学和安全技术提出了很多新的需求，反过来也将促进相关学科的进一步发展。

 

Source:  @yeasy -Github