第四讲单钥体制二分组密码课件

36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。--拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。第四讲单钥体制二分组密码第四讲单钥体制二分组密码36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。--拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。第四讲单钥体制二分组密码第四讲单钥体制（二）——分组密码一、分组密码概述二、代换网络三、迭代分组密码四、DES五、IDEA六、其它重要分组密码七、分组密码运行模式八、分组密码的组合九、分组密码的分析十、AES2021/3/202第四讲单钥体制（二）——分组密码分组密码：单钥分组密码是许多系统安全的一个重要组成部分。分组密码易于构造拟随机数生成器、流密码、消息认证码(MAC)和杂凑函数等，还可进而成为消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组码可能提出多方面的要求，除了安全性外，还有运行速度、存储量(程序的长度、数据分组长度、高速缓存大小)、实现平台(硬、软件、芯片)、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折衷选择。内容：分组密码的基本概念、设计原理、工作原理、运行模式、以及一些标准算法，DES、IDEA、SAFERK-64、、RC-5、Twofish等。2021/3/20336、“不可能”这个字(法语是一个字)，只在愚人的字典中找得第四讲单钥体制二分组密码课件第四讲单钥体制二分组密码课件第四讲单钥体制二分组密码课件第四讲单钥体制二分组密码课件第四讲单钥体制（二）——分组密码

一、分组密码概述置换的选择由密钥k决定。所有可能置换构成一个对称群SYM(2n)，其中元素个数或密钥数为(4—1—4)例如n=64bit时,(264)!>10347380000000000000000>(1010)20为表示任一特定置换所需的二元数字位数为

log2(2n!)(n－1.44)2n=O(n2n)(bit)(4—1—5)即密钥长度达n2nbit，n=64时的值为64264=270

bit，DES的密钥仅为56bit，IDEA的密钥也不过为128bit。实用中的各种分组密码(如后面要介绍的DES、IDEA、RSA和背包体制等)所用的置换都不过是上述置换集中的一个很小的子集。2023/1/46第四讲单钥体制（二）——分组密码

一、分组密码概述置换的第四讲单钥体制（二）——分组密码

一、分组密码概述

分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。设计的算法应满足下述要求：(1)分组长度n要足够大，防止明文穷举攻击法奏效。(2)密钥量要足够大，尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。(3)由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。2023/1/47第四讲单钥体制（二）——分组密码

一、分组密码概述第四讲单钥体制（二）——分组密码

一、分组密码概述设计的算法应满足下述要求：(4)加密和解密运算简单，易于软件和硬件高速实现。(5)数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。(6)差错传播尽可能地小。

实现上述几点要求并不容易。首先，图8-1-1的代换网络的复杂性随分组长度n呈指数增大，常常会使设计变得复杂而难以控制和实现；实际中常常将n分成几个小段，分别设计各段的代换逻辑实现电路，采用并行操作达到总的分组长度n足够大，这将在下面讨论。其次，为了便于实现，实际中常常将较简单易于实现的密码系统进行组合，构成较复杂的、密钥量较大的密码系统。2023/1/48第四讲单钥体制（二）——分组密码

一、分组密码概述设计的算第四讲单钥体制（二）——分组密码

一、分组密码概述

Shannon曾提出了以下两种可能的组合方法：“概率加权和”的方法。设有r个子系统，以T1,T2,…,Tr表示，相应被选用的概率为p1,p2,…,pr，其中。其概率和系统可表示成T=p1T1+p2T2+…+prTr(4—1—6)显然，系统T的密钥量将是各子系统密钥量之和。“乘积”方法。设有两个子密码系统T1和T2，则先以T1对明文进行加密，然后再以T2对所得结果进行加密。其中，T1的密文空间需作为T2的“明文”空间。乘积密码可表示成

T=T1T2(4—1—7)利用这两种方法可将简单易于实现的密码组合成复杂的更为安全的密码。2023/1/49第四讲单钥体制（二）——分组密码

一、分组密码概述第四讲单钥体制（二）——分组密码二、代换网络代换网络。在密码学研究中，代换网络起着中心作用。明文和密文字母之间的双射变换可以由一个输入和输出字母表相同的代换网络实现。一个代换网络可看作是有n个多元输入和n个多元输出变量的黑盒子，其每个输出变量都是n个输入的布尔函数。代换网络的研究涉及电话交换、开关函数理论和密码学等多个领域。

