实验六-古典密码与破译课件.ppt

1、1实验六实验六古典密码与破译古典密码与破译谢谢观赏2019-8-232n 为什么要加密为什么要加密l 保密通讯无论在军事、政治、经济还是日常生活中都起着保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。非常重要的作用。l 为了将信息传递给己方的接受者，同时又要防止他人（敌为了将信息传递给己方的接受者，同时又要防止他人（敌方）获取信息内容，必须将传递的信息（方）获取信息内容，必须将传递的信息（明文明文）加密，变成）加密，变成密文密文后发送出去，这样，即使敌方得到密文也看不懂，而己后发送出去，这样，即使敌方得到密文也看不懂，而己方的接受者收到密文后却可以按照预先定好的方法加以解密。

2、方的接受者收到密文后却可以按照预先定好的方法加以解密。信息加密信息加密n 密码分类密码分类l 古典密码：古典密码：以字符为基本加密单元以字符为基本加密单元l 现代密码：现代密码：以信息块为基本加密单元以信息块为基本加密单元本实验主要介绍本实验主要介绍古典密码古典密码的加密与破译原理，同时介绍的加密与破译原理，同时介绍如何用如何用 Matlab 编程来实现加密、解密和破译过程。编程来实现加密、解密和破译过程。谢谢观赏2019-8-233加密信息传递过程加密信息传递过程明文明文（信息）（信息）加密器加密器密文密文密文密文明文明文（信息）（信息）解密器解密器普普通通信信道道发发送送敌方截获敌方截获破

3、译破译发送方发送方接收方接收方谢谢观赏2019-8-234Hill2 密码的加密过程密码的加密过程l Hill2 密码中所用的数学手段是密码中所用的数学手段是 矩阵运算矩阵运算l 加密过程：加密过程：将将 26 个字母个字母 与与 0 到到 25 之间的整数建立一一对应关系，之间的整数建立一一对应关系，称为字母的称为字母的 表值表值，然后根据明文字母的表值，然后根据明文字母的表值，将明文信将明文信息用数字表示息用数字表示ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250设通讯双方所给出的设通讯双方所给出的 2

4、6 个字母的表值如下：个字母的表值如下：注：这里假定明文中只使用注：这里假定明文中只使用 26 个大写字母个大写字母谢谢观赏2019-8-235Hill2 密码的加密过程密码的加密过程 选择一个选择一个 二阶可逆整数方阵二阶可逆整数方阵 A，称为，称为Hill2密码的密码的 加加密矩阵密矩阵，它是加密体制的，它是加密体制的“密钥密钥”，是加密的关键，是加密的关键，仅仅通讯双方掌握通讯双方掌握 将明文字母分组。将明文字母分组。Hill2 使用的是二阶矩阵，所以将明使用的是二阶矩阵，所以将明文字母每文字母每 2 个一组（可以推广至个一组（可以推广至Hilln密码）。查出每个字密码）。查出每个字母的

5、表值，这样，每组字母构成一个二维列矢量母的表值，这样，每组字母构成一个二维列矢量 若最后仅剩一个字母，则补充一个若最后仅剩一个字母，则补充一个没有实际意义的哑字母没有实际意义的哑字母（哑元哑元），这样使得每组都有），这样使得每组都有 2 个字母个字母 令令 =A ，由，由 的两个分量反查字母表值表，得到的两个分量反查字母表值表，得到相应的两个字母，即为相应的两个字母，即为密文字母密文字母谢谢观赏2019-8-236Hill2 加密举例加密举例例：例：设明文为设明文为“HDSDSXX”（华东师大数学系），试（华东师大数学系），试给出这段明文的给出这段明文的 Hill2 密文密文。其中加密矩阵为。

6、其中加密矩阵为 将明文字母分组：将明文字母分组：HD SD SX XX最后的一个字母最后的一个字母 X 为哑字母，无实际意义。为哑字母，无实际意义。解解:,8191924,442424 A B C D E F G HIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250查表得每组字母的表值，得到查表得每组字母的表值，得到 4 个二维列矢量：个二维列矢量：1203A 谢谢观赏2019-8-237将上述将上述 4 个二维矢量个二维矢量左乘密钥矩阵左乘密钥矩阵 A 得：得：16276772,12127272作作模模 26 运算运算，将

7、所有的数都化为，将所有的数都化为 0 到到 25 之间的整数：之间的整数：1627(mod 26),(mod 26)12126772(mod 26)1611212152020,(mod 26).20 7272Hill2 加密举例加密举例谢谢观赏2019-8-238反查字母表值得每个矢量对应的字母组为：反查字母表值得每个矢量对应的字母组为：HDSDSXXPLALOTTTHill2 加密加密Hill2 加密举例加密举例A B C D E F G HIJKLM12345678910111213NOPQRSTUVWXYZ14151617181920212223242501611520,12122020

