(现代密码学课件）03分组密码

1、( (现代密码学课件现代密码学课件0303分组密码分组密码7分组密码设计问题分组密码设计问题 分组密码的设计问题在于找到一种算法，分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密用来对当前输入的明文的数字组进行加密变换。变换。8分组密码算法的要求分组密码算法的要求n分组长度分组长度n要足够大：要足够大：n 防止明文穷举攻击法奏效。防止明文穷举攻击法奏效。n密钥量要足够大：密钥量要足够大：n 尽可能消除弱密钥并使所有密钥同尽可

2、能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。等地好，以防止密钥穷举攻击奏效。n由密钥确定置换的算法要足够复杂：由密钥确定置换的算法要足够复杂：n 充分实现明文与密钥的扩散和混淆，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种的没有简单的关系可循，要能抗击各种的攻击。攻击。 9分组密码算法的要求分组密码算法的要求n加密和解密运算简单：加密和解密运算简单：n 易于软件和硬件高速实现。易于软件和硬件高速实现。n数据扩展：数据扩展：n 一般无数据扩展，在采用同态置换和随一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。机化加密技术时可引入数据扩展。n过失传

3、播尽可能地小。过失传播尽可能地小。10代换网络代换网络n代换是输入集代换是输入集A到输出集到输出集A上的双射变换：上的双射变换：n fk：AAn 式中，式中，k是控制输入变量，在密码学中那么是控制输入变量，在密码学中那么为密钥。为密钥。n实现代换实现代换fk的网络称作代换网络。双射条件保的网络称作代换网络。双射条件保证在给定证在给定k下可从密文惟一地恢复出原明文。下可从密文惟一地恢复出原明文。11代换网络代换网络12代换网络代换网络n代换代换fk的集合：的集合： n S=fk|kKnK是密钥空间。如果网络可以实现所有是密钥空间。如果网络可以实现所有可能的可能的2n!个代换，那么称其为全代换个代

4、换，那么称其为全代换网络。网络。n全代换网络密钥个数必须满足条件：全代换网络密钥个数必须满足条件：k2n! 13代换网络代换网络n密码设计中需要先定义代换集密码设计中需要先定义代换集S，而后还需定义，而后还需定义解密变换集，即逆代换网络解密变换集，即逆代换网络S-1，它以密文，它以密文y作作为输入矢量，其输出为恢复的明文矢量为输入矢量，其输出为恢复的明文矢量x。n要实现全代换网络并不容易。因此实用中常常要实现全代换网络并不容易。因此实用中常常利用一些简单的根本代换，通过组合实现较复利用一些简单的根本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密码体制杂的、元素个数较多的代换集。实用密

5、码体制的集合的集合S中的元素个数都远小于中的元素个数都远小于2n!。14代换盒代换盒(S盒盒) 在密码设计中，可选在密码设计中，可选n=r n0，其中其中r和和n0都为正整都为正整数，将设计数，将设计n个变量的代换网络化为设计个变量的代换网络化为设计r个较小个较小的子代换网络，而每个子代换网络只有的子代换网络，而每个子代换网络只有n0个输入个输入变量。称每个子代换网络为代换盒变量。称每个子代换网络为代换盒(Substitution Box) S盒盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0DES的的S盒盒15扩散和混淆扩散和混淆n扩散将扩散将明文明文的统计特性散布到的统计特性

6、散布到密文密文中。实中。实现的方式是使明文的每一位影响密文中多现的方式是使明文的每一位影响密文中多位的值。位的值。n混淆使混淆使密文密文和和密钥密钥之间的统计关系变得尽之间的统计关系变得尽可能复杂，以使敌手无法得到密钥可能复杂，以使敌手无法得到密钥。16S盒的组合盒的组合 问题问题: 如何将几个如何将几个S盒组合起来构成一个盒组合起来构成一个n值值较大的组。较大的组。 将几个将几个S盒的输入端并行，并通过坐标盒的输入端并行，并通过坐标置换置换(P-盒盒)将各将各S盒输出比特次序打乱，再盒输出比特次序打乱，再送 到 下 一 级 各送 到 下 一 级 各 S 盒 的 输 入 端 ， 起 到 了盒

7、的 输 入 端 ， 起 到 了Shannon所谓的所谓的“扩散作用。扩散作用。S盒提供非盒提供非线性变换，将来自上一级不同的线性变换，将来自上一级不同的S盒的输出盒的输出进行进行“混淆。经过混淆。经过P-盒的扩散作用使盒的扩散作用使1均均匀地分散到整个输出矢量中，从而保证了匀地分散到整个输出矢量中，从而保证了输 出 密 文 统 计 上 的 均 匀 性 ， 这 就 是输 出 密 文 统 计 上 的 均 匀 性 ， 这 就 是Shannon的乘积密码的作用。的乘积密码的作用。17迭代分组密码迭代分组密码n假设以一个简单函数假设以一个简单函数f，进行屡次迭代，就称其为迭代密码。，进行屡次迭代，就称其

8、为迭代密码。n每次迭代称作一轮每次迭代称作一轮(Round)。相应函数。相应函数f称作轮函数。称作轮函数。n每一轮输出都是前一轮输出的函数，即每一轮输出都是前一轮输出的函数，即y(i)=fy(i-1), k(i)，其中其中k(i)是第是第i轮迭代用的子密钥，由秘密密钥轮迭代用的子密钥，由秘密密钥k通过密钥生通过密钥生成算法产生。成算法产生。 fff子子 密密 钥钥 产产 生生 器器kk(1)k(2)k(r)y(0) = xy(1)y(2)y(r-1)y(r)=y18Feistel网络网络 将将n bit明文分成为左右各半、长为明文分成为左右各半、长为n/2 bit的段，的段，以以L和和R表示。

9、然后进行多轮迭代，其第表示。然后进行多轮迭代，其第i轮迭代的轮迭代的输出为前轮输出的函数输出为前轮输出的函数 Li =Ri-1 Ri =Li-1F(Ri-1, Ki) 式中，式中，Ki是第是第i轮用的子密钥，轮用的子密钥，F是任意密码轮函是任意密码轮函数。称这种分组密码算法为数。称这种分组密码算法为Feistel网络网络Feistel Network，它保证加密和解密可采用同一算法，它保证加密和解密可采用同一算法实施实施19Feistel网络框图网络框图20Feistel网络参数网络参数Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： 分组大小分组大小: 分组越大

10、那么平安性越高，但加密速度就越慢分组越大那么平安性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是。分组密码设计中最为普遍使用的分组大小是64比特。比特。 密钥大小：密钥越长那么平安性越高，但加密速度就越密钥大小：密钥越长那么平安性越高，但加密速度就越慢。现在普遍认为慢。现在普遍认为64比特或更短的密钥长度是不平安的比特或更短的密钥长度是不平安的，通常使用，通常使用128比特的密钥长度。比特的密钥长度。 轮数：单轮结构远缺乏以保证平安性，但多轮结构可提轮数：单轮结构远缺乏以保证平安性，但多轮结构可提供足够的平安性。典型地，轮数取为供足够的平安性。典型地，轮数取为16。 子密钥产生

11、算法：该算法的复杂性越大，那么密码分析子密钥产生算法：该算法的复杂性越大，那么密码分析的困难性就越大。的困难性就越大。 轮函数：轮函数的复杂性越大，密码分析的困难性也越轮函数：轮函数的复杂性越大，密码分析的困难性也越大。大。21Feistel网络实现网络实现在设计在设计Feistel网络时，还有以下两个方面需网络时，还有以下两个方面需要考虑：要考虑： 快速的软件实现：在很多情况中，算法是快速的软件实现：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。现。此时算法的执行速度是考虑的关键。 算法容易分析：如果算法能被无

12、疑义地解算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。能力，有助于设计高强度的算法。22Feistel解密结构解密结构Feistel解密过程本质上和加密过程是一样解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密的，算法使用密文作为输入，但使用子密钥钥Ki的次序与加密过程相反，即第的次序与加密过程相反，即第1轮使用轮使用Kn，第第2轮使用轮使用Kn-1，最后一轮使用最后一轮使用K1。这一特性保证了解密和加密可采用同这一特性保证了解密和加密可采用同一算法。一算法。23Feistel加解密结

13、构加解密结构24二、二、DES密码算法密码算法n分组密码概述分组密码概述n数据加密标准数据加密标准DESn国际数据加密算法国际数据加密算法IDEAn数据加密标准数据加密标准AESn分组密码的分析分组密码的分析n分组密码运行模式分组密码运行模式25DES数据加密标准数据加密标准n目的目的n 通信与计算机相结合是人类步入信通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，息社会的一个阶梯，它始于六十年代末，完成于完成于90年代初。计算机通信网的形成与年代初。计算机通信网的形成与开展，要求信息作业标准化，平安保密亦开展，要求信息作业标准化，平安保密亦不例外。只有标准化，才能真正实现网

14、的不例外。只有标准化，才能真正实现网的平安，才能推广使用加密手段，以便于训平安，才能推广使用加密手段，以便于训练、生产和降低本钱。练、生产和降低本钱。 26DES数据加密标准数据加密标准n美国美国NBS在在1973年年5月月15公布了征求建议。公布了征求建议。1974年年8月月27日日NBS再次出公告征求建议，对再次出公告征求建议，对建议方案提出如下要求：建议方案提出如下要求：n算法必须完全确定而无模糊之处；算法必须完全确定而无模糊之处；n算法必须有足够高的保护水准，即可以检测到算法必须有足够高的保护水准，即可以检测到威胁，恢复密钥所必须的运算时间或运算次数威胁，恢复密钥所必须的运算时间或运算

15、次数足够大；足够大；n保护方法必须只依赖于密钥的保密；保护方法必须只依赖于密钥的保密；n对任何用户或产品供给者必须是不加区分的。对任何用户或产品供给者必须是不加区分的。27DES数据加密标准数据加密标准nIBM公司在公司在1971年完成的年完成的LUCIFER密码密码 (64 bit分组，代换分组，代换-置换，置换，128 bit密钥密钥)的根底上，改进成为建议的的根底上，改进成为建议的DES体制体制n1975年年3月月17日日NBS公布了这个算法，并说明要以它作为联公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。邦信息处理标准，征求各方意见。n1977年年1月月15日建议被批

16、准为联邦标准日建议被批准为联邦标准FIPS PUB 46，并设，并设计推出计推出DES芯片。芯片。n1981年美国年美国ANSI 将其作为标准，称之为将其作为标准，称之为DEAANSI X3.92n1983年国际标准化组织年国际标准化组织(ISO)采用它作为标准，称作采用它作为标准，称作DEA-128DES数据加密标准数据加密标准nNSA宣布每隔宣布每隔5年重新审议年重新审议DES是否继续作为联邦标准，是否继续作为联邦标准，1988年年FIPS46-1、1993年年FIPS46-2，1998年不年不再重新批准再重新批准DES为联邦标准。为联邦标准。n虽然虽然DES已有替代的数据加密标准算法，但

17、它仍是迄今已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。的分组加密体制。n1993年年4月，月，Clinton政府公布了一项建议的加密技术标政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准准，称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府。算法属美国政府SECRET密级。密级。29DES数据加密标准数据加密标准nDES开展史确定了开展公用标准算法模式，而开展史确定了开展公用标准算法模式，而EES的的制定路线与制定路线与D

18、ES的背道而驰。人们疑心有陷门和政府的背道而驰。人们疑心有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。部门肆意侵犯公民权利。此举遭到广为反对。n1995年年5月月AT&T Bell Lab的的M. Blaze博士在博士在PC机上用机上用45分钟时间使分钟时间使SKIPJACK的的 LEAF协议失败，伪造协议失败，伪造ID码获得成功。码获得成功。1995年年7月美国政府宣布放弃用月美国政府宣布放弃用EES来加来加密数据，只将它用于语音通信。密数据，只将它用于语音通信。n1997年年1月美国月美国NIST着手进行着手进行AESAdvanced Encryption Standard的

19、研究，成立了标准工作室。的研究，成立了标准工作室。2001年年Rijndael被批准为被批准为AES标准。标准。30DES加密算法加密算法n分组长度为分组长度为64 bits (8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密钥长度为密钥长度为64 bits，有有8 bits奇偶校验，有效密奇偶校验，有效密钥长度为钥长度为56 bits。n算法主要包括：初始置换算法主要包括：初始置换IP、16轮迭代的乘积轮迭代的乘积变换、逆初始置换变换、逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 31DES算法框图算法框图输入64 bit明文数据64 bit密文数据初

20、始置换IP逆初始置换IP-1 轮变换(16轮迭代)标准数据加密算法标准数据加密算法输出32初始置换初始置换n初始置换初始置换IPIP ：将：将64 bit明文的位置进行置换，得到一个明文的位置进行置换，得到一个乱序的乱序的64 bit明文组，而后分成左右两段，每段为明文组，而后分成左右两段，每段为32 bit，以以L0和和R0表示，表示，IP中各列元素位置号数相差为中各列元素位置号数相差为8，相当，相当于将原明文各字节按列写出，各列比特经过偶采样和于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置

21、换输出。读出构成置换输出。n逆初始置换逆初始置换IPIP-1-1：将：将16轮迭代后给出的轮迭代后给出的64 bit组进行置组进行置换，得到输出的密文组。输出为阵中元素按行读得的换，得到输出的密文组。输出为阵中元素按行读得的结果。结果。nIP和和IP-1-1在密码意义上作用不大，它们的作用在于打乱在密码意义上作用不大，它们的作用在于打乱原来输入原来输入x的的ASCII码字划分的关系，并将原来明文的码字划分的关系，并将原来明文的校验位校验位x8, x16, x64变成为变成为IP输出的一个字节。输出的一个字节。33初始置换初始置换34轮变换框图轮变换框图Li-1(32bit)Ri-1(32bit

22、)Ri (32bit)选择扩展运算选择扩展运算E按按bit模模2加密加密选择压缩运算选择压缩运算S置换运算置换运算P按按bit模模2和和Li (32bit)密钥产生器密钥产生器48 bit48 bit32 bitKi35轮变换流程轮变换流程n它是它是DES算法的核心局部。将经过算法的核心局部。将经过IP置换后的数据分成置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。的左右两组，在迭代过程中彼此左右交换位置。n每次迭代时只对右边的每次迭代时只对右边的32 bit进行一系列的加密变换，进行一系列的加密变换，在此轮迭代即将结束时，把左边的在此轮迭代即将结束时，把左边的32 bi

23、t与右边得到的与右边得到的32 bit逐位模逐位模2相加，作为下一轮迭代时右边的段，并将相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的存放器中作为下原来右边未经变换的段直接送到左边的存放器中作为下一轮迭代时左边的段。一轮迭代时左边的段。n在每一轮迭代时，右边的段要经过选择扩展运算在每一轮迭代时，右边的段要经过选择扩展运算E、密、密钥加密运算、选择压缩运算钥加密运算、选择压缩运算S、置换运算、置换运算P和左右混合运和左右混合运算。算。36选择扩展运算选择扩展运算 选择扩展运算选择扩展运算E。将输入的。将输入的32 bit Ri-1扩展成扩展成48 bit的输的输出，令出，

24、令s表示表示E原输入数据比特原输入数据比特的原下标，那么的原下标，那么E的输出是将的输出是将原下标原下标s0或或1(mod 4)的各的各比特重复一次得到的，即对原比特重复一次得到的，即对原第第32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29各位都重复一次各位都重复一次,实现数据实现数据扩展。将表中数据按行读出得扩展。将表中数据按行读出得到到48 bit输出。输出。 37密钥加密运算密钥加密运算 密钥加密运算密钥加密运算。将子密钥产生器输出的。将子密钥产生器输出的48 bit子密钥子密钥ki与选择扩展运算与选择扩展运算E输出的输出

25、的48 bits数据按位模数据按位模2相加。相加。38选择压缩运算选择压缩运算选择函数组选择函数组 48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S86 bit4 bit选择压缩运算选择压缩运算S：将前面送来的将前面送来的48 bit数据自左至右分成数据自左至右分成8组，组，每组为每组为6 bit。而后并行送入而后并行送入8个个S盒，每个盒，每个S盒为一非线性代换盒为一非线性代换网络，有网络，有4个个bit输出，运算输出，运算S的框图在图的框图在图3-7中给出。中给出。39DES的的S1盒盒定义定义(y3 , y2, y1 , y0)=(0,0,1,0)nx5 x0 x5

26、 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 40DES的的S盒定义盒定义41DES的的S盒定义盒定义42S盒的设计准那么盒的设计准那么 迄今为止，有关方面未曾完全公开有关迄

27、今为止，有关方面未曾完全公开有关DES的的S盒的设计准盒的设计准那么。那么。Branstead等曾披露过下述准那么：等曾披露过下述准那么：P1 S盒的输出都不是其输入的线性或仿射函数。盒的输出都不是其输入的线性或仿射函数。P2 改变改变S盒的一个输入比特，其输出至少有两比特产生变化，盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。即近一半产生变化。P3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变化时位输入变化时(共有共有25 =32种情况种情况)，输出数字中的，输出数字中的0和和1的总数近于相等。的总数近于相等。 这三点使这三点使DES的的S盒能够

28、实现较好的混淆。盒能够实现较好的混淆。43置换运算置换运算 置换运算置换运算P P。对。对S1S1至至S8S8盒输出的盒输出的32 bit32 bit数据进数据进行坐标置换，置换行坐标置换，置换P P输出的输出的32 bit32 bit数据与左边数据与左边32 32 bitbit即即Ri-1Ri-1逐位模逐位模2 2相加，所得到的相加，所得到的32 bit32 bit作为作为下一轮迭代用的右边的数字段。并将下一轮迭代用的右边的数字段。并将Ri-1Ri-1并行并行送到左边的存放器，作为下一轮迭代用的左边的送到左边的存放器，作为下一轮迭代用的左边的数字段。数字段。置换置换P16 7 20 21 2

29、9 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 919 13 30 6 22 11 4 2544左右混合运算左右混合运算左右混合运算左右混合运算：前面四步运算就组成了：前面四步运算就组成了Feistel网络的轮函数网络的轮函数F(Ri-1, Ki)，左右混合，左右混合运算就是如下的运算。运算就是如下的运算。 Li =Ri-1 Ri =Li-1 F(Ri-1, Ki)45轮变换框图轮变换框图Li-1(32bit)Ri-1(32bit)Ri (32bit)选择扩展运算选择扩展运算E按按bit模模2加密加密选择压缩运算选择压缩运算S置换运算置换运

30、算P按按bit模模2和和Li (32bit)密钥产生器密钥产生器48 bit48 bit32 bitKi46密钥的产生密钥的产生n子密钥产生器子密钥产生器 将将64 bit初始密钥经过初始密钥经过置换选择置换选择PC1PC1、循环移位置换循环移位置换LSi、置换选择、置换选择PC2PC2给出每次给出每次迭代加密用的子密钥迭代加密用的子密钥Ki。共生成。共生成16个子密钥。个子密钥。n移位次数表移位次数表 第第i次迭代次迭代 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 循环左移次数循环左移次数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 147子

31、密钥产生器框图子密钥产生器框图 密钥（密钥（64 bit ）置换选择置换选择1，PC1置换选择置换选择2，PC2 Ci(28 bit) Di(28 bit) 循环左移循环左移ti+1bit 循环左移循环左移ti+1bit除去第除去第8,16, ,64位位(8个校验位个校验位)Ki48置换选择置换选择1n置换选择置换选择1: PC-1 64位密钥位密钥K的第的第8, 16, 24,64位共位共8位位是奇偶校验位是奇偶校验位, 其余其余56位作为密钥用位作为密钥用. 选择选择K的第的第57,49,位共位共28位作为密钥位作为密钥段段C0;选择选择K的第的第63,55,位共位共28位作位作为密钥段为

32、密钥段D0.PC-157 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 2719 11 3 60 52 44 3663 55 47 39 31 23 15 7 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 449循环左移循环左移n循环左移循环左移LSi 将将28位的密钥段作为位的密钥段作为Ci，Di循环左移循环左移1或或2位，左移位，左移位数由下表确定位数由下表确定. i12345678910111213141516LSi112222221222222150置换选择置换选择2

33、n置换选择置换选择2: PC-2 从从56位密钥段位密钥段Ci|Di中选择中选择48位作为位作为子密钥子密钥Ki.PC-2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 3251DES解密算法解密算法n与与DES加密结构相同加密结构相同n子密钥使用次序相反子密钥使用次序相反: K16,K15,K2,K1n输入：密文输入：密文yn输出：明文输出：明文x52DES的平安性的平安性DES (

34、)Kyx这种互补性会使这种互补性会使DES在选择明文破译下所在选择明文破译下所需的工作量减半。需的工作量减半。互补性。互补性。DES算法具有下述性质。假设明文算法具有下述性质。假设明文组组 x 逐 位 取 补 ， 密 钥逐 位 取 补 ， 密 钥 K 逐 位 取 补 ， 即逐 位 取 补 ， 即y=DESK(x), 那么有那么有53DES的平安性的平安性n弱密钥弱密钥。DES算法在每次迭代时都有一个子算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥密钥供加密用。如果给定初始密钥K，各轮的，各轮的子密钥都相同，即有子密钥都相同，即有 K1=K2= =K16 就称给定密钥就称给定密钥K为弱

35、密钥为弱密钥(Weak key)。弱密钥值弱密钥值(带奇校验带奇校验)实际密钥实际密钥(经置换选择经置换选择1)0101010101010101010101010101010100000000000000000000000000001F1F1F1F1F1F1F1F0E0E0E0E0E0E0E0E00000000000000FFFFFFFFFFFFFFE0E0E0E0E0E0E0E0F1F1F1F1F1F1F1F1FFFFFFFFFFFFFF00000000000000FEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFFFFFFFFFFFFFFFFFFFFFFFFFFFF54DE

36、S的平安性的平安性假设假设K为弱密钥，那么有为弱密钥，那么有 DESK(DESK(x)=x DESK-1(DESK-1(x)=x 即以即以K对对x加密两次或解密两次都可恢复出明文。其加加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。密运算和解密运算没有区别。 弱密钥下使弱密钥下使DES在选择明文攻击下的搜索量减半。在选择明文攻击下的搜索量减半。 如果随机地选择密钥，弱密钥所占比例极小，而且如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及稍加注意就不难避开。因此，弱密钥的存在不会危及DES的平安性。的平安性。55DES的平安性的平安性密文

37、与明文、密文与密钥的相关性密文与明文、密文与密钥的相关性 Meyer1978详细研究了详细研究了DES的输入明文的输入明文与密文及密钥与密文之间的相关性。说明与密文及密钥与密文之间的相关性。说明每个密文比特都是所有明文比特和所有密每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出到达这一要钥比特的复合函数，并且指出到达这一要求 所 需 的 迭 代 次 数 至 少 为求 所 需 的 迭 代 次 数 至 少 为 5 。Konheim1981用用2检验证明，迭代检验证明，迭代8次次后输出和输入就可认为是不相关的了。后输出和输入就可认为是不相关的了。56DES的平安性的平安性S盒设计盒设计

38、 DES靠靠S盒实现非线性变换。盒实现非线性变换。密钥搜索机密钥搜索机 对对DES平安性批评意见中，较为一致的看法是平安性批评意见中，较为一致的看法是DES的密钥短了些。的密钥短了些。IBM最初向最初向NBS提交的建提交的建议方案采用议方案采用112比特密钥，但公布的比特密钥，但公布的DES标准采标准采用用64比特密钥。有人认为比特密钥。有人认为NSA成心限制成心限制DES的的密钥长度。采用穷举搜索对已经对密钥长度。采用穷举搜索对已经对DES构成了构成了威胁威胁57DES的平安性的平安性1991年研究说明年研究说明DES搜索机本钱如下。搜索机本钱如下。资本成本资本成本时间成本时间成本$1万万2

39、.5天天$10万万6小时小时$100万万35分钟分钟$1000万万3.5分钟分钟58二重二重DES 用用DES进行两次加密，但这是否就意味着两重进行两次加密，但这是否就意味着两重DES加密的强度等价于加密的强度等价于112 bit密钥的密码的强密钥的密码的强度？答案是否认的。度？答案是否认的。 中途相遇攻击法中途相遇攻击法(Meet-in-the-Middle Attack) 由由Diffie和和Hellman1977最早提出，可以降低最早提出，可以降低搜索量。其根本想法如下。假设有明文密文对搜索量。其根本想法如下。假设有明文密文对(xi,yi)满足满足 yi=Ek2Ek1xi 那么可得那么可

40、得 z=Ek1xi=Dk2yi 59二重二重DES中途相遇攻击示意图中途相遇攻击示意图 zEEDDxiyixizyi K1 K1K2K260中途相遇攻击中途相遇攻击给定一明密文对给定一明密文对(x1,y1)，可按下述方法攻击。，可按下述方法攻击。以密钥以密钥k1的所有的所有256个可能的取值对此明文个可能的取值对此明文x1加密，加密，并将密文并将密文z存储在一个表中；存储在一个表中；从所有可能的从所有可能的256个密钥个密钥k2中依任意次序选出一个对中依任意次序选出一个对给定的密文给定的密文y1解密，并将每次解密结果解密，并将每次解密结果z在上述在上述表中查找相匹配的值。一旦找到，那么可确定出

41、表中查找相匹配的值。一旦找到，那么可确定出两个密钥两个密钥k1和和k2；以此对密钥以此对密钥k1和和k2对另一明文密文对对另一明文密文对(x2, y2)中的明中的明文文x2进行加密，如果能得出相应的密文进行加密，如果能得出相应的密文y2就可确就可确定定k1和和k2是所要找的密钥。是所要找的密钥。61中途相遇攻击中途相遇攻击n对于给定明文对于给定明文x，以两重以两重DES加密将有加密将有264个可能个可能的密文。的密文。n可能的密钥数为可能的密钥数为2112个。所以，在给定明文下，个。所以，在给定明文下，将有将有2112/264 =248个密钥能产生给定的密文。个密钥能产生给定的密文。n用另一对

42、用另一对64bits明文密文对进行检验，就使虚报明文密文对进行检验，就使虚报率降为率降为248-64=2-16。n这一攻击法所需的存储量为这一攻击法所需的存储量为2568 Byte，最大试最大试验的加密次数验的加密次数2256 =257。这说明破译双重。这说明破译双重DES的难度为的难度为257量级。量级。62三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1y称其为加密称其为加密-解密解密-加密方案，简记为加密方案，简记为EDE(encrypt-decrypt-encrypt)。此方案已在和此方案已在和ISO 8732标准中采用，并在保密增强邮递标

43、准中采用，并在保密增强邮递(PEM)系统中得到利用。系统中得到利用。破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为211251035量级，而用差量级，而用差分分析破译也要超过分分析破译也要超过1052量级。此方案仍有足够的平量级。此方案仍有足够的平安性。安性。63DES密码练习密码练习n将你的学号的后将你的学号的后3位转换为位转换为2进制数，并在进制数，并在前面补前面补0得到得到32比特的二进制串。比特的二进制串。n假设在假设在DES加密的第加密的第i轮中，轮中，Li-1和和Ri-1都都等于上面的等于上面的32比特串，比特串，Ki等于等于“crypto的的ASCII码其码其16进制表示为进制

44、表示为63 72 79 70 74 6F这个这个48比特串，计算比特串，计算Li和和Ri。64三、三、分组密码的分析分组密码的分析n分组密码概述分组密码概述n数据加密标准数据加密标准DESn国际数据加密算法国际数据加密算法IDEAn高级加密标准高级加密标准AESn分组密码的分析分组密码的分析n分组密码运行模式分组密码运行模式65差分密码分析差分密码分析nDES经历了近经历了近20年全世界性的分析和攻击，提出了年全世界性的分析和攻击，提出了各种方法，但破译难度大都停留在各种方法，但破译难度大都停留在255量级上。量级上。n1991年年Biham和和Shamir公开发表了差分密码分析法公开发表了差

45、分密码分析法(Differential Cryptanalysis)才使对才使对DES一类分组密一类分组密码的分析工作向前推进了一大步。码的分析工作向前推进了一大步。这一方法是攻击这一方法是攻击迭代密码体制的最有效方法之一，它对多种分组密迭代密码体制的最有效方法之一，它对多种分组密码和码和Hash 函数都相当有效，相继攻破了函数都相当有效，相继攻破了FEAL、LOKI、LUCIFER等密码。等密码。n此法对分组密码的研究设计也起到巨大推动作用。此法对分组密码的研究设计也起到巨大推动作用。66DES差分分析差分分析n对对DES中的非线性的中的非线性的S盒的分析盒的分析 nS盒输入为盒输入为6比特

46、，输出为比特，输出为4比特，设为比特，设为s(x)；n选择二进制数选择二进制数a, b和和c都为都为6比特，比特，d为为4比特比特；nabc，那么，那么s(a)s(b) = d的概率远远大的概率远远大于于1/16(抗差分攻击的分组密码此概率恒等抗差分攻击的分组密码此概率恒等1/2n，n为为S盒输出位数盒输出位数)；n由此性质可得局部密钥的信息，通过穷举由此性质可得局部密钥的信息，通过穷举就可以得出密钥。就可以得出密钥。67差分密码分析差分密码分析n以这一方法攻击以这一方法攻击DES，尚需要用，尚需要用247个选择明文个选择明文和和247次加密运算。为什么次加密运算。为什么DES在强有力的差值在

47、强有力的差值密码分析攻击下仍能站住脚密码分析攻击下仍能站住脚?n根据根据Copper Smith1992内部报告内部报告透露，透露，IBM的的DES研究组早在研究组早在1974年就道这类攻击方法，因年就道这类攻击方法，因此，在设计此，在设计S盒、盒、P置换和迭代轮数上都做了充置换和迭代轮数上都做了充分考虑，从而使分考虑，从而使DES能经受住这一有效破译法能经受住这一有效破译法的攻击。的攻击。68差分密码分析差分密码分析n差分密码分析是一种攻击迭代分组密码的选择明差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法。文统计分析破译法。n它不是直接分析密文或密钥的统计相关性，而是它不是直接分

48、析密文或密钥的统计相关性，而是分析明文差分和密文差分之间的统计相关性。分析明文差分和密文差分之间的统计相关性。n给定一个给定一个r轮迭代密码，对轮迭代密码，对n长明文对长明文对X和和X，定，定义其差分为义其差分为nX=X(X)-1 n 其中，其中，表示表示n比特组比特组X的集合中定义的群运算，的集合中定义的群运算，(X)-1为为X在群中的逆元。在群中的逆元。69差分密码分析差分密码分析n在密钥在密钥K作用下，各轮迭代所产生的中间密文作用下，各轮迭代所产生的中间密文差分为差分为 Y(i)=Y(i) Y(i)-1 0 i rni=0时，时，Y(0)=X，Y(0)=X， Y(0)= X。ni=r时，

49、时， Y= Y(r)，K(i)是第是第i轮加密的子密钥，轮加密的子密钥，Y(i)=f(Y(i-1), K(i)。n由于由于X X，因此，因此， Y(i) e(单位元单位元)。n每轮迭代所用子密钥每轮迭代所用子密钥K(i)与明文统计独立，且与明文统计独立，且可认为服从均匀分布。可认为服从均匀分布。70差分密码分析差分密码分析r 轮迭代分组密码的差分序列轮迭代分组密码的差分序列 Y(0)=X Y(1) Y(2) Y(r1) Y(r) Y(0)=X Y(1) Y(2) Y(r1) Y(r) f f f k(1) k(2) k(r) f f fX=Y(0) Y(1) Y(2) Y(r1) Y=Y(r)

50、71DES差分分析差分分析n输入一对输入一对X和和X，那么差分，那么差分X。同理，输出。同理，输出Y；n由于扩展置换由于扩展置换E和和P盒，那么盒，那么A和和C；n虽然无法知道虽然无法知道B和和B，但是，但是B = A；n对任意给定的对任意给定的A，C值不值不一定相同。将一定相同。将A和和C联合联合起来，可以猜测的起来，可以猜测的AKi及及AKi的位值，因为的位值，因为A和和A，故可推测，故可推测Ki的信息。的信息。XEXE(X)KiAS盒PYBCY72差分密码分析差分密码分析n 差分密码分析揭示出，迭代密码中的一个轮迭代函数差分密码分析揭示出，迭代密码中的一个轮迭代函数f，假设三元，假设三元

51、组组Y(i-1), Y(i), Y(i), Y(i)=f(Y(i-1), K(i), Y(i)=f(Y(i-1), K(i)，那么不难决定该轮密钥那么不难决定该轮密钥K(i)。n因此轮函数因此轮函数f的密码强度不高。如果密文对，且有方法得到上一轮的密码强度不高。如果密文对，且有方法得到上一轮输入对的差分，那么一般可决定出上一轮的子密钥输入对的差分，那么一般可决定出上一轮的子密钥(或其主要局部或其主要局部)。n在差分密码分析中，通常选择一对具有特定差分在差分密码分析中，通常选择一对具有特定差分的明文，它使最的明文，它使最后一轮输入对的差值后一轮输入对的差值Y(r-1)为特定值为特定值的概率很高。

52、的概率很高。n 73差分密码分析差分密码分析n差分密码分析的根本思想是在要攻击的迭代密码系统差分密码分析的根本思想是在要攻击的迭代密码系统中找出某高概率差分来推算密钥。中找出某高概率差分来推算密钥。n一个一个i轮差分是一轮差分是一(,)对，其中对，其中是两个不同明文是两个不同明文X和和X的差分，的差分，是密码第是密码第i轮输出轮输出Y(i)和和Y(i)之间的差之间的差分。分。n在给定明文的差分在给定明文的差分X条件下，第条件下，第i轮出现一对输轮出现一对输出的差分为出的差分为的条件概率称之为第的条件概率称之为第i轮差分概率，以轮差分概率，以 P(Y(i)=|X)表示。表示。74差分密码分析差分

53、密码分析n寻 求 第寻 求 第 ( r- 1 ) 轮 差 分轮 差 分 (,) 使 概 率使 概 率 P (Y ( r-1)=|X=)的值尽可能为最大。的值尽可能为最大。n随机地选择明文随机地选择明文X，计算，计算X使使X与与X之差分为之差分为，在，在密钥密钥k下对下对X和和X进行加密得进行加密得Y(r)和和Y(r)，寻求能使，寻求能使Y(r-1)=的所有可能的第的所有可能的第r轮密钥轮密钥K(r)，并对各子，并对各子密钥密钥Ki(r)计数，假设选定的计数，假设选定的X=，(X, X)对在对在ki(r)下产生的下产生的(Y, Y)满足满足Y(r-1)=，就将相应，就将相应Ki(r)的计的计数增

54、加数增加1。n重复第重复第2步，直到计数的某个或某几个子密钥步，直到计数的某个或某几个子密钥ki(r)的的值，显著大于其它子密钥的计数值，这一子密钥或这值，显著大于其它子密钥的计数值，这一子密钥或这一小的子密钥集可作为对实际子密钥一小的子密钥集可作为对实际子密钥K(r)的分析结果。的分析结果。75线性密码分析线性密码分析nRueppel1986的流密码专著中曾提出以最接近的的流密码专著中曾提出以最接近的线性函数逼近非线性布尔函数的概念，线性函数逼近非线性布尔函数的概念，Matsui推广推广了这一思想以最正确线性函数逼近了这一思想以最正确线性函数逼近S盒输出的非零盒输出的非零线性组合线性组合19

55、93，即所谓线性攻击，这是一种明文，即所谓线性攻击，这是一种明文攻击法。攻击法。n对明文对明文x密文密文y和特定密钥和特定密钥k，寻求线性表示式，寻求线性表示式n(ax)(by)=(dk) n 其中其中(a, b, d)是攻击参数。对所有可能密钥，此是攻击参数。对所有可能密钥，此表达式以概率成立。对给定的密码算法，使极大化。表达式以概率成立。对给定的密码算法，使极大化。76线性密码分析线性密码分析n假设条件假设条件n设明文分组长度和密文分组长度都为设明文分组长度和密文分组长度都为n n比特，密钥分组长度比特，密钥分组长度为为m比特；比特；n明文：明文：P1,Pn；密文：密文：P1,Pn；密钥：

56、密钥：K1,Km。n定义定义 Ai,j = Pi Pjn线性分析的目标线性分析的目标n找出有效的线性方程：找出有效的线性方程：Pi1,ia Cj1,jb = Kk1,kc；n上面的线性方程将得到一个位，这一位是将密钥的一些位进上面的线性方程将得到一个位，这一位是将密钥的一些位进行异或运算的结果。行异或运算的结果。77线性密码分析线性密码分析n方程成立的概率方程成立的概率p(如果如果p1/2，那么就可以使用该偏差，用，那么就可以使用该偏差，用得到的明文及对应的密文来猜测密钥的位值得到的明文及对应的密文来猜测密钥的位值)n如果如果p1/2，那么称该方程是有效的线性逼近；，那么称该方程是有效的线性逼

57、近；n如果如果|p-1/2|是最大的，那么称该方程是最有效的线性逼近。是最大的，那么称该方程是最有效的线性逼近。n设设N表示明文数，表示明文数，T是使方程左边为是使方程左边为0的明文数的明文数nT N / 2nKk1,kc = 0(p ) Kk1,kc = 1(p ) nT ) Kk1,kc = 0(p 1)为素数，如果为素数，如果p的因子只有的因子只有1,pn整数分解的唯一性：任一整数整数分解的唯一性：任一整数a (a1)可分解为假可分解为假设干素数的乘积设干素数的乘积n有限域上的多项式环有限域上的多项式环Fxn多项式多项式p(x) (deg(p)0)为不可约多项式，如果为不可约多项式，如果

58、p(x)的因子只有的因子只有c 和和 cp(x)，(其中其中c为常数为常数)n多项式分解的唯一性多项式分解的唯一性n 任一多项式任一多项式a(x) (deg(a)0)可分解为假设干不可可分解为假设干不可约多项式和一个常数的乘积。约多项式和一个常数的乘积。112素元和互素素元和互素n整数环整数环Zn设设c0，c是是a和和b的的最大公因子最大公因子, ,记为记为c=gcd(=gcd(a, ,b),),指指nc是是a的因子也是的因子也是b b的因子的因子na和和b的任一公因子也是的任一公因子也是c的因子的因子ngcd(gcd(a, ,b)=1,)=1,称为称为a, ,b互素互素n有限域上的多项式环有

59、限域上的多项式环Fxn设设c(x)最高项系数等于最高项系数等于1，c(x)是是a(x)和和b(x)的的最大公最大公因因式式，记为，记为c(x)=gcd=gcd(a(x), ,b(x), , 指指nc(x)是是a(x)的因子也是的因子也是b b(x)的因子的因子na(x)和和b(x)的任一公因子也是的任一公因子也是c(x)的因子的因子ngcd(a(x), ,b(x)=1,=1,称为称为a(x), ,b(x)互素互素112113同余和模运算同余和模运算n整数环整数环Z Zn设设n n是一正整数是一正整数,a,a是整数是整数, ,假设假设n a=qn+r, 0rn, a=qn+r, 0rn, 那么记

60、为那么记为 a mod n=r a mod n=rn假设假设n|(a-b)n|(a-b)，称，称a,ba,b模模n n同余，记为同余，记为ab (mod n)ab (mod n)nab (mod n) ab (mod n) 等价于等价于 (a mod n)=(b mod n) (a mod n)=(b mod n)n有限域上的多项式环有限域上的多项式环FxFxn设设n(x)n(x)是次数大于零的多项式是次数大于零的多项式,a(x),a(x)是多项式是多项式, ,假设假设n a(x)=q(x)n(x)+r(x), 0deg(r)deg(n), a(x)=q(x)n(x)+r(x), 0deg(r)deg