第3讲_对称密钥密码体制

1、1第第3讲讲对称密钥密码体制对称密钥密码体制按加解密采用的密钥不同按加解密采用的密钥不同按密码出现的时间不同按密码出现的时间不同古典密码古典密码现代密码现代密码密码学密码学（Cryptology）(Symmetric cipher)(Asymmetric cipher)分组密码分组密码流密码流密码公钥密码公钥密码按加密的方式按加密的方式对称密码对称密码非对称密码非对称密码(Classical cipher)(Modern cipher)(Block cipher)(Stream cipher)(Public-Key cipher)什么是流密码什么是流密码一次一密：指在流密码当中使用与消息长度等

2、长的随机密钥一次一密：指在流密码当中使用与消息长度等长的随机密钥, , 密钥本身只使用一次密钥本身只使用一次流密码的研究现状流密码的研究现状 当前对流密码的研究主要集中在以下两个方向：当前对流密码的研究主要集中在以下两个方向：（1 1）什么样的序列可以作为安全可靠的密钥序列？即衡量密什么样的序列可以作为安全可靠的密钥序列？即衡量密钥流序列好坏的标准。钥流序列好坏的标准。（2 2）如何构造线性复杂度高、周期大的密钥流序列？如何构造线性复杂度高、周期大的密钥流序列？ 在保密强度要求高的场合如大量军事密码系统，仍多采用在保密强度要求高的场合如大量军事密码系统，仍多采用流密码，美军的核心密码仍是流密码

3、，美军的核心密码仍是“一次一密一次一密”的的流密码体制流密码体制。鉴。鉴于流密码的分析和设计在军事和外交保密通信中有重要价值，于流密码的分析和设计在军事和外交保密通信中有重要价值，流密码的设计基本上都是保密的流密码的设计基本上都是保密的，国内外少有专门论述流密码，国内外少有专门论述流密码学的著作，公开的文献也不多。尽管如此，由于流密码长度可学的著作，公开的文献也不多。尽管如此，由于流密码长度可灵活变化，且具有运算速度快、密文传输中没有差错或只有有灵活变化，且具有运算速度快、密文传输中没有差错或只有有限的错误传播等优点，目前仍是国际密码应用的主流，而基于限的错误传播等优点，目前仍是国际密码应用的

4、主流，而基于伪随机序列的流密码是当今最通用的密码系统。伪随机序列的流密码是当今最通用的密码系统。流密码的研究现状流密码的研究现状3.1 流密码流密码v在流密码中，将明文消息按一定长度分组（长度较小，通常按在流密码中，将明文消息按一定长度分组（长度较小，通常按字或字节），然后对各组用相关但不同的密钥进行加密，产生字或字节），然后对各组用相关但不同的密钥进行加密，产生相应的密文，相同的明文分组会因在明文序列中的位置不同而相应的密文，相同的明文分组会因在明文序列中的位置不同而对应于不同的密文分组。对应于不同的密文分组。v相对分组密码而言，流密码主要有以下优点：相对分组密码而言，流密码主要有以下优点：

5、第一，在硬件实施上，流密码的速度一般要比分组密码快，而且不需第一，在硬件实施上，流密码的速度一般要比分组密码快，而且不需要有很复杂的硬件电路：要有很复杂的硬件电路：第二，在某些情况下（例如对某些电信上的应用），当缓冲不足或必第二，在某些情况下（例如对某些电信上的应用），当缓冲不足或必须对收到的字符进行逐一处理时，流密码就显得更加必要和恰当；须对收到的字符进行逐一处理时，流密码就显得更加必要和恰当；第三，流密码能较好地隐藏明文的统计特征等。第三，流密码能较好地隐藏明文的统计特征等。流密码的原理流密码的原理v在流密码中，明文按一定长度分组后被表示成一个序列，并在流密码中，明文按一定长度分组后被表示

6、成一个序列，并称为称为明文流明文流，序列中的一项称为一个，序列中的一项称为一个明文字明文字。加密时，先由。加密时，先由主密钥产生一个密钥流序列，该序列的每一项和明文字具有主密钥产生一个密钥流序列，该序列的每一项和明文字具有相同的比特长度，称为一个相同的比特长度，称为一个密钥字密钥字。然后依次把明文流和密。然后依次把明文流和密钥流中的对应项输入加密函数，产生相应的钥流中的对应项输入加密函数，产生相应的密文字密文字，由密文，由密文字构成密文流输出。即字构成密文流输出。即 设明文流为：设明文流为：M=m1 m2mi 密钥流为：密钥流为：K=k1 k2ki 则加密为：则加密为：C=c1 c2ci=Ek

7、1(m1)Ek2(m2)Eki(mi) 解密为：解密为：M=m1 m2mi=Dk1(c1)Dk2(c2)Dki(ci)流密码通信模式框图流密码通信模式框图加密算法加密算法E密文密文ci=Ek(mi)解密算法解密算法D明文明文mi=Dk(ci)明文明文mi密钥密钥ki密钥密钥ki流密码的原理流密码的原理例例 设明文、密钥、密文都是设明文、密钥、密文都是F2上的二元数字序列，明文上的二元数字序列，明文m=m1m2，密钥为，密钥为k=k1k2，若加密变换与解密变换都是，若加密变换与解密变换都是F2中的模中的模2加法，试写出加密过程与加法，试写出加密过程与解密过程。解密过程。 解解 经加密变换得密文：