代换是输入集A到输出A＇上的双射变换：

fk：AA＇(4—2—1)式中，k是控制输入变量，在密码学中则为密钥。实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。2023/1/410第四讲单钥体制（二）——分组密码二、代换网络代换网络。第四讲单钥体制（二）——分组密码

二、代换网络代换fk的集合：S={fkkK}(4—2—2)K是密钥空间。S完全表示了一个代换网络特性。如果网络可以实现所有可能的2n!个代换，则称其为全代换网络。显然，密钥个数必须满足条件：＃{k}2n!(4—2—3)密码设计中需要先定义代换集S，即确定加密用的代换网络，而后还需定义解密变换集，即逆代换网络S-1，它以密文y作为输入矢量，其输出为恢复的明文矢量x。如前所述，实用密码体制的集合S中的元素个数都远小于2n!。要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。2023/1/411第四讲单钥体制（二）——分组密码

二、代换网络代换fk的第四讲单钥体制（二）——分组密码

二、代换网络常用的基本代换有下述几种。1．左循环移位(Shiftleftcircular)

2．右循环移位(Shiftrightcircular)代换3．模2n加1(Additionwithmodule)代换4．线性变换(Lineartransformation)A5．换位(Transposition)代换6．连线交叉或坐标置换T7．仿射变换(Affinetransform)一般二元代换网络可用布尔函数描述。2023/1/412第四讲单钥体制（二）——分组密码

二、代换网络常用的基第四讲单钥体制（二）——分组密码二、代换网络代换盒：简称为S盒。在密码设计中，可选n=rn0，其中r和n0都为正整数，将设计n个变量的代换网络化为设计r个较小的子代换网络，而每个子代换网络只有n0个输入变量。称每个子代换网络为代换盒(SubstitutionBox)，例如，在DES的S盒

x5x4x3x2x1x0

S盒图4-2-3S盒

y3

y2

y1y0

2023/1/413第四讲单钥体制（二）——分组密码二、代换网络代换盒第四讲单钥体制（二）——分组密码

二、代换网络

DES的S盒设计经验表明，实现代换所需最小的逻辑单元电路(如小项)数目可作为排除弱(安全性差)盒函数的指标或直观依据。如果实现盒的逻辑函数的小项个数低于某个确定的阈值，其安全性就值得怀疑。对S盒提出的设计准则越严格，其逻辑表达式中的小项数就越大，最多可达64项(即所有可能达26个选取)。以DES体制中的8个S盒之一，即第一个S1－盒为例说明其输入输出之间的代换关系，参看图4-2-4。DES的S盒的最终设计，其小项表达式中的项数在55左右，比开始的增加了10项。从LSI设计角度出发，应使其尽可能在一个基片上实现。小项数越多，实现也就越复杂。有了小项表达式后，还要进行布尔式化简，以利于实现。2023/1/414第四讲单钥体制（二）——分组密码

二、代换网络第四讲单钥体制（二）——分组密码

二、代换网络图4-2-4DES的S1-盒的输入和输出关系x5x0x5x4x3x2x1x010101100

列号0123456789101112131415行号01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613(y3,

y2,

y1,

y0)=(0,0,1,0)2023/1/415第四讲单钥体制（二）——分组密码

二、代换网络图4-2-4第四讲单钥体制（二）——分组密码

二、代换网络根据什么准则设计S盒以保障安全性是一个复杂问题。迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则：P1S盒的输出都不是其输入的线性或仿射函数。P2

改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。P3

当S盒的任一输入位保持不变，其它5位输入变化时(共有25=32种情况)，输出数字中的0和1的总数近于相等。这三点使DES的S盒能够实现较好的混淆。2023/1/416第四讲单钥体制（二）——分组密码

二、代换网络第四讲单钥体制（二）——分组密码

二、代换网络当S盒设计之后，下一个问题是如何将几个S盒组合起来构成一个n值较大的组。一般是将几个S盒的输入端并行，并通过坐标置换(P-盒)将各S盒输出比特次序打乱，再送到下一级各S盒的输入端，起到了Shannon所谓的“扩散”作用。S盒提供非线性变换，将来自上一级不同的S盒的输出进行“混淆”。例如，对于重量为1的输入矢量，经过S盒的混淆作用使1的个数增加，经过P-盒的扩散作用使1均匀地分散到整个输出矢量中，从而保证了输出密文统计上的均匀性，这就是Shannon的乘积密码的作用。这种用S盒和P-盒交替在密钥控制下组成的复杂的、分组长度n足够大的密码设计方法是由IBM的研究人员根据Shannon思想提出的，最初在LUCIFER密码系统中实现，选用n=128，n0=4，后发展成为DES。2023/1/417第四讲单钥体制（二）——分组密码

