实验四 Hill密码

1、实验四实验四 Hill密码密码 实验目的：本实验主要涉及代数，利用模运实验目的：本实验主要涉及代数，利用模运算下的矩阵乘法、求逆矩阵、线性无关、线性空算下的矩阵乘法、求逆矩阵、线性无关、线性空间和线性变换等概念和运算，学习间和线性变换等概念和运算，学习Hill密码体制密码体制的加密、解密和破译过程。的加密、解密和破译过程。一、密码学基本概念一、密码学基本概念明文明文( (plaintext) )：未加密的信息；：未加密的信息；密文密文( (ciphertext) )：加密后的信息；：加密后的信息；加密加密( (encryption) )：从明文到密文的变换；：从明文到密文的变换；解密解密( (

2、decryption) )：从密文到明文的变换：从密文到明文的变换 加密和解密都是在密钥加密和解密都是在密钥( (key) )的控制下进行的的控制下进行的, ,给定一个密钥给定一个密钥, ,就可以确定一对具体的加密变换和就可以确定一对具体的加密变换和解密变换解密变换. .二、密码分类二、密码分类密密码码古典密码古典密码现代密码现代密码以字符为以字符为基本加密基本加密单元单元以信息块以信息块为基本加为基本加密单元密单元三、加密和解密的一般过程三、加密和解密的一般过程明文明文加密器加密器普通信道普通信道密文密文解密器解密器明文明文易被截获易被截获四、实际问题四、实际问题(1)(1)甲方收到乙方的一

3、封密文信息甲方收到乙方的一封密文信息, ,密文如下密文如下: :WOWUYSBACPGZSAVCOVKPEWCPADKPPABUJCQLYXQEZAACPP 按约定按约定, ,他们之间采用他们之间采用Hill2密码通信密码通信, ,密钥是二阶矩密钥是二阶矩阵阵 ，且汉语拼音的，且汉语拼音的2626个字母与个字母与0-250-25之间的之间的整数建立一一对应关系整数建立一一对应关系, ,称之为字母的称之为字母的表值表值, ,具体如下具体如下. .问这段密文的原文是什么问这段密文的原文是什么? ? 3021AABCDEFGHIJKLM12345678910 11 12 13NOPQRSTUVWXY

4、Z14 15 16 17 18 19 20 21 22 23 24 250(2)(2)甲方截获了一段密文甲方截获了一段密文: :OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH经分析，这段密文使用经分析，这段密文使用Hill2密码编译的密码编译的, ,且这段且这段密文的字母密文的字母UCRS依次代表字母依次代表字母TACO, ,文能否破译文能否破译这段密文的内容这段密文的内容? ?五、五、Hill2 密码的数学模型密码的数学模型加密过程：加密过程： 1. 1.设明文信息只需要设明文信息只需要2626个字母个字母(A-Z),(A-Z),(可能不可能不止这止这2

5、626个个),),通信双方给出这通信双方给出这2626个字母的表值个字母的表值, ,根据根据表值将明文信息用数字表示表值将明文信息用数字表示. . 2. 2.选择一个二阶可逆方阵选择一个二阶可逆方阵 , ,称为加密矩阵称为加密矩阵, ,也也就是密钥就是密钥. .A 3. 3.将明文字母依次逐对分组将明文字母依次逐对分组. .Hill2密码的加密密码的加密矩阵是为二阶矩阵，则明文字母矩阵是为二阶矩阵，则明文字母2个一组个一组( (Hilln密密码码, ,n个明文字母为一组个明文字母为一组),),若最后一组只有一个字母若最后一组只有一个字母, ,则补充一个无意义的字母，称为哑字母则补充一个无意义的

6、字母，称为哑字母. .由明文字母由明文字母表值查出每一组表值查出每一组2个明文字母的表值得到一个二维列个明文字母的表值得到一个二维列向量向量 。a解密过程是加密过程的逆过程。解密过程是加密过程的逆过程。例例 明文为明文为YI CHU FA. ,. ,求这段明文的求这段明文的Hill2密文密文. . 3021A将明文相邻将明文相邻2个字母分为一组个字母分为一组 YI CH UF AA最后一个字母最后一个字母A为哑字母为哑字母, ,无实际意义无实际意义. .查出每对字母查出每对字母的表值的表值, ,构造构造2维列向量维列向量: : 4. 4. 左乘以左乘以 得到一个新的二维向量得到一个新的二维向量

7、 , ,由由 的两个分量反查字母表值得到密文字母的两个分量反查字母表值得到密文字母. .从而从而完成加密过程完成加密过程. .A A 11,621,83,925将上述将上述4个向量左乘矩阵个向量左乘矩阵 , ,得到得到4个新的列向量个新的列向量: :A 33,1833,2419,2743在反查这在反查这4 4个向量对应的字母时个向量对应的字母时, ,遇到了问题遇到了问题: :第一第一个第三个向量中含有不在表中的值个第三个向量中含有不在表中的值, ,处理的办法是处理的办法是加减加减2626的整数倍，使其化成的整数倍，使其化成0-250-25之间的一个整数之间的一个整数, ,这称为这称为模模262

