信息安全理论与技术 3、密码学知识

信息安全基本原理与技术目录信息安全概述常见攻击手段密码学知识认证与数字签名网络安全防御体系访问控制可信计算密码学的基本概念(1)密码学是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。密码是什么?密码就是变换。（信息代码变换、数据电平变换）变换是什么？变换是一种算法实现过程。谁来做变换？变换可以由硬件和软件实现。（人、器件部件、计算机）密码学的基本概念(2)密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支

密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问

密码分析学(Cryptanalytics)，研究分析破译密码的学问。

明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。密码学的基本概念(3)

加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。密码学的基本概念(4)

密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。密码学的基本概念(5)一个密码系统，通常简称为密码体制，由5部分组成：明文空间M全体明文的集合密文空间C全体密文的集合密钥空间K全体密钥的集合加密算法E一组由M到C的加密变换解密算法D一组由C到M的解密变换密码体制基本组成信息加密传输的过程加密:C=E(M,Ke)MCEKeCMKdD解密:M=D(C,Kd)M------明文C------密文Ke-----加密密钥Kd-----解密密钥E-------加密算法D------解密算法明文加密算法加密密钥K1网络信道解密算法明文解密密钥K2密文用户A用户B传送给B的信息B收到信息窃听者CC窃听到的信息!@#$%^注意数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。例如，加密算法为Y=aX+b，其中，X为明文，计算后Y成为密文。在具体加密过程中，a、b的取值为密钥，假设为（2，3），X=2,则密文计算后为7。在这个过程中，Y=aX+b可以公开，但具体a=2，b=3的取值不公开。所以即使对方知道了采用的加密算法，由于不知道具体参数取值，也无法根据密文计算出明文。密码系统的分类(1)根据密钥的使用方式分类

对称密码体制（秘密钥密码体制）用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。加密：EK(M)=C解密：DK(C)=M非对称密码体制（公钥密码体制）用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。用公钥KP对明文加密可表示为：EKP(M)=C用相应的私钥KS对密文解密可表示为：DKS(C)=M密码系统的分类(2)根据明文和密文的处理方式分类

分组密码体制（BlockCipher）

设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。M=(M1,M2,…,Mn)，C=(C1,C2,

…,Cn,)，其中Ci=E(Mi,Ke)，i=1,2…,n。序列密码体制（StreamCipher）将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。M=(M1,M2,…,Mn)，Ke=(ke1,ke2,…,ken)，C=(C1,C2,…,Cn)，其中Ci=E(mi,kei)，i=1,2,…,n。

密码系统的分类(3)根据加密算法是否变化分类设E为加密算法，K0,K1,…,Kn,为密钥，M0,M1,…,Mn为明文，C为密文

固定算法密码体制C0=E(M0,K0),C1=E(M1,K1),...,Cn=E(Mn,Kn)

变化算法密码体制C0=E1(M0,K0),C1=E2(M1,K1),...,Cn=En(Mn,Kn)

密码分析

截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。密码分析

密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别

密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。密码分析方法—分析法

确定性分析法利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。

统计分析法利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。

密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击加密算法截获的部分密文已知明文攻击加密算法，截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文密码分析方法--穷举破译法

对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功必须尝试所有可能密钥的一半。

或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Completetrial-and-errorMethod)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。

