
2.2 分组密码
2.2.1 分组密码介绍
与序列密码通过生成密钥流对消息加解密不同,分组密码(见图2-11)用于对固定分组大小的消息加解密。分组密码有两个重要参数:分组长度与密钥长度。如果分组长度为n比特,密钥长度为k比特,则从数学角度看,分组密码E映射为E:{0,1}k×{0,1}n→{0,1}n即分组密码E是在密钥K控制下的n比特明文到n比特密文的置换,其逆过程即分组密码E的解密算法。分组密码通常包含以下要素。
1)分组大小:常见的分组大小有64比特、128比特等。
2)密钥长度:分组密码使用密钥来控制加密和解密过程,密钥长度关系着算法的安全性。通常来说,较长的密钥能够提供更高的安全性。
3)加密算法:用于将明文分组转换为密文分组。分组密码通常采用迭代结构,通过多轮运算实现加密。每一轮包含不同的步骤,如代换和置换等。
4)解密算法:加密算法的逆过程,通常与加密算法结构相似。
5)密钥扩展算法:将初始密钥扩展成加密或解密算法的每一轮运算所使用的轮密钥的过程。
6)填充方案:如果明文块的大小不是分组大小的整数倍,通常需要使用填充方案来将数据填充到合适的大小。

图2-11 分组密码示意图
分组密码的设计就是找到一种算法,能在密钥控制下从一个足够大且足够好的置换子集合中简单而迅速地选出一个置换,用来对当前输入的明文进行加密变换。一个可实际应用的安全的分组密码应满足以下条件。
1)已知明文M和密钥K,计算C=EK(M)是容易的;
2)攻击者在不知道密钥K时,由密文C算出明文M是不可行的;
3)加解密双方能通过安全的方式共享密钥;
4)算法的安全性依赖于密钥的保密,而不依赖于密码算法的保密。
2.2.2 分组密码的设计原理
现代分组密码的研究始于20世纪70年代,目前已取得丰富的研究成果,常见的分组密码算法如DES、IDEA、RC5、AES、SM4等已被广泛应用。影响分组密码安全性的因素很多,如分组长度和密钥长度等。为抵抗字典攻击,分组长度不能太短,同时考虑到实现因素,分组长度通常为64比特或128比特。为抵抗密钥穷举攻击,密钥长度不能太短,常见的密钥长度有128比特、192比特、256比特等。
如果明文和密文的分组长度都为n比特,那么明文和密文的每个分组都有2n个可能的取值。为了使加密运算可逆(解密运算可行),明文的每个分组都应产生唯一一个密文分组,这样一一对应的变换是可逆的。我们称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数为2n!,但考虑密钥管理问题和实现效率,现实中的分组密码的密钥长度klen往往与分组长度n差不多,由密钥控制共有2klen个变换,而不是理想分组的2n!个变换。分组密码的设计遵循两个重要原则:混淆和扩散。
1.混淆
混淆使密钥和密文之间的关系尽可能复杂化,使得即使攻击者能够分析出密文的某些统计特性,也无法轻易推断出密钥。混淆通常通过非线性变换来实现,如S盒(替代盒)在DES和AES中的应用。这些非线性部件确保了密钥的每一位都以复杂且不可预测的方式影响最终的密文。
2.扩散
扩散是将明文的统计特性分散到整个密文中,确保明文的每一位都对多个密文位产生影响,使得即使攻击者观察到密文的某些模式,也难以将其直接关联到明文的特定部分。理想情况下,明文中的每一位都会影响密文中的所有位,这样就可以最大限度地隐藏明文的统计特性。在实践中,这通常通过复杂的数学变换来实现,如AES算法中的行移位和列混淆步骤。
混淆(Confusion)和扩散(Diffusion)是香农在密码学领域提出的两个核心概念。它们的目的是增强密码系统对统计分析的抵抗力,从而提高安全性。在现代分组密码的设计中,混淆和扩散是不可或缺的。它们共同作用确保了密码系统即使面对强大的攻击者也能保持稳固。例如,在AES算法中,多轮代换和置换操作就是实现扩散和混淆的典型例子。每一轮操作都使密文的每一位与明文的多位以及密钥的多位相关联,从而大大增加了破解密码所需的工作量。
2.2.3 分组密码的结构
如果分组密码E是一个简单函数F迭代若干次而形成的,我们称其为“迭代型密码”。每次迭代称作一轮,相应的函数F被称作“轮函数”。目前,主流的分组密码均是迭代型密码。迭代型密码与分组密码的基本设计原则相符,一方面简单的轮函数容易实现,另一方面轮函数经过若干轮迭代后具有较好的混淆和扩散效果。
对于分组密码的整体结构的研究,我们多采用可证明安全理论的方法,主要研究它们对差分、线性等分析方法的抵抗力,以及在一定假设条件下的伪随机性和超伪随机性等。常见的分组密码结构有Feistel、SP、MISTY、Lai-Massey等,以及进一步细化的Feistel-SP、SP-Feistel、GFN-SP、Feistel-SPS、SP-SPS、Feistel-MISTY、LM-SPS、Feistel-Feistel等。下面简要介绍Feistel结构和SP结构。
1.Feistel结构
Feistel结构可以将任何函数转化成一个置换,由H.Feistel在设计Lucifer分组密码时发明,并因DES的使用而流行。Feistel结构每次更新消息状态的一部分,通过多轮运算实现对整个消息分组的加密,如图2-12所示。设x为待加密的明文,长度为n比特,将x分成两部分x=L0‖R0,其中L0为n1比特,R0为n2比特,n1+n2=n,则Feistel结构型分组密码的加密过程为:

