73密码与解密模型

7.3密码和解密模型密码的历史密码的作用密码模型西元前404年斯巴达国(今希腊)北路军司令莱山得在征服雅典之后,信使赶到,献上了一条皮带,上面有文字,通报敌军欲断其归路的企图.4世纪希腊出现了隐蔽书信内容的初级密码.8世纪古罗马教徒为传播新教,创造了「圣经密码」.中世纪末叶，西班牙的平民百姓与贵族阶级的青年男女,为了冲破封建制度对自由恋爱的束缚,不得不采取种种秘密通信的形式,从而导致了各种原始密码的产生.密码的历史2020/1/121200年罗马教皇政府和意大利世俗政府开始有系统地使用密码.19世纪随着资本主义的发展和资产阶级相互斗争的需要,出现了无线电密码通信.密码的作用1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。2020/1/12密码学名词明文需要采用某种方法对其进行变换来隐蔽它所载荷的信息或字符串加密过程将明文变换成另一种不能被非授权者所理解的隐蔽信息的消息或字符串的过程明文经过加密过程的变换所得的消息或密文字符串将明文变为密文的变换加密变换解密变换将密文变为明文的变换密钥加（解）密变换所使用的参数2020/1/12置换密码是一个最容易实现而且最为人们熟悉的密码。只需要把每个字母由其它的字母来替换而形成密文。而替换的规则是随机的或者是系统的。凯撒密码是首先将讯息(明码)中的字母,用不同的字母代替。他的做法是系统地将字母向后推三个位置。a-Db-Ec-Fd-Ge-Hf-Ig-Jh-Ki-Lj-Mk-Nl-Om-Pn-Qo-Rp-Sq-Tr-Us-Vt-Wu-Xv-Yw-Zx-Ay-Bz-C置换密码2020/1/12关于模运算（mod26）模m等价设a,b为两个整数,若Zkkmba,称a模m等价于b，记作)(modmba剩余集{0,1,2,,1}mZm称为模m的剩余集运算律)(mod)(mod)(mod)(modmmbmamba设a,b为两个整数，则模m倒数设maZ，若存在mZb使得1(mod),abm则称a模m可逆（有模m倒数），记作)(mod1mab命题模26倒数表25175112371931521912523211917151197531a–1(mod26)a整数a模m可逆a与m无公共质数因子gcd(,)1am2020/1/12thismessageistopsecretWKLVPHVVDJHLVWRSVHFUHWwearethechampionZHDUHWKHFKDPSLRQ如果26个字母被从1到26编号，用p表示明文中某个字母的编号，用c表示相应的密文中字母的编号，则凯撒密码就可以由如下的模型给出c=p+3(Mod26)其中的数3就是凯撒密码的秘钥，更一般的形式由下面的公式给出c=p+k(Mod26)其中1≤k≤25.称这种密码为移位置换密码，k称为移位因子.2020/1/12仿射变换密码上面移位置换密码的一个简单变种就是仿射变换密码，其数学表示为(mod)capbm在上面例子移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，如A和B对应的密文字母分别为D和E,但在仿射变换下，对应的密文字母分别为H和K，它们有3个字母的间隔(a=3))26(mod53pc其中自然数a必须与模m互素2020/1/121111(mod),1(mod),,()(mod)apcbmamaaamapacbm仿射变换的解密公式可通过求解同余方程得到记整数关于模的同余逆为即对上式两边同乘得2020/1/12例假设下面是仿射变换加密的，试破译此文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHKFSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS假设此问题由26个英文字母组成，取m=26.由于与26互素，a有12种不同的取法，b有26种不同的取法，所以仿射变换有12*26=312种。可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母对应。在密文中在平常统计中F：出现12次E：出现频率13.04%R：出现12次T：出现频率13.04%S：出现9次Z：出现频率0.08%K：出现8次2020/1/12-1(5)(4),(17)(19),54(mod26)1719(mod26)1215(mod26)a1512(mod26)712(mod26)6(mod26)FERTababa（1）如令对应对应得同余式这样有：所以：a=6与26不互素，所以无法对密文解密。2020/1/12-1(17)(4),(18)(19),174(mod26)1819(mod26)115(mod26)a151(mod26)71(mod26)7(mod26)17-47(mod26)11(mod26)15(mod26)715(mod26)159(mod26)RESTabababcppc（2）如令对应对应得同余式这样有：所以：a=7我们可得到加密公式:解密公式:2020/1/12GTGAERCSGTKESRE……RKLGUGXDERTMMT利用上述解密公式对密文进行解密得到：这是一串没有意义的字符串，解密失败2020/1/12最后破译文为ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON破译成功(3)如令R(17)对应E(4)，K(10)对应T(19)，得同余式17=4a+b(mod26)10=19a+b(mod26),我们可以得到加密公式：c=3p+5(mod26),解密公式：p=3-1(c-5)(mod26)=9(c-5)(mod26)=9c+7(mod26)2020/1/12多重图系统Hill密码中所用的数学手段是矩阵运算。加密过程：1）将英文的26个字母、空格和必要的标点符号与1到29之间的整数建立一一对应关系，称为字符的表值，然后根据明文字符的表值，将明文信息用数字表示。设通讯双方给出这29个字符的表值如下：ABCDEFGHIGKLMNO123456789101112131415PQRSTUVWXYZ空格？！16171819202122232425262728292020/1/122）选择一个n阶可逆整数方阵A，称为Hilln密码的加密矩阵，它是加密体制的“密钥”，是加密的关键，仅通讯双方掌握。3）将明文字母分组。Hill2使用的是二阶矩阵，所以将明文字母每2个一组（可以推广至Hilln密码），若最后仅有一个字母，则补充一个没有实际意义的哑字母。这样使得每组都有2个字母，查出每个字母的表值，构成一个二维列向量。4）令，由的两个分量反查字符表值得到的两个字母即为密文字母。A2020/1/12解密过程：加密过程的逆过程。字符（明文）表值一组数分组向量A左乘向量反查表值密文ＨILL密码的数学模型2020/1/12例：设明文为“MEET求这段明文的Hill2密文。5021A将明文分为：MEET135,520A2345,25100292316,,2513对应的列向量为左乘矩阵后的向量关于取模对应密文WYPM2020/1/1211.{1,2,,}.ABABBAI(modm)AmBAm(mod)mmmmZmZnZnBAm定义设为一正整数，记整数集合对于一个元素属于的阶方阵，若存在一个元素属于的阶方阵，使得称为模可逆。为的模逆矩阵，记为1det()det1AA(mod)mmZAmmAAZAmmAm命题2.元素属于的方阵模可逆的充要条件是：和没有公共的素数因子。推论2.若方阵的每个元素属于，而且则是模可逆的，且它的逆矩阵就是的模逆矩阵。2020/1/12dcbaA)(mod)(11macbdbcadA设方阵满足命题2的条件,容易验证11()(mod)adbcadbcmAmAm其中是关于模的同余逆。于是方程组在模意义下的解为2020/1/12对上面例子,det(A)=5,它与29互素，所以满足2的条件，故A关于模29的逆为1152525(mod29)6(mod29)(521)01013012117(mod29)(mod29)0606A因为的同余逆1117(mod)(mod29)06Am解密公式为：2020/1/12对密文WYPM进行解密得到1172344813(mod29)06251505117162375(mod29)06137820即明文MEET2020/1/12一个简单实例明文：Ourmarshalwasshot分组：ourmarshalwasshott补充哑元对应向量1518119123198202113188121191520加密：左乘加密矩阵3021A直接结果574437352525573860633954243635745602020/1/125181192525512811132241035198密文向量密文ekrmkbixyjyceelshh解密求得解密矩阵118(mod26)09A左乘密文向量再取模即可求得明文向量，从而得出明文结论使用Hill密码时的加解密矩阵应该模26可逆11(mod26)dbAAca2020/1/12HILLn密码的破译关键在于求出解密矩阵（解密密钥）只要破译出n组线性无关的密文向量1133112244,ababAAabab若有131312424aabbAaabb1131312424aabbAaabb2020/1/12一个破译例子甲方截获了一段密文：OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH经分析这段密文是用HILL2密码编译的，且这段密文的字母UCRS依次代表了字母TACO，若明文字母的表值如前，试破译这密文的内容？2118(319URQCS密文矩阵)203()115TCPAO明文矩阵关系根据解密原理1(mod26)PAQ11(mod26)APQ2020/1/12计算解密密钥A－111111203211811531920319183451153213712977262975565445539(mod26)(mod26)(mod26)(mod26)(mod26)0445511709APQ2020/1/12破译密文向量1523902421952211016192112