注意Internet的广泛应用，可以把全世界的计算机资源连成一体，形成巨大的计算能力，从而拥有巨大的密码破译能力，使原来认为安全的密码被破译。1994年，40多个国家的600多位科学家通过Internet，历时9个月破译了RSA-129密码，1999年又破译了RSA-140密码，2005年，RSA-200也被成功破译。1997年6月18日美国科罗拉多州以RockeVerser为首的工作小组宣布，通过利用Internet上的数万台微机，历时4个多月，通过穷举破译了DES。因此，在21世纪，只有经得起通过Internet进行全球攻击的密码，才是安全的密码。经典密码学经典密码学经典密码（古典密码）对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础。经典密码运用的两种基本技术：代换法：将明文字母替换成其他字母、数字或符号置换法：明文的字母保持相同，但顺序被打乱代换技术代换法，是将明文字母替换成其他字母、数字或符号的方法。例如：明晨五点发动反攻明文：MINGCHENWUDIANFADONGFANGONG密文：GNOGNAFGNODAFNAIDUWNEHCGNIMCaesar密码（已知的最早的代换密码）例如：明晨五点发动反攻明文：MINGCHENWUDIANFADONGFANGONG密文：PLQJFKHQZXGLDQIDGRQJIDQJRQJCaesar密码如果让每个字母等价于一个数值：a=0,b=1,…,z=25则加密公式为：

C=E(p)=(p+3)mod26更一般地：

C=E(p)=(p+k)mod26解密：p=D(C)=(C-k)mod26用穷举分析可轻松破解Caesar密码通常，加密和解密算法是已知的。需测试的密钥只有25个。明文所用的语言是已知的，其意义易于识别。因此，为了提高穷举分析的难度，密钥空间必须很大。例如3-DES算法的密钥长度为168位，密钥空间为2168。单表代换密码使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。例如，明文a用c来代换，b用剩下的25个字母中随机的一个来代换，c用剩下的24个字母中随机的一个来代换，……，以此类推。这样，密钥空间为26！，约4*1026种可能的密钥。破解单表代换密码根据频率统计进行分析确定每个字母被映射到什么字母单个字母出现的可能是A或I一般来说3个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合还可以应用其它很少应用的字母最常见的两字母组合，依照出现次数递减的顺序排列：TH、HE、IN、ER、AN、RE、DE、ON、ES、ST、EN、AT、TO、NT、HA、ND、OU、EA、NG、AS、OR、TI、IS、ET、IT、AR、TE、SE、HI、OF最常见的三字母组合，依照出现次数递减的顺序排列：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH改变明文的语法模式和结构

------抵抗频度分析可采用多表代换密码Playfair密码Hill密码Vigenère密码采用相关的单表代换规则由密钥来决定给定变换的具体规则最著名的多表代换加密体制--Playfair由英国科学家CharlesWheatstone于1854年发明，以其好友BaronPlayfair的名字命名。在第一次世界大战中，英军使用Playfair密码作为陆军的标准加密体制。在第二次世界大战中，盟军使用它作为通信加密工具。LordPeterWimsey给出的例子Playfair算法基于使用一个5×5字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母I和J被算作一个字母。MONARCHYBDEFGI/JKLPQSTUVWXZ属于相同对中的重复的明文字母将用一个填充字母进行分隔，因此，词balloon将被加密为balxloon。属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CM否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为BP，ea成为IM（或JM，这可根据加密者的意愿而定）。代换规则Playfair密码的优点Playfair密码与简单的单一字母替代法密码相比有了很大的进步虽然仅有26个字母，但有26×26＝676种字母对，因此，识别字母对要比单个字母要困难得多一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP,hq成为YP)。由于这些原因，Playfair密码过去长期被认为是不可破的。最简单的多表代换密码---Vigenère

维吉尼亚密码选择一个词组作为密钥，密钥中每个字母用来确定一个代换表，每个密钥字母用来加密一个明文字母。例如密钥字母为a，明文字母为c，则密文字母为0+2(mod26)=2，也就是c。直到所有的密钥字母用完，后再从头开始，使用第一个密钥字母加密。也就是说，密钥循环使用。一个例子明文为attackbeginsatfive，密钥为cipher，

attackbeginsatfive明文＋cipherciphercipher密钥

----------------------------------------------

＝cbihgbdmvprjcbupzv密文去除空格后为cbihgbdmvprjcbupzv破解维吉尼亚密码的一个途径如果密文足够长，其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子，分析者可能猜出密钥词的长度（因为密钥词是重复使用的）。一次一密---无法攻破的加密体制一次一密乱码本（one-timepad）,由MajorJosephMauborgne和AT&T公司的GilbertVernam在1917发明。一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。

