3.2　对称密钥加密

对称密钥加密（symmetric key cryptography），又称为私钥加密、单钥加密，因同一个密钥既用于加密又用于解密而得名。

密钥实际上就是一串二进制数据。既然对称加密方法的密钥也要用于解密，那么密钥一定要被妥善保护好、绝不示人，这是其称为私钥的原因。又由于密文的合法接受者也需要这个私钥，所以如何在通信双方间安全地分享密钥就显得非常重要。

对称密钥加密是实现信息保密的主要手段，具有如下技术特点：

•　密钥是关键（Key is key）。现代加密技术的加密算法可以公布，加密代码也可以公开，只要保护好密钥，密文就是安全的。

•　密钥长度决定安全性。密钥越长则加密强度越大，因为穷举密钥几乎是尝试破解的唯一方式，那么密钥每增加1位，就可以给破解者的计算工作量增加1倍，密钥增加1字节，破解工作量就是原来的256倍，相当于原本1天就可破解，现在则需要将近1年。

•　对称加密算法被设计为具有很高的计算效率，可面向大量数据的加密，如文件、数据库、流媒体等，然而密钥的安全生成、安全分发、安全存储、安全使用需要较大的管理工作量。

对称密钥加密可分为流式加密和分组加密两大类，前者适用于流媒体应用，例如在线播放音乐或视频，后者应用范围更广，适用于绝大多数需要数据加密的场合。常用的对称密钥加密技术有BLOWFISH、TEA、DES、AES、IDEA、SM4、RC4等，本章选取其中具有代表性的SM4和DES来展开算法细节。

在比特币核心系统中并没有直接采用对称密钥加密技术，这应该与比特币提倡信息透明化有关，而且存储的信息也比较单一。但是在区块链扩展应用中，当需要对保存的私密信息进行保护时，对称密钥加密技术就有用武之地了。

3.2.1　分组加密技术原理

分组加密（block ciphering）是以一定长度的数据块为单位，对其进行整体变换，从明文块生成密文块，密文块与明文等长，一块数据加密完成后继续加密下一块，密文块也是依次执行解密。就加密算法本身而言，每一块数据的加密或解密运算都可以独立进行。

设分组大小为nB（字节）。明文数据交付加密前，需要先进行数据填充（填充数据可为任意数值），如图3.5所示，使总长度为n的整数倍。最后4字节为长度字段，用以表示有效数据长度，以便解密后完全恢复原始数据。

显然，对nb（位）的分组，有2ⁿ个不同的明文分组和2ⁿ个不同的密文分组，相互间共有2ⁿ！个非奇异的映射（变换）关系。

不失一般性，设n=4，如图3.6所示，4b明文分组M=（M₃M₂M₁M₀）共有2⁴=16种编码组合，编码器的16个输出分别为X₀~X_f，共有2⁴！=20，922，789，888，000种不同的映射关系。设对于一种特定的映射关系转换为Y₀~Y_f，可解码为4b，输出C=（C₃C₂C₁C₀），C即为明文M加密后的密文。例如，4b明文为1001（十六进制9），编码结果应为X₉，在图3.6所示的映射关系下被转换为Y₇，则可解码并输出密文0111。在相同的映射关系下，若以C为密文输入、M为明文输出，则为解密操作。

“不对啊，4位明文不是应该就只有16种编码组合，怎么会弄出16！个映射关系呢？”Bob有点不在状态，脑子一时转不过弯来。

乐于助人的Alice一如既往地耐心解释：“映射是从编码器的16个输出到解码器的16个输入之间的不同关系。对于例子中的映射关系，X₉映射为Y₇、X₂映射为Y₀，如果换一种映射关系，例如只把Y₀和Y₁上两根线调换位置，其他不变，那么X₉仍然映射为Y₇，X₂就映射为Y₁了。所以编码组合与映射关系是不同的概念。”

当映射关系改变时，同一个明文可输出不同的密文，这就相当于采用了不同的密钥而产生不同的加密结果。换句话说，映射关系就是密钥，每一种变换就是一个密钥。因此，映射关系需要像个“黑盒子”一样严密保护起来。