二、代换网络第四讲单钥体制（二）——分组密码二、代换网络

Feistel网络：Feistel提出，将nbit明文分成为左右各半、长为n/2bit的段，以L和R表示。然后进行多轮迭代，其第i轮迭代的输出为前轮输出的函数

Li=Ri-1

Ri=Li-1f(Ri-1,Ki)式中，Ki是第i轮用的子密钥，f是任意密码轮函数。称这种分组密码算法为Feistel网络（FeistelNetwork），它保证加密和解密可采用同一算法实施，因而被广泛用于多种分组密码体制中。在设计整个分组密码的代换网络时，要求输出的每比特密文都和输入的明文及密钥各比特有关，这对增加密码强度有好处。2023/1/418第四讲单钥体制（二）——分组密码二、代换网络Feist第四讲单钥体制（二）——分组密码

三、迭代分组密码

迭代分组密码

迭代密码：若以一个简单函数f，进行多次迭代，如图4-3-1所示，就称其为迭代密码。每次迭代称作一轮(Round)。相应函数f称作轮函数。每一轮输出都是前一轮输出的函数，即y(i)=f[y(i-1),

k(i)]，其中k(i)是第i轮迭代用的子密钥，由秘密密钥k通过密钥生成算法(产生。DES为16轮，IDEA为8轮。

y(0)=x

y(1)

y(2)

y(r-1)

y(r)=y图4-3-1以轮函数f

f

f

f构造的r轮迭代密码k(1)

k(2)

k(r)

子密钥产生器

k2023/1/419第四讲单钥体制（二）——分组密码

三、迭代分组密码迭第四讲单钥体制（二）——分组密码

三、迭代分组密码

对合密码(InvolutionCipher)。它是加密所用的一种加密函数f(x,k)，实现F2n×F2t

F2n的映射。其中，n是分组长，t是密钥长。若对每个密钥取值都有f[f(x,

k)，k]=x，即f(x,

k)2=I(恒等置换)(4—3—1)则称其为对合密码，以fI表示。

I型迭代分组密码:以对合密码函数构造的多轮迭代分组密码。显然，对合加密函数fI，在子密钥k(1)，...，k(r)控制下对明文x进行r轮迭代加密运算E(x,k)得到密文y；而以密码函数fI在逆序子密钥k(r)，…，k(1)作用下，进行r轮迭代运算，就给出恢复的明文x。后r轮运算就作为解密运算D(y,

k)。即有D[E[x,

k]，k]=fI[fI[x,

k]，k]=fI

2[x,

k]=I[x]=x

(4—3—2)2023/1/420第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码

其中

E[x,

k]=fI[fI[

fI[fI[x,

k(1)]，k(2)]，k(r-1)]，k(r)](4—3—3)D[y,

k]=fI[fI[

fI[fI[y,

k(r)]，k(r-1)]，k(2)]，k(1)](4—3—4)

缺点：对任意偶数轮变换，若对所有i选择k(2i-1)=k(2i)，则加密的变换等价于恒等变换，在实用中需要避免这类密钥选择。对合置换：令P是对x的置换，即P：F2n

F2n

，若对所有xGF(2n)，有P[P[x]]=x，即PP=I(恒等置换)，以PI表示。II型迭代分组密码：每轮采用对合密码函数和对合置换级连，即F[x,

k]＝PI[fI

[x,

k]](4—3—5)并选解密子密钥与加密子密钥逆序，则加密解密可用同一器件完成。DES、FEAL和LOKI等都属此类。2023/1/421第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码群密码：若密钥与明文、密文取自同一空间GF(2n)，且y=xk

(4—3—6)式中，是群运算，则称其为群密码。显然x可通过k的逆元求得x=yk-1(4—3—7)III型迭代分组密码：令xk为一群密码，令fI(x,

kB)为一对合密码，以F[x,

k]＝fI(xkA,kB)(4—3—8)为迭代函数，可以构造一种新的多轮迭代分组密码，如图4-3-2所示。注意，在最后一轮中，另外加了一次群密码运算，用以保证整个加、解密的对合性。2023/1/422第四讲单钥体制（二）——分组密码

三、迭代分组密码群密码第四讲单钥体制（二）——分组密码

三、迭代分组密码轮函数F

F

y(1)y(r-1)(a)加密

x

fI···

fI

y

kA(1)kB(1)kA(r)kB(r)kA(r+1)F

F

y

fI···fI

x

(b)解密

kA(r+1))-1

