《分组密码理论》PPT课件.ppt

《《分组密码理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《分组密码理论》PPT课件.ppt（45页珍藏版）》请在三一办公上搜索。

1、第3章 分组密码理论,3.1 分组密码概述3.2 DES3.3 分组密码的设计原理3.4 分组密码的工作模式,3.1 分组密码概述,分组密码，就是一个明文分组被当作一个整体来产生一个等长（通常）的密文分组的密码，通常使用的是128位分组大小。分组密码的实质是，设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。,3.1 分组密码概述(Cont.),分组密码的设计思想（C.E.Shannon)：扩散(diffusion)将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中（将明文冗余度分散到密文中）。产生扩散的最简单方法是通过“置换(Pe

2、rmutation)”（比如：重新排列字符）。,分组密码的设计思想(Cont.),混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。通常的方法是“代换（Substitution)”（回忆恺撒密码）。,3.1 分组密码概述(Cont.),分组密码设计的要求：分组长度足够大（64128比特）密钥量要足够大（64128）算法足够复杂（包括子密钥产生算法）加密、解密算法简单，易软、硬件实现便于分析（破译是困难的，但算法却简洁清晰）,3.2数据加密标准（DES),DES的历史1971 IBM，由

3、Horst Feistel 领导的密码研究项目组研究出LUCIFER算法。并应用于商业领域。1973美国标准局征求标准，IBM提交结果，在1977年，被选为数据加密标准。,3.2数据加密标准（Cont.),4.2.1 简化的DES Simplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。注：1.*加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和代换的运算。(3)置换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1,加密,10b

