第四讲常规加密的现代技术详解演示文稿

第四讲常规加密的现代技术详解演示文稿现在是1页\一共有81页\编辑于星期一（优选）第四讲常规加密的现代技术现在是2页\一共有81页\编辑于星期一分组密码原理分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。现在是3页\一共有81页\编辑于星期一分组密码原理分组密码中密文输出中每一位数字都与该数字所在组块的n位明文数字有关，密钥不变时，分组密码对长度为n的明文所实施的变换是一样的，分组密码本质上是长度为n的数字序列的变换问题现在是4页\一共有81页\编辑于星期一抵御统计分析密码系统统计分析：在已知明文信息的某些统计特征的前提下，分析这些统计特征在密文中的反映，从而推测或推导可能的密钥或包含密钥的可能子集。信息论创始人Shannon提出为了抵御对密码系统的统计分析，设计密码系统的基本方法是扩散和扰乱。现在是5页\一共有81页\编辑于星期一密码系统基本设计原理扩散（Diffusion):将明文的统计特征扩散到密文中,使得明文和密文之间的统计关系尽量复杂方法：使明文中的每一位数字影响密文中多位的值，或者说使密文中的一位依赖于明文中的多位数字例：对英文消息M=c1c2…cn…中字符Cn的加密操作：现在是6页\一共有81页\编辑于星期一密码系统基本设计原理扰乱(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂方法：替换，线性变换无法起到有效的扰乱效果现在是7页\一共有81页\编辑于星期一现代分组密码设计原则分组长度足够大：使得分组替换字母表中的元素个数2n足够大，可有效的防止对明文实施穷举攻击。密钥空间要足够大,尽可能消除弱密钥并且使所有密钥的加密强度相同。保证足够强的密码算法复杂度，充分实现明文于密文的扩散和扰乱，能够抗击各种密码分析攻击现在是8页\一共有81页\编辑于星期一现代分组密码设计原则加解密运算简单,尽量采用子块和简单运算：子块的长度适应软件编程要求，通常长度取2的幂，密码运算尽量采用简单运算，如加法、与、或、异或、移位等。硬件实现:最好加密与解密具有相似性，以便采用同样的器件来实现加密和解密，节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现现在是9页\一共有81页\编辑于星期一DES加密算法的背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功。基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效现在是10页\一共有81页\编辑于星期一DES加密算法的背景美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的112位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。现在是11页\一共有81页\编辑于星期一DES的产生1973年5月15日,NBS开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的现在是12页\一共有81页\编辑于星期一DES的产生1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制1975年3月17日,NBS公开了全部细节1976年,NBS指派了两个小组进行评价1976年11月23日，采纳为联邦标准，批准用于美国政府的非密级政府通信1977年1月15日,“数据加密标准”FIPSPUB46发布现在是13页\一共有81页\编辑于星期一DES的应用1979年，美国银行协会批准使用1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSIX.392）

1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。现在是14页\一共有81页\编辑于星期一DES的应用1997年一个研究小组进过4个月努力，在Internet上搜索了3x1016个密钥，找到了DES的密钥1998年5月美国研究机构ETF用一台价值20万美元的计算机改装的专用解密系统，花费56小时破译了56位密钥的DES2000年10月，美国国家标准局公布了新的AES，DES作为标准正式结束。现在是15页\一共有81页\编辑于星期一S-DES加密算法S-DES：1)用于教学目的的简化的DES加密算法2)以10位密钥和8位明文分组作为输入，产生8位密文分组输出。3)解密使用相同密钥现在是16页\一共有81页\编辑于星期一S-DES加密算法加密步骤：1)对输入的8位明文分组m执行初始置换IP(m)2)执行一个包含替换、置换操作且依赖于密钥的变换fk3)将数据进行左右4位两半部分交换操作SW4)再执行一次fk5)执行逆置换IP-1产生密文输出现在是17页\一共有81页\编辑于星期一S-DES加密算法现在是18页\一共有81页\编辑于星期一

S-DES的密钥生成现在是19页\一共有81页\编辑于星期一S-DES的密钥生成P10:10阶置换,定义为

设10bit的密钥为k=(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)P10(k)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)LS为循环左移:LS-1循环左移1位,LS-2循环左移2位P8:10位转8位变换

P8=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K10)=(K6,K3,K7,K4,K8,K5,K10,K9)现在是20页\一共有81页\编辑于星期一S-DES的密钥生成例：若K选为(1010000010),产生的两个子密钥分别为

