区块链快速入门（六）——区块链密码学与安全相关技术

区块链快速入门（六）——区块链密码学与安全相关技术

一、区块链密码安全技术简介

区块链和分布式账本中大量使用了密码学和安全技术的最新成果，特别是身份认证和隐私保护相关技术。区块链使用了包括Hash 算法与摘要、加密算法、数字签名和证书、PKI体系、Merkle 树、布隆过滤器、同态加密等密码安全相关技术，用于设计实现区块链的机密性、完整性、可认证性和不可抵赖性。

二、Hash算法与数字摘要

1、Hash算法简介

Hash(哈希或散列)算法，常被称为指纹(fingerprint)或摘要(digest)算法，可以将任意长度的二进制明文串映射为较短的(通常是固定长度的)二进制串(Hash 值)，并且不同的明文很难映射为相同的Hash值。

优秀Hash算法的要求：

A、正向快速

给定原文和Hash算法，在有限时间和有限资源内能计算得到Hash值。

B、逆向困难

给定(若干)Hash 值，在有限时间内无法(基本不可能)逆推出原文。

C、输入敏感

原始输入信息发生任何改变，新产生的Hash值都应该发生很大变化。

D、抗碰撞

很难找到两段内容不同的明文，使得其Hash值一致(即发生碰撞)。

2、常见Hash算法

目前常见的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已于2005年被成功碰撞，已经无法满足商用需求。为了提高安全性，NIST后来制定出更安全的SHA-224、SHA-256、SHA-384和 SHA-512算法(统称为SHA-2 算法)。新一代的SHA-3相关算法目前正在研究中。

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

3、Hash算法的性能

大多数Hash算法都是计算敏感型算法，在强大的计算芯片上完成的更快。因此要提升Hash计算的性能可以考虑硬件加速。例如采用普通FPGA来计算SHA-256 值，可以轻易达到数Gbps 的吞吐量，使用专用芯片甚至会更高。

少数Hash算法不是计算敏感型的，如scrypt算法，其计算过程需要大量的内存资源，因此很难通过选用高性能芯片来加速Hash计算，可以有效防范采用专用芯片进行算力***。

4、数字摘要

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

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

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

5、Hash***与防护

Hash算法并不是一种加密算法，不能用于对信息的保护。但Hash算法可被应用到对登录口令的保存上。例如网站登录时需要验证用户名和密码，如果网站后台直接保存用户的口令原文，一旦发生数据库泄露后果不堪设想。

利用Hash的防碰撞特性，后台数据库可以仅保存用户口令的Hash值，每次通过Hash值比对，即可判断输入口令是否正确。即便数据库泄露，***者也无法轻易从Hash值还原回口令。

但如果用户设置口令的安全强度不够，采用了一些常见的字符串，如password、123456等。有人专门搜集常见口令，计算对应的Hash值，制作成字典，可以通过查看字典的Hash值可以快速反查到原始口令，如字典***和彩虹表***(只保存一条Hash链的首尾值，相对字典***可以节省存储空间)等。

为了防范字典***、彩虹表***等***方法，可以采用加盐(Salt)的方法。保存的不是原文的直接 Hash值，而是原文再加上一段随机字符串(即“盐”)后的Hash值。Hash结果和“盐”分别存放在不同的地方，只要不是两者同时泄，***者很难进行破解。

三、加解密算法

1、加解密系统简介

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)等模式。

3、非对称加密算法

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

非对称加密算法的加密密钥和解密密钥是不同的，分别被称为公钥(Public Key)和私钥(Private Key)。私钥一般通过随机数算法生成，公钥可以根据私钥生成。公钥一般是公开的，他人可获取；私钥则是个人持有并且要严密保护，不能被他人获取。

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

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

非对称加密算法代表算法包括:RSA、ElGamal、椭圆曲线(Elliptic Curve Crytosystems,ECC)、SM2等系列算法。

RSA:经典的公钥算法，1978 年由Ron Rivest、Adi Shamir、Leonard Adleman 共同提出，三人于2002年因此获得图灵奖。RSA算法利用了对大数进行质因子分解困难的特性，但目前还没有数学证明两者难度等价，或许存在未知算法可以绕过大数分解而进行解密。

ElGamal:由 Taher ElGamal 设计，利用了模运算下求离散对数困难的特性，比RSA产生密钥更快，被应用在PGP等安全 工具 中。

