第2章 区块链中的密码学

比特币是一种密码货币，区块链技术的基础是密码学。本章主要介绍在区块链技术中用到的密码算法、数字签名、Hash函数等。

2.1 密码学概述

密码学（cryptology）起源于保密通信技术，是结合数学、计算机、信息论等学科的一门综合性、交叉性学科。密码学又分为密码编码学（cryptography）和密码分析学（cryptanalysis）两部分。密码编码学主要研究如何设计编码，使得信息编码后除指定接收者外的其他人都不能读懂。密码分析学主要研究如何攻击密码系统，实现加密消息的破译或消息的伪造。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。

现代密码学主要内容及联系如图2-1所示，这些密码技术为信息安全中的机密性、完整性、认证性和不可否认性提供基本的保障，也为PKI技术、认证技术等实际应用提供基本的工具，本章主要介绍在区块链技术中所用到的有关密码学知识。

随着计算机科学与技术的蓬勃发展，出现了快速电子计算机和现代数学方法，它们一方面为加密技术提供了新的概念和工具，另一方面也给密码破译者提供了有力的武器，二者相互促进，使密码技术飞速发展。新兴信息技术为密码设计者提供了前所未有的条件，从而可以设计出更加复杂和更为高效的密码体制。

近年来，由于其他相关学科的进步和发展，也出现了一些新兴、交叉性的密码技术。例如，随着量子计算研究热潮的兴起，世界各国对量子密码的研究也广泛地开展起来。量子密码具有可证明的安全性，同时还能对窃听行为方便地进行检测。这些特性使量子密码具有一些其他密码所没有的优势，因而量子密码引起国际密码学界的高度重视，我国研究专家已在此领域多次取得世界性突破成果。

2.1.1 密码体制的基本组成及分类

密码学的基本思想就是对信息进行伪装。伪装前的信息称为明文，通常用p（plaintext）或者m（message）表示；伪装后的消息称为密文，通常用c（ciphertext）表示。图2-2是基于密码技术的保密通信基本模型。这种对信息的伪装可以表示成一种可逆的数学变换，从明文到密文的变换称为加密（encryption），从密文到明文的变换称为解密（decryption）。加密和解密都是在密钥（key）的控制下进行的。

一个密码体制（cryptosystem）由五个部分组成：

（1）明文空间M，它是全体明文m的集合。

（2）密文空间C，它是全体密文c的集合。

（3）密钥空间K，它是全体密钥k的集合。其中，每一个密钥k均由加密密钥ke和解密密钥kd组成，即k=(ke, kd)。

（4）加密算法E，是在密钥控制下将明文消息从M对应到C的一种变换，即c=E(ke, m)。

（5）解密算法D，是在密钥控制下将密文消息从C对应到M的一种变换，即m=D(kd, c)。

密码体制是实现加密和解密功能的密码方案，密钥空间中不同密钥的个数称为密码体制的密钥量，它是衡量密码体制安全性的一个重要指标。同时，根据加、解密密钥的使用策略不同，又可将密码体制分为对称密码体制和非对称密码体制。

1．对称密码体制（symmetric cryptosystem）

如果一个密码体制中的加密密钥ke和解密密钥kd相同，或者由其中一个密钥很容易推算出另一个密钥，则称该密码体制为对称密码体制或单钥密码体制（one-key cryptosystem）。因为在使用过程中，密钥必须严格保密，所以也被称为秘密密钥密码体制（secret key cryptosystem）。典型的对称密码体制有DES、AES等。

对称密码体制因为其具有安全、高效、经济等特点，发展非常迅速，并被广泛应用。依据处理数据的方式，对称密码体制通常又分为分组密码（block cipher）和序列密码（stream cipher）。

分组密码是将定长的明文块（如64位一组）转换成等长的密文，这一过程在密钥的控制下完成。解密时使用逆向变换和同一密钥来完成。序列密码是指加、解密时对明文中比特逐个进行处理，也被称为流密码。

对称密码体制主要用来对信息进行保密，实现信息的机密性。它的优点是加密和解密处理效率高，密钥长度相对较短，一般情况下加密后密文和明文长度相同。但是，对称密码体制也存在一些固有的缺陷，如需要安全通道分发密钥，保密通信的用户数量多时，密钥量大，难于管理，难以解决不可否认性等问题。

2．非对称密码体制（asymmetric cryptosystem）