一次一密的优点面对一条待破译的密文，攻击者能够找到很多个与密文等长的密钥，使得破译出的明文符合语法结构的要求，因为密钥本身是随机的，是没有规律的。就算在这些可能的密钥中存在真正的密钥，攻击者也无法在这些可能的密钥中确定真正的密钥，因为密钥只是用一次，攻击者无法用其它密文来验证这个密钥，因此是无法攻破的。一次一密的缺点一个一次一密加密系统，需要在某个规则基础上建立百万个随机字符，提供这样规模的真正随机字符集市相当艰巨的任务。对每一条消息，需要提供给发送发和接收方等长度的密钥，因此存在庞大的密钥分配问题。基于这些原因，一次一密在实际中极少应用。置换技术在置换密码中，明文的字母保持相同，但顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。Plaintext:COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECOMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECiphertext:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX

这种简单的技巧对于密码分析者来说是微不足道的。可在置换前，把列的次序打乱，列的次序就是算法的密钥。代换技术与置换技术通常结合使用。一般地，可先利用代换技术加密，再用置换技术将密文再次加密。转轮机---经典密码的机械阶段20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命——发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。美国人EdwardHebern认识到：通过硬件卷绕实现从转轮机的一边到另一边的单字母代替，然后将多个这样的转轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意组合。转轮被齿轮连接起来，当一个转轮转动时，可以将一个字母转换成另一个字母。照此传递下去，当最后一个转轮处理完毕时，就可以得到加密后的字母。为了使转轮密码更安全，人们还把几种转轮和移动齿轮结合起来，所有转轮以不同的速度转动，并且通过调整转轮上字母的位置和速度为破译设置更大的障碍。转轮机的工作原理每一个旋转轮代表一个单表代换系统，旋转一个引脚，再转变为另一个单表代换系统。为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n，即个单表代换系统。最后一个转轮转完一圈之后，它前面的转轮就旋转一个引脚，有点像时钟的齿轮。转轮机的经典---ENIGMA1918年，德国发明家ArthurScherbius用二十世纪的电气技术来取代已经过时的铅笔加纸的加密方法。他研究的结果就是永远被尊为经典的ENIGMA。ENIGMA首先是作为商用加密机器得到应用的。它的专利在1918年在美国得到确认。售价大约相当于现在的30000美元。ENIGMA在二战中的传奇二战中德国军队大约装备了三万台ENIGMA。在第二次世界大战开始时，德军通讯的保密性在当时世界上无与伦比。ENIGMA在纳粹德国二战初期的胜利中起到的作用是决定性的。精密的转轮破解ENIGMA波兰人在1934年，研究出了破译ENIGMA的方法。德国人在1938年底又对ENIGMA作了大幅度改进。1939年7月25日，波兰情报部门邀请英国和法国的情报部门共商合作破译ENIGMA。1939年7月，英国情报部门在伦敦以北约80公里的一个叫布莱奇利的地方征用了一所庄园。一个月后，鲜为人知的英国政府密码学校迁移到此。不久，一批英国数学家也悄悄来到这所庄园，破译恩尼格玛密码的工作进入了冲刺阶段。在这里刚开始时只有五百人，战争结束时已经增加到了七千人。为了破译ENIGMA，英国人将国内最优秀的数学家悉数照进庄园。其中就有从剑桥来的图灵。正是他打破了ENIGMA不可战胜的神话。虽然英国人成功的破译了ENIGMA，但是他们极好地隐藏了这一点，使得战争的进程大大加速。

