网络信息安全

1、网络信息安全分组密码1 DES加密算法的背景发明人：美国IBM公司W. Tuchman 和 C. Meyer 1971-1972年研制成功。基础：1967年美国Horst Feistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。2DES加密算法的背景美国国家安全局（NSA, National

2、 Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。3DES的产生-i1973年5月15日, NBS开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所

3、有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的4DES的产生-ii1974年8月27日, NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在19711972年研制1975年3月17日, NBS公开了全部细节1976年,NBS指派了两个小组进行评价1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构1977年1月15日,“数据加密标准”FIPS PUB 46发布5DES的应用1979年，美国银行协会批准使用1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（

4、ANSI X.392） 1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。 6分组密码的一般设计原理分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列， 7两个基本设计思想 Shannon称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立 扩散（Diffusion):明文的统计结构被扩散消失到密文的长度统计特性 ,

5、使得明文和密文之间的统计关系尽量复杂 混乱(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂 8分组密码实现的设计原则1 1.要有足够大分组长度n 2.密钥空间要尽可能大 3.保证足够强的密码算法复杂度 4.软件实现尽量采用子块和简单运算。 5.硬件实现最好加密与解密用同样结构，以适应用超大规模集成芯片实现。 9设计原则要求 软件实现的要求：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用处理器的基本运算，如加法、乘法、移位等。10实现

6、的设计原则 硬件实现的要求：加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。11Feistel结构图12Feistel结构定义加密: Li = Ri-1; Ri = Li-1 F(Ri-1,Ki)解密: Ri-1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)13Feistel结构分析块大小(64 128).密钥大小(56 128256).轮数(16).子密钥生成. 轮函数(F).软件加密/解密速度快.硬件实现容易.结构简单.分析

7、容易.14DES示意图15DES: 单轮结构Li = Ri-1 Ri = Li-1F(Ri-1,Ki)16DES:轮函数F扩展: 32 48S-box: 6 4置换:P17DES:子密钥生成18DES的描述DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES算法框图交换左右32比特 1964位码64位码初始变换逆初始变换乘积变换明文密文输入输出IPIP-120输入（64位）58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54

8、 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位）21置换码组 输入（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 273

9、4 2 42 10 50 18 58 2633 1 41 9 49 17 57 25输出（64位）逆初始变换IP-122 DES加解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数。DES的加密和解密过程表示如下。加密过程：L0R0=IP(64bits明文) Li=Ri-1; Ri=Li-1 f(Ri-1,ki);(64bits密文)=IP-1(R16L16)解密过程： L16R16=IP(64bits密文) Ri-1=Li; Li-1=Ri-1 f(Ri-1,ki);(64bits明文)=IP-1(R0L0)23初始置换IP和初始逆置换IP1 24Li-1（32比特）Ri-1（32比特

10、）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代25左32位右32位Li-1Ri-1扩展48位(明文)64位密钥作第i次迭代的计算子密钥Ki48位(密钥)8组6位码S1S2S8模2加选择函数输入：6位输出：4位2632位置换32位LiRi左32位右32位Ri-1Li-1乘积变换中的一次迭代271234567891011.29303132321234545678989101112131213141516171617181920212021222324252425262728292

11、8293032321Ebox选择扩展运算28选择压缩运算29S-Box-i30S-Box-ii31S-Box对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。其中相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，其中的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。 32 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0

12、 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S10 0 1 0输入6位：101100输出4位使用选择函数S1的例子0110331234567891011.29303132Pbox1672021291228171152326518311028241432273919133062211425Pbox置换34子密钥的产生3557 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 5

13、1 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位)36Ci(28位)Di(28位)14 17 11 24 1 5 3 28 15 6 21 1023 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 32Ki(48位)置换选择237置换选择1（PC-

14、1）和置换选择2（PC-2） 38对DES的讨论F函数(S-Box)设计原理未知密钥长度的争论DES的破译 弱密钥与半弱密钥39S-Box问题1976年美国NSA提出了下列几条S盒的设计准则：1. S盒的每一行是整数0，15的一个置换2. 没有一个S盒是它输入变量的线性函数3.改变S盒的一个输入位至少要引起两位的输出改变4.对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）40S-Box问题5.对任何一个S盒，对任何一个输入对e,f属于0,1,S(X) S(X11ef00)6. 对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特

