信息安全原理与应用-密码学基础课件.ppt

1 信息安全原理与应用信息安全原理与应用第二章第二章 密码学基础密码学基础本章由王昭主写本章由王昭主写2内容提要内容提要基本概念和术语基本概念和术语密码学的历史密码学的历史古典密码古典密码3基本概念基本概念密码学密码学(Cryptology)：是研究信息系统安全保是研究信息系统安全保密的科学密的科学。密码编码学密码编码学(Cryptography)：主要研究对信息主要研究对信息进行编码，实现对信息的隐蔽进行编码，实现对信息的隐蔽。密码分析学密码分析学(Cryptanalytics)：主要研究加密消主要研究加密消息的破译或消息的伪造息的破译或消息的伪造。4基本术语基本术语消息被称为消息被称为明文明文(Plaintext)。用某种方法伪装消息以隐。用某种方法伪装消息以隐藏它的内容的过程称为藏它的内容的过程称为加密加密(Encrtption)，被加密的消，被加密的消息称为息称为密文密文(Ciphertext)，而把密文转变为明文的过程，而把密文转变为明文的过程称为称为解密解密(Decryption)。对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员(Cryptographer)。密码算法密码算法(Cryptography Algorithm):是用于加密和解密是用于加密和解密的数学函数。的数学函数。密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称作加密算法加密算法(Encryption Algorithm)。所传送消息的预定对象称为所传送消息的预定对象称为接收者接收者(Receiver)。接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法(Decryption Algorithm)。5凯撒密表凯撒密表公元前公元前54年，古罗马长官凯撒年，古罗马长官凯撒明文字母明文字母 abcdefghijklmnopqrstuvwxyz密文字母密文字母 DEFGHIJKLMNOPQRSTUVWXYZABC有一个拉丁文句子有一个拉丁文句子omnia gallia est divisa in partes tres (高卢全境分为三个部分）高卢全境分为三个部分）RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV把明文的拉丁字母逐个代之以相应的希腊字母把明文的拉丁字母逐个代之以相应的希腊字母6 加解密过程示意图加解密过程示意图加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的，分别称为分别称为加密密钥加密密钥(Encryption Key)和和解密密钥解密密钥(Decryption Key)。7 密码学的目的密码学的目的：A和和B两个人在不安全的信道上进行两个人在不安全的信道上进行通信，而攻击者通信，而攻击者O不能理解他们通信的内容。不能理解他们通信的内容。加密通信的模型加密通信的模型8密码体制密码体制密码体制密码体制：它是一个五元组（：它是一个五元组（P,C,K,E,D)满足条件：满足条件：（1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间）（4）任意）任意k K，有一个加密算法有一个加密算法 和相应的解密算和相应的解密算法法 ，使得，使得 和和 分别为加密解密分别为加密解密函数，满足函数，满足dk(ek(x)=x，这里这里 x P。9密码算法分类密码算法分类-i按照保密的内容分按照保密的内容分:受限制的（受限制的（restricted）算法算法：算法的保密性基于保持算法的保密性基于保持算法的秘密。算法的秘密。基于密钥（基于密钥（key-based）的算法的算法：算法的保密性基于对算法的保密性基于对密钥的保密。密钥的保密。10密码算法分类密码算法分类-ii基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法（对称密码算法（symmetric cipher)：又称：又称传统密码算法传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称或实质上等同，即从一个易于推出另一个。又称秘密秘密密钥算法密钥算法或或单密钥算法单密钥算法。非对称密钥算法（非对称密钥算法（asymmetric cipher）:加密密钥和解加密密钥和解密密钥不相同，从一个很难推出另一个。又称密密钥不相同，从一个很难推出另一个。又称公开密公开密钥算法（钥算法（public-key cipher）。公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密,而用另一个进行解而用另一个进行解密密.其中的加密密钥可以公开其中的加密密钥可以公开，又称又称公开密钥（公开密钥（public key)，简称，简称公钥公钥。解密密钥必须保密解密密钥必须保密，又称又称私人密钥私人密钥（private key）私钥私钥，简称简称私钥私钥。11密码算法分类密码算法分类-iii按照明文的处理方法：按照明文的处理方法：分组密码（分组密码（block cipher）:将明文分成固定长度的组，将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度用同一密钥和算法对每一块加密，输出也是固定长度的密文。的密文。流密码（流密码（stream cipher）:又称又称序列密码序列密码。序列密码每序列密码每次加密一位或一字节的明文，也可以称为流密码。次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流序列密码是手工和机械密码时代的主流12密码算法分类密码算法分类-iv对称密钥密码又可分为：对称密钥密码又可分为：分组密码分组密码 每次对一块数据加密每次对一块数据加密 多数网络加密应用多数网络加密应用 DES、IDEA、RC6、Rijndael流密码流密码 每次对一位或一字节加密每次对一位或一字节加密 手机手机 One-time padding、Vigenre、Vernam13密码算法分类密码算法分类-v公开密钥密码公开密钥密码：大部分是分组密码，只有概率密码体制属于流密码大部分是分组密码，只有概率密码体制属于流密码 每次对一块数据加密每次对一块数据加密 数字签名数字签名,身份鉴别身份鉴别 RSA、ECC、ElGamal 加密解密速度慢加密解密速度慢14Kerckhoff原则原则1883年年Kerchoffs第一次明确提出了编码的原则：加密第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全的算法应建立在算法的公开不影响明文和密钥的安全的基础上。基础上。这一原则已得到普遍承认，成为判定密码强度的衡量这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。标准，实际上也成为古典密码和现代密码的分界线。15密码分析密码分析假设破译者假设破译者O是在已知密码体制的前提下来破译正在是在已知密码体制的前提下来破译正在使用的密钥，这个假设称为使用的密钥，这个假设称为Kerckhoff原则。最常见的原则。最常见的破解类型如下：破解类型如下：唯密文攻击：唯密文攻击：O具有密文串具有密文串y。已知明文攻击已知明文攻击:O具有明文串具有明文串x和相应的密文和相应的密文y。选择明文攻击：选择明文攻击：O可获得对加密机的暂时访问，可获得对加密机的暂时访问，因此因此他能选择明文串他能选择明文串x并构造出相应的密文串并构造出相应的密文串y。选择密文攻击选择密文攻击：O可暂时接近密码机可暂时接近密码机，可选择密文串可选择密文串y，并构造出相应的明文，并构造出相应的明文x。这一切的目的在于这一切的目的在于破译出密钥或密文破译出密钥或密文16 内容提要内容提要基本概念和术语基本概念和术语密码学的历史密码学的历史古典密码古典密码17密码学的起源和发展密码学的起源和发展-i三个阶段：三个阶段：1949年之前年之前 密码学是一门艺术密码学是一门艺术19491975年年 密码学成为科学密码学成为科学1976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学18密码学的起源和发展密码学的起源和发展-ii1949年之前年之前:古典密码（古典密码（classical cryptography)密码学还不是科学密码学还不是科学，而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段代替代替&置换置换（substitution&permutation）出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现19密码学的起源和发展密码学的起源和发展-iii19491975年年:计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能1949年年Shannon的的“The Communication Theory of Secret Systems”1967年年David Kahn的的The Codebreakers1971-73年年IBM Watson实验室实验室的的Horst Feistel等的几篇等的几篇技术报告技术报告 数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密20密码学的起源和发展密码学的起源和发展-iv1976年以后年以后:1976年年Diffie&Hellman的的“New Directions in Cryptography”提出了不对称密钥密码提出了不对称密钥密码1977年年Rivest，Shamir&Adleman提出了提出了RSA公钥算法公钥算法90年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成公钥密码使得发送端和接收端无密钥传输的保密通信成为可能为可能！21密码学的起源和发展密码学的起源和发展-v1976年以后年以后:对称密钥密码算法进一步发展对称密钥密码算法进一步发展1977年年DES正式成为标准正式成为标准80年代出现年代出现“过渡性过渡性”的的“post DES”算法算法，如如IDEA,RCx,CAST等等90年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6,MARS,Twofish,Serpent等出现等出现2001年年Rijndael成为成为DES的替代者的替代者22 内容提要内容提要基本概念和术语基本概念和术语密码学的历史密码学的历史古典密码古典密码23密码算法的安全性密码算法的安全性无条件安全（无条件安全（Unconditionally secure）无论破译者有多少密文无论破译者有多少密文，他也无法解出对应的他也无法解出对应的明文明文，即使他解出了即使他解出了，他也无法验证结果的正他也无法验证结果的正确性确性。One-time pad计算上安全（计算上安全（Computationally secure）破译的代价超出信息本身的价值。破译的代价超出信息本身的价值。破译的时间超出了信息的有效期破译的时间超出了信息的有效期。24古典密码古典密码基于字符的密码基于字符的密码代替密码（代替密码（substitution cipher)：就是明文中的：就是明文中的每一个字符被替换成密文中的另一个字符。接每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。收者对密文做反向替换就可以恢复出明文。（代替规则、密文所用字符、明文中被代替的基本单位）（代替规则、密文所用字符、明文中被代替的基本单位）置换密码置换密码（permutation cipher），又称，又称换位密换位密码（码（transposition cipher）：明文的字母保持相：明文的字母保持相同，但顺序被打乱了。同，但顺序被打乱了。古典密码古典密码代替密码代替密码置换密码置换密码2526代替密码代替密码简单代替密码（简单代替密码（simple substitution cipher），又称又称单字母密码（单字母密码（monoalphabetic cipher）：明文的一个字符用相应的一个密文字符代替，明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与一般的明文所用字符属而且密文所用的字符与一般的明文所用字符属同一语言系统。同一语言系统。多字母密码（多字母密码（ployalphabetic cipher）：明文中：明文中的字符映射到密文空间的字符还依赖于它在上的字符映射到密文空间的字符还依赖于它在上下文中的位置。下文中的位置。27单字母密码单字母密码单表代换密码单表代换密码 移位（移位（shift）密码、乘数（）密码、乘数（multiplicative）密码密码 仿射（仿射（affine)密码、多项式（密码、多项式（Polynomial）密码密码 密钥短语（密钥短语（Key Word）密码密码多表代换密码多表代换密码 维吉尼亚（维吉尼亚（Vigenere）密码密码 博福特（博福特（Beaufort）密码）密码 滚动密钥滚动密钥（running-key）密码密码 弗纳姆弗纳姆（Vernam）密码密码 转轮密码机转轮密码机（rotor machine）28多字母代换密码多字母代换密码可以用矩阵变换方便地描述可以用矩阵变换方便地描述多字母代换密码多字母代换密码，有时又称起为有时又称起为矩阵变换密码矩阵变换密码。Hill cipher Playfair cipher29模运算模运算-i定义集合为定义集合为Zq为小于为小于q的所有非负整数集合：的所有非负整数集合：Zq=0，1，2，,q-1，该集合也可看作模该集合也可看作模q的余数集合。在该的余数集合。在该集合上可以进行算术运算，就是所谓的集合上可以进行算术运算，就是所谓的模运算模运算。定义加法和乘法运算如下定义加法和乘法运算如下:加法加法:(a mod q)+(b mod q)mod q=(a+b)mod q 减法：减法：(a mod q)-(b mod q)mod q=(a-b)mod q 乘法乘法:(a mod q)(b mod q)mod q=(a b)mod q模运算有下述性质：模运算有下述性质：（1）若）若q|(a-b)，则，则a b(mod q)（2）(a mod q)=(b mod q)意味意味a b mod q（3）对称性对称性，a b mod q等价于等价于b a mod q（4）传递性）传递性，若若a b mod q且且b c mod q，则，则a c mod q30模运算模运算-ii类似普通的加法，在模运算中的每个数也存在类似普通的加法，在模运算中的每个数也存在加法逆加法逆元元，或者称为，或者称为相反数相反数。一个数一个数x的加法逆元的加法逆元y是满足是满足x+y 0 mod q的数。的数。对每一个对每一个 ，存在存在z，使得使得w+z 0 mod q。在通常的乘法中，每个数存在在通常的乘法中，每个数存在乘法逆元乘法逆元，或称为，或称为倒数倒数。在模在模q的运算中的运算中，一个数一个数x的乘法逆元的乘法逆元y是满足是满足x y 1 mod q 的数。但是并不是所有的数在模的数。但是并不是所有的数在模q下都存在乘法下都存在乘法逆元。逆元。如果如果(a b)mod q=(a c)mod q，b c mod q，如果如果a与与q互素。互素。如果如果q是一个素数，是一个素数，对每一个对每一个 ,都存在都存在z，使得使得w z 1 mod q，z称作称作w的乘法逆元的乘法逆元w-1。31模运算模运算-iii模模26的最小非负完全剩余系，即模的最小非负完全剩余系，即模26的余数集合为的余数集合为0,1,2,25。可以把字母表与模可以把字母表与模26的余数集合等同，的余数集合等同，26个英文字母个英文字母与模与模26余数集合余数集合0,.,25建立一一对应，在此基础上建立一一对应，在此基础上对字符进行运算。对字符进行运算。32单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码）密码乘数（乘数（multiplicative)密码密码仿射（仿射（affine)密码密码密钥短语（密钥短语（Key Word）密码密码任意的单表代替密码任意的单表代替密码33移位密码算法移位密码算法设设P=C=K=Z26，对对k K,定义定义ek(x)=x+k(mod 26)=y C 同时同时dk(y)=y-k(mod 26)当当k=3时，为时，为Caesar密码密码 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC 例子例子:cipher=FLSKHU 实际算法为：实际算法为：有有 同时有，同时有，d3(y)=y-3(mod 26)34移位密码分析移位密码分析给定加密的消息给定加密的消息:PHHW PH DIWHU WKH WRJD SDUWB由于（由于（1）加解密算法已知）加解密算法已知（2）可能尝试的密钥只有）可能尝试的密钥只有25个个（不包括不包括0）通过强力攻击得到明文：通过强力攻击得到明文：meet me after the toga party.移位密码很容易受到唯密文攻击。移位密码很容易受到唯密文攻击。35单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码）密码乘数（乘数（multiplicative)密码密码仿射（仿射（affine)密码密码密钥短语（密钥短语（Key Word)密码密码任意的单表代替密码任意的单表代替密码36乘数密码算法乘数密码算法加密函数取形式为加密函数取形式为 e(x)=ax(mod 26)，aZ26 要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1 该算法描述为：该算法描述为：设设P=C=Z26，K=a Z26|gcd(a,26)=1,对对k=a K,定义定义 ek(x)=ax(mod 26)和和dk(y)=a-1(y)(mod 26)x,y Z26例子例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 明文明文 密文密文 cipher=SUFLKX37乘数密码分析乘数密码分析对于乘数密码，当且仅当对于乘数密码，当且仅当a与与26互素时，加密互素时，加密变换才是一一映射的，因此变换才是一一映射的，因此a的选择有的选择有11种：种：a=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有可能尝试的密钥只有1个个38单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码）密码乘数（乘数（multiplicative)密码密码仿射（仿射（affine)密码密码密钥短语（密钥短语（Key Word)密码密码任意的单表代替密码任意的单表代替密码39仿射密码算法仿射密码算法-i加密函数取形式为加密函数取形式为 e(x)=ax+b(mod 26),a,bZ26 要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1 该算法描述为：该算法描述为：设设P=C=Z26 K=(a,b)Z26Z26|gcd(a,26)=1,对对k=(a,b)K，定义定义 ek(x)=ax+b(mod 26)和和dk(y)=a-1(y-b)(mod 26)x,y Z26q=26时，可能的密钥是时，可能的密钥是2612-1=311个个40单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码）密码乘数（乘数（multiplicative)密码密码仿射（仿射（affine)密码密码密钥短语（密钥短语（Key Word)密码密码任意的单表代替密码任意的单表代替密码41密钥短语密码密钥短语密码以西文单词为密钥的换字表以西文单词为密钥的换字表例如：取例如：取university为密钥，首先找出其中发生重复为密钥，首先找出其中发生重复的字母，去掉重复字母的字母，去掉重复字母i，成为，成为universty.其次，字母一共其次，字母一共10个，从第个，从第11个字母开始，用个字母开始，用universty按顺序进行代替配置。按顺序进行代替配置。然后把其余然后把其余17个字母按自然顺序接在后面。个字母按自然顺序接在后面。以以university为密钥的换字表为密钥的换字表明文字母明文字母 abcdefghijklmnopqrstuvwxyz密文字母密文字母 JKLMOPQWXZUNIVERSTYABCDFGH42非自然续序配置的换字表非自然续序配置的换字表明文字母与代替他的密文字母豪无关联明文字母与代替他的密文字母豪无关联那么整个换字表就是他的密钥那么整个换字表就是他的密钥明文字母明文字母 abcdefghijklmnopqrstuvwxyz密文字母密文字母 IGVRFHPJYBNKAXLTSMCWDUEOZQ43单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码）密码乘数（乘数（multiplicative)密码密码仿射（仿射（affine)密码密码密钥短语（密钥短语（Key Word)密码密码任意的单表代替密码任意的单表代替密码44任意的单表代替密码算法任意的单表代替密码算法设设P=C=Z26，K是由是由26个符号个符号0，1，.，5的所有可能置的所有可能置换组成。任意换组成。任意K，定义，定义e(x)=(x)=y 且且d(y)=-1(y)=x,-1是是的逆置换。的逆置换。注：注：1*.置换置换的表示：的表示：2*密钥空间密钥空间K很大，很大，|k|=26!41026，破译者穷举搜索是不，破译者穷举搜索是不行的，然而，可由统计的方式破译它。行的，然而，可由统计的方式破译它。3*移位密码、乘数密码、仿射密码算法都是替换密码的特移位密码、乘数密码、仿射密码算法都是替换密码的特例例0 1 2 3.23 24 250 1 2 3.23 24 25)(45单表替换密码的破译单表替换密码的破译语言的统计特性：语言的统计特性：语言的频率特征语言的频率特征连接特征连接特征重复特征重复特征46频率特征频率特征在各种语言中在各种语言中，各个字母的使用次数是不一样的各个字母的使用次数是不一样的，有有的偏高的偏高，有的偏低有的偏低，这种现象叫这种现象叫偏用现象偏用现象。对英文的任何一篇文章，一个字母在该文章中出现的对英文的任何一篇文章，一个字母在该文章中出现的次数称作这个字母（在这篇文章中）的次数称作这个字母（在这篇文章中）的频数频数。一个字母的频数除以文章的字母总数，就得到字母的一个字母的频数除以文章的字母总数，就得到字母的使用频率使用频率。47英文字母的普遍使用频率英文字母的普遍使用频率美国密码学家美国密码学家W.F.Friedman在调查了大量英文资料后在调查了大量英文资料后,得出英文字母的普遍使用规律得出英文字母的普遍使用规律.48英文单字母使用频率分类英文单字母使用频率分类49特殊的特征特殊的特征开头结尾特征开头结尾特征:有些文章的开头和结尾受到固定格式的限制有些文章的开头和结尾受到固定格式的限制有时文章中间的某些特定部位有时文章中间的某些特定部位，某些字母也会某些字母也会出现较高的使用频率出现较高的使用频率。50频度最高的前频度最高的前30个双字母个双字母 51频度最高的前频度最高的前20个三字母个三字母 52其它频率特征其它频率特征the 的使用频率最高，是的使用频率最高，是ING的三倍，若把的三倍，若把the 去掉，去掉，t在第在第II类中排在最后，类中排在最后，h会降为第会降为第III类，类，th和和 he也不是常出现的字母组了也不是常出现的字母组了一半的单词以一半的单词以e s d t 结尾结尾一半的单词以一半的单词以t a s w开头开头Y的使用频率的使用频率90%都集中在单词的结尾都集中在单词的结尾53连接特征连接特征后连接：后连接：q u 前连接前连接：x的前面总是的前面总是 i，e很少是很少是o和和a 间断连接：在间断连接：在e和和e之间，之间，r的出现频率最高的出现频率最高54重复特征重复特征两个字符以上的字符串重复出现的现象，叫做两个字符以上的字符串重复出现的现象，叫做语言的重复特征。语言的重复特征。th tion tious 例子例子-密文密文QRLLIQQPFVICXPFMTPZWRFNFOTFLPYWIGQPQHICQRGIVAKZWIQIBORGZWPFMQPFZWIOGVIGFCHIVYIGQIJIGCFLILCGIBRXHIZWOVQOBCFCXKQPQPFZRPZPOFXRLNZWICAPXPZKCZXICQZZOGICVZWIXCFMRCMIOBZWIOGPMPFCXZISZPQJIGKVIQPGCAXIARZFOZIQQIFZPCX55确定字母的相对频率确定字母的相对频率I可能相当于明文中的可能相当于明文中的e56双字母频率双字母频率57最常见的双字母组合最常见的双字母组合ZW，Z 猜测其为猜测其为T，W对应对应为为HWI HEPF IN进一步分析进一步分析-1ZWIQI与与these相似，相似，Q STPZW与与with类似，类似，T WIQQIFZPCX与与essential相似，相似，C A，X LCFCXKQPQ与与analysis类似，类似，K YCAPXPZK与与ability类似，类似，A B58进一步分析进一步分析-2ZWPFM与与things类似，类似，M GXCFMRCMI与与language类似，类似，R UVICXPFM与与dealing类似，类似，V DQRLLIQQ与与success类似，类似，L CGICV与与read类似，类似，G R59进一步分析进一步分析-3LCGIBRX与与careful类似，类似，B FHICQRGIV与与measured类似，类似，H MHIZWOVQ与与methods类似，类似，O OJIGK猜测为猜测为veryYIGQIJIGCFLI猜测为猜测为perseveranceRFNFOTF猜测为猜测为unknown，把，把ZISZ猜测为猜测为text60密钥密钥61完整明文完整明文Success in dealing with unknown ciphers is measured by these four things in the order named：perseverance，careful methods of analysis，intuition，luck.The ability at least to read the language of the original text is very desirable but not essential.6263对抗频率分析的办法对抗频率分析的办法多名或同音代替密码多名或同音代替密码多表代替密码多表代替密码多字母代替密码多字母代替密码 64多名代替密码多名代替密码 与与简简单单代代替替密密码码类类似似，只只是是映映射射是是一一对对多多的的，每个明文字母可以加密成多个密文字母。每个明文字母可以加密成多个密文字母。例如，例如，A可能对应于可能对应于5、13、25 B可能对应于可能对应于7、9、31、4265多表代替密码多表代替密码多表代替密码：多表代替密码：是以一系列（两个以上）代换是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。表依此对明文消息的字母进行代换的方法。非周期多表代替密码：非周期多表代替密码：代换表是非周期的无限序列代换表是非周期的无限序列 一次一密密码（一次一密密码（one-time padding)：对每个明对每个明文每次采用不同的代换表。文每次采用不同的代换表。周期多表代替密码：代换表个数有限，重复使周期多表代替密码：代换表个数有限，重复使用。用。66多表代替密码多表代替密码多表代替密码多表代替密码维吉尼亚（维吉尼亚（Vigenere)密码密码滚动密钥滚动密钥（running-key）密码密码弗纳姆（弗纳姆（Vernam）密码密码转轮密码机转轮密码机（rotor machine）67Vigenre cipher(1858)是一种多表移位代替密码是一种多表移位代替密码 设设d为一固定的正整数，为一固定的正整数，d个移位代换表个移位代换表=（1，2,d)由由密钥序列密钥序列K（k1,k2,kd)给定给定，第，第i+td个明个明文字母由表文字母由表 i决定，即密钥决定，即密钥ki决定决定 ek(xi+td)=(xi+td+ki)mod q=y dk(yi+td)=(xi+td-ki)mod q=x例子：例子：q=26,x=polyalphabetic cipher,K=RADIO68Vigenre cipher-破译破译密钥空间大小为密钥空间大小为26m，m=5，265=1.1 107依然保留了字符频率某些统计信息依然保留了字符频率某些统计信息分析的第一步是确定密钥字的长度分析的第一步是确定密钥字的长度d，确定，确定d的的方法最常用的有两种方法最常用的有两种-Kasiski测试法测试法1863年，普鲁士军官年，普鲁士军官Kasiski提出的一种重码分提出的一种重码分析法析法-重合指数法（重合指数法（index of coincidence)69Kasiski测试法测试法重码分析法重码分析法：间距是密钥长度整数倍的相同子串有相同密：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的文，反过来，密文中两个相同的子串对应的密文相同的可可能性很大能性很大偶然重复和真重复偶然重复和真重复-他们之间的距离的因数可能就是密钥长度。他们之间的距离的因数可能就是密钥长度。Kasiski实验：实验：对一份用周期性多表密码加密的密文，确定其中所有的对一份用周期性多表密码加密的密文，确定其中所有的重复出现的字母串，计算他们之间的距离，并对这些距重复出现的字母串，计算他们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的离进行因子分解，出现频率较高的因子很可能是密钥的长度。长度。70重合指数重合指数设设y是一个长度为是一个长度为n密文，即密文，即y=y=y1y2y3ym，其中其中yi是密是密文字母，同样来求从中抽到两个相同字母的概率是多少文字母，同样来求从中抽到两个相同字母的概率是多少？为此？为此，设设NA为字母为字母A在这份密文中的频数在这份密文中的频数，设设NB为字为字母母B在这份密文中的频数在这份密文中的频数，依此类推依此类推。从从n个密文字母中抽取两个字母的方式有个密文字母中抽取两个字母的方式有Cn2=n(n-1)/2，而其中而其中NA个个A组成一对组成一对A的方式有的方式有CNA2=NA(NA-1)/2，于，于是从是从y中抽到两个字母都为中抽到两个字母都为A的概率为的概率为NA(NA-1)/n(n-1)，因此，从因此，从y中抽到两个相同字母的概率为中抽到两个相同字母的概率为这个数据称为这份密文的这个数据称为这份密文的重合指数。重合指数。记为记为IC71一个判断准则一个判断准则根据概率论中的大数定律，如果根据概率论中的大数定律，如果y是用单表加是用单表加密的，那么当密的，那么当n较大时，较大时，IC很可能接近于很可能接近于0.068772多表代替密码多表代替密码多表代替密码多表代替密码维吉尼亚（维吉尼亚（Vigenere)密码密码滚动密钥滚动密钥（running-key）密码密码弗纳姆弗纳姆（Vernam）密码密码转轮密码机转轮密码机（rotor machine）73滚动密钥密码滚动密钥密码对于周期代换密码，当密钥的长度对于周期代换密码，当密钥的长度d和明文一和明文一样长时，就成为滚动密钥密码。样长时，就成为滚动密钥密码。Vigenre本人建议密钥与明文一样长本人建议密钥与明文一样长74多表代替密码多表代替密码多表代替密码多表代替密码维吉尼亚（维吉尼亚（Vigenere)密码密码滚动密钥滚动密钥（running-key）密码密码弗纳姆弗纳姆（Vernam）密码密码转轮密码机转轮密码机（rotor machine）75Vernam密码密码1918年，年，Gillbert Vernam建议密钥与明文一样建议密钥与明文一样长并且没有统计关系的密钥内容长并且没有统计关系的密钥内容，他采用的是，他采用的是二进制数据二进制数据:加密加密：Ci=Pi Ki 解密解密 Pi=Ci Ki 核心：构造和消息一样长的随机密钥核心：构造和消息一样长的随机密钥 76多表代替密码多表代替密码多表代替密码多表代替密码维吉尼亚（维吉尼亚（Vigenere)密码密码滚动密钥滚动密钥（running-key）密码密码弗纳姆弗纳姆（Vernam）密码密码转轮密码机转轮密码机（rotor machine）77转轮密码机转轮密码机三个转轮的代替表数量三个转轮的代替表数量 262626=1757678对抗频率分析的办法对抗频率分析的办法多名或同音代替密码多名或同音代替密码多表代替密码多表代替密码多字母代替密码多字母代替密码Playfair密码密码Hill密码密码79多字母代替密码多字母代替密码-PlayfairPlayfair:将明文中的双字母组合作为一个单元将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。对待，并将这些单元转换为密文的双字母组合。55变换矩阵变换矩阵:I与与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 Z加密规则加密规则:按成对字母加密按成对字母加密1)1)相同对中的字母加分隔符相同对中的字母加分隔符(如如x)x)2)2)balloon balloon ba lx lo on ba lx lo on3)3)同行取右边同行取右边:he:he EC EC4)4)同列取下边同列取下边:dm:dm MT MT5)5)其他取交叉其他取交叉:kt:kt MQ OD MQ OD TR TR80Playfair密码分析密码分析Playfair有有2626=676种字母对组合种字母对组合字符出现几率一定程度上被均匀化字符出现几率一定程度上被均匀化基于基于字母字母频率的攻击比较困难频率的攻击比较困难依然保留了相当的结构信息依然保留了相当的结构信息81多字母代替密码多字母代替密码多字母代替密码多字母代替密码Playfair密码密码Hill密码密码82Hill密码（密码（1929）基于矩阵的线性变换基于矩阵的线性变换:假设假设K是一个是一个m*m矩阵，在矩阵，在Z26上可逆，即存在上可逆，即存在K-1使得：使得：KK-1=I（在（在Z26上），上），对每一个对每一个kK，定义，定义ek(x)=xK(mod 26)和和 dk(y)=yK-1(mod 26)明文与密文都是明文与密文都是 m元的向量元的向量 （x1,x2,xm），（），（y1,y2,ym）83Hill密码分析密码分析完全隐藏了字符完全隐藏了字符（对对）的频率信息的频率信息采用唯密文攻击希尔密码是很难攻破的采用唯密文攻击希尔密码是很难攻破的.线性变换的安全性很脆弱，易被线性变换的安全性很脆弱，易被已知明文攻击已知明文攻击击破。击破。古典密码古典密码代替密码代替密码置换密码置换密码8485置换密码置换密码在换位密码中，明文的字母保持相同，但顺序在换位密码中，明文的字母保持相同，但顺序被打乱了。被打乱了。一种换位密码把明文按行写入一种换位密码把明文按行写入,按列读出按列读出密钥包含密钥包含3方面信息方面信息:行宽行宽、列高列高、读出顺序读出顺序完全保留字符的统计信息完全保留字符的统计信息使用多轮加密可提高安全性使用多轮加密可提高安全性86 古典密码小结古典密码小结模运算：模运算：加法、减法、乘法加法、减法、乘法性质：对