第二次课 密码学基本概念

密码学基本概念主要内容密码学基本概念1密码体制组成2密码系统分类3密码分析学4本节主要内容经典密码学5对称密码体制6公钥密码体制7散列、数字签名、证书、PKI概念6密码学基本概念密码学(Cryptology)：研究信息系统安全保密的科学，是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。它包含两个分支

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

密码分析学(Cryptanalytics)，研究分析破译密码的学问。北京邮电大学信息安全中心密码学基本概念明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。密码学基本概念加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。北京邮电大学信息安全中心密码学基本概念密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。密码体制组成一个密码系统，通常简称为密码体制，由5部分组成：明文空间M全体明文的集合密文空间C全体密文的集合密钥空间K全体密钥的集合加密算法E一组由M到C的加密变换解密算法D一组由C到M的解密变换北京邮电大学信息安全中心密码体制组成-加密传输过程信源Mm加密器解密器接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道北京邮电大学信息安全中心密码体制组成-加密传输过程明文加密算法加密密钥K1网络信道解密算法明文解密密钥K2密文用户A用户B传送给B的信息B收到信息窃听者CC窃听到的信息!@#$%^密码体制组成-加解密过程加密:C=E(M,Ke)MCEKeCMKdDM------明文C------密文Ke-----加密密钥Kd-----解密密钥E-------加密算法D------解密算法解密:M=D(C,Kd)北京邮电大学信息安全中心密码体制组成注意

数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。北京邮电大学信息安全中心密码系统分类根据密钥的使用方式分类对称密码体制（秘密钥密码体制）用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。加密：EK(M)=C解密：DK(C)=M非对称密码体制（公钥密码体制）用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。用公钥KP对明文加密可表示为：EKP(M)=C用相应的私钥KS对密文解密可表示为：DKS(C)=M北京邮电大学信息安全中心密码系统分类根据明文和密文的处理方式分类（对称密码）序列密码(流密码)体制（StreamCipher）将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。M=(M1,M2,…,Mn)，Ke=(ke1,ke2,…,ken)，C=(C1,C2,…,Cn)，其中Ci=E(mi,kei)，i=1,2,…,n。分组密码体制（BlockCipher）设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。M=(M1,M2,…,Mn)，C=(C1,C2,

…,Cn,)，其中Ci=E(Mi,Ke)，i=1,2…,n。密码系统分类根据加密算法是否变化分类设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)

北京邮电大学信息安全中心密码分析学截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别密码设计是利用数学来构造密码；密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。密码分析学-分析方法分类攻击类型攻击者拥有的资源惟密文攻击加密算法截获的部分密文已知明文攻击加密算法，截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文北京邮电大学信息安全中心密码分析学-典型分析方法最可靠的攻击办法:强力攻击统计分析最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特.线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统插值攻击方法密钥相关攻击北京邮电大学信息安全中心古典密码学经典密码（古典密码）对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础。经典密码运用的两种基本技术：

代换法：将明文字母替换成其他字母、数字或符号

置换法：明文的字母保持相同，但顺序被打乱古典密码学-代换密码代换法，是将明文字母替换成其他字母、数字或符号的方法。

例如：明晨五点发动反攻

明文：MINGCHENWUDIANFADONGFANGONG

密文：GNOGNAFGNODAFNAIDUWNEHCGNIMCaesar密码（已知的最早的代换密码）例如：明晨五点发动反攻明文：MINGCHENWUDIANFADONGFANGONG密文：PLQJFKHQZXGLDQIDGRQJIDQJRQJ古典密码学-代换密码Caesar密码如果让每个字母等价于一个数值：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密码作为陆军的标准加密体制。在第二次世界大战中，盟军使用它作为通信加密工具。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码MONARCHYBDEFGI/JKLPQSTUVWXZPlayfair算法基于使用一个5×5字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母I和J被算作一个字母。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码规则属于相同对中的重复的明文字母将用一个填充字母进行分隔，因此，词balloon将被加密为balxloon。属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CM否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为BP，ea成为IM（或JM，这可根据加密者的意愿而定）。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Playfair密码优点Playfair密码与简单的单一字母替代法密码相比有了很大的进步

虽然仅有26个字母，但有26×26＝676种字母对，因此，识别字母对要比单个字母要困难得多

一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP,hq成为YP)。由于这些原因，Playfair密码过去长期被认为是不可破的。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Vigenère密码例子明文为attackbeginsatfive，密钥为cipher，attackbeginsatfive

明文

＋

cipherciphercipher

密钥----------------------------------------------

＝

cbihgbdmvprjcbupzv密文

去除空格后为cbihgbdmvprjcbupzv北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-Vigenère密码分析如果密文足够长，其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子，分析者可能猜出密钥词的长度（因为密钥词是重复使用的）。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-

一次一密一次一密乱码本（one-timepad）,由MajorJosephMauborgne和AT&T公司的GilbertVernam在1917发明。是无法攻破的密码体制。一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。北京邮电大学信息安全中心古典密码学-代换密码多表代换密码-

一次一密的优点面对一条待破译的密文，攻击者能够找到很多个与密文等长的密钥，使得破译出的明文符合语法结构的要求，因为密钥本身是随机