实验十古典密码及破译

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

2、加以解密。问题背景和实验目的问题背景和实验目的明文明文密文密文明文明文加密加密解密解密q 密码可分为古典密码和现代密码密码可分为古典密码和现代密码q 本实验主要介绍古典密码的加密与破译原理，本实验主要介绍古典密码的加密与破译原理，同时介绍如何用同时介绍如何用 Matlab 编程来实现加密、解密和编程来实现加密、解密和破译过程。破译过程。问题背景和实验目的问题背景和实验目的u 古典密码：古典密码：以字符为基本加密单元；以字符为基本加密单元；u 现代密码：现代密码：以信息块为基本加密单元。以信息块为基本加密单元。加密信息传递过程加密信息传递过程明文明文（信息）（信息）加密器加密器密文密文密文密文明

3、文明文（信息）（信息）解密器解密器普普通通信信道道发发送送敌方截获敌方截获破译破译发送方发送方接收方接收方Hill2 密码的加密过程密码的加密过程q Hill2 密码中所用的数学手段是密码中所用的数学手段是 矩阵运算矩阵运算。q 加密过程：加密过程： 将汉语拼音的将汉语拼音的 26 个字母个字母 与与 0 到到 25 之间的整数建之间的整数建立一一对应关系，称为字母的立一一对应关系，称为字母的 表值表值，然后根据明文字，然后根据明文字母的表值，母的表值，将明文信息用数字表示将明文信息用数字表示。ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161

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

5、广至Hill n密码）。查出每个字密码）。查出每个字母的表值，这样，每组字母构成一个二维列向量母的表值，这样，每组字母构成一个二维列向量 。若最后仅剩一个字母，则补充一个若最后仅剩一个字母，则补充一个没有实际意义的哑字母没有实际意义的哑字母（哑元哑元）。这样使得每组都有）。这样使得每组都有 2 个字母，个字母， 令令 = A ，由，由 的两个分量反查字母表值表，得到的两个分量反查字母表值表，得到相应的两个字母，即为相应的两个字母，即为密文字母密文字母。Hill2 加密举例加密举例例：例： 设明文为设明文为“HRXYSJX”（华锐学院数计系），（华锐学院数计系），试给出这段明文的试给出这段明文的

6、 Hill2 密文密文。 将明文字母分组：将明文字母分组： HR XY SJ XX最后的一个字母最后的一个字母 X 为哑字母，无实际意义。为哑字母，无实际意义。解解:, 8241924,18251024A B C D E F G H IJKLM1 2 3 4 5 6 7 89 10 1112 13NOPQRSTUVW XYZ1415161718192021222324250查表得每组字母的表值，得到查表得每组字母的表值，得到 4 个二维列向量：个二维列向量：1203A 将上述将上述 4 个二维向量个二维向量左乘密钥矩阵左乘密钥矩阵 A 得：得：44743972, , , 54753072作作模

7、模 26 运算运算，将所有的数都化为，将所有的数都化为 0 到到 25 之间的整数：之间的整数：4474(mod 26) (mod 26) 54753972(mod 21822223136) (mod 26) 302042207,. Hill2 加密举例加密举例反查字母表值得每个向量对应的字母组为：反查字母表值得每个向量对应的字母组为：HRXYSJXRBVWMDTTHill2 加密加密Hill2 加密举例加密举例A B C D E F G H IJKLM1 2 3 4 5 6 7 89 10 1112 13NOPQRSTUVW XYZ141516171819202122232425018221

8、320 , , , 223420 RB VW MD TT问题：问题：怎样解密？怎样解密？明文字母明文字母查表值查表值分组分组一组向量一组向量加加密密矩矩阵阵左左乘乘一组新的向量一组新的向量反查表值反查表值密文密文Hill2 加密过程加密过程模运算模运算先查出密文字母先查出密文字母 “RB VW MD TT” 所对应的向量：所对应的向量：在模运算下解方程组：在模运算下解方程组： A = q 解密：加密的逆过程，解密：加密的逆过程，将加密过程逆转回去即可。将加密过程逆转回去即可。Hill2 解密过程解密过程18221320223420 ，例：例：怎么得到密文怎么得到密文 “RBVWMDTT ” 的