从海里打捞起来的二战中用到的ENIGMA对称密码体制概述对称密码体制就是在加密和解密是用到的密钥相同，或者加密密钥和解密密钥之间存在着确定的转换关系。对称密码体制又有两种不同的实现方式，即分组密码和序列密码（或称流密码）。流密码与分组密码流密码每次加密数据流中的一位或一个字节。分组密码，就是先把明文划分为许多分组，每个明文分组被当作一个整体来产生一个等长（通常）的密文分组。通常使用的是64位或128位分组大小。分组密码的实质，是设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。分组密码分组密码算法实际上就是在密钥的控制下，简单而迅速地找到一个置换，用来对明文分组进行加密变换，一般情况下对密码算法的要求是：分组长度m足够大（64~128比特）密钥空间足够大（密钥长度64~128比特）密码变换必须足够复杂（包括子密钥产生算法）分组密码的设计思想扩散(diffusion)

将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中。产生扩散的最简单方法是通过“置换(Permutation)”（比如：重新排列字符）。混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。通常的方法是“代换（Substitution)”（回忆恺撒密码）。DES(DataEncryptionStandard)

美国国家标准局NBS于1973年5月发出通告，公开征求一种标准算法用于对计算机数据在传输和存储期间实现加密保护的密码算法。1975年美国国家标准局接受了美国国际商业机器公司IBM推荐的一种密码算法并向全国公布，征求对采用该算法作为美国信息加密标准的意见。经过两年的激烈争论，美国国家标准局于1977年7月正式采用该算法作为美国数据加密标准。1980年12月美国国家标准协会正式采用这个算法作为美国的商用加密算法。DES的实质DES是一种对称密码体制，它所使用的加密和解密密钥是相同的，是一种典型的按分组方式工作的密码。其基本思想是将二进制序列的明文分成每64bit一组，用长为64bit(56bit)的密钥对其进行16轮代换和置换加密，最后形成密文。DES的基本加密流程加密前，先将明文分成64bit的分组，然后将64bit二进制码输入到密码器中，密码器对输入的64位码首先进行初始置换，然后在64bit主密钥产生的16个子密钥控制下进行16轮乘积变换，接着再进行末置换就得到64位已加密的密文。DES算法的一般描述子密钥产生器

密钥（64bit）除去第8，16，…，64位，共8个校验位置换选择1（PC-1）Ci（28bit）Di（28bit）循环左移ti+1位循环左移ti+1位置换选择2（PC-2）Ki（48bit）置换选择1移位次数表第i次迭代12345678910111213141516循环左移次数1122222212222221若C1=c1c2…c28，D1=d1d2…d28则C2=c2c3…c28c1，D2=d2d3…d28d1。置换选择2置换选择PC-2将C中第9182225位和D中第791526位删去，并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥kiCiDi=b1b2…b56，则ki=b14b17b11b24…b36b29b32

初始置换将64个明文比特的位置进行置换，得到一个乱序的64bit明文组，然后分成左右两段，每段为32bit以L和R表示。2.乘积变换Li-1(32比特)Ri-1(32比特)选择扩展运算E48比特寄存器子密钥Ki(48比特)48比特寄存器选择压缩运算S32比特寄存器置换运算PLi(32比特)Ri(32比特)Li=Ri-1Ri=Li-1F(Ri-1,Ki)选择扩展运算E对原第321458912131617202124252829各位重复一次得到数据扩展。1，2，…………3232123454567898910111213121314151617161718192021202122232425242526272829282930313211，2，…………48选择扩展运算结果(48bit)E的输入(32bit)选择压缩运算S将前面送来的48bit数据自左至右分成8组，每组6bit。然后并行送入8个S盒，每个S盒为一非线性代换网络，有4个输出。

