第03章 常规加密的现代技术

1第三章常规加密的现代技术1.Feistel密码2.简化的数据加密标准S-DES3.数据加密标准DES4.DES分组密码操作方式21.Feistel密码–当前使用的几乎所有对称加密算法都基于被称为Feistel分组密码的结构。•数据映射设计•扩散和扰乱•加密算法结构•解密算法31.1数据映射设计•可逆映射和不可逆映射–nbit的可逆映射的不同变换个数为2n！–分组长度较小时等同于古典的替代密码–nbit的一般替代分组密码，密钥的大小是nx2n–nbit线性映射的密钥的大小是n2可逆映射明文密文0011011010001101不可逆映射明文密文00110110100111014bit输入4到16译码器16到4译码器4bit输出1023456789101112131415102345678910111213141541.1数据映射设计示例：4bit明文–一般替代–线性映射y1＝k11x1＋k12x2＋k13x3＋k14x4y2＝k21x1＋k22x2＋k23x3＋k24x4y3＝k31x1＋k32x2＋k33x3＋k34x4y4＝k41x1＋k42x2＋k43x3＋k44x4明文密文明文密文000011100000111000010100000101110010110100100100001100010011110101000010010000010101111101010010011010110110111101111000011110111000001110001000100110101001001110100110101010101011110010110110110001011100110011011001110101011110000011101001111101111111000051.2扩散和扰乱现代分组密码设计的基础是为统计分析制造障碍•扩散–将明文的统计结构被扩散消失到密文的长程统计特性中，让明文的每个数字影响许多密文数字的取值，亦即每个密文数字被许多明文数字影响。•扰乱–明文分组到密文分组的变换依赖于密钥，扰乱应使得密文的统计特性与加密密钥的取值之间的关系尽量复杂，使得即使攻击者掌握了密文的某些统计特性，由于密钥产生密文的方式是如此复杂以至于攻击者难于从中推测出密钥。61.2扩散和扰乱•扩散–采用平均操作进行加密–重复使用对数据的某种置换，并对置换结果再应用某个函数。•扰乱–采用复杂的替代算法（非线性函数）。kiinnmc126mod71.3Feistel加密算法结构•明文分组被分为两个部分L0和R0，数据的这两个部分经过n轮的处理后组合起来产生密文分组。•每一轮i以从前一轮得到的Li-1和Ri-1为输入，另外的输入还有从总的密钥K生成的子密钥Ki。•子密钥Ki不同于K，它们彼此之间也不相同。•每一轮的结构都一样。对数据的左边一半进行替代操作，替代的方法是对数据右边一半应用round函数F，然后用这个函数的输出和数据的左边一半做异或。•round函数在每一轮中有着相同的结构，但是以各轮的子密钥Ki为参数形成区分。•在这个替代之后，算法做一个置换操作把数据的两个部分进行互换。明文(2w比特)w比特w比特第1轮L0R0L1K1∶R1Rn+1F∶第i轮LiKi∶RiF∶第n轮LnKnRnFLn+1密文(2w比特)81.3Feistel加密算法结构Feistel具体实现依赖的参数和设计特点–分组大小：分组越大意味着安全性越高（如果其他条件相同），但加密/解密速度也越慢。–密钥大小：密钥长度越长则安全性越高，但加密/解密速度也越慢。–循环次数：一个循环不能保证足够的安全性，而循环越多则安全性越高。–子密钥产生算法：算法越复杂则密码分析就应该越困难。–Round函数：复杂性越高则抗击密码分析的能力就越强。91.3Feistel加密算法结构Feistel具体实现应考虑的其它因素–快速的软件加密/解密：在很多情况下，加密过程被以某种方式嵌入在应用程序或工具函数中以至于没法用硬件实现，因此，算法的执行速度就成为一个重要的考虑因素。–便于分析：如果算法能够简洁地解释清楚，那么就很容易通过分析算法而找到密码分析上的弱点，也就能够对其牢固程度有更大信心。101.4Feistel解密算法•Feistel密码的解密过程与其加密过程实质是相同的。–以密文作为算法的输入，但是以相反的次序使用子密钥Ki。这就是说在第一轮用Kn，在第二轮用kn-1，如此等等，直到在最后一轮使用K1。RD15=LE1LD15=RE1LD16=RE0RE16LE16LE1输入(明文)输出(明文)输入(密文)输出(密文)LE0FFK1RE0K2RE1RE2LE2∶∶∶∶LE15LE14FFK15RE14K16RE15RE16LE16RD16=LE0RD14=LE2FFK1K2LD14=RE2RD0=LE16∶∶∶∶RD1=LE15RD14=LE14FFK15LD1=RE15K16LD2=RE14LD0=RE16LD16=RE0RD16=LE0111.4Feistel解密算法证明：设：LEi和REi表示加密过程中各个阶段的数据LDi和RDi表示解密过程中各个阶段的数据则：LE16＝RE15RE16=LE15F(RE15，K16)LD1=RD0=LE16=RE15RD1=LD0⊕F(FD0，K16)=RE16⊕F(RE15，K16)＝[LE15⊕F(RE15，K16)]⊕F(RE15，K16)由于：[A⊕B]⊕C=A⊕[B⊕C]D⊕D=0E⊕0=E故：RD1=LE15通式：由于：LEi=REi-1REi=LEi-1⊕F(REi-1，Ki)因此：REi-1=LEiLEi-1=REi⊕F(REi-1，Ki)=REi⊕F(LEi，Ki)122.简化的数据加密标准S-DES•DES-DataEncryptionStandard(1977年元月15日-美国联邦标准）1998年！！SimplifiedDES方案，简称S-DES方案。•1.*加密算法涉及算法涉及五个函数：(1)初始置换IP(initialpermutation)(2)复合函数fk1，它是由密钥K确定的，具有转换和替换的运算。(3)转换函数SW(4)复合函数fk2(5)初始置换IP的逆置换IP-1132.简化的数据加密标准S-DES10bit密钥加密解密8bit明文规定8bit密文K1K18bit密文8bit明文规定K2K2P10移位P8移位P8IPfKfKfKfKIP-1SWSWIPIP-1142.简化的数据加密标准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(密文)))))15•（1）S-DES的密钥生成：设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)置换P10是这样定义的P10(k1,k2,…,k10)=(k3,k4,k2,k7,k4,k10,k1,k9,k8,k6)相当于P10=LS-1为循环左移，在这里实现左移1位P8=按照上述条件,若K选为(1010000010),产生的两个子密钥分别为K1=(10100100),K2=(01000011)6891104725310987654321910584736876543212.简化的数据加密标准S-DES16（1）S-DES的密钥生成：2.简化的数据加密标准S-DES10bit密钥K1K255810P10LS-1P8LS-2LS-2LS-1P85555817(2)S-DES的加密运算:初始置换用IP函数:末端算法的置换为IP的逆置换:易见IP-1(IP(X))=X2.简化的数据加密标准S-DES35742186IP35742186IP-118•(3)S-DES加密图8bit密文IP-1SW8822444E/PS0S1P4fKK2444888224448bit明文E/PIPS0S1P4fKK184442.简化的数据加密标准S-DES19函数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）运算：事实上，它的直观表现形式为：2.简化的数据加密标准S-DES23243141E/P13432124nnnnnnnn208-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：把它们重记为8位：上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：2.简化的数据加密标准S-DES181143174163132121152114knknknknknknknkn3,13,02,11,12,01,00,10,0pppppppp23133120012323010S30120103310232101S21S盒按下述规则运算：将第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）输出。由S0,S1输出4-bit经置换它的输出就是F函数的输出。2.简化的数据加密标准S-DES3124P422•(4)S-DES的安全性分析–无法抗强力攻击–具有一定的抗密码分析能力•置换和加法操作都是线性映射•非线性来自于S盒子设：S盒子输入为(p0,0，p0,1，p0,2，p0,3)=(a，b，c，d)和(p1,0，p1,1，p1,2，p1,3)=(w，x，y，z)S盒子输出为(q，r，s，t)则：q=abcd+ab+ac+b+d（模2加）r=abcd+abd+ab+ac+ad+a+c+1（模2加）•线性映射和非线性映射交替使用将产生复杂的密文比特多项式，其复杂性可用8个包含10个未知数的非线性方程表示，每一个方程大约有29个项（含有10个二进制未知数的一个多项式方程可以有210个可能的项）。2.简化的数据加密标准S-DES23•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-1F(Ri-1,Ki)其中Ki是长为48位的子密钥。子密钥K1，K2，…，K16是作为密钥K（56位）的函数而计算出的。3.对比特串R16L16使用逆置换IP-1得到密文Y。Y=IP-1（R16L16）3.数据加密标准DES243.数据加密标准DESDES加密流程图K2K16K1循环左移循环左移循环左移置换选择1置换选择2置换选择2第16轮初始置换第1轮置换选择2第2轮32bit对换逆初始置换64bit明文56bit密钥64bit密文253.数据加密标准DES初始置换及逆初始置换初始置换58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始置换4084816562464323974