8、6运算运算: :记为记为4317337(mod26),(mod26)2711818 六、模六、模 运算的一些定义和结论运算的一些定义和结论 m关于模关于模 运算运算, ,可以验证可以验证, ,对两个整数对两个整数 , ,进行加减进行加减或乘的模或乘的模 运算有如下规律运算有如下规律: :mm21,aa) (mod) (mod() (mod() (mod2121mmamamaa 这样这样, ,这这4 4个新的个新的2 2维列向量对应的字母为维列向量对应的字母为QA SX GR CC这也就是上段明文这也就是上段明文: :”YI CHU FA”的密文的密文. . 定义一定义一: :设整数集合设整数集

9、合 , ,其中其中 为一正整数为一正整数. .对对 中的一个整数中的一个整数 , ,如果存在如果存在 中的中的一个整数一个整数 , ,使得使得 , ,称称 为为 的模的模 倒数倒数或乘法逆或乘法逆, ,记作记作 . .例如例如1, 1 , 0 mZmmmZmZb) (mod1mab baam) (mod1mab )26 (mod391 要将这段密文解密，只要将上述加密过程逆转要将这段密文解密，只要将上述加密过程逆转即可即将密文按照同样的方法分组查它们的表即可即将密文按照同样的方法分组查它们的表值，但是如何通过密文的表值得到明文的表值？这值，但是如何通过密文的表值得到明文的表值？这就要在模运算意

10、义下，如何解方程组：就要在模运算意义下，如何解方程组： A一般的阶方阵可逆的充要条件为一般的阶方阵可逆的充要条件为 . .但在但在模运算下的可逆与一般意义下的可逆有所不同模运算下的可逆与一般意义下的可逆有所不同n0det A如果如果 与与 无公共素因子无公共素因子, ,则则 有唯一的模有唯一的模 倒数倒数. .amam 对于一个元素属于对于一个元素属于 的的 阶方阵阶方阵 , ,若存在若存在一个元素属于一个元素属于 中的一个中的一个 阶方阵阶方阵 , ,使得使得mZnAmZnB) (mod mEBAAB 则称则称 为模为模 可逆可逆, , 为为 的模的模 可逆矩阵可逆矩阵, ,记作记作: :A

11、mBAm) (mod1mAB 元素属于元素属于 的的 阶方阵阶方阵 模模 可逆的充要条可逆的充要条件是件是, , 和和 没有公共素数因子没有公共素数因子. .mZnAmmAdet七、七、Hill2密码的破译密码的破译问题问题(2)(2)属于破译问题前面的加密和解密过程类属于破译问题前面的加密和解密过程类似于在二维向量空间进行线性变换与其逆变换似于在二维向量空间进行线性变换与其逆变换. .每每个明文向量是一个个明文向量是一个 上的二维向量上的二维向量, ,乘以加密矩阵乘以加密矩阵后后, ,仍为仍为 上的一个二维向量上的一个二维向量. .由加密矩阵由加密矩阵 可逆可逆, ,所以如果知道了两个线性无

12、关的二维明文向量与其所以如果知道了两个线性无关的二维明文向量与其对应的密文向量对应的密文向量, ,就可以求出加密矩阵就可以求出加密矩阵 及及 mZmZAA1 A在问题在问题(2)(2)中中 OCSRATCU ,明文明文 密文密文 明文明文 密文密文 OCASRATACU1531918120321222111 在模在模2626意义下意义下, ,7)26 (mod345)26 (mod1931821),det(21 它有模它有模2626倒数倒数, ,所以在模所以在模2626意义下意义下 线性无关线性无关. .类似地类似地, ,可以验证可以验证 线性无关线性无关. .21, 21, 记记 , ,则则

13、 ),(),(2121 CP1, PCAACP在模在模2626意义下进行初等行变换意义下进行初等行变换, ,求得求得 , ,因而因而求出求出 . .利用利用 即可将问题即可将问题(2)(2)的密文解密的密文解密. .TA )(1 1 A1 A 3239052215115319185221511531918120321)()26)(mod18(5)26(mod2112111rrrrTTCP初等变换过程如下初等变换过程如下: : 917100101917105221513)26)(mod15(3)26(mod9221212rrrrr故故 90171,91701)(11AAT这段密文解密后为这段密文

14、解密后为: :Clinton is going to visit a country in Middle East t.最后一个为哑字母最后一个为哑字母. .练习题练习题ABCDEFGHIJKLM523220 10 158418 25016 13NOPQRSTUVWXYZ73119612 24 21 17 14 22 119 1. 1.利用所介绍的利用所介绍的Hill2 2密码体制的原理密码体制的原理, ,根据根据给定的给定的2626个英文字母的乱序表值个英文字母的乱序表值( (见下表见下表),),设计和设计和建立建立HillHill4 4密码体制的加密和解密的必要的计算机密码体制的加密和解密

15、的必要的计算机程序程序. .设设2626个英文字母以下面的乱序表与个英文字母以下面的乱序表与Z Z2626中的中的整数对应。整数对应。(2)(2)设明文为设明文为HILL CRYPTOGRAPHIC SYSTEM IS TRADITIONAL利用上述表值和加密矩阵给此明文加密利用上述表值和加密矩阵给此明文加密,编程实现编程实现加密和解密过程加密和解密过程. (1) (1)设设 ,验证矩阵验证矩阵 能否作能否作为为Hill4密码体制的加密矩阵密码体制的加密矩阵.编程实现编程实现. 4116109485105965968AA (3) (3)已知上述给定表值的一段已知上述给定表值的一段Hill4密码

16、密文为密码密文为对应的明文为对应的明文为能否确定对应的加密矩阵能否确定对应的加密矩阵?JCOW ZLVB DVLE QMXCDELAY OPERATIONSU 2. 2.设已知一份设已知一份Hill2密码体系密码体系, ,其中出现频其中出现频率最高的双字母是率最高的双字母是RH和和NI, ,而在明文语言中而在明文语言中, ,出出现频率最高的双字母为现频率最高的双字母为TH和和HE. .由这些信息按由这些信息按照下表给出的表值能得到什么样的加密矩阵照下表给出的表值能得到什么样的加密矩阵? ?ABCDEFGHIJKLM012345678910 11 12NOPQRSTUVWXYZ13 14 15 16 17 18 19 20 21 22 23 24 25 3. 3.找