第二章密码学概论教学课件

n问题：问题：什么是电子商务安全，安全的措施有哪些？什么是电子商务安全，安全的措施有哪些？信息安全措施信息安全措施 信息信息信息信息安全措施安全措施安全措施安全措施 法律法律法律法律措施措施措施措施，教育，教育，教育，教育措施措施措施措施，管理，管理，管理，管理措施措施措施措施，技术技术技术技术措施措施措施措施，注意：注意：注意：注意：决不能低估法律、教育、管理的作用，许多时候决不能低估法律、教育、管理的作用，许多时候决不能低估法律、教育、管理的作用，许多时候决不能低估法律、教育、管理的作用，许多时候它们的作用大于技术。它们的作用大于技术。它们的作用大于技术。它们的作用大于技术。n n信息安全的技术措施信息安全的技术措施信息安全的技术措施信息安全的技术措施n n 信息安全技术措施信息安全技术措施信息安全技术措施信息安全技术措施 硬件系统安全、操作系硬件系统安全、操作系硬件系统安全、操作系硬件系统安全、操作系统安全、密码技术、通信安全、网络安全、数统安全、密码技术、通信安全、网络安全、数统安全、密码技术、通信安全、网络安全、数统安全、密码技术、通信安全、网络安全、数据库安全、病毒防治技术，防电磁辐射技术，据库安全、病毒防治技术，防电磁辐射技术，据库安全、病毒防治技术，防电磁辐射技术，据库安全、病毒防治技术，防电磁辐射技术，信息隐藏技术，数字资源保护技术，电子对抗信息隐藏技术，数字资源保护技术，电子对抗信息隐藏技术，数字资源保护技术，电子对抗信息隐藏技术，数字资源保护技术，电子对抗技术，技术，技术，技术，。n n 注意：硬件结构的安全和操作系统安全是基础，注意：硬件结构的安全和操作系统安全是基础，注意：硬件结构的安全和操作系统安全是基础，注意：硬件结构的安全和操作系统安全是基础，密码、网络安全等是关键技术密码、网络安全等是关键技术密码、网络安全等是关键技术密码、网络安全等是关键技术。信息安全的管理措施信息安全的管理措施信息安全的管理措施信息安全的管理措施 信息安全管理措施既包括信息设备、机房的安全管理，信息安全管理措施既包括信息设备、机房的安全管理，信息安全管理措施既包括信息设备、机房的安全管理，信息安全管理措施既包括信息设备、机房的安全管理，又包括对人的安全管理，其中又包括对人的安全管理，其中又包括对人的安全管理，其中又包括对人的安全管理，其中对人的管理是最主要的。对人的管理是最主要的。对人的管理是最主要的。对人的管理是最主要的。目前，计算机网络系统安全的最大威胁之一是缺少有效目前，计算机网络系统安全的最大威胁之一是缺少有效目前，计算机网络系统安全的最大威胁之一是缺少有效目前，计算机网络系统安全的最大威胁之一是缺少有效的计算机网络安全监管。的计算机网络安全监管。的计算机网络安全监管。的计算机网络安全监管。信息安全的法律措施信息安全的法律措施信息安全的法律措施信息安全的法律措施 信息安全措施包括各级政府关于信息安全措施包括各级政府关于信息安全措施包括各级政府关于信息安全措施包括各级政府关于信息安全的各种法律、信息安全的各种法律、信息安全的各种法律、信息安全的各种法律、法规。法规。法规。法规。商用密码管理条例；商用密码管理条例；商用密码管理条例；商用密码管理条例；计算机安全管理条例；计算机安全管理条例；计算机安全管理条例；计算机安全管理条例；因特网安全管理条例等。因特网安全管理条例等。因特网安全管理条例等。因特网安全管理条例等。信息安全的教育措施信息安全的教育措施 对人的思想品德教育、安全意识教育、安全法对人的思想品德教育、安全意识教育、安全法对人的思想品德教育、安全意识教育、安全法对人的思想品德教育、安全意识教育、安全法律法规的教育等。律法规的教育等。律法规的教育等。律法规的教育等。国内外的计算机犯罪事件都是人的思想品德出国内外的计算机犯罪事件都是人的思想品德出国内外的计算机犯罪事件都是人的思想品德出国内外的计算机犯罪事件都是人的思想品德出问题造成的。问题造成的。问题造成的。问题造成的。信息安全是一个系统工程必须综信息安全是一个系统工程必须综合采取各种措施才能奏效。合采取各种措施才能奏效。4、计算机系统的安全服务功能：、计算机系统的安全服务功能：l身份认证服务，身份认证服务，l访问控制服务，访问控制服务，l数据加密服务，数据加密服务，l数据完整性服务数据完整性服务，l不可否认服务，不可否认服务，l安全审计。安全审计。密码学的起源和发展三个阶段：三个阶段：1949 1949年之前年之前密码学是一门艺术密码学是一门艺术 1949 194919751975年年密码学成为科学密码学成为科学 1976 1976年以后年以后密码学的新方向密码学的新方向公钥密码学公钥密码学 1949 1949年之前年之前:n古典密码（古典密码（classical cryptography)classical cryptography)n密码学还不是科学密码学还不是科学,而是艺术而是艺术n出现一些密码算法和加密设备出现一些密码算法和加密设备n密码算法的基本手段密码算法的基本手段(substitution&(substitution&permutation)permutation)出现，针对的是字符出现，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现 隐写术隐写术(steganography):(steganography):通过隐藏消息的存在来保护消息通过隐藏消息的存在来保护消息.a.a.隐形墨水隐形墨水b.b.字符格式的变化字符格式的变化c.c.图象图像图象图像(象形文字的修改象形文字的修改)Modified Hieroglyphics,c.1900 B.C.)Modified Hieroglyphics,c.1900 B.C.密码学的第一个例子是对标准书写符号的修改密码学的第一个例子是对标准书写符号的修改例如例如:古埃及法老坟墓上的文字古埃及法老坟墓上的文字思想思想:代替代替(substitution)(substitution)n古埃及的原始密码（左方是密文，右方是相应的明文）古埃及的原始密码（左方是密文，右方是相应的明文）Phaistos圆盘古典密码圆盘古典密码Phaistos圆盘圆盘，一种直径约，一种直径约为为160mm的的Cretan-Mnoan粘土圆盘，始于粘土圆盘，始于公元前公元前17世纪。表面有明显字间空格的字母，世纪。表面有明显字间空格的字母，至今还没有破解。至今还没有破解。20世纪早期密码机世纪早期密码机Kryha密码机大约在密码机大约在1926年由年由Alexander vo Kryha发明。这是一发明。这是一个多表加密设备，密个多表加密设备，密钥长度为钥长度为442，周期，周期固定。一个由数量不固定。一个由数量不等的齿的轮子引导密等的齿的轮子引导密文轮不规则运动文轮不规则运动。哈格林（哈格林（HagelinHagelin）密码机）密码机C-36C-36，由，由Aktiebolaget Cryptoeknid StockholmAktiebolaget Cryptoeknid Stockholm于于19361936年制造密钥周期长度为年制造密钥周期长度为3,900,2553,900,255。M-209M-209是哈格林对是哈格林对C-36C-36改进后的产品，由改进后的产品，由Smith-Smith-CornaCorna负责为美国陆军生产。它的密码周期达到负责为美国陆军生产。它的密码周期达到了了101,105,950101,105,950。转轮密码机转轮密码机ENIGMAENIGMA，由，由Arthur ScherbiusArthur Scherbius于于19191919年发明，面板前有年发明，面板前有灯泡和插接板；灯泡和插接板；4 4轮轮ENIGMAENIGMA在在19441944年装备德年装备德国海军，似的英国从国海军，似的英国从19421942年年2 2月到月到1212月都没月都没能解读德国潜艇的信号。能解读德国潜艇的信号。英国的英国的TYPEXTYPEX打字密码机，是德国打字密码机，是德国3 3轮轮ENIGMAENIGMA的改的改进型密码机。它在英国通信中使用广泛，且在破进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。译密钥后帮助破解德国信号。在线密码电传机在线密码电传机Lorenz Lorenz SZ 42SZ 42，大约在，大约在19431943年年由由Lorenz A.GLorenz A.G制造。英制造。英国人称其为国人称其为“tunny”tunny”，用于德国战略级陆军，用于德国战略级陆军司令部。司令部。SZ 40/SZ 42SZ 40/SZ 42加密因为德国人的加密加密因为德国人的加密错误而被英国人破解，错误而被英国人破解，此后英国人一直使用电此后英国人一直使用电子子COLOSSUSCOLOSSUS机器解读德机器解读德国信号。国信号。计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 相关技术的发展相关技术的发展19491949年年ShannonShannon的的“The Communication Theory of The Communication Theory of Secret SystemsSecret Systems”19671967年年David KahnDavid Kahn的的The The CodebreakersCodebreakers1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst Horst FeistelFeistel等几篇技等几篇技术报告术报告 Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data Communication,1971Communication,19711.1.Smith,J.L.,An Smith,J.L.,An ExprementalApplicationExprementalApplication of of CryptogrphytoCryptogrphyto a a remotely Accessed Data System,Aug.1972remotely Accessed Data System,Aug.19722.2.Feistel,H.,CryptographyandFeistel,H.,Cryptographyand Computer Privacy,May 1973 Computer Privacy,May 1973主要特点：主要特点：数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密 第第2阶段阶段 1949197519761976年：年：DiffieDiffie&Hellman&Hellman 的的 “New Directions in New Directions in CryptographyCryptography”提出了不对称密钥密提出了不对称密钥密19771977年年Rivest,ShamirRivest,Shamir&AdlemanAdleman 提出了提出了RSARSA公钥算法公钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法主要特点：主要特点：公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能第第3阶段阶段 197619771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“Post DESPost DES”算法算法,如如IDEA,RCx,CASTIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6,MARS,Rijndael,RC6,MARS,Twofish,SerpentTwofish,Serpent等等对称算法对称算法出现出现20192019年年RijndaelRijndael成为成为DESDES的替代者的替代者第第3阶段阶段 1976为什么需要密码为什么需要密码n信息的存储信息的存储:在公开的地方在公开的地方n信息的交换信息的交换:使用非隐秘介质使用非隐秘介质n信息的传输信息的传输:通过不安全信道通过不安全信道密码基本概念密码基本概念n密码学密码学(Cryptology):(Cryptology):是研究信息系统安是研究信息系统安全保密的科学全保密的科学.n密码编码学密码编码学(Cryptography):(Cryptography):主要研究对主要研究对信息进行编码信息进行编码,实现对信息的隐蔽实现对信息的隐蔽.n密码分析学密码分析学(Cryptanalytics):(Cryptanalytics):主要研究加主要研究加密消息的破译或消息的伪造密消息的破译或消息的伪造.原始可理解的消息或数据被称为原始可理解的消息或数据被称为明文明文(Plaintext)(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为用某种方法伪装消息以隐藏它的内容的过程称为加密加密(Encrtption)(Encrtption)，消息被加密后得到的信息称，消息被加密后得到的信息称之为之为密文密文(Ciphertext)(Ciphertext)，而把密文转变为明文的，而把密文转变为明文的过程称为过程称为解密解密(Decryption)(Decryption)。对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员(Cryptographer).(Cryptographer).密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密是用于加密和解密的数学函数。和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称密码员对明文进行加密操作时所采用的一组规则称作作加密算法加密算法(Encryption Algorithm).(Encryption Algorithm).所传送信息的预定对象称为所传送信息的预定对象称为接收者接收者(Receiver).(Receiver).接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法(Decryption Algorithm).(Decryption Algorithm).加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的,分别称为加密密钥分别称为加密密钥(Encryption(EncryptionKey)Key)和解密密钥和解密密钥(Decryption Key).(Decryption Key).常规加密简化模型常规加密简化模型加密通信的模型密码学的目的：密码学的目的：AliceAlice和和BobBob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者OscarOscar不能理解他们通信的内容。不能理解他们通信的内容。按保密程度划分（按保密程度划分（保密内容）保密内容）按密钥方式划分按密钥方式划分 基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：按编制原理划分（明文处理的方式）按编制原理划分（明文处理的方式）密码分类密码分类 P13 受限制的（受限制的（restricted)算法算法 算法的保密性基于保持算法的秘密算法的保密性基于保持算法的秘密 基于密钥（基于密钥（key-based)的算法的算法 算法的保密性基于对密钥的保密算法的保密性基于对密钥的保密 对称密码算法（对称密码算法（symmetric cipher)symmetric cipher)加密密钥和解密密钥相同，或实质上等同，即从一个易于加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个推出另一个 又称秘密密钥算法或单密钥算法又称秘密密钥算法或单密钥算法 非对称密钥算法（非对称密钥算法（asymmetric cipher)asymmetric cipher)加密密钥和解密密钥不相同，从一个很难推出另一个加密密钥和解密密钥不相同，从一个很难推出另一个 又称公开密钥算法（又称公开密钥算法（public-key cipher)public-key cipher)公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密,而用另一个进行解密而用另一个进行解密 其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)public key)，简称公钥。，简称公钥。解密密钥必须保密解密密钥必须保密,又称私人密钥（又称私人密钥（private key)private key)私钥，简称私钥私钥，简称私钥基于密钥的算法，按照密钥的特点基于密钥的算法，按照密钥的特点分类分类：分组密码（分组密码（block cipher)将明文分成固定长度的组，用同一密钥和算法对将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。每一块加密，输出也是固定长度的密文。流密码（流密码（stream cipher)又称序列密码。又称序列密码。序列密码每次加密一位或一字节序列密码每次加密一位或一字节的明文。的明文。（按编制原理）明文处理方（按编制原理）明文处理方式式n密码系统的设计原则 P13Kerckhoffs原则 18831883年年KerchoffsKerchoffs第一次明确提出了编码的第一次明确提出了编码的原则：原则：加密算法加密算法应建立在算法的公开不影应建立在算法的公开不影响明文和密钥的安全的基础上。响明文和密钥的安全的基础上。这一原则已得到普遍承认，成为判定密码这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。和现代密码的分界线。替代替代移位（置换）移位（置换）加法加法经典加密技术经典加密技术基于字符的密码 代替密码（代替密码（substitution cipher)substitution cipher)：就是明文中的：就是明文中的每一个字符被替换成密文中的另一个字符。接收者每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。对密文做反向替换就可以恢复出明文。（代替规则、密文所用字符、明文中被代替的基本（代替规则、密文所用字符、明文中被代替的基本单位）单位）置换密码置换密码(permutation cipher)(permutation cipher)，又称换位密码，又称换位密码（transposition cipher)transposition cipher)：明文的字母保持相同，：明文的字母保持相同，但顺序被打乱了。但顺序被打乱了。n凯撒密表凯撒密表 公元前公元前5454年，古罗马长官凯撒年，古罗马长官凯撒 明文字母明文字母abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz 密文字母密文字母DEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABC 有一个拉丁文句子有一个拉丁文句子 Omnia Gallia est divisa in Partes tresOmnia Gallia est divisa in Partes tres RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV 把明文的拉丁字母逐个代之以相应的希腊字母把明文的拉丁字母逐个代之以相应的希腊字母恺撒密码恺撒密码破译以下密文：破译以下密文：wuhdwb lpsrvvleohTREATY IMPOSSIBLECi=E(Pi)=Pi+3加密算法：加密算法：字母表：字母表：(密码本）密码本）ABCDEFGHIJKLMNOPQRSTUVWXYZ defghijklmnopqrstuvwxyzabc明文明文（PlaintextPlaintext）：消息的初始形式；）：消息的初始形式；密文密文（CypherTextCypherText）：加密后的形式）：加密后的形式记：记：明文记为明文记为P P且且P P为字符序列，为字符序列，P=P1,P2,PnP=P1,P2,Pn密文记为密文记为C,C,C1,C2,CnC1,C2,Cn明文和密文之间的变换记为明文和密文之间的变换记为 C=E(P)C=E(P)及及P=D(C)P=D(C)其中其中 C C表示密文，表示密文，E E为加密算法；为加密算法；P P为明文，为明文，D D为解密算法为解密算法我们要求密码系统满足：我们要求密码系统满足：P=D(E(P)P=D(E(P)需要密钥的加密算法，记为：需要密钥的加密算法，记为：C=E(K,P),即密文消息即密文消息同时依赖于初始明文和密钥的值。实际上，同时依赖于初始明文和密钥的值。实际上，E是一组加是一组加密算法，而密钥则用于选择其中特定的一个算法。密算法，而密钥则用于选择其中特定的一个算法。加密与解密的密钥相同，即：加密与解密的密钥相同，即：P=D(K,E(K,P)加密与解密的密钥不同，则：加密与解密的密钥不同，则：P=D(KD,E(KE,P)恺撒密码的特点恺撒密码的特点n单字母密码（简单替换技术）单字母密码（简单替换技术）n简单，便于记忆简单，便于记忆n缺点：结构过于简单，密码分析员只使缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构用很少的信息就可预言加密的整个结构恺撒密码的改进恺撒密码的改进n已知加密与解密算法已知加密与解密算法nC=E(p)=(p+k)mod(26)np=D(C)=(C-k)mod(26)n25个可能的密钥个可能的密钥k，适用适用Brute-Force Cryptanalysis 暴力攻击法暴力攻击法(brute-force attack);attack);密码破密码破解法解法(cryptanalysis)n明文的语言是已知的且易于识别明文的语言是已知的且易于识别恺撒密码的改进恺撒密码的改进：其它单字母替换：其它单字母替换n使用密钥使用密钥nkeykeyABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzkeyabcdfghijlmnopqrstuvwxznspectacularspectacularABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyzspectaulrbdfghijkmnoqvwxyzn泄露给破译者的信息更少泄露给破译者的信息更少1.替换加密(1)单字母加密法单表置换密码，密钥Key是BEIJINGTSINGHUA明文字母abcdefghijklm密文字母BEIJN G TSH UACD明文字母nopqrstuvw xyz密文字母FKLM O PQRVW XYZ明文“important”，密文“HDLKOQBFQ”密钥短语密码 以西文单词为密钥的换字表以西文单词为密钥的换字表 例如：取例如：取atmosphereatmosphere为密钥，首先找出其中发生重为密钥，首先找出其中发生重复的字母，去掉重复字母复的字母，去掉重复字母e e，成为，成为atmospher.atmospher.其次，字母一共其次，字母一共1010个，从第个，从第1111个字母开始，用个字母开始，用atmosphereatmosphere按顺序进行代替配置。按顺序进行代替配置。然后把其余然后把其余1717个字母按自然顺序接在后面。个字母按自然顺序接在后面。以以atmosphereatmosphere为密钥的换字表为密钥的换字表 明文字母明文字母abcdeabcdefghijfghijklmnopqrstuvwxyzklmnopqrstuvwxyz密文字母密文字母KLNQUVWXYZATMOSPHERBCDFGIJKLNQUVWXYZATMOSPHERBCDFGIJ对称密码分析的两个基本方法 穷举法穷举法(Exhaustive Attack method),(Exhaustive Attack method),又称为强力法又称为强力法(Brute-force method).(Brute-force method).完全试凑法完全试凑法(complete trial-(complete trial-and error method)and error method)这是对截获的密文依次用各种可能的密钥破译这是对截获的密文依次用各种可能的密钥破译.对所有可能的明文加密直到与截获的密文一致为止对所有可能的明文加密直到与截获的密文一致为止.分析法分析法 系统分析法（统计分析法）系统分析法（统计分析法）:利用明文的统计规律利用明文的统计规律 确定性分析法确定性分析法密码破译 密码设计是利用数学来构造密码密码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学知密码分析除了依靠数学、工程背景、语言学知识外，识外，还要靠经验、统计、测试、眼力、直觉判断力还要靠经验、统计、测试、眼力、直觉判断力.有时还要靠点运气有时还要靠点运气 密码破译的原则密码破译的原则:遵循观察与经验遵循观察与经验 方法方法:采用归纳与演绎采用归纳与演绎 步骤步骤:分析、假设、推测和证实分析、假设、推测和证实多表代替代替密码 多表代替密码多表代替密码 维吉尼亚（维吉尼亚（Vigenere)Vigenere)密码密码 滚动密钥滚动密钥(running-key)(running-key)密码密码 弗纳姆弗纳姆(Vernam)(Vernam)密码密码 转子机转子机(rotor machine)(rotor machine)Vigenre cipher(1858)例子：例子：q=26,x=polyalphabeticcipher,K=RADIO明文明文x=p o l y a l p ha b e t i c c i p h e r密钥密钥k=RAD I ORADI ORADI ORADIO密文密文y=GOOGOCPKTP NTLKQZPKMF 是一种多表移位代替密码，以明文字母在Vigenre方阵中所代表的列，与对应的密钥字方阵中所代表的列，与对应的密钥字母在母在Vigenre方阵中所代表的行的交点处的字方阵中所代表的行的交点处的字母替换该明文字母。母替换该明文字母。明文密钥Vigenere方阵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 zAA B C D E F G H I J K L M N O P Q R S T U V W X Y ZBB C D E F G H I J K L M N O P Q R S T U V W X Y Z ACC D E F G H I J K L M N O P Q R S T U V W X Y Z A BDD E F G H I J K L M N O P Q R S T U V W X Y Z A B CEE F G H I J K L M N O P Q R S T U V W X Y Z A B C DFF G H I J K L M N O P Q R S T U V W X Y Z A B C D EGG H I J K L M N O P Q R S T U V W X Y Z A B C D E FHH I J K L M N O P Q R S T U V W X Y Z A B C D E F GII J K L M N O P Q R S T U V W X Y Z A B C D E F G HJJ K L M N O P Q R S T U V W X Y Z A B C D E F G H IKK L M N O P Q R S T U V W X Y Z A B C D E F G H I JLL M N O P Q R S T U V W X Y Z A B C D E F G H I J KMM N O P Q R S T U V W X Y Z A B C D E F G H I J K LNN O P Q R S T U V W X Y Z A B C D E F G H I J K L MOO P Q R S T U V W X Y Z A B C D E F G H I J K L M NPP Q R S T U V W X Y Z A B C D E F G H I J K L M N OQQ R S T U V W X Y Z A B C D E F G H I J K L M N O PRR S T U V W X Y Z A B C D E F G H I J K L M N O P QSS T U V W X Y Z A B C D E F G H I J K L M N O P Q RTT U V W X Y Z A B C D E F G H I J K L M N O P Q R SUU V W X Y Z A B C D E F G H I J K L M N O P Q R S TVV W X Y Z A B C D E F G H I J K L M N O P Q R S T UWW X Y Z A B C D E F G H I J K L M N O P Q R S T U VXX Y Z A B C D E F G H I J K L M N O P Q R S T U V WYY Z A B C D E F G H I J K L M N O P Q R S T U V W XZZ 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多多字字母母替替换换密密码码明文howareyou密钥STUDENTST密文ZHQDVRRGNVigenre cipher-破译 依然保留了字符频率某些统计信息依然保留了字符频率某些统计信息 分析的第一步是确定密钥字的长度分析的第一步是确定密钥字的长度d d，确定确定d d的的方法最常用的有两种方法最常用的有两种-Kasiski-Kasiski测试法测试法 1863 1863年，普鲁士军官年，普鲁士军官KasiskiKasiski提出的一种：提出的一种：-重码分析法重码分析法-重合指数法（重合指数法（index of coincidence)index of coincidence)英语的统计规律英语的统计规律 n每个单字母出现的频率稳定。每个单字母出现的频率稳定。最高频率字母最高频率字母 E E 次高频率字母次高频率字母 T A O I N S H RT A O I N S H R 中高频率字母中高频率字母 D LD L 低频率字母低频率字母 C U M W F G Y P BC U M W F G Y P B 最低频率字母最低频率字母 V K J X Q Z V K J X Q Z 英英语的统计规律语的统计规律 n频率最高的双字母组：频率最高的双字母组：TH HE IN ER AN RE ED ONTH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET OU EA NG AS OR TI IS ET IT AR TE SE HI OF IT AR TE SE HI OF 英语的统计规律英语的统计规律 n频率最高的三字母组：频率最高的三字母组：THE ING AND HER ERE ENT THA WASTHE ING AND HER ERE ENT THA WAS ETH FOR DHT HAT SHE ION HIS ERS ETH FOR DHT HAT SHE ION HIS ERS VER VER 其中其中THETHE的频率是的频率是INGING的的3 3倍！倍！英语的统计规律英语的统计规律 n英文单词以英文单词以E E，S S，D D，T T为结尾的超过一半。为结尾的超过一半。n英文单词以英文单词以T T，A A，S S，W W为起始字母的约占一为起始字母的约占一半。半。n还有其它统计规律还有其它统计规律！n教科书上有一个完整的统计分析例教科书上有一个完整的统计分析例子。子。Kasiski测试法 重码分析法：间距是密钥长度整数倍的相同子串有相同密重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可文，反过来，密文中两个相同的子串对应的密文相同的可能性很大能性很大 偶然重复和真重复偶然重复和真重复-他们之间的距离的因数可能就是密钥长度。他们之间的距离的因数可能就是密钥长度。Kasiski实验：实验：对一份用周期性多表密码加密的密文，确定其中所有的对一份用周期性多表密码加密的密文，确定其中所有的重复出现的字母串，计算他们之间的距离，并对这些距重复出现的字母串，计算他们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的离进行因子分解，出现频率较高的因子很可能是密钥的长度。长度。多名或同音代替密码多名或同音代替密码 多表代替密码多表代替密码 多字母代替密码多字母代替密码 PlayfairPlayfair密码密码 Hill Hill密码密码多字母代替密码-Playfair Playfair:Playfair:将将明文中的双字母组合明文中的双字母组合作为一个单元对待，并将这些单元转作为一个单元对待，并将这些单元转换为换为密文的双字母组合密文的双字母组合。55 55变换矩阵变换矩阵:I I与与J J视为同一字符视为同一字符C I P H EC I P H ER A B D FR A B D FG K L M N(cipher)G K L M N(cipher)O Q S T UO Q S T UV W X Y ZV W X Y ZPlayfair举例:computerPlayfair密码分析 PlayfairPlayfair有有26X26=67626X26=676种字母对组合种字母对组合 字符出现几率一定程度上被均匀化字符出现几率一定程度上被均匀化 基于字母频率的攻击比较困难基于字母频率的攻击比较困难 依然保留了相当的结构信息依然保留了相当的结构信息1、置换密码、置换密码把明文中的字母重新排列，字母本身不变，把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置但其位置改变了，这样编成的密码称为置换密码。换密码。n最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。明文：明晨明晨5点发动反攻。点发动反攻。MING CHEN WU DIAN FA DONG FAN GONG密文：GNOGN AFGNO DAFNA IDUWN EHCGN IM置换置换例如：例如：明文：明文：MING CHEN WU DIAN FA DONG FANMING CHEN WU DIAN FA DONG FAN GONGGONG矩阵：矩阵：MINGCH MINGCH 选出顺序：选出顺序：按列按列按列按列 ENWUDIENWUDI ANFADO ANFADO 改变矩阵大小和取出序列改变矩阵大小和取出序列改变矩阵大小和取出序列改变矩阵大小和取出序列 NGFANG NGFANG 可得到不同的密码可得到不同的密码可得到不同的密码可得到不同的密码 ONGONG密文：密文：MEANO INNGN NWFFG GUAA CDDNMEANO INNGN NWFFG GUAA CDDN HIOG HIOG 把明文按某一顺序排成一个矩阵，把明文按某一顺序排成一个矩阵，把明文按某一顺序排成一个矩阵，把明文按某一顺序排成一个矩阵，然后按另一顺然后按另一顺然后按另一顺然后按另一顺序选出矩阵中的字母以形成密文，最后截成固定长序选出矩阵中的字母以形成密文，最后截成固定长序选出矩阵中的字母以形成密文，最后截成固定长序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。度的字母组作为密文。度的字母组作为密文。度的字母组作为密文。换位密码 换位密码把明文按行写入换位密码把明文按行写入,按列读出按列读出 密钥包含密钥包含3方面信息方面信息:行宽行宽,列高列高,读出顺序读出顺序key:4 3 1 2 5 6 7 dcabefgplaintext:a t t a c k p o s t p o n e d u n t i l t w o a m x y zciphertext:TTNAAPTMTSUOAODWCOIXPETZ 完全保留字符的统计信息完全保留字符的统计信息 使用多轮加密可提高安全性使用多轮加密可提高安全性a t t a c k p o s t p o n e d u n t i l t w o a m x y z多次置换 多次置换，减少结构性排列，不易于重构。多次置换，减少结构性排列，不易于重构。key:4 3 1 2 5 6 7plaintext:t t n a a p t m t s u o a o d w c o I x k n l y p e t zciphertext:NSCYAUOPTTWLTMDNAOIEPAXTTOKZ列换位密码密钥MEGABUCK明文:pleasetransferonemilliondollars列序74512836 tomyswissbankaccountsixtwotwopleasetransferon密文:afllskso selawaia toossctc lnmomantemillion 第1列 第2列 第3列 第4列dollarst esilyntw rnntsowd paedobuo eriricxbomyswiss 第5列 第6列 第7列 第8列bankaccountsixtwotwoabcd古典密码小结 古典密码古典密码 代替密码代替密码 简单代替密码（单字母密码）简单代替密码（单字母密码）单表代替密码单表代替密码 移位（移位（shift shift）密码）密码 密钥短语（密钥短语（Key Word)Key Word)密码密码 任意的单表代替密码算法任意的单表代替密码算法 单表代替密码分析单表代替密码分析 多表代替密码多表代替密码 维吉尼亚（维吉尼亚（Vigenere)Vigenere)密码密码 弗纳姆弗纳姆(Vernam)(Vernam)密码密码 转子机转子机(rotor machine)(rotor machine)多字母密码：多字母密码：HillHill、PlayfairPlayfair密码密码 置换密码置换密码密码分析密码分析试图破译单条消息试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息破译后续的消息试图找到加密算法中的普遍缺陷（无须截取任何消息试图找到加密算法中的普遍缺陷（无须截取任何消息）课堂练习：若明文为 student，密钥为，密钥为BEIJING，利用凯撒密码加密方法，则对应的密文利用凯撒密码加密方法，则对应的密文是？是？xiexie!xiexie!谢谢！谢谢！xiexie!xiexie!谢谢！谢谢！