8、经加密变换得密文： C = Ek (m) = Ek1(m1)Ek2(m2) = (k1+m1) (k2+m2) 经解密变换得：经解密变换得： Dk (C) = Dk (k1+m1)(k2+m2) = (k1+k1+m1)(k2+k2+m2) 由于由于kiF2，则，则 ki+ki=0，i=1,2,，故，故 Dk (C)= m1m2 = m 。 v 密文密文C 可由明文可由明文m与密钥与密钥k进行进行模模2加加获得。因此要用该密码系统通信就要获得。因此要用该密码系统通信就要求每发送一条消息都要产生一个新的密钥并在一个安全的信道上传送，习求每发送一条消息都要产生一个新的密钥并在一个安全的信道上传送，

9、习惯上人们称这种通信系统为惯上人们称这种通信系统为“一次一密系统一次一密系统”。流密码的时变性流密码的时变性-随时间而变化随时间而变化 流流密码采用了类似于一次一密的思想，但加密各明文字的密钥密码采用了类似于一次一密的思想，但加密各明文字的密钥字不是独立随机选取的，而是由一个共同的较短的主密钥按一个算字不是独立随机选取的，而是由一个共同的较短的主密钥按一个算法产生的。因此，它不具有一次一密的无条件安全性，但增加了实法产生的。因此，它不具有一次一密的无条件安全性，但增加了实用性，只要算法设计得当，其安全性可以满足实际应用的需要。用性，只要算法设计得当，其安全性可以满足实际应用的需要。 密密钥流中

