资源描述:
《线性代数方法建模3Hill密码的数学模型--数学建模案例分析》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、§3HiII密码的数学模型Hill密码是一种传统的密码体系,它的加密过程可以描述如卜I明文-加密器-密文-普通信道-解密器-明文在这个过程中,运用的手段是矩阵运算,具体步骤如2一、加密1、根据明文字母的表值,将明文信息用数字表示,设明文信息只需要26个英文字母A—Z(也可以不只26个,如还有数字、标点符号等),通信双方给出这26个字母表值(见卜-表)。ABCDEFGII1JKLM12345678910111213N0PQRSTUVWXYZ14151617181920212223242502、选择一个二阶可逆整数方阵A,称为Hill密码的加密
2、矩阵,它是这个加密体制的“密钥”(是加密的关键,仅通信双方掌握)。3、将明文字母依次逐对分组。Ilill密码的加密矩阵为二阶矩阵,则明文字母2个一组(可以扩充至每n个明文字母为一组)。若最后一组只有一个字付,则补充一个没有实际意义的哑字母,这样使得每一组都由2个切文字母组成。查出每个明文字母的表值,构成一个二维列向量4、4乘以得到一个新的二维列向量p=g由0的两个分量反查字母表值得到的两个字母即为密文字母。以上4步即为Hill密码的加密过程。例明文为YTCHUFAoA=2
3、,求这段明文的H订1密码。W3丿将明文相邻2个字母分为一组:YIC
4、HUFAA。授后一个字母是哑字母,它是为使最后一组的字母数为2而添加的,无实际意义。査出每对字母的表值,并构造2维列向量:,25、‘3、、9丿©1(1)将上述4个列向量左乘矩阵4,得到4个新的列向量:厂19、"33、30丿<27/(2)在反杳这4个向最对应的字母时,遇到了问题:第1个向最与第三个向最屮的43与33不是表值,处理的办法是加减26的整数倍,使其化为0-25Z间的一个整数,这称为模26运算,记为:(43)(mod26)=27/(mod26)=(3)这样,这4个新的二维列向量对应的字母为:QASXGRCC。它就是明文“YICHUF
5、A”的密文。二、解密解密过程即为上述过程的逆过程。这是在模运算下如何解方程组=0的问题。一般一个n阶方阵A可逆的充耍条件是detA0o在模26运算下矩阵可逆与一般的愆阵可逆有所不同。记整数集合Z={0,1,2,…,m-1},m为一正整数,模mnj逆定义如下:定义1对于一个元素属于集合Z的n阶方阵A,若存在一个元素属于集合Z的方阵B,使得AB=BA=E(modm)称A为模m可逆,B为A的模m逆矩阵,记为B=A~l(modm)®E(modm)的意义是,每一个元素减去m的整数倍后,可以化成单位矩阵。例如:(2752)(mod26)=E(2627丿
6、定义2对Z的一个整数a,若存在Z的一个整数b,使得ab=l(modm),称b为a的模m倒数,记作b=a~x(modm)。Z中有模26倒数的整数及其倒数见下表:a1357911151719212325a~]1921153197231151725可以证明,如果a与m无公共素数因子,则a有唯一的模m倒数。利用这点,可以证明下述命题:命题元素属于Z的方阵A模m可逆的充要条件是m和detA没冇公共素数因了。显然,所选加密矩阵必须符合该命题的条件。这里所选项的明文字母共26个,m=26,26的素数因子为2和13,所以Z上的方阵A可逆的充要条件是detA
7、(modm)不能被2和13整除。(ab设,若力满足命题的条件,不难验证:2〃丿厂db、A1=(ad-be)1(mod26)I-ca丿其l](ad-bey1是(ad-be)(mod26)的倒数。显然(cul-be)(mod26)为Z中的数。(4)这样,在模26意义下,求解方程组=0的问题即可解决:a-A^/3(mod26)例要将一段密文QASXGRCC解密,只要将上述加密过程逆转回去,即将密文按同样方式分组,查它们的表值即得:厂17、仃9、"7〕丄<24;⑶(5)(3丿根据上述命题与表值,所选加密矩阵4的行列式detA=3没有2与13这两
8、个素数因子,所以A模26可逆。川(mod26)=3」3-2、1>(mod26)=9勺-2、,01丿‘27-18、仃8、39丿<09丿(mod26)=这样,由(4)和(5)中的向最可得到(1)屮的向最,明文为YICHUFAA。三、密码的破译密码破译实际上就是破译加密矩阵A及,前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换。每个明文向量都是一•个Z上的二维向量,乘以加密矩阵A后仍为一•个Z上的二维向最。由于A为可逆矩阵,所以,如果知道了两个线性无关的二维明文向量与其对应的密文向量,就可以求出它的加密矩阵A及A"o下而以一个具体例
9、子说明这种方法。有一段密文:QJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENHo经分析是用Hill密码编译的,且这段密文的字母UCRS依次代表字