第4章-现代对称分组密码课件

现代对称分组密码张原 电子信息学院回顾上一讲的内容n古典密码代替密码n单字母密码n多字母密码置换密码n对称密码的两个基本运算代替和置换(Substitution&permutation)n对称密码分析的两个基本方法系统分析法（统计分析法）、穷举法n多轮加密n数据安全基于算法的保密内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用乘积密码(Product Ciphers)n因为语言的特征，用代替和置换规则构造的密码是不安全的n因此，可以考虑连续使用两个或两个以上的基本密码的方式来增强密码强度:两次代替可以构造一个更难于分析的代替两次置换可以构造一个更难于分析的置换代替之后在进行一次置换，可以构造一个强度更高的新密码n这是古典密码通往现代密码的桥梁乘积密码(Product Ciphers)n乘积密码就是以某种方式连续执行两个或多个密码以使得到的最后结果从密码编码的角度比其任何一个组成密码都强.n两个加密按它们加密的顺序连接进行合成时，要求第一个方法的密文空间与第二个方法的明文空间一致。n挫败基于统计分析的密码破译加密合成n两类方法的合成比单个方法更具有抗非法解密的能力?n这不一定都对，第二个方法可以部分或全部抵消第一个方法的作用。n如果合成的方法不满足交换性，而且其中之一与另一个还独立，则这一合成是有效的。n比如换位，执行一次“扩散”，多字母代替，执行一次“混乱”，不是一个群，因此可以被重复而且其组合复杂度进一步增加。等于是扩大了密钥空间。转子机（Rotor Machines）n在现代密码之前，转子机是最普遍的乘积密码n在第二次世界大战中得到广泛应用 German Enigma,Allied Hagelin,Japanese Purplen实现了一个非常复杂的可变的代替密码n使用一系列的转子，每一个状态给定一种代替表，每加密一个字母，转子转一格，代替表就变一个n3 个转子可以产生263=17576 代替表转子机Rotor machine置换密码l换位密码把明文按行写入,按列读出l密钥包含3方面信息:行宽,列高,读出顺序key:4 3 1 2 5 6 7plaintext:a t t a c k po s t p o n ed u n t i l t w o a m x y zciphertext:TTNAAPTMTSUOAODWCOIXPETZl完全保留字符的统计信息l使用多轮加密可提高安全性多次置l多次置换，减少结构性排列，不易于重构。置换密码分析内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用DES的产生背景 美国国家标准局（NBS）1973 年公开征求计算机加密算法标准，要求如下：该算法必须提供较高的安全性；该算法必须完全确定并且易于理解；该算法的安全性不应依赖于算法本身，而是应该依赖于密钥；该算法必须对所有的用户有效；该算法必须适用于各种应用；该算法必须能够通过价格合理的电子器件得以实现；该算法必须能够有效使用；该算法必须能够得以验证；该算法必须能够得以出口出口。数据加密标准（DES）HISTORYn1974年8月27日,NBS开始第二次征集nIBM提交了算法 Lucifer cipherby team led by Feistelused 64-bit data blocks with 128-bit keyn1977 年正式颁布为数据加密标准（DES-Data Encryption Standard）。n1979 年，美国银行协会批准使用 DES。n1980 年，DES 成为美国标准化协会(ANSI)标准。n1984 年，ISO 开始在 DES 基础上制定数据加密的国际标准，称之为DEA-1。n美国国家安全局NSA每五年对该算法进行评估，1994年，决定1998年12月之后不再使用DES。n现已由采用Rijndael算法的高级加密标准AES取代。内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用分组密码与流密码n流密码加密过程是将信息流分为基本的信息单位，然后与相应的密钥流作运算从而掩盖明文信息。n分组密码与之不同的是将明文编码表示后的数字序列，划分成等长的组，在密钥的作用下变换成等长的输出序列。解密时，将加密后的分组与相同的密钥相互作用而得到明文信息。分组密码的特点n 分组密码与流密码的不同之处在于，分组密码输出的每一位数字不是只与相应时刻输入的明文数字有关，而是还与一组长为m的明文数字有关。n在密钥相同下，分组密码对长为m的输入明文所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。n分组密码易于标准化和易于实现；n不善于隐藏明文的数据模式，可以离线操作，对于重放、插入、删除等攻击方式的抵御能力不强。(时间无关)分组密码的长度明文为分组长度为m的序列，密文为分组长度为n的序列：nnm，称其为有数据扩展的分组密码；nn密文的映射方法），为表示任一特定代替所需的二元数字位数为：lb(2n!)(n-1.44)2n=O(n2n)(bit)即密钥长度达n2n位。n=4,424=64n=64,64264=270 1021位分组长度n要足够大，防止明文穷举攻击。分组密码的一般设计原理-ivDES的密钥长度仅为56位，AES的密钥长度为128/196/256分组密码的设计问题在于找到一种算法，能在密钥的控制之下，从一个足够大而且能在密钥的控制之下，从一个足够大而且足够好的代替子集中，简单而迅速地选取足够好的代替子集中，简单而迅速地选取出一个代替。出一个代替。分组密码的一般设计原理-v分组长度足够大 密钥量足够大，能抵抗密钥穷举攻击，但 又不能过长，以利于密钥管理由密钥确定代替的算法要足够复杂，能抵抗各种已知攻击分组密码设计原则Shannon指出：理想的密码中理想的密码中，密文的统计特性独立于密钥。1949年Shannon提出了保证实际密码实际密码安全的两个基本原则：混乱混乱（Confusion）和扩散扩散（Diffusion）原则。混乱原则：为了避免密码分析者利用明文和密文明文和密文之间的依赖关系之间的依赖关系进行破译，密码的设计应保证这种依赖关系足够复杂。需要非线性非线性代换算法。扩散原则：为避免密码分析者对密钥逐段破译密钥逐段破译，密码的设计应保证密钥的每位数字能够影响密文中的多位数字。同时，为了避免密码分析者利用明文的统计特性，密码的设计应该保证明文的每明文的每位数字能够影响密文中的多位数字位数字能够影响密文中的多位数字，从而隐藏明文的统计特性。Shannon and Substitution-Permutation Ciphersn1949 Shannon 提出了代替置换网络的思想substitution-permutation(S-P)networks modern substitution-transposition product ciphern这是构成现代分组密码的基础nS-P 网络基于密码学的两个基本操作：substitution(S-box)permutation(P-box)n提供了消息的扩散与混乱实现方法的设计原则n软件实现的要求：使用子模块：密码运算在子模块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。使用简单的运算。在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用标准处理器所具有的一些基本指令，如加法、乘法、移位等。n硬件实现的要求：能够采用同样的器件同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用简化的DESnSimplified DES方案，简称S-DES方案。n分组长度8位，密钥长度10位n加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和代替的运算。(3)转换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1加密算法的数学表示nIP-1fk2SWfk1IP也可写为密文=IP-1fk2(SW(fk1(IP(明文)其中K1=P8(移位(P10(密钥K)K2=P8(移位(移位(P10(密钥K)n解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文)S-DES的密钥生成exampleS-DES加密操作内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用Feistel分组加密算法结构之动机分组加密算法，一一映射（加密是可逆的）当n较小时，等价于代替变换当n较大时，比如n=64，无法表达这样的任意变换。Feistel结构很好地解决了二者之间的矛盾Feistel分组加密算法结构之思想基本思想：用简单算法的乘积来近似表达大尺寸的替换变换乘积密码就是以某种方式连续执行两个或多个密码，以使得所得到的最后结果或乘积从密码编码的角度比其任意一个组成密码都更强。交替使用代替和置换(permutation)混乱(confusion)和扩散(diffusion)概念的应用Feistel密码结构 Feistel结构定义n加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)n解密:Ri-1=LinLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel加密与解密基于Feistel结构的密码算法设计分组大小。越大安全性越高，但速度下降，64比特较合理密钥位数。越大安全性越高，但速度下降，64比特广泛使用，但现在已经不够用128循环次数。越多越安全，典型16次子钥产生算法。算法越复杂，就增加密码分析的难度round轮函数。函数越复杂，就增加密码分析的难度快速软件实现，包括加密和解密算法易于分析。便于掌握算法的保密强度以及扩展办法。内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用DES的描述nDES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文DES加解密过程DES示意图n输入的明文首先经过一个初始置换IP，将明文分为左半部分和右半部分，各长32位。然后进行16轮完全相同的运算，即图中的f函数。在这些函数中，数据与密钥结合起来从而隐藏了密文，最后左、右半部分合在一起经过一个末置换IP-1（初始置换的逆置换），就完成了密文的生成。初始置换IP和IP-1n同S-DES（简化的DES）相同，DES在算法的开始和结束部分增加了两个置换操作。n目的增加算法的抗分析能力。输入（64位）58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7输出（64位）初始变换IPL0（32位）R0（32位）置换码组 输入（64位）40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25输出（64位）逆初始变换IP-1初始置换IP和IP-1(互逆)M20 M14M14M20一轮DES左32位右32位Li-1Ri-1扩展置换E48位(明文)64位密钥作第i次迭代的计算机子密钥Ki密钥程序表48位(密钥)8组6位码S1S2S8模2加选择函数输入：6位输出：4位+32位置换32位32位LiRi左32位右32位Ri-1Li-1模2加+.+乘积变换中的一次迭代DES:Function F扩展置换的作用n它产生了与密钥同长度的数据进行异或运算n它产生了更长的结果，使得在代替运算时能进行压缩(增加复杂性)n输入的一位将影响两个替换（例如第一位输入，存在于第一个和第8个子分组中，每个子分组分别进行S盒替换），所以输出对输入的依赖性将传播得更快，明文或密钥的一点小的变动应该使密文发生一个大的变化.这叫雪崩效应。（avalanche effect）S-Box对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定16列中的相应列，行、列交叉处的十进制数转换为二进制数后，4位二进制数表示作为输出。S-盒的构造（S6）P-盒置换16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 2557 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 33 15 7 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 4置换选择1密钥（64位）C0(28位)D0(28位)DES的解密过程n采用与加密相同的算法。n以逆序（即 ）使用密钥。第一圈用第16个子密钥K16，第二圈用K15，其余类推。不同微处理器上的DES软件实现速度 处理器处理器速度（MHz）每秒处理的DES分组个数80884.7370680007.69008028661,10068020163,50068030163,90080286255,000680305010,000680402516,000680404023,000804866643,000采样专业硬件速度可达千万分组/S内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问弱密钥n初始密钥被分成两部分，每部分都单独做移位。如果每一部分的每一位都是0或都是1，则每一圈的子密钥都相同。这样的密钥被称为弱密钥。n弱密钥的定义：若k使得加密函数与解密函数一致，则称k为弱密钥。nEK(EK(p)=pnDES存在4个弱密钥半弱密钥n有些成对的密钥会将明文加密成相同的密文，即一对密钥中的一个能用来解密由另一个密钥加密的消息，这种密钥称作半弱密钥。这些密钥不是产生16个不同的子密钥，而是产生两种不同的子密钥。n半弱密钥：对于密钥 k，存在一个不同的密钥 ，满足 。n至少有12个半弱密钥。对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问互补密钥n将密钥的0换成1，1换成0，就得到该密钥的补密钥。如果用原密钥加密一组明文，则用补密钥可以将明文的补码加密成密文的补码。nDES算法具有互补性，即：若 、是 的补、是 的补，则 。证明-in对于一位的A和B有下的真值表，n因此，对于任何等长的A和B，有(AB)=AB,AB=AB证明-ii如果明文和密钥取补(A、B、K)，相当于第一个XOR的输入也取补，这样输出和没有取补时一样F(B,K)，进一步我们看到对于第二个XOR的输入只有一个取补了，因此输出A F(B,K)（A F(B,K)(AB)=AB,AB=AB互补密钥对穷举式攻击的影响n在一个选择明文攻击选择明文攻击中，如果选择明文X,攻击者可以得到Y1=EKX 和 Y2=EKX,那么穷举式攻击只需要进行255次加密，而不是256次.n注意到(Y2)=EK X，现在选取一个测试密钥T,计算ETX.如果结果是Y1,T是正确的密钥.如果结果是(Y2),T 是正确的密钥.如果都不是，我们就通过一次加密否定了两个基本密钥。对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问DES的破译：分组密码的分析方法n根据攻击者所掌握的信息，可将分组密码的攻击分为以下几类：唯密文攻击已知明文攻击选择明文攻击n攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量分组密码的典型攻击方法n最可靠的攻击办法：强力攻击n差分密码分析：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。选择明文攻击，需要247个选择明文n线性密码分析：本质上是一种已知明文攻击方法，通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统，需要247个已知明文n插值攻击方法n密钥相关攻击强力攻击n穷尽密钥搜索攻击:唯密文：用2k个密钥对密文解密，看明文是否有意义已知(选择)明文：用2k个密钥对明文加密,看明密文是否相同n字典攻击：明密文对编成字典,得到密文后在字典中查找对应的明文，需2n个明文-密文对。n查表攻击：是选择明文攻击,给定明文,用所有的2k个密钥,预计算密文,构成密文密钥表，得到密文后在表中查找对应的密钥。（某些协议中会出现固定的短语）DES的破译n1990年，以色列密码学家Eli Biham和AdiShamir提出了差分密码分析法，可对DES进行选择明文攻击。nIBM声称1974年就知道该方法，因此在S盒和P盒的设计中做了考虑，差分方法对8轮DES需214个选择明文，对其他分组密码算法更有效。n线性密码分析比差分密码分析更有效n强力攻击：平均255次尝试n差分密码分析法：使用247对明密文的选择明文攻击n线性密码分析法：使用247对明密文的已知明文攻击对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问密钥长度n关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有256 1017个n早在1977年，Diffie和Hellman已建议制造一个每微秒能测试100万个密钥的VLSI芯片。每微秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。nHellman提出通过空间和时间的折衷，可以加速密钥的寻找过程。他建议计算并存储256种用每种可能密钥加密一段固定明文的结果。估计机器造价500万美元。密钥长度n1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。n1998年7月电子前沿基金会（Electronic FrontierFoundation）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES。n1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问DES的轮数nFeistel密码的编码强度来自于：迭代轮数、函数F和密钥使用的算法。n一般来说，循环次数越多进行密码分析的难度就越大。一般来说，循环次数的选择准则是要使已知的密码分析的工作量大于简单的穷举式密钥搜索的工作量。n对于16个循环的DES来说，差分密码分析的运算次数为255.1，而穷举式搜索要求255，前者比后者效率稍低，如果DES有15次循环，那么差分密码分析比穷举式搜索的工作量要小。对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问函数FnFeistel密码的核心是函数F，函数F依赖于S盒的使用。n函数F 作用：给Feistel密码注入了混淆的成分。nF是非线性的，是DES中唯一的非线性成分。n函数F设计的雪崩准则（输入的一位变化引起输出的很多位变化严格雪崩准则SAC（Strict avalanche criterion)：对于任何的i,j，当任何一个输入比特i变化时，一个S盒子的任何输出比特j变化的概率为1/2。比特独立准则BIC(bit independence criterion)：对于任意的i,j,k，当任意一个输入比特i变化时，输出j和k应当独立地变化。DES的雪崩效应-iDES的雪崩效应-ii对DES的讨论n弱密钥与半弱密钥n互补密钥nDES的破译n密钥长度的争论nDES的轮数n函数FnS-盒的疑问盒的疑问S-盒的构造要求nS-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度n提供了密码算法所必须的混乱作用n如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题n非线性度、差分均匀性、严格雪崩准则、没有陷门S-Box问题-inS-Box的设计细节，NSA和IBM都未公开过。n70年代中Lexar公司和Bell公司都对S-Box进行了大量研究，她们都发现了S-Box有一些不能解释的特征，但并没有找到弱点。nLexar结论：“已发现的DES的结构毫无疑问增强了系统抗击一定攻击的能力，同时也正是这些结构似乎削弱了系统抗攻击的能力。”（S-Box不是随机选取的）nBell结论：S-Box可能隐藏了陷门。S-Box问题-iin1976年美国NSA提出了下列几条S盒的设计准则：没有一个S盒是它输入变量的线性函数S盒的每一行是整数0，15的一个置换改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于0,1,S(X)S(X11ef00)对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，使这个输出比特为0的输入数目将接近于使这个输出比特为1的输入数目。S-Box问题-iiin在差分分析公开后，1992年IBM公布了S-盒和P-盒设计准则。没有一个S盒是它输入变量的线性函数S盒的每一行是整数0，15的一个置换改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于0,1,S(X)S(X11ef00)对于任何输入之间的非零的6位差值，具有这种差值的输入中32对中有不超过8对的输出相同。S盒子的设计n从本质上说，希望S盒子输入向量的任何变动在输出方都产生看似随机的变动。这两种变动之间的关系是非线性的并难于用线性函数近似。nS盒的设计方法：随机产生：s盒较小时不太理想带测试的随机产生人工产生：利用简单的数学原理，配合手工方法，DES就是利用这种方法设计。用数学方法：安全性高内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用分组密码的工作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)n计数器CTR(counter)电子密码本（ECB）n重要特点：在给定的密钥下，相同的明文总是对应相同的密文。n名称的由来：对给定的密钥，任何64位的明文组只有唯一的密文与之对应，可以想像存在一个很厚的密码本，根据任意64位明文可以查到相应的密文。n使用方法：若明文长度大于64位，可将其分为64位分组，必要时可对最后一个分组进行填充。电子密码本（ECB）ECB的的特点简单和有效可以并行实现不能隐藏明文的模式信息相同明文 相同密文同样信息多次出现造成泄漏对明文的主动攻击是可能的（提款）信息块可被替换、重排、删除、重放误差传递：密文块损坏 仅对应明文块损坏适合于传输短信息：加密密钥分组密码的工作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)n计数器CTR(counter)密码分组链接（CBC）n目点：消除电子密码本ECB 模式的缺点。模式的缺点。n相同的明文加密成不同的密文。相同的明文加密成不同的密文。n密码算法的输入是当前的明文组和上一个密文组的异或。n相当于每个明文异或一个初始化向量的ECB密码分组链接（CBC）CBC特点n没有已知的并行实现算法n能隐藏明文的模式信息：相同明文 不同密文n需要共同的初始化向量IVnIV需要保密：初始化向量IV可以用来改变第一块n对明文的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递：密文块损坏 两明文块损坏n安全性好于ECBn适合于传输长度大于64位的报文，是大多系统的标准如SSL、IPSec分组密码的工作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)n计数器CTR(counter)密码反馈CFBn在密码分组链接CBC模式下，整个数据分组在接受完成之后才能进行加密。n例如：某些安全的网络环境中，可能需要当从终端输入时，必须把每个字符实时加密传给主机，这种方式CBC无法满足。nCFB:分组密码 流密码CFB加密示意图CFB解密示意图CFB特点n相当于自同步序列密码n分组密码 流密码n隐藏了明文模式n需要共同的移位寄存器初始值IVn对于不同的消息，IV必须唯一：如果第三方知道了先前的EK(IV)，则可恢复P1n误差传递：明文的一个错误会影响后面所有密文。密文的1位错误会引起对应明文的1位错误，同时密文进入移位寄存器后，会引起其后多个明文单元的错误。流密码的分类n依据状态转移函数 与输入明文有无关系分类，也即系统状态 与明文信息 的关系来划分：n同步流密码：与明文信息无关，即密码流独立于明文。n自同步流密码：与明文信息有关，不仅与当前输入有关，而且与以前的输入历史 有关。分组密码的工作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)n计数器CTR(counter)输出反馈OFBn同CFB模式非常相似nOFB:分组密码 流密码OFB加密示意图OFB解密示意图OFB特点n相当于同步序列密码nOFB:分组密码 流密码n隐藏了明文模式n对于不同的消息，IV必须唯一n误差传递：传输过程中一个密文单元的错误只影响对应明文单元n对明文的主动攻击是可能的密文的某位取反，恢复的明文相应位也取反信息块可被替换、重放n安全性较CFB差n在明文存在之前可以进行离线工作分组密码的工作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)n计数器CTR(counter)计数器模式Counter(CTR)n很早之前就提出，但在ATM网络安全和IPSec中的广泛应用才引起注意nCTR:分组密码 流密码n与OFB 类似，但使用加密计数器值，而不是反馈值n必须对每一个明文使用一个不同的计数器值n加解密方式：Ci=Pi XOR Oi（取Oi 与Pi长度相同的位数）Oi=DESK(i)n应用于高速网络加密计数器模式Counter(CTR)CTR特点nCTR:分组密码 流密码n有效性：可以并行实现可以预处理适用于高速网络n可以随机访问加密的数据分组n隐藏了明文模式，与CBC模式一样安全n可以处理任意长度的消息n误差传递：一个单元损坏只影响对应单元n对明文的主动攻击是可能的n信息块可被替换、重放内容提要n乘积密码nDES的产生与应用n分组密码的设计原理与方法n简化的DESnFeistel密码结构n对DES的描述n对DES的讨论n分组密码的工作模式nDES密码的应用DES密码的应用n由于DES在穷举攻击下相对比较脆弱，因此一般不能简单使用DES进行加密处理，需要某种算法进行替代，这里通常有两种方案：一种是利用全新的算法。另一种是为保护对使用DES的已有软件和硬件的投资，采用多个密钥的多个多次DES加密。n应用最广泛的是：三重DES加密双重DES(Double DES)双重DES的讨论中间相遇攻击n对双重DES有：n攻击过程：给定明文密文对(P,C)1、首先用K1的所有256个密钥加密P，对结果按X的值排序保存在表T中。2、用K2的所有256个密钥解密C，每解密一次，就将解密结果与T中的值比较，如果有相等的，就用用刚测试的两个密钥对刚测试的两个密钥对P加密，若结果为加密，若结果为C，则这两，则这两个密钥个密钥可能可能是正确的密钥。是正确的密钥。对双重DES的中间相遇攻击的分析n二重DES所用密钥的长度应是112bits，所以密钥空间为2112，也就是选择密钥有2112个可能性。即一个明文P有2112种方式映射到密文空间n对于任意给定的一个明文P，经二重DES加密后可能得到264个密文中的一个。即一个明文P有264个变换结果。n于是对给定一个明文P，可加密成密文C的密钥个数为2112/264=248。也就是对一个(P,C)对将产生248个错误的结果。2112264密文分组明文分组明文分组密文分组264对双重DES的中间相遇攻击的分析n给定两个明密文对,虚警率降为248-64=2-16。因为对第一个明密文对成立的密钥K，使第2个(P,C)成立的概率为1/264。换句话说，对已知2个明文-密文对的中间相遇攻击成功的概率为1-2-16。n攻击用的代价加密或解密所用运算次数 2 256，比攻击单DES所需的255多不了多少。n需要大量的存储器:256 64=1017字节，例如对128位密钥，中间攻击需要1039字节，如果一位信息对应一个铝原子，1039字节需要一立方公里的铝。Triple-DES的四种模型n对付中间攻击的一个方法是使用三重对付中间攻击的一个方法是使用三重DESnDES-EEE3：三个不同密钥，顺序使用三次加密算法nDES-EDE3：三个不同密钥，依次使用加密-解密-加密算法nDES-EEE2：K1=K3，同上nDES-EDE2：K1=K3，同上双密钥的三重DES对双密钥的三重DES的分析n该模式由IBM设计,可与常规加密算法兼容n这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（The Key Manager StandardsANSX9.17和ISO8732).n交替使用K1和K2可以抵抗中间相遇攻击C=EK1(DK2(EK1(P)，如果C=EK2(EK1(EK1(P),可以采用中间攻击，只需要256+2次加密n目前还没有针对两个密钥三重DES的实用攻击方法。但对两个密钥三重DES的攻击有一些设想，以这些设想为基础将来可能设计出更成功的攻击技术。三密钥的三重DES三密钥的三重DES分析n密钥的有效长度为168位n与DES的兼容性可以通过令K3=K2或K1=K2得到n许多基于Internet的应用里用到：PGP和S/MIME（Secure/Multipurpose Internet Mail Extension)