这个加密模型穷尽了所有的编码和映射关系，在技术上已经无法更好了，因此被称为是“理想分组加密”方法，保密性达到最佳。然而，理想归理想，该模型存在一个不容忽视的问题：密钥过长。如图3.6所示的映射关系可表示为如图3.7所示的编码对应表，每一种不同映射产生一张表，nb明文总共可得2ⁿ！张表。不失一般性，将明文编码统一为升序排列，密文一行所代表的就是密钥，则密钥长度为n×2ⁿb。对于常用的64b分组，其密钥长度将达到惊人的10²¹b。过长的密钥对数据加密的计算和管理均会带来不利影响。

所以实际的分组加密算法设计采用的是理想分组加密的近似体制，相当于取不同映射关系的一个子集，以减少映射关系数为代价，换取较短的密钥长度，虽然牺牲了一部分保密性，但使加密方法更具有实用性。

根据信息论创始人香农（Claude Shannon）的加密理论，使用信息编码的混淆（confusion）和扩散（diffusion）方法，可以抵抗基于统计方法的密码分析（破解）。混淆可以尽可能使密文和密钥间的统计关系复杂化，防止密钥被发现；扩散则使明文的统计特征消散在密文中，可以让每个明文编码单元尽可能多地影响多个密文编码单元。

费斯托（Feistel）模型就是基于香农理论设计的对称密钥加密统一架构。各种对称密钥加密算法都是参照这一模型设计的。在Feistel模型中，数据运用代换（substitution）和置换（swap）操作进行处理，分别就是混淆和扩散的实际应用。代换采用函数运算方法，置换通过数据的交叉换位实现。

设：明文和密文为2wb，密钥为K。图3.8所示即为Feistel加密的算法结构。该模型由i轮加密运算组成，每轮具有相似的运算方法，分别使用由密钥K生成的该轮次的子密钥K_i。每轮2wb输入被分为wb的左半部分和wb的右半部分，进行代换运算，在输出前左、右两部分进行置换运算。算法结束前再进行一次左右置换运算，最终合并成2wb的密文。

解密过程与加密过程完全一致（注意不是逆向进行），但解密时逆序使用子密钥。这一论断的正确性可被证明，如下：

不失一般性，设加密算法执行16轮，再设：加密时，明文为LE₀|RE₀，输出密文为RE₁₆|LE₁₆；解密时，密文为LD₀|RD₀，输出密文为RD₁₆|LD₁₆。

显然有：

LD₀=RE₁₆，　RD₀=LE₁₆

对于加密过程有：

LE₁₆=RE₁₅，　RE₁₆=LE₁₅⊕f（RE₁₅，K₁₆）

其中，⊕表示按位异或运算（位相同得0，相异得1），其“优秀”性质是一个数被另一个数异或两次就会还原。

按照解密过程第1轮算法有：

LD₀=RE₁₆，　RD₀=LE₁₆，　LD₁=RD₀=LE₁₆=RE₁₅

RD₁=LD₀⊕f（RD₀，K₁₆）=RE₁₆⊕f（RE₁₅，K₁₆）=[LE₁₅⊕f（RE₁₅，K₁₆）]⊕f（RE₁₅，K₁₆）=LE₁₅

因此，解密第1轮输出LE₁₅|RE₁₅，正是加密第16轮输入左右互换的值。

依此类推，解密第16轮：

LD₁₆=RE₀，　RD₁₆=LE₀

最终换位输出为LE₀|RE₀，正是原始明文（证毕）。

Feistel加密模型采用的i轮次运算又称为迭代（iteration）操作。迭代轮次数越多，密文信息的混淆和扩散越彻底，保密性就越强，但会有加解密速度越慢的“后遗症”，作为妥协，通常选择16轮迭代。此外，分组长度和密钥长度越长，安全性能也越好，但同样存在拖慢运算速度的弊端，常见的分组长度选择64b或128b，密钥长度则会根据算法指标、密级要求来确定。

