实验十【Hill密码的加密解密与破译】.doc

Hill 密 码 的 加 密 、 解 密 与 破 译 小组成员: 钱晨 201000090092 2010级二班 林锦帆 201000090056 2010级一班 王颖慧 201000090126 2010级基地 刘乐 201000090063 2010级二班 [实验十] Hill密码的加密、解密与破译 一、实验目的 本实验主要涉及代数，利用模运算意义下的矩阵乘法、求逆矩阵、线性无关、线性空间与线性变换等概念和运算，学习Hill密码体制的加密、解密和破译过程。 二、实验内容 (1)甲方收到与之有秘密通信往来的乙方的一个密文信息，密文内容： W O W U Y S B A C P G Z S A V C O V K P E W C P A D K P P A B U J C Q L Y X Q E Z A A C P P 按照甲方与乙方的约定，他们之间的密文通信采用Hill2密码，密钥为 二阶矩阵 且汉语拼音的26个字母与0~25之间的整数建立一一对应的关系，称之为字母的表值，具体的表值见表10. 1 明文字母的表值。问这段密文的原文是什么？ 表10. 1 明文字母的表值 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 0 (2)甲方截获了一段密文： O J W P I S W A Z U X A U U I S E A B A U C R S I P L B H A A M M L P J J O T E N H 经分析这段密文是用Hill2密码编译的，且这段密文的字母UCRS依次代表字母TACO，问能否破译这段密文的内容？ 三、Hill2密码的数学模型 Ⅰ、加密与解密过程 Hill2密码是一种传统的密码体制，它的加密过程可用以下框图描述： 明文------?加密器------?密文------?普通信道------?解密器 密码分析（敌方截获）?----- 明文 在这个过程中，运用的数学手段是矩阵运算，加密过程的具体步骤如下： 1．根据明文字母的表值将明文信息用数字表示，设明文信息只需要26个拼音字母A~Z（也可能不止26个，如还有数字、标点符号等），通信双方给出这26个字母表值（见表10.1明文字母的表值）。 2．选择一个二阶可逆整数方阵A，称为Hill2密码的加密矩阵，它是这个加密体制的“密钥”（是加密的关键，仅通讯双方掌握）。问题(1)已给出了这个二阶矩阵。 3．将明文字母依次逐对分组。Hill2密码的加密矩阵为二阶矩阵，则明文字母2个一组（可以推广至Hilln密码，则每n个明文字母为一组）。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使每一组都由2个明文字母组成。查出每个明文字母的表值，构成一个二维列向量α。 4．A乘以α，得一新的2维列向量β=Aα，由的两个分量反查字母表值得到的两个字母即为密文字母。 以上4步即为Hill2密码的加密过程。解密过程，即为上述过程的逆过程。 例如，明文为YI CHU FA，A=。 将明文相邻2个字母分为一组：YI CH UF AA，最后一个字母A是为使最后一组的字母数为2而添加的，无实际意义。根据表值可构造相应2维列向量： ，，， (*) 用矩阵A左乘上述4个向量，得到4个新的列向量： ，，，， 为与表值对应作模26运算得到： ，，， 关于模m运算，可以验证，对两个正整数a1，a2进行加，减或乘的模m运算有如下规律： 这样，这4个新的2维列向量对应的字母为 QA SX GR CC 这段文字即为明文“YI CHU FA”的密文。 要将这段密文解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，查他们的表值即得： ，，， 但如何由该组中的向量求得(*)中的向量呢？这是在模运算意义下，如何求解方程组：Aα=β的问题。一个一般的n阶方阵可逆的充要条件为det A≠0。 在模26意义下矩阵可逆与一般的矩阵可逆有所不同。记整数集合Zm={0,1,2, 定义1 对于一个元素属于集合Zm的n阶方阵A，若存在一个元素属于Zm集合的方阵B，使得 AB=BA=E(mod m)称A为模m可逆，B为A的模m逆矩阵，记为B=A-1(mod m) E(mod m)的意义是，每一个元素减去m的整数倍后，可以化成单位矩阵。例如， 定义2 对Zm的一个整数a，若存在Zm的一个整数b，使得ab=1(mod m），称b为a的模m倒数或乘法逆，记作b=a?1(mod m)。 可以证明，如果a与