10、的元素的产生由钥流中的元素的产生由 i 时刻的流密码内部状态（记作时刻的流密码内部状态（记作 ）和种子密钥（记作和种子密钥（记作k）决定）决定 ，即，即 ；加密变换；加密变换 与解与解密变换密变换 也和也和 i 时刻的流密码内部状态有关。时刻的流密码内部状态有关。 i),(iikfkikEikD流密码分类流密码分类v 用状态转移函数用状态转移函数 描述流密码加密器中存储器的状态随时间变化描述流密码加密器中存储器的状态随时间变化的过程。的过程。 同步流密码同步流密码 ：如果某个流密码中的状态转移函数：如果某个流密码中的状态转移函数 不依赖被不依赖被输入加密器存储器的明文，即密钥流的生成独立于明文

11、流和密输入加密器存储器的明文，即密钥流的生成独立于明文流和密文流的流密码称为同步流密码。文流的流密码称为同步流密码。使用最广泛。使用最广泛。自同步流密码自同步流密码也叫异步流密码也叫异步流密码 ：状态转移函数：状态转移函数 与输入明文与输入明文有关，即其中密钥流的产生并不是独立于明文流和密文流的。有关，即其中密钥流的产生并不是独立于明文流和密文流的。通常第通常第i个密钥字的产生不仅与主密钥有关，而且与前面已经产个密钥字的产生不仅与主密钥有关，而且与前面已经产生的若干个密文字（与明文字）有关。生的若干个密文字（与明文字）有关。sfsfsf加密算法加密算法E密钥流密钥流发生器发生器解密算法解密算法

12、D密钥流密钥流发生器发生器安全通道安全通道密钥密钥 k密文流密文流 c i密钥流密钥流 k i密钥流密钥流 k i明文流明文流m i明文流明文流m i图图1 同步流密码模型同步流密码模型内部状态内部状态输出函数输出函数内部状态内部状态输出函数输出函数密钥发生器密钥发生器密钥发生器密钥发生器明文流明文流 m i密文流密文流 c i明文流明文流 m i种子种子 k种子种子 kkk图图2 自同步流密码模型自同步流密码模型同步流密码同步流密码中，消息的发送者和接收者必须同步才能做到正确中，消息的发送者和接收者必须同步才能做到正确地加密解密，即双方使用相同的密钥，并用其对同一位置进行地加密解密，即双方使

13、用相同的密钥，并用其对同一位置进行操作。一旦由于密文字符在传输过程中被插入或删除而破坏了操作。一旦由于密文字符在传输过程中被插入或删除而破坏了这种同步性，那么解密工作将失败。否则，需要在密码系统中这种同步性，那么解密工作将失败。否则，需要在密码系统中采用能够建立密钥流同步的辅助性方法。采用能够建立密钥流同步的辅助性方法。分解后的同步流密码分解后的同步流密码密钥流生成器密钥流生成器v密钥流生成器设计中，在考虑安全性要求的前提下还应考虑密钥流生成器设计中，在考虑安全性要求的前提下还应考虑以下两个因素：以下两个因素： 密钥密钥k易于分配、保管、易于分配、保管、更换更换简单；简单；易于实现，快速易于实

14、现，快速。v目前密钥流生成器大都是基于移位寄存器的。因为移位寄存目前密钥流生成器大都是基于移位寄存器的。因为移位寄存器结构简单，易于实现且运行速度快。这种基于移位寄存器器结构简单，易于实现且运行速度快。这种基于移位寄存器的密钥流序列称为移位寄存器序列。的密钥流序列称为移位寄存器序列。密钥流生成器密钥流生成器v一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数, , 构构成一个成一个密钥流生成器密钥流生成器。 每次输出一位，移位寄存器中所有位都右每次输出一位，移位寄存器中所有位都右移一位，新的最左端的位根据寄存器中其它位计算得到。移位寄移一位

15、，新的最左端的位根据寄存器中其它位计算得到。移位寄存器输出的一位常常是最低有效位。存器输出的一位常常是最低有效位。v移位寄存器的周期是指输出序列从开始到重复时的长度。移位寄存器的周期是指输出序列从开始到重复时的长度。v这种方法通过一个种子（有限长）产生具有足够长周期的、随机这种方法通过一个种子（有限长）产生具有足够长周期的、随机性良好的序列。只要生成方法和种子都相同，就会产生完全相同性良好的序列。只要生成方法和种子都相同，就会产生完全相同的密钥流。的密钥流。反馈函数反馈函数 0,11jacaninjinj若若 ，则该，则该LFSR生成的序列为周期序列。生成的序列为周期序列。 0nc又称为又称为

16、n阶线性递归关系阶线性递归关系密钥流生成器密钥流生成器v最简单的反馈移位寄存器是线性移位寄存器（最简单的反馈移位寄存器是线性移位寄存器（LFSR），反），反馈函数是寄存器中某些位的简单异或。如教材馈函数是寄存器中某些位的简单异或。如教材P64图图4.5。v异或异或(XOR)运算，异或密文和相同的密钥流就可以完成解密运算，异或密文和相同的密钥流就可以完成解密操作。操作。v流密码基于流密码基于XOR运算具有下列属性：如果运算具有下列属性：如果B=A K，那么，那么A=B K。vn 级移位寄存器级移位寄存器 （见下图）（见下图）开始时，设第开始时，设第1级内容是级内容是 an-1，第，第2级内容是级

17、内容是 an-2 , , 第第n 级内容是级内容是 a0，则，则称这个寄存器的初始状态是称这个寄存器的初始状态是 (a0, a1, , an-1)。当加上一个脉冲时，每个寄存器的内容移给下一级，第当加上一个脉冲时，每个寄存器的内容移给下一级，第 n 级内容输出，同级内容输出，同时将各级内容送给运算器时将各级内容送给运算器 f (x0, x1, , xn-1) ，并将运算器的结果，并将运算器的结果 an= f (a0 , a1 , , an-1) 反馈到第一级去。这样这个移位寄存器的状态就是反馈到第一级去。这样这个移位寄存器的状态就是 (a1 , a2 , , an)，而输出是，而输出是a0 。

18、不断地加脉冲，上述不断地加脉冲，上述 n 级移位寄存器的输出就是一个二元级移位寄存器的输出就是一个二元(或或q元元)序列：序列： a0 , a1, a2 , 寄存器寄存器 1寄存器寄存器 2寄存器寄存器 3寄存器寄存器 nf (x0, x1, , xn-1)密钥流生成器密钥流生成器v移位寄存器产生的序列都是周期序列，周期都不大于移位寄存器产生的序列都是周期序列，周期都不大于2n。 例例 右图是一个右图是一个4级线性移位寄存器。给定初状态级线性移位寄存器。给定初状态 (0001) ， 求该移位寄存器产生的周期序列。求该移位寄存器产生的周期序列。 解解 易见易见 f (x0，x1，x2，x3) =

19、 x0 + x1， 因此对因此对 k4 有有 ak = ak-3+ ak-4 从而该从而该4级移位寄存器产生的序列是周期级移位寄存器产生的序列是周期15的序列：的序列： 000100110101111 线性移存器序列的最长周期为线性移存器序列的最长周期为2n1v由上例知，移位寄存器由上例知，移位寄存器(简记简记SR，Shifted Register)可由短的序列生成可由短的序列生成具有一定规律的长序列。这种序列便可以作为密钥流序列，但抗攻击具有一定规律的长序列。这种序列便可以作为密钥流序列，但抗攻击能力较差。能力较差。+密钥流生成器密钥流生成器状态转移和相应输出状态转移和相应输出 时刻时刻 状

20、状 态态 输输 出出 3 2 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 0 1 0 0 0 3 0 0 1 0 0 4 1 0 0 1 1 5 1 1 0 0 0 6 0 1 1 0 0 7 1 0 1 1 1 8 0 1 0 1 1 9 1 0 1 0 0 10 1 1 0 1 1 11 1 1 1 0 0 12 1 1 1 1 1 13 0 1 1 1 1 14 0 0 1 1 1 15 0 0 0 1 1 多项式多项式v以以LFSR的反馈系数所决定的多项式的反馈系数所决定的多项式 又称又称反馈多项式反馈多项式、连接多项式连接多项式。式中，式中，c0=cn=1v互反多

21、项式互反多项式 称作是称作是LFSR的的特征多项式特征多项式。cn 0称之为非奇异称之为非奇异LFSR。 njjjnnnnxcxcxcxcxccxf0112210.)(nnnnncxcxcxcxfxxfxc1110*.)1()()(v 收缩密钥流生成器（见右图）收缩密钥流生成器（见右图） 通常的密钥流生成器都是由若干个移位寄存器并联，并且与特殊的电子通常的密钥流生成器都是由若干个移位寄存器并联，并且与特殊的电子电路组合而成。电路组合而成。 上图为由两个移位寄存器构成的上图为由两个移位寄存器构成的收缩密钥流生成器收缩密钥流生成器，通过，通过 SR1 的输出选的输出选择择 SR2 的输出来生成密钥

22、流，其工作模式如下：的输出来生成密钥流，其工作模式如下：输入参数：两个移位寄存器的级数及反馈函数输入参数：两个移位寄存器的级数及反馈函数密钥：两个移位寄存器的初始状态密钥：两个移位寄存器的初始状态 (1) 移位移位SR1 并产生并产生 yi(1) ；同时移位；同时移位SR2 并产生并产生 yi(2) ； (2) 如果如果 yi(1) =1，则，则输出输出密钥元素密钥元素ki = yi(2) ； 如果如果 yi(1) =0，则，则删去删去 yi(2)，i =1, 2, ，不输出不输出。由此收缩生成器产生的密钥流为由此收缩生成器产生的密钥流为ki | i1。SR 1SR 2yi (1)输出输出k

23、kiyi (2)密钥流生成器密钥流生成器流密码对密钥流的要求流密码对密钥流的要求v没有绝对不可破的密码，比如穷搜索总能破译，只是破译所没有绝对不可破的密码，比如穷搜索总能破译，只是破译所需时间是否超过信息的有效期以及破译所需代价是否值得。需时间是否超过信息的有效期以及破译所需代价是否值得。v若一个加密算法没有比穷搜索更好的破译方法，则被认为是若一个加密算法没有比穷搜索更好的破译方法，则被认为是不可破的。不可破的。v实际使用的密钥流序列（简称密钥）都是按一定算法生成的，实际使用的密钥流序列（简称密钥）都是按一定算法生成的，因而不可能是完全随机的，所以也就不可能是完善保密系统。因而不可能是完全随机

24、的，所以也就不可能是完善保密系统。为了尽可能提高系统的安全强度，就必须要求所为了尽可能提高系统的安全强度，就必须要求所产生的密钥产生的密钥流序列尽可能具有随机序列的某些特征流序列尽可能具有随机序列的某些特征。如极大的周期、良。如极大的周期、良好的统计特性。好的统计特性。3.2 分组密码分组密码其他分组密码其他分组密码数据加密标准数据加密标准 DESFeistel密码结构密码结构分组密码的设计原则分组密码的设计原则分组密码的原理分组密码的原理分组密码的典型攻击方法分组密码的典型攻击方法1.分组密码的原理分组密码的原理 v密文中的每位数字不仅仅与某时刻输入的明文数字有关，而密文中的每位数字不仅仅与

25、某时刻输入的明文数字有关，而是与该明文中一定组长的明文数字有关。是与该明文中一定组长的明文数字有关。分组密码将明文按分组密码将明文按一定的位长分组，输出是固定长度的密文。一定的位长分组，输出是固定长度的密文。 加密算法加密算法解密算法解密算法明文明文x=(x1, x2, )密文密文y=(y1, y2, , yn )明文明文x=(x1, x2, )密钥密钥k=(k1, k2, )密钥密钥k=(k1, k2, )分组密码的基本模型分组密码的基本模型 分组密码的长度分组密码的长度明文为分组长度为明文为分组长度为m的序列，密文为分组长度为的序列，密文为分组长度为n的序列：的序列： nm，称其为有数据扩

26、展的分组密码；，称其为有数据扩展的分组密码；nm，称其为有数据压缩的分组密码；，称其为有数据压缩的分组密码；n=m，称其为无数据扩展与压缩的，称其为无数据扩展与压缩的分组密码。分组密码。我们一般所说的分组密码为我们一般所说的分组密码为无数据扩展与压缩的分组密码无数据扩展与压缩的分组密码。 典型的分组是典型的分组是64位或位或128位位分组密码的特点分组密码的特点v主要主要优点优点：易于标准化；易于标准化；易于实现同步。易于实现同步。 v主要主要缺点缺点：不善于隐藏明文的数据模式、对于重放、插入、删除等不善于隐藏明文的数据模式、对于重放、插入、删除等攻击方式的抵御能力不强。攻击方式的抵御能力不强

27、。 分组密码的数学表示分组密码的数学表示v记记明文空间和密文空间为明文空间和密文空间为 （明文与密文分组的长度均为（明文与密文分组的长度均为m），密钥空间为），密钥空间为 （ 是是 的子集的子集，r为密钥长度）：为密钥长度）：v密钥密钥k下的加密函数为下的加密函数为 ，m表示待加密的信息，表示待加密的信息，k为密为密钥，则可将该映射记为钥，则可将该映射记为 ，这个映射应满，这个映射应满足：足： ， 是是 的的一个置换；一个置换； v密钥密钥k下的解密函数记为下的解密函数记为 ，它是，它是 的的逆。逆。 mF2kSkSrF2),(kE mkmFSFE22:kSk ),(kEmmFF22到),(k

28、D ),(kE 2.分组密码的分组密码的设计原则设计原则安全性安全性角度：角度：v“混乱原则混乱原则”：为了避免密码分析者利用明文与密文之间的：为了避免密码分析者利用明文与密文之间的依赖关系进行破译，密码的设计应该保证这种依赖关系足够依赖关系进行破译，密码的设计应该保证这种依赖关系足够复杂。复杂。 v“扩散原则扩散原则” ” ：为避免密码分析者对密钥逐段破译，密码的：为避免密码分析者对密钥逐段破译，密码的设计应该保证密钥的每位数字能够影响密文中的多位数字设计应该保证密钥的每位数字能够影响密文中的多位数字 ；同时，为了避免避免密码分析者利用明文的统计特性，密码同时，为了避免避免密码分析者利用明文

29、的统计特性，密码的设计应该保证明文的每位数字能够影响密文中的多位数字，的设计应该保证明文的每位数字能够影响密文中的多位数字，从而隐藏明文的统计特性。从而隐藏明文的统计特性。 2.分组密码的设计原则分组密码的设计原则可实现性可实现性角度：角度：v应该具有标准的组件结构应该具有标准的组件结构 （子模块），以适应超大规模集（子模块），以适应超大规模集成电路的实现。成电路的实现。v分组密码的运算能在子模块上通过简单的运算进行。分组密码的运算能在子模块上通过简单的运算进行。 3.3 Feistel密码结构密码结构 加密加密: Li = Ri-1 Ri = Li-1 F(Ri-1,Ki)解密解密: Ri-

30、1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)Feistel结构依赖参数和特征结构依赖参数和特征v分组长度分组长度：分组长度越长意味着安全性越高（其他条件不：分组长度越长意味着安全性越高（其他条件不变），但是会降低加解密的速度。一般变），但是会降低加解密的速度。一般64位的分组长度。位的分组长度。v密钥长度密钥长度：密钥较长意味着安全性较高，但会降低加解密的：密钥较长意味着安全性较高，但会降低加解密的速度。一般需要速度。一般需要128位密钥，位密钥，64位密钥通常不够。位密钥通常不够。v迭代轮数迭代轮数： Feistel密码的本质在于单轮不能提供足够的安全密