4、it密钥,解密,8bit明文,P10,8bit明文,IP,移位,IP-1,P8,fk,fk,SW,SW,移位,P8,fk,fk,IP,IP-1,8bit密文,8bit密文,K2,K2,K1,K1,S-DES方案示意图,2*.加密算法的数学表示：IP-1*fk2*SW*fk1*IP也可写为密文=IP-1（fk2(SW(fk1(IP(明文)其中 K1=P8(移位(P10(密钥K)K2=P8(移位(移位(P10(密钥K)解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文),对S-DES的深入描述,（1）S-DES的密钥生成：设10bit的密钥为（k1,k2,k10)置换P10是这样

5、定义的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)P8=(k1,k2,k10)=(k6,k3,k7,k4,k8,k5,k10,k9)LS-1为循环左移1位，LS-2为循环左移2位按照上述条件,若K选为(1010000010),产生的两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1),S-DES的密钥生成,10-bit密钥,P10,LS-1,LS-1,LS-2,LS-2,P8,P8,K1,8,K2,5,5,5,5,8,(2)S-DES的加密运算:初始置换用IP函数:IP=1 2 3 4 5 6 7

6、8 2 6 3 1 4 8 5 7 末端算法的置换为IP的逆置换:IP-1=1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易见IP-1(IP(X)=X,S-DES加密图,8-bit 明文,IP,E/P,+,S0,S1,P4,+,L,R,4,K1,8,4,4,fk,F,4,S-DES加密图(续),E/P,+,S0,S1,8,K2,P4,+,IP-1,8-bit 密文,4,8,4,4,fk,F,4,4,2,2,8,SW,函数fk，是加密方案中的最重要部分，它可表示为：fk(L,R)=(LF(R,SK),R)其中L，R为8位输入,左右各为4位,F为从4位集到4位集的一个映射,并不要

7、求是1-1的。SK为子密钥。对映射F来说：首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算：E/P 4 1 2 3 2 3 4 1 事实上，它的直观表现形式为：n4 n1 n2 n3n2 n3 n4 n1,8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：n4+k11 n1+k12 n2+k13n3+k14n2+k15 n3+k16n4+k17n1+k18把它们重记为8位：P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3上述第一行输入进S-盒S0，产生2

8、-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。,两个S盒按如下定义：,S盒按下述规则运算：将第1和第4的输入比特做为2-bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(1 0)确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出。由S0,S1输出4-bit经置换 P4 2 4 3 1它的输出就是F函数的输出。,作业,试证明S-DES的加密、解密是互逆的，即：D(E(M,K),K)M。,Feistel 密码结构,Feistel 密码设计原则,分组大

9、小 increasing size improves security,but slows cipher 密钥长度 increasing size improves security,makes exhaustive key searching harder,but may slow cipher 轮次数 increasing number improves security,but slows cipher 子密钥生成 greater complexity can make analysis harder,but slows cipher 轮函数 greater complexity can

10、 make analysis harder,but slows cipher 快速软件加密/解密are more recent concerns for practical use and testing,Feistel 密码解密,3.2 DES的描述,DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文该算法分三个阶段实现：1.给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。X0=IP（X）=L0R0其中L0由X0前32位组成，R0由X0的后32位组成。2.计算函数F的16次迭代,根据下述规则来计算LiRi(1=i=16）Li=Ri-1,Ri=Li

11、-1 F(Ri-1,Ki)其中Ki是长为48位的子密钥。子密钥K1，K2，K16是作为密钥K（56位）的函数而计算出的。3.对比特串R16L16使用逆置换IP-1得到密文Y。Y=IP-1（R16L16）,DES 算法的一般描述,一轮加密的简图,Li-1 Ri-1,F,+,Li Ri,Ki,对F函数的说明：（类比于S-DES）F（Ri-1,Ki）函数F以长度为32的比特串A=R（32bits）作第一个输入，以长度为48的比特串变元J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。(1)对第一个变元A，由给定的扩展函数E，将其扩展成48位串，E（A）(2)计算E（A）+J，并把结

12、果写成连续的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为固定置换。,A=R(32 bits),J=K(48 bits),E,E(A)为48 bits,+,B1 B2 B3 B4 B5 B6 B7 B8,S1,S2,S3,S4,S

13、5,S6,S7,S8,C1 C2 C3 C4 C5 C6 C7 C8,P,32 bits F(A,J),B,写成8个6比特串,DES 的F函数,DES中使用的其它特定函数：初始置换IP：从表3.2中看出X的第58个比特是IP（X）的第一个比特；X的第50个比特是IP（X）的第二个比特逆置换IP-1；扩展函数E；置换函数P。从密钥K计算子密钥：实际上，K是长度为64的位串，其中56位是密钥，8位是奇偶校验位（为了检错），在密钥编排的计算中，这些校验位可略去。(1).给定64位的密钥K，放弃奇偶校验位（8，16，64）并根据固定置换PC-1（见144页图4-4-9）来排列K中剩下的位。我们写 PC

14、-1(K)=C0D0其中C0由PC-1（K）的前28位组成；D0由后28位组成。,(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中48位组成一个48比特密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如：第7轮的表7：K7取K中的比特情况：52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 182

15、8 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6,图表（密钥生成Ki）,K,PC-1,C0 D0,LS1,LS1,C1 D1,LS2,LS2,LS16,LS16,C16 D16,PC-2,PC-2,K1,K16,DES加密的一个例子取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1IP，我们得到：L01=R0然后进行16轮加密。最后对L16,R16使用IP-1得到密文：85E813540F0AB405,3.2.3 DES的争论,DES的核心是S盒，除此之外的计算是属线性的

16、。S盒作为该密码体制的非线性组件对安全性至关重要。S盒的设计准则：1.S盒不是它输入变量的线性函数2.改变S盒的一个输入位至少要引起两位的输出改变3.对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。,公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有陷门？）。密钥长度是否足够？迭代的长度？（8、16、32？）,3.3 分组密码的设计原理,可变密钥长度混合操作依赖数据的循环移位依赖于密钥的循环移位依赖密钥的S盒子冗长的密钥调度算法可变的F函数和可变的明文/密文长度可变的循环次数在每次循环中都对两半数据进行操作,分组密码的工作模式,分组密码加密固定长度

17、的数据分组需要使用一些实际的方法来加密任意数量的明文 五种工作模式,Electronic Codebook Book(ECB),电码本模式,ECB的优势与局限,相同的明文对于相同的密文 结构化明文 消息有重复部分 主要用于发送少数量的分组数据,Cipher Block Chaining(CBC),密码分组链接模式,Advantages and Limitations of CBC,each ciphertext block depends on all message blocks thus a change in the message affects all ciphertext bloc

18、ks after the change as well as the original block need Initial Value(IV)known to sender&receiver however if IV is sent in the clear,an attacker can change bits of the first block,and change IV to compensate hence either IV must be a fixed value(as in EFTPOS)or it must be sent encrypted in ECB mode b

19、efore rest of message at end of message,handle possible last short block by padding either with known non-data value(eg nulls)or pad last block with count of pad size eg.b1 b2 b3 0 0 0 0 5-3 data bytes,then 5 bytes pad+count,Cipher FeedBack(CFB),密码反馈模式,Advantages and Limitations of CFB,appropriate w

20、hen data arrives in bits/bytes most common stream mode limitation is need to stall while do block encryption after every n-bits note that the block cipher is used in encryption mode at both ends errors propogate for several blocks after the error,Output FeedBack(OFB),输出反馈模式,Advantages and Limitation

21、s of OFB,used when error feedback a problem or where need to encryptions before message is available superficially similar to CFB but feedback is from the output of cipher and is independent of message a variation of a Vernam cipher hence must never reuse the same sequence(key+IV)sender and receiver

22、 must remain in sync,and some recovery method is needed to ensure this occurs originally specified with m-bit feedback in the standards subsequent research has shown that only OFB-64 should ever be used,Counter(CTR),计算器模式,Advantages and Limitations of CTR,效率可并行加密预处理吞吐量仅受可使用并行数量的限制加密数据块的随机访问可证明安全简单性（只要求实现加密算法）,