1976年，Diffie和Hellmen发表了具有里程碑意义的《密码学的新方向》（New Dire-ction in Cryptography），提出了非对称密码的思想，即加密过程和解密过程使用两个不同的密钥来完成。进一步说，如果在计算上由加密密钥ke不能推出解密密钥kd，那么将ke公开不会损害kd的安全，于是可以将ke公开，因此这种密码体制也被称为公钥密码（public key cryptosystem），亦称双钥密码体制（two key cryptosystem）。典型的非对称密码体制有RSA、ElGamal等。

非对称密码体制的提出解决了对称密码体制的固有缺陷，它不仅可以保障信息的机密性，还可以对信息进行数字签名，具有认证性和抗否认性的功能。不过，非对称密码体制与对称密码体制相比，其设计所依赖的数学计算较复杂，因而加、解密效率较低。在达到同样安全强度时，非对称密码通常所需的密钥位数较多，并且加密产生的密文长度通常会大于明文长度。因此，在保密通信过程中通常是用对称密码来进行大量数据的加密，而用非对称密码来传输少量数据，如对称密码所使用的密钥信息。

2.1.2 密码体制的设计原则

密码学的基本目的就是保障不安全信道上的通信安全。密码学领域存在一个很重要的事实：“许多聪明人都不能解决的问题，它可能不会很快得到解决。”这暗示很多加密算法的安全性并没有在理论上得到严格的证明，只是这种算法思想出来以后，经过许多人许多年的攻击并没有发现其弱点，没有找到攻击它的有效方法，从而认为它是安全的。一般地，衡量密码体制安全性的方法有三种：

第一种方法是计算安全性（computational security），又称实际保密性（practical secr-ecy）。如果一种密码系统最有效的攻击算法至少是指数时间的，则称这个密码体制是计算安全的。在实际中，人们说一个密码系统是计算上安全的，意思是利用已有的最好方法破译该系统所需要的努力超过了攻击者的破译能力（如时间、空间和资金等资源）。

第二种方法是可证明安全性（provable security）。如果密码体制的安全性可以归结为某个数学困难问题，则称其是可证明安全的。例如，RSA密码可以归结为大整数因数分解问题，ElGamal密码可以归结为有限域上离散对数求解问题。香农（Shannon）曾指出，设计一个安全的密码本质上是要寻找一个难解的问题。

第三种方法是无条件安全性（unconditional security）或者完善保密性（perfect secrecy）。假设存在一个具有无限计算能力的攻击者，如果密码体制无法被这样的攻击者攻破，则称其为无条件安全。香农证明了一次一密密码具有无条件安全性，即从密文中得不到关于明文或者密钥的任何信息。

一个实用的密码体制的设计应该遵守以下原则：

（1）密码算法安全强度高。就是说攻击者根据截获的密文或某些已知明文密文对，要确定密钥或者任意明文在计算上不可行。

（2）密码体制的安全性不应依赖加密算法的保密性，而应取决于可随时改变的密钥。即使密码分析者知道所用的加密体制，也无助于用来推导出明文或密钥。

（3）密钥空间应足够大。使试图通过穷举密钥空间进行搜索的方式在计算上不可行。

（4）既易于实现又便于使用。主要是指加密函数和解密函数都可以高效地计算。

其中第2条是著名的柯克霍夫（Kerckhoffs）原则，是由荷兰密码学家奥古斯特·柯克霍夫于1883年在其名著《军事密码学》中提出的。柯克霍夫原则指出密码算法应该是公开的，唯一需要保护的是密钥。密码算法的公开不仅有利于增加密码算法的安全性，还有利于密码技术的推广应用，有利于增加用户使用的信心，也有利于密码技术的发展。例如国际上，3DES、SHA-1、RSA等密码算法及相关标准在各个领域中被长期沿用。

2.1.3 密码体制的常见攻击形式

密码分析学是伴随着密码编码学的产生而产生的，它是研究如何分析或破解各种密码体制的一门科学。密码分析也被称为密码攻击，是指非授权者在不知道解密密钥的条件下对密文进行分析，试图得到明文或密钥的过程。

密码分析可以发现密码体制的弱点，密码分析者攻击密码体制的方法主要有以下三种。

（1）穷举攻击：密码分析者通过试遍所有的密钥来进行破译。穷举攻击又称为蛮力攻击，是指攻击者依次尝试所有可能的密钥对所截获的密文进行解密，直至得到正确的明文。1997年6月18日，美国科罗拉多州Rocket Verser工作小组宣布，通过网络利用数万台计算机历时4个多月以穷举攻击方式攻破了DES。