其中,F为轮函数,Ki为种子密钥k派生出来的轮密钥,r称为迭代轮数,,
表示取Xi的左侧n1比特,
表示取Xi的右侧n2比特。最终所得密文y=Lr‖Rr。

图2-12 Feistel结构型分组密码轮函数示意图
相应的,对于给定密文y=Xr=Lr‖Rr,Feistel结构型分组密码的解密过程为:
Xi=Li‖Ri

解密所得明文为x=L0‖R0。
若n1=n2,则Feistel结构被称为“平衡Feistel结构”。此时,加密过程中的状态重组运算为,以及解密过程中的相应运算为Xi=Li‖Ri,
可舍去。若n1≠n2,则Feistel结构被称为“非平衡Feistel结构”或“广义Feistel结构”。
Feistel结构型分组密码的优点是加密过程和解密过程相似,特别是若舍去最后一轮的交换运算,则可使用同一个算法实现加密过程与解密过程,只是轮密钥的使用顺序相反。
2.SP结构
SP结构指代换-置换网络(Substitution-Permutation Net),其主要思想为将明文分组在每轮密钥控制下进行代换,并通过置换来扩散密钥信息,最后经过多轮代换-置换运算实现加密。SP结构是目前使用最为广泛的一种结构,AES、Present等算法都采用这种结构。S一般被称为“混淆层”,主要起混淆作用,具有较大的非线性。P一般被称为“扩散层”,主要起扩散作用。在明确S和P的某些密码指标后,设计者能估计SP结构型密码抵抗差分和线性密码分析的能力。与Feistel结构相比,SP结构扩散效率更高,更适合高速的硬件实现,但要使SP结构具有如Feistel结构加解密类似的特性,需要对密码子模块进行精心设计。
设x为待加密消息,长度为n比特,记X0=x,则SP结构型分组密码加密过程如下:
Xi=P◦S(Xi-1,Ki),i=1,2,…,r
其中,Ki为由种子密钥扩展而得的轮密钥,r为轮数。最终所得密文记为y=Xr。SP结构型密码轮函数示意图如图2-13所示。

