实验六 古典密码与破译.

Presentation on theme: "实验六 古典密码与破译."— Presentation transcript:

1 实验六 古典密码与破译

2 信息加密 为什么要加密 密码分类 保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。
为了将信息传递给己方的接受者，同时又要防止他人（敌方）获取信息内容，必须将传递的信息（明文）加密，变成密文后发送出去，这样，即使敌方得到密文也看不懂，而己方的接受者收到密文后却可以按照预先定好的方法加以解密。 密码分类 古典密码：以字符为基本加密单元 现代密码：以信息块为基本加密单元 本实验主要介绍古典密码的加密与破译原理，同时介绍如何用 Matlab 编程来实现加密、解密和破译过程。

3 加密信息传递过程 加密器 发送方 明文（信息） 密文 普通信道 发送 敌方截获 破译 解密器 明文（信息） 密文 接收方

4 Hill2 密码的加密过程 Hill2 密码中所用的数学手段是 矩阵运算 加密过程：
① 将 26 个字母 与 0 到 25 之间的整数建立一一对应关系，称为字母的 表值，然后根据明文字母的表值，将明文信息用数字表示 设通讯双方所给出的 26 个字母的表值如下： A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 注：这里假定明文中只使用 26 个大写字母

5 Hill2 密码的加密过程 ② 选择一个 二阶可逆整数方阵 A，称为Hill2密码的 加密矩阵，它是加密体制的 “密钥”，是加密的关键，仅通讯双方掌握 ③ 将明文字母分组。 Hill2 使用的是二阶矩阵，所以将明文字母每 2 个一组（可以推广至Hilln密码）。查出每个字母的表值，这样，每组字母构成一个二维列向量  若最后仅剩一个字母，则补充一个没有实际意义的哑字母（哑元），这样使得每组都有 2 个字母 ④ 令  = A ，由  的两个分量反查字母表值表，得到相应的两个字母，即为密文字母

6 Hill2 加密举例 解: 例： 设明文为“HDSDSXX”（华东师大数学系），试给出这段明文的 Hill2 密文。其中加密矩阵为
将明文字母分组： HD SD SX XX 最后的一个字母 X 为哑字母，无实际意义。 查表得每组字母的表值，得到 4 个二维列向量： A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

7 Hill2 加密举例 将上述 4 个二维向量左乘密钥矩阵 A 得： 作模 26 运算，将所有的数都化为 0 到 25 之间的整数：

8 Hill2 加密举例 HDSDSXX PLALOTTT PL AL OT TT 反查字母表值得每个向量对应的字母组为： Hill2 加密 A
B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

9 Hill2 加密过程 分组 明文字母 一组向量 查表值 加密矩阵 左乘 模运算 密文 一组新的向量 反查表值 问题：怎样解密？

10 Hill2 密码解密

11 Hill2 解密过程 解密：加密的逆过程，将加密过程逆转回去即可 例：怎么得到密文 “ PLALOTTT ” 的原文
上面的向量是由 经过模 26 运算得来的，现在的问题是怎样逆转回去？ 在模运算下解方程组： A = 

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 模 m 可逆 问题：是否 Zm 中所有的数都存在模 m 倒数？ Hill2 密码的加密矩阵必须满足上述条件。 m=26
a 存在唯一的模 m 倒数 a 与 m 无公共素数因子 命题：定义在集合 Zm 上的 n 阶方阵 A 模 m 可逆的充要条件是：m 和 det(A) 无公共素数因子，即 m 与 det(A) 互素。 Hill2 密码的加密矩阵必须满足上述条件。 m=26 m 的素数因子只有 2 和 13 定义在 Z26上的方阵 A 模 26 可逆的充要条件是： det(A) 不能被 2 和 13 整除

14 模 26 可逆 Z26 中具有模 26 倒数的整数及其模 26 倒数表 a 1 3 5 7 9 11 15 17 19 21 23 25 a-1 思考：如何用 Matlab 编程来找出所有模 m 倒数的整数及其模 m 倒数？（穷举法）