椭圆曲线算法(Elliptic Curve Cryptography，ECC)：现代备受关注的算法系列，基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。最早在1985年由Neal Koblitz和Victor Miller分别独立提出。ECC系列算法一般被认为具备较高的安全性，但加解密过程比较费时。

SM2(ShangMi 2):中国国家商用密码系列算法标准，由中国密码管理局于2010年12月17日发布，同样基于椭圆曲线算法，一般认为其安全强度优于RSA系列算法。

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

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

4、选择明文***

非对称加密中公钥是公开的，因此任何人都可以利用公钥加密给定明文，获取对应的密文，达到破解的目的，带来选择明文***的风险。

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

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

5、混合加密机制

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

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

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

与以明文方式传输数据的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，成为目前广泛采用的方案。2008年，TLS1.2版本发布，修正了之前版本的不少漏洞，极大增强了安全性，推荐商用场景使用。除了Web服务外，TLS 协议也被广泛应用到FTP、Email、实时消息、音视频通话等场

景中。

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

1、消息认证码

消息认证码(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。

消息认证码的主要问题是需要提前共享密钥，并且当密钥可能被多方同时拥有(甚至泄露)的场景下，无法追踪消息的真实来源。

2、数字签名

数字签名既可以证实某数字内容的完整性，又可以确认其来源(即不可抵赖，Non-Repudiation)。

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

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

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

3、盲签名

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

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

4、多重签名

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

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

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

5、群签名

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

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

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

6、环签名

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

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

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

五、数字证书

1、数字证书简介

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

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

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

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

2、X.509证书规范

通常，一个数字证书内容可能包括证书域(证书的版本、序列号、签名算法类型、签发者信息、有效期、被签发主体、签发的公开密钥)、CA对证书的签名算法和签名值等。目前使用最广泛的标准为ITU和ISO联合制定的X.509的v3版本规范(RFC5280)，其中定义了如下证书信息域:

版本号(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)：证书的有效期限，包括起止时间(如 Not Before 2018-08-08-00-00UTC,Not After 2028-08-08-00-00UTC);

被签发主体(Subject)：证书拥有者的标识信息(Distinguished Name)，如“C=CN, ST=Beijing, L=Beijing, CN=personA.org.example.com”;

主体的公钥信息(Subject Public Key Info)：所保护的公钥相关的信息;

A、公钥算法(Public Key Algorithm)：公钥采用的算法;

B、主体公钥(Subject Public Key)：公钥的内容;

颁发者唯一号(Issuer Unique Identifier，可选)：代表颁发者的唯一信息，仅2、3版本支持，可选;

主体唯一号(Subject Unique Identifier,可选):代表拥有证书实体的唯一信息,仅 2、3版本支持，可选。

扩展(Extensions,可选):可选的一些扩展。可能包括:

Subject Key Identifier：实体的密钥标识符，区分实体的多对密钥;

Basic Constraints：一般指明该证书是否属于某个CA;

Authority Key Identifier：颁发这个证书的颁发者的公钥标识符;

Authority Information Access：颁发相关的服务地址,如颁发者证书获取地址和吊销证书列表信息查询地址;

CRL Distribution Points：证书注销列表的发布地址;

Key Usage: 表明证书的用途或功能信息，如Digital Signature、Key CertSign;

Subject Alternative Name：证书身份实体的别名，如该证书可以同样表.org.example.com,org.example.com,.example.com,example.com身份等。

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

3、证书格式

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

3、证书信任链

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

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

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

因此，证书作为公钥信任的基础，对其生命周期进行安全管理十分关键。

六、PKI体系

1、PKI简介

按照X.509规范，公钥可以通过证书机制来进行保护，但证书的生成、分发、撤销等步骤并未涉及。要实现安全地管理、分发证书需要遵循PKI(Public Key Infrastructure)体系。PKI体系提供了一套完整的证书管理的框架，包括生成、颁发、撤销过程等，解决了证书生命周期相关的认证和管理问题。

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

通常，PKI至少包括如下核心组件:

CA(Certification Authority)：负责证书的颁发和吊销(Revoke)，接收来自 RA 的请求，是最核心的部分，主要完成对证书信息的维护；

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

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

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

2、证书签发

3、证书吊销

证书超出有效期后会作废，用户也可以主动向CA申请吊销某证书文件。由于CA无法强制收回已经颁发出去的数字证书，因此为了实现证书的作废，往往还需要维护一个吊销证书列表(Certificate Revocation List，CRL)，用于记录已经吊销的证书序号。因此，通常情况下，当对某个证书进行验证时，需要首先检查该证书是否已经记录在列表中。如果存在，则该证书无法通过验证。如果不在，则继续进行后续的证书验证过程。

为了方便同步吊销列表信息，IETF提出了在线证书状态协议(Online Certificate Status Protocol，OCSP)，支持该协议的服务可以实时在线查询吊销的证书列表信息。

七、Merkel树

1、Merkel树简介

2、Merkel树的应用场景

（1）快速比较大量数据

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

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

（2）快速定位修改

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

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

（3）零知识证明

如何向他人证明拥有的某组数据(D0......D3)中包括给定某个内容D0而不

暴露其它任何内容。

对于本文所示默克尔树，公布N1，N5，Root。验证者计算Root值，验证是否跟提供值一致，即可很容易检测D0存在。整个过程中验证者无法获知其它任何信息。

八、布隆过滤器

1、布隆过滤器简介

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

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

2、基于Hash的快速查找

Hash可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很低，构成了一个很好的“内容->索引”的生成关系。

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

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

3、布隆过滤器实现原理

九、同态加密

1、同态加密简介

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

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

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

2、同态加密的问题与挑战

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

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

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

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

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

A、基于理想格(ideal lattice)的方案

Gentry和Halevi在2011年提出的基于理想格的方案可以实现 72 bit 的安全强度，对应的公钥大小约为2.3GB，同时刷新密文的处理时间需要几十分钟。

B、基于整数上近似GCD问题的方案

Dijk等人在2010年提出的方案(及后续方案)采用了更简化的概念模型，可以降低公钥大小至几十MB量级。

C、基于带扰动学习(Learning With Errors，LWE)问题的方案

Brakerski和Vaikuntanathan等在2011年左右提出了相关方案；Lopez-Alt A等在2012年设计出多密钥全同态加密方案，接近实时多方安全计算的需求。

目前，已知的同态加密技术往往需要较高的计算时间或存储成本，相比传统加密算法的性能和强度还有差距，但同态加密技术领域关注度一直很高。

3、函数加密

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

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

十、其它安全技术

1、零知识证明

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

证明过程包括交互式和费交互式两种。

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

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

A、完整性(Completeness)：真实的证明可以让验证者成功验证。

B、可靠性(Soundness)：虚假的证明无法保证通过验证，但理论上存在小概率例外。

C、零知识(Zero-Knowledge)：如果得到证明，无法从证明过程中获知除了所证明信息之外的任何信息。

2、可验证随机函数

可验证随机函数(Verifiable Random Function，VRF)最早由Silvio Micali(MIT)、Michael Rabiny(哈佛大学)、Salil Vadha(MIT)于1999年在论文《Verifiable Random Functions》中提出。

VRF讨论的是一类特殊的伪随机函数，其结果可以在某些场景下进行验证。

例如，Alice拥有公钥Pk和对应私钥 Sk。Alice宣称某可验证随机函数 F和一个输入x，并计算y = F(Sk, x)。Bob可以使用Alice公钥Pk，对同样的x和F进行验证，证明其结果确实为y。因为F的随机性，任何人都无法预测y的值。

VRF提供了一种让大家都认可并且可以验证的随机序列，可以用于分布式系统中进行投票的场景。目前已经有利用VRF的共识算法VBFT。

3、量子密码学

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

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

2016年3月，人类第一次以可扩展的方式，用 Shor算法完成对数字15的质因数分解。目前广泛应用的非对称加密算法，包括基于大整数分解的RSA、基于椭圆曲线随机数的ECC等将来都将很容易被破解。当然，现代密码学体系并不会因为量子计算的出现而崩溃。一方面，量子计算设备离实际可用的通用计算机还有较大距离，密码学家可以探索更安全的密码算法。另一方面，很多安全机制尚未发现能加速破解的量子算法，包括数字签名(基于Hash)、格(Lattice)密码、基于编码的密码等。

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

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

4、社交工程学

密码学与安全问题，一直是学术界和工业界都十分关心的重要话题，相关的技术也一直在不断发展和完善。然而，即便存在理论上完美的技术，也不存在完美的系统。看起来设计十分完善的系统最后被攻破，并非是因为设计上出现了深层次的漏洞。而问题往往出在事后看来十分浅显的一些方面。例如，系统管理员将登陆密码贴到电脑前；财务人员在电话里泄露用户的个人敏感信息；公司职员随意运行来自不明邮件的附件；不明人员借推销或调查问卷的名义进入办公场所窃取信息等