图2-13 SP结构型分组密码轮函数示意图
相应的,SP结构型分组密码的解密过程如下:
Xi-1=S-1(P-1(Xi),Ki),i=r,r-1,…,1
最终所得明文为x=X0。SP结构型分组密码的解密过程与加密过程通常不一致,需要使用相应运算的逆运算来实现。
2.2.4 常见的分组密码算法
1.DES
1973年5月15日,美国国家标准局启动了一项公开征集密码体制的活动。在经过广泛的公开讨论和评估之后,IBM设计的一种算法于1977年被正式采纳为数据加密标准,这就是著名的DES算法。由于对安全性的持续评估,美国决定在1998年12月之后停止使用DES算法。作为分组密码的经典例子,DES不仅是第一个被公开的标准加密算法,而且在推动密码学理论的发展和实际应用方面发挥了重要作用。DES的基本理论、设计思想和应用实践仍具有重要的参考价值。
DES算法的分组大小为64比特,密钥长度也为64比特(其中,有效密钥长度为56比特,另外8比特密钥用于奇偶校验),共16轮运算,每轮运算使用的轮密钥长度为48比特。DES加密流程如图2-14所示。DES加密算法由初始置换IP、16轮Feistel结构迭代运算及逆初始置换IP-1构成。DES解密算法与加密算法相同,只是轮密钥的使用顺序相反。设明文为x=x1x2…x64,xi∈{0,1},密钥为K,密文为y=y1y2…y64,yi∈{0,1},则DES加密过程如下:
1){K1,K2,…,K16}=KeySchedule(K);(注,由密钥扩展算法生成轮密钥)
2)L0‖R0=IP(x);
3)对i=1到15,计算
a)Li=Ri-1;
b)Ri=Li-1⊕f(Ri-1,Ki);
4)L16=L15⊕f(R15,K16);
5)R16=R15;
6)y=IP-1(L16‖R16)。

图2-14 DES加密流程
初始置换IP为64比特位置的置换,IP-1为其逆置换,以下只简要介绍初始置换IP。设输入信息为x1x2…x64,经IP置换后的输出信息为,则
,其中,
。
具体地,当i=1,2,…,64时,对应的j的取值为
{58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7}。
轮函数f为DES算法的核心,其输入为32比特状态信息Ri-1与48比特轮密钥Ki,输出为32比特。轮函数f结构如图2-15所示,具体过程如下。
1)将Ri-1使用扩展变换E扩展成48比特。记Ri-1=x1x2…x32,则E(Ri-1)=x32x1x2x3x4x5‖x4x5x6x7x8x9‖…‖x28x29x30x31x32x1,即将Ri-1划分成8个4比特x4j+1x4j+2x4j+3x4j+4,j=0,1,…,7,依次对其左右各扩充一位相邻的比特,x1左侧扩充的比特为x32,x32右侧扩充的比特为x1。
2)将Ri-1扩展所得48比特值与轮密钥异或,即Xi=E(Ri-1)⊕Ki。
3)使用8个6比特输入4比特输出的S盒进行混淆运算。8个S盒如表2-5所示。

图2-15 轮函数f结构示意图
表2-5 DES算法轮函数中8个S盒的取值

(续)

S盒是DES算法的唯一非线性部件,也是决定算法安全性的关键。若给定某个S盒的输入为b0b1b2b3b4b5,则其输出结果为该S盒中第b0b5行、第b1b2b3b4列所对应的值。例如,若输入第一个S盒S1的值为010111,则输出第01=1行、第1011=11列所对应的值11,即S1(010111)=11。对输入的48比特值,将其划分为8个6比特值,然后依次查询8个S盒,输出32比特值Y。
4)使用置换运算P对32比特值Y处理后输出。置换P的取值为
P={16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25}
即对输入x=x1x2…x32,经置换后,输出y=x16x7x20…x11x4x25。
密钥扩展算法KeySchedule(K)将输入的64比特密钥(56比特有效密钥和8比特校验值)扩展成16个48比特轮密钥K1,K2,…,K16。密钥扩展过程如图2-16所示。
DES算法包含3种变换:置换选择PC-1与PC-2,循环左移变换LS。设64比特密钥K=k1k2…k64,密钥扩展算法KeySchedule(K)如下:

