第 2章 古典密码学
2.1古典密码学体制
2.1.1定义和分类
– 一个密码系统（ Cryptosystem）是一个五元组
（ P,C,K,E,D)满足条件,
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
（ 4）任意,有一个加密算法 和相应的解密
算法,使得 和 分别为加密、
解密函数，满足 。
Kk? Eek ?
Ddk ? CPek ?,PCdk ?:
Pxxxed kk ??,,))(( 这里
x x
Alice 加密 解密
密钥源
安全信道
窃听者 Oscar
k
y
Bob
? 实用密码体系
– 每个加密函数和每个解密函数应当能有效
地被计算。
– 即使看到密文串 y，窃听者 Oscar确定所用
的密钥 k或明文串 x是不可行的。
? 已知密文串 y的情况下试图计算密钥 k的
过程称为 密码分析 （ Cryptanalysis）。
? 古典密码学分类
– 代换（ Substitution）密码和置换
（ Permutation）密码
? 2.1.2 代换密码
将明文字母表 Θ抽象地表示为一个整数集 。在加密时
通常将明文消息划分成长为 L的消息单元，称为明文组，以 m表示，
如 。 m也称作 L－报文，它可以看作是
定义在 上的随机变量
这时明文空间 。密文字母表 Ξ抽象表示成整数集 。
密文单元或组为 。 c是定义在 上的
随机变量。密文空间 。一般地，明文和密文由同一字母表构成。代
换密码可以看作是从 到 的映射。 L＝ 1时，称作单字母代换，也称作
流密码（ Stream cipher）。 L>1时，称作多字母代换，亦称分组密码
（ Block cipher）。
? ?1,,1,0 ?? qZ q ?
10,),,,,( 110 ????? ? LlZqmmmm lL?
LqZ
? ? ? ?10,),,,( 110 ?????????? ? LlZmmmmmLZZZZ qlLqqqLq ?? 个
LqZP? ? ?1,,1,0 '' ?? qZ q ?
10,,)(,,,( '''110 ''' ????? ? LlZcLcccc qlL 个）? '
'LqZ
''LqZC?
LqZ ''LqZ
1,单表代换密码
单表代换密码是对明文的所有字母都用
一个固定的明文字母表到密文字母表的
映射，即 。令明文,则
相应地密文为 。
qq ZZf ?,?10 mmm ?
?? )()()( 1010 mfmfccmec ???
? 几类简单的单表代换密码
– 移位密码（ Shift Cipher）
设 定义
且
,250,26 ????? kZKCP 对
26m o d)( kxxe k ??
? ?26,26m o d)( Zyxkyyd k ???
? 例 2,1 恺撒（ Caesar）密码是 k＝ 3的情况。即通过简单的向右
移动源字母表 3个字母则形成如下代换字母表
若明文为,please confirm receipt
则密文为,SOHDVE FRQILUP UHFHLSW
Θ,a b c d e f g h i j k l m
Ξ, D E F G H I J K L M N O P
n o p q r s t u v w x y z
Q R S T U V W X Y Z A B C
? 安全性分析
– 移位密码是极不安全的（ mod26），因为
它可被穷举密钥搜索所分析：仅有 26个可
能的密钥，尝试每一个可能的加密规则，直
到一个有意义的明文串被获得。平均地说，
一个明文在尝试 26/2＝ 13解密规则后将显
现出来。
? 替换密码
– 设,密钥空间 K由所有可能的 26个
符号 0,1,……,,25的置换组成。对每一
个置换,定义
则,
其中 的逆置换。
26ZCP ??
???
)()( xxe ?? ?
)()( 1 yyd ?? ??
?? 是1?
? 例 2.2 密钥句子为,the message was
transmitted an hour ago 。
源字母表为,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
代换字母表为：
THEMSAGWRNIDOUBCFJKLPQVXYZ
明文,please confirm receipt
密文,CDSTKS EBUARJO JSESRCL
? 安全性分析
– 替换密码的密钥是由 26个字母的置换组成。
这些置换的数目是 26！，超过，一个非常
大的数。这样即使对现代计算机来说，穷举
密钥搜索也是不可行的。然而，以后我们会
看到，替换密码容易被其他的分析方法所破
译。
? 仿射密码
– 设,且
对,定义
且
26ZCP ??
? ?1)26,g c d (:),( 2626 ???? aZZbaK Kbak ?? ),(
26m o d)( baxxe ?? 26m o d)()( 1 byayd k ?? ?
),( 26Zyx ?
? 例 2.3 假定,,加密函数为,
则相应的解密函数为,其中所有的运算都
是在 中。容易验证 。
加密明文 hot。
首先转化这三个字母分别为数字 7,14和 19。然后加密
密文串为 AGX。
)3,7(?k 1526m o d7 1 ?? 37)( ?? xxek
1915)3(15)( ???? yyyd k
26Z xxxxdxed kkk ????????? 194519)37(15)37())((
);26( m o d
6
23
0
3
3
3
19
14
7
7
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
G
X
A
? 多表代换密码
– 多表代换密码是以一系列（两个以上）代换表
依次对明文消息的字母进行代换的加密方法。
– 令明文字母表为, 为代换序列，明文
字母序列,则相应的密文字母序列
为 。
qZ ),,( 21 ?fff ?
?21xxx ?
?)()()()( 2211 xfxfxfxec k ???
– 若 f是非周期的无限序列，则相应的密码称
为非周期多表代换密码。这类密码，对每个
明文字母都采用不同的代换表（或密钥）进
行加密，称作一次一密密码（ One-time
pad cipher）,这是一种理论上唯一不可破
的密码 。
– 有名的多表代换密码有 Vigenère、
Beaufort,Running-Key,Vernam和转轮
机（ Rotor machine）等密码。
? Vigenère密码
– 设 m是某固定的正整数，定义,
对一个密钥,我们定义
且
所有的运算都在 中。
mZKCP )( 26???
),,,( 21 mkkkk ??
),,,(),,,( 221121 mmmk kxkxkxxxxe ???? ??
),,(),,,( 221121 mmmk kykykyyyyd ???? ??
26Z
? 例 2.4 设 m＝ 6，且密钥字是 CIPHER,这相应于密钥。假定明文
串是 this cryptosystem is not secure
首先将明文串转化为数字串，按 6个一组分段，然后模 26“加, 上
密钥字得,
相应的密文串将是,
VPXZGIAXIVWPUBTTMJPWIZITWZT
解密过程与加密过程类似,不同的只是进行模 26减,而不是模 26加。
8625231521
17471582
172188719
1522218230
17471582
241814191524
9121919121
17471582
1881241918
1982582215
17471582
2418191413
192522
1582
41720
? 多字母代换密码（ Polygram substitution
cipher） ——Hill 密码
– 设 m是某个固定的正整数，,又
设 ；对任意,定义
, 则 。
– 其中所有的运算都是在 中进行。
mZCP )( 26??
? ?26ZmmK 可逆阵，?? Kk?
xkxek ?)( 1)( ?? ykyd k
26Z
? 例 2.5 假定密钥是，则。现在我们加密明文 july
分为两个明文组（ 9,20）（相应于 ju）和（ 11,24）（相应于
ly）。计算如下,
因此,july的加密是 DELW。
)4,3()1 4 072,6099(73 811)20,9( ??????
?
?
???
?
? 2.1.3置换密码（ Permutation Cipher）
– 设 m是某个固定的整数。,且由所
有 的置换组成。对一个密钥 （即一
个置换），定义
,
其中,。
mZCP )( 26??
? ?m,,2,1 ? ?
),,,(),,,( )()2()1(21 mm xxxxxxe ???? ?? ?
),,,(),,,( )()2()1(21 111 mm yyyyyyd ???? ???? ??
的逆置换是 ?? 1?
? 例 2.6 假定 m＝ 6，密钥是以下置换, ；
则逆置换 为,。 给出明文
shesellsseashellsbytheseashore,
首先把明文分为 6个字母一组,
shesel lsseas hellsb ythese ashore,
每六个字母按重排，得密文,
EESLSHSALSESLSHBLEHSYEETHRAEOS
用 类似地解密。
246153
654321?
1??
425163
654321
1??
? 安全性分析
– Hill密码解密等价于用逆置换 的置换密码
解密。
1??
2,2 古典密码体制分析
? Kerckhoff假设：攻击方知道所用的密码系统。
? 简单的单表代换密码，如移位密码，仅统计标出最高
频度字母再与明文字母表字母对应决定出移位量，就
差不多得到正确解了。也很容易用穷举密钥搜索来破
译。
? 一般的仿射密码，多考虑几个密文字母统计表与明文
字母统计表的匹配关系也不难解出。
? 结论：一个密码系统是安全的一个必要条件是密钥空
间必须足够大，使得穷举密钥搜索破译是不可行的。
? 唯密文攻击法分析单表和多表代换密码
是可行的。
? 但用唯密文攻击法分析多字母代换密码
如 Hill密码是比较困难的。分析多字母代
换多用已知明文攻击法。
2.2.1 单表代换密码分析
? 例 2.7 假设从仿射密码获得的密文为,
FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK
APRKDLYEVLRHHRH 仅有 57个密文字母，但足够分析仿射密码。
最高频的密文字母是,R(8次 ),
D（ 6次）,E,H,K（各五次）,
F,S,V（各四次）。
开始，我们可以假定 R是 e的加密
且 D是 t的加密，因为 e和 t分别是
两个最常见的字母。数值化后,
我们有 。
回忆加密函数 。
所以得到两个含两个未知量的
线性方程组,
表 2.3 26个英文字母的概率分布
字母 概率 字母 概率
A 0.082 N 0.067
B 0.015 O 0.075
C 0.028 P 0.019
D 0.043 Q 0.001
E 0.127 R 0.060
F 0.022 S 0.063
G 0.020 T 0.091
H 0.061 U 0.028
I 0.070 V 0.010
J 0.002 W 0.023
K 0.008 X 0.001
L 0.040 Y 0.020
M 0.024 Z 0.001
3)19(17)4( ?? kk ee 且
baxxe k ??)(
?
?
?
??
??
319
174
ba
ba
这个系统有唯一的解 。但这是一个非法的密钥，
因为 。所以我们假设有误。
我们下一个猜想可能是 R是 e的加密,E是 t的加密。得,
又是不可能的。继续假定 R是 e的加密且 K是 t的加密。这产生
了,至少是一个合法的密钥。剩下的事是计算相应于 k
＝（ 3,5）的解密函数，然后解密密文看是否得到了有意义的英
文串。容易证明这是一个有效的密钥。
最后的密文是,
algorithms are quite general definitions of arithmetic
processes
)(19,6 26Zba ??
12)26,g c d ( ??a
8?a
5,3 ?? ba
2.2.2 多表代换密码分析
? 分析 Vigenère密码的方法,
– Kasiski测试法
若用给定的 m个密钥表周期地对明文字母加密，则
当明文中有两个相同字母组在明文序列中间隔的字
母数为 m的倍数时，这两个明文字母组对应的密文
字母组必相同。但反过来，若密文中出现两个相同
的字母组，它们所对应的明文字母组未必相同，但
相同的可能性很大。如果我们将密文中相同的字母
组找出来，并对其相同字母数综合研究，找出它们
的相同字母数的最大公因子，就有可能提取出有关
密钥字的长度 m的信息。
? 例子,
明文,REQUESTS ADDITIONAL TEST
密钥,TELEXTEL EXTELEXTEL EXTE
密钥,CAVKTBLT EUQWSWJGEA LTBL
一个给定密文包含下列重复的序列,
且有距离,
因为 3是出现最频繁的因子,
所以密文的周期最有可能是 3。
字母序列 距离
PQA 150=2× 52 × 3
RET 42=7× 2× 3
FRT 10=2× 5
ROPY 81=34
DER 57=19× 3
RUN 117=13× 32
– 重合指数法（ Coincidence Index）
– 设一门语言由 n个字母构成，每个字母发生
的概率为,则重合指数是指其中两个
随机元素相同的概率，记为 。
– 判断文本是用单表还是用多表代换加密。
– 提供对两个不同密文的洞察力 。
–
nipi ??1
?
?
? n
i
ipCI
1
2
?
?
??? n
i ii
LLxxCI
1
' )1(/)1(
– Chi 测试
比较两个频率分布,决定是否同样或不同
的代换被采用
简化多表代换为单表代换
??? ni iiqp1?
? 例,
明文,EXECUTE THESE COMMANDS
密钥,RADIORA DIORA DIORADIO
密文,VXHKIKE WPSJE FWADAQLG
V O V T L
K V K Y V
J V T F D
D R E U J
R A D I O
0 9 12 17 23
R A D I O
V X H K I
K E W P S
J E F W A
D A Q L G
? 例 2.8 在相距很短的时间间隔内我们收到了两段密文,
? 密文 1,
? k o o m m a c o m o q e g l x x m q c c k u e y f c u r
? y l y l i g z s x c z v b c k m y o p n p o g d g i a z
? t x d d i a k n v o m x h i e m r d e z v x b m z r n l
? z a y q i q x g k k k p n e v h o v v b k k t c s s e p
? k g d h x y v j m r d k b c j u e f m a k n t d r x b i
? e m r d p r r j b x f q n e m x d r l b c j h p z t v v
? i x y e t n i i a w d r g n o m r z r r e i k i o x r u
? s x c r e t v
? 密文 2,
? z a o z y g y u k n d w p i o u o r i y r h h b z x r c
? e a y v x u v r x k c m a x s t x s e p b r x c s 1 r u
? k v b x t g z u g g d w h x m x c s x b i k t n s l r j
? z h b x m s p u n g z r g k u d x n a u f c m r z x j r
? y w y m i
（ 1） 假定两段文
本的确是用同样方式加密的。
（ 2）采用 Kasiski测试 确认是用多表代
换加密
（ 3）转化多表代换的密文为某个单个的
单表代换加密的密文
（ 4）用一单表代换密码的解密方法解密
这段文本
0 4 2 1.0)( 1' ?CCI 0 4 4 5.0)( 2' ?CCI
2.2.3 对 Hill密码的已知明文分析
? 例 2.9 明文 friday是用 Hill 密码加密的,m=2，得
到密文 POCFKU。
? 则有,, 。
? 从最初两个明文对，我们得到矩阵方程
?,容易计算,
? 所以 。
? 可用第三个明密文对验证。
)16,15()17,5( ?ke )5,2()3,8( ?ke )20,10()24,0( ?ke
k????????????????? 36 17552 1615 ??
?
?
???
??
???
?
???
? ?
152
19
36
175 1
???
?
???
??
???
?
???
?
???
?
???
??
38
197
52
1615
152
19
k
小结
? （ 1）本章简要介绍了几种有代表性的古典密
码体制及对这些体制的一些破译方法，用来说
明设计和分析密码的基本方法。
? （ 2）代换和置换方法是增强密码安全性的两
个基本手段。
? （ 3）详细的叙述 Kasiski测试法、重合指数法
和 Chi测试法的具体操作。
2.1古典密码学体制
2.1.1定义和分类
– 一个密码系统（ Cryptosystem）是一个五元组
（ P,C,K,E,D)满足条件,
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
（ 4）任意,有一个加密算法 和相应的解密
算法,使得 和 分别为加密、
解密函数，满足 。
Kk? Eek ?
Ddk ? CPek ?,PCdk ?:
Pxxxed kk ??,,))(( 这里
x x
Alice 加密 解密
密钥源
安全信道
窃听者 Oscar
k
y
Bob
? 实用密码体系
– 每个加密函数和每个解密函数应当能有效
地被计算。
– 即使看到密文串 y，窃听者 Oscar确定所用
的密钥 k或明文串 x是不可行的。
? 已知密文串 y的情况下试图计算密钥 k的
过程称为 密码分析 （ Cryptanalysis）。
? 古典密码学分类
– 代换（ Substitution）密码和置换
（ Permutation）密码
? 2.1.2 代换密码
将明文字母表 Θ抽象地表示为一个整数集 。在加密时
通常将明文消息划分成长为 L的消息单元，称为明文组，以 m表示，
如 。 m也称作 L－报文，它可以看作是
定义在 上的随机变量
这时明文空间 。密文字母表 Ξ抽象表示成整数集 。
密文单元或组为 。 c是定义在 上的
随机变量。密文空间 。一般地，明文和密文由同一字母表构成。代
换密码可以看作是从 到 的映射。 L＝ 1时，称作单字母代换，也称作
流密码（ Stream cipher）。 L>1时，称作多字母代换，亦称分组密码
（ Block cipher）。
? ?1,,1,0 ?? qZ q ?
10,),,,,( 110 ????? ? LlZqmmmm lL?
LqZ
? ? ? ?10,),,,( 110 ?????????? ? LlZmmmmmLZZZZ qlLqqqLq ?? 个
LqZP? ? ?1,,1,0 '' ?? qZ q ?
10,,)(,,,( '''110 ''' ????? ? LlZcLcccc qlL 个）? '
'LqZ
''LqZC?
LqZ ''LqZ
1,单表代换密码
单表代换密码是对明文的所有字母都用
一个固定的明文字母表到密文字母表的
映射，即 。令明文,则
相应地密文为 。
qq ZZf ?,?10 mmm ?
?? )()()( 1010 mfmfccmec ???
? 几类简单的单表代换密码
– 移位密码（ Shift Cipher）
设 定义
且
,250,26 ????? kZKCP 对
26m o d)( kxxe k ??
? ?26,26m o d)( Zyxkyyd k ???
? 例 2,1 恺撒（ Caesar）密码是 k＝ 3的情况。即通过简单的向右
移动源字母表 3个字母则形成如下代换字母表
若明文为,please confirm receipt
则密文为,SOHDVE FRQILUP UHFHLSW
Θ,a b c d e f g h i j k l m
Ξ, D E F G H I J K L M N O P
n o p q r s t u v w x y z
Q R S T U V W X Y Z A B C
? 安全性分析
– 移位密码是极不安全的（ mod26），因为
它可被穷举密钥搜索所分析：仅有 26个可
能的密钥，尝试每一个可能的加密规则，直
到一个有意义的明文串被获得。平均地说，
一个明文在尝试 26/2＝ 13解密规则后将显
现出来。
? 替换密码
– 设,密钥空间 K由所有可能的 26个
符号 0,1,……,,25的置换组成。对每一
个置换,定义
则,
其中 的逆置换。
26ZCP ??
???
)()( xxe ?? ?
)()( 1 yyd ?? ??
?? 是1?
? 例 2.2 密钥句子为,the message was
transmitted an hour ago 。
源字母表为,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
代换字母表为：
THEMSAGWRNIDOUBCFJKLPQVXYZ
明文,please confirm receipt
密文,CDSTKS EBUARJO JSESRCL
? 安全性分析
– 替换密码的密钥是由 26个字母的置换组成。
这些置换的数目是 26！，超过，一个非常
大的数。这样即使对现代计算机来说，穷举
密钥搜索也是不可行的。然而，以后我们会
看到，替换密码容易被其他的分析方法所破
译。
? 仿射密码
– 设,且
对,定义
且
26ZCP ??
? ?1)26,g c d (:),( 2626 ???? aZZbaK Kbak ?? ),(
26m o d)( baxxe ?? 26m o d)()( 1 byayd k ?? ?
),( 26Zyx ?
? 例 2.3 假定,,加密函数为,
则相应的解密函数为,其中所有的运算都
是在 中。容易验证 。
加密明文 hot。
首先转化这三个字母分别为数字 7,14和 19。然后加密
密文串为 AGX。
)3,7(?k 1526m o d7 1 ?? 37)( ?? xxek
1915)3(15)( ???? yyyd k
26Z xxxxdxed kkk ????????? 194519)37(15)37())((
);26( m o d
6
23
0
3
3
3
19
14
7
7
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
G
X
A
? 多表代换密码
– 多表代换密码是以一系列（两个以上）代换表
依次对明文消息的字母进行代换的加密方法。
– 令明文字母表为, 为代换序列，明文
字母序列,则相应的密文字母序列
为 。
qZ ),,( 21 ?fff ?
?21xxx ?
?)()()()( 2211 xfxfxfxec k ???
– 若 f是非周期的无限序列，则相应的密码称
为非周期多表代换密码。这类密码，对每个
明文字母都采用不同的代换表（或密钥）进
行加密，称作一次一密密码（ One-time
pad cipher）,这是一种理论上唯一不可破
的密码 。
– 有名的多表代换密码有 Vigenère、
Beaufort,Running-Key,Vernam和转轮
机（ Rotor machine）等密码。
? Vigenère密码
– 设 m是某固定的正整数，定义,
对一个密钥,我们定义
且
所有的运算都在 中。
mZKCP )( 26???
),,,( 21 mkkkk ??
),,,(),,,( 221121 mmmk kxkxkxxxxe ???? ??
),,(),,,( 221121 mmmk kykykyyyyd ???? ??
26Z
? 例 2.4 设 m＝ 6，且密钥字是 CIPHER,这相应于密钥。假定明文
串是 this cryptosystem is not secure
首先将明文串转化为数字串，按 6个一组分段，然后模 26“加, 上
密钥字得,
相应的密文串将是,
VPXZGIAXIVWPUBTTMJPWIZITWZT
解密过程与加密过程类似,不同的只是进行模 26减,而不是模 26加。
8625231521
17471582
172188719
1522218230
17471582
241814191524
9121919121
17471582
1881241918
1982582215
17471582
2418191413
192522
1582
41720
? 多字母代换密码（ Polygram substitution
cipher） ——Hill 密码
– 设 m是某个固定的正整数，,又
设 ；对任意,定义
, 则 。
– 其中所有的运算都是在 中进行。
mZCP )( 26??
? ?26ZmmK 可逆阵，?? Kk?
xkxek ?)( 1)( ?? ykyd k
26Z
? 例 2.5 假定密钥是，则。现在我们加密明文 july
分为两个明文组（ 9,20）（相应于 ju）和（ 11,24）（相应于
ly）。计算如下,
因此,july的加密是 DELW。
)4,3()1 4 072,6099(73 811)20,9( ??????
?
?
???
?
? 2.1.3置换密码（ Permutation Cipher）
– 设 m是某个固定的整数。,且由所
有 的置换组成。对一个密钥 （即一
个置换），定义
,
其中,。
mZCP )( 26??
? ?m,,2,1 ? ?
),,,(),,,( )()2()1(21 mm xxxxxxe ???? ?? ?
),,,(),,,( )()2()1(21 111 mm yyyyyyd ???? ???? ??
的逆置换是 ?? 1?
? 例 2.6 假定 m＝ 6，密钥是以下置换, ；
则逆置换 为,。 给出明文
shesellsseashellsbytheseashore,
首先把明文分为 6个字母一组,
shesel lsseas hellsb ythese ashore,
每六个字母按重排，得密文,
EESLSHSALSESLSHBLEHSYEETHRAEOS
用 类似地解密。
246153
654321?
1??
425163
654321
1??
? 安全性分析
– Hill密码解密等价于用逆置换 的置换密码
解密。
1??
2,2 古典密码体制分析
? Kerckhoff假设：攻击方知道所用的密码系统。
? 简单的单表代换密码，如移位密码，仅统计标出最高
频度字母再与明文字母表字母对应决定出移位量，就
差不多得到正确解了。也很容易用穷举密钥搜索来破
译。
? 一般的仿射密码，多考虑几个密文字母统计表与明文
字母统计表的匹配关系也不难解出。
? 结论：一个密码系统是安全的一个必要条件是密钥空
间必须足够大，使得穷举密钥搜索破译是不可行的。
? 唯密文攻击法分析单表和多表代换密码
是可行的。
? 但用唯密文攻击法分析多字母代换密码
如 Hill密码是比较困难的。分析多字母代
换多用已知明文攻击法。
2.2.1 单表代换密码分析
? 例 2.7 假设从仿射密码获得的密文为,
FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK
APRKDLYEVLRHHRH 仅有 57个密文字母，但足够分析仿射密码。
最高频的密文字母是,R(8次 ),
D（ 6次）,E,H,K（各五次）,
F,S,V（各四次）。
开始，我们可以假定 R是 e的加密
且 D是 t的加密，因为 e和 t分别是
两个最常见的字母。数值化后,
我们有 。
回忆加密函数 。
所以得到两个含两个未知量的
线性方程组,
表 2.3 26个英文字母的概率分布
字母 概率 字母 概率
A 0.082 N 0.067
B 0.015 O 0.075
C 0.028 P 0.019
D 0.043 Q 0.001
E 0.127 R 0.060
F 0.022 S 0.063
G 0.020 T 0.091
H 0.061 U 0.028
I 0.070 V 0.010
J 0.002 W 0.023
K 0.008 X 0.001
L 0.040 Y 0.020
M 0.024 Z 0.001
3)19(17)4( ?? kk ee 且
baxxe k ??)(
?
?
?
??
??
319
174
ba
ba
这个系统有唯一的解 。但这是一个非法的密钥，
因为 。所以我们假设有误。
我们下一个猜想可能是 R是 e的加密,E是 t的加密。得,
又是不可能的。继续假定 R是 e的加密且 K是 t的加密。这产生
了,至少是一个合法的密钥。剩下的事是计算相应于 k
＝（ 3,5）的解密函数，然后解密密文看是否得到了有意义的英
文串。容易证明这是一个有效的密钥。
最后的密文是,
algorithms are quite general definitions of arithmetic
processes
)(19,6 26Zba ??
12)26,g c d ( ??a
8?a
5,3 ?? ba
2.2.2 多表代换密码分析
? 分析 Vigenère密码的方法,
– Kasiski测试法
若用给定的 m个密钥表周期地对明文字母加密，则
当明文中有两个相同字母组在明文序列中间隔的字
母数为 m的倍数时，这两个明文字母组对应的密文
字母组必相同。但反过来，若密文中出现两个相同
的字母组，它们所对应的明文字母组未必相同，但
相同的可能性很大。如果我们将密文中相同的字母
组找出来，并对其相同字母数综合研究，找出它们
的相同字母数的最大公因子，就有可能提取出有关
密钥字的长度 m的信息。
? 例子,
明文,REQUESTS ADDITIONAL TEST
密钥,TELEXTEL EXTELEXTEL EXTE
密钥,CAVKTBLT EUQWSWJGEA LTBL
一个给定密文包含下列重复的序列,
且有距离,
因为 3是出现最频繁的因子,
所以密文的周期最有可能是 3。
字母序列 距离
PQA 150=2× 52 × 3
RET 42=7× 2× 3
FRT 10=2× 5
ROPY 81=34
DER 57=19× 3
RUN 117=13× 32
– 重合指数法（ Coincidence Index）
– 设一门语言由 n个字母构成，每个字母发生
的概率为,则重合指数是指其中两个
随机元素相同的概率，记为 。
– 判断文本是用单表还是用多表代换加密。
– 提供对两个不同密文的洞察力 。
–
nipi ??1
?
?
? n
i
ipCI
1
2
?
?
??? n
i ii
LLxxCI
1
' )1(/)1(
– Chi 测试
比较两个频率分布,决定是否同样或不同
的代换被采用
简化多表代换为单表代换
??? ni iiqp1?
? 例,
明文,EXECUTE THESE COMMANDS
密钥,RADIORA DIORA DIORADIO
密文,VXHKIKE WPSJE FWADAQLG
V O V T L
K V K Y V
J V T F D
D R E U J
R A D I O
0 9 12 17 23
R A D I O
V X H K I
K E W P S
J E F W A
D A Q L G
? 例 2.8 在相距很短的时间间隔内我们收到了两段密文,
? 密文 1,
? k o o m m a c o m o q e g l x x m q c c k u e y f c u r
? y l y l i g z s x c z v b c k m y o p n p o g d g i a z
? t x d d i a k n v o m x h i e m r d e z v x b m z r n l
? z a y q i q x g k k k p n e v h o v v b k k t c s s e p
? k g d h x y v j m r d k b c j u e f m a k n t d r x b i
? e m r d p r r j b x f q n e m x d r l b c j h p z t v v
? i x y e t n i i a w d r g n o m r z r r e i k i o x r u
? s x c r e t v
? 密文 2,
? z a o z y g y u k n d w p i o u o r i y r h h b z x r c
? e a y v x u v r x k c m a x s t x s e p b r x c s 1 r u
? k v b x t g z u g g d w h x m x c s x b i k t n s l r j
? z h b x m s p u n g z r g k u d x n a u f c m r z x j r
? y w y m i
（ 1） 假定两段文
本的确是用同样方式加密的。
（ 2）采用 Kasiski测试 确认是用多表代
换加密
（ 3）转化多表代换的密文为某个单个的
单表代换加密的密文
（ 4）用一单表代换密码的解密方法解密
这段文本
0 4 2 1.0)( 1' ?CCI 0 4 4 5.0)( 2' ?CCI
2.2.3 对 Hill密码的已知明文分析
? 例 2.9 明文 friday是用 Hill 密码加密的,m=2，得
到密文 POCFKU。
? 则有,, 。
? 从最初两个明文对，我们得到矩阵方程
?,容易计算,
? 所以 。
? 可用第三个明密文对验证。
)16,15()17,5( ?ke )5,2()3,8( ?ke )20,10()24,0( ?ke
k????????????????? 36 17552 1615 ??
?
?
???
??
???
?
???
? ?
152
19
36
175 1
???
?
???
??
???
?
???
?
???
?
???
??
38
197
52
1615
152
19
k
小结
? （ 1）本章简要介绍了几种有代表性的古典密
码体制及对这些体制的一些破译方法，用来说
明设计和分析密码的基本方法。
? （ 2）代换和置换方法是增强密码安全性的两
个基本手段。
? （ 3）详细的叙述 Kasiski测试法、重合指数法
和 Chi测试法的具体操作。