15、的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目。41密钥长度关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个 早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。 在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个

16、芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。421997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。

17、43DES的破译1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击。线性密码分析比差分密码分析更有效 441.弱密钥与半弱密钥弱密钥: EKEK = I，DES存在4个弱密钥451.弱密钥与半弱密钥半弱密钥: EK1=EK2，至少有12个半弱密钥46DES设计原理重复交替使用选择函数S和置换运算P两种变换（confusion + diffusion)使用Feistel方法+K1+K2+Kn472.对DES的S盒疑义 算法的公开性与脆弱性DES的两个主要弱点：密钥容量：56位不太可能提供足够的安全性S盒：可能隐含有陷井（Hidden

18、 trapdoors）DES的半公开性：S盒的设计原理至今未公布(3) DES的有效密钥位数和迭代次数缺陷 48DES算法存在的问题与挑战强力攻击：255次尝试差分密码分析法：247次尝试线性密码分析法：243次尝试49对DES攻击结果及其启示1997年1月28日美国RSA数据安全公司悬赏“秘密密钥挑战”竞赛48位的RC5 313小时/3500台计算机1997年3月13日Rocke Verser设计一个攻击程序（DESCHALL），参加的志愿者有78516个，第96天（6月17日晚10：39）Michael Sanders破译成功，获1万美圆奖金。搜索量为24.6%。50密钥长度(bit)穷举

