密码的设计解密与破译

密码的设计，解码与破译密码的设计和使用至少可以追溯到四千多年前的埃及、巴比伦、罗马和希腊，历史极为久远。古代隐藏信息的方法主要有两大类：其一为隐藏信息载体，采用隐写术等；其二为变换信息载体，使之无法为一般人所理解。密码学中，信息代码被称为密码，加密前的信息被称为明文，加密后不为常人所理解的用密码表示的信息称为密文(ciphertext)，将明文转变成密文的过程被称为加密(enciphering)，其逆过程则被称为解密(deciphering)，而用以加密、解密的方法或算法则被称为密码体制(crytosystem)。记全体明文组成的集合为U，全体密文组成的集合为V，称U为明文空间，V为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合K。按数学的观点来看，加密与解密均可被看成是一种变换：取一k∈K，u∈U，令v=ku，v为明文u在密钥K下的密文，而解码则要用到K的逆变换K-1。由此可见，密码体系虽然可以千姿百态，但其关键还在于密钥的选取。随着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、……，许多相当高深的数学知识都被用上，逐步形成了（并仍在迅速发展的）具有广泛应用面的现代密码学。早期密码替代密码移位密码代数密码代替法密码采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即将明文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回，解密过程是加密过程的逆过程。在代替法加密过程中，密文字母表即代替法密钥，密钥可以是标准字母表，也可以是任意建立的。1.代替法密码明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表KLMNOPQRSTUVWXYZABCDEFGHIJ密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。混合一个字母表，常见的有两种方法，这两种方法都采用了一个密钥单词或一个密钥短语。方法1：a)选择一个密钥单词或密钥短语，例如：constructb)去掉其中重复的字母，得：construc)在修改后的密钥后面接上从标准字母表中去掉密钥中已有的字母后剩下的字母，得：明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表CONSTRUABDEFGHIJKLMPQVWXYZ在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例如，对于上例，选取特定字母k，则可得：明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表KLMPQVWXYZCONSTRUABDEFGHIJ方法2：a)选择一个密钥单词或密钥短语，例如：constructb)去掉其中重复的字母，得：construc)这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥单词的字母后剩下的字母构成d)将所得矩阵中的字母按列的顺序排出得：cugmyoahpznbiqsdjvrtekwrflx按照此方法产生的字母表称为混淆字母表。还可以使用混淆数。混淆数由以下方法产生：a)选一密钥单词或密钥短语，例如：constructb)按照这些字母在标准字母表中出现的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得：construct143675928c)自左向右选出这些数字，得到一个混淆数字组:143675928，混淆字母表由从小到大的顺序取矩阵中相应列得出。为增加保密性，在使用代替法时还可利用一些其他技巧，如单字母表对多字母表、单字母对多字母、多重代替等。2.移位密码体制移位密码采用移位法进行加密，明文中的字母重新排列，本身不变，只是位置改变了。早在4000多年前，古希腊人就用一种名叫“天书”的器械来加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同的圆筒上，才能看到正确的消息。在这里圆筒的直径起到了密钥的作用。以上移位较易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。例如，对明文：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS.以7列矩阵表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先约定的方式选出密文。例如，如按列选出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写方式，得到的密文也是不同的。当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就是钥控列序加密法。例如，用密钥单词construct对明文MATHEMATICALMODELINGISUSEFUL加密：CONSTRUCT143675928MATHEMATICALMODELINGISUSEFUL按混淆数的顺序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重复多次，只进行一次移位加密的称为一次移位法，经多次移位的则称为多次移位法代替法与移位法密码的破译对窃听到的密文进行分析时，穷举法和统计法是最基本的破译方法。穷举分析法就是对所有可能的密钥或明文进行逐一试探，直至试探到“正确”的为止。此方法需要事先知道密码体制或加密算法（但不知道密钥或加密具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表－单字母－单元代替法加密的密码，字母表的可能情况有26！种，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，只能与其它方法结合使用。统计法是根据统计资料进行猜测的。在一段足够长且非特别专门化的文章中，字母的使用频率是比较稳定的。在某些技术性或专门化文章中的字母使用频率可能有微小变化。在上述两种加密方法中字母表中的字母是一一对应的，因此，在截获的密文中各字母出现的概率提供了重要的密钥信息。根据权威资料报道，可以将26个英文字母按其出现的频率大小较合理地分为五组：I.t,a,o,i,n,s,h,r;II.e;III.d,l;IV.c,u,m,w,f,g,y,p,b;V.v,k,j,x,q,z;不仅单个字母以相当稳定的频率出现，相邻字母对和三字母对同样如此。按频率大小将双字母排列如下：th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of使用最多的三字母按频率大小排列如下：The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth统计的章节越长，统计结果就越可靠。对于只有几个单词的密文，统计是无意义的。下面介绍一下统计观察的三个结果：a)单词the在这些统计中有重要的作用；b)以e，s，d，t为结尾的英语单词超过了一半；c)以t，a，s，w为起始字母的英语单词约为一半。对于a)，如果将the从明文中删除，那么t的频率将要降到第二组中其他字母之后，而h将降到第三组中，并且th和he就不再是最众多的字母了。以上对英语统计的讨论是在仅涉及26个字母的假设条件下进行的。实际上消息的构成还包括间隔、标点、数字等字符。总之，破译密码并不是件很容易的事。2.希尔密码代替密码与移位密码的一个致命弱点是明文字符和密文字符有相同的使用频率，破译者可从统计出来的字符频率中找到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字符间的一一对应。1929年，希尔利用线性代数中的矩阵运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。为了便于计算，希尔首先将字符变换成数，例如，对英文字母，我们可以作如下变换：ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789101112131415161718192021222324250将密文分成n个一组，用对应的数字代替，就变成了一个个n维向量。如果取定一个n阶的非奇异矩阵A（此矩阵为主要密钥），用A去乘每一向量，即可起到加密的效果，解密也不麻烦，将密文也分成n个一组，同样变换成n维向量，只需用A逆去乘这些向量，即可将他们变回原先的明文。定理1,若使得(mod26)，则必有=1，其中为与26的最大公因子。{0,...,25}a{0,25}a11aaaa11gcd{a,26}gcd{a,26}a在具体实施时，我们很快会发现一些困难：(1)为了使数字与字符间可以互换，必须使用取自0—25之间的整数(2)由线性代数知识，，其中为A的伴随矩阵。由于使用了除法，在求A的逆矩阵时可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。det(A)AA1Aa13579111517192123251a1921153197231151725例1取a=3用希尔密码体系加密语句THANKYOU步1将THANKYOU转换成（20，8，1，14，11，25，15，21）步2每一分量乘以3并关于26取余得（8，24，3，16，7，23，19，11）密文为HXCPGWSK现在我们已不难将方法推广到n为一般整数的情况了,只需在乘法运算中结合应用取余，求逆矩阵时用逆元素相乘来代替除法即可。例2取A=则(具体求法见后),用A加密THANKYOU,再用对密文解密013201A1981A82014125112115用矩阵A左乘各向量加密（关于26取余）得2410163239115得到密文JXCPIWEK解:(希尔密码加密)用相应数字代替字符，划分为两个元素一组并表示为向量：（希尔密码解密）用A-1左乘求得的向量，即可还原为原来的向量。(自行验证)希尔密码是以矩阵法为基础的，明文与密文的对应由n阶矩阵A确定。矩阵A的阶数是事先约定的，与明文分组时每组字母的字母数量相同，如果明文所含字数与n不匹配，则最后几个分量可任意补足。A-1的求法方法1利用公式，例如，若取，则,,(mod26)，即方法2利用高斯消去法。将矩阵(A,E)中的矩阵A消为E，则原先的E即被消成了A-1，)det(1AAA01A323)det(A9)det(1A039A112011A98如0132，0110(用9乘第二行并取同余)0112，0190第一行减去第二行的2倍并取同余，得0110，0198左端矩阵已化为单位阵，故右端矩阵即为A-1希尔密码系统的解密依赖于以下几把钥匙（key）：Key1矩阵A的阶数n，即明文是按几个字母来划分的。Key2变换矩阵A，只有知道了A才可能推算出Key3明文和密文由字母表转换成n维向量所对应的非负整数表（上面，为方便起见，我们采用了字母的自然顺序）。希尔密码体系为破译者设置了