分组密码理论ppt课件

1、第第3章章 分组密码实际分组密码实际3.1 分组密码概述分组密码概述3.2 DES3.3 分组密码的设计原理分组密码的设计原理3.4 分组密码的任务方式分组密码的任务方式3.1 分组密码概述分组密码概述 分组密码，就是一个明文分组被当作一分组密码，就是一个明文分组被当作一个整体来产生一个等长通常的密文个整体来产生一个等长通常的密文分组的密码，通常运用的是分组的密码，通常运用的是128位分组大位分组大小。小。 分组密码的本质是，设计一种算法，能分组密码的本质是，设计一种算法，能在密钥控制下，把在密钥控制下，把n比特明文简单而又迅比特明文简单而又迅速地置换成独一速地置换成独一n比特密文，并且这种变

2、比特密文，并且这种变换是可逆的解密。换是可逆的解密。3.1 分组密码概述分组密码概述(Cont.)分组密码的设计思想分组密码的设计思想C.E. Shannon)：分散分散(diffusion)将明文及密钥的影响尽能够迅速地分布到将明文及密钥的影响尽能够迅速地分布到较多个输出的密文中将明文冗余度分散较多个输出的密文中将明文冗余度分散到密文中。产生分散的最简一方法是通到密文中。产生分散的最简一方法是通过过“置换置换(Permutation)比如：重新排比如：重新排列字符。列字符。分组密码的设计思想分组密码的设计思想(Cont.) 混淆混淆(confusion) 其目的在于使作用于明文的密钥和密文其

3、目的在于使作用于明文的密钥和密文之之 间的关系复杂化，是明文和密文之间、间的关系复杂化，是明文和密文之间、密密 文和密钥之间的统计相关特性极小化，文和密钥之间的统计相关特性极小化，从从 而使统计分析攻击不能奏效。通常的方而使统计分析攻击不能奏效。通常的方法法 是是“代换代换Substitution)回想恺撒密回想恺撒密 码。码。3.1 分组密码概述分组密码概述(Cont.)分组密码设计的要求：分组密码设计的要求：分组长度足够大分组长度足够大64128比特比特密钥量要足够大密钥量要足够大64128算法足够复杂包括子密钥产生算法算法足够复杂包括子密钥产生算法加密、解密算法简单，易软、硬件实现加密、

4、解密算法简单，易软、硬件实现便于分析破译是困难的，但算法却简约便于分析破译是困难的，但算法却简约明晰明晰3.23.2数据加密规范数据加密规范DES)DES) DES的历史的历史 1971 IBM，由，由Horst Feistel 指点的密码指点的密码研研 究工程组研讨出究工程组研讨出LUCIFER算法。并运用算法。并运用于于 商业领域。商业领域。 1973美国规范局征求规范，美国规范局征求规范，IBM提交结提交结果，果， 在在1977年，被选为数据加密规范。年，被选为数据加密规范。3.23.2数据加密规范数据加密规范Cont.)Cont.)4.2.1 4.2.1 简化的简化的DESDES Si

5、mplified DES Simplified DES方案，简称方案，简称S-DESS-DES方案。它方案。它是一个供教学而非平安的加密算法，它与是一个供教学而非平安的加密算法，它与DESDES的特性和构造类似，但参数小。的特性和构造类似，但参数小。注：注：1.1.* * 加密算法涉及五个函数：加密算法涉及五个函数：(1)(1)初始置换初始置换IP(initial permutation)IP(initial permutation)(2)(2)复合函数复合函数fk1fk1，它是由密钥，它是由密钥K K确定的，具确定的，具有置换和代换的运算。有置换和代换的运算。 (3)(3)置换函数置换函数S