19、时间4078秒485 小时5659天6441年7210，696年802，738，199年88700，978，948年96179，450，610，898年11211，760，475，235，863，837年128770，734，505，057，572，442，069年DESCHALL搜索速度估算51双重 DES C = EK2(EK1(P) P = DK1(DK2(C)52双重 DES安全性中间相会(meet-in-the-middle)攻击 C = EK2(EK1(P) X = EK1(P) = DK2(C)给定明文密文对(P,C) 对所有256个密钥,加密P,对结果排序 对所有256个密钥,

20、解密C,对结果排序 逐个比较,找出K1,K2使得EK1(P) = DK2(C)一个明文密文对,误警次数2112/264=248两个明文密文对,误警次数248/264=2-1653三重 DESC=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C)54三重 DES分析With two keys: C=EK1(DK2(EK1(P)256可选择明文256次计算 With three keys: C=EK3(DK2(EK1(P)比two-key更安全Tripe DES速度慢55多重DESDES是否构成一个闭合群? 任给K1,K2,是否存在K3,使得:EK1EK2 = EK3Double D

21、ESTriple DES56国际数据加密IDEA（InternationalData Encryption Algorithm)算法1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节. 设计目标从两个方面考虑 加密强度 易实现性 强化了抗差分分析的能力， PGP57IDEA算法特点58IDEA设计思想1.得到confusion的途径 按位异或 以216(65536)为模的加法 以216+1 (65537)为模的乘法 互不满足分配律、结合律2.得到diffusion的途径 乘加(MA)结构3.实现上的考虑 软件和硬件实现上的考虑59IDEA加密算法60IDEA

22、每一轮61IDEA输出变换阶段62IDEA的子密钥63AES介绍1997年NIST宣布征集AES算法要求: 与Tripe DES比要快且至少一样安全,分组128位,密钥128/192/256位1998年确定第一轮15个候选者1999年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofish2000年底Rijndael成为胜利者64Rijndael简介1.不属于Feistel结构2.加密、解密相似但不对称3.支持128/192/256(/32=Nb)数据块大小4.支持128/192/256(/32=Nk)密钥长度5.结构简单6.速度快6566676869

23、Rijndael结构SubKeyPlaintext BlockKeyAddSubstitutionShiftrowMixcolumnSubKeyKeyAddFinal RoundSubstitutionShiftrowKeyAddSubKeyPlaintext BlockyesNo70717273747576777879808182838485868788有限域GF(28)(一)字节b=b7b6b5b4b3b2b1b0看成系数属于0,1的多项式: b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如:A7 10100111 x7+x5+x2+x+1加法: 0,1上加法(等

24、价于按位XOR)乘法: 多项式模乘,模为(11B):m(x) = x8+x4+x3+x+1如: (x7+x6+x+1)(x5+x+1)=x12+x11+x5+x2+1 =x6+x4+x2+x mod (x8+x4+x3+x+1)m(x)不可约89有限域GF(28)(二)对次数低于8的b(x)(非0),扩展Euclid算法可计算出a(x),c(x)使得: b(x)a(x)+m(x)c(x)=1 b(x)a(x)=1 mod m(x) b-1(x)=a(x) mod m(x)集合0255构成有限域GF(28)GF(28)上b(x)乘x(02): 记作xtime(b)xb(x)=b7x8+b6x7+

25、b5x6+b4x5+b3x4+b2x3+b1x2+b0 x若b7为0,则从字节上看是一个左移位;否则,还需要减去m(x),从字节上看是与1B作XOR.90有限域GF(28)上多项式4-byte向量GF(28)元素为系数多项式(4次)加法: 对应系数的加法(XOR)乘法: 多项式模乘, M(x)=x4+1xj mod M(x) = xj mod 4 a(x)= a3x3+a2x2+a1x+a0, b(x)= b3x3+b2x2+b1x+b0 d(x) = a(x)b(x) = d3x3+d2x2+d1x+d0 mod M(x) |d0| |a0 a3 a2 a1| |b0| |d1| |a1 a

26、0 a3 a2| |b1| |d2| = |a2 a1 a0 a3| |b2| |d3| |a3 a2 a1 a0| |b3|xb(x) = b3x4+b2x3+b1x2+b0 x = b2x3+b1x2+b0 x+b3 即按字节循环左移位.91Rijndael简介(续)数据/密钥的矩阵表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12

27、 12 14Nk=8 14 14 14Number of rounds92Rijndael: overview首轮前执行AddRoundKey(State,RoundKey)Round(State,RoundKey) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); FinalRound(State,RoundKey) ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey); 93Rijndael: AddRoundKey按字节在

28、GF(28)上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b3594Rijndael: ByteSubByteSub(S-box)非线性、可逆独立作用在每个字节上先取乘法的逆,再经过GF(2)上一个仿射

29、变换a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij95Rijndael: ShiftRow第一行保持不变,其他行内的字节循环移位96Rijndael: MixColumn示意图列作为GF(28)上多项式乘以多项式c(x)模M(x) = x4+197Rijndael: MixColumn多项式c(x) = 03x3+ 01x2+ 01x

30、+ 02M(x) = x4+1=(x2+1)(x2+1)c(x)与模M(x) = x4+1互素b(x)=c(x)a(x) |b0| |02 03 01 01| |a0| |b1| |01 02 03 01| |a1| |b2| = |01 01 02 03| |a2| |b3| |03 01 01 02| |a3|c(x)的逆: 0Bx3+ 0Dx2+ 09x+ 0E98Rijndael: AddRoundKey按字节在GF(28)上相加a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k

31、02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b3599Rijndael: Key schedule(1)主密钥生成子密钥数组, (Nr+1)*Nb个字Nk=6KeyExpansion(byte Key4*Nk, word WNb*(Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i

32、=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp6KeyExpansion(byte Key4*Nk, word WNb*(Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp8)Rconi/Nk; else if(i%Nk = 4) temp=ByteSub(temp8); Wi=Wi-Nktemp; ; ;Rco

33、ni=(xi, 00 , 00 , 00); xi为GF(28)上的数.101Rijndael: encrypt structureRijndael(State,CipherKey) KeyExpansion(CipherKey, ExpandedKey); AddRoundKey(State, ExpandedKey) For(i=1;iNr;+i) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,ExpandedKey+Nb*i); ByteSub(State); ShiftRow(State); AddRoundKey(State, ExpandedKey+Nb*i); 102Rijndael: decrypt structureAddRoundKey()For(i=1;iNr;+i) ByteSub();ShiftRow();MixColumn();AddRoundKey() ByteSub();ShiftRow();AddRoundKe