第1章 分组密码

1.1 数据加密标准和分组密码的四种工作方式

1.1.1 DES加密算法的研制经过

DES（Data Encryption Standard）加密算法的研究历经6年的时间（1968年—1974年）。20世纪60年代末，IBM公司的一个研究组在菲斯特（Feistel）的带领下研制出了Lucifer密码。1971年，IBM公司请塔其曼（Tuchman）和迈耶（Meyer）在Lucifer密码的基础上进一步做研究，以增加密码强度。他们经过3年多的研究，试图破解Lucifer密码，通过搜索强有力的代替置换网络和密钥编制函数，完成了DES加密算法的设计和编制工作。

1976年年底，DES加密算法被采纳为联邦标准，自1977年7月15日起正式生效。1986年，NSA宣布停止执行DES计划。从1988年1月1日起，除了电子资金过户（Electronic Fund Transfer），不再批准政府部门使用采用DES加密算法的产品，但已批准的产品可继续销售和使用。美国安全局（National Security Agency, NSA）感到DES加密算法的广泛使用已使之成为众矢之的。

1.1.2 DES加密算法

1.DES加密算法的框架

DES加密算法如图1.1.1所示。输入明文块M0（64比特）, M0=m0m1…m63，经初始置换IP（见表1.1.1）换位成M0=m57m49…m6。

将M0分成左右两个半块（32比特）, M0=(L0, R0), (L0, R0)经过第1层变换后记为(L1, R1)，其中，L1=R0, R1=L0⊕f(R0, K1)。

经过第 i（i=1,2, …,16）层变换后记为(Li, Ri)。其中，Li=Ri-1, Ri=Li-1⊕f(Ri-1, Ki)，此处的f函数将在下面详述，Ki为密钥，经过16层变换后，预输出为(R16, L16)，再经IP-1置换成密文块C。

2.f函数

f函数是DES加密算法的核心部分（见图1.1.2），进入第i层时，f函数的输入Ri-1（32比特）先经扩张函数E变成48比特，设Ri-1=r0 r1r2…r31经E扩张后记为Ti-1=E(Ri-1)。

Ti-1=t0 t1 t 2…t 47

参考表1.1.2的比特选择表和置换表，其中t 0=r 31, t 1=r0, t2=r 1, …, t 46=r 31, t47=r 0。Ti-1与Ki的48比特按位进行模2加可得B=b0b1…b47。B顺序地按6比特分组，分别进入代替表（S盒） S0, S1, …, S7，见表1.1.3。

代替的规则如下：输入Si的6比特的左端1比特和右端1比特组成二进制数0～3中的某个数，作为取Si的行数；中间4比特组成二进制数0～15中的某个数，作为取Si的列数；在Si表行列交叉处取得一个数，用4比特表示作为Si盒的输出。例如，若输入S0盒的6比特为“011011”，则行数为“01”，列数为“1101”，即13。S0的第1行第13列的元素为5，于是输出为“0101”，如下所示。

经过S盒后的32比特再经过置换表可改变比特位置，结果作为f函数的输出。

3．子密钥发生器

64比特的初始密钥K通过子密钥发生器变成K1, K2, …, K16，分别作为1到16层的f函数子密钥（48比特）。

在64比特的初始密钥K中，除去8比特（第7、15、23、31、39、47、55、63比特作为校验位），其余56比特送入置换PC I，经过坐标置换后分成两组，每组28比特，分别送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分别将存储的数按移位次数表进行循环左移。每次移位后将C和D寄存器的第6、9、14、25比特除去，其余比特经置换后PC II送出48比特，作为第i次迭代时所用的子密钥Ki。子密钥发生器如图1.1.3所示。

DES加密算法可以简单归结如下。

加密过程：

L0, R0←IP（64比特输入）

Li← Ri-1

Ri←Li-1⊕f(Li, …, Ki), i=1,2, …,16

（64比特密文）← IP-1(R16L16)

DES的加密运算是可逆的，其解密过程与加密过程类似。

解密过程：

R16, L16←IP（＜64比特密文＞）

Ri-1← Li

Li-1←Ri⊕f(Ri-1, Ki), i=16,15, …,1

＜64比特明文＞ ← IP-1(L0R0)

这里给出了一个加密过程的例子（用十六进制表示）：

密钥：03 96 48 C5 39 31 39 65

明文：00 00 00 00 00 00 00 00

经置换IPRG: 00 00 00 00 00 00 00 00

第1层：00 00 00 00 85 7E 2A 43

第2层：85 7E 2A 43 D7 2F 0D 7B

第3层：D7 2F 0D 7B C7 6E 6C B1

第4层：C7 6E 6C B1 4C B0 77 8A

第5层：4C B0 77 8A 72 2B BC 81

第6层：72 2B BC 81 59 85 72 7B

第7层：59 85 72 7B 82 67 AE 9C

第8层：82 67 AE 9C E7 DD DB 94

第9层：E7 DD DB 94 71 90 0F 11

第10层：71 90 0F 11 0A AD 33 E4

第11层：0A AD 33 E4 51 61 B2 81

第12层：51 61 B2 81 7D DD 4A 9E

第13层：7D DD 4A 9E 75 17 39 28

第14层：75 17 39 28 9D A0 1E 4E

第15层：9D A0 1E 4E BB 14 FC F2

