1、 华中科技大学计算机学院信息安全课题组华中科技大学计算机学院信息安全课题组信息安全的含义（COMSECCOMSEC）：）：60-7060-70年代年代 信息保密信息保密（INFOSECINFOSEC）：）：80-9080-90年代年代 机密性、完整性、可用性、不可否认性机密性、完整性、可用性、不可否认性 等等（IAIA）：）：9090年代年代-基本的通讯模型基本的通讯模型 通信的保密模型通信的保密模型通信安全通信安全-60年代（年代（COMSEC）发方发方收方收方信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议发方发方收方收方敌人敌人信源编码信源编码信道编码信道编码信道传输信道
2、传输通信协议通信协议密码密码信息安全的含义信息安全的含义(80-90年代年代)信息安全的三个基本方面信息安全的三个基本方面 保密性保密性 Confidentiality即保证信息为授权者享用而不泄漏给未经授权者即保证信息为授权者享用而不泄漏给未经授权者 完整性完整性 Integrity 数据完整性，未被未授权篡改或者损坏数据完整性，未被未授权篡改或者损坏 系统完整性，系统未被非授权操纵，按既定的功系统完整性，系统未被非授权操纵，按既定的功能运行能运行 可用性可用性 Availability即保证信息和信息系统随时为授权者提供服务，而即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥
3、用却对授权者拒绝服务的情况。不要出现非授权者滥用却对授权者拒绝服务的情况。信息安全的其他方面信息安全的其他方面 信息的不可否认性信息的不可否认性Non-repudiation：要求无论发送方还是接收方都不能抵赖所进要求无论发送方还是接收方都不能抵赖所进行的传输行的传输 鉴别鉴别Authentication 鉴别就是确认实体是它所声明的。适用于用鉴别就是确认实体是它所声明的。适用于用户、进程、系统、信息等户、进程、系统、信息等 审计审计Accountability 确保实体的活动可被跟踪确保实体的活动可被跟踪 可靠性可靠性Reliability 特定行为和结果的一致性特定行为和结果的一致性安全需
4、求的多样性安全需求的多样性 保密性保密性 一致性一致性 可用性可用性 可靠性可靠性 可认证，真实性可认证，真实性 责任定位，审计性责任定位，审计性 高性能高性能 实用性实用性 占有权占有权 信息保障Information Assurance（rotect）（etect）（eact）（estore）保护保护Protect检测检测Detect反应反应React恢复恢复Restore密码从军事走向生活密码从军事走向生活 电子邮件电子邮件 自动提款机自动提款机 电话卡电话卡:IP卡、卡、201电话卡电话卡 银行取钱银行取钱 信用卡购物信用卡购物基本概念基本概念 密码学密码学(Cryptology):是
5、研究信息系统安全保密是研究信息系统安全保密的科学的科学.密码编码学密码编码学(Cryptography):主要研究对信息主要研究对信息进行编码进行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):主要研究加密消主要研究加密消息的破译或消息的伪造息的破译或消息的伪造.基本术语基本术语 消息被称为消息被称为明文明文(Plaintext)(Plaintext)。用某种方法伪装消息以。用某种方法伪装消息以隐藏它的内容的过程称为隐藏它的内容的过程称为加密加密(Encrtption(Encrtption)，被加密，被加密的消息称为的消息称为密文密文(Cipher
6、text(Ciphertext)，而把密文转变为明文，而把密文转变为明文的过程称为的过程称为解密解密(Decryption)(Decryption)。对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员(Cryptographer).(Cryptographer).密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解是用于加密和解密的数学函数。密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称作加密算法加密算法(Encryption
7、 Algorithm).(Encryption Algorithm).所传送消息的预定对象称为所传送消息的预定对象称为接收者接收者(Receiver).(Receiver).接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法(Decryption Algorithm).(Decryption Algorithm).加解密过程示意图加解密过程示意图 加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的,分别称为分别称为加密密钥加密密钥(Encryption Key)和和解密密钥解密密钥(Decryption
8、 Key).明文明文密文加密算法解密算法密钥密钥 密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者Oscar不能理解他们通信的内容。不能理解他们通信的内容。加密通信的模型加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk密码体制密码体制 密码体制：密码体制：它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件：满足条件：（1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间）（3）K是一切可能密钥构
9、成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间）*（4）任意）任意k K,有一个加密算法有一个加密算法 和相应的解密算和相应的解密算法法 ，使得，使得 和和 分别为加密解密分别为加密解密函数，满足函数，满足dk(ek(x)=x,这里这里 x P。EekDdkCPek:PCdk:密码算法分类密码算法分类-i 按照保密的内容分按照保密的内容分:受限制的（受限制的（restricted)算法算法:算法的保密性基于算法的保密性基于保持算法的秘密。保持算法的秘密。基于密钥（基于密钥（key-based)的算法的算法:算法的保密性基算法的保密性基于对密钥的保密。于对密钥的保密。密码算法分类
10、密码算法分类-ii 基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法对称密码算法（symmetric cipher)：又称：又称传统密码算传统密码算法（法（conventional cipher)，就是加密密钥和解密密钥，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又相同，或实质上等同，即从一个易于推出另一个。又称称秘密密钥算法秘密密钥算法或或单密钥算法单密钥算法。非对称密钥算法（非对称密钥算法（asymmetric cipher):加密密钥和解密加密密钥和解密密钥不相同，从一个很难推出另一个。又称密钥不相同，从一个很难推出另一个。又称
11、公开密钥公开密钥算法（算法（public-key cipher)。公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密,而用另一个进行解而用另一个进行解密密.其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥，简称公钥.解密密钥必须保密解密密钥必须保密,又称私人密钥又称私人密钥（private key)私钥私钥.简称简称私钥私钥。密码算法分类密码算法分类-iii 按照明文的处理方法：按照明文的处理方法：分组密码（分组密码（block cipher):将明文分成固定长度将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出的组，
12、用同一密钥和算法对每一块加密，输出也是固定长度的密文。也是固定长度的密文。流密码（流密码（stream cipher):又称又称序列密码序列密码.序列密序列密码每次加密一位或一字节的明文，也可以称为码每次加密一位或一字节的明文，也可以称为流密码。流密码。序列密码是手工和机械密码时代的主流序列密码是手工和机械密码时代的主流密码算法分类密码算法分类-iv 对称密钥密码又可分为：对称密钥密码又可分为：分组密码分组密码 每次对一块数据加密每次对一块数据加密 多数网络加密应用多数网络加密应用 DES,IDEA,RC6,RijndaelDES,IDEA,RC6,Rijndael流密码流密码 每次对一位或一
13、字节加密每次对一位或一字节加密 手机手机 One-time padding,Vigenre,VernamOne-time padding,Vigenre,Vernam密码算法分类密码算法分类-v 公开密钥密码公开密钥密码:大部分是分组密码，只有概率密码体制属于大部分是分组密码，只有概率密码体制属于流密码流密码 每次对一块数据加密每次对一块数据加密 数字签名数字签名,身份认证身份认证 RSA,ECC,ElGamalRSA,ECC,ElGamal 加密解密速度慢加密解密速度慢密码学的起源和发展密码学的起源和发展-i三个阶段：三个阶段：19491949年之前年之前 密码学是一门艺术密码学是一门艺术
14、1949194919751975年年 密码学成为科学密码学成为科学 19761976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学密码学的起源密码学的起源隐写术隐写术(steganography):通过隐藏消息的通过隐藏消息的存在存在来保护消息来保护消息.a.隐形墨水隐形墨水b.字符格式的变化字符格式的变化c.图象图像图象图像 example-i(象形文字的修改象形文字的修改)Modified Hieroglyphics,c.1900 B.C.密码学的第一个例子是对标准书写符号的修改密码学的第一个例子是对标准书写符号的修改 例如例如:古埃及法老坟墓上的文字古埃及法老坟墓上的文字
15、 思想思想:代替代替(substitution)example-ii Spartan Scytale,c.500 B.C.斯巴达人用于加解密的一种军事设备斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形发送者把一条羊皮螺旋形地缠在一个圆柱形棒上棒上思想：置换（思想：置换（permutation)example-iii Polybius Checkerboard,205123 B.C.明文明文:POLYBIUS 密文密文:3534315412244543 123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZExample-iv Caesar Ciphe
16、r,c.50 B.C.A B C D E F G X Y Z D E F G H I J A B C 明文明文:Caesar cipher is a shift substitution 密文密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQExample-V Nomenclator 代码本代码本 c.1400字母、符号、单词、短语字母、符号、单词、短语 代码代码代码代码 字母、符号、单词、短语字母、符号、单词、短语应用：应用：World War II密码学的起源和发展密码学的起源和发展-ii 19491949年之前年之前:古典密码（古典密码（classical
17、cryptography)classical cryptography)密码学还不是科学密码学还不是科学,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段(substitution&(substitution&permutation)permutation)出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现密码学的起源和发展密码学的起源和发展-iii 1949194919751975年年:计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 19491949年年ShannonShan
18、non的的“The Communication Theory of The Communication Theory of Secret Systems”Secret Systems”19671967年年David KahnDavid Kahn的的The CodebreakersThe Codebreakers 1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst FeistelHorst Feistel等的几等的几篇技术报告篇技术报告 Smith,J.L.,The Design of Lucifer,A Cryptographic Device
19、for Data Communication,1971Smith,J.L.,An Expremental Application of Cryptogrphy to a remotely Accessed Data System,Aug.1972 Feistel,H.,Cryptography and Computer Privacy,May 1973数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密密码学的起源和发展密码学的起源和发展-iv 19761976年以后年以后:19761976年年Diffie&HellmanDiffie&Hellman的的“New Directi
20、ons“New Directions in Cryptography”in Cryptography”提出了不对称密钥密码提出了不对称密钥密码19771977年年Rivest,Shamir&AdlemanRivest,Shamir&Adleman提出了提出了RSARSA公公钥算法钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能！密码学的起源和发展密码学的起源和发展-v 19761976年以后年以后:对称密钥密码算法进一步发展对称密钥密码算法进一步发展1
21、9771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“post DES”“post DES”算法算法,如如IDEA,RCx,CASTIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6,MARS,TwofishRijndael,RC6,MARS,Twofish,Serpent,Serpent等出等出现现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者密码分析密码分析 假设破译者假设破译者Oscar是在已知密码体制的前提下来是在已知密码体制的前提下
22、来破译破译Bob使用的密钥。这个假设称为使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：原则。最常见的破解类型如下：1.唯密文攻击：唯密文攻击：Oscar具有密文串具有密文串y.2.已知明文攻击已知明文攻击:Oscar具有明文串具有明文串x和相应的密和相应的密文文y.3.选择明文攻击：选择明文攻击：Oscar可获得对加密机的暂时可获得对加密机的暂时访问，访问，因此他能选择明文串因此他能选择明文串x并构造出相应的并构造出相应的密文串密文串y。4.选择密文攻击选择密文攻击:Oscar可暂时接近密码机可暂时接近密码机,可选可选择密文串择密文串y，并构造出相应的明文，并构造出相应
23、的明文x.这一切的目的在于这一切的目的在于破译出密钥或密文破译出密钥或密文密码破译密码破译 密码破译的原则密码破译的原则:遵循观察与经验遵循观察与经验 方法方法:采用归纳与演绎采用归纳与演绎 步骤步骤:分析、假设、推测和证实分析、假设、推测和证实 三大要素：三大要素：语言的频率特征：语言的频率特征：e 连接特征连接特征:q u,I e x,重复特征重复特征:th,tion,tious密码算法的安全性密码算法的安全性无条件安全（无条件安全（Unconditionally secureUnconditionally secure）无论破译者有多少密文无论破译者有多少密文,他也无法解出他也无法解出对
24、应的明文对应的明文,即使他解出了即使他解出了,他也无法验他也无法验证结果的正确性证结果的正确性.Onetime pad Onetime pad计算上安全（计算上安全（Computationally secureComputationally secure）破译的代价超出信息本身的价值破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译的时间超出了信息的有效期.古典密码古典密码基于字符的密码基于字符的密码 代替密码（代替密码（substitution cipher)：就是明文中：就是明文中的每一个字符被替换成密文中的另一个字符。的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替
25、换就可以恢复出明文。接收者对密文做反向替换就可以恢复出明文。置换密码置换密码(permutation cipher)，又称，又称换位密码换位密码（transposition cipher)：明文的字母保持相同，：明文的字母保持相同，但顺序被打乱了。但顺序被打乱了。代替密码代替密码 简单代替密码（简单代替密码（simple substitution cipher),又又称称单字母密码（单字母密码（monoalphabetic cipher):明文明文的一个字符用相应的一个密文字符代替。的一个字符用相应的一个密文字符代替。多字母密码（多字母密码（ployalphabetic cipher)：明文中
26、明文中的字符映射到密文空间的字符还依赖于它在上的字符映射到密文空间的字符还依赖于它在上下文中的位置。下文中的位置。单字母密码单字母密码 单表代换密码单表代换密码 移位（移位（shift）密码、乘数（）密码、乘数（multiplicative)密码密码 仿射（仿射（affine)密码、多项式（密码、多项式（Polynomial)密码密码 密钥短语（密钥短语（Key Word)密码密码 多表代换密码多表代换密码 维吉尼亚（维吉尼亚（Vigenere)密码密码 博福特（博福特（Beaufort）密码）密码 滚动密钥滚动密钥(running-key)密码密码 弗纳姆弗纳姆(Vernam)密码密码 转子
27、机转子机(rotor machine)多字母代换密码多字母代换密码 可以用矩阵变换方便地描述多可以用矩阵变换方便地描述多字母代换密码字母代换密码，有时又称起为有时又称起为矩阵变换密码矩阵变换密码。Hill cipher Playfair cipher模模q算术算术-i 同余同余：给定任意整数给定任意整数a和和q，以，以q除除a，余数是，余数是r，则可以表示为，则可以表示为a=sq+r,0 r FLSKHU 实际算法为：实际算法为：有有 同时有，同时有，d3(y)=y-3(mod 26)Pxyxxe)26(mod3)(3移位密码分析移位密码分析 给定加密的消息给定加密的消息:PHHW PH DI
28、WHU WKH WRJD SDUWB由于（）加解密算法已知由于（）加解密算法已知（）可能尝试的密钥只有（）可能尝试的密钥只有6个个通过强力攻击得到明文：通过强力攻击得到明文：meet me after the toga party.移位密码很容易受到唯密文攻击。移位密码很容易受到唯密文攻击。乘数密码算法乘数密码算法 加密函数取形式为加密函数取形式为 e(x)=ax(mod 26),aZ/(26)要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1 该算法描述为：该算法描述为：设设P=C=Z/(26)，K=a Z/(26)|gcd(a,26)=1,对对k=a K,定义定义 ek(x
29、)=ax(mod 26)和和dk(y)=a-1(y)(mod 26)x,y Z/(26)例子例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 明文明文 密文密文 cipher=SUFLKX4乘数密码分析乘数密码分析 对于乘数密码，当且仅当对于乘数密码，当且仅当a与互素时，加与互素时，加密变换才是一一映射的，因此密变换才是一一映射的，因此a的选择有的选择有种：种：a=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有可能尝试的密钥只有1个个仿射密码算法仿射密码算法-i 加密函数取形式为加密函数取形式
30、为 e(x)=ax+b(mod 26),a,bZ/(26)要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1 该算法描述为：该算法描述为：设设P=C=Z/(26)K=(a,b)Z/(26)Z/(26)|gcd(a,26)=1,对对k=(a,b)K,定义定义 ek(x)=ax+b(mod 26)和和dk(y)=a-1(y-b)(mod 26)x,y Z/(26)q=26时，可能的密钥是时，可能的密钥是2612=311个个仿射密码算法仿射密码算法-ii 例子，设例子，设k（7，3），注意到），注意到7-1(mod 26)=15,加密函加密函数是数是ek(x)=7x+3,相应的解密函
31、数是相应的解密函数是dk(y)=15(y-3)=15y-19,易见易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x(mod 26)若加密明文：若加密明文：hot，首先转换字母，首先转换字母h,o,t成为数字成为数字7,14,19,然后加密：然后加密：解密：解密：);26(mod6230333191477GXA19147191919623015任意的单表代替密码算法任意的单表代替密码算法 设设P=C=Z/(26)，K是由是由26个符号个符号0，1,.,25的所有可能的所有可能置换组成。任意置换组成。任意K，定义，定义e(x)=(x)=y 且且 d(y)=-
32、1(y)=x,-1是是的逆置换。的逆置换。注：注：1*.置换置换的表示：的表示：2*密钥空间密钥空间K很大，很大，|k|=26!41026，破译者穷举搜索是，破译者穷举搜索是不行的，问题不行的，问题:用什么破译方法较为有效用什么破译方法较为有效?3*移位密码、乘数密码、仿射密码算法都是替换密码的移位密码、乘数密码、仿射密码算法都是替换密码的特例特例0 1 2 3.23 24 250 1 2 3.23 24 25)(单表替换密码的破译单表替换密码的破译通过字母的使用频率破译通过字母的使用频率破译对抗频率分析的办法对抗频率分析的办法 多名或同音代替密码多名或同音代替密码 多表代替密码多表代替密码
33、多字母代替密码多字母代替密码 多名代替密码多名代替密码 与简单代替密码类似，只是映射是一对多的，与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。每个明文字母可以加密成多个密文字母。例如，例如，A可能对应于可能对应于5、13、25 B可能对应于可能对应于7、9、31、42 当对字母的赋值个数与字母出现频率成比例时。当对字母的赋值个数与字母出现频率成比例时。这是因为密文符号的相关分布会近似于平的，这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。可以挫败频率分析。然而，若明文字母的其它统计信息在密文中仍然而，若明文字母的其它统计信息在密文中仍很明显时，那么同音代
34、替密码仍然是可破译的。很明显时，那么同音代替密码仍然是可破译的。多表代替密码多表代替密码 多表代替密码：多表代替密码：是以一系列（两个以上）代换是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。表依此对明文消息的字母进行代换的方法。非周期多表代替密码：非周期多表代替密码：代换表是非周期的无限序列代换表是非周期的无限序列 一次一密密码（一次一密密码（one time padding):对每个明文对每个明文每次采用不同的代换表。每次采用不同的代换表。周期多表代替密码：代换表个数有限，重复使周期多表代替密码：代换表个数有限，重复使用。用。Vigenre cipher(1858)是一种多
35、表移位代替密码是一种多表移位代替密码 设设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=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 O
36、RADIO 密文密文 y=GOOGOCPKTP NTLKQZPKMFVigenre cipher-破译破译依然保留了字符频率某些统计信息依然保留了字符频率某些统计信息重码分析法：间距是密钥长度整数倍的相同子串有相重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。相同的可能性很大。a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222
37、324 25密钥密钥:cryptographycryptographycr明文明文:yourpackagereadyroomathree密文密文:AFSGIOI PG PG滚动密钥密码滚动密钥密码 对于周期代换密码，当密钥的长度对于周期代换密码，当密钥的长度d和明文一和明文一样长时，就成为滚动密钥密码。样长时，就成为滚动密钥密码。VigenreVigenre本人建议密钥与明文一样长本人建议密钥与明文一样长Vernam密码密码19181918年，年，Gillbert VernamGillbert Vernam建议密钥与明文一建议密钥与明文一样长并且没有统计关系的密钥内容样长并且没有统计关系的密钥
38、内容，他采用的，他采用的是二进制数据是二进制数据:加密加密：C Ci i=P=Pi i K Ki i 解密解密 P Pi i=C=Ci i K Ki i 核心：构造和消息一样长的随机密钥核心：构造和消息一样长的随机密钥 多字母代替密码多字母代替密码-PlayfairPlayfair:将明文中的双字母组合作为一个单元对待，并将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。将这些单元转换为密文的双字母组合。5 55 5变换矩阵变换矩阵: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(cip
39、her)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 ba lx lo on lx lo on3)3)同行取右边同行取右边:he:he EC EC4)4)同列同列取下边取下边:dm:dm MT MT5)5)其他其他取交叉取交叉:kt:kt MQ OD MQ OD TR TRPlayfair举例举例以前面的以前面的5 55 5变换矩阵变换矩阵(cipher)(cipher)为例为例
40、 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)balloon ba lx lo on db sp gs ug(1)balloon ba lx lo on db sp gs ug(2)book bo ok rs qg(2)book bo ok rs qg(3)fill fi lx lx ae(3)fill fi lx lx ae sp sp sp spPlayfair密码分析密码分析PlayfairPlayfair有有26X
41、26=67626X26=676种字母对组合种字母对组合字符出现几率一定程度上被均匀化字符出现几率一定程度上被均匀化基于基于字母字母频率的攻击比较困难频率的攻击比较困难依然保留了相当的结构信息依然保留了相当的结构信息Hill密码（密码（1929）基于矩阵的线性变换基于矩阵的线性变换:K K是一个是一个m m*m m矩阵矩阵,在在Z/(26)上可逆上可逆,即存在即存在K K-1-1使得使得:KKKK-1-1=I(=I(在在Z/(26)对每一个对每一个k K,定义定义ek(x)=xK(mod 26)和和 dk(y)=yK-1(mod 26)注：明文与密文都是注：明文与密文都是 m元的向量元的向量（x
42、1,x2,xm);(y1,y2,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵为同余类环。在这个环上的可逆矩阵Amxm,是指行列式是指行列式detAmxm的值的值 Z*/(26),它为它为Z/(26)中全中全体可逆元的集合。体可逆元的集合。Z*/(26)=a Z/(26)|(a,26)=1，Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25Hill密码的例子密码的例子-i例子：当例子：当 m=2时，明文元素时，明文元素x=(x1,x2),密文元素密文元素y=(y1,y2)(y1,y2)=(x1,x2)K 若若K=,可得可得K-1=若对明文若对明文july加密，它
43、分成加密，它分成2个元素（个元素（j,u),(l,y),分别对应分别对应于（于（9,20）,（11,24）,有有（9,20）（9960,72140）mod 26（3,4）且且（11,24）(12172,88168)mod 26（11,22）于是对于是对 july加密的结果为加密的结果为DELW。738117381111231877381173811Hill密码的例子密码的例子-ii为了解密，为了解密，Bob计算计算 且且 因此，得到了正确的明文因此，得到了正确的明文“july”)20,9(1123187)4,3()24,11(1123187)22,11(mod 26mod 26Hill密码求解
44、密码求解K K是一个是一个m m*m m矩阵矩阵,在在Z/(26)上可逆上可逆,即存在即存在K K-1-1使使得得:KKKK-1-1=I(=I(在在Z/(26)对每一个对每一个k K,定义定义:ek(x)=xK(mod 26)dk(y)=yK-1(mod 26)明文求解分为两步明文求解分为两步 (1)求逆求逆K-1-1 (2)矩阵运算求明文矩阵运算求明文 例子：例子：已知已知Hill密码加密函数密码加密函数 Y=E(x)=(X0,X1)mod 26 截获密文为截获密文为(2,5)试求其明文试求其明文.(1)求求K-1 求求k-1有两种方法：列方程以及根据伴随矩阵求解有两种方法：列方程以及根据伴
45、随矩阵求解问题：怎么列方程？问题：怎么列方程？什么是伴随矩阵？什么是伴随矩阵？Hill密码求解密码求解5 76 95 76 9a bc d1 00 1(1)5*a+7*c=1 (2)5*b+7*d=0 (3)6*a+9*c=0 (4)6*b+9*d=1求之:a=3 b=-7/3 c=-2 d=5/3 由于K-1并不是整数，3 -7/3-2 5/3需要将其规范化，方法是乘以mod 26上面的单位矩阵.Hill密码求解密码求解(1.1)列方程列方程 Hill密码求解密码求解3 -7/3-2 5/3K-1=关键是把3消去，而又必须是mod26单位矩阵3X mod 26=1 x=9 3 -7/3-2
46、5/327 00 27mod 26=mod 2681 -63-54 453 1524 19K-1=验证 KK-1=5 76 9=183 208234 2611 00 13 1524 19Mod 26Hill密码求解密码求解(1.2)运用伴随矩阵求解逆矩阵运用伴随矩阵求解逆矩阵K-15 76 9求矩阵k=的逆矩阵 根据公式 K-1=(1/|K|)K*求|k|=(-1)1+1*9+(-1)1+2*6=3求K*K11=(-1)1+1*9=9K12=(-1)1+2*6=-6K21=(-1)1+2*7=-7K22=(-1)2+2*5=59 -6-7 5K0=9 -7-6 5K*=9 -7-6 5K-1=
47、(1/3)Mod 26Hill密码求解密码求解9 -7-6 5K-1=(1/3)Mod 263 -7/3-2 5/3K-1=Mod 2627 0 0 2781 -63-54 45K-1=Mod 263 1524 19K-1=3 1524 19验证 KK-1=5 76 9=183 208234 2611 00 1Mod 26(2)解密矩阵运算解密矩阵运算Hill密码求解密码求解（x1,x2）=(y1,y2)mod 2631524 19=(2,5)mod 26 31524 19=(2*3+5*24,2*15+5*19)mod 26=(126,125)mod 26=(22,21)验算:(x1,x2)
48、K=(22,21)mod 26=(2,5)5 76 9Hill密码分析密码分析 完全隐藏了字符完全隐藏了字符(对对)的频率信息的频率信息 线性变换的安全性很脆弱，易被已知明文攻击击破。线性变换的安全性很脆弱，易被已知明文攻击击破。对于一个对于一个mxmmxm的的hillhill密码，假定有密码，假定有m m个明文个明文-密文对，明密文对，明文和密文的长度都是文和密文的长度都是m.m.可以把明文和密文对记为：可以把明文和密文对记为：P Pj j=(p=(p1j1j,p,p2j2j,.p,.pmjmj)和和C Cj j=(C=(C1j1j,C,C2j2j,C,Cmjmj),),C Cj j=KP=
49、KPj j,1,1 j j m m 定义定义mxmmxm的方阵的方阵X=X=（P Pijij)Y=(C)Y=(Cijij),),得到得到Y=KXY=KX，K=YXK=YX-1-1例子：例子：fridayfriday PQCFKU PQCFKU K(5 17)=(15 16)K(8 3)=(2 5)K(0 24)=(10 20)K(5 17)=(15 16)K(8 3)=(2 5)K(0 24)=(10 20)因此，因此，K38175521615152193817511X3819752161515219K古典密码小结古典密码小结Substitution&permutationSubstituti
50、on&permutation 仿射密码仿射密码?Hill?Hill密码密码?Playfair?Playfair?密码分析密码分析多轮加密多轮加密数据安全基于算法的保密数据安全基于算法的保密现代常规加密技术现代常规加密技术 DES(Data Encryption Standard)Triple DES IDEA Blowfish RC5 CAST-128 AES DES的产生的产生-i 1973年年5月月15日日,NBS开始公开征集标准加密算法开始公开征集标准加密算法,并公并公布了它的设计要求布了它的设计要求:(1)算法必须提供高度的安全性算法必须提供高度的安全性(2)算法必须有详细的说明算法必