kB(r)(kA(r))-1

kB(1)(kA)-1

图4-3-2型迭代分组密码2023/1/423第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码

IV型迭代分组密码：

显然，若以

kA(1),kB(1),kA(2),kB(2),…,kA(r),kB(r),kA(r+1)作为加密子密钥，以(kA(r+1))-1,kB(r),(kA(r))-1,kB(r-1),···,(kA(2))-1,kB(1),(kA(1))-1为解密钥，则加、解密类似，可用同一器件实现。PES(ProposalBlockEncryptionStandard)属此类。

在这类密码的轮函数基础上，再增加一个对合置换PI，构成IV型迭代分组密码的轮函数

F[x,

k]＝PI[fI[xkA,kB]](4—3—9)2023/1/424第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码轮函数F

y(1)y(r-1)

F

x

fIPI···

fI

PIPI

y

kA(1)kB(1)

kA(r)

kB(r)

kA(r+1)a)加密

FF

y

fIPI···

fI

x

(b)解密(kA(r+1))-1kB(r)

PI[kA(r)]-1

PI[kA(2)]-1

kB(1)(kA(1))-1图4-3-3型迭代分组密码2023/1/425第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码在最后一轮迭代后，附加了一次对合置换和群密码运算，IDEA属此类，关于它的对合性将在§4.5中讨论。现有大多数分组密码都属于迭代分组密码，迭代分组密码的核心是轮函数F，或称之为Feistel网络。轮函数的基础是对合函数fI的选择以及和其它变换的有机地结合。大多数分组密码的非线性主要依赖于对合函数fI中的S盒的非线性，S盒的强度在很大程度上决定了分组密码的强度，S盒的运行速度也在很大程度上决定了算法的运行速度，因此S盒的设计是迭代分组密码算法成功的关键。DES出现后人们对S盒的研究极为重视，因为它既可以强化密码，又可以设置“机关”，为设计者提供一个很好的舞台。但是设计一个好的S盒决非易事。2023/1/426第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码

好的S盒其布尔函数应满足以下一些基本条件(1)平衡性(Balance)。函数f:Z2nZ2，当输入取遍所有可能值，若输出为0的数目等于为1的数目就称函数f满足平衡性准则。一般对f:Z2nZ2m,nm，当输入取遍所有可能值，若每一输出图样y=f(x)Z2m出现次数相等，即为2

n-m次时，称f满足平衡准则。(2)严格雪崩准则(SAC—StrictAvalancheCriterion)。函数f:Z2nZ2，若输入任一位取补，其输出位将以概率1/2取补则称f满足SAC。(3)高阶SAC。函数f:Z2nZ2，若使f任意k个输入位保持不变下所得到的任意函数都满足SAC，则称f满足k阶SAC。2023/1/427第四讲单钥体制（二）——分组密码

三、迭代分组密码好第四讲单钥体制（二）——分组密码

三、迭代分组密码

好的S盒其布尔函数应满足以下一些基本条件

(4)非线性性(Nonlinearily)。函数f:Z2nZ2，若对常数aZ2n，f(x)=a·x，则称f为线性函数，而f(x)=a·xb为仿射函数，其中常数bZ2n。

对函数f=(f1

f2…fm)：Z2nZ2m，fi:Z2nZ2，i=1,…,n。其非线性度定义为其wZ2n，cZ2m\{0}，bZ2，w·x表示GF(2)上w与x的点积，且式中，c=(c1

c2,…cm)=Z2m。

f

的非线性度就是仿射函数集和f的输出坐标的每个非零线性组合之间的最小Hamming距离。

2023/1/428第四讲单钥体制（二）——分组密码

三、迭代分组密码好

好的S盒其布尔函数应满足以下一些基本条件

