3保障与安全密码学084.pptVIP

网络工程专业08级 * 与26互素的数为1，3，5，7，9，11，15，17，19，21，23，25（12个） 因此，模为26的仿射密码的密钥空间为12×26=312 在Z/(26)的情形下，与26互素的数的元的乘法逆为 1-1=1 3-1 =9(3×9=27=26+1) 5-1 =21(5×21=105=26×4+1) 7-1 =15(7×15=105=26×4+1) 11-1 =19(11×19=209=26×8+1) 17-1 =23(17×23=391=26×15+1) 25-1 =25（625=25×25=26×24+1） 网络工程专业08级 * 6 Hill密码（1929） Hill cipher was developed by the mathematician Lester Hill in 1929. 基于矩阵的线性变换: K是一个m?m矩阵,在Z/(26)上可逆,即存在K-1使得: KK-1 = I (在Z/(26)) 对每一个k∈ K,定义ek(x)=xK (mod 26) 和 dk(y)=yK-1 (mod 26) 注：明文与密文都是 m元的向量 （x1, x2 …, xm ); (y1, y2,…,ym)， 网络工程专业08级 * 定理 设K=(k i,j)为一个定义在zn上的m?m矩阵。若K在zn上可逆，则有 K-1 = (detK)-1 k*，这里k*为K矩阵的伴随矩阵。 推论 设矩阵 为一个定义在zn上的矩阵。 网络工程专业08级 * Hill密码的例子-i 例子：当 m=2时，明文元素x=(x1,x2),密文元素 y=(y1,y2) K= 若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于 （9,20）,（11,24）,有 （9,20） (mod 26)=(99＋60,72＋140）(mod 26)=（3,4） 且（11,24 ） ＝(121＋72,88＋168) ＝（11,22） 于是对 july加密的结果为DELW。 (y1,y2)=(x1,x2) K 网络工程专业08级 * 转轮机 上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟·谢尔比乌斯发明的Enigma 密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在下图中显示了6条），把键盘的信号对应到显示器不同的小灯上去。在图中可以看到，如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样地我们看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果我们在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一——简单代换密码。 网络工程专业08级 * 转轮机 网络工程专业08级 * 转轮机 不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。右图表示了连续键入3个b的情况。 网络工程专业08级 * 转轮机 当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。 为使机器更安全，可以把几种转轮和移动的齿轮结合起来。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。 网络工程专业08级 * 转轮机 德国人为了战时使用，大大加强了其基本设计，军用的Enigma由3个转轮，从5个转轮中选取。转轮机中还有一块稍微改名明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次，结构如图所示。 网络工程专业08级 * 转轮机 于是转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：三个转子不同的方向组成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种；于是一共有17576*6*100391791500，大约为10000000000000000，即一亿亿种可能性。 但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父——图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击