8、PL AL OT TT谢谢观赏2019-8-239问题：问题：怎样解密？怎样解密？明文字母明文字母查表值查表值分组分组一组矢量一组矢量加加密密矩矩阵阵左左乘乘一组新的矢量一组新的矢量反查表值反查表值密文密文Hill2 加密过程加密过程模运算模运算谢谢观赏2019-8-2310Hill2 密码解密密码解密谢谢观赏2019-8-2311先查出密文字母先查出密文字母“PL AL OT TT”所对应的矢量：所对应的矢量：在模运算下解方程组：在模运算下解方程组：A =1611520,12122020n 解密：加密的逆过程，解密：加密的逆过程，将加密过程逆转回去即可将加密过程逆转回去即可Hill2 解密过

9、程解密过程上面的矢量是由上面的矢量是由 经过经过模模 26 运算运算得来的，现在的问题是怎样逆转回去？得来的，现在的问题是怎样逆转回去？16276772,12127272例：例：怎么得到密文怎么得到密文“PLALOTTT”的原文的原文 谢谢观赏2019-8-2312模模 m 可逆可逆0,1,2,.,1mZm记记定义定义 1：设设 A 为定义在集合为定义在集合 Zm 上的上的 n 阶方阵，若存在一个定阶方阵，若存在一个定义在义在 Zm 上的方阵上的方阵 B，使得使得 则称则称 A 模模 m 可逆可逆，B 为为 A 的的 模模 m 逆矩阵逆矩阵，记为，记为(mod)ABBAEm1(mod)BAm

10、定义定义 2：设设 a Zm，若存在，若存在 b Zm 使得使得 ab=1(mod m)，则，则称称 b 为为 a 的的 模模 m 倒数倒数 或乘法逆，记作或乘法逆，记作 b=a-1(mod m)。注注:a,b 都是都是 Zm 中的数中的数谢谢观赏2019-8-2313命题：命题：定义在集合定义在集合 Zm 上的上的 n 阶方阵阶方阵 A 模模 m 可逆的充要条可逆的充要条件是：件是：m 和和 det(A)无公共素数因子无公共素数因子，即，即 m 与与 det(A)互素。互素。Hill2 密码的加密矩阵必须满足上述条件。密码的加密矩阵必须满足上述条件。m=26m 的素数因子只有的素数因子只有

11、2 和和 13l 定义在定义在 Z26上的方阵上的方阵 A 模模 26 可逆可逆的充要条件是：的充要条件是：模模 m 可逆可逆det(A)不能被不能被 2 和和 13 整除整除n 问题：问题：是否是否 Zm 中所有的数都存在中所有的数都存在模模 m 倒数倒数？a 存在唯一的模存在唯一的模 m 倒数倒数a 与与 m 无公共素数因子无公共素数因子谢谢观赏2019-8-2314l Z26 中具有模中具有模 26 倒数的整数及其模倒数的整数及其模 26 倒数表倒数表a1357911151719212325a-11921153197231151725模模 26 可逆可逆l 思考：思考：如何用如何用 Ma

12、tlab 编程来找出所有模编程来找出所有模 m 倒数倒数的整数及其模的整数及其模 m 倒数？（穷举法）倒数？（穷举法）谢谢观赏2019-8-2315 ,1611520,12122020 在模运算下解方程组：在模运算下解方程组：A =1(mo 2d)6A ,8191924,442424 Hill2 解密过程解密过程？(mod26)问题：问题：如何计算如何计算？1(mo)6d2A 谢谢观赏2019-8-2316模模 m 逆矩阵逆矩阵的的计算计算11|AAA l 设设 B=k A*为为 A 的的 模模 26 逆逆，其中，其中 k 为待定系数为待定系数|BAkAE (mo 26d)BAE|1(mo6d

13、)2kA 1|(mod)26kA A*为为 A 的伴随矩阵的伴随矩阵本计算方法可推广到求矩阵本计算方法可推广到求矩阵 A 的的 模模 m 逆矩阵逆矩阵谢谢观赏2019-8-2317Hill2 解密过程解密过程l 设加密矩阵设加密矩阵1203A 32|3,01AA 1132(mod)(m262626od)(mod)013A 1809 1(mo 2d)6BA 329(mod)0126 谢谢观赏2019-8-2318 ,16112197,12108121081517520180,2018020180BBBBl 用用 B 左乘密文对应的矢量得：左乘密文对应的矢量得：l 模模 26 运算后得：运算后得：

14、,8191924,442424 l 查表后得明文分别为：查表后得明文分别为：HD SD SX XX ,1611520,12122020 ,8191924,442424？谢谢观赏2019-8-2319Hill2 加密过程总结加密过程总结 通讯双方确定通讯双方确定加密矩阵加密矩阵(密钥密钥)和字母的和字母的表值对应表表值对应表 将将明文字母明文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的矢量矢量 令令 =A mod(m)，由，由 的分量反查字母表值表，的分量反查字母表值表，得到相应的得到相应的密文字母密文字母若明文只含奇数个字母，则补充一个若明文只含奇数个字母，则补充一个哑