S盒的内部结构S盒的内部计算若输入为b1b2b3b4b5b6其中b1b6两位二进制数表达了0至3之间的数。b2b3b4b5为四位二进制数，表达0至15之间的某个数。在S1表中的b1b6行b2b3b4b5列找到一数m（0≤m≤15），若用二进制表示为m1m2m3m4，则m1m2m3m4便是它的4bit输出。例如，输入为001111，b1b6=01=1，b2b3b4b5=0111=7，即在S1盒中的第1行第7列求得数1，所以它的4bit输出为0001。关于S盒S盒是DES的核心，也是DES算法最敏感的部分，其设计原理至今仍讳莫如深，显得非常神秘。所有的替换都是固定的，但是又没有明显的理由说明为什么要这样，有许多密码学家担心美国国家安全局设计S盒时隐藏了某些陷门，使得只有他们才可以破译算法，但研究中并没有找到弱点。置换运算P对S1至S8盒输出的32bit数据进行坐标变换置换P输出的32bit数据与左边32bit即Ri-1诸位模2相加所得到的32bit作为下一轮迭代用的右边的数字段，并将Ri-1并行送到左边的寄存器作为下一轮迭代用的左边的数字段。逆初始置换IP-1

将16轮迭代后给出的64bit组进行置换得到输出的密文组1，2，…………64408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757251，2，…………64密文(64bit)置换码组(64bit)DES的解密解密算法与加密算法相同，只是子密钥的使用次序相反。DES的安全性DES在20多年的应用实践中，没有发现严重的安全缺陷，在世界范围内得到了广泛的应用，为确保信息安全做出了不可磨灭的贡献。存在的安全弱点：密钥较短：56位密钥空间约为7.2*1016。1997年6月RockeVerser小组通过因特网利用数万台微机历时4个月破译了DES；1998年7月，EFF用一台25万美元的机器，历时56小时破译DES。存在弱密钥：有的密钥产生的16个子密钥中有重复者。互补对称性：C=DES(M,K),则C’=DES(M’,K’)，其中，M’,C’,K’是M,C,K的非。DES具有良好的雪崩效应雪崩效应：明文或密钥的微小改变将对密文产生很大的影响。特别地，明文或密钥的某一位发生变化，会导致密文的很多位发生变化。DES显示了很强的雪崩效应两条仅有一位不同的明文，使用相同的密钥，仅经过3轮迭代，所得两段准密文就有21位不同。一条明文，使用两个仅一位不同的密钥加密，经过数轮变换之后，有半数的位都不相同。多重DESDES在穷举攻击下相对比较脆弱，因此需要用某种算法来替代它，有两种解决方法：设计全新的算法；用DES进行多次加密，且使用多个密钥，即多重DES。这种方法能够保护用于DES加密的已有软件和硬件继续使用。二重DES(DoubleDES)给定明文P和两个加秘密钥k1和k2，采用DES对P进行加密E，有密文C=EK2(EK1(P))对C进行解密D，有明文P=DK1(DK2(C))EEPXCK2K1加密图DDK2K1CXP解密图二重DES很难抵挡住中间相遇攻击法（Meet-in-the-MiddleAttack)C=EK2(EK1(P))从图中可见

X=EK1(P)=DK2(C)EEPCXK1K2DDCPXK2K1加密解密

若给出一个已知的明密文对（P,C)做：对256个所有密钥K1做对明文P的加密，得到一张密钥对应于密文X的一张表；类似地对256个所有可能的密钥K2做对密文C的解密，得到相应的“明文”X。做成一张X与K2的对应表。比较两个表就会得到真正使用的密钥对K1,K2。带有双密钥的三重DES

（TripleDESwithTwoKeys)Tuchman给出双密钥的EDE模式（加密-解密-加密）：

C=EK1(DK2(EK1(P)))……对P加密

P=DK1(EK2(DK1(C)))……对C解密这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（TheKeyManagerStandardsANSX9.17和ISO8732).EDEDEDCBAPPAB

CK1K2K1K1K2K1加密图解密图到目前为止，还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行蛮干搜索，那么由于空间太大为2112=5×1033，这实际上是不可行的。注意：1*.Merkle和Hellman设法创造一个条件，想把中间相遇攻击（meet-in-the-middleattack）的方法用于三重DES，但目前也不太成功。2*.虽然对上述带双密钥的三重DES到目前为止还没有好的实际攻击办法，但人们还是放心不下，又建议使用三密钥的三重DES，此时密钥总长为168bits.

