区块链-密码学与安全技术-安全

捐助

区块链-密码学与安全技术

2582 次浏览

2018-8-29

编辑推荐:

本文来自于CSDN，文章介绍密码学领域中跟区块链相关的一些基础知识，包括Hash算法与数字摘要、加密算法、数字签名、数字证书、PKI体系、Merkle树、布隆过滤器、同态加密等。

密码学与安全技术

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

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

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

一、Hash算法与数字摘要

1.1、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

db8305d71a9f2f90a3e118a9b49a4c381d2b80c
f7bcef81930f30ab1832a3c90

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

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

一个优秀的Hash算法将能实现如下功能：

正向快速：给定明文和Hash算法，在有限时间和有限资源内能计算得到Hash值；

逆向困难：给定（若干）Hash值，在有限时间内很难（基本不可能）逆推出明文；

输入敏感：原始输入信息发生任何改变，新产生的Hash值都应该出现很大不同；

冲突避免：很难找到两段内容不同的明文，使得它们的Hash值一致（发生碰撞）。

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

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

1.2、常见算法

目前常见的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算法一起都被认为安全性已不足应用于商业场景。

1.3、性能

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

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

1.4、数字摘要

顾名思义，数字摘要是对数字内容进行Hash运算，获取唯一的摘要值来指代原始完整的数字内容。数字摘要是Hash算法最重要的一个用途。利用Hash函数的抗碰撞性特点，数字摘要可以解决确保内容未被篡改过的问题。

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

1.5、Hash攻击与防护

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

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

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

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

二、加密算法

加解密算法是密码学的核心技术，从设计理念上可以分为两大基本类型，如表5-1所示。

表5-1　加解密算法的类型

2.1、加解密系统基本组成

现代加解密系统的典型组件一般包括：加解密算法、加密密钥、解密密钥。其中，加解密算法自身是固定不变的，并且一般是公开可见的；密钥则是最关键的信息，需要安全地保存起来，甚至通过特殊硬件进行保护。一般来说，对同一种算法，密钥需要按照特定算法每次加密前随机生成，长度越长，则加密强度越大。加解密的基本过程如图5-1所示。

图5-1　加解密的基本过程

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

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

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

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

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

2.2、对称加密算法

对称加密算法，顾名思义，加密和解密过程的密钥是相同的。该类算法优点是加解密效率（速度快，空间占用小）和加密强度都很高。缺点是参与方都需要提前持有密钥，一旦有人泄露则安全性被破坏；另外如何在不安全通道中提前分发密钥也是个问题，需要借助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）等模式。

2.3、非对称加密算法

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

顾名思义，非对称加密算法中，加密密钥和解密密钥是不同的，分别称为公钥（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类算法可能在不远的将来被破解，一般推荐可采用安全强度更高的椭圆曲线系列算法。

2.4、选择明文攻击

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

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

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

2.5、混合加密机制

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

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

典型的应用案例是现在大家常用的HTTPS协议。HTTPS协议正在替换掉传统的不安全的HTTP协议，成为最普遍的Web通信协议。

HTTPS在传统的HTTP层和TCP层之间通过引入Transport Layer Security/Secure Socket Layer（TLS/SSL）加密层来实现可靠的传输。

SSL协议最早是Netscape于1994年设计出来实现早期HTTPS的方案，SSL 3.0及之前版本存在漏洞，被认为不够安全。TLS协议是IETF基于SSL协议提出的安全标准，目前最新的版本为1.2（2008年发布）。推荐使用的版本号至少为TLS 1.0，对应到SSL 3.1版本。除了Web服务外，TLS协议也广泛应用于Email、实时消息、音视频通话等领域。

采用HTTPS建立安全连接（TLS握手协商过程）的基本步骤如下（可参见图5-2）：

图5-2　TLS握手协商过程

客户端浏览器发送信息到服务器，包括随机数R1、支持的加密算法类型、协议版本、压缩算法等。注意该过程为明文。

服务端返回信息，包括随机数R2、选定加密算法类型、协议版本以及服务器证书。注意该过程为明文。

浏览器检查带有该网站公钥的证书。该证书需要由第三方CA来签发，浏览器和操作系统会预置权威CA的根证书。如果证书被篡改作假（中间人攻击），很容易通过CA的证书验证出来。

如果证书没问题，则客户端用服务端证书中的公钥加密随机数R3（又叫Pre-MasterSecret），发送给服务器。此时，只有客户端和服务器都拥有R1、R2和R3信息，基于随机数R1、R2和R3，双方通过伪随机数函数来生成共同的对称会话密钥MasterSecret。

后续客户端和服务端的通信都通过对称加密算法（如AES）进行保护。

可以看出，该过程的主要功能是在防止中间人窃听和篡改的前提下完成会话密钥的协商。为了保障前向安全性（perfect forward secrecy），TLS对每个会话连接都可以生成不同的密钥，避免某次会话密钥泄露之后影响了其他会话连接的安全性。需要注意，TLS协商过程支持加密算法方案较多，要合理地选择安全强度高的算法，如DHE-RSA、ECDHE-RSA和ECDHE-ECDSA。

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

2.6、离散对数与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。

三、消息认证码与数字签名

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

3.1、消息认证码

