现代分组加密算法-DES.ppt

现代分组加密算法-DES,上海交通大学计算机系,第七讲 分组密码理论-DES,7.1 DES 7.2 IDEA 7.3 AES,7.1 数据加密标准（DES),DES的历史 1971 IBM，由Horst Feistel 领导的密码研 究项目组研究出LUCIFER算法。并应用于 商业领域。 1973美国标准局征求标准，IBM提交结果， 在1977年，被选为数据加密标准。,7.2 DES的描述,DES利用56比特长度的密钥K 分组长度64比特，密文64比特 算法分三个阶段实现： 1.对明文X，通过一个固定的初始置换IP得到X0。 X0=IP（X）=L0R0 分为左右两部分 2.函数F的16次迭代：LiRi(1=i=16） Li=Ri-1, Ri=Li-1 F(Ri-1, Ki) 其中Ki是长为48位的子密钥。子密钥K1，K2，K16是作为密钥K（56位）的函数而计算出的。 3.对比特串R16L16使用逆置换IP-1得到密文Y。 Y=IP-1（R16L16）,IP-初始置换,58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7,PC1,57, 49, 41, 33, 25, 17, 9, C Half 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, D Half 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4,S-box-1,0 1 2 3 4 5 6 7 8 9 a b c d e f COL S1 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,DES一轮加密的简图,Li-1 Ri-1,F,+,Li Ri,Ki,F（Ri-1, Ki）： 函数F有两个输入：32的消息A=R（32bits）作第一个输入，48比特的子密钥J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。 (1)对第一个变元A，先利用扩展函数E，扩展成48位E（A） (2)计算E（A）+J，结果写成8个6位串,B=b1b2b3b4b5b6b7b8 （3）使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取015的整数。给定长度为6个比特串，如 Bj=b1b2b3b4b5b6 计算Sj(Bj)如下：b1b6两个比特确定了Sj的行数, r(0=r=3); 而b2b3b4b5四个比特确定了Sj的列数c（0=c=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）, 得Cj=Sj(Bj)。 (4) 最后，P为固定置换。,对F函数的说明,DES 轮函数F（ ）,初始置换IP：对明文输入进行次序的打乱。 逆置换IP-1： 扩展函数E；（32到48） 置换函数P。,DES中使用的其它特定函数：,密钥K是长度为64的位串，56位参加子密钥编排。8位是奇偶校验位（为了检错），在密钥编排的计算中，不参加运算。 (1). 给定64位的密钥K，放弃奇偶校验位（8，16，64）并根据固定置换PC-1（见144页图4-4-9）来排列K中剩下的位。我们写 PC-1(K)=C0D0 其中C0由PC-1（K）的前28位组成；D0由后28位组成。,密钥K计算子密钥：,(2)对1=i=16，计算 Ci=LSi(Ci-1) Di=LSi(Di-1) LSi表示循环左移2或1个位置，取决于i的的值。i=1,2,9和16 时移1个位置，否则移2位置 Ki=PC-2(CiDi), PC-2为固定置 注：一共16轮，每一轮使用K生成的一个子密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如： 第7轮的表7：K7取K中的比特情况： 52 57 11 1 26 59 10 34 44 51 25 19 9 41 3 2 50 35 36 43 42 33 60 18 28 7 14 29 47 46 22 5 15 63 61 39 4 31 13 38 53 62 55 20 23 37 30 6,轮密钥编排,K,PC-1,C0 D0,LS1,LS1,C1 D1,LS2,LS2,LS16,LS16,C16 D16,PC-2,PC-2,K1,K16,14, 17, 11, 24, 1, 5, C half 3, 28, 15, 6, 21, 10, (bits 1-28) 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, D half 30, 40, 51, 45, 33, 48, (bits 29-56) 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 C half provides bits to S1-S4, D half to S5-S8,PC2,7.3 DES加密的一个例子,取16进制明文X：0123456789ABCDEF 密钥K为：133457799BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000 应用IP，我们得到： L0=11001100000000001100110011111111 L1=R0=11110000101010101111000010101010 然后进行16轮加密。 最后对L16, R16使用IP-1得到密文：85E813540F0AB405,7.4 DES的争论,DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。 S盒的设计准则： 1. S盒不是它输入变量的线性函数 2.改变S盒的一个输入位至少要引起两位的输出改变 3. 对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。,公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有陷门？）。 密钥长度是否足够？ 迭代的长度？（8、16、32？）,7.5 三重DES,7.5.1双重DES 加密 解密 问题：下式成立吗？,7.5.2 三重DES(Cont.),两个密钥的三重DES 目前，没有针对三重DES的攻击方法，它是一种较受欢迎的DES替代方案。,7.6 IDEA简介,瑞士的Xuejia Lai和James Massey于1990年 公布了IDEA密码算法第一版，称为PES (Proposed Encryption Standard)。为抗击 差分密码攻击，他们增强了算法的强度， 称IPES（Improved PES)，并于1992年改 名为IDEA（International Data ncryption Algorithm，国际数据加密算法。）,7.6.1 IDEA(Cont.),IDEA： 分组长度为64位 密钥长度为128位（抗强力攻击能力比DES强），同一算法既可加密也可解密。 IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：,7.6.2 IDEA简介(Cont.),异或运算（ ） 整数模216加（ + ） 整数模216+1乘（ ）(IDEA的S盒） 扩散由称为MA结构的算法基本构件提供。,Z6,F2,F1,Z5,G1,G2,7.6.3 IDEA简介(Cont.),实现上的考虑 使用子分组：16bit的子分组； 使用简单操作（易于加法、移位等操作实现） 加密解密过程类似； 规则的结构（便于VLSI实现）。,IDEA加密的总体方案图,循环2,循环8,循环1,输出变换,64位密文,64位明文,Z1,Z6,Z7,Z12,Z43,Z48,Z49,Z52,子密钥生成器,128位密钥,Z1,Z52,16,7.6.4 IDEA的密钥生产,56个16bit的子密钥从128bit的密钥中生成 前8个子密钥直接从密钥中取出； 对密钥进行25bit的循环左移，接下来的密钥就从中取出； 重复进行直到52个子密钥都产生出来。,IDEA的解密,加密解密实质相同，但使用不同的密钥； 解密密钥以如下方法从加密子密钥中导出： 解密循环I的头4个子密钥从加密循环10I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元； 对前8个循环来说，循环I的最后两个子密钥等于加密循环9I的最后两个子密钥；,7.6.5 IDEA简介(Cont.),IDEA是PGP的一部分； IDEA能抗差分分析和相关分析； IDEA似乎没有DES意义下的弱密钥； Bruce Schneier 认为IDEA是DES的最好替代，但问题是IDEA太新，许多问题没解决。,7.6.7先进分组密码的特点,可变密钥长度 混合操作 依赖数据的循环移位 依赖于密钥的循环移位 依赖密钥的S盒子 冗长的密钥调度算法 可变的F函数和可变的明文/密文长度 可变的循环次数 在每次循环中都对两半数据进行操作,7.7 AES候选算法,背景 DES已走到了它生命的尽头 56比特密钥实在太小 DES的软件实现效率低（设计主要针对硬件实现） 1997年4月15日美国国家标准和技术研究所（NIST）征集AES（AESAdvanced Encryption Standard）算法 并成立了AES工作组。 目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。,AES候选算法（续1）,要求 - 比三重DES快，至少还要一样的安全， - 应当具有128比特分组长度和256比特分组密钥长度（不过必须支持128和192比特的密钥） - 还应该具有较大的灵活性。,AES候选算法（续2）,评选过程中采用的方法 1.用量化的或定性的尺度作为选择的标准； 2.选择一种以上的算法； 3.选择一个备用算法； 4.考虑公众的建议以改进算法。,AES候选算法（续3）,1998年8月20日，NIST在第一阶段讨论（AES1）中宣布了由12个国家提出的15个候选算法 1999年3月开始的第二阶段讨论（AES2）， 1999年8月NIST选出5个算法候选: MARS、RC6、Rijndael、Serpent和Twofish。,AES候选算法-过程（续4）,在宣布最后的5个候选算法后，NIST再次恳请公众参与对这些算法的评论。公众对这五种候选算法的评阅期于2000年5月15日结束。NIST发布的AES主页2提供了大量的关于算法描述、源程序、有关AES3的论文以及其他公众评论的信息。2000年4月开始进行第三阶段（AES3）的评选，AES3共收到37篇提交给NIST的论文，并采用了其中的24篇。在这一阶段的讨论中，这些算法得到了非常深入的分析。NIST的AES小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。,AES候选算法-过程（续5）,经过长时间的评审和讨论之后，NIST在2000年5月宣布选择Rijndael作为AES的算法。该算法的开发者提出以下几种发音供选择“Reign Dah1“，“Rain doll“和 “Rhine Dah1“。,AES候选算法（续6）,结果 NIST最终选择了Rijndael作为AES的标准，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等优点。Rijndael使用非线性结构的S-boxes，表现出足够的安全余地；Rijndael在无论有无反馈模式的计算环境下的硬，软件中都能显示出其非常好的性能；它的密钥安装的时间很好，也具有很高的灵活性；Rijndael的非常低的内存需求也使它很适合用于受限的环境；,AES候选算法-结果（续）,Rijndael的操作简单，并可抵御时间和能量攻击，此外，它还有许多未被特别强调的防御性能；Rijndael在分组长度和密钥长度的设计上也很灵活，算法可根据分组长度和密钥长度的不同组合提供不同的迭代次数，虽然这些特征还需更深入地研究，短期内不可能被利用，但最终，Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。,7.8 分组密码工作模式,分组密码加密固定长度的年信息，eg. DES加密64-bit，使用 56-bit key 需要一种使用方法，加密任意长度的消