31、码的本质在于单轮不能提供足够的安全性，多轮可取得很高安全性。迭代轮数的典型值为性，多轮可取得很高安全性。迭代轮数的典型值为16。v子密钥产生算法子密钥产生算法：子密钥越复杂，密码分析攻击越困难。：子密钥越复杂，密码分析攻击越困难。v轮函数轮函数：轮函数越复杂，抗攻击的能力就越强。：轮函数越复杂，抗攻击的能力就越强。3.4 数据加密标准数据加密标准 DES （ Data Encryption Standard ）vDES（Data Encryption Standard）算法于）算法于1977年得到美国政年得到美国政府的正式许可，是一种用府的正式许可，是一种用56位密钥来加密位密钥来加密64位数

32、据的方法，位数据的方法，其密文的长度也为其密文的长度也为64位。位。v国内随着三金工程尤其是金卡工程的启动，国内随着三金工程尤其是金卡工程的启动，DES算法在算法在ATM、磁卡及智能卡（磁卡及智能卡（IC卡）、加油站、高速公路收费站等领域被卡）、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密。如信用卡持卡人的广泛应用，以此来实现关键数据的保密。如信用卡持卡人的PIN的加密传输，的加密传输，IC卡与卡与POS间的双向认证、金融交易数据包间的双向认证、金融交易数据包的的MAC校验等，均用到校验等，均用到DES算法。算法。vDES (Data Encryption Standard

33、) 是由是由IBM公司在公司在20世纪世纪70年年代研制的，经过政府的加密标准筛选后，于代研制的，经过政府的加密标准筛选后，于1976年年11月被美月被美国政府采用，随后被美国国家标准局和美国国家标准协会国政府采用，随后被美国国家标准局和美国国家标准协会(ANSI)所认可。所认可。 vDES算法具有以下特点：算法具有以下特点： （1）DES算法是分组加密算法：以算法是分组加密算法：以64位为分组。位为分组。 （2）DES算法是对称算法：加密和解密用同一密钥。算法是对称算法：加密和解密用同一密钥。 （3）DES算法的有效密钥长度为算法的有效密钥长度为56位。位。 （4）换位和置换。）换位和置换。