K1=(10100100)K2=(01000011)1)进行P10置换,m1=P10(1010000010)=(1000001100)2)循环左移m2=LS-1(m1L)||LS-1(m1R)==LS-1(10000)||LS-1(01100)=(0000111000)现在是21页\一共有81页\编辑于星期一S-DES的密钥生成3)P8变换K1=P8(0000111000)=(10100100)4)循环左移m3=LS-2(m2L)||LS-2(m2R)=LS-2(00001)||LS-2(11000)=(0010000011)5)P8变换K2=P8(0010000011)=(01000011)现在是22页\一共有81页\编辑于星期一S-DES的加密运算初始置换用IP函数:末端置换为IP的逆置换:易见IP-1(IP(X))=X现在是23页\一共有81页\编辑于星期一现在是24页\一共有81页\编辑于星期一S-DES的加密运算E/P变换：一个4位到8位的扩展变换，将输入字节的右半4位扩展为8位E/P(b1,b2,b3,b4)=(b4,b1,b2,b3,b2,b3,b4,b1,):按位异或运算S0,S1:4位到2位的变换盒,S0作用于E/P变换输出的左4位，S1作用于右4位输出为Sij,i由4位输入的0,3位确定,j由4位输入的1，2位确定现在是25页\一共有81页\编辑于星期一S-DES的加密运算例：S0(1110)=S23=3=(11)P4:4位置换P4(b1,b2,b3,b4)=(b2,b4,b3,b1)现在是26页\一共有81页\编辑于星期一Feistel密码结构思想基本思想：用简单算法的乘积来近似表达大尺寸的替换变换多个简单算法的结合得到的加密算法比任何一个部分算法都要强交替使用替换和置换应用扰乱(confusion)和扩散(diffusion)的概念现在是27页\一共有81页\编辑于星期一Feistel加密过程输入：

长为2w比特的明文分组

密钥k输出：长为2w比特的密文分组现在是28页\一共有81页\编辑于星期一Feistel密码结构特点明文分组分为：L0，R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组每i次循环都以上一循环产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，相互之间也不同，它是用子密钥生成算法从密钥生成的现在是29页\一共有81页\编辑于星期一Feistel结构特点所有循环的结构都相同替换：在数据的左半部分进行，其方法是先对数据的右半部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR)置换操作：数据左右两个部分互换循环函数对每次循环都有相同的通用结构，但由循环子密钥Ki来区分在置换之后，执行由数据两部分互换构成的交换现在是30页\一共有81页\编辑于星期一Feistel密码结构加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)现在是31页\一共有81页\编辑于星期一Feistel密码结构解密过程：以密文作为输入，以相反次序使用子密钥解密:

Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)现在是32页\一共有81页\编辑于星期一现在是33页\一共有81页\编辑于星期一Feistel解密LD1=RD0=LE16=RE15

RD1=LD0

F(RD0,K16)=RE16

F(RE15,K16)=(LE15F(RE15,K16))F(RE15,K16)=LE15现在是34页\一共有81页\编辑于星期一Feistel网络的设计特点分组大小：较大的分组意味着较强的安全性，但会降低加密解密速度。64位的分组大小是合理的折中，几乎所有的分组设计中都使用它密钥大小：较大的密钥意味着较强的安全性，但会降低加密解密速度。现代算法中最常用的是64位，128位密钥循环次数：本质是单一循环的不足，多重循环能够加强安全性。典型的循环次数为16子密钥生成算法：较大复杂性会增大密钥分析难度循环函数F：较大复杂性意味着给密码分析带来更大难度现在是35页\一共有81页\编辑于星期一数据加密标准DESDES概述：分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用扰乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现现在是36页\一共有81页\编辑于星期一DES加密算法的一般描述现在是37页\一共有81页\编辑于星期一输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES加密过程DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文现在是38页\一共有81页\编辑于星期一现在是39页\一共有81页\编辑于星期一令i表示迭代次数,表示逐位异或,f为加密函数DES加密过程现在是40页\一共有81页\编辑于星期一DES解密过程令i表示迭代次数,表示逐位模2求和,f为加密函数现在是41页\一共有81页\编辑于星期一输入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157输出（64位）L0（32位）R0（32位）初始置换IP现在是42页\一共有81页\编辑于星期一置换码组输入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输出（64位）逆置换IP—1现在是43页\一共有81页\编辑于星期一DES的一轮迭代现在是44页\一共有81页\编辑于星期一选择运算E32位输入321234545678989101112131213141516171617181920212021222324252425262728292829303132148位输出选择扩展运算现在是45页\一共有81页\编辑于星期一扩展置换Ｅ-盒－32位扩展到48位扩展现在是46页\一共有81页\编辑于星期一选择压缩运算现在是47页\一共有81页\编辑于星期一S盒现在是48页\一共有81页\编辑于星期一S盒

