网络信息安全第2章网络信息安全基础

北京邮电大学朱洪亮网络信息安全基础网络信息安全基础-密码学部分密码学部分北京邮电大学信息安全中心北京邮电大学信息安全中心本节主要内容密码学基本概念1密码体制组成2密码系统分类3密码分析学4北京邮电大学信息安全中心北京邮电大学信息安全中心本节主要内容经典密码学5对称密码体制6公钥密码体制7散列、数字签名、证书、PKI概念6北京邮电大学信息安全中心北京邮电大学信息安全中心密码学基本概念v密码学密码学(Cryptology)：研究信息系统安全保密：研究信息系统安全保密的科学的科学，是关于加密和解密变换的一门科学，是是关于加密和解密变换的一门科学，是保护数据和信息的有力武器保护数据和信息的有力武器。它包含两个分支。它包含两个分支密码编码学密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学密码分析学(Cryptanalytics)，研究分析破译密码的学问。北京邮电大学信息安全中心北京邮电大学信息安全中心密码学基本概念 明文明文(消息)(Plaintext) ：被隐蔽消息。 密文密文(Ciphertext)或密报密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。 加密加密(Encryption)：将明文变换为密文的过程。 解密解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。 加密员加密员或密码员密码员(Cryptographer)：对明文进行加密操作的人员。北京邮电大学信息安全中心北京邮电大学信息安全中心密码学基本概念 加密算法加密算法(Encryption algorithm)：密码员对明文进行加密时所采用的一组规则。 接收者接收者(Receiver)：传送消息的预定对象。 解密算法：解密算法：接收者对密文进行解密时所采用的一组规则。 密钥密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥加密密钥和解密密钥解密密钥。 截收者截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。北京邮电大学信息安全中心北京邮电大学信息安全中心密码学基本概念 密码分析密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。 密码分析员密码分析员(Cryptanalyst)：从事密码分析的人 被动攻击被动攻击(Passive attack)：对一个保密系统采取截获密文进行分析的攻击。 主动攻击主动攻击(Active attack)：非法入侵者入侵者(Tamper)、攻击者攻击者(Attcker)或黑客黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。北京邮电大学信息安全中心北京邮电大学信息安全中心密码体制组成v一个密码系统，通常简称为密码体制，由一个密码系统，通常简称为密码体制，由5部分组部分组成：成：明文空间明文空间M全体明文的集合密文空间密文空间C全体密文的集合密钥空间密钥空间K全体密钥的集合加密算法加密算法E一组由M到C的加密变换解密算法解密算法D一组由C到M的解密变换北京邮电大学信息安全中心北京邮电大学信息安全中心密码体制组成-加密传输过程信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭线信道（主动攻击）C 搭线信道（被动攻击）密码分析员m密钥源K1k1密钥源K2k2密钥信道北京邮电大学信息安全中心北京邮电大学信息安全中心密码体制组成-加密传输过程明文加密算法加密密钥K1网络信道解密算法明文解密密钥K2密文用户用户A用户用户B传送给B的信息B收到信息窃听者窃听者CC窃听到的信息窃听到的信息!#$%北京邮电大学信息安全中心北京邮电大学信息安全中心密码体制组成-加解密过程w 加密加密: C = E(M,Ke)MCEKeCMKdDM-明文 C-密文Ke-加密密钥 Kd-解密密钥E-加密算法 D-解密算法w 解密解密: M = D(C, Kd)北京邮电大学信息安全中心北京邮电大学信息安全中心密码体制组成注意注意 v数据安全基于密钥而不是算法的保密。也就是说，数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。用的密钥，则是保密的。北京邮电大学信息安全中心北京邮电大学信息安全中心密码系统分类v根据密钥的使用方式分类根据密钥的使用方式分类 对称密码体制（秘密钥密码体制） 用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。 加密：EK(M)=C 解密：DK(C)=M 非对称密码体制（公钥密码体制） 用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。 用公钥KP对明文加密可表示为：EKP(M)=C 用相应的私钥KS对密文解密可表示为：DKS(C)=M北京邮电大学信息安全中心北京邮电大学信息安全中心密码系统分类v根据明文和密文的处理方式分类根据明文和密文的处理方式分类 （对称密码）（对称密码） 序列密码(流密码)体制（Stream Cipher） 将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。 M=(M1, M2, ,Mn) ， Ke=(ke1, ke2,ken)，C=(C1, C2,Cn)，其中Ci=E(mi,kei) ，i=1,2,n。 分组密码体制（Block Cipher） 设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。 M=(M1, M2, ,Mn) ，C=(C1, C2 , ,Cn,)，其中Ci=E(Mi,Ke)， i=1,2,n。北京邮电大学信息安全中心北京邮电大学信息安全中心密码系统分类v根据加密算法是否变化分类根据加密算法是否变化分类设设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) 北京邮电大学信息安全中心北京邮电大学信息安全中心密码分析学 截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学 密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。 密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密码设计是利用数学来构造密码；密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。北京邮电大学信息安全中心北京邮电大学信息安全中心密码分析学-分析方法分类攻击类型攻击者拥有的资源惟密文攻击v加密算法v截获的部分密文已知明文攻击v加密算法，v截获的部分密文和相应的明文选择明文攻击v加密算法v加密黑盒子，可加密任意明文得到相应的密文选择密文攻击v加密算法v解密黑盒子，可解密任意密文得到相应的明文北京邮电大学信息安全中心北京邮电大学信息安全中心密码分析学-典型分析方法 最可靠的攻击办法:强力攻击 统计分析 最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特. 线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统 插值攻击方法 密钥相关攻击北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学v经典密码（古典密码）对于今天来说，是极不经典密码（古典密码）对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础。近、现代密码学的基础。v经典密码运用的两种基本技术：经典密码运用的两种基本技术： 代换法：将明文字母替换成其他字母、数字或符号 置换法：明文的字母保持相同，但顺序被打乱 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码v代换法，是将明文字母替换成其他字母、数字或符代换法，是将明文字母替换成其他字母、数字或符号的方法。号的方法。 例如：明晨五点发动反攻 明文：MING CHEN WU DIAN FA DONG FAN GONG 密文：GNOGN AFGNO DAFNA IDUWN EHCGN IMvCaesar密码（已知的最早的代换密码）密码（已知的最早的代换密码）例如：明晨五点发动反攻明文：MING CHEN WU DIAN FA DONG FAN GONG密文：PLQJ FKHQ ZX GLDQ ID GRQJ IDQ JRQJ北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码Caesar密码v如果让每个字母等价于一个数值：如果让每个字母等价于一个数值：a=0,b=1,z=25则加密公式为： C=E(p)=(p+3) mod 26更一般地： C=E(p)=(p+k) mod 26解密：p=D(C)=(C-k) mod 26北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码用强力分析可轻松破解Caesar密码v通常，加密和解密算法是已知的。通常，加密和解密算法是已知的。v需测试的密钥只有需测试的密钥只有25个。个。v明文所用的语言是已知的，其意义易于识别。明文所用的语言是已知的，其意义易于识别。 因此，为了提高穷举分析的难度，密钥空间必须很因此，为了提高穷举分析的难度，密钥空间必须很大。例如大。例如3-DES算法的密钥长度为算法的密钥长度为168位，密钥位，密钥空间为空间为2168。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码单表代换密码v使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。v例如，明文a用c来代换，b用剩下的25个字母中随机的一个来代换，c用剩下的24个字母中随机的一个来代换，以此类推。这样，密钥空间为26！，约4*1026种可能的密钥。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码破解单表代换密码v根据频率统计进行分析v确定每个字母被映射到什么字母v单个字母出现的可能是A或Iv一般来说3个字母出现的可能是THE或ANDv还可以用其他通常出现的双字母或三字母组合v还可以应用其它很少应用的字母北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码破解单表代换密码v 最常见的两字母组合，依照出现次数递减的顺序排列：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、OFv 最常见的三字母组合，依照出现次数递减的顺序排列：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码v 改变明文的语法模式和结构，可抵抗频度分析v 常见的多表代换密码：Playfair密码、Hill密码、Vigenre密码北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码v由英国科学家Charles Wheatstone于1854年发明，以其好友Baron Playfair的名字命名。v在第一次世界大战中，英军使用Playfair密码作为陆军的标准加密体制。v在第二次世界大战中，盟军使用它作为通信加密工具。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码MONARCHYBDEFGI/JKLPQSTUVWXZvPlayfair算法基于使用一个55字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母I和J 被算作一个字母。 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码规则v属于相同对中的重复的明文字母将用一个填充字母进行分隔，因此，词balloon将被加密为ba lx lo on。 v属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。 v属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CMv否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为BP，ea成为IM（或JM，这可根据加密者的意愿而定）。 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码优点vPlayfair密码与简单的单一字母替代法密码相比有密码与简单的单一字母替代法密码相比有了很大的进步了很大的进步 虽然仅有26个字母，但有2626676种字母对，因此，识别字母对要比单个字母要困难得多 一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP, hq成为YP)。v由于这些原因，由于这些原因，Playfair密码过去长期被认为是不密码过去长期被认为是不可破的。可破的。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码- Vigenre密码例子v明文为明文为attack begins at five，密钥为，密钥为cipher， attack begins at five 明文明文 cipher cipher ci pher 密钥密钥 - cbihgb dmvprj cb upzv 密文密文 去除空格后为去除空格后为cbihgbdmvprjcbupzv北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码- Vigenre密码分析v如果密文足够长，其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子，分析者可能猜出密钥词的长度（因为密钥词是重复使用的） 。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码- 一次一密v 一次一密乱码本（one-time pad）, 由Major Joseph Mauborgne 和AT&T公司的Gilbert Vernam 在1917发明。是无法攻破的密码体制。v 一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。 v 每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码- 一次一密的优点v面对一条待破译的密文，攻击者能够找到很多个与密文等长的密钥，使得破译出的明文符合语法结构的要求，因为密钥本身是随机的，是没有规律的。v就算在这些可能的密钥中存在真正的密钥，攻击者也无法在这些可能的密钥中确定真正的密钥，因为密钥只是用一次，攻击者无法用其它密文来验证这个密钥，因此是无法攻破的。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-代换密码多表代换密码- 一次一密的缺点v一个一次一密加密系统，需要在某个规则基础上建立百万个随机字符，提供这样规模的真正随机字符集是相当艰巨的任务。v对每一条消息，需要提供给发送发和接收方等长度的密钥，因此存在庞大的密钥分配问题。v基于这些原因，一次一密在实际中极少应用。北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-置换密码v在置换密码中，明文的字母保持相同，但顺序被打乱了。v在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学-置换密码Plaintext: COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVEC O M P U T E R G RA P H I C S M A Y BE S L O W B U T A TL E A S T I T S E XP E N S I V ECiphertext: CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX 北京邮电大学信息安全中心北京邮电大学信息安全中心古典密码学v代换技术与置换技术通常结合使用。v一般地，可先利用代换技术加密，再用置换技术将密文再次加密。北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制v流密码和分组密码v密码设计原则： 混淆原则 所设计的密码应使得密钥和明文以及密文之间的信赖关系相当复杂以至于这种信赖性对密码分析者来说是无法利用。 扩散原则 所设计密码应使得密钥的每一位数字影响密文的多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也影响密文的多位数字以便隐藏明文数字的统计性性。北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-流密码v 流密码主要应用于军事和外交场合。v 流密码的优点是错误扩展小、速度快、利于同步、安全程度高。v 典型流密码算法：RC4，A5等密钥流密钥流产生器产生器密钥密钥k明文明文m密文密文c异或运算北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-流密码v 伪随机序列发生器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。v 真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。 v 伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。v 随机数是较短的随机位序列。 seed(short)PRBS(long)011011010010110.北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码v分组密码的操作模式 电子密码本ECB (electronic codebook mode) 密码分组链接CBC (cipher block chaining) 密码反馈CFB (cipher feedback) 输出反馈OFB (output feedback) 计数器模式CTR 美国NSB在FIPS PUB 74和81中规定 ANSI 在ANSI X3.106中规定 ISO和ISO/IEC在ISO 9732 ISO/IEC 10116中规定北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码v分组密码的操作模式模式模式描述描述典型应用典型应用电子密码电子密码本本ECB用相同的密钥分别对明文分组加密用相同的密钥分别对明文分组加密单个数据的安全传输单个数据的安全传输密码分组密码分组链接链接CBC加密算法的输入是上一个密文分组和下一个明加密算法的输入是上一个密文分组和下一个明文分组的异或文分组的异或普通目的的面向分组普通目的的面向分组的传输的传输密码反馈密码反馈CFB一次处理一次处理J位，上一个分组密文作为产生一个位，上一个分组密文作为产生一个伪随机数输出的加密算法的输入，该输出与明伪随机数输出的加密算法的输入，该输出与明文分组异或，作为下一个分组的输入文分组异或，作为下一个分组的输入普通目的的面向分组普通目的的面向分组的传输认证的传输认证输出反馈输出反馈OFB与与CFB相同，只是加密算法的输入是上一次相同，只是加密算法的输入是上一次DES的输出的输出噪声信道上数据流的噪声信道上数据流的传输（如卫星传输）传输（如卫星传输）计数器模计数器模式式CTR）每个明文分组是加密的计数器的异或，对每个每个明文分组是加密的计数器的异或，对每个后续的分组，计数器是累加的。后续的分组，计数器是累加的。普通目的的面向分组普通目的的面向分组的传输用于高速需求的传输用于高速需求北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码v典型分组密码算法 1. DES，3DES 2. IDEA 3. RC5 4. RC6 5. AES 其他一些较实用的算法，如Blowfish，CAST，以及RC2。北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v1973年，美国国家标准局(NBS) 开始征集联邦数据加密标准的方案。 Feistel等人研究了一种128位的对称密钥系统， 后IBM改进为56位的密钥系统，并提交NBS。v1975年3月17日，NBS公布了IBM公司提供的密码算法，以标准建议的形式在全国范围内征求意见。v1977年7月15日，NBS接受这个建议，数据加密标准DES正式颁布，供商业界和非国防性政府部门使用。北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vDES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES算法框图算法框图交换左右交换左右32比特比特 北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v初始置换和逆置换北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法 Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器扩充扩充/置换运算置换运算48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器代换代换/选择运算选择运算置换运算置换运算PRi（32比特）比特）Li=Ri-1F函数函数北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法F函数函数：Expansion: 32 48（扩充）（扩充）S-box: 6 4（压缩）（压缩）Permutation:置换置换北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法32 | 01 02 03 04 | 0504 | 05 06 07 08 | 0908 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 01v扩充/置换运算北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v代换/选择运算北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vS-Box-i北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vS-Box-ii北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vS-Box 对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。 例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v置换运算16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v子密钥的产生 k1 （ 56位） (48位 ) ki （ 56位） （ 48位） 64位密钥置换选择1 C0（ 28 位） D0（ 28位） 循环左移循环左移 C1（ 28 位） D1（ 28位） 循环左移循环左移 Ci（ 28位） Di（ 28 位）置换选择2置换选择2密钥表的计算逻辑循环左移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v置换选择1(PC-1)和置换选择2(PC-2) 北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vDES示意图-总结北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vDES安全性分析vDES的安全性完全依赖于密钥，与算法本身没有关系。 v主要研究内容： 密钥的互补性； 弱密钥与半弱密钥； 密文-明文相关性； 密文-密钥相关性； S-盒的设计； 密钥搜索。 北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v弱密钥v弱密钥：弱密钥：由密钥由密钥 k 确定的加密函数与解确定的加密函数与解密函数相同密函数相同 ，即，即 。vDES的弱密钥：的弱密钥： 如果各轮产生的子密钥如果各轮产生的子密钥一样，则加密函数与解密函数相同。一样，则加密函数与解密函数相同。 vDES至少有至少有4个弱密钥个弱密钥 ：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe)()(1kkDESDES北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v弱密钥半弱密钥：对于密钥半弱密钥：对于密钥 k ，存在一个不同的，存在一个不同的密钥密钥 ，满足，满足 。 DES的半弱密钥：子密钥生成过程中只能的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密产生两个不同的子密钥或四个不同的子密钥，互为对合。钥，互为对合。 DES至少有至少有12个半弱密钥。个半弱密钥。 *k)()(*kkDESDES北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法vS盒的设计原则S -盒的设计原理没有公开，一些原则如下：盒的设计原理没有公开，一些原则如下：v所有S-盒的每一行是0,1,15的一个置换；v所有S-盒的输出都不是输入的线性函数或仿射函数；vS-盒的输入改变任意一位都会引起输出中至少两位发生变化；v对于任何输入x（6位），S(x)与S(x 001100)至少有两位不同；v对于任何输入x（6位），S(x)与S(x 00ef00)不相等，e, f取0或1；v对于任意一个输入位保持不变而其他五位变化时，输出中0和1的数目几乎相等。 北京邮电大学信息安全中心北京邮电大学信息安全中心对称密码体制-分组密码-DES算法v针对DES的攻击方法攻击攻击DES的方法主要有：的方法主要有： 密钥穷搜索攻击，DES算法总的密钥量为 ，1998年使用高级计算机的情况下，破译DES只需56小时； 差分攻击； 线性攻击，比差分攻击更有效； 相关密钥攻击等。1756102北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制v 公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。v 在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。v 公开密钥算法主要用于加密/解密、数字签名、密钥交换。 v 典型公钥密码算法：Diffie-Hellman密钥交换算法、背包算法、RSA算法、ElGamal算法、ECC等北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制加密与解密由不同的密钥完成加密: mc: c = EK(m)解密: cm: m = DB(c) = DB(EK(m)两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)m = DB(EK(m) = EK(DB(m)北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-应用场景v传统加密过程加密和解密使用相同密钥加密和解密使用相同密钥明文明文明文明文密文密文北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-应用场景v公钥密码算法加密和解密使用加密和解密使用不同密钥不同密钥明文明文明文明文密文密文北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-应用场景v公钥密码算法加密和解密使用加密和解密使用不同密钥不同密钥明文明文明文明文密文密文北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-应用场景v基于公钥密码算法的认证北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-应用场景v公钥密码算法的应用范围算法加/解密 数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制v单向陷门函数单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是容易的。北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制v公钥密码算法基于的数学难题 背包问题（背包算法） 大整数分解问题（RSA算法） 有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem, ElGamal体制，DH算法,ElGamal算法） 椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem, 类比的ElGamal体制，ECC）北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v第一个发表的公开密钥算法，1976v用于通信双方安全地协商一个会话密钥v只能用于密钥交换v基于离散对数计算的困难性v主要是模幂运算 ap mod n 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v离散对数v 对数是指数的反函数：对数是指数的反函数： b= ai = i= logab ; v 模运算如何？模运算如何？ b ai mod p = i = logab mod p ？v 素根（素根（Primitive Root）a是素数p 的一个素根，如果a mod p, a2 mod p , , ap-1 mod p 是1到p-1的排列p= 19, a i mod p, i=1,2,3,18aa2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17a18111111111111111111248161371491817151136125101398515726181610111441217131416791711651416791711651561117971641561117971641北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v离散对数v 对于任何整数b 和素数p 的一个素根a, 可以找到一个唯一的指数i，使得： b = ai mod p , 其中0i(p-1) i 称为 b 的以a 为底模p的离散对数或指数，记为 ind a,p (b) 对比：对数运算： i = log a （b） mod p inda,p (1)=0, 因为 a0 mod p =1 mod p =1; inda,p (a)=1 因为 a1 mod p =a mod p =a; 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v离散对数y = gx mod p 已知已知 g, x , p 计算计算y 是容易的，是容易的， 已知已知g, y, p , 计算计算x 是非常困难的是非常困难的北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v密钥交换过程全局公开的参数：q 是一个素数，a q , a是q 的一个素根A 选择一个私有的XA, XA q计算公开的YA, YA= a XA mod q B 选择一个私有的XB, XB q计算公开的YB, YB= a XB mod q YAYBA计算会话密钥K=(YB) XA mod q B计算会话密钥K=(YA) XB mod q EK(m)北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-DH算法v密钥交换过程例： 全局公开参数： q=97, a = 5 ( 5是97 的素根） A选择私钥 XA=36 , B 选择私钥 XB=58 A 计算公钥 B 计算公钥 YA= 5 36 mod 97 = 50 YB= 5 58 mod 97=44 A 与 B 交换公开密钥 A 计算会话密钥 K = YBXA mod q = 4436 mod 97= 75 B 计算会话密钥 K = YAXB mod q = 4436 mod 97= 75 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRon Rivest, Adi Shamir , Leonard dlemanvRSA的安全性基于大数分解的难度vRSA在美国申请了专利（已经过期），在其他国家没有vRSA已经成了事实上的工业标准，在美国除外北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法v a与与b的最大公因数：的最大公因数：gcd (a, b) gcd(20, 24)=4 , gcd (15, 16)=1v 如果如果gcd(a, b)=1 ，称，称a与与b 互素互素v 模运算模运算 moda= q n +r 0rn ; q=a/n ; x 表示小于或等于x的最大整数a=a/nn + (a mod n) , r = m mod n 如果 (a mod n )= (b mod n) ，则称a 与b 模模n同余同余，记为 a b mod n 例如， 23 8 mod 5 , 8 1 mod 7v数论基础北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法v数论基础 模运算是可交换的、可结合的、可分配的模运算是可交换的、可结合的、可分配的(a+b) mod n = (a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) (b mod n) ) mod n(ab) mod n = ( (a mod n ) （b mod n) ) mod n (a (b+c) ) mod n = ( a b) mod n + (a c) mod n 幂幂, 模运算模运算 ma mod n m2 mod n = (mm) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n ) 2 mod n m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m m8 m16) mod n 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法v数论基础v欧拉函数欧拉函数(n) n是正整数， (n) 是比n小且与n 互素的正整数的个数(3)=|1, 2| =2 (4)=|1, 3| =2 (5)=|1, 2, 3, 4 | =4 (6)=|1, 5| =4 (7)=|1, 2, 3, 4, 5, 6| =6(10)=|1, 3, 7, 9| =4 (11)=|1, 2,3,4,5,6, 7,8, 9,10| =10 如果p是素数，则(p)=(p-1), 比如(2), (5)， (11) 如果p,q 是素数，则(pq)=(p) (q) (p-1)(q-1) 。比如，(10)北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法v数论基础例如：例如： m=3, n=10; (10)=4 m(n)=34=81 ; 81 mod 10 = 1 即即 81 1 mod 10 34+1 = 243 3 mod 10 nmn mod 1)(nmmn mod 1)(欧拉定理欧拉定理 若整数m 和n 互素，则等价形式:北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法v数论基础 推论：给定两个素数推论：给定两个素数p, q , 两个整数两个整数 n, m ，使得使得n=pq, 0mn ； 则对于任意整数则对于任意整数k ，下列关系成立：下列关系成立： m k(n)+1 m mod n北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法流程 密钥产生密钥产生1. 取两个大素数 p, q , 保密; 2. 计算n=pq，公开n; 3. 计算欧拉函数(n) =（p-1）(q-1)；4. 任意取一个与(n) 互素的小整数e, 即 gcd (e, (n) )=1; 1e (n) e作为公钥公开;5. 寻找d, 使得 de 1 mod (n) , ed =k (n) +1 d 作为私钥保密。p=7,q=17n=119(n)=96选择e=55d=k961令 k=4, 得到求得d=77北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法流程v密钥对（密钥对（KU, KR）:KU=e, n , KR=d, nv加密过程加密过程把待加密的内容分成k比特的分组，k log2n，并写成数字，设为M,则：C= Me mod nv解密过程解密过程M = Cd mod n 5,11977,119c=m5 mod 119m=c77 mod 119北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法证明v证明解密过程是正确的证明解密过程是正确的 M Cd mod n ( Me mod n)d mod n = Med mod n即 Med M mod n 根据欧拉定理推论，根据欧拉定理推论，Mk(n)+1 M mod n ed =k(n)+1北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法举例1.p=7,q=17, n=7*17=1192.(n)=(7-1)(17-1)=963.选 e=5, gcd (e, (n) = gcd (5, 96)=1;4.寻找 d，使得 ed 1 mod 96 , 即 ed= k*96+1, 取 d= 77 5.公开(e,n)=(5, 119)6.将d 保密，丢弃p, q；7.加密：m=19 19 5 66 mod 119 , c= 66解密 6677 mod 119 =? 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法举例1.p=7,q=17, n=7*17=1192.(n)=(7-1)(17-1)=963.选 e=5, gcd (e, (n) = gcd (5, 96)=1;4.寻找 d，使得 ed 1 mod 96 , 即 ed= k*96+1, 取 d= 77 5.公开(e,n)=(5, 119)6.将d 保密，丢弃p, q；7.加密：m=19 19 5 66 mod 119 , c= 66解密 6677 mod 119 =? 北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法的安全性v攻击方法攻击方法 蛮力攻击：对所有密钥都进行尝试 数学攻击：等效于对两个素数乘积(n)的因子分解v大数的因子分解是数论中的一个难题大数的因子分解是数论中的一个难题十进制数字位数近似比特数得到的数据MIPS年100332199171103651992751203981993830129428199450001304311996500因子分解的进展北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-RSA算法vRSA算法的安全性v速度速度 无论软硬件实现，最快也比DES慢100倍512位768位1024位加密0.030.050.08解密0.160.480.93签名0.160.520.97验证0.020.070.08北京邮电大学信息安全中心北京邮电大学信息安全中心公钥密码体制-ECC算法vECC算法简介v椭圆曲线密码系统椭圆曲线密码系统 有限域GF(2n) 运算器容易构造 加密速度快 更小的密钥长度实现同等的安全性北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数vHash : 哈希函数，杂凑函数，散列函数哈希函数，杂凑函数，散列函数 h= H(m)vH 具有如下特性：具有如下特性：1）可以操作任何大小的报文m；2）给定任意长度的m，产生的h的长度固定；3）给定m 计算h=H(m) 是容易的；4）给定h, 寻找m，使得H(m)=h是困难的；5）给定m ，要找到m,m m 且 H(m)=H(m)是计算上不可行的；6）寻找任何(x,y) ，xy ，使得H(x) =H(y)是计算上不可行的。北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数v简单简单Hash函数函数-纵向的奇偶校验码纵向的奇偶校验码比特1比特2比特n分组1b11b21bn1分组2b21b22bn2.分组mb1mb2mbnm散列码C1C2CnCi= bi1 bi2 bim+北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法vRon Rivest 设计, RFC 1321v经历过MD2, MD4 不同的版本v对任意输入均产生128bit的输出v基于32位的简单操作，易于软件实现v简单而紧凑，没有复杂的程序和大数据结构v适合微处理器实现（特别是Intel）北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法报文m1000.0长度Y0Y1YqYL-1MD5MD5MD5MD5摘要128IV512512512512512512512512cv1cvqCvq+1CvL寄存器北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法vStep1: 填充，使报文长度为512的倍数减64vStep2: 附加长度，将填充前的报文长度写入最后的64比特，总长度N=L512vStep3: 初始化MD 缓存，4个32bit的寄存器（A,B,C,D）,共128 bitsA= 01 23 45 67 B= 89 AB CD EFC=FE DC BA 98D=76 54 32 10北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法vStep 4 : 处理每个报文分组（512 bits）。算法的核心是4轮循环的压缩函数。使用一个随机矩阵 T i= 232 abs (sin (i) ) i=1,2,.64 CV0= IV CVq+1= SUM32 ( CVq, RFIYq ,RFHYq , RFG Yq ,RFFYq ,CVq vStep 5 : 输出 。 所有L 个 512 bit 的分组处理完之后，第L阶段的输出便是128bit 的报文摘要北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法F,T1,16 , XiG,T17,32 , Xp2iH,T33,48 , Xp3iI,T49,64 , Xp4i128+12832512YqABCDCVqCVq+1MD5 的压缩函数北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-MD5算法+ : 模模 232加法加法Xk: 512bit 输入中的第输入中的第k字节字节Ti ： T 矩阵中第矩阵中第i 个个32 bitABCDABCD+sgXkTi+循环原始函数g(b,c,d)1F(bc) v(bd)2G(bd) v(cd)3Hb xor c xor d4Ic xor (b v d)基本的MD5操作（单步）北京邮电大学信息安全中心北京邮电大学信息安全中心单向散列函数-典型散列算法vSHA, SHA-1 NIST 和NSA共同设计, 用在DSS中 基于MD4 设计，与MD5 非常相似 产生160 位 散列值vRIPE-MD 欧共体RIPE 项目 128 位散列值北京邮电大学信息安全中心北京邮电大学信息安全中心消息认证码(MAC)ABMAC= H(M)MMAC= H(M)ABMAC= H(M)MAC= H(M)CM=MMAC= H(M)MACMMACMMAC北京邮电大学信息安全中心北京邮电大学信息安全中心消息认证码(MAC)vA 和和 B 共享一个密钥共享一个密钥KvA 计算散列值计算散列值 MAC= H( M, K) , 附在附在M之之后发送给后发送给B . MAC= MD5( M+K) MAC= DESK( MD5(M) )vB 收到收到M 和和H (M,K) 之后计算之后计算 H(M,K) 并与并与收到的收到的MAC比较比较ABMAC= H(M,K)MMAC= H(M,K)MAC北京邮电大学信息安全中心北京邮电大学信息安全中心数字签名MA: (KUa KRa), KUbHashEncryptKRaEKRa(H(m)MHashB: (KUb KRb), KRaEncryptKUa= ?H(m)v 电子形式的“签名”v 数字签名可用于鉴权、完整性和不可抵赖性保证北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-对称密钥分配v问题问题 密钥必须通过保密信道分配 密钥的数量O(n2)北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-对称密钥分配v集中式密钥分配中心（集中式密钥分配中心（KDC） 每个用户和KDC之间共享一个主密钥 （ master key）,通过可靠的信道分配 会话密钥（ session key）协商 A KDC : 请求访问 B KDC A: Ka Kab, KbKab A B: KbKab AB: KabmKDCABKaKbKab北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-公开密钥分配v公开密钥公开密钥 公开宣布 公布到目录服务AB目录服务目录服务A:KPaB: KPbEKPb(M)EKPa(M)北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-中间人攻击发送方 A接收方B给你我的公钥给你我的公钥(A,KA)给你我的公钥给你我的公钥(A,KH)KH, KH-1中间人HackerEKH(Message)DKH-1(Message)EKA(Message)北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-PKIvPKI是用于发放公开是用于发放公开密钥的一种渠道密钥的一种渠道vCAvRAvDirectory 大量的查询操作 少量的插入、删除和修改DirectoryCARA用户用户用户用户注册注册签发证书、证书回收列表签发证书、证书回收列表北京邮电大学信息安全中心北京邮电大学信息安全中心密钥分配-PKIv数字证书数字证书公钥证书的主要内容公钥证书的主要内容身份证主要内容身份证主要内容持有者（Subject）标识签发者（Issuer）标识有效期公钥（n,e）CA的数字签名姓名签发单位有效期照片签发单位盖章、防伪标志序列号身份证号码北京邮电大学信息安全中心北京邮电大学信息安全中心场景分