消息认证码全称是“基于Hash的消息认证码”（Hash-based Message Authentication Code，HMAC）。消息验证码基于对称加密，可以用于对消息完整性（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。注意这里并没有考虑中间人攻击的情况，假定信道是安全的。

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

3.2、数字签名

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

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

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

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

3.2.1、盲签名

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

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

3.2.2、多重签名

多重签名（multiple signature）即n个签名者中，收集到至少m个（n>=m>=1）的签名，即认为合法。其中，n是提供的公钥个数，m是需要匹配公钥的最少的签名个数。

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

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

3.2.3、群签名

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

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

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

3.2.4、环签名

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

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

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

3.3、安全性

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

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

四、数字证书

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

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

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

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

4.1、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：证书的用途或功能信息。

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

4.2、证书格式

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

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

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

可以通过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格式互相转换。

4.3、证书信任链

证书中记录了大量信息，其中最重要的包括“签发的公开密钥”和“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相关规范等。

5.1、PKI基本组件

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

CA（Certification Authority）：负责证书的颁发和作废，接收来自RA的请求，是最核心的部分；

RA（Registration Authority）：对用户身份进行验证，校验数据合法性，负责登记，审核过了就发给CA；

证书数据库：存放证书，多采用X.500系列标准格式。可以配合LDAP目录服务管理用户信息。

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

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

5.2、证书的签发

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
1
-----BEGIN CERTIFICATE REQUEST-----
MIIBrzCCARgCAQAwbzELMAkGA1UEBhMCQ04xEDAOBgNVBAgTB0JlaWpp
bmcxEDAO
BgNVBAcTB0JlaWppbmcxEzARBgNVBAoTCkJsb2NrY2hhaW4xDDAKBgNV
BAsTA0Rl
djEZMBcGA1UEAxMQeWVhc3kuZ2l0aHViLmNvbTCBnzANBgkqhkiG9w0B
AQEFAAOB
jQAwgYkCgYEA8fzVl7MJpFOuKRH+BWqJY0RPTQK4LB7fEgQFTIotO264
ZlVJVbk8
Yfl42F7dh/8SgHqmGjPGZgDb3hhIJLoxSOI0vJweU9v6HiOVrFWE7BZE
vhvEtP5k
lXXEzOewLvhLMNQpG0kBwdIh2EcwmlZKcTSITJmdulEvoZXr/DHXnyUC
AwEAAaAA
MA0GCSqGSIb3DQEBBQUAA4GBAOtQDyJmfP64anQtRuEZPZji/7G2+y3L
bqWLQIcj
IpZbexWJvORlyg+iEbIGno3Jcia7lKLih26lr04W/7DHn19J6Kb/CeXr
jDHhKGLO
I7s4LuE+2YFSemzBVr4t/g24w9ZB4vKjN9X9i5hc6c6uQ45rNlQ8UK5n
AByQ/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方由于不持有私钥信息，无法进行恢复，意味着通过该证书中公钥加密的内容将无法被解密。

5.3、证书的撤销

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

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

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

六、Merkle树结构

Merkle（默克尔）树，又叫哈希树，是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。在区块链系统出现之前，广泛用于文件系统和P2P系统中，如图5-3所示。

图5-3　Merkle树示例

其主要特点为：

最下面的叶节点包含存储数据或其哈希值；

非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。

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

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

目前，默克尔树的典型应用场景有很多，下面分别介绍。

6.1、快速比较大量数据

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

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

6.2、快速定位修改

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

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

6.3、零知识证明

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

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

七、布隆过滤器

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

布隆过滤器因为其高效性大量应用于网络和安全领域，例如信息检索（BigTable和HBase）、垃圾邮件规则、注册管理等。

7.1、基于Hash的快速查找

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

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

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

7.2、更高效的布隆过滤器

布隆过滤器采用了多个Hash函数来提高空间利用率。对同一个给定输入来说，多个Hash函数计算出多个地址，分别在位串的这些地址上标记为1。进行查找时，进行同样的计算过程，并查看对应元素，如果都为1，则说明较大概率是存在该输入。如图5-4所示。

图5-4　布隆过滤器

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

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

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

八、同态加密

8.1、定义

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

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

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

E（XΔY）=E（X）ΔE（Y）

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

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

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

8.2、问题与挑战

同态加密的问题最早是由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年设计出多密钥全同态加密方案，接近实时多方安全计算的需求。

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

8.3、函数加密

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

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

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

九、其他问题

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

9.1、零知识证明

零知识证明（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）：如果得到证明，无法从证明过程中获知除了所证明信息之外的任何信息。

9.2、量子密码学

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

量子计算的概念最早是物理学家费曼于1981年提出，基本原理是利用量子比特可以同时处于多个相干叠加态，理论上可以同时用少量量子比特来表达大量的信息，并同时进行处理，大大提高计算速度。如1994年提出的基于量子计算的Shor算法，理论上可以实现远超经典计算速度的大数因子分解。这意味着大量加密算法包括RSA、DES、椭圆曲线算法等都将很容易被破解。但量子计算目前离实际可用的通用计算机还有一定距离。

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

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

9.3、社交工程学

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

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

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

十、小结

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

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

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

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

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

2582 次浏览