第02-02章 现代密码技术及其应用-密码技术

第02-2章现代密码技术及其应用---现代密码技术主讲人：李学明单位：重庆大学计算机学院2013年1月2.3现代密码技术2.3.1、序列密码2.3.2、分组密码2.3.3、公开密码2.3.4、混沌密码2.3.5、量子密码1、基本思想明文序列m=m0m1m2…ms密钥序列k=k0k1k2…ks密文序列c=c0c1c2…cs1,ikmciiimi∈GF(2)ki∈GF(2)ci∈GF(2)⊕O1x01010110010001GF(2)=F={0,1},⊕,X2.3.1序列密码(流密码)密钥源密钥序列k0k1k2…公开信道秘密信道密钥流产生器密钥流产生器KK密钥序列k0k1k2…明文序列m0m1m2…明文序列m0m1m2…密文序列c0c1c2…序列密码工作原理K为种子密钥，一般较短；密钥流发生器在K的控制下产生较长的蜜钥流2、密钥序列如何构造产生密钥序列，且要保证其随机性。真正的随机序列是很难得到的，故序列密码的核心就是研究如何产生伪随机序列，即研究伪随机发生器。伪随机序列的性质：1)看起来是随机的2)它是不可预测的3)它不能重复产生3、伪随机序列的产生方法1)利用反馈移位寄存器来产生伪随机序列2)其他方法基于困难问题的伪随机数产生方法如：shamir伪随机数发生器是基于大数分解的困难性4、线性反馈移位寄存器(LSFR)原理),...,,(21tntttbbbs),,...,,(),...,,(132112111tntntttntttbbbbbbbs)(1ttnSfbbnBn-1b2b1…反馈函数:f(b1,b2,…,bn-1,bn)输出序列112211...)(bcbcbcbcsfnnnnCi=0或1，bi=0或1举例4位-LSFRb4b3b2b1输出序列S0=(b4,b3,b2,b1)=(1,1,1,1)0:11118:10011:01119:01002:101110:00103:010111:00014:101012:10005:110113:11006:011014:11107:001115:11111)一般地,n位-LSFR的最长周期为L=2n-12)m序列当n位-LSFR的周期L=2n-1时，称其为m序列（全为0的状态不用）5、非线性序列构造(有多种形式)例1：基于J-K触发器的非线性序列LSFR(m)LSFR(n)JK{ai}{bi}{Qn}JKQn00011011Qn-101Qn-1Qn序列是ai、bi的非线性组合，当(m,n)=1时，Qn序的周期为(2m-1)(2n-1)例2：非线性组合序列LSFR1LSFR2LSFRnf()a1x1a2x2anxnf(.)为非线性组合函数6、常用序列密码A5:用于欧洲蜂窝移动电话系统GSM,基于LSFRRC4：不是基于LSFR，基于表置乱原理可随便使用，无需专利许可SEAL(IBM):需专利许可…在军事等要求很高的通信中，一般使用序列密码1、分组密码(块密码)的基本概念1)输入块：数字输入序列x0,x1,…,xi,…被划分成长度为n的块：m=(m0,m1,…,mn-1)其中mi=xi+ln(l=0,1,2,…)2)块蜜钥：k=(k1,k2,…,kr-1)3)密文块：c=(c0,c1,…,ct-1)2.3.2分组密码一般地t=n若tn:有数据扩散的分组密码tn:有数据压缩的分组密码加密器E解密器D块密钥k0k1k2…kr-1明文块m0m1m2…mn-1密文块c0c1c2…ct-1块密钥k0k1k2…kr-1明文块m0m1m2…mn-1mi∈GF(2)ki∈GF(2)ci∈GF(2)2、分组密码设计原则(1)要有足够大分组长度n不能过小，否则攻击者可利用穷举明文空间来获取明文、密文对应关系(2)密钥空间要尽可能大若r太小，则攻击者可利用穷举密钥空间来把截获的密文还原成明文(3)密码算法复杂度足够强目的是除穷举攻击外，无法利用简单数学关系找到突破口。3、分组密码基本加密方法1)混乱使明文、密钥、密文之间的关系变得复杂，是攻击者无复获得相互间的依赖关系，也即掩盖明文、密钥、密文间的关系。非线性替代变换可达到较好的混乱效果2)扩散使明文中的每一位能影响密文中的许多位，或者说密文中的每一位受制于明文中的许多位。达到隐藏明文统计特性的目的，起到雪崩效应。3)Feistel网络明文分组分为：L0，R0，通过n次循环处理后，再结合起来生成密文分组n次循环的结构都是完全相同的每次循环都以上一循环产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，不同的子密钥Ki相互间也不同，它是用子密钥生成算法从密钥生成的Feistel网络的一轮循环Li-1Ri-1f函数KiLiRiFeistel网络的一个轮回|Li-1|=|Ri-1|输入：长为2|Li-1|比特的明文分组密钥k输出：长为2|Li-1|比特的密文分组密钥Ki：Ki是由密钥K产生的子密钥每个Ki都不相同Feistel网络的一个轮回加密过程：Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)右边的输出直接移动到左边。但是，左边在使用某个函数f并进行异或运算后才移动到右边。f函数可以任意的复杂。Feistel网络是可逆的解密过程显然Ri-1=Li直接获得。而Li-1通过下式可得：Li-1=Li-1⊕f(Ri-1,Ki)⊕f(Ri-1,Ki)=Ri⊕f(Li,Ki)Feistel网络说明:基于Feistel的加密与解密算法本质上是相同的，不同在于输入参数不同Feistel网络设计特点：分组大小：较大的分组意味着较强的安全性，但会降低加密解密速度。64位的分组大小是合理的折中，几乎所有的分组设计中都使用它密钥长度：较大的密钥意味着较强的安全性，但会降低加密解密速度。现代算法中最常用的是128位密钥循环次数：本质是单一循环的不足，多重循环能够加强安全性。典型的循环次数为16子密钥生成算法：较大的复杂性会增大密钥分析的难度F函数：较大的复杂性意味着给密码分析带来更大的难度Fiestel网络在分组密码中的应用LUCIFER(IBM)DES(IBM)RC5(RSA)GOST(前苏联)FEAL(日本)CAST(加拿大)BlowFish(美国,应用密码学一书的作者)LOKI、LOKI91(澳大利亚)…4、DES加密算法(1)DES历史1)20世纪60年代末，IBMfeistel小组研制出Lucifer密码算法(128位)2)1971,IBM推出DES密码，其密钥长度缩短到56位(8位校验位)3)1977年，DES作为美国联邦信息处理标准，FIPS-464)90年代来，DES由于密钥长度不够，受到各种攻击，其安全性不够5)1998年，美国国家保密局经评估后认为，DES已无安全感DES基于Feistel网络(2)、DES原理明文64位输入初始变换IP16轮变换初始变换的逆变换IP-1密文64位输出初始密钥64位移位变换(16次)产生每轮子密钥k1---k16DES的一轮Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-11)IP置换的作用对明文中的各位进行换位目的在于：打乱明文中的各位58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157IP置换40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725IP-1置换初始置换用IP函数:IP=123…40…64585042…1…7末端算法的置换为IP的逆置换:IP-1=123…40…6440848…28…25易见IP-1(IP(X))=XIP和IP—12014'MM1420'''MMIPIP—12)E置换：扩展置换把32位扩展成48位是一个与密钥无关的纯移位置换32位分为8组，每组4位；经E置换后，变成每组6位扩展置换Ｅ-盒－32位扩展到48位扩展3)S置换（压缩替换）(DES算法的关键所在)8个盒，48位输入变成32位输出;每个S盒将6位输入变成4位输出E-盒输出的每个分组(共8个)对应一个S盒(S盒的设计思想未公布)每个S盒有4行16列。S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造与实例（S6）1234561626234521133911001110019bbbbbbbbSbbbb行：-盒子行列列：值：14=1100实例：1100111100DES中其它算法都是线性的，而S-盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性S-盒是DES算法的关键所在S-盒特点S-盒构造原则S盒的每一行是整数0，…，15的一个置换没有一个S盒是它输入变量的线性函数改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于{0,1},S(X)S(X11ef00)对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目S-盒的构造要求S-盒是许多密码算法的唯一非线性部件,因此它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门4)P置换把压缩得到的32位重新排列，输出即为f(Ri-1,ki)p-盒的构造准则P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化5)子密钥生成64位密钥：校验位在8、16、32、40、48、56、64位置6)解密过程类似于加密过程密钥输入顺序与加密相反加密和解密可共用一个程序k1（56位）(48位)ki（56位）（48位）64位密钥置换选择1C0（28位）D0（28位）循环左移循环左移C1（28位）D1（28位）循环左移循环左移Ci（28位）Di（28位）置换选择2置换选择2密钥表的计算逻辑循环左移：119121102321124212252132621427215282161DES中的子密钥的生成密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性实现简单速度不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥(3)DES的工作模式1）电子密码本ECB(electroniccodebookmode)2）密码分组链接CBC(cipherblockchaining)3）密码反馈CFB(cipherfeedback)4）输出反馈OFB(outputfeedback)iKiiKiC=E(P)P=D(C)电子密码本ECBECB的特点简单和有效可以并行实现不能隐藏明文的模式信息相同明文生成相同密文，同样信息多次出现造成泄漏对明文的主动攻击是可能的信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息密码分组链接CBCiKii-1iKii-1C=E(PC)P=D(C)CCBC的特点没有已知的并行实现算法能隐藏明文的模式信息需要共同的初始化向量IV相同明文生成不同密文初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递