• 1. 实验六 古典密码与破译数学实验
  • 2. 保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。 为了将信息传递给己方的接受者,同时又要防止他人(特别是敌人)知道信息的内容,必须将要传递的信息(明文)加密,变成密文后发送出去,这样,即使敌方得到密文也看不懂,而己方的接受者收到密文后却可以按照预先定好的方法加以解密。问题背景和实验目的
  • 3. 密码可分为古典密码和现代密码 本实验主要介绍古典密码的加密与破译原理,同时介绍如何用 Matlab 编程来实现加密、解密和破译过程。问题背景和实验目的 古典密码:以字符为基本加密单元; 现代密码:以信息块为基本加密单元。
  • 4. 加密信息传递过程明文(信息)加密器密文密文明文(信息)解密器普通信道发送敌方截获 破译发送方接收方
  • 5. Hill2 密码的加密过程 Hill2 密码中所用的数学手段是 矩阵运算。 加密过程:① 将汉语拼音的 26 个字母 与 0 到 25 之间的整数建立一一对应关系,称为字母的 表值,然后根据明文字母的表值,将明文信息用数字表示。ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250设通讯双方所给出的 26 个字母的表值如下:注:这里假定明文中只使用 26 个大写字母
  • 6. Hill2 密码的加密过程② 选择一个 二阶可逆整数方阵 A,称为Hill2密码的 加密矩阵,它是加密体制的 “密钥”,是加密的关键,仅通讯双方掌握。③ 将明文字母分组。 Hill2 使用的是二阶矩阵,所以将明文字母每 2 个一组(可以推广至Hilln密码)。查出每个字母的表值,这样,每组字母构成一个二维列向量  。若最后仅剩一个字母,则补充一个没有实际意义的哑字母(哑元)。这样使得每组都有 2 个字母,④ 令  = A ,由  的两个分量反查字母表值表,得到相应的两个字母,即为密文字母。
  • 7. Hill2 加密举例例: 设明文为“HDSDSXX”(华东师大数学系),试给出这段明文的 Hill2 密文。其中加密矩阵为 将明文字母分组: HD SD SX XX 最后的一个字母 X 为哑字母,无实际意义。解:ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250查表得每组字母的表值,得到 4 个二维列向量:
  • 8. 将上述 4 个二维向量左乘密钥矩阵 A 得:作模 26 运算,将所有的数都化为 0 到 25 之间的整数:Hill2 加密举例
  • 9. 反查字母表值得每个向量对应的字母组为:HDSDSXXPLALOTTTHill2 加密Hill2 加密举例ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250PL AL OT TT
  • 10. 问题:怎样解密?明文字母查表值分组一组向量加密矩阵左乘一组新的向量反查表值密文Hill2 加密过程模运算
  • 11. 先查出密文字母 “ PL AL OT TT ” 所对应的向量:在模运算下解方程组: A =  解密:加密的逆过程,将加密过程逆转回去即可。Hill2 解密过程上面的向量是由 经过模 26 运算得来的,现在的问题是怎样逆转回去?例:怎么得到密文 “ PLALOTTT ” 的原文
  • 12. 模 m 可逆记定义 1:设 A 为定义在集合 Zm 上的 n 阶方阵,若存在一个定义在 Zm 上的方阵 B,使得 则称 A 模 m 可逆, B 为 A 的 模 m 逆矩阵,记为定义 2:设 a  Zm ,若存在 b  Zm 使得 ab=1 (mod m) ,则称 b 为 a 的 模 m 倒数 或乘法逆,记作 b = a-1 (mod m) 。注: a , b 都是 Zm 中的数
  • 13. 命题:定义在集合 Zm 上的 n 阶方阵 A 模 m 可逆的充要条件是:m 和 det(A) 无公共素数因子,即 m 与 det(A) 互素。Hill2 密码的加密矩阵必须满足上述条件。m=26m 的素数因子只有 2 和 13 定义在 Z26上的方阵 A 模 26 可逆的充要条件是:模 m 可逆det(A) 不能被 2 和 13 整除 问题:是否 Zm 中所有的数都存在模 m 倒数?a 存在唯一的模 m 倒数a 与 m 无公共素数因子
  • 14. Z26 中具有模 26 倒数的整数及其模 26 倒数表a1357911151719212325a-11921153197231151725m=26 时的 Matlab 程序见教材第 121 页 fuluA.m 可以用来判断一个 2 阶矩阵在模 26 运算下是否可逆,并在可逆的前提下给出其模 26 逆矩阵。模 26 可逆 思考:如何用 Matlab 编程来找出所有模 m 倒数的整数及其模 m 倒数?
  • 15. 在模运算下解方程组: A = Hill2 解密过程? 问题:如何计算 ?
  • 16. 模 m 逆矩阵的计算 设 B=k A*为 A 的 模 26 逆,其中 k 为待定系数 A*为 A 的伴随矩阵本计算方法可推广到求矩阵 A 的 模 m 逆矩阵
  • 17. Hill2 解密过程 设加密矩阵
  • 18. 用 B 左乘密文对应的向量得: 模 26 运算后得: 查表后得明文分别为: HD SD SX XXMatlab 的 Hill2 加密程序见 附录 B,相应解密程序见 附录 C。?
  • 19. Hill2 加密过程总结① 通讯双方确定加密矩阵 ( 密钥) 和字母的表值对应表② 将明文字母分组,通过查表列出每组字母对应的向量 ③ 令  = A mod(m) ,由  的分量反查字母表值表, 得到相应的密文字母若明文只含奇数个字母,则补充一个哑元
  • 20. Hill2 解密过程总结① 将密文字母分组,通过查表列出每组字母对应的向量② 求出加密矩阵 A 的 模 m 逆矩阵 B③ 令  = B mod(m) ,由  的分量反查字母表值表, 得到相应的明文字母
  • 21. 甲方收到乙方(己方)的一个密文信息,内容为:Hill2 解密举例WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方与乙方的约定,他们之间采用 Hill2密码,密钥 为 ,字母表值见下表,问这段密文的原文 是什么?ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250
  • 22. Hill2 解密举例① 将密文字母分组,通过查表列出每组字母对应的向量② 求出加密矩阵 A 的 模 26 逆矩阵③ 用 B 左乘每组密文字母组成的向量,然后再反查字母表值表,得到相应的明文字母
  • 23. 序号分组 密文密文 表值明文 表值分组 明文1W K23 117 21G U2V A22 14 9D I3C P3 161 14A N4E A5 113 9M I5O C15 313 1M A6I X9 2419 8S H序号分组 密文密文 表值明文 表值分组 明文7G W7 239 25I Y8I Z9 09 0I Z9U R21 189 6I F10O Q15 1721 23U W11W A23 15 9E I12B A2 110 9J IHill2 解密举例
  • 24. 序号分组 密文密文 表值明文 表值分组 明文13L O12 152 5B E14H D8 414 10N J15K C11 39 1I A16E A5 113 9M I17F C6 34 1D A18L W12 2314 25N Y序号分组 密文密文 表值明文 表值分组 明文19W C23 321 1U A20V L22 1214 4N D21E M5 135 13E M22I M9 139 13I M23C C3 31 1A AHill2 解密举例
  • 25. 即:“古典密码是以字符为基本加密单元的密码”GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA AWKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC原文Hill2 解密举例密文
  • 26. ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250经分析该密文是用 Hill2密码 加密,且密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O ),问能否破译这段密文?Hill2 密码破译举例MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP我方截获一段密文 猜测密文是由26个字母组成,即 m=26, 经破译部门通过大量的统计分析和语言分析确定表值 破译这段密文的关键是找到“密钥”和字母对应的表值
  • 27. 密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )Hill2 密码破译举例查 字 母 表 值PC
  • 28. P、C 模26可逆可唯一确定加密矩阵 AHill2 密码破译举例注:这里的运算都是在模运算意义下进行
  • 29. HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ON相应的 Matlab 程序见附录 D 得到加密矩阵的 模26逆矩阵 后,根据前面的解密方法即可得密文的原文Hill2 密码破译举例
  • 30. 相关Matlab函数介绍 inputA=input(提示信息) 其中 提示信息 为字符串 该命令要求用户输入 A 的值,可以是数、矩阵或字符串 数可以直接输入 矩阵需要加 [] 字符串需要加单引号>> A=input('Please input A: ') sizesize(a)
  • 31. 相关Matlab函数介绍 lengthlength(a) 如果 a 是向量,则返回其长度; 如果 a 是矩阵,则返回行数与列数中最大的一个。 modmod(m,n) 求余,返回 m 被 n 整除后的余数,符号与 n 相同; 另外一个求余函数是 rem gcd :求最大公约数gcd(m,n)
  • 32. 相关Matlab函数介绍 det :计算行列式det(A) inv :计算逆矩阵inv(A) reshape :将矩阵元素按列方向进行重组reshape(A,m,n) 将 A 排 m 行,n 列的矩阵,要求 A 的元素个数 =m*n
  • 33. 相关Matlab函数介绍 doubledouble(str) 当 str 是字符串时,返回所有字符的 ASCII 码 charchar(a) 当 a 是整数时,返回 ASCII 码等于 a 的字符
  • 34. 数据输出 fprintf fid 为文件句柄,若缺省,则将变量的值输出到屏幕上 format 用来指定数据输出时采用的格式,常见的有 %d ( 输出一个整数类型的数据 ) %e ( 采用科学计算形式输出一个实数 ) %f ( 采用浮点数形式输出一个实数) %g ( 由系统自动选取上述两种格式之一) %s ( 输出字符串) format 中还可以使用一些特殊格式,如:\n ( 换行 ) \t ( 制表符 ) \b ( 退格 ) \\ ( 反斜杆 ) %% ( 百分号 ) fprintf(fid,format,variables)按指定的格式将变量的值输出到指定的文件 fprintf :格式化输出
  • 35. 数据输出 fprintf>> a='Hello'; b=2.4; c=100*pi; >> fprintf('a=%s,b=%f,c=%e\n',a,b,c)例: format 中的输出格式要与输出变量一一对应 可以没有输出变量>> fprintf(' Today is Monday\n')例:
  • 36. 教材 P 124:练习 1、2、3上机作业 写入实验报告册。 请在上机前(课后)将报告册中的问题背景与目的、实验原理和数学模型、实验所用软件及版本、主要内容、实验程序(参考附录)填写好,上机时验证你修改的实验程序,记录异常情况,完成实验报告,在上机结束后递交实验报告。 练习 4、5、6 作为思考题,不必写入实验报告