34、 （5）易于实现。）易于实现。1. DES的产生背景的产生背景DES的生命期的生命期 vNBS最终采纳了最终采纳了 IBM 的的 LUCIFER 方案，于方案，于 1975 年公开发表。年公开发表。v1977 年正式颁布为数据加密标准（年正式颁布为数据加密标准（DES - Data Encryption Standard）。）。v1979 年，美国银行协会批准使用年，美国银行协会批准使用 DES。v1980 年，年，DES 成为美国标准化协会成为美国标准化协会 (ANSI) 标准。标准。v1984 年，年，ISO 开始在开始在 DES 基础上制定数据加密的国际标准。基础上制定数据加密的国际标准

35、。v美国国家安全局美国国家安全局NSA每隔年对该算法进行评估每隔年对该算法进行评估 ，1994年，决定年，决定1998年年12月之后不再使用月之后不再使用DES 。v现已经确定了选用现已经确定了选用Rijndael算法作为高级加密算法算法作为高级加密算法AES。 2. DES算法要点算法要点 v 算法设计中采用的基本变换和操作：算法设计中采用的基本变换和操作：置换置换（P）：重新排列输入的比特位置。）：重新排列输入的比特位置。交换交换（SW）：将输入的左右两部分的比特进行互换。）：将输入的左右两部分的比特进行互换。循环移位循环移位：将输入中的比特进行循环移位，作为输出。：将输入中的比特进行循环