（2）统计分析攻击：密码分析者通过分析密文和明文的统计规律来破译密码。统计分析攻击在历史上为破译密码做出过极大的贡献。许多古典密码都可以通过分析密文字母和字母组的频率及其统计参数而破译。例如，在英语里，字母e是英文文本中最常用的字母，字母组合th是英文文本中最常用的字母组合。在简单的替换密码中，每个字母只是简单地被替换成另一个字母，那么在密文中出现频率最高的字母就最有可能是e，出现频率最髙的字母组合就最有可能是th。抵抗统计分析攻击的方式是在密文中消除明文的统计特性。

（3）数学分析攻击：密码分析者针对加密算法的数学特征和密码学特征，通过数学求解的方法来设法找到相应的解密变换。为对抗这种攻击，应该选用具有坚实的数学基础且足够复杂的加密算法。

密码攻击和解密的相似之处在于都是设法将密文还原成明文的过程，但攻击者和消息接收者所具备的条件是不同的。密码分析者的任务是恢复尽可能多的明文，或者最好能推算出解密密钥，这样就很容易解出被加密的信息。根据密码分析者可获取的信息量不同，常见的密码分析攻击包括以下4种类型。

（1）唯密文攻击（ciphertext only attack）。

密码分析者除了拥有截获的密文外（密码算法是公开的，以下同），没有其他可以利用的信息。这种攻击的方法至少可采用穷举搜索法，只要有足够多的计算资源和存储资源，理论上穷举搜索是可以成功的，但实际上，任何一种能保障安全要求的算法复杂度都是实际攻击者无法承受的。

（2）已知明文攻击（known plaintext attack）。

密码分析者不仅掌握了相当数量的密文，还有一些已知的明—密文对可供利用。密码分析者的任务就是用密文信息推出解密密钥或导出一个替代算法，此算法可以对所获得的密文恢复出相应的明文。在现实中，密码分析者可能通过各种手段得到更多的信息，而且明文消息往往采用某种特定的格式，如电子现金传送消息总有一个标准的报头或标题等。

（3）选择明文攻击（chosen plaintext attack）。

密码分析者不仅能够获得一定数量的明—密文对，还可以选择任何明文并在使用同一未知密钥的情况下得到相应的密文。如果攻击者在加密系统中能选择特定的明文消息，则通过该明文消息对应的密文就有可能确定密钥的结构或获取更多关于密钥的信息。这种情况往往是密码分析者通过某种手段暂时控制加密机。根据非对称密码体制的特点，非对称密码算法必须经受住这种攻击。

（4）选择密文攻击（chosen ciphertext attack）。

密码分析者能选择不同的密文，并且还可得到对应的明文。如果攻击者能从密文中选择特定的密文消息，则通过该密文消息对应的明文有可能推导出密钥的结构或产生更多关于密钥的信息。这种情况往往是密码分析者通过某种手段暂时控制解密机。

上述攻击类型中，唯密文攻击的强度最弱，其他情况下的攻击强度依次增加。当然密码体制的攻击不限于以上类型，还包括一些非技术手段，如通过威胁、勒索、贿赂等方式获取密钥或相关信息，在某些情况下这些手段是非常有效的攻击，但不是本章所关注的内容。

2.1.4 密码学在区块链中的应用

区块链是比特币的基础技术，而密码学是区块链技术的基础。在署名中本聪的论文《比特币：一种点对点的电子现金系统》中提出了一套“基于公钥加解密验证而不是基于信用，使得任何达成一致的双方能够端对端进行支付，而不需要一个中间的金融机构”的电子支付系统，同时提出了“一种基于P2P网络解决双重支付问题的方法。这个网络给支付交易打上时间戳……除非可以提供之前所有的工作量证明，否则不能被篡改。只要占多数的CPU不被同时控制以联合起来对网络进行攻击，它们就可以比攻击者生成更长的链条”。从而此系统就是安全的。区块链中有关密码学知识的应用如图2-3所示。

从图2-3可以看出，在比特币的区块链中，用到了公钥密码体制、数字签名、Hash函数等密码学知识。图中，U0、U1、U2、U3等分别表示不同的用户。每一位电子货币的所有者将电子货币转移给下一位所有者的过程是：对前一个交易和下一位所有者的公钥签署一个数字签名，并将这个签名附加在交易的末尾。收款人通过验证签名，就可以验证电子货币的所有者链条。

在后面的章节中，将重点介绍在区块链中用到的密码学基础知识。