(5)线性结构。函数f:Z2nZ2，的线性结构定义为一个矢量aZ2n/{0}，使对所有xZ2n，f(xa)f(x)取同样值(0或1)。(6)输出bit独立准则。函数f:Z2nZ2m，当一个输入bit取补时，每二个输出bit之间的相关系数变为0，则称f满足BIC(BitIndependenceCriterion)。(7)完备性。函数f:Z2nZ2m，若其每个输出bit都与所有输入变量有关，就称f满足完备性准则。(8)输入/输出的差分分布。最初曾追求均匀，后来发现应使差分最大值尽量小为好。抗差分攻击能力请参看§4.5。(9)线性近似和抗线性攻击能力。第四讲单钥体制（二）——分组密码三、迭代分组密码2023/1/429好的S盒其布尔函数应满足以下一些基本条件第四讲单钥体制第四讲单钥体制（二）——分组密码

三、迭代分组密码按一定的准则构造的S盒肯定可以抗击现有已知的各种攻击，但对于尚未提出的攻击是否能抗？这是难于定论的事，DES的S盒曾为抗差分攻击进行最佳化设计，但后来发现，它对抗线性攻击的能力不够强。因此有人提出，采用随机选择的S盒也许是更好的方法。当然，如果S盒的输入和输出的规模太小，随机选择S盒的性能肯定不会好。但当S盒的输入和输出的规模足够大时，就很可能不仅能抗击各种已知的攻击，而且很可能也能抗击未知的攻击。研究表明，输入为8bit或更大的随机选择的S盒的密码性能是相当强的。S盒应选得尽可能地大些、随机且可用密钥控制。以随机方式生成S盒，经过一组准则测试，具有好的性质代数构造或组合这类方法是构造S盒的途经。2023/1/430第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

三、迭代分组密码现有的大多数分组密码是采用S盒结构实现的，而且所用的S盒是固定的，如DES、CAST、FEAL、SAFERK-64等。有些方案所用的S盒可以在密钥控制下动态地改变，如IDEA、Blowfish、RC-4，以及Ritter提出的动态代换[Ritter1997]。S盒的实现需要较多的存储空间以存储S盒。也有用代换-置换网络或其它技术而不采用S盒的分组密码。如RC-5、TEA，其轮函数由简单的固定逻辑移位运算或由数据相依旋转构成。

2023/1/431第四讲单钥体制（二）——分组密码

三、迭代分组密码第四讲单钥体制（二）——分组密码

四、DES美国数据加密标准——DES（DataEncryptionStandard）。1.美国制定数据加密标准简况

通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。

美国NBS在1973年5月15公布了征求建议。1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求：（1）算法必须完全确定而无含糊之处；（2）算法必须有足够高的保护水准，即可以检测到威胁，恢复密钥所必须的运算时间或运算次数足够大；（3）保护方法必须只依赖于密钥的保密；（4）对任何用户或产品供应者必须是不加区分的。2023/1/432第四讲单钥体制（二）——分组密码

四、DES美国第四讲单钥体制（二）——分组密码

四、DES，标准简况

IBM公司从60年代末即看到通信网对于这种加密标准算法的需求，投入了相当的研究力量开发，成立了以Tuchman博士为领导的小组，包括A.Konkeim,E.Grossman,N.Coppersmith和L.Smith等(后二人做实现工作)的研究新密码体制的小组，H.Fistel进行设计，并在1971年完成的LUCIFER密码(64bit分组，代换-置换，128bit密钥)的基础上，改进成为建议的DES体制。NSA组织有关专家对IBM的算法进行了鉴定，而成为DES的基础。

1975年3月17日NBS公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。1977年1月15日建议被批准为联邦标准[FIPSPUB46]，并设计推出DES芯片。DES开始在银行、金融界广泛应用。1981年美国ANSI将其作为标准，称之为DEA[ANSIX3.92]。1983年国际标准化组织(ISO)采用它作为标准，称作DEA-1。

2023/1/433第四讲单钥体制（二）——分组密码

四、DES，标准简况第四讲单钥体制（二）——分组密码

四、DES，标准简况

1984年9美国总统签署145号国家安全决策令(NSDD)，命令NSA着手发展新的加密标准，用于政府系统非机密数据和私人企事业单位。NSA宣布每隔5年重新审议DES是否继续作为联邦标准，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批准DES为联邦标准。

