信息安全工程师教程之《古典密码》篇

      在2016 年下半年计算机技术与软件专业技术资格(水平〉考试中将开考的《信息安全工程师》，将会成为科学评价我国信息安全专业技术人员的重要手段，也将为我国培养和选拔信息安全专业技术人才，发挥重要作用。而这一课程我们主要学习的是密码学基础与应用当中的古典密码，希望通过这一课程能帮助大家更多更快地了解古典密码学。

很多人如今从近代密码学的观点来看，对于古典密码很不以为然，事实上很多古典密码也确实不安全。但一个人总不能因为学习了新知识就要把学过的旧知识扔在一旁置之不理。不管如今的密码学有多么地厉害，我们都不能忽视古典密码在历史上发挥的巨大作用。而且，古典密码中主要的代换和置换两种编码方法如今对于编制近代密码仍然有效。

古典密码主要编码方法

　　1、代替密码

　　代替密码也叫做移位密码，首先建立一个或多个密文字母表，然后用密文字母表中的字母或者字母组来代替明文字母或字母组，各字母或字母组的相对位置不变，但本身却是改变了。这样编成的密码称为代替密码。按代替所使用的密文字母表的个数可将代替密码分为单表代替密码、多表代替密码和多名代替密码。

　　以单表代替密码为例，根据下面的教程来学习一下这种密码设置规则。

　　单表代替密码又称为简单代替密码。它只使用一个密文字母表，并且用密文字母表中的-个字母来代替一个明文字母表中的一个字母。

　　设A和B分别为含n个字母的明文字母表和密文字母表:

　　A={a₀，a₁，…，a_n-1}

　　B={b₀, b₁ ,…,b_n-1}

　　定义一个由A到B的--映射: f:A→B

　　f(a_i)= b_i

　　设明文M=(m₀ ， m₁ ， …， m_n-1) ，则密文C =(f(m₀),f(m₁),… ,f(m_n-1))。由此可见，简单代替密码的密钥就是映射函数f或密文字母表B。

　　以下为几种典型的简单代替密码。

　　(1)乘法密码

　　乘法密码的映射函数为

　　f(a_i)=b_i=a_j　　j=ik mod n               (2-3)

　　其中，要求k与n互素。这是因为仅当(k， n)=1时，才存在两个整数x,y 使得xk+yn=1，才有xk=1 mod n ，才有i=xj mod n ，密码才能正确解密。

　　例如，当用英文字母表作为明文字母表而取k=13时，因为(13，26)=13≠1，便会出现:

　　f(A)=f(C)=f(E)=f(G)=f(I)=f(K)=f(M)=f(O)=f(Q)=f(S)=f(U)=f(W)=f(Y)=A

　　f(B)=f(D)=f(F)=f(H)=f(J)=f(L)=f(N)=f(P)=f(R)=f(T)=f(V)=f(X)=f(Z)=N

　　此时的密文字母表变为

　　B={A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N,A,N}

　　整个密文字母表只包含A和N两今字母，密文将不能正确解密。

　　而若选k=5，因为(5，26)=1，便得到如下的合理的密文字母表：

　　A={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}

　　B={A,F,K,P,U,Z,E,J,O,T,Y,D,I,N,S,X,C,H,M,R,W,B,G,L,Q,V}

　　(2)加法密码

　　加法密码的映射函数为

　　f(a_i)=b_i=a_j

　　j=i+k    mod n                        （2-4）

其中， a_iЄA ，k是满足0<K<N的正整数。

　　著名的加法密码是古罗马的凯萨大帝(Caesar)使用过的一种密码。Caesar密码取k=3 ，因此其密文字母表就是把明文字母表循环右移3位后得到的字母表。例如：

　　A={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}

　　B={D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A,B,C,}

　　明文MNGI WHEG AQ BVJJ DA DAIE MAN ZANG

　　密文PQJL ZKHJ DT EYMM GD GDLH PDQ CDQJ

　　(3)仿射密码

　　乘法密码和加法密码相结合便构成仿射密码。仿射密码的映射函数为

　　f (a_i)=b_i=a_j

　　j=ik₁+k₀   mod n                        (2-5)

　　其中，要求(k₁ ，n)=1,

　　0≤k₀<N,且不允许同时有K₁=1 k₀=O

　　简单代替密码很容易被破译，其原因在于只使用一个密文字母表，从而使得明文中的每一个字母都只用唯一的一个密文字母表来代替。提高代替密码强度的一种方法是采用多个密文字母表，使明文中的每一个字母都有多种可能的字母来代替。

　　构造d个密文字母表:

　　B_j={B_j0,B_j1,B_jn-1}　　 j=0,1,...,d-1

　　定义d个映射

　　f_j: A→B_j

　　f_i(a_i)=b_j1 j=ik    mod n               (2-6)

　　设密文M=(m₀,m_l, …,m_d-l,m_d,…),C=的(f₀(m₀),f_i(m_l),…,f_d-1(m_d-l ),f₀(m_d)…)。

　　由于加密用到多个密文字母表，故称为多表代替密码。多表代替密码的密钥就是这组映射函数或密文字母表。

　　最著名的多表代替密码要算16世纪法国密码学者Vigenre使用过的Vigenre密码。

Vigenre密码使用26个密文字母表，像加法密码一样，它们是依此把明文字母表循环右移0，1，2，…，25位的结果。选用一个词组或短语作密钥，以密钥字母控制使用哪一个文字母表。把26个密文字母表排在一起称为Vigenre方阵，如表2-1 所示。

　　Vigenre密码的代替规则是用明文字母在Vigenre方阵中的列和密钥字母在Vigenre方阵中的行的交点处的字母来代替该明文字母。例如，设明文字母为p，密钥字母为y，则用字母N来代替瞬文字母P。又例如:

　　明文MING CHEN WU DIAN FA DONG FAN GONG

　　密钥XING CHUI PING YE KUO YUE YONG DA JIANG LIU

　　密文JQAME OYVLC QOYRP URMHK DOAMR NP

　　Vigenre密码的解密就是利用Vigenre方阵进行反代替。

　　2、置换密码

　　置换密码也叫换位密码。把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码就是置换密码。

　　例如某明文按某一顺序排成一个矩阵，其中不足部分用θ填充，而θ是明文中不会出现的一个符号。然后按另一顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。

　　举例:

　　明文：NENG XIAN YI SHER BI QUAN FAN DONG

　　矩阵：NENGXI    选出顺序：按列

　　         ANYISH　　      

               ERBIQU

　　         ANFAND

　　         ONGθθθ 其中θ为明文中不会出现的字符，表示空。

　　密文NAEAO ENRNN NYBFG GIIAθ XSQNθ IHUDθ

　　由此可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码。置换密码的密钥就是矩阵的大小和选出顺序。置换密码比较简单，但它经不起己知明文攻击。但是，把它与其他密码技术相结合，可以得到十分有效的密码。

古典密码的破译方法

学习了几种古典密码的实例之后，下面我们继续学习古典密码的破译方法

　　1、统计分析

　　任何自然语言都有许多固有的统计特性。如果自然语言的这种统计特性在密文中有所反映，则密码分析者便可以通过分析明文和密文的统计规律而将密码破译。许多古典密码都可以用统计分析的方法破译。

随便阅读一篇英文文献，立刻就会发现，其中字母E出现的次数比其他字母都多。如果进行认真统计，并且所统计的文献的篇幅足够长，便可以发现各字母出现的相对频率十分稳定。而且，只要文献不特别专门化，对不同的文献进行统计所得的频率分布大体相同。根据各字母频率的大小可将英文字母分为几组。表2-2 描述了这一分组情况。

　　不仅单字母以相当稳当的频率出现，而且双字母组(相邻的两个字母）和三字母组(相邻的三个字母)同样如此。出现频率最高的30个双字母组依此是:

　　TH HE IN ER AN RE ED ON

　　ES ST EN AT TO NT HA ND

　　OU EA NG AS OR TI IS ET

　　IT AR TE SE HI OF

　　出现频率最高的20 个三字母组依此是:

　　THE ING AND HER ERE ENT THA NTH WAS

　　ETH FOR DTH HAT SHE ION HIS STH ERS

　　VER

　　特别值得注意的是，THE的频率几乎是排在第二位的ING的3倍，这对于破译密码是非常有帮助的。此外，统计资料还表明:

　　①英文单词以E、S、D、T为结尾的超过一半。

　　②英文单词以T、A、S、W为起始字母的约占一半。

　　以上所有这些统计数据，对于密码分析者来说都是十分有用的信息。

　　破译单代替密码的大致过程是:首先统计密文的各种统计特征，如果密文量比较多，则完成这步后便可确定出大部分密文字母:其次分析双字母、三字母密文组，以区分元音和辅音字母:最后分析字母较多的密文，在这一过程中大胆使用猜测的方法，如果猜对一个或几个词，就会大大加快破译过程。

　　2、穷举分析

    乘法密码,根据式(2-3) 可知，密钥整数k 满足条件(n ,k)=1，因此，k只有φ(n)个不同的取值。去掉k=1这一恒等情况，k的取值只有φ(n)-1种。这里φ(n)为n的欧拉函数。对于明文字母表为英文字母表的情况， k只能取3,5,7,9,11,15,17,19,21,23,25共11种不同的取值，比加法密码弱得多。

　　对于加法密码比乘法密码破译稍微难一点，根据式(2-4)可知，密钥整数k只有n-l个不同的取值。对于明文字母表为英文字母表的情况，k只有25种可能的取值。即使是对于明文字母表为8位扩展ASCII码而言，k也只有255种可能的取值。因此，只要对k的可能取值逐一穷举就可破译加法密码。

　　仿射密码的保密性能好些。但根据式(2-5)，可能的密钥也只有nφ(n)-1 种。对于明文字母表为英文字母表的情况，可能的密钥只有26x12-1=311种。这一数目对于古代密码分析者企图用穷举全部密钥的方法破译密码，可能会造成一定的困难，然而对于应用计算机进仔破译来说，这就是微不足道的了。

　　密码破译是十分复杂和需要极高智力的劳动。世界上第一台计算机一诞生便投入密码破译的应用，目前计算机已经成为密码破译的主要工具。可以预计，随着计算机科学技术的发展，计算机在密码破译中将会发挥更大的作用。

　　小编结语：通过学习以上的古典密码学，是不是觉得自己的知识又丰富了呢?其实，古典密码的设置情况和破译方法学习起来并不难，对于我们学习信息安全工程师也会有一定的帮助，日常使用起来也会逐渐得心应手，如果还是不太熟悉，还可以多看几遍哟，多看总是无害的呢。希望大家能阅读愉快！