《密码的设计、解密与破译资料》由会员分享，可在线阅读，更多相关《密码的设计、解密与破译资料（28页珍藏版）》请在金锄头文库上搜索。
1、 密码的设计，解码与破译密码的设计，解码与破译 密码的设计和使用至少可以追溯到四千多年前的埃及、巴比 伦、罗马和希腊，历史极为久远。古代隐藏信息的方法主要 有两大类： 其一为隐藏信息载体，采用隐写术等； 其二为变换信息载体，使之无法为一般人所理解。 密码学中，信息代码被称为密码，加密前的 信息被称为明文，加密后不为常人所理解的 用密码表示的信息称为密文(ciphertext)， 将明文转变成密文的过程被称为加密 (enciphering)，其逆过程则被称为解密 (deciphering)，而用以加密、解密的方法 或算法则被称为 密码体制(crytosystem)。 记全体明文组成的集合 为U，
2、全体密文组成的集合为V，称U 为明文空间，V为密文空间。加密常利用某一被称为密钥的东 西来实现，它通常取自于一个被称为密钥空间的含有若干参数 的集合K。按数学的观点来看，加密与解密均可被看成是一种 变换：取一kK，uU，令 v =k u ，v为明文u在密钥K下的 密文，而解码则要用到K的逆变换K-1。由此可见，密码体系虽 然可以千姿百态，但其关键还在于密钥的选取。 随着计算机与网络技术的迅猛发展，大量各具特色的密码体系 不断涌现。离散数学、数论、计算复杂性、混沌、，许多 相当高深的数学知识都被用上，逐步形成了（并仍在迅速发展 的）具有广泛应用面的现代密码学 。 早期密码早期密码 替代密码 移位
3、密码 代数密码 代替法密码采用另一个字母表中的字母来代替明文中的字母 ，明文字母与密文字母保持一一对应关系，但采用的符号改 变了。加密时，把明文换成密文，即将明文中的字母用密文 字母表中对应位置上的字母取代。解密时，则把密文换成明 文，即把密文中的字母用明文字母表中对应位置上的字母代 回，解密过程是加密过程的逆过程。在代替法加密过程中， 密文字母表即代替法密钥，密钥可以是标准字母表，也可以 是任意建立的。 1.代替法密码 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ 密钥常用一密钥单词或密钥短语生成混淆字母表
4、。密钥单词 或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。 混合一个字母表，常见的有两种方法，这两种方法都采用了 一个密钥单词或一个密钥短语。 方法1： a)选择一个密钥单词或密钥短语，例如：construct b)去掉其中重复的字母，得：constru c)在修改后的密钥后面接上从标准字母表中去掉密钥中已有的 字母后剩下的字母，得： 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ 在设计密钥时，也可在明文字母表中选择一个特定字母，然后 从该特定字母开始写密钥单词将密钥单词隐藏于其中。例如， 对于上例，
5、选取特定字母k，则可得： 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ 方法2： a)选择一个密钥单词或密钥短语，例如： construct b)去掉其中重复的字母，得：constru c)这些字母构成矩阵的第一行，矩阵的后续各行由标准字母 表中去掉密钥单词的字母后剩下的字母构成 d)将所得矩阵中的字母按列的顺序排出 得： cugmyoahpznbiqsdjvrtekwrflx 按照此方法产生的字母表称为 混淆字母表。 还可以使用混淆数。混淆数由以下方法产生： a)选一密钥单词或密钥短语，例如：constru
6、ct b)按照这些字母在标准字母表中出现的相对顺序给它们编号， 对序列中重复的字母则自左向右编号，得 ：construct 143675928 c)自左向右选出这些数字，得到一个混淆数字组:143675928， 混淆字母表由从小到大的顺序取矩阵中相应列得出。 为增加保密性，在使用 代替法时还可利用一些 其他技巧，如单字母表 对多字母表、单字母对 多字母、多重代替等。 2.移位密码体制 移位密码采用移位法进行加密，明文中的字母重新排列，本 身不变，只是位置改变了。 早在4000多年前，古希腊人就用一种名叫“天书”的器械来 加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径 确定的圆筒上，明文逐
7、行横写在纸带上，当取下纸带时，字 母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要 将纸带重新绕在直径与原来相同的圆筒上，才能看到正确的 消息。在这里圆筒的直径起到了密钥的作用。 以上移位较易被人破译，为打破字母表中原有的顺序还可采用 所谓路线加密法，即把明文字母表按某种既定的顺序安排在一 个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表 。 例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以7列矩阵表示如下： THEHIST ORYOFZJ UISMORE THANONE HUNDRED YEARS 再按事先约定的方
8、式选出密文。例如，如按列选出，得到密 文：touthyhrihueeysanahomndrifoorsszrnetjeed 使用不同的顺序进行编写和选择，可以得到各种不同的路线 加密体制。对于同一明文消息矩阵，采用不同的抄写方式， 得到的密文也是不同的。 当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加 密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用 的字母来填满矩阵。 移位法也可和代替法结合使用，并使用约定的单词或短语作 密钥，以进一步加强保密性，这就是钥控列序加密法。 例如，用密钥单词 construct对明文MATHEMATICAL MODELING IS USEFUL加密：
9、CONSTRUCT 1 4 36 7 5 928 MATHEMATI CALMODELI NGI S USEFU L 按混淆数的顺序选出各列，得到密文： MCNLTLFTLIAAGMDSHMSEOSIIUAEE 移位法的使用可重复多次，只进行一次移位加密的称为一 次移位法，经多次移位的则称 为多次移位法 代替法与移位法密码的破译 对窃听到的密文进行分析时，穷举法和统计法是最基本的破 译方法 。 穷举分析法 就是对所有可能的密钥或明文进行逐一试探， 直至试探到“正确”的为止。此方法需要事先知道密码体制或 加密算法（但不知道密钥或加密具体办法）。破译时需将猜 测到的明文和选定的密钥输入给算法，产生
10、密文，再将该密 文与窃听来的密文比较。如果相同，则认为该密钥就是所要 求的，否则继续试探，直至破译。以英文字母为例，当已知 对方在采用代替法加密时，如果使用穷举字母表来破译，那 么对于最简单的一种使用单字母表单字母单元代替法加 密的密码，字母表的可能情况有26！种，可见，单纯地使 用穷举法，在实际应用中几乎是行不通的，只能与其它方法 结合使用。 统计法是根据统计资料进行猜测的。在一段足够长且非特别 专门化的文章中，字母的使用频率是比较稳定的。在某些技 术性或专门化文章中的字母使用频率可能有微小变化。 在上述两种加密方法中字母表中的字母是一一对应的，因此， 在截获的密文中各字母出现的概率提供了重
11、要的密钥信息。根 据权威资料报道，可以 将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,a s,or,ti,is,er,it,ar,te,se,hi,of 使用最多的三字母按频率大小排列如下： The,ing,and,her,
12、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个字母的假设条件 下进行的。实际上消息的构成还包括间隔、标点、数字 等字符。总之，破译密码并不是
13、件很容易的事。 2.希尔密码 代替密码与移位密码的一个致命弱点是明文字符和密文字符 有相同的使用频率，破译者可从统计出来的字符频率中找到 规律，进而找出破译的突破口。要克服这一缺陷，提高保密 程度就必须改变字符间的一一对应。 1929年，希尔利用线性代数中的矩阵运算，打破了字符间的 对应关系，设计了一种被称为希尔密码的代数密码。为了便 于计算，希尔首先将字符变换成数，例如，对英文字母，我 们可以作如下变换： ABC DE FG H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1
14、9 20 21 22 23 24 25 0 将密文分成 n个一组，用对应的数字代替，就变成了一个个n 维向量。如果取定一 个n阶的非奇异矩阵A（此矩阵为主要 密钥）， 用A去乘每一向量，即可起到加密的效果，解密也 不麻烦，将密文也分成n个一组，同样变换 成n维向量，只需 用A逆去乘这些向量，即可将他们变回原先的明文。 定理1 ,若 使得 (mod26)，则必有 =1，其 中 为 与26的最大公因子。 在具体实施时 ，我们很快会发现一些困 难： (1) 为了使数字与字符间可以互换，必须 使用取自025之间的整数 (2)由线性代数知识， ，其中 为A的伴随矩阵。由于使用了除法， 在求A的逆矩阵时可
15、能会出现分数。不 解决这些困难，上述想法仍然无法实现 。解决的办法是引进同余运算，并用乘 法来代替除法，（如同线性代数中用逆 矩阵代替矩阵除法一样）。 1 3 5 7 9 11 15 17 19 21 23 25 1 9 21 15 3 19 7 23 11 5 17 25 例1 取a = 3用希尔密码体系加密语句 THANK YOU 步1 将THANK YOU转换成 （20 ，8，1，14，11，25，15，21） 步2 每一分量乘以 3并关于26取余得 （8 ，24，3，16，7，23，19，11） 密文为HXCPG WSK 现在我们已不难将方法推 广到n为一般整数 的情况了,只需在乘法运算中结合应用取余， 求逆矩阵时用逆元素相乘来代替除法即可。 例2 取A = 则 (具体求法见 后),用A加密THANK YOU,再用 对密文解密 用矩阵阵A左乘各向量加密（关 于26取余）得 得到密文 JXCPI WEK 解:(希尔密码码加 密)用相应应数字代替字符，划分为为两个元素一 组组并表示为为向量： （希尔密码解密） 用A-1左乘求得的向量，即可还原为原来的向量。 (自行验证) 希尔密码是以矩阵 法为基础的，明文与密文的对应由n阶矩 阵A确定。矩阵A的阶数是事先约定的，与明文分组时每组字 母的字母数量相同，如果明文所含字数与n