虽然DES不会长期地作为数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。因此，详细地研究这一算法的基本原理、设计思想、安全性分析以及实际应用中的有关问题，对于掌握分组密码理论和当前的实际应用都是很有意义的。1993年4月，Clinton政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准EES(EscrowedEncryptionStandard)。其开发设计始于1985年，由NSA负责研究。1990年完成评价工作。其算法为SKIPJACK。已由Mykotronix公司开发芯片产品，编程后为MYK-78(26美元/片)。算法属美国政府SECRET密级。但安全性与算法是否公开无关。2023/1/434第四讲单钥体制（二）——分组密码

四、DES，标准简况第四讲单钥体制（二）——分组密码

四、DES，标准简况

DES发展史确定了发展公用标准算法模式，而EES的制定路线与DES的背道而驰。虽然由美国政府精心选定的五人小组评估意见，不能解除人们对算法安全性的疑虑。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对，1995年5月AT&TBellLab的M.Blaze博士在PC机上用45分钟时间使SKIPJACK的LEAF协议失败，伪造ID码获得成功。虽NSA声称已弥补，但丧失了公众对此体制的信心。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。

重新回到制定DES标准立场。1997年1月美国NIST着手进行AES（AdvancedEncryptionStandard）的研究，成立了标准工作室。1997年4月15日讨论了AES的评估标准，开始在世界范围征集AES的建议算法，截止时间为1998年6月15日。1998年8月20~22日经评审选定并公布了15个候选算法。1999年3月经评审筛选出5个算法,2001：2023/1/435第四讲单钥体制（二）——分组密码

四、DES，标准简况第四讲单钥体制（二）——分组密码

四、DES，算法

算法：分组长度为64bits(8bytes)，密文分组长度也是64bits。密钥长度为64bits，有8bits奇偶校验，有效密钥长度为56bits。算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。

初始置换IP：将64bit明文的位置进行置换，得到一个乱序的64bit明文组，而后分成左右两段，每段为32bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。

逆初始置换IP-1。将16轮迭代后给出的64bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。2023/1/436第四讲单钥体制（二）——分组密码

四、DES，算法第四讲单钥体制（二）——分组密码

四、DES，算法

输入64bit明文数据初始置换IP乘积变换（16轮迭代）逆初始置换IP-164bit密文数据输出图4-4-1DES算法框图标准数据加密算法2023/1/437第四讲单钥体制（二）——分组密码

四、DES，算法第四讲单钥体制（二）——分组密码

四、DES，算法

IP和IP-1在密码意义上作用不大，因为输入组x与其输出组y=IP(x)(或IP-1(x))是已知的一一对应关系。它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8,x16,,x64变成为IP输出的一个字节。

乘积变换。图4-4-4中给出乘积变换的框图，它是DES算法的核心部分。将经过IP置换后的数据分成32bit的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的32bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32bit与右边得到的32bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。2023/1/438第四讲单钥体制（二）——分组密码

四、DES，算法

Li-1(32bit)Ri-1(32bit)

选择扩展运算E48bit寄存器按bit模2加密48bit寄存器选择压缩运算S32bit寄存器置换运算P按bit模2和

Li(32bit)Ri(32bit)图4-4-4乘积变换框图密钥产生器2023/1/439密钥产生器2022/12/1139第四讲单钥体制（二）——分组密码

四、DES，算法

选择扩展运算E。将输入的32bitRi-1扩展成48bit的输出，其变换表在图4-4-5中给出。令s表示E原输入数据比特的原下标，则E的输出是将原下标s0或1(mod4)的各比特重复一次得到的，即对原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重复一次,实现数据扩展。将表中数据按行读出得到48bit输出。

密钥加密运算。将子密钥产生器输出的48bit子密钥ki与选择扩展运算E输出的48bits数据按位模2相加。

选择压缩运算S。将前面送来的48bit数据自左至右分成8组，每组为6bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出，如§4-1中所述。盒S1至S8的选择函数关系如表4-4-1所示。运算S的框图在图4-4-6中给出。

p.186

图4-4-6选择压缩运算S