第16层：73 6A 7F 8A BB 14 FC F2

经过IP-1后的密文：C4 D7 2C 9D EE DE 5E 8B

1.1.3 DES的工作方式

DES的工作方式也适用于其他分组密码。

（1）电子密本（ECB）方式。将明文＜X＞分成m个64比特分组，即

＜X＞=(x0, x1, …, xm-1)

如果明文长度不是64比特的整数倍，则在明文末尾填补适当数目的规定符号。ECB方式对明文分组用给定的密钥K分别进行加密，可得密文

＜Y＞=(y0, y1, …, ym-1)

式中，yi=DES(K, xi), i=0,1, …, m-1。这种工作方式组间同明即同密，组间可能出现重复。

（2）密文分组连接（CBC）方式。在CBC方式下，在对每个明文分组 xi加密之前先与前一分组的密文yi-1按位进行模2加后，再进行DES加密，需预置一个初始向量(IV)y-1=IV。

CBC方式：

＜X＞ → ＜Y＞, ＜Y＞=CBC(k, ＜X＞)

y-1=IV

yj=DES(K, xj⊕yj-1), 0≤j≤m

脱密CBC-1：

＜Y＞ → ＜X＞

y-1=IV

xj=DES-1(K, yj)⊕yj-1

CBC方式克服了ECB方式组间重复的缺点，但由于明文分组的加密与前一分组密文有关，因此前一分组密文的错误会传播到下一分组。

（3）密文反馈（CFB）方式（可用于序列密码）。设明文为＜X＞=(x0, x1, …, xm-1)，其中 xi由t比特组成，0＜t≤64。

由图1.1.4可知，CFB方式实际上将DES作为一个密钥流发生器，在t比特密文的反馈下，每次输出t比特乱数来对t比特明文进行加密，即：

＜X＞ → ＜Y＞

yi=leftt[DES(k, Zi)]⊕xi

或

yi=rightt[DES(k, Zi)]⊕xi

式中，Z0=IV（初始向量为64比特）。

Zi=right64[Zi-1‖yi-1], 1≤i＜m-1

式中，“‖”表示相接，leftt[·]表示取左边的t比特，rightt[·]表示取右边的t比特。

由于CFB方式采用密文反馈，因此对密文错误（通常由信道传输等造成）比较敏感，t比特密文中只要有1比特的错误，就会导致连续数个t比特出错。

（4）输出反馈（OFB）方式（可用于序列密码）。

由图1.1.5可看出，OFB方式与CFB方式的不同点只是OFB方式直接取DES加密算法输出的t比特作为反馈（而CBF方式以密文yi作为反馈），其余都与CFB方式相同。

＜X＞ → ＜Y＞

yi=leftt[DES(k, Zi)]⊕xi

或

yi=rightt[DES(k, Zi)]⊕xi

Z0=IV（初始向量为64比特）

Zi=right64{Zi-1‖left t[DES(k, Zi-1)]}

或

Zi=right64[Zi-1‖rightt[DES(k, Zi-1)]]

OFB方式以DES加密算法的输出作为反馈，因而克服了CFB方式密文错误传递的缺点。

1.1.4 DES加密思想和特点

香农（Shannon）曾建议使用不同类型的函数（如反复、交替地进行代替和简单的线性变换）来构成一个混搅变换（Mixing Transformation），通过这种变换可以把明文消息随机、均匀地分布在所有可能的密文消息集合上。DES加密算法每层的f函数包含加乱（⊕Ki）、代替（S盒）、移位（置换P），也就是反复、交替地使用这些变换使输出的每个比特都依赖于整个输入组，使加密的每个比特都依赖于整个密钥，即通过多层的反复变换，使密文的每个比特都是明文和密钥的完全函数。

DES加密算法采用扩张函数E实现S盒和P置换，采用S盒进行小块的非线性变换，以达到混合（Confusion）；采用P置换进行大块的线性变换，以达到扩散（Diffusion）。因此， S盒的设计是DES加密算法的一个核心问题。实际使用的S盒是经过精心设计和严格挑选的，因为S盒的某些设计原则是敏感的，NSA给出了下列三条属于设计准则。

① S盒的输出不是输入的线性函数或仿射函数。

② 改变S盒的1个输入比特，就至少可引起S盒的2个输出比特不同。

③ S(X)与S(X+001100)至少有2个比特不同。

DES加密算法具有互补性的特点，假设对明文X逐位取补，记为；密钥逐位取补，记为。若密文组为：

则有

式中，是Y的逐位取补。互补性特点是由DES加密算法中的两次异或运算决定的，一次是在S盒之前，另一次是在P置换之后。

DES加密算法存在弱密钥和半弱密钥。

DES加密算法每次迭代都有一个子密钥供加密使用，16次迭代子密钥分别为 K1, K2, …, K16，由初始密钥K生成。如果K通过子密钥发生器生成的K1, K2, …, K16都相同，则称密钥K为弱密钥，DES加密算法存在4个弱密钥。如果用初始密钥K对明文X进行2次加密或2次解密，都可恢复出明文（即加密运算与解密运算没有区别），则称这类密钥K为半弱密钥，即

DES加密算法存在6对半弱密钥。

弱密钥和半弱密钥是不安全的，属于禁用密钥。当采用随机途径生成密钥时，要检查并删除禁用密钥。