图2-16 DES密钥扩展算法结构图
1)使用置换选择PC-1去除校验位k8,k16,…,k64,并对余下的56比特值进行重新排列,置换选择PC-1取值为{57,49,41,33,25,17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,63,55,47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4}。并记经PC-1置换选择后所得56比特值为C0D0,其中C0、D0分别为左右各28比特值。
2)对1≤i≤16,计算Ci=LSi(Ci-1),Di=LSi(Di-1),其中LSi表示对输入的28比特值进行循环左移,当i=1,2,9,16时,LSi表示循环左移1比特,否则LSi表示循环左移2比特。
3)根据置换选择PC-2从状态值CiDi依次获取每轮轮密钥Ki,其中置换选择PC-2的取值为{14,17,11,24,1,5,3,28,15,6,21,10,23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,30,40,51,45,33,48,44,49,39,56,34,53,46,42,50,36,29,32}。
DES算法的解密过程与加密过程相同,只是轮密钥的使用顺序相反。DES算法的有效密钥长度只有56比特,密钥空间过小,已无法抵抗密钥穷举攻击。1999年1月,“DES破译者”在分布式网络的协同下,在22h15min时间内找到了DES的密钥。DES算法已无法满足安全要求。为了延长DES算法的使用寿命并充分利用DES算法现有的软件和硬件资源,研究者提出了一些对DES的改进方案,如使用多重DES以扩大密钥空间。由于DES最初设计主要基于硬件实现,在软件中运行本身偏慢,多重DES导致运行速度更慢,因此DES算法正在逐步退出历史舞台。
2.AES
1997年,为了找到一种更高效且安全的加密标准来替代DES算法,美国国家标准与技术研究院(NIST)向全球发起了高级加密标准(AES,Advanced Encryption Standard)的征集活动。这一新标准的要求是效率超过三重DES,同时在安全性上不亚于三重DES,并支持128比特、192比特、256比特的密钥长度。经过超过3年的广泛讨论和评估,NIST于2000年10月宣布比利时学者Vincent Rijmen和Joan Daemen设计的Rijndael算法为最终胜出方案。2001年11月26日,NIST正式发布了新的AES(FIPS PUBS 197)。这一标准的制定进一步推动了分组密码设计和分析技术的发展。
AES算法分组大小为128比特,密钥长度为128比特、192比特、256比特,相应的运算轮数为10、12、14轮,分别记为AES-128、AES-192和AES-256。AES算法采用SP结构,每轮运算由字节代换、行移位、列混淆、轮密钥加构成,最后一轮缺少列混淆运算,并在首轮运算之前使用额外一个轮密钥对消息进行白化处理。下面以AES-128为例介绍AES算法加密过程。AES-128算法结构如图2-17所示。
记AES-128算法待加密的消息为P=X0,由128比特初始密钥K经密钥扩展算法所得轮密钥为K0,K1,…,K10,则AES-128加密过程如下:
Xi=MC◦SR◦SB(Xi-1⊕Ki-1),i=1,2,…,9
X10=SR◦SB(X9⊕K9)⊕K10
输出的密文为C=X10。其中,SB表示字节代换运算,SR表示行移位运算,MC表示列混淆运算。
AES算法的运算过程均基于字节运算,将128比特分组及加解密过程的内部状态以4×4矩阵表示,矩阵中的每个元素为一个字节,128比特状态State=s0s1…s15,si∈GF(28),以如下矩阵表示:

其中,si,j=s4i+j,i,j=0,1,2,3。

图2-17 AES-128算法结构
基于该数据表示方法,下面依次简要介绍AES算法的各运算步骤。
(1)字节代换
字节代换是AES算法唯一的非线性部件,决定着算法的安全强度。字节代换由16个相同的8比特S盒构成。字节代换过程如图2-18所示。S盒取值如表2-6所示。对于输入的8比特信息,可以其高4比特作为行数、低4比特作为列数来查询该S盒,所得结果即S盒的输出值。如S盒的输入信息为00101011,则输出为第0010(2行)、1011(b列)的值F1。