置换运算P。对S1至S8盒输出的32bit数据进行坐标置换，如图4-4-7所示。置换P输出的32bit数据与左边32bit即Ri-1逐位模2相加，所得到的32bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。子密钥产生器。将64bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki，参看图4-4-8。在64bit初始密钥中有8位为校验位，其位置号为8、16、32、48、56和64。其余56位为有效位，用于子密钥计算。将这56位送入置换选择PC1，参看图4-4-9。经过坐标置换后分成两组，每级为28bit，分别送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分别将存数进行左循环移位置换，移位次数在表4-4-2中给出。每次移位后，将C和D寄存器原存数送给置换选择PC2，见图4-4-10。置换选择PC2将C中第9、18、22、25位和D中第7、9、15、26位删去，并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥ki。p.186p.186

图4-4-7置换运算P

图4-4-8子密钥产生器框图

表4-4-2移位次数表第i次迭代12345678910111213141516循环左移次数1122222212222221

p.187

图4-4-9置换选择PC1

至此，我们已将DES算法的基本构成作了介绍，加密过程可归结如下：令IP表示初始置换，KS表示密钥运算，i为迭代次数变量，KEY为64bit密钥，f为加密函数，表示逐位模2求和。2023/1/440第四讲单钥体制（二）——分组密码

四、DES，算法选第四讲单钥体制（二）——分组密码

四、DES，算法

6bit选择函数组4bit

图4-4-6选择压缩运算S

48bit寄存器32bit寄存器S1S2S3S4S5S6S7S82023/1/441第四讲单钥体制（二）——分组密码

四、DES，算法第四讲单钥体制（二）——分组密码

四、DES，算法

置换运算P。对S1至S8盒输出的32bit数据进行坐标置换，如图4-4-7所示。置换P输出的32bit数据与左边32bit即Ri-1逐位模2相加，所得到的32bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。

子密钥产生器。将64bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki，参看图4-4-8。在64bit初始密钥中有8位为校验位，其位置号为8、16、32、48、56和64。其余56位为有效位，用于子密钥计算。将这56位送入置换选择PC1，参看图4-4-9。经过坐标置换后分成两组，每级为28bit，分别送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分别将存数进行左循环移位置换，移位次数在表4-4-2中给出。每次移位后，将C和D寄存器原存数送给置换选择PC2，见图4-4-10。置换选择PC2将C中第9、18、22、25位和D中第7、9、15、26位删去，并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥ki。2023/1/442第四讲单钥体制（二）——分组密码

四、DES，算法第四讲单钥体制（二）——分组密码

四、DES，算法

密钥（64bit）置换选择1，PC1置换选择2，PC2

Ci(28bit)

Di(28bit)循环左移ti+1bit循环左移ti+1bit除去第8,16,,64位(8个校验位)ki图4-4-8子密钥产生器框图2023/1/443第四讲单钥体制（二）——分组密码

四、DES，算法第四讲单钥体制（二）——分组密码

四、DES，算法表4-4-2移位次数表第i次迭代12345678910111213141516循环左移次数1122222212222221

至此，我们已将DES算法的基本构成作了介绍，加密过程可归结如下：令IP表示初始置换，KS表示密钥运算，i为迭代次数变量，KEY为64bit密钥，f为加密函数，表示逐位模2求和。

2023/1/444第四讲单钥体制（二）——分组密码

第四讲单钥体制（二）——分组密码

四、DES，算法加密过程:式(4-4-1)和式(4-4-2)的运算进行16次后就得到密文组。

L0R0IP(〈64bit输入码〉)

LiRi-1i=1,...,16(4—4—1)

RiLi-1f(Ri-1,

ki)i=1,...,16(4—4—2)〈64bit密文〉IP-1(R16L16)解密过程:DES的加密运算是可逆的，其解密过程可类似地进行。

R16L16IP(〈64bit密文〉)

Ri-1Lii=16,...,1(4—4—3)

Li-1Rif(Li-1,ki)i=16,...,1(4—4—4)〈64bit明文〉IP-1(R0L0)

2023/1/445第四讲单钥体制（二）——分组密码第四讲单钥体制（二）——分组密码

四、DES，算法DES算法的可逆性证明：令T(L,Ｒ)＝(R,L)(4—4—5)即T是将64bit组的左、右半边交换位置。并令