9、原文的原文? 上面的向量是由上面的向量是由 经过经过模模 26 运算运算得来的，现在的问题是怎样逆转回去？得来的，现在的问题是怎样逆转回去？44743972, , , 54753072模模 m 可逆可逆0,1,2,.,1mZm记记定义定义 1：设设 A 为定义在集合为定义在集合 Zm 上的上的 n 阶方阵，若存在一个定阶方阵，若存在一个定义在义在 Zm 上的方阵上的方阵 B，使得使得 则称则称 A 模模 m 可逆可逆， B 为为 A 的的 模模 m 逆矩阵逆矩阵，记为，记为(mod)ABBAEm 1(mod)BAm 定义定义 2：设设 a Zm ，若存在，若存在 b Zm 使得使得 ab=1

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

11、要条件是：的充要条件是：模模 m 可逆可逆det(A) 不能被不能被 2 和和 13 整除整除u 问题：问题：是否是否 Zm 中所有的数都存在中所有的数都存在模模 m 倒数倒数？a 存在唯一的模存在唯一的模 m 倒数倒数a 与与 m 无公共素数因子无公共素数因子u Z26 中具有模中具有模 26 倒数的整数及其模倒数的整数及其模 26 倒数表倒数表2a1357911 15 17 19 21 23 25a-11921 15319723 11517 25m=26 时的时的 Matlab 程序见教材第程序见教材第 121 页页 附录附录1程序程序 可以用来判断一个可以用来判断一个 2 阶矩阵阶矩阵在

12、在模模 26 运算运算下是否可逆，并在可逆的前提下给出其模下是否可逆，并在可逆的前提下给出其模 26 逆矩阵。逆矩阵。模模 26 可逆可逆u 思考：思考：如何用如何用 Matlab 编程来找出所有模编程来找出所有模 m 倒倒数的整数及其模数的整数及其模 m 倒数？倒数？nm=26;nfor a=1:mn for i=1:mn if mod(a*i,m)=1n fprintf(%d 的模的模%d倒数是倒数是: %dn,a,m,i);break;n end;n end;nend在模运算下解方程组：在模运算下解方程组： A = 1(mo 2d)6A Hill2 解密过程解密过程？(mod26)u 问

13、题：问题：如何计算如何计算 ？1(mo)6d2A , 8241924,1825102418221320223420 ，模模 m 逆矩阵逆矩阵的的计算计算11|AAA l 设设 B=k A*为为 A 的的 模模 26 逆逆，其中，其中 k 为待定系数为待定系数 |BAkAE (mo 26d)BAE | 1(mo6d)2kA 1|(mod)26kA A*为为 A 的伴随矩阵的伴随矩阵本计算方法可推广到求矩阵本计算方法可推广到求矩阵 A 的的 模模 m 逆矩阵逆矩阵Hill2 解密过程解密过程l 设加密矩阵设加密矩阵1203A 32|3,01AA 1132(mod)(m262626od)(mod)0

14、13A 1809 1(mo 2d)6BA 329(mod)0126 , 183422206,21823207134520180,43620180BBBB l 用用 B 左乘密文对应的向量得：左乘密文对应的向量得：l 模模 26 运算后得：运算后得：l 查表后得明文分别为：查表后得明文分别为： HR XY SJ XXMatlab 的的 Hill2 加密程序见加密程序见 附录附录 2，相应解密程序见，相应解密程序见 附录附录 3。18221320223420 ，, 8241924,18251024？, 8241924,18251024Hill2 加密过程总结加密过程总结 通讯双方确定通讯双方确定加

15、密矩阵加密矩阵 ( 密钥密钥) 和字母的和字母的表值对应表表值对应表 将将明文字母明文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的向量向量 令令 = A mod(m) ，由，由 的分量反查字母表值表，的分量反查字母表值表， 得到相应的得到相应的密文字母密文字母若明文只含奇数个字母，则补充一个若明文只含奇数个字母，则补充一个哑元哑元Hill2 解密过程总结解密过程总结 将将密文字母密文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的向量向量 求出加密矩阵求出加密矩阵 A 的的 模模 m 逆矩阵逆矩阵 B 令令 = B mod(m) ，由，由 的分量反查