现在是49页\一共有81页\编辑于星期一S盒对每个盒，6比特输入中的第1和第6比特组成的二进制数确定行，中间4位二进制数用来确定列。其中相应行、列位置的十进制数的4位二进制数表示作为输出。例如输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，其中的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。现在是50页\一共有81页\编辑于星期一选择函数S1的例子

01234567891011121314150

1441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S1101100

1020010输入6位：101100输出4位0110现在是51页\一共有81页\编辑于星期一

置换P盒选择函数的输出（32位）1672021291228171152326518311028241432273919133062211425置换P加密函数的结果（32位）现在是52页\一共有81页\编辑于星期一子密钥的产生现在是53页\一共有81页\编辑于星期一置换选择157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124密钥（64位）C0(28位)D0(28位)现在是54页\一共有81页\编辑于星期一Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)置换选择2现在是55页\一共有81页\编辑于星期一DES安全性讨论S盒设计准则对S盒的疑义雪崩效应弱密钥与半弱密钥DES的有效密钥位数和迭代次数缺陷现在是56页\一共有81页\编辑于星期一S-盒的构造DES中其它算法都是线性的，而S-盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的关键所在现在是57页\一共有81页\编辑于星期一S-盒的构造准则没有一个S盒是它输入变量的线性函数S盒的每一行(由输入比特的最左和最右比特确定)应该包含16种比特组合改变S盒的一个输入位至少要引起两位的输出改变如果对S盒子的两个输入刚好在两个中间比特上不同，则输出必须在至少两个比特上不同如果对S盒子的两个输入在它们的前两位不同而在最后两位相同，两个输出必须不同.现在是58页\一共有81页\编辑于星期一S-盒的构造准则对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的扰乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门现在是59页\一共有81页\编辑于星期一对DES的S盒疑义DES的半公开性：S盒的设计原理至今未公布,只公布了设计准则S盒可能隐含有陷井（Hiddentrapdoors)S盒是唯一具有差分扩散功能的组件现在是60页\一共有81页\编辑于星期一DES安全性讨论雪崩效应：明文或密钥的一个比特的变化应该引起密文许多比特的改变，如果变化太小,就可能找到一种方法减小有待搜索的明文和密钥空间的大小现在是61页\一共有81页\编辑于星期一雪崩效应例：明文:00000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000密钥：00000011001011010010011000100011100001100000111000110010循环不同比特的个数0116221335439534632731现在是62页\一共有81页\编辑于星期一雪崩效应明文：01101000 10000101001011100111101000010011011101101110101110100100密钥：111001011110111101111001100000111010000100011000111011100011001011110111101111001100000111010000100011000111011100循环不同比特的个数0012214328432530632735现在是63页\一共有81页\编辑于星期一弱密钥当k1=k2=…=k16时，满足DESk(m)=DESk-1(m)或者DESk(DESk(m))=m的密钥称为弱密钥。现在是64页\一共有81页\编辑于星期一半弱密钥半弱密钥:若存在k或k’,使得DESk(m)=DESk’-1(m)或DESk(DESk’(m))=m,则k和k’构成半弱密钥。半弱密钥将导致通过密钥k’能够破解有密钥k加密的信息。现在是65页\一共有81页\编辑于星期一半弱密钥半弱密钥：DES至少有12个半弱密钥,成对构成k’-k现在是66页\一共有81页\编辑于星期一密钥长度关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有个早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。现在是67页\一共有81页\编辑于星期一

在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。

1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。

现在是68页\一共有81页\编辑于星期一

1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。现在是69页\一共有81页\编辑于星期一双重DESC=EK2(EK1(P))P=DK1(DK2(C))现在是70页\一共有81页\编辑于星期一双重DES的安全性中间相遇(meet-in-the-middle)攻击

C=EK2(EK1(P))X=EK1(P)=DK2(C)给定明文密文对(P,C)

对所有256个密钥,加密P,对结果排序

对所有256个密钥,解密C,对结果排序逐个比较,找出K