图2-18 字节代换示意图
表2-6 AES算法的S盒取值

(2)行移位
行移位是将输入状态矩阵的每一行按字节进行循环移位,第i行循环左移i字节。行移位如图2-19所示。
(3)列混淆
列混淆运算将状态矩阵中的每个列视为GF(28)上的多项式,再与一个固定的多项式a(x)进行模x4+1乘法运算。令
sj(x)=s3,jx3+s2,jx2+s1,jx+s0,j,0≤j≤3


图2-19 行移位示意图
则

其中,a(x)={03}x3+{01}x2+{01}x+{02},⊗表示模x4+1乘法。列混淆运算以矩阵乘积形式表示为:

(4)轮密钥加
轮密钥加运算即将128比特状态按比特与128比特轮密钥进行异或运算。
AES算法的密钥扩展算法将种子密钥(矩阵)K扩展成长度为Nr+1个轮密钥,其中Nr=10、12、14,分别对应AES-128/192/256算法的轮数。设N为种子密钥以32比特字划分的长度,N=4、6、8分别对应AES-128/192/256算法。将种子密钥K表示成32比特字序列K0,K1,…,KN-1,并记扩展所得密钥信息为32比特字序列W0,W1,…,W4N-1,则密钥扩展过程如下:

其中,密钥扩展所得每一轮轮密钥为Ki=(W4i,W4i+1,W4i+2,W4i+3),i=0,1,…,Nr。SB表示字节代换,与AES加密算法中相同。对于32比特输入W=(b0,b1,b2,b3),循环移位运算Rot(W)=(b1,b2,b3,b0)。32比特常数rconi=(rci,0016,0016,0016),其中0016表示十六进制表示,rci取值如表2-7。
表2-7 rci的取值

与DES等Feistel结构类密码算法不同,AES的解密算法与加密算法并不相同。在AES的解密算法中,每一轮操作均为相应操作的逆运算,且轮密钥使用顺序相反。由于解密算法中每一步逆运算与加密算法一一对应,在此略过解密算法的具体过程。
3.SM4
SM4(原SMS4)算法由国家密码管理办公室于2006年发布,并于2012年成为密码行业标准GM/T 0002—2012,2016年成为国家标准GB/T 32907—2016《信息安全技术SM4分组密码算法》,2021年成为国际标准ISO/IEC18033——3:2010/AMD1:2021《信息技术 安全技术 加密算法第3部分:基于分组密码修正案1:SM4》。SM4算法在我国广泛应用于各种领域,包括金融、电子政务、互联网安全、物联网等。
SM4算法的分组大小和密钥长度均为128比特,采用非平衡Feistel结构,共迭代32轮。SM4的加解密算法与密钥扩展算法都采用32轮非线性迭代结构。解密算法与加密算法的结构相同,只是轮密钥的使用顺序相反,即解密轮密钥是加密轮密钥的逆序。SM4加密算法结构如图2-20所示。设SM4加密算法输入信息为X=(X0,X1,X2,X3),Xi∈GF(232),i=0,1,2,3,由128比特种子密钥经密钥扩展算法生成的32轮轮密钥记为rk0,rk1,…,rk31,加密所得密文记为Y=(Y0,Y1,Y2,Y3),则SM4算法加密过程如下:
Xi+4=Xi⊕T(Xi+1⊕Xi+2⊕Xi+3⊕rki),i=0,1,…,31
(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32)
其中,R为反序变换,T=L◦τ为轮变换。
对于32比特输入a=a0‖a1‖a2‖a3,ai∈GF(28),非线性变换τ由4个并行的相同8比特S盒构成,即τ(a)=S(a0)‖S(a1)‖S(a2)‖S(a3),其中S盒的取值如表2-8所示。对于输入的8比特信息,可以其高4比特作为行数、低4比特作为列数来查询该S盒,所得结果即S盒的输出值。如S盒的输入信息为00101011,则输出为第0010(2行)、1011(b列)的值43。

