ch02 密码学基础01概述+对称密码

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,0 1 ,0,1,0,第二部分密码学基础,密码学概述,对称密码学,单向散列函数,公钥密码系统,8,7,6,5,4,3,密码学概述,密码学的发展,基本术语,保密通信系统模型,密码体制,密码分析,密码算法的安全性,密码学的发展,密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码(Cipher),由于密码长期以来仅用于政治、军事、公安、外交等要害部门，其研究本身也只限于秘密进行。所以密码被蒙上神秘的面纱。在军事上，密码成为决定战争胜负的重要因素之一。有些军事评论家认为，盟军在破译密码方面的成功，使二次世界大战提前几年结束。,密码学是研究如何对敏感信息进行保护的一门重要学科。,随着计算机和通信技术的迅速发展和普及应用，出现了电子政务、电子商务、电子金融等重要的应用信息系统。在这些系统中必须确保信息的安全传递和存储,密码学的发展,1949年之前：古典密码（classical cryptography),密码学多半是具有艺术特征的字谜，出现一些密码算法和机械的加密设备,。,密码算法的基本手段是：替代和置换(substitution,&,permutation)出现，针对的是字符,。,密码破译的手法逐渐形成，二次世界大战尤为明显,。,19491975年:,计算机使得基于复杂计算的密码成为可能,1949年Shannon,：,The Communication Theory of Secret Systems,1967年David,Kahn的The,Codebreakers,1971-73年IBM,Watson实验室的Horst,Feistel等的几篇技术报告,数据的安全基于密钥而不是算法的保密,密码学的发展,1976年以后:,1976年Diffie和Hellman发表了“密码学的新方向”（New Directions in Cryptography）提出了不对称密钥密码，奠定了公钥密码学的基础。,1977年Rivest,Shamir& Adleman提出了RSA公钥算法。,公钥技术是二十世纪最伟大的思想之一,改变了密钥分发的方式,可以广泛用于数字签名和身份认证服务,90年代逐步出现椭圆曲线等其他公钥算法,公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,密码学的发展,1976年以后，对称密钥密码算法进一步发展,1977年DES正式成为标准,80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等,90年代对称密钥密码进一步成熟Rijndael,RC6, MARS, Twofish, Serpent等出现,2001年Rijndael成为DES的替代者，有了新的分组密码加密标准AES,密码学的发展,总结,未来会有什么密码？,物理,密码,计算,密码,古典,密码,艺术,密码,基本术语,密码体制是密码技术中最为核心的一个概念。密码体制被定义为一对数据变换,：,基本术语,密码技术的,基本思想,是伪装信息，伪装就是对数据施加一种可逆的,数学变换,。伪装前的数据称为,明文,(Plaintext), 伪装后的数据称为,密文,(Ciphertext)。伪装的过程称为,加密,(Encryption), 去掉伪装恢复明文的过程称为,解密,(Decryption)。加/解密要在,密钥,(Key)的控制下进行。将数据以密文的形式存储在计算机的文件中或送入网络信道中传输，而且只给合法用户分配密钥。这样即使密文被非法窃取，因不法分子没有密钥而不能得到明文。,基本术语,密码员对明文进行加密操作时所采用的一组规则称作,加密算法,(Encryption Algorithm),。,所传送信息的预定对象称为接收者,(Receiver),。,接收者对密文解密所采用的一组规则称为,解密算法,(Decryption Algorithm),。,密码学,(Cryptology):,是研究信息系统安全保密的科学。,密码编码学,(Cryptography):,主要研究对信息进行编码,实现对信息的隐蔽。,密码分析学,(Cryptanalytics):,主要研究对密文（对明文加密后而得的信息）的破译和对明文的伪造,密码学的分类,密码学,编码学：密码的设计,分析学：密码的破译,其它,安全管理，安全协议设计，秘密分存,现代：数字化现金，量子密码，馄饨,密码等,相互依存,相互支持,密不可分,保密系统通信模型,密码学的,目的,：,郭靖,和,黄蓉,两个人在不安全的信道上进,行悄悄话通信，而,第三者欧阳克,不能理解与破坏他们通信的内容。,密码体制,定义: (密码体制）它是一个五元组（P,C,K,E,D)：,（1）P是可能明文的有限集；（明文空间）,（2）C是可能密文的有限集；（密文空间）,（3）K是一切可能密钥构成的有限集（密钥空间）,（4）E 加密算法。,（5）D 解密算法。,对于任意kK,有一个加密算法e,k,E和相应的解密算法d,k,D，使得e,k,: PC和d,k,:CP分别为加密解密函数，满足d,k,(e,k,(x)=x, 这里xP。,空间集合的大小与安全有什么关系？,攻击动画,密码体制分类方法,可从三种不同的角度进行分类,（1）从明文到密文的变换,替换(substitution),换位,(Transposition),置换(permutation),（2）钥匙的数目,对称、单钥加密法,双钥、公钥加密,（3）明文的处理方式,分组加密（块加密算法）,流方式加密,传统： 加密 解密,分类,传统密码：人工,计算机密码,现代,双钥：公钥,/,私钥,字符,:,流密码,分组,:,分组密码,单钥,单钥,单钥,传统： 加密 解密,分类,传统密码：人工,计算机密码,现代,双钥：公钥,/,私钥,字符,:,流密码,分组,:,分组密码,单钥,单钥,单钥,密码体制分类方法,-1,基于密钥的算法，按照密钥的特点分类：,􀂾,对称密钥算法,（symmetric cipher)：又称,传统密钥算法,（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。,􀂾,非对称密钥算法,（asymmetric cipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称,公开密钥算法,（public-key cipher) 。,􀂋公开密钥算法用一个密钥进行加密，而用另一个密钥进行解密。其中的,加密密钥,可以公开，又称公开密钥（public key)，简称,公钥,。,解密密钥,必须保密，又称私人密钥（private key)私钥，简称,私钥,。,三种方法分析,1.,三种方法各有什么特点？,2.,可否将一些方法混合使用，以充分利用其各自的特点？,三种方法分析,密码体制分类方法,-2,按照加密过程中对明文的处理方法：,分组密码,（block cipher)：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。,流密码,（stream cipher)：又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。,序列密码是手工和机械密码时代的主流,密码分析,发现X和K的过程被称为,密码分析,分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到的技术,根据可利用信息的不同，可分为4类：,（1）只有密文,（2）已知部分明文-密文对,（3）选择明文,（4）选择密文,* （1）（2）（3）常见、（4）不常见,对密码系统的攻击类型,对密码系统的攻击类型,自适应选择明文攻击,自适应选择明文攻击,(adaptive-chosen-plaintext attack),：是选择明文攻击的一种特殊情况，指的是密码分析者不仅能够选择被加密的明文，也能够依据以前加密的结果对这个选择进行修正。,自适应选择密文攻击,密码破译的手段,密码破译的原则,:,遵循观察与经验,方法,:,采用归纳与演绎,步骤,:,分析、假设、推测和证实,三大要素：,语言的频率特征：,e,连接特征,: q u, I e x,重复特征,: th, tion, tious,单表替换密码的破译,通过字母的使用频率破译,密码算法的安全性,无条件安全（,Unconditionally secure,）,无论破译者有多少密文,他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。,计算上安全（,Computationally secure,）,破译的代价超出信息本身的价值,破译的时间超出了信息的有效期。,直觉：什么是一个好的加密算法,假设密码,(password)k,是固定的,明文和密文是一个映射关系：单射，即,E,k,(x,1,) E,k,(x,2,) if x,1,x,2,通常情况是：明文非常有序,好的密码条件下，我们期望得到什么样的密文,随机性,如何理解随机性,静态：特殊的点,动态：小的扰动带来的变化不可知,考虑设计一个加密算法,打破明文本身的规律性,􀂾,随机性,(,可望不可及,),非线性,(,一定要,),统计意义上的规律,多次迭代,􀂾,迭代是否会增加变换的复杂性,是否存在通用的框架，用于迭代,复杂性带来密码分析的困难和不可知性,􀂾,实践的检验和考验,柯克霍夫（,Kerckhoffs,）原则,柯克霍夫（,Kerckhoffs,）原则：密码系统的安全性取决于密钥，而不是密码算法，即密码算法要公开。,这是荷兰密码学家,Kerckhoff,于,1883,年在名著,军事密码学,中提出的基本假设。遵循这个假设的好处是：, 它是评估算法安全性的惟一可用的方式。因为如果密码算法保密的话，密码算法的安全强度无法进行评估。, 防止算法设计者在算法中隐藏后门。因为算法公开后，密码学家可以研究分析是否存在漏洞，同时也接受攻击者的检验。, 有助于推广使用。当前网络应用十分普及，密码算法的应用不再局限于传统的军事领域，只有算法公开，才可能被大多数人接受并使用，同时，对用户而言，只需掌握密钥就可以使用。,对称密码学,古典密码,1.,移位密码,2.,仿射密码,3.,维吉利亚,(Vigenere),密码,4.,置换密码,对称加密体制,1,序列密码,2,分组密码,3,数据加密标准,DES,艺术密码与古典密码,艺术密码,可以通过多种方式来实现，主要方式包括：文字变形、在艺术作品中加入巧妙的手笔、符号的适当排列等等，目前已经发展成为隐写术。,古典密码,本质上是一种以线性代数为基础的密码形式，主要包括置换密码体制和代换密码体制。,许多文献直接将艺术密码归为古典密码,艺术密码实例,水浒传吴用智赚玉麒麟,芦,花丛中一扁舟，,俊,杰俄从此地游，,义,士若能知此理，,反,躬难逃可无忧。,早妆未罢暗凝眉，,迎户愁看紫燕飞，,无力回天春已老，,双栖画栋不如归。,艺术密码实例,水洗尘埃道未,甞,，甘于名利两相忘。,心怀六洞丹霞客，口诵三清紫府章。,十里采莲歌达旦，一轮明月桂飘香。,日高公子还相觅，见得山中好酒浆。,艺术密码实例,艺术密码实例,The word steganography, with origin in Greek, means,“covered writing,”,in contrast with cryptography, which means “,secret writing,.”,Example: covering data with text,Example: using dictionary,Example: covering data under color image,古典密码编码学之外：最牛游戏玩家,密码学破译隐藏任务,游戏,大航海时代,Online,永远的矢车菊任务至今尚未被人破解,两位堪称史上最牛的玩家冰魂心、,水镜却利用,密码学,知识找到了一丝曙光！,破译优势信息,在城里领了,26,个物品后，提示卡纳冯伯爵在金字塔附近，但是，无论换什么衣服和他说话，都没有实质性反应。,永远的矢车菊任务连锁到：寻找大盗墓集团，和海事公会会长对话三次，分别给出提示：“,4445332443”,、“,434512454212”,、“,42452433”,。,古典密码编码学之外：最牛游戏玩家,密码学破译隐藏任务,暗示一,数字替代法是,密码学,中常用的方法,先分拆这个数列,找到数字替代的字母,暗示二,如何分拆数字,第一行,10,个数字，第二行,12,个数字，第三行,8,个数字，,3,数字分拆不完整,采用,2,数字分拆,44 45 33 24 4343 45 12 45 42 1242 45 24 33,暗示三,所有数字都是由,1-5,以内的数字组成,暗合,棋盘密码,古典密码编码学之外：最牛游戏玩家,密码学破译隐藏任务,棋盘密码,公元前,2,世纪，伟大的希腊历史学家、军事家、数学家波利比奥斯发明了波利比奥斯方表,Polybius Square,棋盘密码,1,2,3,4,5,1,a,b,c,d,e,2,f,g,h,i,k,3,l,m,n,o,p,4,q,r,s,t,u,5,v,w,x,y,z,明文,：,tuni(j)stunis,突尼斯,suburb,郊外,rui(j)nruin,废墟,古典密码,1.,移位密码,移位密码的加密方法是将明文字母按某种方式进行移位，如著名的恺撒密码。在移位密码中，,将,26,个英文字母依次与,0,1,2,25,对应,，密文字母,c,可以用明文字母,m,和密钥,k,按如下算法得到：,c=m+k,(mod 26),给定一个密文字母,c,对应的明文字母,m,可由,c,和密钥,k,按如下算法得到：,m=c-k,(mod 26),按照密码体制的数学形式化定义，移位密码体制描述为五元组,(,P,，,C,，,K,，,E,，,D,),，其中：,P,=,C,=,K,=,Z,26,=0,，,1,，,2,，,，,25,，,E,=,e,k,:,Z,26,Z,26,|,e,k,(,m,)=,m,+,k,(mod 26),，,D,=,d,k,:,Z,26,Z,26,|,d,k,(,c,)=,c,k,(mod 26),。,古典密码,2.,仿射密码,仿射密码和移位密码一样,也是一种替换密码,.,不同的是,移位密码,中,我们使用的是,模,n,加,;,而在下面的仿,射密码,中,我们使用的是,模,n,乘,.,在安全性方面,仿射密码同移位密码一样,都是,极其差,的,不仅因为他们的原理简单,更要命,的是这两种替换密码,没有隐藏明文的字频信息,这很容易导致破解者轻易的攻破,.,古典密码,2.,仿射密码,仿射密码算法如下：,(1),明密文字母表为,Z26(2),秘匙,K=(a,b)Z26_Z26.,其中,Z26_,表示小于,26,且与,26,互素,(,或叫互质,),的正整数的集合,这点非常重要的,.,（为什么？）,(3),加密变换为,y=(ax+b)mod26;,(4),解密变换为,:x=a,-1,(y-b)mod26,若,a,b,两数的乘积对正整数,n,取模的结果为,1.,则称,a,b,互为另外一个的模逆,.,比如,:3*7=21;21%20=1;,所以,3,7,互为,20,的模逆,.9*3=27;27%26=1;,所以,9,3,互为,26,的模逆,.,古典密码,例,假设,k,1,=9,和,k,2,=2,，明文字母为,q,则对其用仿射密码加密如下：,先把文字母为,q,转化为数字,13,。由加密算法得,c,=9,13+2=119 (mod 26)=15,再把,c,=15,转化为字母得到密文,P,。,解密时，先计算,k,1,1,。因为,9,3,1(mod 26),，因此,k,1,1,=3,。再由解密算法得,m,=,k,1,1,(,c,k,2,) (mod 26)=3,(,c,-2)=3,c,-6 (mod 26),45+20 (mod 26)=13 (mod 26),。,对应的明文字母为,q,。,古典密码,3.,维吉利亚,(Vigenere),密码,Vigenere,是法国的密码学专家，,Vigenere,密码是以他的名字命名的。该密码体制有一个参数,n,。在加解密时同样把英文字母用数字代替进行运算，并按,n,个字母一组进行变换。明、密文空间及密钥空间都是,n,长的英文字母串的集合，因此可表示,P,=,C,=,K,=(,Z,26,),n,。加密变换如下：,设密钥,k,=(,k,1,k,2,k,n,),，明文,P,=(,m,1,m,2,m,n,),，加密函数,e,k,(,P,)=(,c,1,c,2,c,n,),，其中,c,i,=(,m,i,+,k,i,) (mod 26),i,=1, 2,n,。,对密文,c,=(,c,1,c,2,c,n,),，密钥,k,=(,k,1,k,2,k,n,),，解密变换为,d,k,(,c,)=(,m,1,m,2, ,m,n,),，其中,m,i,=(,c,i,k,i,) (mod 26),i,=1, 2, ,n,。,古典密码,例 设,n,=6,， 密钥是,cipher,，这相应于密钥,k,=(2, 8, 15, 7, 4, 17),，明文是,this cryptosystem is not secure,。试用,Vigenere,密码对其加密。,解 首先将明文按每,6,个分为一组，然后与密钥进行模,26,“加”得：,19 7 8 18 2 17 24 15 19 14 18 24,2 8 15 7 4 17 2 8 15 7 4 17,21 15 23 25 6 8 0 23 8 21 22 15,18 19 4 12 8 18 13 14 19 18 4 2 20 17 4,2 8 15 7 4 17 2 8 15 7 4 17 2 8 15,20 1 19 19 12 9 15 22 8 25 8 19 22 25 19,相应的密文是：,VPXZGIAXIVWPUBTTMJPWIZITWZT,古典密码,4.,置换密码,置换密码是把明文中各字符的,位置次序重新排列,来得到密文的一种密码体制。实现的方法多种多样。在这里，我们介绍一类较常见的置换密码。,其加解密方法如下：把明文字符以固定的宽度,m,(,分组长度,),水平地,(,按行,),写在一张纸上（如果最后一行不足,m,，需要补充固定字符），按,1,，,2,，,，,m,的一个置换,交换列的位置次序，再按垂直方向,(,即按列,),读出即得密文。,解密就是将密文按相同的宽度,m,垂直在写在纸上，按置换,的逆置换交换列的位置次序，然后水平地读出得到明文。置换,就是密钥。,古典密码,例 设明文,Joker is a murderer,，密钥,=(4 1)(3 2)(,即,(4)=1,，,(1)=4,，,(3)=2,，,(2)=3),即按,4,，,3,，,2,，,1,列的次序读出得到密文，试写出加解密的过程与结果。,解：加密时，把明文字母按长度为,4,进行分组，每组写成一行，这样明文字母,Joker is a murderer,被写成,4,行,4,列，然后把这,4,行,4,列按,4,，,3,，,2,，,1,列的次序写出得到密文。过程与结果如图,2-3-1,所示。解密时，把密文字母按,4,个一列写出，再按,的逆置换重排列的次序，最后按行写出，即得到明文。,明文：,Joker is a murderer,按,4,字母一行写出,joke,risa,murd,erer,按列写出的顺序,4 3 2 1,按列写出密文：,eadrksreoiurjrme,密文：,eadrksreoiurjrme,按,4,字母一列写出,ekoj,asir,drum,rere,交换列的顺序,4 3 2 1,按行写出明文：,joker is a murderer,古典密码,总结,在现代密码学中，假定密码方案遵从,Kerckhoffs,原则，因此，对密文的破解取决于加密密钥。就古典密码而言，由于算法相对简单，算法复杂度也不高，一种可能的攻击方法是对所有可能的密钥进行尝试的强力攻击，称为穷举搜索攻击。,移位密码：密钥空间,K,=,Z,26,=0,，,1,，,2,，,，,25,，因此，最多尝试,26,次即可恢复明文。,古典密码,总结,仿射密码：密钥空间为,K,=(,k,1,，,k,2,)|,k,1,，,k,2,Z,26,其中,gcd(,k,1, 26)=1,，,k,1,可能的取值有,1,，,3,，,5,，,7,，,9,，,11,，,15,，,17,，,19,，,21,，,23,，,25,，因此，最多尝试,12,26,次即可恢复明文。,对于古典密码方案而言，由于密钥空间非常有限，因此，很难抵抗穷举搜索攻击。另一方面，就英文而言，一些古典密码方案不能很好地隐藏明文消息的统计特征，攻击者也可以利用这一弱点进行破译。,结论：古典密码方案并不适合,Kerckhoffs,原则，密码方案的保密性基于算法的保密。,对称加密体制,序列密码,分组密码,数据加密标准,DES,这个世界的问题在于聪明人充满疑惑，而傻子们坚信不疑。,-,罗素,对称加密体制,在这种密码体制中，对于大多数算法而言，解密算法是加密算法的逆运算，加密密钥和解密密钥相同，满足关系：,M= D,k,(C)= D,k,(E,k,(M),。,对称密码体制的开放性差，要求通信双方在通信之前，商定一个共享密钥，彼此必须妥善保管。,对称密码体制分为两类。一类是对明文的单个位（或字节）运算的算法，称为,序列密码算法，也称为流密码算法,(Stream Cipher),。另一类算法是把明文信息划分成不同的块（或小组）结构，分别对每个块进行加密和解密，称为,分组加密算法,(Block Cipher),。,滚动密钥生成器,.,滚动密钥生成器,.,E,zi,(M,i,),D,zi,(C,i,),K,K,i,K,C,i,M,i,K,i,同步流密码体制模型,:,密钥流与明文串相互独立,M,i,E,zi,(M,i,),D,zi,(C,i,),流密码的基本思想,：产生一个密钥流,k=k,1,k,2,根据下面规则加密明文,M = m,1,m,2,;,C = C,1,C,2,= E,K1,(m,1,) E,K2,(m,2,),序列密码,(,流密码,),滚动密钥生成器,.,滚动密钥生成器,.,K,Z,i,K,Y,i,X,i,Z,i,X,i,+,加法流密码体制模型,+,序列密码,序列密码,序列密码分为同步序列密码和自同步序列密码两种。,同步序列密码要求发送方和接收方必须是同步的，在同样的位置用同样的密钥才能保证正确地解密。如果在传输过程中密文序列有篡改、删除、插入等错误导致同步失效，则不可能成功解密，只能通过重新同步来实现恢复。在传输期间，一个密文位的改变只影响该位的恢复，不会对后继位产生影响。,自同步序列密码的密钥的产生与密钥和已产生的固定数量的密文位有关，因此，密文中产生的一个错误会影响到后面有限位的正确解密。因此，自同步密码的密码分析比同步密码更加困难。,序列密码具有实现简单、便于硬件计算、加解密处理速度快、低错误（没有或只有有限位的错误）传播等优点，但同时也暴露出对错误产生不敏感的缺点。,序列密码,序列密码的安全强度依赖于密钥流产生器所产生的密钥流序列的特性，关键是密钥生成器的设计及收发两端密钥流产生的同步技术。,1.,伪随机序列,在序列密码中，一个好的密钥流序列应该满足：,良好的伪随机性，如极大的周期，极大的线性复杂度，序列中,0,和,1,的分布均匀；产生的算法简单；硬件实现方便。,产生密钥流序列的方法可以是使用自然现象随机生成或标准,C,库函数中函数,rand(),。,产生伪随机数的一个不错的选择是使用数论中的难题。最常用的是,BBS,伪随机序列生成器：产生两个大素数,p,和,q,，且 ，设,n=pq,，并选择一个随机整数,x,(,x,与,n,互素,),设初始输入 ，,BBS,通过如下过程产生一个随机序列 ：, ；, 是 的最低有效比特。,序列密码,2.,线性反馈移位寄存器,通常，产生密钥流序列的硬件是反馈移位寄存器。一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数：,a,n,a,n-1,a,2,a,1,f(,a,1,a,2,a,n,),输出序列,f (a,1,a,2,a,n,) = c,n,a,1,c,n-1,a,2,. c,1,a,n,+,+,+,序列密码,序列密码,对于,n,级线性反馈移位寄存器，不可能产生全,0,状态，因此，最大可能周期为 。,选择线性反馈移位寄存器作为密钥流生成器的主要原因有：适合硬件实现；能产生大的周期序列；能产生良好的统计特性的序列；它的结构能够应用代数方法进行很好的分析。,实际应用中，通常将多个,LFSR,组合起来构造非线性反馈移位寄存器，,n,级非线性反馈移位寄存器产生伪随机序列的周期最大可达到 ，因此，研究产生最大周期序列的方法具有重要意义。,序列密码,3.,RC4,RC4,是由麻省理工学院的,Ron Rivest,教授在,1987,年为,RSA,公司设计的一种可变密钥长度、面向字节流的序列密码。,RC4,算法很简单，它以一个数据表为基础，对表进行非线性变换，从而产生密码流序列。包含两个主要算法：密钥调度算法,(Key-Scheduling Algorithm,，,KSA),和伪随机生成算法,(Pseudo Random Generation Algorithm,，,PRGA),。,序列密码,KSA,的作用是将一个随机密钥,(,大小为,40256,位,),变换成一个初始置换表,S,。过程如下：,S11 S,表中包含,256,个元素,S0S255,，对其初始化，令,S12,用主密钥填充字符表,K,，如果密钥的长度小于,256,个字节，则依次重复填充，直至将,K,被填满。,S13,令,j,=0,；,S14,对于,i,从,0,到,255,循环,交换,Si,和,Sj,。,序列密码,PRGA,的作用是从,S,表中随机选取元素，并产生密钥流。过程如下：,S21,i=0,j=0,；,S22,i=i+1(mod 256),；,S23,j=j+Simod 256,S24,交换,Si,和,Sj,；,S25,t=Si+Sjmod 256,；,S26,输出密钥字,k=St,。,虽然,RC4,要求主密钥,K,至少要,40,位，为了保证安全强度，目前至少要达到,128,位。,分 组 密 码,分组密码概述,分组密码是将明文消息序列,m,1,，,m,2,，,，,m,1k,分成等长的消息组,(m,1,，,m,2,，,，,m,n,),，,(m,n+1,，,m,n+2,，,，,m,2n,), ,在密钥控制下，按固定的算法,E,k,一组一组进行加密。加密 后输出等长密文组（,y,1,，,，,y,m,), (y,m+1,，,，,y,2m,) ,加 密 算 法,密 钥,k,明文,(x,1,，,x,2,，,，,x,n,),密文,(y,1,，,y,2,，,，,y,n,),加密一组明文的过程,分组密码,分组加密的本质就是由密钥 控制的从明文空间,M,（长为,n,的比特串的集合）到密文空间,C,（长为,r,的比特串的集合）的一个,1-1,映射。为了保证密码算法的安全强度，一般说来，加密变换的构造应遵循下列几个原则：, 分组长度足够大, 密钥量空间足够大, 加密变换足够复杂, 加密和解密运算简单，易于实现, 加密和解密的逻辑结构最好一致,分组密码,古典密码中最基本的变换是代替（,substitution cipher),和移位,(,置换,permutation cipher),，其目的是产生尽可能混乱的密文。代替变换就是经过复杂的变换关系将输入位进行转换，记为,S,，称为,S,盒；移位变换就是将输入位的排列位置进行变换，记为,P,，称为,P,盒。,分组密码由多重,S,盒和,P,盒组合而成，如图所示。,S,盒的直接作用是将输入位进行某种变换，起到混乱作用，,P,盒的直接作用就是移动输入位的排列位置关系，起到扩散的作用。,分组密码,实现分组密码设计算法的具体操作包括以下三个方面：,1.,代替,将明文位用某种变换关系变换成新的位，使得产生的密文是一堆杂乱无章的乱码，分组密码中采用复杂的非线性代替变换就可达到比较好的混乱效果。,2.,移位,指让明文中的每一位,(,包括密钥的每一位,),直接或间接影响输出密文中的许多位，以便隐蔽明文的统计特性。这种效果也称为“雪崩效应”。,3.,乘积变换,在分组密码算法设计中，为了增强算法的复杂度，常用的方法是采用乘积变换的思想，即加密算法不仅仅是简单的一次或两次基本的,S,盒和,P,盒变换，而是通过两次或两次以上,S,盒和,P,盒的反复应用，也就是迭代的思想，克服单一密码变换的弱点，构成更强的加密结果，以强化其复杂程度。,数据加密标准,-DES,1971,年末,IBM,公司提出了一种称为,Lucifer,的密码算法,1977,年,7,月,15,日该算法被正式采纳作为美国联邦信息处理标准生效，即数据加密标准（,Data Encryption Standard,，,DES,）。实现分组密码设计算法的具体操作包括以下三个方面：,1.,DES,加密算法流程,乘,积,变,换,数据加密标准,-DES,DES,加密过程,64,位明文, , , , ,密钥（,1,）,密钥（,2,）,密钥（,3,）,密钥（,16,）,算法概要,L,i,= R,i-1,R,i,= L,i-1, f (R,i-1, K,i,),R,i-1,压缩置换,扩展置换,S-,盒代替,L,i-1,L,i,密 钥,密 钥,移位,移位,P-,盒转换,R,i,带有密钥变换的,DES,的一轮迭代,数据加密标准,-DES,(1),初始置换,IP,初始置换如图所示，方法是将,64,位明文的位置顺序打乱，表中的数字代表,64,位明文的输入顺序号，表中的位置代表置换后的输出顺序，表中的位置顺序是先按行后按列进行排序。,初始置换表中的位序特征：,64,位输入按,8,行,8,列进行排列，最右边一列按,2,4,6,8,和,1,3,5,7,的次序进行排列，往左边各列的位序号依次紧邻其右边一列各序号加,8,。,数据加密标准,-DES,(2),乘积变换（,16,轮迭代）,乘积变换部分要进行,16,轮迭代，如图所示。将初始置换得到的,64,位结果分为两半，记为,L,0,和,R,0,，各,32,位。设初始密钥,64,位，经密钥扩展算法产生,16,个,48,位的子密钥，记为,K,1,，,K,2,，,，,K,16,，每轮迭代的逻辑关系为：,其中 ，,f,函数是每轮变换的核心变换,。,32,32,数据加密标准,-DES,(3),逆初始置换,IP,-1,逆初始置换,IP,-1,与初始置换正好相反，如图所示。比如，处在第一位的比特位置换后排在第,58,位，第二位排在第,50,位。,逆初始置换表中的位序特征：,64,位输入依然按,8,行,8,列进行排列，,1,2,3,4,5,6,7,8,按列从下往上进行排列，然后是,9,到,16,排在右边一列，依次进行排,4,列，然后从,33,开始排在第一列的左边，从,41,开始排在第二列的左边，交叉进行。,数据加密标准,-DES,2.,乘积变换中的,f,变换,乘积变换的核心是,f,变换，它是非线性的，是每轮实现混乱的最关键的模块，输入,32,位，经过扩展变换变成,48,位，与子密钥进行异或运算，选择压缩变换,S,盒替换，将,48,位压缩还原成,32,位，再进行,P,盒替换，输出,32,位。如图所示，阴影部分为,f,变换。,数据加密标准,-DES,详,细,变,化,如,图,所,示,DES,：,加密运算和压缩运算,密钥加密运算,：将子密钥产生器输出的,48 bit,子密钥,k,i,与选择扩展运算,E,输出的,48 bits,数据按位模,2,相加。,选择压缩运算,S,：将前面送来的,48 bit,数据自左至右分成,8,组，每组为,6 bit,；而后并行送入,8,个,S,一盒，每个,S,盒为一非线性代换网络，有,4,个输出。,48 bit,寄存器,32 bit,寄存器,S,1,S,2,S,3,S,4,S,5,S,6,S,7,S,8,6,位,4,位,选择函数组,数据加密标准,-DES,(1),扩展置换,扩展置换将,32,位扩展成,48,位，按如图,2-4-12,所示的排列方式进行重新排列得到。,DES,：,选择扩展运算,选择扩展运算,E,：将输入的,32 bit,R,i-1,扩展成,48 bit,的输出,令,s,表示,E,原输入数据比特的原下标，则,E,的输出是将原下标,s,0,或,1(mod 4),的各比特重复一次得到的，即对原第,32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29,各位都重复一次,实现数据扩展。,扩展,2.4.3,数据加密标准,-DES,(2) S,盒替换,将,48,位按,6,位分为,1,组，共,8,组，也称为,8,个,S,盒，记为,S,1,，,S,2,，,S,8,，每个,S,盒产生,4,位输出。,8,个,S,盒的替换表如表,2-4-2,所示。,每个,S,盒都由,4,行,16,列组成，每行是,0,15,的一个全排列，每个数字用对应的,4,位二进制比特串表示。如,9,用,1001,表示，,7,用,0111,表示。设,6,位输入为：,a,1,a,2,a,3,a,4,a,5,a,6,，将,a,1,a,6,组成一个,2,位二进制数，对应,S,盒表中的行号；将,a,2,a,3,a,4,a,5,组成一个,4,位二进制数，对应,S,盒表中的列号；映射到交叉点的数据就是该,S,盒的输出。,2.4.3,数据加密标准,-DES,(2) S,盒替换,2.4.3,数据加密标准,-DES,(2) S,盒替换,DES,中其它算法都是线性的，而,S-,盒运算则是非线性的,S-,盒不易于分析，它提供了更好的安全性,所以,S-,盒是算法的关键所在,数据加密标准,-DES,(3),P,盒替换,P,盒替换就是将,S,盒替换后的,32,位作为输入，按下图顺序重新排列，得到的,32,位结果即为,f,函数的输出,f,(,R,i,-1,，,K,i,),。,数据加密标准,-DES-,子密钥的生成,数据加密标准,-DES,3.,子密钥的生成,初始密钥长度为,64,位，但每个第,8,位是奇偶校验位，分布在第,8,、,16,、,24,、,32,、,40,、,48,、,56,和,64,位的位置上，目的是用来检错，实际的初始密钥长度是,56,位。在,DES,算法中，每一轮迭代需要使用一个子密钥，子密钥是从用户输入的初始密钥来产生的。右图是各轮子密钥产生的流程图。,初始密钥,K ( 64 bit ),PC 1 (56bit),LS,1,C,0,(28 bit ) D,0,(28 bit ),LS,1,C,1,D,1,LS,2,LS,2,LS,16,LS,16,C,16,D,16,PC - 2,K,1,(48 bit ),PC - 2,K,16,(48 bit ),压缩置换,密钥置换,数据加密标准,-DES,(1),密钥置换,(PC-1),与压缩置换,(PC-2),对于,64,位初始密钥,K,，按下表中置换表,PC-1,进行重新排列。不难算出，丢掉了其中,8,的整数倍位置上的比特位，转换选择,1,后的变换结果是,56,位。将前,28,位记为,C,0,，后,28,位记为,D,0,。,DES,：,加,/,解密数学描述,加密过程,L,0,R,0,IP,(64 bit,明文,),L,i,R,i,-1,R,i,L,i-1,f,(,R,i,-1,k,i,),i,=1,. , 16,(64 bit,密文,),IP,-1,(,R,16,L,16,),解密过程：,DES,的加密运算是可逆的，其解密过程可类似地进行。,R,16,L,16,IP,(64 bit,密文,),R,i,-1,L,i,L,i,-1,R,i,f,(,L,i,-1,k,i,),i,=16,., 1,(64 bit,明文,),IP,-1,(,R,0,L,0,),分组密码：,分组密码的工作模式比较,模式,描述,用途,电码本模式,(ECB),每个明文组独立地以同一密钥加密。,传送短数据,密码分组链接模式,(CBC),加密算法的输入是当前明文组与前一密文组的异或。,传送数据分组；认证。,密码反馈模式,(CFB),每次只处理输入的,j,比特，将上一次的密文用作加密算法的输入以产生伪随机输出，该输出再与当前明文异或以产生当前密文。,传送数据流；认证。,输出反馈模式,(OFB),与,CFB,类似，不同之处是本次加密算法的输入为前一次加密算法的输出。,有扰信道上,(,无线通讯,),传送数据流,