实验四 hill密码.ppt

实验四 Hill密码,实验目的：本实验主要涉及代数，利用模运算下的矩阵乘法、求逆矩阵、线性无关、线性空间和线性变换等概念和运算，学习Hill密码体制的加密、解密和破译过程一、密码学基本概念,明文(plaintext)：未加密的信息； 密文(ciphertext)：加密后的信息； 加密(encryption)：从明文到密文的变换； 解密(decryption)：从密文到明文的变换,加密和解密都是在密钥(key)的控制下进行的,给定一个密钥,就可以确定一对具体的加密变换和解密变换.,二、密码分类,密码,,,古典密码,现代密码,以字符为基本加密单元,以信息块为基本加密单元,三、加密和解密的一般过程,明文,,加密器,普通信道,密文,解密器,明文,,,,,,易被截获,四、实际问题,(1)甲方收到乙方的一封密文信息,密文如下:,WOWUYSBACPGZSAVCOVKPEWCPADKPPABUJCQLYXQEZAACPP,按约定,他们之间采用Hill2密码通信,密钥是二阶矩 阵 ，且汉语拼音的26个字母与0-25之间的 整数建立一一对应关系,称之为字母的表值,具体如下.问这段密文的原文是什么?,(2)甲方截获了一段密文:,OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH,经分析，这段密文使用Hill2密码编译的,且这段密文的字母UCRS依次代表字母TACO,文能否破译这段密文的内容?,五、Hill2 密码的数学模型,加密过程：,1.设明文信息只需要26个字母(A-Z),(可能不止这26个),通信双方给出这26个字母的表值,根据表值将明文信息用数字表示.,2.选择一个二阶可逆方阵 ,称为加密矩阵,也就是密钥.,3.将明文字母依次逐对分组.Hill2密码的加密矩阵是为二阶矩阵，则明文字母2个一组(Hilln密码,n个明文字母为一组),若最后一组只有一个字母,则补充一个无意义的字母，称为哑字母.由明文字母表值查出每一组2个明文字母的表值得到一个二维列向量 。

解密过程是加密过程的逆过程例 明文为YI CHU FA. ,求这段明文的Hill2密文.,将明文相邻2个字母分为一组 YI CH UF AA,最后一个字母A为哑字母,无实际意义.查出每对字母的表值,构造2维列向量:,4. 左乘以 得到一个新的二维向量 ,由 的两个分量反查字母表值得到密文字母.从而完成加密过程.,将上述4个向量左乘矩阵 ,得到4个新的列向量:,在反查这4个向量对应的字母时,遇到了问题:第一个第三个向量中含有不在表中的值,处理的办法是加减26的整数倍，使其化成0-25之间的一个整数,这称为模26运算:记为,六、模 运算的一些定义和结论,,关于模 运算,可以验证,对两个整数 ,进行加减或乘的模 运算有如下规律:,这样,这4个新的2维列向量对应的字母为,QA SX GR CC,这也就是上段明文:”YI CHU FA”的密文.,,定义一:设整数集合 ,其中 为一正整数.对 中的一个整数 ,如果存在 中的一个整数 ,使得 ,称 为 的模 倒数或乘法逆,记作 .例如,要将这段密文解密，只要将上述加密过程逆转即可．即将密文按照同样的方法分组．查它们的表值，但是如何通过密文的表值得到明文的表值？这就要在模运算意义下，如何解方程组：,一般的 阶方阵可逆的充要条件为 .但在模运算下的可逆与一般意义下的可逆有所不同．,如果 与 无公共素因子,则 有唯一的模 倒数.,对于一个元素属于 的 阶方阵 ,若存在一个元素属于 中的一个 阶方阵 ,使得,则称 为模 可逆, 为 的模 可逆矩阵,记作:,元素属于 的 阶方阵 模 可逆的充要条件是, 和 没有公共素数因子.,七、Hill2密码的破译,问题(2)属于破译问题．前面的加密和解密过程类似于在二维向量空间进行线性变换与其逆变换.每个明文向量是一个 上的二维向量,乘以加密矩阵后,仍为 上的一个二维向量.由加密矩阵 可逆,所以如果知道了两个线性无关的二维明文向量与其对应的密文向量,就可以求出加密矩阵 及 ．,在问题(2)中,明文 密文 明文 密文,在模26意义下,,它有模26倒数,所以在模26意义下 线性无关.类似地,可以验证 线性无关.,记 ,则,在模26意义下进行初等行变换,求得 ,因而求出 .利用 即可将问题(2)的密文解密.,初等变换过程如下:,故,这段密文解密后为:,Clinton is going to visit a country in Middle East t.,最后一个为哑字母.,练习题,1.利用所介绍的Hill2密码体制的原理,根据给定的26个英文字母的乱序表值(见下表),设计和建立Hill4密码体制的加密和解密的必要的计算机程序.设26个英文字母以下面的乱序表与Z26中的整数对应。

1)设 ,验证矩阵 能否作 为Hill4密码体制的加密矩阵.编程实现.,2.设已知一份Hill2密码体系,其中出现频率最高的双字母是RH和NI,而在明文语言中,出现频率最高的双字母为TH和HE.由这些信息按照下表给出的表值能得到什么样的加密矩阵?,3.找出元素属于Z26的所有可能的Hill2密码加密矩阵.若截获了如下一段密文,UTCQCVFOYQUVMGMGULFOEYHDUHOPEASWXTIFBAMWT,且已知它是根据下表按照Hill2密码体制加密的,你能否将其解密?,。