第三章 分组密码.ppt
《第三章 分组密码.ppt》由会员分享,可在线阅读,更多相关《第三章 分组密码.ppt(123页珍藏版)》请在麦多课文档分享上搜索。
1、第三章 分组密码,3.1 分组密码概述 3.2 DES 3.3 AES 3.4 分组密码运行模式,一、分组密码概述,分组密码概述,分组密码是许多系统安全的一个重要组成部分。可用于构造 伪随机数生成器 流密码 消息认证码(MAC)和杂凑函数 消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分。,应用中对于分组码的要求,安全性 运行速度 存储量(程序的长度、数据分组长度、高速缓存大小) 实现平台(硬、软件、芯片) 运行模式,分组密码概述,明文序列 x1, x2, xi,加密函数E: VnKVn 这种密码实质上是字长为m的数字序列的代换密码。,分组密码概述,通常取n=m。
2、若nm,则为有数据扩展的分组密码。 若nm,则为有数据压缩的分组密码。,分组密码设计问题,分组密码的设计问题在于找到一种算法,能在密钥控制下从一个足够大且足够好的置换子集中,简单而迅速地选出一个置换,用来对当前输入的明文的数字组进行加密变换。,分组密码设计准则,混淆:人们所设计的密码应使用使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。 扩散:人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译,而且明文的每一位数字也应影响密文的许多位数字以便隐藏明文数字统计特性。,分组密码算法应满足的要求,分组长度n要足够大:防止明文穷
3、举攻击法奏效。 密钥量要足够大:尽可能消除弱密钥并使所有密钥同等地好,以防止密钥穷举攻击奏效。 由密钥确定置换的算法要足够复杂:充分实现明文与密钥的扩散和混淆,没有简单的关系可循,要能抗击各种已知的攻击。,分组密码算法应满足的要求,加密和解密运算简单:易于软件和硬件高速实现。 数据扩展:一般无数据扩展,在采用同态置换和随机化加密技术时可引入数据扩展。 差错传播尽可能地小。,分组密码的实现原则,软件实现的原则:使用子块和简单的运算。如将分组n化分为子段,每段长为8、16或32。在以软件实现时,应选用简单的运算,使作用于子段上的密码运算易于以标准处理器的基本运算,如加、乘、移位等实现,避免用以软件
4、难于实现的逐比特置换。 硬件实现的原则:加密解密可用同样的器件来实现。,代换网络,代换是输入集A到输出A上的双射变换:fk:AAk是控制输入变量,在密码学中则为密钥。 实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。,代换网络,代换fk的集合: S=fkkK K是密钥空间。如果网络可以实现所有可能的2n!个代换,则称其为全代换网络。 全代换网络密钥个数必须满足条件: k2n!,代换结构,代换网络,密码设计中需要先定义代换集S,而后还需定义解密变换集,即逆代换网络S-1,它以密文y作为输入矢量,其输出为恢复的明文矢量x。 要实现全代换网络并不容易。因此实用中常常
5、利用一些简单的基本代换,通过组合实现较复杂的、元素个数较多的代换集。实用密码体制的集合S中的元素个数都远小于2n!。,代换盒(S盒),在密码设计中,可选 n=rn0,其中r和n0都为正整数,将设计n个变量的代换网络化为设计r个较小的子代换网络,而每个子代换网络只有n0个输入变量,称每个子代换网络为代换盒(Substitution Box),DES的S盒,DES的S1-盒的输入和输出关系,x5 x0 x5 x4 x3 x2 x1 x01 0 1 0 1 1 0 0列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15行号0 14 4 13 1 2 15 11 8 3 1
6、0 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13,(y3 , y2, y1 , y0)=(0,0,1,0),S盒的设计准则,迄今为止,有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则: P1 S盒的输出都不是其输入的线性或仿射函数。 P2 改变S盒的一个输入比特,其输出至少有两比特产生变化,即近一半产生变化。 P3 当S盒的任一输入位保持不变,其
7、它5位输入变化时(共有25 =32种情况),输出数字中的0和1的总数近于相等。这三点使DES的S盒能够实现较好的混淆。,Feistel密码结构,乘积密码指顺序地执行两个或多个基本密码系统,使得最后结果的密码强度高于每个基本密码系统产生的结果. Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。,Feistel网络示意图,输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0,在进行完n轮迭代后,左右两半再合并到一起以产生密文分组。第i轮迭代的输入为前一轮输出的函数:其中Ki是第i轮用的子密钥,由加密密钥K得到
8、。一般地,各轮子密钥彼此不同而且与K也不同。,Feistel密码结构,Feistel密码结构,Feistel网络的实现与以下参数和特性有关: 分组大小: 分组越大则安全性越高,但加密速度就越慢。 密钥大小:密钥越长则安全性越高,但加密速度就越慢。 轮数:单轮结构远不足以保证安全性,但多轮结构可提供足够的安全性。典型地,轮数取为16。 子密钥产生算法:该算法的复杂性越大,则密码分析的困难性就越大。 轮函数:轮函数的复杂性越大,密码分析的困难性也越大。,在设计Feistel网络时,还有以下两个方面需要考虑: 快速的软件实现:在很多情况中,算法是被镶嵌在应用程序中,因而无法用硬件实现。此时算法的执行
9、速度是考虑的关键。 算法容易分析:如果算法能被无疑义地解释清楚,就可容易地分析算法抵抗攻击的能力,有助于设计高强度的算法。,Feistel密码结构,Feistel解密过程本质上和加密过程是一样的,算法使用密文作为输入,但使用子密钥Ki的次序与加密过程相反,即第1轮使用Kn,第2轮使用Kn-1,最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。,Feistel解密结构,Feistel加解密过程,在加密过程中:在解密过程中,Feistel密码结构,所以解密过程第1轮的输出为LE15RE15,等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地,加密
10、过程的第i轮有因此,Feistel密码结构,3.2 美国数据加密标准DES(Data Encryption Standard),美国制定数据加密标准简况,目的通信与计算机相结合是人类步入信息社会的一个阶梯,它始于六十年代末,完成于90年代初。计算机通信网的形成与发展,要求信息作业标准化,安全保密亦不例外。只有标准化,才能真正实现网的安全,才能推广使用加密手段,以便于训练、生产和降低成本。,美国制定数据加密标准简况,美国NBS在1973年5月15公布了征求建议。1974年8月27日NBS再次出公告征求建议,对建议方案提出如下要求: (1)算法必须提供高度的安全性 (2)算法必须有详细的说明,并易
11、于理解 (3)算法的安全性取决于密钥,不依赖于算法 (4)算法适用于所有用户 (5)算法适用于不同应用场合 (6)算法必须高效、经济 (7)算法必须能被证实有效 (8)算法必须是可出口的,美国制定数据加密标准简况,IBM公司在1971年完成的LUCIFER密码 (64 bit分组,代换-置换,128 bit密钥)的基础上,改进成为建议的DES体制 1975年3月17日NBS公布了这个算法,并说明要以它作为联邦信息处理标准,征求各方意见。 1977年1月15日建议被批准为联邦标准FIPS PUB 46,并设计推出DES芯片。 1981年美国ANSI 将其作为标准,称之为DEAANSI X3.92
12、 1983年国际标准化组织(ISO)采用它作为标准,称作DEA-1,美国制定数据加密标准简况,NSA宣布每隔5年重新审议DES是否继续作为联邦标准,1988年(FIPS46-1)、1993年(FIPS46-2),1998年不再重新批准DES为联邦标准。 虽然DES已有替代的数据加密标准算法,但它仍是迄今为止得到最广泛应用的一种算法,也是一种最有代表性的分组加密体制。 1993年4月,Clinton政府公布了一项建议的加密技术标准,称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府SECRET密级。,美国制定数据加密标准简况,DES发展史确
13、定了发展公用标准算法模式,而EES的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。 1995年5月AT&T Bell Lab的M. Blaze博士在PC机上用45分钟时间使SKIPJACK的 LEAF协议失败,伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据,只将它用于语音通信。 1997年1月美国NIST着手进行AES(Advanced Encryption Standard)的研究,成立了标准工作室。2001年Rijndael被批准为AES标准。,DES(Data Encryption Standard)算法于1977年得到美国
14、政府的正式许可,是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。 DES是第一代公开的、完全说明细节的商业级现代算法,并被世界公认。,美国制定数据加密标准简况,DES 算法,分组长度为64 bits (8 bytes) 密文分组长度也是64 bits。 密钥长度为64 bits,有8 bits奇偶校验,有效密钥长度为56 bits。 算法主要包括:初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。,DES算法框图,输入64 bit明文数据初始置换IP乘积变换(16轮迭代)逆初始置换IP-164 bit密文数据输出,标准数据加密算法,初始置换IP,将6
15、4 bit明文的位置进行置换,得到一个乱序的64 bit明文组,而后分成左右两段,每段为32 bit,以L0和R0表示,IP中各列元素位置号数相差为8,相当于将原明文各字节按列写出,各列比特经过偶采样和奇采样置换后,再对各行进行逆序。将阵中元素按行读出构成置换输出。 逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置换,得到输出的密文组。输出为阵中元素按行读得的结果。 IP和IP-1在密码意义上作用不大,它们的作用在于打乱原来输入x的ASCII码字划分的关系。,(1)IP置换表和IP-1逆置换表。输入的64位数据按IP表置换进行重新组合,并把输出分为L0和R0两部分,每部分各32位,
16、其IP表置换如表2-3所示。,Li = Ri-1 Ri= Lif(Ri-1 ,Ki) (i=1,2,3, ,16),乘积变换,它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组,在迭代过程中彼此左右交换位置。 每次迭代时只对右边的32 bit进行一系列的加密变换,在此轮迭代即将结束时,把左边的32 bit与右边得到的32 bit逐位模2相加,作为下一轮迭代时右边的段,并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。 在每一轮迭代时,右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。,乘积变换,选择扩展运算E。将
17、输入的32 bit Ri-1扩展成48 bit的输出,令s表示E原输入数据比特的原下标,则E的输出是将原下标s0或1(mod 4)的各比特重复一次得到的,即对原第32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29各位都重复一次,实现数据扩展。将表中数据按行读出得到48 bit输出。密钥加密运算。将子密钥产生器输出的48 bit子密钥ki与选择扩展运算E输出的48 bits数据按位模2相加。选择压缩运算S。将前面送来的48 bit数据自左至右分成8组,每组为6 bit。而后并行送入8个S一盒,每个S盒为一非线性代换网络,有4个输出,
18、运算S的框图在图4-4-6中给出。p.186图4-4-6 选择压缩运算S置换运算P。对S1至S8盒输出的32 bit数据进行坐标置换,如图4-4-7所示。置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加,所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器,作为下一轮迭代用的左边的数字段。子密钥产生器。将64 bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki,参看图4-4-8。在64 bit初始密钥中有8位为校验位,其位置号为8、16、32、48、56和64。其余56位为有效位,用于子密钥计算。将这
19、56位送入置换选择PC1,参看图4-4-9。经过坐标置换后分成两组,每级为28 bit,分别送入C寄存器和D寄存器中。在各次迭代中,C和D寄存器分别将存数进行左循环移位置换,移位次数在表4-4-2中给出。每次移位后,将C和D寄存器原存数送给置换选择PC2,见图4-4-10。置换选择PC2将C中第9、18、22、25位和D中第7、9、15、26位删去,并将其余数字置换位置后送出48 bit数字作为第i次迭代时所用的子密钥ki。p.186 p.186图4-4-7 置换运算P 图4-4-8 子密钥产生器框图表4-4-2 移位次数表第i次迭代 1 2 3 4 5 6 7 8 9 10 11 12 13
20、 14 15 16循环左移次数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1p.187图4-4-9 置换选择PC1至此,我们已将DES算法的基本构成作了介绍,加密过程可归结如下:令IP表示初始置换,KS表示密钥运算,i为迭代次数变量,KEY为64 bit密钥,f为加密函数,表示逐位模2求和。,E变换的算法是从Ri-1的32位中选取某些位,构成48位,即E将32位扩展为48位。变换规则根据E位选择表,如表2-5所示。,选择压缩运算S,6 bit选择函数组4 bit,乘积变换,置换运算P。对S1至S8盒输出的32 bit数据进行坐标置换,置换P输出的32 bit数据与左边32 b
21、it即Ri-1逐位模2相加,所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器,作为下一轮迭代用的左边的数字段。子密钥产生器。将64 bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki,,子密钥产生器框图,密钥(64 bit ),置换选择1,PC1,置换选择2,PC2,Ci(28 bit),Di(28 bit),循环左移ti+1bit,循环左移ti+1bit,除去第8,16, ,64位(8个校验位),ki,DES的安全性,互补性。DES算法具有下述性质。若明文组x逐位取补,密钥k逐位取补,即y=DESk(x), 则有
22、这种互补性会使DES在选择明文破译下所需的工作量减半。 弱密钥和半弱密钥。DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k,各轮的子密钥都相同,即有 k1=k2= =k16就称给定密钥k为弱密钥(Weak key)。,DES的安全性,若k为弱密钥,则有DESk(DESk(x)=xDESk-1(DESk-1(x)=x即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。弱密钥下使DES在选择明文攻击下的搜索量减半。如果随机地选择密钥,弱密钥所占比例极小,而且稍加注意就不难避开。因此,弱密钥的存在不会危及DES的安全性。,DES的安全性,密文与明文、密文与密钥的
23、相关性。Meyer1978详细研究了DES的输入明文与密文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数,并且指出达到这一要求所需的迭代次数至少为5。Konheim1981用2检验证明,迭代8次后输出和输入就可认为是不相关的了。,DES的安全性,S盒设计。DES靠S盒实现非线性变换。 密钥搜索机。对DES安全性批评意见中,较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112 bits密钥,但公布的DES标准采用64 bits密钥。有人认为NSA故意限制DES的密钥长度。采用穷搜索对已经对DES构成了威胁,DES算法的安全性,DES算
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 分组 密码 PPT