15 Hill2 解密过程 ？ 在模运算下解方程组： A =  问题：如何计算 ？

16 模 m 逆矩阵的计算 A*为 A 的伴随矩阵 设 B=k A*为 A 的 模 26 逆，其中 k 为待定系数
本计算方法可推广到求矩阵 A 的 模 m 逆矩阵

17 Hill2 解密过程 设加密矩阵

18 ？ 用 B 左乘密文对应的向量得： 模 26 运算后得： 查表后得明文分别为： HD SD SX XX

19 Hill2 加密过程总结 ① 通讯双方确定加密矩阵 ( 密钥) 和字母的表值对应表 ② 将明文字母分组，通过查表列出每组字母对应的向量
若明文只含奇数个字母，则补充一个哑元 ③ 令  = A mod(m) ，由  的分量反查字母表值表， 得到相应的密文字母

20 Hill2 解密过程总结 ① 将密文字母分组，通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 m 逆矩阵 B
③ 令  = B mod(m) ，由  的分量反查字母表值表， 得到相应的明文字母

21 Hill2 解密举例 甲方收到乙方（己方）的一个密文信息，内容为：
WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 按照甲方与乙方的约定，他们之间采用 Hill2密码，密钥 为 ，字母表值见下表，问这段密文的原文 是什么？ A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

22 Hill2 解密举例 ① 将密文字母分组，通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 26 逆矩阵
③ 用 B 左乘每组密文字母组成的向量，然后再反查字母表值表，得到相应的明文字母

23 Hill2 解密举例 序号 分组 密文 表值 明文 1 W K 23 11 7 21 G U 2 V A 22 4 9 D I 3 C P
16 14 N E 5 13 M O 15 6 X 24 19 8 S H 序号 分组 密文 表值 明文 7 G W 23 9 25 I Y 8 Z U R 21 18 6 F 10 O Q 15 17 11 A 1 5 E 12 B 2 J

24 Hill2 解密举例 序号 分组 密文 表值 明文 13 L O 12 15 2 5 B E 14 H D 8 4 10 N J K C
11 3 9 1 I A 16 M 17 F 6 18 W 23 25 Y 序号 分组 密文 表值 明文 19 W C 23 3 21 1 U A 20 V L 22 12 14 4 N D E M 5 13 I 9

25 WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC
Hill2 解密举例 WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 密文 GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA A 原文 即：“古典密码是以字符为基本加密单元的密码”

26 相关Matlab函数介绍 double('字符串')：字符  ASCII码 char(数)：ASCII码  字符
length、size mod、det、inv reshape double('字符串')：字符  ASCII码 char(数)：ASCII码  字符 gcd(m,n)：求最大公约数

27 上机作业 要求写实验报告 教材 P 124：练习 1、2、3 上机要求 每个 M文件的第一行为：% 机号-学号-姓名
将所编写的程序分别命名为 hw61.m, hw62.m, hw63.m 将所有 M 文件作为附件，发给 邮件主题为：机号-学号-姓名；其中机号为 两位数 三个字段之间用英文状态下的减号链接 每个 M文件的第一行为：% 机号-学号-姓名

28 Hill2 密码破译

29 Hill2 密码破译举例 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 我方截获一段密文
经分析该密文是用 Hill2密码 加密，且密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )，问能否破译这段密文？ 破译这段密文的关键是找到“密钥”和字母对应的表值 猜测密文是由26个字母组成，即 m=26， 经破译部门通过大量的统计分析和语言分析确定表值 A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

30 P C Hill2 密码破译举例 密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )
查 字 母 表 值 P C

31 Hill2 密码破译举例 P、C 模26可逆 可唯一确定加密矩阵 A 注：这里的运算都是在模运算意义下进行

32 Hill2 密码破译举例 得到加密矩阵的 模26逆矩阵 后，根据前面的解密方法即可得密文的原文
HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ON