6、WSW(4)(4)复合函数复合函数fk2fk2(5)(5)初始置换初始置换IPIP的逆置换的逆置换IP-1IP-1 加密10bit密钥 解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1S-DES方案表示图方案表示图 2*. 加密算法的数学表示：加密算法的数学表示：IP-1*fk2*SW*fk1*IP也可写为也可写为密文密文=IP-1fk2(SW(fk1(IP(明文明文)其中其中 K1=P8(移位移位(P10(密钥密钥K)K2=P8(移位移位(移位移位(P10(密钥密钥K)解密算法的数学表示：解密算法的数学

7、表示：明文明文=IP-1fk1(SW(fk2(IP(密文密文)对对S-DES的深化描画的深化描画1 S-DES的密钥生成：的密钥生成：设设10bit的密钥为的密钥为 k1,k2,k10 )置换置换P10是这样定义的是这样定义的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), 产产生的两个子密钥分别为生的两个子密钥分别为

8、K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)S-DES的密钥生成的密钥生成10-bit密钥P10LS-1LS-1LS-2LS-2K18K255558(2) S-DES的加密运算的加密运算: 初始置换用初始置换用IP函数函数: IP= 1 2 3 4 5 6 7 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+P4+LR4K1844fkF4S-DES加密图加密图(续

9、续)+8K2P4+IP-18-bit 密文密文4844fkF44228SW函数函数fk，是加密方案中的最重要部分，它可表示为：，是加密方案中的最重要部分，它可表示为：f k ( L , R ) = ( LF ( R , S K ) , R )其中其中L，R为为8位输入位输入, 左右各为左右各为4位位, F为从为从4位集到位集到4位集位集的一个映射的一个映射, 并不要求是并不要求是1-1的。的。SK为子密钥。为子密钥。对映射对映射F来说：来说：首先输入是一个首先输入是一个4-位数位数n1,n2,n3,n4，第一步运算是，第一步运算是扩张扩张/置换置换E/P运算：运算： E/P 4 1 2 3 2

10、 3 4 1 现实上，它的直观表现方式为：现实上，它的直观表现方式为：n4 n1 n2 n3n2 n3 n4 n18-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-位的位的输出；第二行的输出；第二行的4位输入进位输入

11、进S盒盒S1，产，产生生2-位的输出。位的输出。两个两个S盒按如下定义：盒按如下定义：2313312001232301321032100S3012010331023210321032101SS盒按下述规那么运算：盒按下述规那么运算：将第将第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的系

12、数为的系数为3，记为，记为1 1输出。输出。由由S0, S1输出输出4-bit经置换经置换 P4 2 4 3 1它的输出就是它的输出就是F函数的输出。函数的输出。作业 试证明S-DES的加密、解密是互逆的，即：D( E(M,K), K)M。Feistel 密码结构Feistel 密码设计原那么 分组大小分组大小 increasing size improves security, but slows cipher 密钥长度密钥长度 increasing size improves security, makes exhaustive key searching harder, but may

13、slow cipher 轮次数轮次数 increasing number improves security, but slows cipher 子密钥生成子密钥生成 greater complexity can make analysis harder, but slows cipher 轮函数轮函数 greater complexity can make analysis harder, but slows cipher 快速软件加密快速软件加密/解密解密 are more recent concerns for practical use and testingFeistel 密码解密3

14、.2 DES的描画的描画 DES利用利用56比特串长度的密钥比特串长度的密钥K来加密长度为来加密长度为64位的明文，位的明文，得到长度为得到长度为64位的密文位的密文 该算法分三个阶段实现：该算法分三个阶段实现：1. 给定明文给定明文X，经过一个固定的初始置换，经过一个固定的初始置换IP来陈列来陈列X中的中的位，得到位，得到X0。X0=IPX=L0R0其中其中L0由由X0前前32位组成，位组成，R0由由X0的后的后32位组成。位组成。2.计算函数计算函数F的的16次迭代次迭代, 根据下述规那么来计算根据下述规那么来计算LiRi(1=i=16 Li=Ri-1, Ri=Li-1 F(Ri-1, K

15、i)其中其中Ki是长为是长为48位的子密钥。子密钥位的子密钥。子密钥K1，K2，K16是是作为密钥作为密钥K56位的函数而计算出的。位的函数而计算出的。 3.对比特串对比特串R16L16运用逆置换运用逆置换IP-1得到密文得到密文Y。Y=IP-1R16L16DES 算法的普通描画一轮加密的简图一轮加密的简图 Li-1 Ri-1F+Li RiKi 对对F F函数的阐明：类比于函数的阐明：类比于S-DESS-DESF FRi-1, KiRi-1, Ki函数函数F F以长度为以长度为3232的比特串的比特串A=RA=R32bits32bits作第一个输入，作第一个输入，以长度为以长度为4848的比特

16、串变元的比特串变元J=K(48bits)J=K(48bits)作为第二个输入。作为第二个输入。产生的输出为长度为产生的输出为长度为3232的位串。的位串。(1)(1)对第一个变元对第一个变元A A，由给定的扩展函数，由给定的扩展函数E E，将其扩展成，将其扩展成4848位串，位串，E EA A(2)(2)计算计算E EA A+J+J，并把结果写成延续的，并把结果写成延续的8 8个个6 6位串位串, , B=b1b2b3b4b5b6b7b8 B=b1b2b3b4b5b6b7b8(3)(3)运用运用8 8个个S S盒，每个盒，每个SjSj是一个固定的是一个固定的4 41616矩阵，它的元矩阵，它的

17、元素取素取015015的整数。给定长度为的整数。给定长度为6 6个比特串，如个比特串，如Bj=b1b2b3b4b5b6Bj=b1b2b3b4b5b6计算计算Sj(Bj)Sj(Bj)如下：如下：b1b6b1b6两个比特确定了两个比特确定了SjSj的行数的行数, , r(0=r=3); r(0=r=3); 而而b2b3b4b5b2b3b4b5四个比特确定了四个比特确定了SjSj的列数的列数c c0=c=150=c=15。最后。最后Sj(Bj)Sj(Bj)的值为的值为S-S-盒矩阵盒矩阵SjSj中中r r行行c c列的列的元素元素r,cr,c, , 得得Cj=Sj(Bj)Cj=Sj(Bj)。(4)

18、(4) 最后，最后，P P为固定置换。为固定置换。 A=R(32 bits)J=K(48 bits)EE(A)为48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B写成8个6比特串DES 的的F函数函数 DES中运用的其它特定函数：中运用的其它特定函数：初始置换初始置换IP：从表：从表3.2中看出中看出X的第的第58个比特是个比特是IPX的第一个比特；的第一个比特；X的第的第50个比特是个比特是IPX的第二个比的第二个比特特逆置换逆置换IP-1；扩展函数；扩展函数E；置换函

19、数；置换函数P。 从密钥从密钥K计算子密钥：计算子密钥： 实践上，实践上，K是长度为是长度为64的位串，其中的位串，其中56位是密钥，位是密钥，8位是奇偶校验位为了检错，在密钥编排的计算中，位是奇偶校验位为了检错，在密钥编排的计算中，这些校验位可略去。这些校验位可略去。(1). 给定给定64位的密钥位的密钥K，放弃奇偶校验位，放弃奇偶校验位8，16，64并根据固定置换并根据固定置换PC-1见见144页图页图4-4-9来陈列来陈列K中剩下的位。我们写中剩下的位。我们写 PC-1(K)=C0D0其中其中C0由由PC-1K的前的前28位组成；位组成；D0由后由后28位组成。位组成。 (2)对对1=i

20、=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 1

21、1 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6图表密钥生成图表密钥生成KiKPC-1C0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 DES加密的一个例子加密的一个例子取取16进制明文进制明文X：0123456789ABCDEF密钥密钥K为：为：133457799BBCDFF1去掉奇偶校验位以二进制方式表示的密钥是去掉奇偶校验位以二进制方式表

22、示的密钥是00010010011010010101101111001001101101111011011111111000运用运用IP，我们得到：，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进展然后进展16轮加密。轮加密。最后对最后对L16, R16运用运用IP-1得到密文：得到密文：85E840F0AB4053.2.3 DES的争论的争论 DES的中心是的中心是S盒，除此之外的计算是属盒，除此之外的计算是属线性的。线性的。S盒作为该密码体制的非线性组盒作为该密码体制的非线性组

23、件对平安性至关重要。件对平安性至关重要。 S盒的设计准那么：盒的设计准那么：1. S盒不是它输入变量的线性函数盒不是它输入变量的线性函数2.改动改动S盒的一个输入位至少要引起两位盒的一个输入位至少要引起两位的输出改动的输出改动3. 对任何一个对任何一个S盒，假设固定一个输入比盒，假设固定一个输入比特，其它输入变化时，输出数字中特，其它输入变化时，输出数字中0和和1的总数近于相等。的总数近于相等。 公众依然不知道公众依然不知道S盒的构造中能否还运用盒的构造中能否还运用了进一步的设计准那么有陷门？。了进一步的设计准那么有陷门？。 密钥长度能否足够？密钥长度能否足够？ 迭代的长度？迭代的长度？8、1

24、6、32？3.3 分组密码的设计原理分组密码的设计原理 可变密钥长度可变密钥长度 混合操作混合操作 依赖数据的循环移位依赖数据的循环移位 依赖于密钥的循环移位依赖于密钥的循环移位 依赖密钥的依赖密钥的S盒子盒子 冗长的密钥调度算法冗长的密钥调度算法 可变的可变的F函数和可变的明文函数和可变的明文/密文长度密文长度 可变的循环次数可变的循环次数 在每次循环中都对两半数据进展操作在每次循环中都对两半数据进展操作分组密码的任务方式 分组密码加密固定长度的数据分组 需求运用一些实践的方法来加密恣意数量的明文 五种任务方式Electronic Codebook Book (ECB)电码本方式电码本方式E

25、CB的优势与局限 一样的明文对于一样的密文 构造化明文 音讯有反复部分 主要用于发送少数量的分组数据 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 blocks after the change as well as the original block need Initial V

26、alue (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 before 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 when data arrives in bits/by