C=EK3(DK2(EK1(P)))高级加密标准AES

1997年1月，美国国家标准局NIST向全世界密码学界发出征集21世纪高级加密标准（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES标准工作研究室，1997年4月15日的例会制定了对AES的评估标准。AES的要求（1）AES是公开的；（2）AES为单钥体制分组密码；（3）AES的密钥长度可变，可按需要增大；（4）AES适于用软件和硬件实现；（5）AES可以自由地使用，或按符合美国国家标准（ANST）策略的条件使用；算法衡量条件满足以上要求的AES算法，需按下述条件判断优劣a.安全性b.计算效率c.内存要求d.使用简便性e.灵活性。AES加密算法的具体实现AES每轮要经过四次变换，分别是

字节代换运算(SubByte())ShiftRows()(行移位)变换

MixColumns()（列混合）变换

AddRoundKey()(轮密钥的混合)变换

我们用的128bit的密钥（循环次数为10），那么每次加密的分组长为128bit，16个字节，每次从明文中按顺序取出16个字节假设为a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，这16个字节在进行变换前先放到一个4×4的矩阵中。如下页图所示：a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15这个矩阵称为状态（state）

以后所有的变换都是基于这个矩阵进行的，到此，准备工作已经完成。现在按照前面的顺序进行加密变换，首先开始第一次循环的第一个变换：字节代换(SubByte())。字节代换(SubByte())

a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33out0out4out8out12out1out5out9out13out2out6out10out14out3out7out11out15查表字节代换-S盒变换(查表)S12={53},则X=5,Y=3,out9=edShiftRows()(行移位)变换s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33s00s01s02s03s11s12s13s10s22s23s20s21s33s30s31s32行变换示意图SS′MixColumns()（列混合）变换S’0cS’1cS’2cS’3cS0cS1cS2cS3c02030101010203010101020303010102