16、字母表值表，的分量反查字母表值表， 得到相应的得到相应的明文字母明文字母甲方收到乙方（己方）的一个密文信息，内容为：甲方收到乙方（己方）的一个密文信息，内容为：Hill2 解密举例解密举例WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方与乙方的约定，他们之间采用按照甲方与乙方的约定，他们之间采用 Hill2密码密码，密钥，密钥为为 ，字母表值见下表，问这段密文的原文，字母表值见下表，问这段密文的原文是什么？是什么？1203A ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021

17、222324250Hill2 解密举例解密举例 将将密文字母密文字母分组，通过查表列出每组字母对应的分组，通过查表列出每组字母对应的向量向量 求出加密矩阵求出加密矩阵 A 的的 模模 26 逆矩阵逆矩阵 用用 B 左乘每组密文字母组成的向量，然后再反查字母左乘每组密文字母组成的向量，然后再反查字母表值表，得到相应的表值表，得到相应的明文字母明文字母1809B 序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文1W K2311721GU2VA22149DI3CP316114AN4EA51139MI5OC153131MA6IX924198SH序序号号分组分组密文密文密文密文表

18、值表值明文明文表值表值分组分组明文明文7GW723925IY8IZ9090IZ9UR211896IF10OQ15172123UW11WA23159EI12BA21109JIHill2 解密举例解密举例序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文13LO121525BE14HD841410NJ15KC11391IA16EA51139MI17FC6341DA18LW12231425NY序序号号分组分组密文密文密文密文表值表值明文明文表值表值分组分组明文明文19WC233211UA20VL2212144ND21EM513513EM22IM913913IM23CC3311A

