第三章分组密码DES

第3章分组密码理论3.1分组密码概述3.2DES3.3分组密码的设计原理3.4分组密码的工作模式3.1分组密码概述•分组密码，就是一个明文分组被当作一个整体来产生一个等长（通常）的密文分组的密码，通常使用的是128位分组大小。•分组密码的实质是，设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。3.1分组密码概述(Cont.)分组密码的设计思想（C.E.Shannon)：•扩散(diffusion)将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中（让每个明文数字尽可能地影响多个密文数字）。分组密码的设计思想(Cont.)•混淆(confusion)其目的在于让密文和加密密钥间的统计关系更加复杂。可以使用一些复杂的代换算法来实现，简单的线性代换几乎增加不了混淆。3.1分组密码概述(Cont.)分组密码设计的要求：•分组长度足够大（64~128比特）•密钥量要足够大（64~128）•算法足够复杂（包括子密钥产生算法）•加密、解密算法简单，易软、硬件实现•便于分析（破译是困难的，但算法却简洁清晰）3.2数据加密标准（DES)•DES的历史1971IBM，由HorstFeistel领导的密码研究项目组研究出LUCIFER算法。并应用于商业领域。1973美国标准局征求标准，IBM提交结果，在1977年，被选为数据加密标准。3.2数据加密标准（Cont.)4.2.1简化的DESSimplifiedDES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。注：1.*加密算法涉及五个函数：(1)初始置换IP(initialpermutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和代换的运算。(3)置换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1加密10bit密钥解密8bit明文P108bit明文IP移位IP-1P8fk1fk2SWSW移位P8fk2fk1IPIP-18bit密文8bit密文K2K2K1K1S-DES方案示意图加密10bit密钥解密8bit明文P108bit明文IP移位IP-1P8fk1fk2SWSW移位P8fk2fk1IPIP-18bit密文8bit密文K2K2K1K1S-DES方案示意图加密加密10bit密钥解密8bit明文P108bit明文IP移位IP-1P8fk1fk2SWSW移位P8fk2fk1IPIP-18bit密文8bit密文K2K2K1K1S-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是这样定义的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=(10100100),K2=(01000011)S-DES的密钥生成10-bit密钥P10LS-1LS-1LS-2LS-2P8P8K18K255558(2)S-DES的加密运算:初始置换用IP函数:IP=1234567826314857末端算法的置换为IP的逆置换:IP-1=1234567841357286易见IP-1(IP(X))=XS-DES加密图8-bit明文IPE/P+S0S1P4+LR4K1844fk14S-DES加密图(续)E/P+S0S18K2P4+IP-18-bit密文4844fk244228SW函数fk，是加密方案中的最重要部分，它可表示为：fk(L,R)=(LF(R,SK),R)其中L，R为8位输入,左右各为4位,F为从4位集到4位集的一个映射,并不要求是1-1的。SK为子密钥。对映射F来说：首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算：E/P41232341事实上，它的直观表现形式为：n4n1n2n3n2n3n4n18-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：n4+k11n1+k12n2+k13n3+k14n2+k15n3+k16n4+k17n1+k18把它们重记为8位：P0,0P0,1P0,2P0,3P1,0P1,1P1,2P1,3上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：2313312001232301321032100S3012010331023210321032101SS盒按下述规则运算：将第1和第4的输入比特做为2-bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(10)确定了S0中的第0行2列（0，2）的系数为3，记为（11）输出。P4运算：由S0,S1输出4-bit经过置换。它的输出就是F函数的输出。P424313.2DES的描述•DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文•该算法分三个阶段实现：1.给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。X0=IP（X）=L0R0其中L0由X0前32位组成，R0由X0的后32位组成。3.2DES的描述•DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文•该算法分三个阶段实现：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）DES算法的一般描述一轮加密的简图•Li-1Ri-1F+LiRiKi•对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，并把结果写成连续的8个6位串,B=b1b2b3b4b5b6b7b8•(3)使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取0~15的整数。给定长度为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(32bits)J=K(48bits)EE(A)为48bits+B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P32bitsF(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-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中的比特情况：5257111265910344451251994132503536434233601828714294746225156361394311338536255202337306图表（密钥生成Ki）KPC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16…•DES加密的一个例子取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16,R16使用IP-1得到密文：85E813540F0AB4053.2.3DES的争论•DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。•S盒的设计准则：1.S盒不是它输入变量的线性函数2.改变S盒的一个输入位至少要引起两位的输出改变3.对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。•公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有陷门？）。•密钥长度是否足够？•迭代的长度？（8、16、32？）本周作业•用C＃或者Java调用程序库中的DES算法，实现DES加密和解密。