S’0c＝({02}●S0c)⊕({03}●S1c)⊕S2c⊕S3c，但这个结果可能会超出一个字节的存储范围，所以实际上还要对结果进行处理。序列密码(流密码)“一次一密”密码在理论上是不可攻破的。流密码则由“一次一密”密码启发而来。流密码目前的理论已经比较成熟，工程实现也比较容易，加密效率高，在许多重要领域得到应用。“一次一密”密码使用的密钥是和明文一样长的随机序列，密钥越长越安全，但长密钥的存储、分配都很困难。流密码的密钥流流密码的关键就是产生密钥流的算法，该算法必须能够产生可变长的、随机的、不可预测的密钥流。保持通信双方的精确同步是流密码实际应用中的关键技术。由于通信双方必须能够产生相同的密钥流，所以这种密钥流不可能是真随机序列，只能是伪随机流。明文流密文流密钥流流密码的结构典型的流密码每次加密一位或一个字节明文。将初始密钥(种子)输入到发生器，输出一个随机数(密钥)。伪随机字节发生器(密钥流发生器)明文字节流M密文字节流C密钥Kk异或加密伪随机字节发生器(密钥流发生器)密钥Kk异或解密明文字节流M11001100明文01101100密钥流10100000密文设计流密码需要考虑的因素密钥流的周期要长。伪随机数发生器产生的并非完全随机的序列，它是一个产生确定的比特流的函数，该比特流最终将产生重复。重复的周期越长，相当于密钥越长，密码分析也就越困难。密钥流应尽可能地接近于一个真正的随机数流的特征。例如1和0的个数应大致相同。密钥流越随机，加密所得的密文也越随机，分析就越困难。伪随机数发生器的输出取决于输入的密钥的值。RC4流密码RC4是RonRivest为RSA公司在1987年设计的一种流密码。它是一种可变密钥长度、面向字节操作的流密码。RC4可能是应用最广泛的流密码用于SSL/TLS(安全套接字/传输层安全协议)用于IEEE802.1无线局域网中的WEP协议。RC4算法输入：一个256个字节的表示0---255的状态矢量S、密钥K(长度为kenlen)输出：密钥字节流*初始化*Fori=0to255do S[i]=i; T[i]=K[imodkeylen];//临时矢量T(256字节)*置换*j=0;Fori=0to255do j=(j+S[i]+T[i])mod256;Swap(S[i],S[j]);//S仍然包含所有值为0到255的元素*密钥流的生成*i=0,j=0;While(true) i=(i+1)mod256; j=(j+S[i])mod256; swap(S[i],S[j]); t=(S[i]+S[j])mod256; k=S[t];加密中，将k的值与下一明文字节异或；解密中，将k的值与下一密文字节异或。其他对称密码IDEA由旅居瑞士的华人来学嘉和他的导师J.L.Massey共同开发的。IDEA使用128位密钥，明文和密文分组长度为64位。已被用在多种商业产品中。CLIPPER密码采用SKIPJACK算法，明文和密文分组长度为64位，密钥长度为80位。BlowfishBlowfish允许使用最长为448位的不同长度的密钥，并针对在32位处理器上的执行进行了优化。TwofishTwofish使用128位分组，可以使用128、192或256位密钥。CAST-128CAST-128使用128位密钥。它在更新版本的PGP中使用。GOSTGOST是为了回应DES而开发的俄罗斯标准，它使用256位密钥。公钥密码体制整除定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b例：3|15，-15|60性质：对所有整数a≠0，a|0、a|a成立对任意整数b，1|b成立素数(primenumber)定义：如果整数p(p>1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。素数定理：在各种应用中，我们需要大的素数,如100位的素数素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。最大公约数a和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。如果gcd(a,b)=1，则说a和b是互素的。定理：设a和b是两个整数(至少一个非0)，d=gcd(a,b)，则存在整数x和y，使得ax+by=d特殊地，如果a和b互素，则有整数x和y，使得ax+by=1同余设整数a，b，n(n≠0)，如果a-b是n的整数倍，则a≡b(modn)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。(modn)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。模算术的性质：(amodn)+(bmodn)=(a+b)modn(amodn)-(bmodn)=(a-b)modn(amodn)*(bmodn)=(a*b)modn性质有整数a，b，c，n(n≠0)：如果a≡b(modn)，b≡c(modn)

那么a≡c(modn)如果a≡b(modn)，c≡d(modn)

那么a+c≡b+d，a-c≡b-d，ac≡bd(modn)计算117mod13计算21234mod789除法设整数a，b，c，n(n≠0)，且gcd(a,n)=1。如果ab≡ac(modn)，那么b≡c(modn)证明：∵gcd(a,n)=1，∴有x和y，使ax+ny=1两边同乘以(b-c):(b-c)(ax+ny)=b-c即:(ab-ac)x+n(b-c)y=b-c……①∵ab≡ac(modn),即ab=ac+k1n,∴ab-ac是n的倍数同时，n(b-c)y显然也是n的倍数所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍则①式变为：b-c=k2n即b≡c(modn)欧几里德算法(Euclid)用欧几里德算法求最大公约数。求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=2乘法逆元如果gcd(a,b)=1，那么：存在a-1，使a*a-1

≡1modb存在b-1，使b*b-1

≡1moda这里，把a-1称为a模b的乘法逆元，b-1称为b模a的乘法逆元用扩展的欧几里德算法求乘法逆元gcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+01=5-1*4=5-1*(1234-246*5)=247*5-1*1234=247*(11111-9*1234)-1*1234=247*11111-2224*1234=247*11111-2224*(12345-1*11111)=2471*11111-2224*12345费尔马小定理(Fermat)如果p是一个素数,a不是p的倍数，则：ap-1≡1(modp)证明：设有一整数空间S={1,2,…,p-1}再设有一函数Ψ(x)=ax(modp)x∈S(1)对于任何x∈S，有Ψ(x)∈S(2)对于x和y(x≠y),有Ψ(x)≠Ψ(y)(3)根据乘法定理和除法定理