3.2.2　SM4算法

SM4算法（原名SMS4）是基于Feistel模型的对称密钥分组加密算法，作为中国的第一个商用密码国家标准，于2006年1月发布。

SM4采用的数据分组长度和密钥长度均为128b，数据处理单位为8b和32b，进行32轮非线性迭代运算。

如图3.9所示，SM4将128b的明文分割为4个32b分组块，采用8次循环，每次使用轮函数f进行4轮迭代（故总共为32轮迭代），每轮使用一个子密钥（轮密钥）。子密钥由128b的密钥经扩展函数g生成。最后，反向排列32b的X₃₂~X₃₅，合并为128b的密文。

SM4的加密运算过程可用如图3.10所示的等价变换图表示。

设X_j为32b寄存器，k_i为轮密钥。SM4每轮的迭代运算由按位异或（⊕）、循环左移（＜＜＜）和变换函数S所组成，轮函数f定义如下：

X_i+4=f（X_i，X_i+1，X_i+2，X_i+3，k_i）

=X_i⊕T（X_i+1⊕X_i+2⊕X_i+3⊕k_i），i=0，1，…，31

T（x）=L（S（x））

L（x）=x⊕（x＜＜＜2）⊕（x＜＜＜10）⊕（x＜＜＜18）⊕（x＜＜＜24）

如图3.11所示，32b的S函数由4个并列的8b单元的S-box变换所构成。S-box采用查表选择法，使用如表3.1所示的置换选择表，属于一种非线性变换方式。表中的256个数值从0x00到0xff，具有唯一性。设S-box的8b输入为十六进制0xRC，S-box以R为行号、C为列号查表，所得的数据作为S-box的输出结果。例如，输入0x2a应查行号为2、列号为a的数据，经S-box输出为0x0b。

SM4加密算法每轮使用不同的32b子密钥，每个子密钥都是由128b原始密钥K经变换生成。设4个32b常数为FK_i（i=0，1，2，3）：

FK₀=0xA3B1BAC6，　FK₁=0x56AA3350，

FK₂=0x677D9197，　FK₃=0xB27022DC

又设32b参数为CK_i（i=0，1，2，…，31），定义：CK_i=<ck[i][0]|ck[i][1]|ck[i][2]|ck[i][3]>，即CK_i是由4个一组的8b数值ck[i][j]（j=0，1，2，3）拼接而成，而ck[i][j]可根据其下标进行取值：ck[i][j]=（4i+j）×7（mod 256）。由此可得32个CK_i参数为：

      00070e15 1c232a31 383f464d 545b6269 70777e85 8c939aa1 a8afb6bd c4cbd2d9
      e0e7eef5 fc030a11 181f262d 343b4249 50575e65 6c737a81 888f969d a4abb2b9
      c0c7ced5 dce3eaf1 f8ff060d 141b2229 30373e45 4c535a61 686f767d 848b9299
      a0a7aeb5 bcc3cad1 d8dfe6ed f4fb0209 10171e25 2c333a41 484f565d 646b7279

将密钥K分割为4个32b数值，即K=（K₀，K₁，K₂，K₃）。设每轮使用的子密钥为k_i（i=0，1，2，…，31），Z_j为中间变量，密钥变换算法如下：

Z_j=K_j⊕FK_j，　j=0，1，2，3

k_i=Z_i+4=Z_i⊕T′（Z_i+1⊕Z_i+2⊕Z_i+3⊕CK_i）

T′（x）=L′（S（x）），　L′（x）=x⊕（x≪13）⊕（x≪23）

可见，SM4子密钥的生成同样采用了加密运算中的S函数变换，迭代运算方法也很类似，便于算法的实现。

SM4算法的解密过程与加密完全相同，但逆序使用子密钥。

3.2.3　DES算法

数据加密标准（Data Encryption Standard，DES）是信息加密领域最著名、应用最广泛的对称密钥加密技术，于1977年作为美国联邦标准发布，被全球各国广泛采用。DES采用DEA（Data Encryption Algorithm）算法，但习惯上称之为DES算法。