图2-20 SM4加密算法结构示意图
表2-8 SM4算法的S盒取值

(续)

线性变换L(a)=a⊕(a<<<2)⊕(a<<<10)⊕(a<<<18)⊕(a<<<24),其中<<<表示循环左移运算。
设SM4加密算法的密钥为MK=(MK0,MK1,MK2,MK3),经密钥扩展算法生成的32轮轮密钥为rk0,rk1,…,rk31,则密钥扩展算法如下:
(K0,K1,K2,K3)=(MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3)
rki=Ki+4=T′(Ki+1⊕Ki+2⊕Ki+3⊕CKi),i=0,1,…,31
其中,FK0=A3B1BAC6,FK1=56AA3350,FK2=677D9197,FK3=B27022DC。变换T′=L′◦τ,非线性变换τ与轮变换T中的τ相同,均由4个相同的8比特S盒构成,线性变换L′(a)=a⊕(a<<<13)⊕(a<<<23)。CKi为固定参数,取值为
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。
2.2.5 分组密码的工作模式
分组密码定义了固定长度的消息块上的一种置换操作。而实际应用中,由于待加密消息的长度不固定,分组密码需根据应用场景需求,结合适当的工作模式使用。分组密码的工作模式规定了分组密码的使用方式。GB/T 17964—2021《信息安全技术 分组密码算法的工作模式》规定了以下9种分组密码的工作模式。
1)电码本(ECB)工作模式:在ECB工作模式下,每个消息分组独立地使用相同的密钥进行加密。这意味着相同的明文块将被加密成相同的密文块,因此ECB工作模式不适用于对较长的消息进行加密,主要用于对短消息或会话密钥的加密。
2)密文分组链接(CBC)工作模式:在CBC工作模式下,前一个密文分组会与当前明文分组进行异或操作,然后再进行加密。这个异或操作引入了密文分组之间的依赖性,使得CBC模式更适合对长消息进行加密。另外,CBC工作模式下解密可以并行处理。
3)密文反馈(CFB)工作模式:CFB工作模式下,前一个密文块用于更新初始向量,然后用于后续消息的加密。CFB模式可看成一种自同步序列密码,适用于流数据加密,特别适用于低误码率网络中的数据保护。
4)输出反馈(OFB)工作模式:OFB工作模式下通过反复加密初始向量生成密钥流,然后与消息进行异或操作以生成密文。OFB工作模式适用于对流数据进行加密,特别是在噪声环境下。国家标准GB 35114—2017《公共安全视频监控联网信息安全技术要求》规定使用分组密码的OFB工作模式进行视频数据的加密保护。
5)计数器(CTR)工作模式:CTR工作模式通过加密计数器来生成密钥流,然后与消息进行异或操作以生成密文。CTR工作模式具有高度的并行性,适用于高速网络数据加密,特别是在需要快速加解密的情况下,可满足突发的高速加解密需求。
6)带密文挪用的XEX可调分组密码(XTS)工作模式:XTS工作模式通常用于磁盘加密等场景,结合了分组密码和特定的操作,以提供对长期存储数据的高度保护。
7)带泛杂凑函数的计数器(HCTR)工作模式:HCTR工作模式是CTR工作模式的变种,引入了泛杂凑函数以提高安全性,通常用于磁盘加密等场景。
8)分组链接(BC)工作模式:BC工作模式与其他工作模式不同,它具有一种特殊的错误传播性质,即单一错误可能导致所有后续密文分组解密出错。因此,在设计应用时,我们需要特别小心处理错误情况。
9)带非线性函数的输出反馈(OFBNLF)工作模式:OFBNLF工作模式是OFB和ECB工作模式的变种,引入了非线性函数以提高安全性。密钥在每个分组中都会改变,增加了密码的复杂性。
我们应根据不同的应用场景和需求选择分组密码的工作模式,以满足数据加密和解密的安全性和性能要求。选择和使用合适的分组密码工作模式对于数据保护至关重要。