(p-1)!ap-1≡(p-1)!modp欧拉函数Ф(n)：小于n且与n互素的正整数的个数显然，对于素数p，有Ф(p)=p-1设有两个素数p和q，p≠q，那么对于n=pq，有：Ф(n)=Ф(pq)=Ф(p)*Ф(q)=(p-1)*(q-1)欧拉定理(Euler)对于任意互素的a和n，有aФ(n)

≡1modn证明：对于整数n，与n互素的数有Ф(n)个：令这些数为：R={x1,x2,…,xФ(n)

}用a与R中的每个元素相乘模n，得到集合S：

S={ax1modn,x2modn,…,xФ(n)modn

}其实S就是R：(ax1modn)RS中的元素是唯一的那么：R中各元素相乘就等于S中各元素相乘：∈公钥密码体制(Publickeysystem)公钥密码学与其他密码学完全不同：公钥算法基于数学函数而不是基于替换和置换使用两个独立的密钥公钥密码学的提出是为了解决两个问题：密钥的分配数字签名1976年Diffie和Hellman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。公钥密码体制的原理公钥体制(Publickeysystem)(Diffie和Hellman,1976)

每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。公钥密码体制有4个组成部分明文：算法的输入，它们是可读信息或数据，用M表示；密文：算法的输出。依赖于明文和密钥，对给定的消息，不同的密钥产生密文不同。用E表示；公钥和私钥：算法的输入。这对密钥中一个用于加密，为Ke，此密钥公开；一个用于解密，为Kd，此密钥保密。加密算法执行的变换依赖于密钥；加密、解密算法公钥密码体制下的秘密通信公钥加密体制的特点加密和解密能力分开多个用户加密的消息只能由一个用户解读，可用于公共网络中实现保密通信用私钥加密的消息可以用对应的公钥解密，所以由一个用户加密消息而使多个用户可以解读，可用于认证系统中对消息进行数字签字无需事先分配密钥密钥持有量大大减少提供了对称密码技术无法或很难提供的服务：如与哈希函数联合运用可生成数字签名，可证明的安全伪随机数发生器的构造，零知识证明等保证机密性

MEKbeE(M,Kbe)DKbdMKbe：Bob的公钥Kbd

：Bob的私钥保证真实性

Kad：Alice的私钥Kae

：Alice的公钥MEKadE(M,Kad)DKaeM既保证机密性又保证真实性

Kad：Alice的私钥Kae

：Alice的公钥MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe：Bob的公钥Kbd

：Bob的私钥公钥密码应满足的要求接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。收方B用自己的秘密钥对密文c解密在计算上是容易的。敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是对任何算法都做此要求。对公钥密码体制的攻击和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。RSA算法

RSAAlgorithm概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman[Rivest等1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。算法原理RSA算法使用了乘方运算。要求：明文M经过加密得到密文C：C=Memodn

密文C经过解密得到明文M：

Cd

modn=(Memodn)dmodn=Medmodn=M即：必须存在e，d，n，使Medmodn=M成立如何确定e,d,n确定n：独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值

(n)=(p－1)(q－1)确定e：随机选一整数e，1

e<

(n)，gcd(

(n),e)=1确定d：根据ed≡

1

mod

(n)在模

(n)下，计算d这样确定的e,d,n是否能使Medmodn=M成立呢？因为ed≡1

mod

(n)即ed=k

(n)+1

所以：Med=Mk

(n)+1如果M和n互素，即gcd(M,n)=1那么，根据欧拉定理(如果gcd(a,n)=1，则

aФ(n)

≡1modn)：有：M

(n)≡1modn所以：Med≡Mk

(n)+1≡M[M

(n)]kmodn

≡M[1]kmodn