DES符合Feistel模型，针对64b数据块（分组）进行加密和解密操作。DES采用的密钥为64b的任意数，每字节的最高位作为奇偶校验位，因此实际密钥长度为56b。

输入明文被划分成64b分组单元，DES对每个分组进行16轮迭代运算，每轮使用一个48b的子密钥，而子密钥由56b的原始密钥变换而来。

DES算法首先对64b（设编号为1~64）的输入分组作初始置换（Initial Permutation，IP），置换规则如表3.2所示：第6位置换到第24位的位置，第57位置换到第33位的位置。即把位排列次序“打乱”，最后输出自然地分为32b的L₀、R₀两部分。

随后，DES进入16轮的迭代运算f，包括扩展换位运算、选择压缩运算、置换运算等步骤，每轮使用一个子密钥K_i。运算过程如表3.3所示。

经过16轮次迭代运算f后，得到L₁₆和R₁₆，以此作为输入，进行如表3.4所示的逆置换（IP^-1）操作，即可得到输出的64b密文。IP^-1正好是IP的逆变换，例如，第1位经过IP后，在第40位的位置；而通过IP^-1后，从第40位换回到第1位的位置。

扩展换位运算E可实现32b到48b变换，如表3.5所示，位排列次序发生变化，部分位被复制。

置换运算P实现的是32b的换位操作，如表3.6所示，对位排列次序进行了调整。

选择压缩运算S如图3.12所示。输入的48b数据被均分为8份，各为6b，分别由S所包含的S₁~S₈8个选择函数（S-box）进行处理。每个选择函数的功能是把6b数据变换为4b数据，最终把48b输入值压缩转换为32b。

选择函数S₁~S₈采用查表变换方法。如表3.7所示，每个S-box均占有4行（0~3行）、每行16列（0~15列）的数值矩阵。设输入6b数据为D₁D₂D₃D₄D₅D₆，令列号=D₂D₃D₄D₅（取值0，1，2，…，15），行号=D₁D₆（取值0，1，2，3），查表得到对应的数以4b表示，即得到S-box输出。例如，S₈输入110110，则行、列号为（2，11），查表得6，输出为0110。

16轮迭代运算f中，每轮使用的子密钥K₀~K₁₅来自64b初始会话密钥K（bit₀~bit₆₃）。先实施密钥缩小选择换位运算1（如表3.8所示），换位的同时顺便去除了校验位（每字节的最高位，如bit₇），得到各28b的两部分P和Q，作为每次计算子密钥的输入。

共16次密钥变换（i=0，1，2，…，15）的计算方式一致：对P和Q分别进行M[i]位循环左移，M[i]={1，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1}，得P和Q，合并得到56b后，再实施缩小选择换位运算2（如表3.9所示），即获得用于第i轮迭代运算的48b子密钥K_i。

DES解密运算方法和加密完全一致，只是逆向使用子密钥。

DES在诞生之初，有人曾估计要使用耗资2000万美元的专用计算机连续运行12小时才可能将其破解，当时它被认为很强大。然而，这一经典的算法如今面临安全性严重不足的问题，一方面是破解方法不断被探索，另一方面是56b密钥长度太短，很难抵抗性能越来越强大的计算机进行的暴力攻击。

改善DES保密性的一种可行方式为三重DES（triple DES），即对一个明文分组用3个相同或不同的密钥实施3次DES加密（或解密）运算，可获得大约相当于112b长度密钥的强度。设：加密操作为E，解密操作为D，密钥为K₁、K₂、K₃，则可采用以下4种模型之一实现加密：E（K₁）E（K₂）E（K₃）；E（K₁）D（K₂）E（K₃）；E（K₁）E（K₂）E（K₁）；E（K₁）D（K₂）E（K₁）。

DES加密实际应用时，根据在加密过程中对明文分组不同的处理手段，分为4种工作方式（如图3.13所示），有的支持并行计算，有的可加强密文分组之间的相关性。

DES算法的改进是高级加密标准（Advanced Encryption Standard，AES）。