15、元哑元谢谢观赏2019-8-2320Hill2 解密过程总结解密过程总结 将将密文字母密文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的矢量矢量 求出加密矩阵求出加密矩阵 A 的的 模模 m 逆矩阵逆矩阵 B 令令 =B mod(m)，由，由 的分量反查字母表值表，的分量反查字母表值表，得到相应的得到相应的明文字母明文字母谢谢观赏2019-8-2321甲方收到乙方（己方）的一个密文信息，内容为：甲方收到乙方（己方）的一个密文信息，内容为：Hill2 解密举例解密举例WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方与乙方的

16、约定，他们之间采用按照甲方与乙方的约定，他们之间采用 Hill2密码密码，密钥，密钥为为 ，字母表值见下表，问这段密文的原文，字母表值见下表，问这段密文的原文是什么？是什么？1203A ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250谢谢观赏2019-8-2322Hill2 解密举例解密举例 将将密文字母密文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的矢量矢量 求出加密矩阵求出加密矩阵 A 的的 模模 26 逆矩阵逆矩阵 用用 B 左乘每组密文字母组成的矢量，然后再反查字母左乘每组密

17、文字母组成的矢量，然后再反查字母表值表，得到相应的表值表，得到相应的明文字母明文字母1809B 谢谢观赏2019-8-2323序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文1W K2311721GU2VA22149DI3CP316114AN4EA51139MI5OC153131MA6IX924198SH序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文7GW723925IY8IZ9090IZ9UR211896IF10OQ15172123UW11WA23159EI12BA21109JIHill2 解密举例解密举例谢谢观赏2019-8-2324序序号

18、号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文13LO121525BE14HD841410NJ15KC11391IA16EA51139MI17FC6341DA18LW12231425NY序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文19WC233211UA20VL2212144ND21EM513513EM22IM913913IM23CC3311AAHill2 解密举例解密举例谢谢观赏2019-8-2325即：即：“古典密码是以古典密码是以字符为基本加密单元的密码字符为基本加密单元的密码”GU DIAN MI MA SHI YI ZI FU WEI

19、JI BEN JIA MI DAN YUAN DE MI MA AWKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC原文原文Hill2 解密举例解密举例密文密文谢谢观赏2019-8-2326相关相关Matlab函数介绍函数介绍length、sizemod、det、invreshapegcd(m,n)：求最大公约数：求最大公约数double(字符串字符串)：字符字符 ASCII码码char(数数)：ASCII码码 字符字符谢谢观赏2019-8-2327l 教材教材 P 124：练习练习 1、2、3上机作业上机作业要求写实验报告要求写实验报告l 将所编写的

20、程序分别命名为将所编写的程序分别命名为 hw61.m,hw62.m,hw63.ml 将所有将所有 M 文件作为附件，发给文件作为附件，发给 mhjssystem.maill 邮件主题为：邮件主题为：机号机号-学号学号-姓名；姓名；其中机号为其中机号为 两位数两位数l 三个字段之间用英文状态下的减号链接三个字段之间用英文状态下的减号链接q 上机要求上机要求每个每个 M文件的第一行为：文件的第一行为：%机号机号-学号学号-姓名姓名谢谢观赏2019-8-2328Hill2 密码破译密码破译谢谢观赏2019-8-2329ABCDEFGHIJKLM12345678910111213NOPQRSTUVWX

21、YZ1415161718192021222324250经分析该密文是用经分析该密文是用 Hill2密码密码 加密，且密文加密，且密文(U,C)和和(R,S)分别对应明分别对应明文文(T,A)和和(C,O)，问能否破译这段密文？问能否破译这段密文？Hill2 密码破译举例密码破译举例MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP我方截获一段密文我方截获一段密文l 猜测密文是由猜测密文是由26个字母组成，即个字母组成，即 m=26，经破译部门通过大量的统计分析和语言分析确定表值经破译部门通过大量的统计分析和语言分析确定表值l 破译这段密文的关键是找到破译这段密文的关键是找到“密钥

22、密钥”和和字母对应的表值字母对应的表值谢谢观赏2019-8-2330 ,URCSTCAO 2118319203,115 A l 密文密文(U,C)和和(R,S)分别对应明文分别对应明文(T,A)和和(C,O)Hill2 密码破译举例密码破译举例查查 字字 母母 表表 值值A 2118 3 20319115A PCPAC 谢谢观赏2019-8-2331 2118203,319115PC PAC 1A PC|(m7od26)P|(mo161d2)C P、C 模模26可逆可逆可唯一确定加密矩阵可唯一确定加密矩阵 A11AC P 1126262(mod)(m(moodd6)APC Hill2 密码破译举例密码破译举例注：这里的运注：这里的运算都是在模运算都是在模运算意义下进行算意义下进行谢谢观赏2019-8-2332HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ONl 得到加密矩阵的得到加密矩阵的 模模26逆矩阵逆矩阵 后，根据前面的解密方法即后，根据前面的解密方法即可得密文的原文可得密文的原文Hill2 密码破译举例密码破译举例谢谢观赏2019-8-23