第02章 常规加密的经典技术.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 常规加密的经典技术,密码学基本概念,常规加密模型,隐写术,替代加密和转置加密,简单的,XOR,一次一用密码本,1.密码学基本概念,发送者和接收者,在信息传送过程中，主动提供信息的一方称发送者，得到信息的一方称接收者。发送者要确保信息安全传送，使窃听者不能盗取信息。,1.密码学基本概念,密码技术,目的：,使不知道如何解密的黑客不可能由其截获的乱码中得到任何有意义的信息；,使黑客不可能伪造任何乱码型的信息。,密码学(密码技术)分类,密码编码学：对信息进行编码实现信息隐蔽,密码分析学：研究分析破译密码,1.密码学基本概念,密码通信系统模型,1.密码学基本概念,被隐蔽的消息称作,明文,密码可将明文变换成另一种隐蔽形式，称为,密文,。,由明文到密文的变换称为,加密,。由合法接收者从密文恢复出明文的过程称为,解密,（或,脱密,）。,非法接收者试图从密文分析出明文的过程称为,破译,。,对明文进行加密时采用的一组规则称为,加密算法,。,对密文解密时采用的一组规则称为,解密算法,。,加密算法和解密算法是在一组仅有合法用户知道的秘密信息，称为,密钥,的控制下进行的。,加密和解密过程中使用的密钥分别称为,加密密钥,和,解密密钥,。,1.密码学基本概念,明文消息空间,M；,密文消息空间,C；,密钥空间,K,1,和,K,2,；,加密交换,E,k1,：M,C，,其中,k,1,K,1,；,解密变换,D,k2,：C,M，,其中,k,2,K,2,；,称总体（,M，C，K,1,，K,2,，E,k1,，D,k2,）,为密码系统。对于给定明文消息,m,M，,密钥,k,1,K,1,，,加密交换将明文,m,变换为密文,c：,cf(m,k,1,)E,k1,(m)m,M，k,1,K,1,1.密码学基本概念,合法接收者，利用其知道的解密密钥,k2,对收到的密文进行变换，恢复出明文消息,mD,k2,(c)m,M，k,2,K,2,黑客则利用其选定的变换函数,h，,对截获的密文,c,进行变换，得到的明文是明文空间的某个元素,m,h(c)m,M，k,2,K,2,一般,mm。,如果,mm，,则黑客破译成功。,1.密码学基本概念,认证，完整性和不许抵赖,认证：信息接受者应有可能核查信息来源，任何闯入者无力装扮成原有的发送者。,完整性：信息接收者应有可能验证信息在传播中未经修改，闯入者无力用假信息代替合法的原有信息。,不可抵赖：发送者在发送出信息后无法抵赖他所发出的信息。,1.密码学基本概念,算法和密钥,密码算法，称为加密算法，是用来加密和解密的数学函数。为给明文信息加密，用加密算法函数。为给密文信息解密，用解密算法函数。,如果算法的安全性基于算法工作的保安，这是一个,受约算法,。,近代密码术用密钥来解决安全性问题。,1.密码学基本概念,算法和密钥,加密和解密函数表示,E,K,(M)=C,D,K,(C)=M,若加密和解密密钥相同：,D,K,(E,K,(M)M,若加密和解密密钥不同：,E,K1,(M)C,D,K2,(C)=M,D,K2,(E,K1,(M)=M,1.密码学基本概念,密码系统分类,用于将明文转换为密文操作的类型。所有加密算法基于两个基本原则：替代，即明文中的每个元素（比特、字母、比特组合或字母组合）被映射为另一个元素；转置，即在明文中的元素被重排列，对它们的基本要求是不丢失信息（即所有操作都是可逆转的）。被称为乘积系统的多数系统涉及多个阶段的替代和转置。,所使用密钥的数量。如果发送者和接收者双方使用相同的密钥，该系统称为对称加密、单密钥加密、秘密密钥加密或常规加密。如果发送者和接收者各自使用一个不同的密钥，则该系统称为非对称加密、双密钥加密或公开密钥加密。,明文处理的方式。分组加密一次处理一块元素的输入，对每个输入块产生一个输出块。流（序列）加密连续地处理输入元素，并随着该过程的进行，一次产生一个元素的输出。,1.密码学基本概念,单钥密码的特点,是无论加密还是解密都使用同一个密钥，因此，此密码体制的安全性就是密钥的安全。如果密钥泄露，则此密码系统便被攻破。最有影响的单钥密码是1977年美国国家标准局颁布的,DES,算法。,优点：安全性高、加解密速度快。,缺点：1)随着网络规模的扩大，密钥的管理成为一个难点；2)无法解决消息确认问题；3)缺乏自动检测密钥泄露的能力。,1.密码学基本概念,双钥体制特点,加密密钥与解密密钥不同，此时不需要安全信道来传送密钥而只需利用本地密钥发生器产生解密密钥,k,2,K,2,。,并以此来控制解密操作,D。,双钥密码是1976年,W.,Diffie,和,M.E.,Hellman,提出的一种新型密码体制。,优点：由于双钥密码体制的加密和解密不同，且能公开加密密钥，而仅需保密解密密钥，所以双钥密码不存在密钥管理问题。双钥密码还有一个优点是可以拥有数字签名等新功能。最有名的双钥密码是1977年由,Rivest,，,Shamir,和,Adleman,三人提出的,RSA,密码体制。,缺点：双钥密码算法一般比较复杂，加解密速度慢。,1.密码学基本概念,序列密码,加密过程是把明文序列与等长的密钥序列进行逐位模2加。,解密过程则是把密文序列与等长的密钥序列进行逐位模2加。,安全性：主要依赖于密钥序列。最著名的序列密码是“一次一密密码”，它的密钥序列是真正的随机二元序列。,优点：1)处理速度快，实时性好；2)错误传播小；3)不存在串破译问题；4)适用于军事、外交等保密信道。,缺点：1)明文扩散性差；2)插入信息的敏感性差；3)需要密钥同步。,1.密码学基本概念,分组密码,加密方式是首先将明文序列以固定长度进行分组，每一组明文用相同的密钥和加密函数进行运算。为了减少存储量和提高运算速度，密钥的长度一般不大，因而加密函数的复杂性成为系统安全的关键。分组密码设计的核心是构造既具有可逆性又有很强的非线性的算法。加密函数重复地使用代替和置换两种基本的加密变换。,优点：1)明文信息良好的扩散性；2)对插入的敏感性；3)不需要密钥同步；4)较强的适用性，适宜作为加密标准。,缺点：1)加密速度慢；2)错误易扩散和传播。,1.密码学基本概念,密码破译,密码破译则是无须取得密钥而能将密文信息恢复成明文的科学。密码破译成功，不仅恢复明文也可得到密钥。并且发现密码系统中导致上述结果的弱点。,仅知密文攻击,已知明文攻击,选择明文攻击,选择文本（自适应选择明文攻击）,选择密文攻击,选择密钥攻击,牛皮筋式破译,1.密码学基本概念,仅知密文攻击,在这种攻击中，密码破译员有几个信息的密文，所有的信息使用相同加密算法加密。为将相同密钥加密的信息解密，密码破译员会尽可能多地恢复信息的明文，或者更好地是导出用于加密信息的密钥。,已知：,C,1,=E,K,(P,1,)，C,2,=E,K,(P,2,)，,C,i,=E,K,(P,i,),导出：,P,1,、P,2,P,i,、K,或导出从,C,i,+1,=E,K,(P,i+1,),得知,P,i+1,的算法,已知明文攻击,密码破译员不但利用几个信息的密文，而且有这些信息的明文。导出用于加密信息的密钥或用相同的密钥加密任何新的信息的解密算法。,已知：,P,1,，C,1,=E,K,(P,1,)，P,2,，C,2,=E,K,(P,2,)，P,i,，,C,i,=E,K,(P,i,),导出：,K,或导出从,C,i,+1,=E,K,(P,i+1,),得知,P,i+1,的算法,1.密码学基本概念,选择明文攻击,密码破译员不但利用密文和涉及到的信息的明文，而且能选择加密的明文。这比已知明文攻击更强有力，因为密码破译员能选择专用的明文块加密，可能产生更多关于密钥的信息。导出用于加密信息的密钥或用相同的密钥加密任何新的信息的解密算法。,已知：,P,1,，C,1,=E,K,(P,1,)，P,2,，C,2,=E,K,(P,2,)，P,i,，,C,i,=E,K,(P,i,),其中密码分析者选择,P,1,、P,2,P,i,导出：,K,或导出从,C,i,+1,=E,K,(P,i+1,),得知,P,i+1,的算法,选择文本（自适应选择明文攻击）,这是选择明文攻击的一个特例。密码破译员不但选择加密的明文，而且能依据以前加密的结果修改选择。在选择明文攻击中，密码破译员可以选择一大块明文加密；在自适应选择明文攻击中，选择一个较小的明文块，然后依据第一次的结果选择另一块，等等。,1.密码学基本概念,选择密文攻击,密码破译员能选择不同的将要解密的密文和已解的明文，将它们放入一个自动解密的分解判别的工具箱中，导出密钥。,已知：,C,1,，P,1,=D,K,(C,1,)，C,2,，P,2,=D,K,(C,2,)，,C,i,，P,i,=D,K,(,C,i,),导出：,K,这种攻击主要应用于公开密钥加密系统。选择密文攻击有时对对称算法一样有效。,选择密钥攻击,这种攻击并不意味破译员能选择密钥。只不过破译员对不同密钥之间的关系有所了解。它较新奇和含混但并不实用。,牛皮筋式破译,破译员威胁、写黑信或折磨某人直至给出密钥，或用金钱收买，所以也称购买密钥攻击，这已不是科学技术的内容了，但在现实社会中却也常有奏效。,1.密码学基本概念,攻击的类型,密码破译者己知的东西,仅有密文,加密算法,待破译的密文,已知明文,加密算法,待破译的密文,由密钥形成的一个或多个明文密文对,选择明文,加密算法,待破译的密文,由密码破译者选择的明文消息，连同它对应的由其密钥生成的密文,选择文本,加密算法,待破译的密文,由密码破译者选择的明文消息，连同它对应的由密钥生成的密文,由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文,加密算法,待破译的密文,由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文,密码破译方法小结,1.密码学基本概念,算法安全性,算法根据攻破的难易标定了不同的安全程度。如攻破某算法的费用大于加密数据的代价，该算法认为是安全的。如攻破某算法的时间长于数据的保密期，该算法也认为是安全的。同样如攻破某算法所需的数据量多于密钥加密的数据量，该算法仍认为是安全的。以上所说的安全并非绝对，因为在密码破译中新的攻破机遇频频发生，另一方面大部分数据的价值会随时间流逝而贬低。所以，安全的要点是数据的价值要继续保持低于攻破安全屏障所花的代价。,1.密码学基本概念,Lars Knudsen,按攻破算法难易的递降顺序，分类如下：,全攻破，密码破译员找到密钥,K，,于是解密,D,K,(C)=M。,全局推导，密码破译员找到另一算法,A，,无须知道,K，,因为,A,等价于,D,K,(C),而解密。,局部推导，密码破译员找到窃听来的密文的明文而解密。,信息推导，密码破译员得到关于密钥信息或是有关明文格式的信息。利用这些信息而解密。,如果无论破译员有多少密文，仍无足够信息能恢复明文，这样的算法是无条件安全的。事实上只有一次一用的密码本是不可攻破的。其它所有密码系统在惟密文攻击下都是可以攻破的。,1.密码学基本概念,加密算法的安全准则：,破译该密码的成本超过被加密信息的价值。,破译该密码的时间超过该信息有用的生命周期。,攻击复杂性的度量：,数据复杂性，为攻击所需数据的攻击量。,处理复杂性，执行攻击所须的时间，又称工作因子。,存储需求，做攻击所须的存储量。,1.密码学基本概念,自然界常用大数,物理类似物,数字,到下个冰世纪的时间,14,000（2,14,）年,到太阳销毁的时间,10,9,（2,30,）年,行星的寿命,10,9,（2,30,）年,宇宙的寿命（如果宇宙是开放的）,10,11,（2,67,）年,到小质量恒星冷却时间,10,16,（2,61,）秒,到行星脱离恒星时间,10,15,（2,30,）年,到所有恒星离开银河的时间,10,19,（2,64,）年,到天体轨道因向心辐射而消逝时间,10,20,（2,67,）年,到黑洞因,Hawking,过程而消逝时间,10,64,（2,213,）年,到所有物质冷却成零度液体的时间,10,65,（2,216,）年,到所有物质衰变成铁的时间,10,1026,年,到所有物质陷落到黑洞的时间,10,1076,年,1.密码学基本概念,密钥长度与安全性评估,密钥长度（,bit）,密钥数量,每微秒加密1次所需时间,每微秒加密100万次所需时间,32,2,32,=4.3,x 10,9,2,31,us=35.8,分,2.15微秒,56,2,56,=7.2,x 10,16,2,55,us=1142,年,10.01小时,128,2,128,=3.4,x 10,38,2,127,us=5.4 x 10,24,年,5.4,x 10,18,年,26字符（排列）,26!=4,x 10,26,2,x 10,26,us=6.4 x 10,12,年,6.4,x 10,6,年,2.常规加密模型,常规加密的简化模型,2.常规加密模型,常规密码系统的模型,2.隐写术,字符标记：印刷或打印的文本字母经选择用铅笔重写。该标记通常不可见，除非该纸以一定的角度对着亮光看。,不可见墨水：使用一些物质来书写，但不留下任何可见痕迹，除非加热该纸或在该纸上涂上某种化学药品。,扎小孔：在所选的字母上扎小孔，这些小孔通常不可见，除非把该纸放在光的前面。,打字机改正带：用于行间与一根黑带一同打印，用改正带打印的结果仅在强光下才可见。,格孔密写卡：将它覆盖在一张纸上从格孔中写入密件，然后在纸上余下部分填入其它字句，使它像一般信件。,2.隐写术,示例：,3.替代加密和置换加密,替代技术,置换技术,转子机（,Rotor Machine）,3.替代加密和置换加密,替代技术,替代技术是这样一种技术，其中明文的字母由其他字母或数字或符号所代替。如果该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式。,在经典密码学中，替代加密算法有四种基本类型：,简单替代加密算法或称单字符加密，明文每一字符被替代成密文中的相应字符。新闻密电就是用这种方法。,同音替代加密算法，类似于简单替代加密算法，但明文中的单一字符能对应密文中的几个字符。例如“,A”,可能相应于5、13、25或“,B”,可能相应于7、19、31或42等等。,多元替代加密算法，成块的字符加密成一组其它字符。如“,ABA”,相应于“,RTQ”，“ABB”,相应于“,SLL”,等等。,多字母替代加密算法，由多次简单替代加密组成。例如用5次不同的简单替代加密，具体所用的次数随每一字符在明文中的位置而变化。,3.1 替代加密,移位密码体制,设,P=C=K=Z/(26),对,k K,定义,e,k,(x)=x+k(mod 26)=y,C,同时,d,k,(y)=y-k(mod 26),注1,*,：26个英文字母与模26剩余类集合0,.,25建立一一对应：,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,0,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25,2,*,.,当,k=3,时，为,Caesar,密码：,明文：,meet me after the toga party,密文：,PHHW PH DIWHO WKH WRJD SDUWB,实际算法为：有,同时有，,d,3,(y)=y-3(mod 26),3.1 替代加密,替换密码体制,设,P=C=Z/(26)，K,是由26个符号0，1,.,25的所有可能置换组成。任意,K，,定义,e,(x)=(x)=y,且,d,(y)=,-1,(y)=x,-1,是,的逆置换。,注：,1,*,.,置换,的表示：,2,*,密钥空间,K,很大，|,k|=26!410,26,，,破译者穷举搜索是不行的，然而，可由统计的方式破译它。,3,*,移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间,(,0 1 2 3.23 24 25,0 1 2 3.23 24 25,),3.1 替代加密,维吉尼亚密码,(,Vigenere,),设,m,为一固定的正整数，定义,P=C=K=(Z/(26),m,对一个密钥,K（k,1,k,2,k,m,),定义,e,k,(x,1,x,2,x,m,)=(x,1,+k,1,x,2,+k,2,x,m,+k,m,)=y,d,k,(y,1,y,2,y,m,)=(x,1,-k,1,x,2,-k,2,x,m,-k,m,)=x,这里的所有的运算都是在（,mod 26),中进行的。,注：维吉尼亚密码是多表替换体制，分析起来更困难。密钥空间大，如当,m=5,时，密钥空间所含密钥的数量是1.110,7,3.1 替代加密,Hill,密码体制,设为某个固定的正整数，,P=C=(Z/(26),m,K=Z/(26),上的,mm,可逆矩阵,对每一个,k K,定义,e,k,(x)=,xK,(mod 26),和,d,k,(y)=,yK,-1,(mod 26),注：明文与密文都是,m,元的向量,（,x,1,x,2,x,m,);(y,1,y,2,y,m,)，Z/(26),为同余类环。在这个环上的可逆矩阵,A,mxm,是指行列式,detA,mxm,的值,Z,*,/(26),它为,Z/(26),中全体可逆元的集合。,Z,*,/(26)=a,Z/(26)|(a,26)=1，,Z,*,/(26)=1,3,5,7,9,11,15,17,19,21,23,25,例子：当,m=2,时，明文元素,x=(x,1,x,2,),密文元素,y=(y,1,y,2,),(y,1,y,2,)=(x,1,x,2,),K,事实上,y,i,为,x1,x2,的线性组合，,y,1,=11x,1,+3x,2,;y2=8x,1,+7x,2,，,一般，将取,mm,的矩阵,K,作为我们的密钥：有,y=(y,1,y,2,y,m,)=(x,1,x,2,x,m,),换言之，,y=,xK,;,且有,x=,yK,-1,若,K=,可得,K,-1,=,若对明文,july,加密，它分成2个元素（,j,u),(l,y),分别对应于（9,20）,（11,24）,有,（9,20）,（9960,72140）（3,4）,且,（11,24）,(12172,88168)（11,22）,于是对 july加密的结果为DELW。为了解密，B,ob,计算,且,因此，得到了正确的明文“,july,”,3.替代加密和置换加密,置换技术,通过执行对明文字母的某种置换，取得一种类型完全不同的映射。这种技术称为置换密码。,3.1 置换加密,示例：,3.1 置换加密,设,m,为固定的正整数，,P=C=(Z/(26),m,K,是由1,2,.,m,的所有置换构成，对一个密钥,K，,定义,e,(x,1,x,2,.,x,m,)=(x,(1),.,x,(m),),和,d,(y,1,y,2,.,y,m,)=(y,(1),.,y,(m),),这里,1,为,的逆置换。,注：这里的加密与解密仅仅用了置换，无代数运算。,例子：,设,m=6,取密钥,而,若给定的明文是：,cryptography,首先找分成6个字母长的,明文组：,crypto|,graphy,求得的密文是：,YTCOPRAHGYPR,注：事实上，置换密码是,Hill,密码的特例。给定一个集合1,2,.,m,的置换矩阵,K,=(,k,ij,),mm,（,置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。）,对上面例子决定的置换,对应：,3.替代加密和置换加密,转子机（,Rotor Machine）,4.,简单的,XOR,XOR,是异或运算。,C,语言中用“”表示，数学符号为。它是一种标准的位运算：,00=0,01=1,10=1,11=0,又定义：,aa=0,abb=a,MK=C CK=M,5.,一次一用密码本,1917,年由,Major Joseph,Manborgne,和,AT,T,的,Gnbert Vernam,发明的。实际上，一次一用密码本是门槛方案的一个特殊情况。传统地说，一次一用密码本只不过是将许多不重复的随机的字母，写在几张纸上，然后粘贴成一本密码本。最初的形式，是电报打字员一次性胶带。发送者用本子上的每一个密钥加密明文中的每个字符。所谓解密就是将明文字符和一次一用密码本上的密钥相加取模,26,。,5.,一次一用密码本,1917,年由,Major Joseph,Manborgne,和,AT,T,的,Gnbert Vernam,发明的。实际上，一次一用密码本是门槛方案的一个特殊情况。传统地说，一次一用密码本只不过是将许多不重复的随机的字母，写在几张纸上，然后粘贴成一本密码本。最初的形式，是电报打字员一次性胶带。发送者用本子上的每一个密钥加密明文中的每个字符。所谓解密就是将明文字符和一次一用密码本上的密钥相加取模,26,。,