1、1/67第第2 2章章 古典密码技术古典密码技术 古典密码技术古典密码技术 替代密码替代密码 置换密码置换密码 周期置换密码周期置换密码 列置换密码列置换密码 转轮机密码转轮机密码 古典密码的统计分析古典密码的统计分析 单表替代密码分析单表替代密码分析 多表替代密码分析多表替代密码分析 对对HillHill密码的已知明文分析密码的已知明文分析 2/67第第2 2章章 古典密码技术古典密码技术2.1 2.1 替代密码替代密码 替代是古典密码中用到的最基本的处理技巧之一替代是古典密码中用到的最基本的处理技巧之一 ； 替代密码是指先建立一个替换表，加密时将需要加密替代密码是指先建立一个替换表，加密时
2、将需要加密的明文依次通过查表，替换为相应的字符，明文字符的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文，被逐个替换后，生成无任何意义的字符串，即密文，替代密码的密钥就是其替换表替代密码的密钥就是其替换表 ； 根据密码算法加解密时使用替换表多少的不同，替代根据密码算法加解密时使用替换表多少的不同，替代密码又可分为单表替代密码和多表替代密码。密码又可分为单表替代密码和多表替代密码。 单表替代密码的密码算法加解密时使用一个固定的替单表替代密码的密码算法加解密时使用一个固定的替换表；换表； 多表替代密码的密码算法加解密时使用多个替换表。多表替代密码的密码算法
3、加解密时使用多个替换表。 3/67第第2 2章章 古典密码技术古典密码技术2.1.1 2.1.1 单表替代密码单表替代密码 单表替代密码对明文中的所有字母都使用一个固定的映单表替代密码对明文中的所有字母都使用一个固定的映射（明文射（明文字母表到密文字母表）。字母表到密文字母表）。 设设Aa0, a1, an-1为包含了为包含了n n个字母的明文字母表；个字母的明文字母表； Bb0, b1, bn-1 为包含为包含n n个字母的密文字母表，单表替个字母的密文字母表，单表替代密码使用了代密码使用了A A到到B B的映射关系：的映射关系： f：AB， f ( ai ) bj 一般情况下，一般情况下，
4、f 是一一映射，以保证加密的可逆性。是一一映射，以保证加密的可逆性。加密变换过程就是将明文中的每一个字母替换为密文字母加密变换过程就是将明文中的每一个字母替换为密文字母表的一个字母。而单表替代密码的密钥就是映射表的一个字母。而单表替代密码的密钥就是映射f f或密文或密文字母表。字母表。 经常密文字母表与明文字母表的字符集是相同的，这时经常密文字母表与明文字母表的字符集是相同的，这时的密钥就是映射的密钥就是映射f。下面给出几种典型的单表替代密码。下面给出几种典型的单表替代密码。 4/67第第2 2章章 古典密码技术古典密码技术 一般单表替代密码一般单表替代密码 一般单表替代密码的原理是以一般单表
5、替代密码的原理是以2626个英文字母集合上的一个置换个英文字母集合上的一个置换为为密钥，对明文消息中的每个字母依次进行变换。密钥，对明文消息中的每个字母依次进行变换。 可描述为：明文空间可描述为：明文空间M M和密文空间和密文空间C C都是都是2626个英文字母的集合，密个英文字母的集合，密钥空间钥空间K=：Z26Z26|是置换是置换，是所有可能置换的集合。，是所有可能置换的集合。 对任意对任意K K，定义，定义: : 加密变换：加密变换：e( (m)=)=( (m)=)=c 解密变换：解密变换：d(c) = -1(c)=m， -1是是的逆置换。的逆置换。 【例例2.12.1】设置换设置换的对
6、应关系如下：的对应关系如下： 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 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 q w e r t y u i o p a s d f g h j k l z x c v b n m q w e r t y u i o p a s d f g h j k l z x c v b n m 试用单表替代密码以试用单表替代密码以为密钥对明文消息为密钥对明文消息messagemessage加密，然后写出逆加密，然后写出逆置换置换 ，并对密文解密。
7、，并对密文解密。 解：以解：以为密钥用单表替代密码对明文消息为密钥用单表替代密码对明文消息messagemessage加密，所得加密，所得 密文消息为：密文消息为： (m) (e) (s) (s) (a) (g) (e)=dtllqut 2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）5/67第第2 2章章 古典密码技术古典密码技术 一般单表替代密码算法特点：一般单表替代密码算法特点： 密钥空间密钥空间K很大，很大，|K|=26!=41026 ，破译者穷举搜索计算不可行，破译者穷举搜索计算不可行，1微秒试微秒试一个密钥，遍历全部密钥需要一个密钥，遍历全部密钥需要1013 年。年。
8、移位密码体制是替换密码体制的一个特例，它仅含移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。个置换做为密钥空间。 密钥密钥不便记忆。不便记忆。 针对一般替换密码密钥针对一般替换密码密钥不便记忆的问题，又衍生出了各种形式单表替代密码不便记忆的问题，又衍生出了各种形式单表替代密码。移位密码移位密码 明文空间明文空间M、密文空间、密文空间C都是和密钥空间都是和密钥空间K满足满足 即把即把26个英文字母与整数个英文字母与整数0，1，2，25一一对应，如表一一对应，如表2.1所示。所示。 260,1,2,.,25PCKZ2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）表表
9、2.1 字母数字映射表字母数字映射表6/67第第2 2章章 古典密码技术古典密码技术加密变换，加密变换，E=E:Z26Z26, Ek (m) = m + k (mod26)| mM, kK 解密变换，解密变换，D=D:Z26Z26, Dk (c) = ck (mod26)| cC, kK 解密后再把解密后再把Z26中的元素转换英文字母。中的元素转换英文字母。 显然，移位密码是前面一般单表替代密码的一个特例。当移显然，移位密码是前面一般单表替代密码的一个特例。当移位密码的位密码的 密钥密钥k=3时，就是历史上著名的凯撒密码（时，就是历史上著名的凯撒密码（Caesar）。根据其加密函数特。根据其加
10、密函数特 点，移位密码也称为加法密码。点，移位密码也称为加法密码。l 仿射密码仿射密码 仿射密码也是一般单表替代密码的一个特例，是一种线性仿射密码也是一般单表替代密码的一个特例，是一种线性变换。仿射密码的明文空间和密文空间与移位密码相同，但密变换。仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为钥空间为 K=(k1，k2)| k1，k2Z26，gcd(k1，26)=1 对任意对任意mM，cC，k = (k1，k2)K，定义加密变换为定义加密变换为 c = Ek (m) = k1 m +k2 (mod 26)相应解密变换为：相应解密变换为： m = Dk (c) = k11 (ck2)
11、(mod 26)2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）7/67第第2 2章章 古典密码技术古典密码技术 相应解密变换为：相应解密变换为： 其中，其中， 。很明显，很明显，k1=1时即为移位密码，而时即为移位密码，而k2=1则称为乘法则称为乘法 密码。密码。 【例例2.32.3】设明文消息为设明文消息为chinachina，密钥，密钥 试用仿射密码对其进行试用仿射密码对其进行 加密，然后再进行解密。加密，然后再进行解密。 解：利用扩展的欧几里德算法（参见附录解：利用扩展的欧几里德算法（参见附录A.1.2A.1.2）可计算出）可计算出 加密变换为：加密变换为： 解密变换为：解
12、密变换为： 明文明文消息对应的数字依次为消息对应的数字依次为2，7，8，13，0，用仿射密码对明文进行加密，用仿射密码对明文进行加密 如下：如下： 22207213()98222 mod 2613215022kunEmwcpc1111mod26k k113k1,2()(9,2)kk k2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）12( )(mod26)92(mod26)kmmmkkE 112( )()(mod26)3 (2)(mod26)(36)(mod26)kcccckkD 12()(mod26)kmckD1（c）=k8/67第第2 2章章 古典密码技术古典密码技术 密文消息
13、为密文消息为unwpcunwpc。而解密过程如下：。而解密过程如下： 即恢复明文消息为即恢复明文消息为chinachina。 仿射密码要求仿射密码要求(k1, 26)=1 ，否则就会有多个明文字母对应，否则就会有多个明文字母对应一个密文字母的情况。由于与一个密文字母的情况。由于与26互素的整数有互素的整数有12个，故仿射密码密钥空间大个，故仿射密码密钥空间大小为小为|K|=1226=312。 若将仿射密码的加密函数换为多项式函数时，即为多项式密码若将仿射密码的加密函数换为多项式函数时，即为多项式密码。l 密钥短语密码密钥短语密码 选用一个英文选用一个英文短语或单词串作为密钥，去掉其中重复的字母
14、得到一个无短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构造出一个字母替代表。如密钥为可构造出一个字母替代表。如密钥为key时，替代表如表时，替代表如表2.2所示。所示。 20621367()32268mod 2615613260kchDmina2.1.1 2.1.1 单表替代密码（续）单表替代密码（续）9/67第第2 2章章 古典密码技术古典密码技术 表表2.2 2.2 密钥为密钥为keykey的单表替代密码的单表替代密码 当选择上面的密钥当选择上面的密钥
15、进行加密时，若明文为进行加密时，若明文为“china”，则密文为，则密文为“yfgmk”。 显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语的情况时，密钥短语密码最多可能有的情况时，密钥短语密码最多可能有26!=41026个不同的替换表个不同的替换表。2.1.2 2.1.2 多表替代密码多表替代密码 单表替代密码表现出明文中单字母出现的频率分布与密文中相同，单表替代密码表现出明文中单字母出现的频率分布与密文中相同， 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现多表替代密码使用从明文字母到密文字母的多个
16、映射来隐藏单字母出现 的频率分布，的频率分布，每个映射是简单替代密码中的一对一映射多表替代密码将每个映射是简单替代密码中的一对一映射多表替代密码将 明文字母划分为长度相同的消息单元，称为明文明文字母划分为长度相同的消息单元，称为明文分组分组，对明文成组地进，对明文成组地进 行替代，同一个字母有不同的密文，改变了单表替代密码中密文的唯一行替代，同一个字母有不同的密文，改变了单表替代密码中密文的唯一 性，使密码分析更加困难。性，使密码分析更加困难。 10/67第第2 2章章 古典密码技术古典密码技术 多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉多表替代密码的特点是使用了两个或两个以
17、上的替代表。著名的维吉尼亚密码和尼亚密码和HillHill密码等均是多表替代密码。密码等均是多表替代密码。1.1.维吉尼亚密码维吉尼亚密码 维吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移维吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移密码体制相似，但密码体制相似，但维吉尼亚密码的密钥是动态周期变化的维吉尼亚密码的密钥是动态周期变化的。 该密码体制有一个参数该密码体制有一个参数n n。在加解密时，同样把英文字母映射为。在加解密时，同样把英文字母映射为0 02525的数字再进行运算，并按的数字再进行运算，并按n n个字母一组进行变换。明文空间、密文空间及密个字母一组进行变
18、换。明文空间、密文空间及密钥空间都是长度为钥空间都是长度为n n的英文字母串的集合，因此可表示的英文字母串的集合，因此可表示 加密变换定义如下：加密变换定义如下： 设密钥设密钥 k=(k1,k2,kn), , 明文明文m=(m1,m2,mn), , 加密变换为加密变换为： Ek(m)=(c1,c2,cn), , 其中其中ci(mi + ki)(mod26)，i =1,2,n 对密文对密文 c=(c1,c2,cn), , 解密变换为：解密变换为： Dk(c)=(m1,m2,mn), , 其中其中 mi=(ci ki)(mod26)，i =1,2,n2 6nPCKZ2.1.2 多表替代密码多表替代
19、密码（续）（续） 11/67第第2 2章章 古典密码技术古典密码技术【例例2.42.4】设密钥设密钥k k =cipher=cipher，明文消息，明文消息appliedcryptosystemappliedcryptosystem， 试用维吉尼亚密码对其进行加密，然后再进行解密。试用维吉尼亚密码对其进行加密，然后再进行解密。解：由密钥解：由密钥k k=cipher=cipher，得，得n=6n=6，密钥对应的数字序列为，密钥对应的数字序列为 (2(2，8 8，1515，7 7，4 4，17)17)。然后将明文按每。然后将明文按每6 6个字母进行分组，并转换这个字母进行分组，并转换这些明文字母
20、为相应的数字，再用模些明文字母为相应的数字，再用模2626加上对应密钥数字，其加加上对应密钥数字，其加密过程如表密过程如表2.32.3所示。所示。 表表2.3 2.3 密钥为密钥为ciphercipher的维吉尼亚密码加密过程的维吉尼亚密码加密过程 密文为：密文为：cxtsmvfkgftkqanzxvocxtsmvfkgftkqanzxvo。 解密使用相同的密钥，但用模解密使用相同的密钥，但用模2626的减法代替模的减法代替模2626加法，这里加法，这里不再赘述。不再赘述。2.1.2 多表替代密码多表替代密码（续）（续） 12/672.2.希尔（希尔（HillHill）密码）密码 Hill H
21、ill密码算法的基本思想是将密码算法的基本思想是将n n个明文字母通过线性变换，将它们转换为个明文字母通过线性变换，将它们转换为n n个密文字母。解密只需做一次逆变换即可个密文字母。解密只需做一次逆变换即可。 算法的密钥算法的密钥K =K = 上的上的 可逆矩阵可逆矩阵，明文，明文M M与密文与密文C C 均为均为n n维向量，维向量，记为记为 其中，其中， 或写成或写成 解密变换则为：解密变换则为： 第第2 2章章 古典密码技术古典密码技术26Znn1111121222112()nijn nnnnnnnmckkkmckMCKkmckkk， 11 111 22122 112 2221122.m
22、 o d 2 6.m o d 2 6.m o d 2 6nnnnnnnn nnckmkmkmckmkmkmckmkmkm1(mod26).MCK(mod26)CK M2.1.2 多表替代密码多表替代密码（续）（续） 13/67第第2 2章章 古典密码技术古典密码技术 其中，其中，K 1为为K在模在模26上的逆矩阵，满足：上的逆矩阵，满足：K K 1 = K 1 K=I (mod 26) 这里这里 I 为单位矩阵。为单位矩阵。 定理定理2.12.1：假设假设A = ( ai,j) 为一个定义在为一个定义在Z26上的上的nn矩阵，若矩阵，若A 在模在模26上可上可逆，则有：逆，则有： A 1= (
23、 det A ) 1 A* (mod 26 ) ；这里；这里A*为矩阵为矩阵A的伴随矩阵的伴随矩阵在在n = 2的情况下，有下列推论：的情况下，有下列推论：假设假设 A= ，是一个是一个Z Z2626上的上的2 22 2矩阵，它的行列式：矩阵，它的行列式： 是可逆的，那么：是可逆的，那么：例如，例如， 1,11,22,12,2aaaa1,1 2,21,2 2,1detA a aa a2,21,2112,11,1(det )mod26aaAAaa11837K118det11 73 8(mod26)7724(mod26)53(mod26)137 2.1.2 多表替代密码多表替代密码（续）（续） 1
24、4/67第第2 2章章 古典密码技术古典密码技术 这时这时 ，所以，所以K K的逆矩阵为：的逆矩阵为：【例例2.52.5】设明文消息为设明文消息为goodgood，试用，试用n n2 2，密钥，密钥 的的HillHill密码对其密码对其进进 行加密，然后再进行解密。行加密，然后再进行解密。解：将明文划分为两组：解：将明文划分为两组：(g(g，o ) o ) 和和 (o(o，d )d )，即（，即（6 6，1414）和（）和（1414，3 3）。）。加密过程如下：加密过程如下： 因此，因此，goodgood的加密结果是的加密结果是wmwlwmwl。显然，明文不同位置的字母。显然，明文不同位置的字
25、母“o o”加密成加密成的密文字母不同。为了解密，由前面计算有的密文字母不同。为了解密，由前面计算有 ，可由密文解密计，可由密文解密计算出明文：算出明文：1mod 2611111118787181mod 26373112311K11837K1122118617822(mod26)371411612cmwKcmm33441181417822(mod 26)3736311cmwKcml17182311K2.1.2 多表替代密码多表替代密码（续）（续） 15/67第第2 2章章 古典密码技术古典密码技术 因此，解密得到正确的明文因此，解密得到正确的明文“goodgood”。 HillHill密码特点
26、：密码特点：u 可以较好地抑制自然语言的统计特性，不再有单字母替换的一一可以较好地抑制自然语言的统计特性，不再有单字母替换的一一 对应关系，对抗对应关系，对抗“惟密文攻击惟密文攻击”有较高安全强度。有较高安全强度。u 密钥空间较大，在忽略密钥矩阵密钥空间较大，在忽略密钥矩阵K可逆限制条件下，可逆限制条件下，|K|=26nn u 易受已知明文攻击及选择明文攻击（详见易受已知明文攻击及选择明文攻击（详见2.3节相关分析）。节相关分析）。3 3一次一密密码（一次一密密码（One Time PadOne Time Pad） 若替代码的密钥是一个随机且不重复的字符序列，这种密码则称为一若替代码的密钥是一
27、个随机且不重复的字符序列，这种密码则称为一次一密密码，因为它的密钥只使用一次。次一密密码，因为它的密钥只使用一次。 该密码体制是美国电话电报公司的该密码体制是美国电话电报公司的Joseph MauborgneJoseph Mauborgne在在19171917年为电报年为电报通信设计的一种密码，所以又称为通信设计的一种密码，所以又称为VernamVernam密码。密码。VernamVernam密码在对明文加密密码在对明文加密前首先将明文编码为（前首先将明文编码为（0 0，1 1）序列，然后再进行加密变换。）序列，然后再进行加密变换。11221718223706(mod 26)231112638
28、14mcgKmco334417182235214mod 262311116273mcoKmcd2.1.2 多表替代密码多表替代密码（续）（续） 16/67第第2 2章章 古典密码技术古典密码技术设设m=(m1 m2 m3 mi )为明文为明文, ,k=(k1 k2 k3 ki )为密钥为密钥, ,其中其中mi, ,ki (0,1), , i1, 则加密变换为：则加密变换为： c=(c1 c2 c3 ci ) ,其中其中ci mi ki , i1, 2.1.2 多表替代密码多表替代密码（续）（续） m=(m1 m2 m3 mi ) ,其中其中mi ci ki , i1, 这里为模这里为模2加法（
29、或异或运算）加法（或异或运算）解密变换为：解密变换为： 在应用在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时密码时，如果对不同的明文使用不同的随机密钥，这时Vernam密码为密码为一次一密密码。一次一密密码。 由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则制在理论上是不可破译的。但如果重复使用同一个
30、密钥加密不同的明文，则这时的这时的Vernam密码就较为容易破译。密码就较为容易破译。若敌手获得了一个密文若敌手获得了一个密文c=(c1 c2 c3 ci ) 和对应明文和对应明文m=(m1 m2 m3 mi ) 时，就很容易得出密钥时，就很容易得出密钥 k=(k1 k2 k3 ki ) ，其中，其中ki ci mi ，i1。故若重复使用密钥，该密码体制就很不安全。故若重复使用密钥，该密码体制就很不安全。17/67第第2 2章章 古典密码技术古典密码技术 实际上实际上VernamVernam密码属于序列密码，加密解密方法都使用模密码属于序列密码，加密解密方法都使用模2 2加，这使软加，这使软硬
31、件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而硬件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该密码体制要求：密码体制要求： 密钥是真正的随机序列；密钥是真正的随机序列； 密钥长度大于等于明文长度；密钥长度大于等于明文长度； 每个密钥只用一次（一次一密）。每个密钥只用一次（一次一密）。 这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难的；另外，如何生成真正
32、的随机序列也是一个现实问题。因此，人们转而寻的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻求实际上不对攻破的密码系统。求实际上不对攻破的密码系统。4 4PlayfairPlayfair密码密码 Playfair Playfair密码是一种著名的双字母单表替代密码，实际上密码是一种著名的双字母单表替代密码，实际上PlayfairPlayfair密码密码属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合。些单元转换为密文字母组合。2.1.2 多表替代密码多表替代密码（续）（
33、续） 18/67第第2 2章章 古典密码技术古典密码技术 替代时基于一个替代时基于一个5 55 5的字母矩阵。字母矩阵构造方法同密钥的字母矩阵。字母矩阵构造方法同密钥短语密码类似，即选用一个英文短语或单词串作为密钥，去掉其短语密码类似，即选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中中重复的字母得到一个无重复字母的字符串，然后再将字母表中剩下的字母依次从左到右、从上往下填入矩阵中，字母剩下的字母依次从左到右、从上往下填入矩阵中，字母I I，j j占同占同一个位置。一个位置。 例如，密钥例如，密钥K= playfair is a digram c
34、ipherK= playfair is a digram cipher，去除重复字，去除重复字母后，母后，K=playfirsdgmcheK=playfirsdgmche，可得字母矩阵如图，可得字母矩阵如图2.12.1。 图图2.1 Playfair2.1 Playfair密码字母矩阵示例密码字母矩阵示例 2.1.2 多表替代密码多表替代密码（续）（续） 19/67第第2 2章章 古典密码技术古典密码技术 对每一明文字母对对每一明文字母对P1P1、P2P2的加密方法如下：的加密方法如下：（1 1）若）若P1P1、P2P2在同一行，密文在同一行，密文C1C1、C2C2分别是紧靠分别是紧靠P1P1
35、、P2P2右右端的字母；端的字母；（2 2）若）若P1P1、P2P2在同一列，密文在同一列，密文C1C1、C2C2分别是紧靠分别是紧靠P1P1、P2P2下下方的字母；方的字母；（3 3）若）若P1P1、P2P2不在同一行，也不在同一列，则不在同一行，也不在同一列，则C1C1、C2C2是由是由P1P1、P2P2确定的矩形其它两角的字母，且确定的矩形其它两角的字母，且C1C1和和P1P1在同一行，在同一行，C2C2和和P2P2在同一行；在同一行；（4 4）若）若P1P1P2P2，则两个字母间插入一个预先约定的字母，则两个字母间插入一个预先约定的字母，如如x x，并用前述方法处理；，并用前述方法处理
36、； 如如balloonballoon，则以，则以ba lx lo on ba lx lo on 来加密。来加密。（5 5）若明文字母数为奇数，则在明文尾填充约定字母。）若明文字母数为奇数，则在明文尾填充约定字母。 算法还约定字母矩阵中第一列看做最后一列的右边一列，算法还约定字母矩阵中第一列看做最后一列的右边一列，表中第一行看做最后一行的下一行。表中第一行看做最后一行的下一行。2.1.2 多表替代密码多表替代密码（续）（续） 20/67第第2 2章章 古典密码技术古典密码技术 置换密码又称为换位密码；置换密码又称为换位密码； 置换密码通过改变明文消息各元素的相对位置，但明文消息元素本身置换密码通
37、过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不变；的取值或内容形式不变； 在前面的替代密码中，则可以认为是保持明文的符号顺序，但是将它在前面的替代密码中，则可以认为是保持明文的符号顺序，但是将它们用其它符号来替代；们用其它符号来替代； 这种密码是把明文中各字符的位置次序重新排列来得到密文的一种密这种密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。实现的方法多种多样。直接把明文顺序倒过来，然后排成固码体制。实现的方法多种多样。直接把明文顺序倒过来，然后排成固 定长度的字母组作为密文就是一种最简单的置换密码。定长度的字母组作为密文就是一种最简单的置换密码。 下
38、面再给出几种典型的置换密码算法。下面再给出几种典型的置换密码算法。2.2.1 2.2.1 周期置换密码周期置换密码 周期置换密码是将明文字符按一定长度周期置换密码是将明文字符按一定长度n n分组，把每组中的字符按分组，把每组中的字符按1 1， 2 2，n n的一个置换的一个置换重排位置次序来得到密文的一种加密方法。重排位置次序来得到密文的一种加密方法。 其中的密钥就是置换其中的密钥就是置换，在，在的描述中包含了分组长度的信息。的描述中包含了分组长度的信息。 解密时，对密文字符按长度解密时，对密文字符按长度n n分组，并按分组，并按的逆置换的逆置换 把每组字符重排把每组字符重排位置次序来得到明文
39、。位置次序来得到明文。 周期置换密码可描述为：周期置换密码可描述为：2.2 置换密码置换密码 ( Permutation Cipher )( Permutation Cipher )121/67第第2 2章章 古典密码技术古典密码技术2.2.1 2.2.1 周期置换密码周期置换密码（续）（续） 设设n n为固定的正整数，为固定的正整数，P = C = (Z26)n , K, K是由是由 11，2 2，n n 的所有的所有置换构成。对一个密钥置换构成。对一个密钥KK，定义：，定义： 加密变换：加密变换： E (m1, m2,., mn) = (m(1),., m(n) =( c1, c2,.,
40、cn) 解密变换：解密变换： ;这里1为的逆置换注意，这里的加密与解密变换仅仅用了置换，无代数运算。注意，这里的加密与解密变换仅仅用了置换，无代数运算。 12345636152411112(1)(2)( )( ,.,)(.)nnD c ccccc= (3 5 1 6 4 2)的置换密码对其进行加密，然后再对密文进的置换密码对其进行加密，然后再对密文进行解密。行解密。 解：解：密钥长度是密钥长度是6，所以按周期长度，所以按周期长度6对明文分组，对每组字对明文分组，对每组字母用密钥母用密钥 进行重排得到对应的加密结果。进行重排得到对应的加密结果。 明文分组为：明文分组为：crypto|graphy
41、，再利用置换密钥，再利用置换密钥进行加密变进行加密变换，得：换，得：E (crypto) = (ytcopr); E (graphy) = (ahgypr) 即密文消息为即密文消息为ytcoprahgypr。【例例2.7】给定给定明文为明文为cryptography，试用密钥试用密钥= 22/67第第2 2章章 古典密码技术古典密码技术 显然由加密置换可求出逆置换，显然由加密置换可求出逆置换， = =（3 6 1 5 2 43 6 1 5 2 4），根），根据密文和逆置换据密文和逆置换 即可直接明文。即可直接明文。 必须要指出的是，必须要指出的是，置换密码在实质上是置换密码在实质上是HillH
42、ill密码的特例密码的特例，下面给出，下面给出分析。分析。 给定一个集合给定一个集合11，2 2， . . . . .，nn的置换的置换，写出置换矩阵为：，写出置换矩阵为： 这时，置换矩阵是每一行和每一列都刚好有一个这时，置换矩阵是每一行和每一列都刚好有一个“1”，而其余元素为，而其余元素为“0”的稀疏矩阵。如例的稀疏矩阵。如例2.72.7的加解密置换的加解密置换=(3 5 1 6 4 2)=(3 5 1 6 4 2)， = =（3 6 1 5 2 43 6 1 5 2 4），对应的置换矩阵为：），对应的置换矩阵为：12.2.1 2.2.1 周期置换密码周期置换密码（续）（续） 11( )()
43、0ijn nijjiKkk若否则；表示仅第i行中第(i)个元素为1，其余为零。1001000000010100000000001000100010000K1001000000001100000000010010000000100K23/67第第2 2章章 古典密码技术古典密码技术 加密变换：加密变换： 解密变换：解密变换： = = 所以，置换密码实质上是输入分组的一个线性变换。所以，置换密码实质上是输入分组的一个线性变换。 2.2.1 2.2.1 周期置换密码周期置换密码（续）（续） 1,2,(1),.,( )1,2,(.)()(.)nnnMm mmmmc ccEK（M）=E11112(1)(
44、2)( )()(,.,)(.)nnDCDc ccccc1KCM24/67第第2 2章章 古典密码技术古典密码技术 这种密码的加密方法就是将明文按行填写到一个列宽固定（设为这种密码的加密方法就是将明文按行填写到一个列宽固定（设为m m）的）的 表格或矩阵中；然后按（表格或矩阵中；然后按（1 1，2 2，m m）的一个置换）的一个置换 交换列的位置次交换列的位置次 序，再按列读出即得密文。序，再按列读出即得密文。 解密时，将密文按列填写到一个行数固定（也为解密时，将密文按列填写到一个行数固定（也为m m）的表格或矩阵中，）的表格或矩阵中， 按置换按置换 的逆置换交换列的位置次序，然后按行读出即得到
45、明文。置换的逆置换交换列的位置次序，然后按行读出即得到明文。置换 可看成是算法的密钥。可看成是算法的密钥。 例例2.82.8略，参见课本，略，参见课本， 请读者思考，在请读者思考，在例例2.82.8列置换密码中，如果明文字母的长度不是列宽列置换密码中，如果明文字母的长度不是列宽m m的的整倍数，加解密时会有什么问题，应如何处理？整倍数，加解密时会有什么问题，应如何处理？ 由于置换密码只需打乱原明文字符的排列顺序形成乱码来实现加密变换由于置换密码只需打乱原明文字符的排列顺序形成乱码来实现加密变换，因此，置换的方法还有很多，例如，图形置换密码就是先按一定的方向把，因此，置换的方法还有很多，例如，图
46、形置换密码就是先按一定的方向把明文输入到某种预先规定的图形中，再按另一种方向输出密文字符，不足部明文输入到某种预先规定的图形中，再按另一种方向输出密文字符，不足部分填入随机字符，这里就不一一列举了。分填入随机字符，这里就不一一列举了。2.2.2 2.2.2 列列置换密码置换密码25/67第第2 2章章 古典密码技术古典密码技术2.3 2.3 转轮机密码转轮机密码 转轮机的基本结构由一个键盘、若干灯泡和一系列转轮组成转轮机的基本结构由一个键盘、若干灯泡和一系列转轮组成，如图，如图1.41.4（a a）所示。键盘一共有）所示。键盘一共有2626个键，键盘上方就是标示了字母的个键，键盘上方就是标示了
47、字母的2626个小灯泡，当键个小灯泡，当键盘上的某个键被按下时，与这个字母被加密后的密文字母所对应的小灯泡就亮盘上的某个键被按下时，与这个字母被加密后的密文字母所对应的小灯泡就亮了起来。在显示器的上方是几个转轮，每个转轮是了起来。在显示器的上方是几个转轮，每个转轮是2626个字母的任意组合。个字母的任意组合。 如图如图2.22.2是一个三转轮的原理示意图，图中是一个三转轮的原理示意图，图中3 3个矩形框代表个矩形框代表3 3个转轮，从左到个转轮，从左到右分别称为慢转子、中转子和快转子。每个转轮有右分别称为慢转子、中转子和快转子。每个转轮有2626个输入引脚和个输入引脚和2626个输出引个输出引
48、脚，其内部连线将每个输入引脚连接到一个对应的输出引脚，这样每个转轮内脚，其内部连线将每个输入引脚连接到一个对应的输出引脚，这样每个转轮内部相当于一个单表替代。部相当于一个单表替代。当按下某一键时，电信号从慢转子的输入引脚进入，当按下某一键时，电信号从慢转子的输入引脚进入，通过内部连线经过每个转轮，最后从快转子的输出引脚信号输出对应密文字母通过内部连线经过每个转轮，最后从快转子的输出引脚信号输出对应密文字母（点亮）。（点亮）。例如，在图例如，在图2.22.2（a a）中，如果按下字母）中，如果按下字母B B，则相应电信号被加到慢，则相应电信号被加到慢转子的输入引脚转子的输入引脚2525，并通过内
49、部连线连接到慢转子的输出引脚，并通过内部连线连接到慢转子的输出引脚2525，经过中转子，经过中转子的输入引脚的输入引脚2222和输出引脚和输出引脚2222，连接到快转子的输入引脚，连接到快转子的输入引脚1313，最后从快转子的输，最后从快转子的输出引脚出引脚1313输出密文字母（输出密文字母（I I）。）。 26/67第第2 2章章 古典密码技术古典密码技术 如果转轮密码机始终保持图如果转轮密码机始终保持图2.22.2（a a）的连接状态，则按下字母键）的连接状态，则按下字母键B B，输出的，输出的密文字母始终是密文字母始终是I I（按下字母键（按下字母键A A，输出的密文字母则始终是，输出的
50、密文字母则始终是B B，等等），等等），转轮转轮密码机为了能够实现复杂的多表替代密码，打破明文与密文之间固定的替代关密码机为了能够实现复杂的多表替代密码，打破明文与密文之间固定的替代关系，在每次击键输出密文字母后，快转子都要转动一个位置，以改变中转子与系，在每次击键输出密文字母后，快转子都要转动一个位置，以改变中转子与快转子之间的对应关系。快转子之间的对应关系。例如，在图例如，在图2.22.2（a a）的初始状态下，如果按下任意一）的初始状态下，如果按下任意一个键（如个键（如B B键）后，转轮密码机输出密文字母（键）后，转轮密码机输出密文字母（B B键对应密文字母为键对应密文字母为I I），然
