上海交大密码学课件--第七讲现代分组密码(续1).ppt

密码学,第七讲 现代分组加密算法 S-DESDESIDEA,上海交通大学 郑东,第七讲 分组密码理论-DES,7.1 S-DES 7.2 DES 7.3 IDEA,7.1.1 简化的DES Simplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。 注：1.* 加密算法涉及五个函数： (1)初始置换IP(initial permutation) (2)复合函数fk1，它是由密钥K确定的，具有转换和替换的运算。 (3)转换函数SW (4)复合函数fk2 (5)初始置换IP的逆置换IP-1,10bit密钥,解密,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方案示意图,加密,7.1.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(密文),7.1.3算法描述,（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), 产生的两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1),7.1.4 S-DES的密钥生成,P10,LS-1,LS-1,LS-2,LS-2,P8,P8,K1,8,5,5,5,5,8,10bit密钥,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,7.1.5 S-DES加密图,IP,E/P,+,S0,S1,P4,+,L,R,4,K1,8,4,4,fk,F,4,8bit明文,E/P,+,S0,S1,8,K2,P4,+,IP-1,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位集的一个映射, 并不要求是1-1的。SK为子密钥。 对映射F来说： 首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算： E/P 4 1 2 3 2 3 4 1 事实上，它的直观表现形式为： n4 n1 n2 n3 n2 n3 n4 n1,8-bit子密钥： K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得： n4+k11 n1+k12 n2+k13 n3+k14 n2+k15 n3+k16 n4+k17 n1+k18 把它们重记为8位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3 上述第一行输入进S-盒S0，产生2-位的输出；第二行的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函数的输出。 Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。,S-DES的安全性分析,对10 bit密钥的强行攻击是可行的 密钥空间：210=1024 密码分析：利用已知明文攻击： 已知: 明文（p1,p2,p8), 及对应的密文 （c1,c2,c8), 未知：(k1,k2, ，k10) Ci是pjs和kjs的函数 这些加密算法可以表示成8个含10个变量的非线性方程 非线性是由S盒作用的结果,S0的非线性表示如下： 设a,b,c,d为输入的4个比特，输出的两个比特分别为q,r. 则 q=abcd+ab+ac+b+d mod2 r=abcd+abd+ab+ac+ad+a+c+1 mod2 线性映射与非线性映射交替产生了复杂的密文比特输出函数，使得密码分析很困难。（可以试图寻找8个密文比特的复杂度）,7.2 数据加密标准（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）,(a) 初始置换(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,(b) 初始置换的逆置换(IP-1), 扩展置换(E),(d) 置换函数(P,32bit),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 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,XOR,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）XOR 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,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,PC2,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,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 encryption 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的密钥生产,52个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的最好替代.,7.6.7先进分组密码的特点,可变密钥长度 混合操作 依赖数据的循环移位 依赖于密钥的循环移位 依赖S盒子 冗长的密钥调度算法 可变的F函数和可变的明文/密文长度 可变的循环次数 在每次循环中都对两半数据进行操作,7.7 分组密码工作模式,分组密码加密固定长度的年信息，eg. DES加密64-bit，使用 56-bit key 需要一种使用方法，加密任意长度的消息 这种使用方法叫做工作模式