《实验十古典密码与破译》由会员分享，可在线阅读，更多相关《实验十古典密码与破译（43页珍藏版）》请在金锄头文库上搜索。
1、实验十 密码加密，解密与破译 数学实验 q 保密通讯无论在军事、政治、经济还是日常 生活中都起着非常重要的作用。 q 为了将信息传递给己方的接受者，同时又要防 止他人（特别是敌人）知道信息的内容，必须将 要传递的信息（明文）加密，变成密文后发送出 去，这样，即使敌方得到密文也看不懂，而己方 的接受者收到密文后却可以按照预先定好的方法 加以解密。 问题背景和实验目的 明文 密文明文 加密 解密 q 密码可分为古典密码和现代密码 q 本实验主要介绍古典密码的加密与破译原理，同 时介绍如何用 Matlab 编程来实现加密、解密和破 译过程。 问题背景和实验目的 u 古典密码：以字符为基本加密单元；
2、u 现代密码：以信息块为基本加密单元。 加密信息传递过程 明文（信息） 加密器 密文 密文 明文（信息） 解密器 普 通 信 道 发 送 敌方截获 破译 发送方 接收方 Hill2 密码的加密过程 q Hill2 密码中所用的数学手段是 矩阵运算。 q 加密过程： 将汉语拼音的 26 个字母 与 0 到 25 之间的整数建 立一一对应关系，称为字母的 表值，然后根据明文字 母的表值，将明文信息用数字表示。 ABCDEFGHIJKLM 12345678910 11 12 13 NOPQRSTUVW XYZ 14 15 16 17 18 19 20 21 22 23 24 25 0 设通讯双方所给
3、出的 26 个字母的表值如下： 注：这里假定明文中只使用 26 个大写字母 Hill2 密码的加密过程 选择一个 二阶可逆整数方阵 A，称为Hill2密码的 加 密矩阵，它是加密体制的 “密钥”，是加密的关键，仅通 讯双方掌握。 将明文字母分组。 Hill2 使用的是二阶矩阵，所以将明 文字母每 2 个一组（可以推广至Hill n密码）。查出每个字 母的表值，这样，每组字母构成一个二维列向量 。 若最后仅剩一个字母，则补充一个没有实际意义的哑字母 （哑元）。这样使得每组都有 2 个字母， 令 = A ，由 的两个分量反查字母表值表，得到 相应的两个字母，即为密文字母。 Hill2 加密举例 例
4、： 设明文为“HRXYSJX”（华锐学院数计系）， 试给出这段明文的 Hill2 密文。 将明文字母分组： HR XY SJ XX 最后的一个字母 X 为哑字母，无实际意义。 解: A B C D E F G H IJKLM 1 2 3 4 5 6 7 89 10111213 NOPQRSTUVWXYZ 1415161718192021222324250 查表得每组字母的表值，得到 4 个二维列向量： 将上述 4 个二维向量左乘密钥矩阵 A 得： 作模 26 运算，将所有的数都化为 0 到 25 之间的整数： Hill2 加密举例 反查字母表值得每个向量对应的字母组为： HRXYSJXRBVW
5、MDTT Hill2 加密 Hill2 加密举例 A B C D E F G H IJKLM 1 2 3 4 5 6 7 89 10111213 NOPQRSTUVW XYZ 1415161718192021222324250 RB VW MD TT 问题：怎样解密？ 明文字母 查表值 分组 一组向量 加 密 矩 阵 左 乘 一组新的向量 反查表值 密文 Hill2 加密过程 模运算 先查出密文字母 “RB VW MD TT” 所对应的向量： 在模运算下解方程组： A = q 解密：加密的逆过程，将加密过程逆转回去即可。 Hill2 解密过程 例：怎么得到密文 “RBVWMDTT ” 的原文?
6、 上面的向量是由 经过模 26 运算 得来的，现在的问题是怎样逆转回去？ 模 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 中的数 命题：定义在集合 Zm 上的 n 阶方阵 A 模 m 可逆的充要条 件是：m 和 det(A) 无公共素数因子，即 m 与 det(A)
7、 互素。 Hill2 密码的加密矩阵必须满足上述条件。 m=26m 的素数因子只有 2 和 13 u 定义在 Z26上的方阵 A 模 26 可逆的充要条件是： 模 m 可逆 det(A) 不能被 2 和 13 整除 u 问题：是否 Zm 中所有的数都存在模 m 倒数？ a 存在唯一的模 m 倒数a 与 m 无公共素数因子 u Z26 中具有模 26 倒数的整数及其模 26 倒数表2 a1357911 15 17 19 21 23 25 a-11921 15319723 11517 25 m=26 时的 Matlab 程序见教材第 121 页 附录1程序 可以用来判断一个 2 阶矩阵在模 26
8、运算 下是否可逆，并在可逆的前提下给出其模 26 逆矩阵 。 模 26 可逆 u 思考：如何用 Matlab 编程来找出所有模 m 倒 数的整数及其模 m 倒数？ nm=26; nfor a=1:m n for i=1:m n if mod(a*i,m)=1 n fprintf(%d 的模%d倒数是: %dn,a,m,i);break; n end; n end; nend 在模运算下解方程组： A = Hill2 解密过程 ？ u 问题：如何计算 ？ 模 m 逆矩阵的计算 l 设 B=k A*为 A 的 模 26 逆，其中 k 为待定系数 A*为 A 的伴随矩阵 本计算方法可推广到求矩阵 A
9、 的 模 m 逆矩阵 Hill2 解密过程 l 设加密矩阵 l 用 B 左乘密文对应的向量得： l 模 26 运算后得： l 查表后得明文分别为： HR XY SJ XX Matlab 的 Hill2 加密程序见 附录 2，相应解密程序见 附录 3。 ？ Hill2 加密过程总结 通讯双方确定加密矩阵 ( 密钥) 和字母的表值对应表 将明文字母分组，通过查表列出每组字母对应的向量 令 = A mod(m) ，由 的分量反查字母表值表， 得到相应的密文字母 若明文只含奇数个字母，则补充一个哑元 Hill2 解密过程总结 将密文字母分组，通过查表列出每组字母对应的向量 求出加密矩阵 A 的 模 m
10、 逆矩阵 B 令 = B mod(m) ，由 的分量反查字母表值表， 得到相应的明文字母 甲方收到乙方（己方）的一个密文信息，内容为： Hill2 解密举例 WKVACPEAOCIXGWIZUROQWAB ALOHDKCEAFCLWWCVLEMIMCC 按照甲方与乙方的约定，他们之间采用 Hill2密码，密钥 为 ，字母表值见下表，问这段密文的原文 是什么？ ABCDEFGHIJKLM 12345678910 11 12 13 NOPQRSTUVW XYZ 14 15 16 17 18 19 20 21 22 23 24 25 0 Hill2 解密举例 将密文字母分组，通过查表列出每组字母对应
11、的向量 求出加密矩阵 A 的 模 26 逆矩阵 用 B 左乘每组密文字母组成的向量，然后再反查字母 表值表，得到相应的明文字母 序 号 分 组 密 文 密 文 表 值 明 文 表 值 分组 明文 1W K 23 11 7 21 G U 2V A 22 1 4 9 D I 3C P 3 16 1 14 A N 4E A 5 1 13 9 M I 5O C 15 3 13 1 M A 6I X 9 24 19 8 S H 序 号 分 组 密 文 密 文 表 值 明 文 表 值 分组 明文 7G W 7 23 9 25 I Y 8I Z 9 0 9 0 I Z 9U R 21 18 9 6 I F
12、10O Q 15 17 21 23 U W 11W A 23 1 5 9 E I 12B A 2 1 10 9 J I Hill2 解密举例 序 号 分 组 密 文 密 文 表 值 明 文 表 值 分组 明文 1 3 L O 12 15 2 5 B E 1 4 H D 8 4 14 10 N J 1 5 K C 11 3 9 1 I A 1 6 E A 5 1 13 9 M I 1 7 F C 6 3 4 1 D A 1 8 L W 12 23 14 25 N Y 序 号 分 组 密 文 密 文 表 值 明 文 表 值 分组 明文 1 9 W C 23 3 21 1 U A 2 0 V L 2
13、2 12 14 4 N D 2 1 E M 5 13 5 13 E M 2 2 I M 9 13 9 13 I M 2 3 C C 3 3 1 1 A A Hill2 解密举例 即：“古典密码是以字符为基本加密单元的密码” GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA A WKVACPEAOCIXGWIZUROQWAB ALOHDKCEAFCLWWCVLEMIMCC 原文 Hill2 解密举例 密文 ABCDEFGHIJKLM 12345678910111213 NOPQRSTUVWXYZ 141516171819
14、2021222324250 经分析该密文是用 Hill2密码 加密，且密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O )，问能否破译这段密文？ Hill2 密码破译举例 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 我方截获一段密文 l 猜测密文是由26个字母组成，即 m=26， 经破译部门通过大量的统计分析和语言分析确定表值 l 破译这段密文的关键是找到“密钥”和字母对应的表值 l 密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O ) Hill2 密码破译举例 查 字 母 表 值
15、 PC P、C 模26可逆 可唯一确定加密矩阵 A Hill2 密码破译举例 HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ON 相应的 Matlab 程序见附录 4 u 得到加密矩阵的 模26逆矩阵 后，根据前面的解 密方法即可得密文的原文 Hill2 密码破译举例 m=27;enmat=1 2;0 4;demat=1 13;0 7;ZERO=64;c=;en=; nfprintf(本组成员的姓名为 陈省身 华罗庚 吴文俊,拼音为:n) nfprintf(CHEN XING SHEN HUA LUO GENG WU WEN JUN n) nfprintf(以1 2;0 4为密钥对此拼音串加密n) nastr=CHEN XING SHEN HUA LUO GENG WU WEN JUN ; nan=double(astr); nif mod(length(an),2)=1 n an=an,an(length(an); nend nan=an-ZERO; nfor i=1:length(an) n if an(i)=-32 n an(i)=0; n end nend nc=reshape(an,2,length(an)/2); ndn=mod(enmat*c,m); nen=reshape(dn,1