36、移位，作为输出。一个复杂变换一个复杂变换（ fK ）通常是一个多阶段的乘积变换；通常是一个多阶段的乘积变换；与密钥与密钥 Key 相关；相关；必须是非线性变换；必须是非线性变换；实现对密码分析的扰乱；实现对密码分析的扰乱；是密码设计安全性的关键。是密码设计安全性的关键。3. DES的加密过程的加密过程第一步：第一步：初始置换初始置换IP。对于给定的明文对于给定的明文m，通过初始置换，通过初始置换IP获得获得 ，并将，并将 分为两部分，分为两部分，前面前面32位记为位记为 ，后面，后面32位记为位记为 ，即，即第二步：第二步：乘积变换乘积变换（ 16轮）。轮）。在每一轮中依据下列方法计算在每一轮

37、中依据下列方法计算 （ ）（）（16轮中的计算方法相轮中的计算方法相同）：同）： ， 其中，其中， 为第为第i轮使用的子密钥，各轮使用的子密钥，各 均为均为 的一个置换选择，所有的一个置换选择，所有 构成密钥方案。函数构成密钥方案。函数 中的变量中的变量 为为32位字符串，位字符串， 为为48位字位字符串，符串， 函数函数 输出的结果为输出的结果为32位字符串。位字符串。 0m0m0L0R000)(RLmIPmiiRL161 i1iiRL),(11iiiiKRfLRiKiKKiK),(21XXf1X2X),(21XXfDES的加密过程的加密过程第三步：初始置换第三步：初始置换 的逆置换的逆置换

38、 。应用初始置换应用初始置换 的逆置换的逆置换 对对 进行置换，得进行置换，得到密文到密文c，即，即 。IP1IP1IP1616RL)(16161RLIPcIPLi-1Ri-1LiRikif+一轮一轮DES加密过程加密过程IPL0R0L1=R0R1= L0 f(R0,K1)R2= L1 f(R1,K2)L2= R1明文明文L15= R14R16= L15 f(R15,K16)R15= L14 f(R14,K15)L16=R15IP-1密文密文fK1fK2fK16DES加密流程图LRexpandshiftshiftkeykeyS-boxescompressLR282828282828483248

39、32323232OneRound ofDES4832KiP box（1）IP置换表和置换表和IP-1逆置换表逆置换表v输入的输入的64位数据按位数据按IP表置换进行重新组合，并把输出分为表置换进行重新组合，并把输出分为L0和和R0两部分，两部分，每部分各每部分各32位，其位，其IP表置换如表表置换如表3-1所示所示表表3-1 IP置换表置换表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315741 初始置换初始

40、置换IP和和IP-12014MM1420MMIPIP-1将输入的将输入的64位明文的第位明文的第58位换到第位换到第1位，第位，第50位换到第位换到第2位，依位，依此类推，最后一位是原来的第此类推，最后一位是原来的第7位。位。L0和和R0则是换位输出后的则是换位输出后的两部分，两部分，L0是输出的左是输出的左32位，位，R0是右是右32位。比如：置换前的输位。比如：置换前的输入值为入值为D1D2D3D64，则经过初始置换后的结果为：，则经过初始置换后的结果为：L0=D58D50D8，R0=D57D49D7。经过经过16次迭代运算后。得到次迭代运算后。得到L16和和R16，将此作为输入进行逆置，

41、将此作为输入进行逆置换，即得到密文输出。换，即得到密文输出。表表3-2 IP-1逆置换表逆置换表逆置换正好是初始置的逆运算，例如，第逆置换正好是初始置的逆运算，例如，第1位经过初始置换后，位经过初始置换后，处于第处于第40位，而通过逆置换位，而通过逆置换IP-1，又将第，又将第40位换回到第位换回到第1位，其逆位，其逆置换置换IP-1规则表如规则表如3-2所示。所示。4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917

42、5725(2) 函数函数 f的内部流程的内部流程Ri-1（32bit）ES1S2S8PKi（48bit）48bit32bitf( Ri-1,ki ) (32bit)v E变换的算法是从变换的算法是从Ri-1的的32位中选取某些位，构成位中选取某些位，构成48位，即位，即E将将32位扩展为位扩展为48位。变换规则根据位。变换规则根据E位选择表，如表位选择表，如表3-3所示。所示。表表3-3 E位选择表位选择表3212345456789891011121312131415161716171819202120212223242524252627282928293031321v每个每个S盒输出盒输出4

43、位，共位，共32位，位，S盒的工作原理将在第盒的工作原理将在第4步介绍。步介绍。S盒的输出作为盒的输出作为P变换的输入，变换的输入，P的功能是对输入进行置换，的功能是对输入进行置换，P换位表如表换位表如表3-4所示。所示。vKi是由密钥产生的是由密钥产生的48位比特串，具体的算法是：将位比特串，具体的算法是：将E的选位结的选位结果与果与Ki作异或操作，得到一个作异或操作，得到一个48位输出。分成位输出。分成8组，每组组，每组6位，位，作为作为8个个S盒的输入。盒的输入。表表3-4 P换位表如表换位表如表1672021291228171152326518311028241432273919133

44、062211425（3）DES的密钥的密钥Ki计算计算vDES在各轮中所用的密钥均为由初始密钥（即种子密钥）导在各轮中所用的密钥均为由初始密钥（即种子密钥）导出的出的48位密钥。位密钥。 v初始密钥为初始密钥为64位，其中第位，其中第8、16、24、32、40、48、56、64位均为校验位。位均为校验位。 v如此设置校验位的目的是使每如此设置校验位的目的是使每8个字节所含的字符个字节所含的字符“1”个数个数为奇数，以便能够检测出每个字节中的错误。为奇数，以便能够检测出每个字节中的错误。子密钥子密钥ki产生流程图产生流程图PC-1C0D0LS1LS1C1D1LS2LS2C2D2LS16LS16C

45、16D16PC-2PC-2PC-2K(64bit)K1(48bit)K2(48bit)K16(48bit)假设初始密钥为假设初始密钥为K，长度为长度为64位，但是位，但是其中第其中第8，16，24，32，40，48，64作作奇偶校验位，实际奇偶校验位，实际密钥长度为密钥长度为56位。位。K下标下标i的取值范围的取值范围是是1到到16，用，用16轮来轮来构造。构造过程如构造。构造过程如图所示。图所示。50子密钥的产生子密钥的产生产生子密钥产生子密钥Ki具体描述为：具体描述为：v首先，对于给定的密钥首先，对于给定的密钥K，应用，应用PC1变换进行选位，选定后变换进行选位，选定后的结果是的结果是56

46、位，设其前位，设其前28位为位为C0，后，后28位为位为D0。PC1选位如选位如表表3-5所示。所示。表表 3-5 PC-1选位表选位表57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124v 第第1轮：对轮：对C0作左移作左移LS1得到得到C1，对，对D0作左移作左移LS1得到得到D1，对，对C1D1应用应用PC2进行选位，得到进行选位，得到K1。其中。其中LS1是左移的位数，如表是左移的位数，如表3-6所示。所示。v 第第2轮：对轮：对C

47、1和和D1作左移作左移LS2得到得到C2和和D2，进一步对，进一步对C2D2应用应用PC2进行选进行选位，得到位，得到K2。如此继续，分别得到。如此继续，分别得到K3，K4，K16。表表3-6 LS移位表移位表轮轮 数数循环左移位循环左移位数数轮轮 数数循环左移位循环左移位数数轮轮 数数循环左移位循环左移位数数轮轮 数数循环左移位循环左移位数数115291132216210214232721121524282122161表表 3-7 PC-2选位表选位表14171124153281562110231912426816727201324152313747553040514533484449395

48、63453464250362932（4）S盒的工作原理盒的工作原理vS盒以盒以6位作为输入，而以位作为输入，而以4位作为输出，现在以位作为输出，现在以S1为例说明为例说明其过程。其过程。v假设输入为假设输入为A=a1a2a3a4a5a6，则，则a2a3a4a5所代表的数是所代表的数是0到到15之之间的一个数，记为：间的一个数，记为：k=a2a3a4a5；由；由a1a6所代表的数是所代表的数是0到到3间间的一个数，记为的一个数，记为h=a1a6。在。在S1的的h行，行，k列找到一个数列找到一个数B，B在在0到到15之间，它可以用之间，它可以用4位二进制表示，为位二进制表示，为B=b1b2b3b4

49、，这就是，这就是S1的输出。的输出。vS盒由盒由8张数据表组成，如教材张数据表组成，如教材P84-85所示。所示。S- -盒的构造盒的构造 DES加密范例加密范例v已知明文已知明文m=computer，密钥，密钥k=program。 m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010 k=01110000 01110010 01101111 01100111 01110010 01100001 01101101v这里这里k只有只有56bit，必须插入第，必须插入第8，16，24，32，40，48，5

50、6，64这这8个奇偶校验位成为个奇偶校验位成为64比特。比特。 k= 0111000* 0011100* 1001101* 1110110* 0111011* 1001001* 1000010* 1101101*vm经过经过IP置换后得置换后得 L0 =11111111 10111000 01110110 01010111 R0 =00000000 11111111 00000110 10000011v 密钥密钥k经经PC-1置换得置换得 C0 =11101100 10011001 00011011 1011 D0 =10110100 01011000 10001110 0111vC0和和 D

51、0各循环左移一位后通过各循环左移一位后通过PC-2得到得到48bit的子密钥的子密钥k1。 C1=11011001 00110010 00110111 0111 D1 =01101000 10110001 00011100 1111 k1 =00111101 10001111 11001101 00110111 00111111 01001000DES加密范例加密范例vR0经过经过E变换后扩展为变换后扩展为48bit。 10000000 00010111 11111110 10000000 11010100 00000110v再和再和k1 作异或运算，得作异或运算，得 10111101 100

52、11000 00110011 10110111 11101011 01001110v分成分成8组组 101111 011001 100000 110011 101101 111110 101101 001110v经过经过S盒后输出盒后输出32bit 0111 0110 1101 0100 0010 0110 1010 0001v再经过再经过P置换得置换得 01000100 00100001 10011111 1001101101(,)f R kDES加密范例加密范例v所以第一轮迭代的结果为所以第一轮迭代的结果为v =10111011 10011001 11101001 1100110010LR

53、1001(,)RLf R kDES加密范例加密范例4. DES的解密过程的解密过程v采用与加密相同的算法。采用与加密相同的算法。v以逆序（即以逆序（即 ）使用密钥。）使用密钥。11516,KKK 111 216( )( )DEScIP TTTIP c实现实现效果效果不同微处理器上的不同微处理器上的DES软件实现速度软件实现速度 处理器处理器处理器速度（处理器速度（MHz）每秒处理的每秒处理的DES分组个数分组个数80884.7370680007.69008028661,10068020163,50068030163,90080286255,000680305010,000680402516,0

54、00680404023,000804866643,000雪崩效应雪崩效应v明文或密钥的微小改变将对密文产生很大的影响是任何算法明文或密钥的微小改变将对密文产生很大的影响是任何算法所期望的一个好性质。明文或密钥的某一位发生变化会导致所期望的一个好性质。明文或密钥的某一位发生变化会导致密文的很多位发生变化。如果相应的改变很小，可能会给分密文的很多位发生变化。如果相应的改变很小，可能会给分析者提供缩小搜索密钥或明文空间的渠道。析者提供缩小搜索密钥或明文空间的渠道。vDES显示出很强的雪崩效应：如下两条仅有一位不同的明文：显示出很强的雪崩效应：如下两条仅有一位不同的明文：00000000 000000

55、00 00000000 00000000 00000000 00000000 00000000 0000000010000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000密钥：密钥：0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010v结果表明仅经过结果表明仅经过3轮迭代后，两段数据有轮迭代后，两段数据有21位不同。全部迭代位不同。全部迭代完成后得到的两段密文则有完成后得到的两段密文则有34位不同。位不同。DES的雪崩效应的雪崩效应(a)

56、 明文的变化明文的变化(b)密钥的变化密钥的变化轮数轮数 改变的位数改变的位数轮数轮数 改变的位数改变的位数0 11 62 213 354 395 346 327 318 29 . . .0 01 22 143 284 325 306 327 358 34 . . . 5. DES的安全性分析的安全性分析 vDES的安全性完全依赖于密钥，与算法本身没有关系。的安全性完全依赖于密钥，与算法本身没有关系。 v主要研究内容：主要研究内容：密钥的互补性；密钥的互补性；弱密钥与半弱密钥；弱密钥与半弱密钥；密文密文- -明文相关性；明文相关性；密文密文- -密钥相关性；密钥相关性；S-S-盒的设计；盒的设

57、计；密钥搜索。密钥搜索。 密钥的互补性密钥的互补性vDES算法具有互补性，即：若算法具有互补性，即：若 、 是是 的的补、补、 是是 的补，则的补，则 。v使用使用DES算法时不要使用互补的密钥，否则当密码算法时不要使用互补的密钥，否则当密码攻击者选择明文攻击时，他们仅需试验一半密钥。攻击者选择明文攻击时，他们仅需试验一半密钥。 )(mDESckccmm)(mDESck弱密钥弱密钥v弱密钥：由密钥弱密钥：由密钥 k 确定的加密函数与解密函数相同确定的加密函数与解密函数相同 ，即即 。vDES的弱密钥：的弱密钥： 如果各轮产生的子密钥一样，则加密函数与如果各轮产生的子密钥一样，则加密函数与解密函

58、数相同。解密函数相同。 vDES至少有至少有4个弱密钥个弱密钥 ：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe)()(1kkDESDES半弱密钥半弱密钥 v半弱密钥：对于密钥半弱密钥：对于密钥 k ，存在一个不同的密钥，存在一个不同的密钥 ，满，满足足 。 vDES的半弱密钥：子密钥生成过程中只能产生两个不同的子的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。密钥或四个不同的子密钥，互为对合。 vDES至少有至少有12个半弱密钥。个半弱密钥。 *k)()(*kkDESDESS-

59、 -盒的设计原则盒的设计原则 S -盒的设计原理没有公开，一些原则如下：盒的设计原理没有公开，一些原则如下：v所有所有S-盒的每一行是盒的每一行是0,1,15的一个置换；的一个置换；v所有所有S-盒的输出都不是输入的线性函数或仿射函数；盒的输出都不是输入的线性函数或仿射函数；vS-盒的输入改变任意一位都会引起输出中至少两位发生变化；盒的输入改变任意一位都会引起输出中至少两位发生变化；v对于任何输入对于任何输入x（6位），位），S(x)与与S(x 001100)至少有两位不同；至少有两位不同；v对于任何输入对于任何输入x（6位），位），S(x)与与S(x 00ef00)不相等，不相等，e, f取

60、取0或或1；v对于任意一个输入位保持不变而其他五位变化时，输出中对于任意一个输入位保持不变而其他五位变化时，输出中0和和1的的数目几乎相等。数目几乎相等。 针对针对DES的攻击方法的攻击方法攻击攻击DES的方法主要有：的方法主要有：密钥穷搜索攻击，密钥穷搜索攻击，DES算法总的密钥量为算法总的密钥量为 ，1998年使用高级计算机的情况下，破译年使用高级计算机的情况下，破译DES只需只需56小时；小时； 差分攻击；差分攻击；线性攻击，较有效的方法；线性攻击，较有效的方法；相关密钥攻击等。相关密钥攻击等。DES遭受攻击的原因只是因为其密钥过短，而不是因为遭受攻击的原因只是因为其密钥过短，而不是因为