第二章-密码学概论2-DES算法.ppt

,第二级,第三级,第四级,第五级,第,2,章,广东工业大学信息安全研究所,*,*,第,2,章 密码学概论,3/1/2026,1,2.1.1,概述,-,加密解密基本过程,使消息保密的技术和科学叫做,密码编码学,破译密文的科学和技术为,密码分析学,密码学作为数学的一个分支，包括密码编码学和密码分析学两部分。,发送者,明文,(M/P),加密,密文,(C),接受者,解密,原始,明文,密钥,(K),密钥,(K),3/1/2026,2,2.1.1,概述,-,加密解密基本过程,密码算法也叫密码，是用于加密解密的函数。,如果算法的保密性是,基于保持算法的秘密,，这种算法称为受限制的算法。,现代密码学用密钥解决这个问题，密钥用,K,表示，,K,的可能取值范围叫做密钥空间。,如，密钥,56,位，,2,56,种,基于密钥的算法,通常有两类,对称密钥算法,公开密钥算法,3/1/2026,3,2.1.1,概述,密码体制分类,对称密码体制,又叫传统密码算法,:,加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加解密密钥是相同的。,这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，,商定一个密钥,。,明文,加密,密文,解密,明文,密钥,密钥,3/1/2026,4,对称密码体制,对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加,/,解密。,加密和解密用函数表示为：,E,K,（,M,）,=C,D,K,（,C,）,=M,对称算法可分为两类,一次只对明文中的单个位,(,有时对字节,),运算的算法称为,序列算法,(stream algorithm),或,序列密码,(stream cipher),。,另一类算法是对明文的一组位进行运算，这些位组称为分组，相应的算法称为,分组算法,(block algorithm),或,分组密码,(b1ock cipher),。,3/1/2026,5,2.1.1,概述,密码体制分类,公钥密码体制,用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来,(,至少在合理假定的长时间内,),。,加密密钥,K1,与相应的解密密钥,K2,不同，函数表示为,E,K1,（,M,）,=C,D,K2,（,C,）,=M,明文,加密,密文,解密,明文,公钥,私钥,3/1/2026,6,2.1.1,概述,常用的密码分析攻击,唯密文攻击,(,ciphertext,-only attack),密码分析者有一些消息的密文，这些消息都用同一加密算法加密。,密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。,密码分析者已知的素材是：,.,加密算法、,.,待破译的密文。,3/1/2026,7,2.1.1,概述,常用的密码分析攻击,已知明文攻击,(known-plaintext attack),密码分析者已知的素材是：,.,加密算法、,.,待破译的密文、,.,由密钥形成的一个或多个明文,-,密文对。,分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。,3/1/2026,8,2.1.1,概述,常用的密码分析攻击,选择明文攻击,(chosen-plaintext attack),。,密码分析者已知的素材是：,.,加密算法、,.,待破译的密文、,.,由密码分析者选择的明文，连同它对应的由其密钥生成的密文。,这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息。,3/1/2026,9,2.1.1,概述,常用的密码分析攻击,选择密文攻击,(chosen-,ciphertext,attack),密码分析者素材的东西是：,.,加密算法、,.,待破译的密文、,.,由密码分析者选择的猜测性密文，连同它对应的由密钥生成的已破译的明文。,3/1/2026,10,2.1.1,概述,常用的密码分析攻击,自适应选择明文攻击,(adaptive-chosen-plaintext attack),。,密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在自适应选择密文攻击中，可选取较小的明文块，然后再基于第一块的结果选择另一明文块，以此类推。,密码分析者已知的素材是：,.,加密算法、,.,待破译的密文、,.,由密码分析者选择的明文，连同它对应的由密钥生成的密文、,.,由密码分析者选择的猜测性密文，连同它对应的由密钥生成的已破译的明文。,3/1/2026,11,2.1.1,概述,常用的密码分析攻击,上述攻击中，唯密文攻击是困难的攻击，因为密码分析者可利用的信息最少,。,若,密码分析者除了密文外，还能获取一段或多段明文，或者可能知道某种明文模式将出现在某个消息中，此时可以进行已知明文攻击。,如果密码分析者能在加密源系统中插入由分析员选择的消息，则可进行选择明文攻击。,其他两种类型的密码分析：选择密文攻击和自适应选择明文攻击较少使用，但无论如何是可能的攻击途径。,3/1/2026,12,2.1.1,概述,常用的密码分析攻击,对密码设计者,被设计的加密算法一般要能经受得住已知明文攻击。,对密码分析者,则有两条必须遵循的基本准则,是破译该密码的成本不能超过被加密信息的价值；,是破译该密码的时间不能超过被加密信息有用的生命周期。,3/1/2026,13,2.1.2,古典密码,在计算机出现之前,:,基于,字符,进行变换,;,计算机密码算法,:,基于,位,进行变换,;,基本的密码算法,:,互相替代,(Substitution),相互置换,(Transposition),好的密码算法是结合这两种方法每次进行多次运算。,3/1/2026,14,加密技术的两个基本构造模块是替代和置换，下面介绍的,Caesar,（恺撒）密码、,Vigenere,（维吉尼尔）密码、,Hill,密码、转轮机都属于使用替代技术的加密技术。,1,替代密码：,明文中的每一个字符被替换为密文中的另外一个字符，接收者对密文进行逆替换即可恢复出明文。,单表替代密码,：,明文的每一个字符用相应的密文字符代替。,3/1/2026,15,恺撒密码,基本原理,在开拓罗马帝国的时候，恺撒担心信使会阅读他送给士兵的命令，因此发明了对命令进行加密的算法恺撒密码器。,恺撒密码器非常简单：把字母表中的每个字母向前循环移动,3,位。,A b c d e f g h I j k l m n o p q r s t u v w x y z,d e f g h I j k l m n o p q r s t u v w x y z A b c,Attack at dawn,Dwwdfn,dw,gdzq,3/1/2026,16,加密信息将字母向前移动三位,解密信息将字母向后移动三位,移动的位数是关键，称之为,密钥,加密和解密的密钥是相同的，我们称之为,对称密码器,Attack at,dawn,t,Dwwdfn,dw,gdzq,t,3/1/2026,17,恺撒密码,数学表达,为每个字母分配一个数值（如,a=0,、,b=1,等），对每个明文字母,p,，,用密文字母,C,代替，则恺撒密码的加密算法可表示为：,C=E(p)=(p+3)mod 26,而解密算法则可表示为,p=D(C)=(C-3)mod 26,3/1/2026,18,恺撒密码,改进的恺撒密码系统,明文的发送方和接收方事先协商好一个密钥。,用,k(1,k25),表示密钥，则通用的恺撒加密算法表示为：,C=E(p)=(p+k)mod 26,相应的，解密算法可表示为：,p=D(C)=(C-k)mod 26,3/1/2026,19,恺撒密码,攻击方式,唯密文攻击,攻击者只有密文消息，他的策略就是穷尽搜索,25,个可能密钥。,加快攻击速度：,只须利用猜想的密钥对前,5,个字符进行解密,每个字母在短文中出现的概率不相同的,3/1/2026,20,已知明文攻击,：如果攻击者知道一个字符以及它的密文，那么他很快就可以通过加密字符与解密后的明文之间的间距推出密钥是多少。例如，如果知道,t,（,=19,）,加密后变成,D,（,=3,），,那么密钥,k=,（,3,19,）,mod 26=,16 mod 26=10,。,选择明文攻击,：选择一个字符,a,作为明文，则由密文可以推导出密钥。例如，如果密文是,H,，,则密钥,k,就是,7,。,选择密文攻击,：选择字符,A,作为密文，则由明文也可推导出密钥。例如，如果明文是,h,，,则密钥,k=,0-,7 mod 26=19,。,恺散密码虽然脆弱，仅对明文进行了不透明的封装，但它可防止消息明文被人意外的获取。,3/1/2026,21,例如，明文为,network security,则密文为,QHWZRUN VHFXULWB,如将,26,个字母分别对应于整数,0,25,，可得凯撒密码变换为,加密：,E(m)=(m+3)mod 26,解密：,D(c)=(c?3)mod 26,凯撒密码的密钥,k=3,。,3/1/2026,22,缺点：,不安全的、容易攻破,:,简单的单表替代没有掩盖明文不同字母出现的频率；,移位替代的密钥空间有限，只有,25,个密钥容易破解。,参看实例：福尔摩斯,跳舞的人,关键人物：,ELSIE,太太,3/1/2026,23,“摆在我面前的就是那些罕见的作品。它们要不是成了一场悲剧的先兆，谁见了都会一笑了之的。,我得到的第一张纸条的内容太短，我唯一比较有把握确定的是（）这个符号代表字,E,。大家都知道，,E,在英语字母中最常见，它出现的次数多到即使在一个短句子中也是最常见的。第一张纸条上有十五个符号，其中四个是一佯的，因此假定它为,E,是合乎情理的。不错，有的小人拿着小旗，有的则没有；但是从小旗分布的情况来看，这些小旗是用来把句子分成单词的。,“下面才是真正困难的地方。跟在,E,后面的出现频率最高的英语字母的顺序根本无法确定，普通一页上和某一个短句子中出现的频率也许大相径庭。一般说来，字母按出现频率排列的顺序是,T,，,A,，,O,，,I,，,N,，,S,，,H,，,R,，,D,，,L,；但是，,T,，,A,，,O,，,I,出现的频率几乎不相上下。要是把每一种组合都试一遍，直到得出一个意思来，那会是一项无止境的工作。我便只好等待出现新的材料。,希尔顿,丘比特先生第二次来的时候，给我带来了另外两个短句子和似乎只有一个单词的一句话，因为上面不带小旗。在这个只有五个字母的单词中，我已经知道第二和第四个字母是,E,，那么这个单词有可能是,sever,（切断），也可能是,lever,（杠杆），也有可能是,never,（决不）。,毫无疑问，使用最后这个词来回答一种请求的可能性很大，而各种情况都表明这是丘比特太太写的答复。如果这种推理正确，我们现在便可以说,这三个符号分别代表字母,N,、,V,和,R,。”,3/1/2026,24,“,即使这样，我的困难仍然很大，但是，一个很妙的想法使我知道了另外几个字母。我突然想到，假如这些请求来自一个早年和丘比特太太亲近过的人的话，一个首尾字母是,E,、中间有三个字母的组合很可能就是,ELSIE,（埃尔茜）。我仔细检查后发现，这一组合曾出现在一句重复了三遍的句子的结尾。这句话肯定是对,埃尔茜,的请求。这样，我就得出了,L,、,S,和,I,。可这请求会是什么内容呢？,埃尔茜,前面的那个单词只有四个字母，而且以,E,字母结尾，那么这个单词一定是,COME,（来）。我把所有以,E,结尾的四个字母的单词都试了一遍，发现都对不上。这样我又得到了,C,，,O,和,M,，可以再次分析第一句话的意思了。我把它分成单词，不知道的字母就用点代替。经过这样的处理，这句话就成了这种样子：,.M.ERE.ESL.NE.,现在，第一个字母只能是,A,。这是最有用的发现，因为这个字母在这个短句中出现了三次，而且第二个单词中的,H,也是很明显的。这句话现在变成了：,AM HERE A.ESLANE.,如果再把名字中所缺的字母添上：,AM HERE ABE SLANE,（,我已到达。阿贝,斯兰尼,。）,我现在有了这么多字母，可以很有把握地解释第二句话了。这句话是：,A.ELRI.ES.,在这句话中，我觉得只有在缺字母的地方加上,T,和,G,才有意义，而且假定这个名字是写信人住的地方或者旅店。,”,3/1/2026,25,“希尔顿,丘比特给我寄来了斯兰尼画的最后的图形。我把已知的字母代进去，它就变成了：,ELSIE.RE.ARE TO MEET THY GO.,添上,P,和,D,，这句话的意思就出来了,（意为：埃尔茜，准备见上帝）”,福尔摩斯用以下字条引导凶手落入圈套,（,意为：尽快来这儿,）,3/1/2026,26,改进：,方法一,多表替代密码,：,以一系列替代表依次对明文消息的字母替代的加密方法。,方法二,多字母替代密码,：,每次对多于一个的字母进行替代的加密方法,优点在于将字母的自然频度隐蔽或均匀化，抗统计分析。,3/1/2026,27,Playfair,密码,基本原理,多字母加密密码：将明文中的双字母组合作为一个加密单元对待，并将这些单元转换为密文双字母组合。,Playfair,算法基于一个,5,5,的字母矩阵，该矩阵使用,一个关键词,构造，方法是按,从左到右、从上到下顺序，填入关键词的字母（去除重复字母）后，将字母表其余字母填入。,3/1/2026,28,基本原理,例如关键词取为,monarchy,时，字母矩阵为,加密方法是先将明文按两个字母一组进行,分组，然后在矩阵中找对应的密文，取密,文的规则如下：,(,1,）若明文分组出现相同字母在一组，则,在重复的明文字母中插入一个填充字母,（譬如,k,）,进行分隔后重新分组,（如,balloon,被重新分组为,ba,lk,lo on,）；,（,2,）若分组到最后一组时只有一个字母，则补充字母,k,；,（,3,）,若明文字母在矩阵中同行，则循环取其右边字母为密文,（如,ar,被加密为,RM,）；,(,4,）,若明文字母在矩阵中同列，则循环取其下边字母为密文,（如,um,被加密为,MC,）；,(,5,）,若明文字母在矩阵中不同行不同列，则取其同行且与下一字母,同列的字母为密文（如,hs,被加密为,BP,，,ea,被加密为,IM,或,JM,）。,3/1/2026,29,例,明文,we are discovered save yourself,分组成为：,we,ar,ed is co,ve,re,ds,av,ey,ou,rs,el,fk,用上述矩阵加密后的密文为：,UG RM KC SX HM UF KM TB XO GC VM TA LU GE,。,3/1/2026,30,Playfair,密码,Playfair,密码比恺撒密码前进了一大步，一方面是它改变了单字母替代密码的频率分布，另一方面是双字母组合有,676,种，识别各种双字母组合要比识别,26,个单字母困难得多。,因此,Playfair,密码过去很长一段时期被认为是不可破译的，第一次世界大战中被英国陆军作为最好的密码系统使用，在第二次世界大战中也曾被美国陆军和盟军大量使用。,3/1/2026,31,Vigenere,密码,密钥,一个字符序列,k=(k,1,k,2,k,m,),，,其中,m,为任意值。,明文,X=(x,1,x,2,x,n,),将被分为长度为,m,的段，如果消息的长度恰好不是,m,的倍数，则在末尾填充随机字符。,3/1/2026,32,加密函数,E,k,(x,1,x,2,x,n,)=,(x,1,+k,1,)mod 26,，,(x,2,+k,2,)mod 26,，,，,(,x,m,+k,m,)mod 26,，,(x,m+1,+k,1,)mod 26,，,(x,m+2,+k,2,)mod 26,，,，,(x,2m,+k,m,)mod 26,，,(x,2m+1,+k,1,)mod 26,，,(x,2m+2,+k,2,)mod 26,，,，,(x,3m,+k,m,)mod 26,，,(x,N-m+1,+k,1,)mod 26,，,(x,N-m+2,+k,2,)mod 26,，,，,(,x,N,+k,m,)mod 26),密钥的第一个字符被加到明文的第,1,个、第,(m+1),个、第,(2m+1),个、第,(3m+1),个字符上（进行,mod 26,运算）,密钥的第二个字符被加到明文的第,2,个、第,(m+2),个、第,(2m+2),个、第,(3m+2),个字符上，依此类推。,3/1/2026,33,解密函数,D,k,假设密文,Y=(y,1,y,2,y,n,),，,则解密函数为：,D,k,(y,1,y,2,y,n,),=,(y,1,-k,1,)mod 26,，,(y,2,-k,2,)mod 26,，,，,(,y,m,-k,m,)mod,26,，,(y,m+1,-k,1,)mod 26,，,(y,m+2,-k,2,)mod 26,，,，,(y,2m,-k,m,)mod 26,，,(y,2m+1,-k,1,)mod 26,，,(y,2m+2,-k,2,)mod 26,，,，,(y,3m,-k,m,)mod 26,，,(y,N-m+1,-k,1,)mod 26,，,(y,N-m+2,-k,2,)mod 26,，,，,(,y,N,-k,m,)mod 26),3/1/2026,34,例子,为了容易记住密钥，常常使用英文单词来充当,Vigenere,密码的密钥。,使用密钥为,vector,，,用数值表示则,k=(21,4,2,19,14,17),m=6,来加密明文,:,here is how it works,。,密钥的第一个字符被加到明文,的第,1,个、第,(m+1),个、第,(2m+1),个、第,(3m+1),个字符上（进行,mod 26,运算）,密钥的第二个字符被加到明文,的第,2,个、第,(m+2),个、第,(2m+2),个、第,(3m+2),个字符上，,依此类推,则第一个明文字符用其后,面的第,21,个字符来代替,(,即,向后移,21,位,),，相应的，,第二个明文字符则向后移,4,位，第三个字符向后移,2,位，以此类推。当用完密,钥,k,的最后一位时，又从,密钥的第一位开始，如此,循环下去。因此，第,7,个,明文字符被向后移,21,位，,第,8,个明文字符向后移,4,位,3/1/2026,35,例子,具体加密过程如下：,明文：,h e r e i s h o w i t w o r k s,密钥：,21 4 2 19 14 17 21 4 2 19 14 17 21 4 2 19,密文：,C I T X W J C S Y B H N J V M L,Vigenere,密码的强度在于对每个明文字母有多个密文字母对应，因此该字母的频率信息是模糊的,(,如，,e,s),。,维吉尼亚（,Vigenere,）,密码是一种多表加密算法，在密文的不同位置出现的字符通常不是以同样的方式加密的，但它是一种周期密码，如果两个同样的字符出现的间隔固定，并且为密钥长度的倍数，则它们将以同样的方法进行加密。,3/1/2026,36,Hill,密码,Hill,密码也是一种多字母替代密码，它由数学家,Lester Hill,于,1929,年研制成功。,该密码算法取,m,个连续的明文字母，并用,m,个密文字母代替,用向量或矩阵表示为：,C,和,P,是长度为,3,的列向量，分别表示明文和密文，,K,是,3,3,矩阵，表示加密密钥，,加密操作要执行模,26,运算。,3/1/2026,37,例如，如果使用的加密密钥是,对明文：,pay more money,进行加密，则先按三个字母一组分组（不足三个时补字母,x,），,然后对每组字母求密文。,该明文的前三个字母表示为,pay=(15 0 24),T,，,计算密文的过程如下：,K(15 0 24),T,=(375 819 486),T,mod 26=(11 13 18),T,=LNS,如此类推，可得密文为：,LNS HDL EWM TRW,。,3/1/2026,38,解密时使用逆矩阵，,对密文,(11 13 18),T,，,做运算,K,-1,(11 13 18),T,mod 26=(431 494 570),T,=(15 0 24),T,=pay,Hill,密码的强度在于完全隐藏了单字母的频率。,3/1/2026,39,2,置换密码,在置换密码中，明文和密文的字母保持相同，但顺序被打乱了。,纵行置换密码：,明文以固定的宽度,水平,地写在一张图表纸上，密文按垂直方向读出；,解密将密文按相同的宽度,垂直,地写在图表纸上，然后水平地读出明文。,3/1/2026,40,例如：,明文：,encryption is the transformation of data into some unreadable form,书写为：,密文：,eiffob,nsodml,ctraee,rhmtuf,yeaano,pttirr,trinem,iaota,onnod,nsosa,3/1/2026,41,上机练习 对称加解密,一、,office,文件加密与解密,1,、创建,DOC,文件,2,、在,office,中加密,3,、下载,office password recovery toolbox 1.0.0.6.zip,安装运行,注：如果是其他类型的解密则难度大大提高,二、使用压缩工具,winrar,加密,压缩时，,winrar,的高级选项卡中可以选择带密码压缩,三、用,openssl,进行文件加密,3/1/2026,42,2.2,数据加密标准,(DES),2.2.1,分组密码简介,对称密码算法有两种类型：,分组密码,(Block Cipher):,一次处理一块输入，每个输入块生成一个输出块；,流密码,(Stream Cipher):,对输入元素进行连续处理，同时产生连续单个输出元素。,分组密码将明文消息划分成固定长度的分组，各分组分别在密钥的控制下变换成等长度的密文分组。,3/1/2026,43,基本原理,：,当前对称加密算法几乎都基于,Feistel,分组密码，,这是一种乘积密码：,连续执行两个或多个密码,Feristel,提出用替代和置换交替的方式构造密码,Shannon,提出用扰乱和扩散交替的方式构造密码,目的：挫败基于统计分析的密码分析方法,扩散：明文的统计结构扩散到密文中,扰乱：密文的统计特性与密钥的取值之间的关系尽可能复杂,3/1/2026,44,2.2.2,DES(Data,Encryption Standard),的历史,1973,年，美国国家标准局,(NBS),开始征集联邦数据加密标准的方案。,Feistel,等人研究了一种,128,位的对称密钥系统，,后,IBM,改进为,56,位的密钥系统，并提交,NBS,。,1975,年,3,月,17,日，,NBS,公布了,IBM,公司提供的密码算法，以标准建议的形式在全国范围内征求意见。,1977,年,7,月,15,日，,NBS,接受这个建议，数据加密标准,DES,正式颁布，供商业界和非国防性政府部门使用。,DES,成为一个使用规模庞大的信息安全处理标准。美国的许多专用系统纷纷宣布采用,DES,作为该系统的信息处理安全标准，如美国的海军系统、金融系统等。计算机厂商也大量生产以,DES,为基本算法的专用机、芯片、软件，形成了一个以,DES,算法为核心的数据安全加密市场。,3/1/2026,45,2.2.2,DES(Data,Encryption Standard),的历史,DES,算法每隔五年就被重新审查一次，分别在,1983,年、,1987,年、,1992,年通过了对其安全性的评估，作为标准一直使用到,1998,年。,随着计算机处理能力的提高，对,DES,的攻击不断显示出对其不利的因素，主要是其密钥过短，仅有,56,位。,最终，,NIST,于,1997,年发布公告，征集新的数据加密标准作为联邦信息处理标准以代替,DES,。新的数据加密标准称为,AES,尽管如此，,DES,仍然具有重要的参考价值，它对于我们掌握分组密码的基本理论与设计思想具有重要的意义。,争论：,1.56,位够长吗？,2.,内部结构公开，设计原理没公开？,3/1/2026,46,2.2.3 DES,算法的描述,DES,的描述,分组加密算法，它以,64,位为分组对数据进行加密,DES,是一个对称算法：加密和解密用的是同一算法,密钥的长度为,56,位。所有的保密性依赖于密钥。,算法是混乱和扩散的组合。,DES,基本组建分组是这些技术的一个组合,(,先代替后置换,),，它基于密钥作用于明文，,“,轮,(round),”,。,DES,有,16,轮，这意味着要在明文分组上,16,次实施相同的组合技术,此算法使用了标准的算术和逻辑运算，而其作用的数也最多只有,64,位，因此用,70,年代末期的硬件技术很容易实现。算法的重复,特性使得它可非常理想地用在一个专用芯片中。,3/1/2026,47,2.2.3 DES,算法的描述,DES,对明文进行分组操作，每组,64,位（密文也,64,位，每个第,8,位作奇偶校验，因此密钥,56bit,）。,1.,初始置换函数,IP,64,位明文分组,x,经过一个初始置换函数,IP,（打乱），产生,64,位的输出,x,0,，,再将分组,x,0,分成,左半部分,L,0,和,右半部分,R,0,，,即：,x,0,=,IP(x,)=L,0,R,0,置换表如表,2-1,所示。,此表顺序为从上到下，,从左至右。,58 50 42 34 26 18 10 2,60 52 44 36 28 20 12 4,62 54 46 38 30 22 14 6,64 56 48 40 32 24 16 8,57 49 41 33 25 17 9 1,59 51 43 35 27 19 11 3,61 53 45 37 29 21 13 5,63 55 47 39 31 23 15 7,表,2-1,初始置换,IP,3/1/2026,48,图,2-3 DES,加密算法,L0R0=,IP(x,),初始置换,for 1=i=16,Li,=Ri1,左半,=,（上一个）右半,Ri,=Li1 XOR f(Ri1,Ki,),上一个左半 异或 上一个右半和,新,key,作,F,运算,共作,16,轮,c=IP,1,(R16L16),末置换函数,3/1/2026,49,2,新key（,48BIT,）,：,获取新的子密钥,K,i,DES,加密算法的密钥长度为,56,位，一般表示为,64,位（每个第,8,位用于奇偶校验），将用户提供的,64,位初始密钥,经过一系列的处理得到,K,1,，,K,2,，,，,K,16,，,分别作为,1,16,轮运算的,16,个子密钥：,1,），将,64,位密钥去掉,8,个校验位，,用,密钥置换,PC1,置换剩下的,56,位密钥；,2,），将,56,位分成,前,28,位,C,0,和,后,28,位,D,0,，,即,PC1(K,56,)=C,0,D,0,。,57 49 41 33 25 17 9,1 58 50 42 34 26 18,10 2 59 51 43 35 27,19 11 3 60 52 44 36,63 55 47 39 31 23 15,7 62 54 46 38 30 22,14 6 61 53 45 37 29,21 13 5 28 20 12 4,表,2-2,密钥置换,PC1,3/1/2026,50,3,），根据轮数，这两部分分别循环左移,1,位或,2,位。,4,），移动后，将两部分合并成,56,位后通过,压缩置换,PC2,后得到,48,位子密钥,(,有些位被丢掉,),，即,K,i,=PC-2(C,i,D,i,),。,表,2-3,每轮移动的位数,轮次,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,位数,1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1,表,2-4,压缩置换,PC2,14 17 11 24 1 5,3 28 15 6 21 10,23 19 12 4 26 8,16 7 27 20 13 2,41 52 31 37 47 55,30 40 51 45 33 48,44 49 39 56 34 53,46 42 50 36 29 32,3/1/2026,51,图,2-4,子密钥产生,子密钥生成算法,：,C0D0=PC1(K),初始置换,for 1=i=16,Ci,=LSi(Ci1),Di,=LSi(Di1),循环左移,Ki,=PC2(CiDi),压缩置换,16,轮，每轮出一个,key,3/1/2026,52,3,F,运算,：密码函数,F,（非线性的）（上一个右半和新,key,作,F,运算）,1),函数,F,的操作步骤,密码函数,F,的输入是,32,比特数据,和,48,比特的子密钥,。,(1.1),扩展置换,(E),将数据的右半部分,Ri,从,32,位扩展为,48,位。,位选择函数,(,也称,E,盒,),：,扩展置换,(E),32 1 2 3 4 5,4 5 6 7 8 9,8 9 10 11 12 13,12 13 14 15 16 17,16 17 18 19 20 21,20 21 22 23 24 25,24 25 26 27 28 29,28 29 30 31 32 1,3/1/2026,53,图,2-5,F(R,i,K,i,),计算,32,比特,3/1/2026,54,(1.2),异或,。扩展后的,48,位输出,E(R,i,),与压缩后的,48,位密钥,K,i,作异或运算。,(1.3),S,盒替代,。将异或得到的,48,位结果分成,八个,6,位的块,，每一块通过对应的一个,S,盒产生一个,4,位的输出,。,S,盒的具体置换过程,(,行和列均从,0,开始计数,),。,：,某个,Si,盒的,6,位输入的第,1,位和第,6,位形成一个,2,位的二进制数，对应表中的某一行；,输入的中间,4,位构成,4,位二进制数对应表中的某一列；,例：,第,8,个,S,盒的输入为,0,0101,1,，对应第,8,个,S,盒的第,1,行第,5,列（数为,6,），就用,6,（,0110,）代替原输入,001011,。,5,3/1/2026,55,表,2-6 S,盒,S,1,盒,14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7,0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8,4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0,15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,S,2,盒,15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10,3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5,0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15,13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9,S,3,盒,10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8,13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1,13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7,1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12,S,4,盒,7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15,13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9,10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4,3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14,S,5,盒,2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9,14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6,4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14,11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3,S,6,盒,12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11,10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8,9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6,4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13,S,7,盒,4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1,13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6,1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2,6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12,S,8,盒,13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7,1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2,7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8,2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11,3/1/2026,56,(1.4),P,盒置换,。将八个,S,盒的输出连在一起生成一个,32,位的输出，输出结果再通过置换,P,产生一个,32,位的输出即：,F(R,i,K,i,),。,最后,，将,P,盒置换的结果与最初的,64,位分组的左半部分异或，,然后,，左、右半部分交换，,开始下一轮计算。,16 7 20 21,29 12 28 17,1 15 23 26,5 18 31 10,2 8 24 14,32 27 3 9,19 13 30 6,22 11 4 25,表,2-7 P,盒置换,3/1/2026,57,2),函数,F,的设计,F,是,DES,加密的核心，依赖于,S,盒的设计。,（适用其它对称分组加密算法）,(1)F,的设计准则,。,（扩散作用）,非线性越高越好,，使要恢复,F,所做的“扰乱”操作越难越好。,严格雪崩准则,(SAC),，,要求算法具有良好的雪崩效应，输入当中的一个比特发生变化都应当使输出产生尽可能多的比特变化。,严格地说，就是当任何单个输入比特位,i,发生变换时，一个,S,盒的第,j,比特输出位发生变换的概率应为,1/2,，且对任意的,i,j,都应成立。,比特独立准则,(BIC),，当单个输入比特位,i,发生变化时，输出比特位,j,k,的变化应当互相独立，且对任意的,i,j,k,均应成立。,（,SAC,和,BIC,可以有效的增强,F,函数的“扰乱”功能，,这是古典密钥不具备的）,3/1/2026,58,(2)S,盒设计,。,S,盒的作用,就是对输入向量进行处理，使得输出看起来更具随机性，输入和输出之间应当是非线性的，很难用线性函数来逼近。,（比特之间的混合作用）,S,盒的尺寸是一个很重要的特性。一个的,S,盒其输入为,n,比特，输出为,m,比特。,S,盒越大，就越容易抵制差分和线性密码分析。,(,在实践当中，通常选择,n,在,8,10,之间,),3/1/2026,59,Mister,和,Adams,提出：,要求,S,盒满足,SAC,和,BIC,的原则,S,盒的所有列的全部线性组合应当满足,Bent,函数的高度非线性布尔函数的原则。,Bent,函数具有很多有趣的特性对于,S,盒的设计很重要,如,:,高度非线性,最高阶的严格雪崩准则,Nyberg,提出了：,随机性：采用某些伪随机数发生器或随机数表格来产生,S,盒的各个项。,随机测试：随机选择,S,盒各个项，然后按照不同准则测试其结果。,数学构造：根据某些数学原理来产生,S,盒。其好处就是可以根据数学上的严格证明来抵御差分和线性密码分析，并且可以获得很好的扩散,(Diffusion),特性。,3/1/2026,60,4,末置换函数,IP,-1,末置换是初始置换的逆