Fk1(L,Ｒ)＝(Lf(R,ki),Ｒ)(4—4—6)则第i次迭代实现的变换为Tki=TFki(4—4—7)这是因为TFki(L,Ｒ)=T(Lf(R,ki),Ｒ)=(L,Ｒf(R,ki))因为T2(L,Ｒ)=T(Ｒ,L)=I(L,Ｒ)(4—4—8)式中，I是恒等变换，所以有T=T-1(4—4—9)同样有Fki2(L,Ｒ)=Fki(Lf(R,ki),Ｒ)=(Lf(R,ki)f(R,ki),Ｒ)=(L,Ｒ)即Fki2=I(4—4—10)2023/1/446第四讲单钥体制（二）——分组密码四、DES，算法DES第四讲单钥体制（二）——分组密码

四、DES，算法或Fki=Fki-1(4—4—11)我们称T和Fki这类换为对合(Involution)变换，其逆变换就是它自己。因为(FkiT)(TFki)=FkiFki=I(4—4—12)所以有(TFki)-1=FkiT(4—4—13)由此可知在密钥k作用下的DES加密过程可写成

DESk=(IP-1)FK16TFK15T···FK2TFK1(IP)(4—4—14)解密过程可写成

DESk-1=(IP-1)FK1TFK2T···FK15TFK16(IP)(4—4—15)因而可证得(DESk-1)(DESk)=I(4—4—16)2023/1/447第四讲单钥体制（二）——分组密码四、DES，算法或第四讲单钥体制（二）——分组密码

四、DES，安全性安全性DES的安全性完全依赖于所用的密钥。从DES诞生起，对它的安全性就有激烈的争论，一直延续到现在。。互补性。DES算法具有下述性质。若明文组x逐位取补，密钥k逐位取补，且y=DESk(x)(4—4—17)则有(4—4—18)式中，是y的逐位取补。称这种特性为算法上的互补性。这种互补性会使DES在选择明文破译下所需的工作量减半。弱密钥和半弱密钥。DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有

k1=k2=…=k16(4—4—19)就称给定密钥k为弱密钥(Weakkey)。2023/1/448第四讲单钥体制（二）——分组密码四、DES，安全性安全第四讲单钥体制（二）——分组密码四、DES，安全性若k为弱密钥，则有

DESk(DESk(x))=x

(4—4—20)DESk-1(DESk-1(x))=x(4—4—21)即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。而对一般密钥只满足

DESk-1(DESk(x))=DESk(DESk-1(x))=x(4—4—22)弱密钥下使DES在选择明文攻击下的搜索量减半。如果随机地选择密钥，则在总数256个密钥中，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。2023/1/449第四讲单钥体制（二）——分组密码四、DES，安全性若k第四讲单钥体制（二）——分组密码

四、DES，安全性密文与明文、密文与密钥的相关性。Meyer[1978]详细研究了DES的输入明文与密文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出达到这一要求所需的迭代次数至少为5。Konheim[1981]用2检验证明，迭代8次后输出和输入就可认为是不相关的了。S盒设计。DES靠S盒实现非线性变换。密钥搜索机。对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112bits密钥，但公布的DES标准采用64bits密钥。有人认为NSA故意限制DES的密钥长度。2023/1/450第四讲单钥体制（二）——分组密码

四、DES，安全性密第四讲单钥体制（二）——分组密码四、DES，安全性

DES的密钥量为256=7.2×1016=720575940379279361017个。若要对DES进行密钥搜索破译，分析者在得到一组明文-密文对条件下，可对明文用不同的密钥加密，直到得到的密文与已知的明文-密文对中的相符，就可确定所用的密钥了。密钥搜索所需的时间取决于密钥空间的大小和执行一次加密所需的时间。若假定DES加密操作需时为100s(一般微处理器能实现)，则搜索整个密钥空间需时为7.2×1015秒，近似为2.28×108年。若以最快的LSI器件，DES加密操作时间可降到5s，也要1.1×104年才能穷尽密钥。但是由于差分和线性攻击法的出现以及计算技术的发展，按Wiener介绍，在1993年破译DES的费用为100万美元，需时3个半小时。如果将密钥加大到80bits，采用这类搜索机找出一个密钥所需的时间约为6700年。

2023/1/451第四讲单钥体制（二）——分组密码四、DES，安全性第四讲单钥体制（二）——分组密码四、DES，安全性

RSA数据安全公司提供10000美元奖金。现已被DESCHALL小组经过近四个月的努力，通过Internet搜索了3×1016个密钥，找出了DES的密钥，恢复出明文。1998年5月美国EFF(ElectronicFrontierFoundation)宣布，他们以一台价值20万美元的计算机改装成的专用解