19、AHill2 解密举例解密举例即：即：“古典密码是以古典密码是以字符为基本加密单元的密码字符为基本加密单元的密码”GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA AWKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC原文原文Hill2 解密举例解密举例密文密文ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250经分析该密文是用经分析该密文是用 Hill2密码密码 加密，且密文加密，且密文 ( U

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

21、文密文 ( U, C ) 和和 ( R, S ) 分别对应明文分别对应明文 ( T, A ) 和和 ( C, O )Hill2 密码破译举例密码破译举例查查 字字 母母 表表 值值A 2118 3 20319115A PCPAC 2118203,319115PC PAC 1A PC |(m7od26)P |(mo161d2 )C P、C 模模26可逆可逆可唯一确定加密矩阵可唯一确定加密矩阵 A11AC P 1126262(mod)(m(moodd6)APC Hill2 密码破译举例密码破译举例HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ON相应的相

22、应的 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为密钥对此拼音串加密为密钥对此拼音串加密

23、n)nastr=CHEN XING SHEN HUA LUO GENG WU WEN JUN ;nan=double(astr);nif mod(length(an),2)=1n an=an,an(length(an);nendnan=an-ZERO;nfor i=1:length(an)n if an(i)=-32n an(i)=0;n endnendnc=reshape(an,2,length(an)/2);ndn=mod(enmat*c,m);nen=reshape(dn,1,length(an);nen=en+ZERO;nfor i=1:length(en)n if en(i)=64n

24、 en(i)=32;n endnendnen=en(1: length(an);ndisp(密文是密文是:,char(en)本组成员的姓名为本组成员的姓名为 陈省身陈省身 华罗庚华罗庚 吴文俊吴文俊, ,拼音为拼音为: :CHEN XING SHEN HUA LUO GENG WU WEN JUN CHEN XING SHEN HUA LUO GENG WU WEN JUN 以以1 2;0 41 2;0 4为密钥对此拼音串加密为密钥对此拼音串加密密文是密文是:SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB:SEFBUOJBG HEFBPEWDXUXFNAFBG K

25、CSKFBTMVB nm=27;enmat=1 2;0 4;demat=1 13;0 7;ZERO=64;c=;en=;nfprintf(本组成员的姓名为陈省身本组成员的姓名为陈省身 华罗庚华罗庚 吴文俊吴文俊,拼音密文为拼音密文为:n)nfprintf( SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB n)nfprintf(以以1 13;0 7为密钥对此拼音串密文解密为密钥对此拼音串密文解密n)nastr=SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB;nan=double(astr);nif mod(length(an),2)=1

26、n an=an,an(length(an);nendnan=an-ZERO;nfor i=1:length(an)n if an(i)=-32n an(i)=0;n endnendnc=reshape(an,2,length(an)/2);ndn=mod(demat*c,m);nen=reshape(dn,1,length(an);nen=en+ZERO;nfor i=1:length(en)n if en(i)=64n en(i)=32;n endnendnen=en(1: length(an);ndisp(明文是明文是:,char(en)本组成员的姓名为陈省身本组成员的姓名为陈省身 华罗庚

27、华罗庚 吴文俊吴文俊, ,拼音密文为拼音密文为: : SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB 以以1 13;0 71 13;0 7为密钥对此拼音串密文解密为密钥对此拼音串密文解密明文是明文是:CHEN XING SHEN HUA LUO GENG WU WEN JUN:CHEN XING SHEN HUA LUO GENG WU WEN JUN相关相关Matlab函数介绍函数介绍u inputA=input(提示信息)l 其中 提示信息 为字符串l 该命令要求用户输入 A 的值，

28、可以是数、矩阵或字符串n 数可以直接输入n 矩阵需要加 n 字符串需要加单引号 A=input(Please input A: )u sizesize(a)相关相关Matlab函数介绍函数介绍u lengthlength(a)l 如果 a 是向量，则返回其长度；l 如果 a 是矩阵，则返回行数与列数中最大的一个。u modmod(m,n)l 求余，返回 m 被 n 整除后的余数，符号与 n 相同;l 另外一个求余函数是 remu gcd ：求最大公约数gcd(m,n)相关相关Matlab函数介绍函数介绍u det ：计算行列式det(A)u inv ：计算逆矩阵inv(A)u reshape

29、：将矩阵元素按列方向进行重组reshape(A,m,n)l 将 A 排 m 行，n 列的矩阵，要求 A 的元素个数 =m*n相关相关Matlab函数介绍函数介绍u doubledouble(str)l 当 str 是字符串时，返回所有字符的 ASCII 码u charchar(a)l 当 a 是整数时，返回 ASCII 码等于 a 的字符数据输出数据输出 fprintfl fid 为文件句柄，若缺省，则将变量的值输出到屏幕上l format 用来指定数据输出时采用的格式，常见的有 %e ( 采用科学计算形式采用科学计算形式 ) %f ( 采用浮点数形式采用浮点数形式 ) %g ( 由系统自动选

30、取上述两种格式之一由系统自动选取上述两种格式之一) %s ( 输出字符串输出字符串) l format 中还可以使用一些特殊格式，如：n ( 换行换行 ) t ( 制表符制表符 ) b ( 退格退格 ) ( 反斜杆反斜杆 ) % ( 百分号百分号 ) fprintf(fid,format,variables)按指定的格式将变量的值输出到指定的文件u fprintf ：格式化输出数据输出数据输出 fprintf a=Hello; b=2.4; c=100*pi; fprintf(a=%s,b=%f,c=%en,a,b,c)例：例：l format 中的输出格式要与输出变量一一对应l 可以没有输出变量 fprintf( Today is Mondayn)例：例：附录附录 1 1：判断一个：判断一个 2 2 阶方阵是否模阶方阵是否模 26 26 意义下意义下可逆；若可逆，求出模可逆；若可逆，求出模 26 26 意义下的逆矩阵意义下的逆矩阵nm=26;naa=input(输入一个输入一个22的矩阵，格式：的矩阵，格式：a11 a12;a21 a22: )nwhile size(aa)=2 2naa=input(输入一个输入一个22的矩阵，格式：的矩阵，格式：a11 a