§ 4.2 密码的设计,解码与破译
密码的设计和使用至少可从追溯到四千多年前的埃及,巴
比伦、罗马和希腊,历史极为久远 。 古代 隐藏信息的方法
主要有两大类:
其一 为 隐藏信息载体,采用隐写术 等;
其二 为 变换信息载体,使之无法为一般人所理解 。
在密码学中,信息代码被称为 密码,加密
前的信息被称为 明文,经加密后不为常人
所理解的用密码表示的信息被称为 密文
(ciphertext),将明文转变成密文的过程被
称为 加密 (enciphering),其逆过程则被称
为 解密 (deciphering),而用以加密、解密
的方法或算法则被称为 密码体制
(crytosystem)。
记全体明文组成的集合 为 U,全体密文组成的集合 为 V,称 U
为明文空间,V为密文空间。加密常利用某一被称为密钥的东
西来实现,它通常取自于一个被称为密钥空间的含有若干参
数的集合 K。按数学的观点来看,加密与解密均可被看成是一
种变换:取一 k∈ K,u∈ U,令, v为明
文 u在密钥 K下的密文,而解码则要用 到 K的逆变换 K-1,。由
此可见,密码体系虽然可以千姿百态,但其关键还在 于 密钥
的选取 。
? Vvu k ?? ??
随着计算机与网络技术的迅猛发展,大量各具特色的密码体
系不断涌现。离散数学、数论、计算复杂性、混沌,……,
许多相当高深的数学知识都被用上,逐步形成了(并仍在迅
速发展的)具有广泛应用面的 现代密码学 。
早期密码
替代密码
移位密码
代数密码
代替法密码 采用另一个字母表中的字母来代替明文中的字母,
明文字母与密文字母保持一一对应关系,但采用的符号改变
了。加密时,把明文换成密文,即将明文中的字母用密文字
母表中对应位置上的字母取代。解密时,则把密文换成明文,
即把密文中的字母用明文字母表中对应位置上的字母代回,
解密过程是加密过程的逆过程。在代替法加密过程中,密文
字母表即代替法密钥,密钥可以是标准字母表,也可以是任
意建立的。
1.代替法密码
明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ
密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词
或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。
混合一个字母表,常见的有两种方法,这两种方法都采用
了一个 密钥单词 或一个 密钥短语 。
方法 1:
a)选择一个密钥单词或密钥短语,例如,construct
b)去掉其中重复的字母,得,constru
c)在修改后的密钥后面接上从标准字母表中去掉密钥中已有
的字母后剩下的字母,得:
明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ
在设计密钥时,也可在明文字母表中选择一个特定字母,然
后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例
如,对于上例,选取特定字 母 k,则可得:
明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ
方法 2:
a)选择一个密钥单词或密钥短语,例如,construct
b)去掉其中重复的字母,得,constru
c)这些字母构成矩阵的第一行,矩阵的后续各行由标准字母
表中去掉密钥单词的字母后剩下的字母构成
d)将所得矩阵中的字母按列的顺序排出
得,cugmyoahpznbiqsdjvrtekwrflx
按照此方法产生的字母表称为 混淆字母表 。
还可以使用 混淆数 。混淆数由以下方法产生:
a)选一密钥单词或密钥短语,例如,construct
b)按照这些字母在标准字母表中出现的相对顺序给它们编号,
对序列中重复的字母则自左向右编号,得, construct
143675928
c)自左向右选出这些数 字,得到一个混淆数字 组,143675928,
混淆字母表由从小到大的顺序取矩阵中相应列得出。
为增加保密性,在使用
代替法时还可利用一些
其他技巧,如单字母表
对多字母表、单字母对
多字母、多重代替等。
2.移位密码体制
移位密码 采用移位法进行加密,明文中的字母重新排列,本
身不变,只是位置改变了。
早在 4000多年前,古希腊人就用一种名 叫“天书”的器械
来加密消息。该密码器械是用一条窄长的草纸缠绕在一个
直径确定的圆筒上,明文逐行横写在纸带上,当取下纸带
时,字母的次序就被打乱了,消息得以隐蔽。收方阅读消
息时,要将纸带重新绕在直径与原来相同的圆筒上,才能
看到正确的消息。在这里圆筒的直径起到了密钥的作用。
另一种移位 法 采用将字母表中的字母平移若干位的方法来构造
密文字母表,传说这类方法是由古罗马皇帝凯撒最早使用的,
故这种密文字母表被称为凯撒字母表。例如,如用将字母表向
右平移 3位的方法来构造密文字母表,可 得:
明文字母表, ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表, DEFGHIJKLMNOPQRTSUVWXYZABC
因此, THANK YOU”,WKDQN BRX”
以上两种移位较易被人破译,为打破字母表中原有的顺序还可
采用所谓路线加密法,即把明文字母表按某种既定的顺序安排
在一个矩阵中,然后用另一种顺序选出矩阵中的字母来产生密
文表。
例如,对明文,THE HISTORY OF ZJU IS MORE THAN
ONE HUNDRED YEARS.以 7列矩阵表示如下:
THEHIST
ORYOFZJ
UISMORE
THANONE
HUNDRED
YEARS
再按事先约定的方式选出密文。例如,如按列选出,得到
密文,touthyhrihueeysanahomndrifoorsszrnetjeed
使用不同的顺序进行编写和选择,可以得到各种不同的路
线加密体制。对于同一明文消息矩阵,采用不同的抄写方
式,得到的密文也是不同的。
当明文超过规定矩阵的大小时,可以另加一矩阵。当需要
加密的字母数小于矩阵大小时,可以在矩阵中留空位或以
无用的字母来填满矩阵。
移位法也可和代替法结合使用,并使用约定的单词或短语作
密钥,以进一步加强保密性,这就 是 钥控列序加密 法 。
例如,用密钥单词 construct对明文 MATHEMATICAL
MODELING IS USEFUL加密:
CONSTRUCT
1 4 3 675 9 28
MATHEMATI
CALMODELI
NGISUSEFU
L
按混淆数的顺序选出各列,得到密文:
MCNLTLFTLIAAGMDSHMSEOSIIUAEE
移位法的使用可重复多次,只进行一次移位加密的称为一
次移位法,经多次移位的则称 为 多次移位法
代替法与移位法密码 的 破译
对窃听到的密文进行分析时, 穷举法 和 统计法 是最基本的
破译方法 。
穷举分析法 就是对所有可能的密钥或明文进行逐一试探,
直至试探到“正确”的为止。此 方法 需要事先知道密码体
制或加密算法 (但不知道密钥或加密具体办法)。破译时
需将猜测到的明文和选定的密钥输入给算法,产生密文,
再将该密文与窃听来的密文比较。如果相同,则认为该密
钥就是所要求的,否则继续试探,直至破译。以英文字母
为例,当已知对方在采用代替法加密时,如果使用穷举字
母表来破译,那么对于最简单的一种使用单字母表-单字
母-单元代替法加密的密码,字母表的可能情况 有 26! 种,
可见,单纯地使用穷举法,在实际应用中几乎是行不通的,
只能与其它方法结合使用。
统计法 是根据统计资料进行猜测的。在一段足够长且非特别
专门化的文章中,字母的使用频率是比较稳定的。在某些技
术性或专门化文章中的字母使用频率可能有微小变化。
在上述两种加密方法中字母表中的字母是一一对应的,因此,
在截获的密文中各字母出现的概率提供了重要的密钥信息。根
据权威资料报道,可以 将 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,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个字母的假设条件
下进行的。实际上消息的构成还包括间隔、标点、数字
等字符。总之,破译密码并不是件很容易的事。
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 19 20 21 22 23 24 25 0
将密文分成 n个一组,用对应的数字代替,就变成了一个
个 n维向量。如果取定一 个 n阶的非奇异矩 阵 A(此矩阵为
主要密钥),用 A去乘每一向量,即可起到加密的效果,解
密也不麻烦,将密文也分 成 n个一组,同样变换 成 n维向量,
只需用去乘这些向量,即可将他们变回原先的明文。
定理 1,若 使得
(mod26),则必有 =1,其
中 为 与 26的最大公因子。
{0,...,25}a ? { 0,2 5 }a 1 ?? ?
1aaaa 11 ?? ?? gcd{a,26}
gcd{a,26} a
证 任取 { 0,.,,,2 5 }p ?,令 q26kap ??,于是
k2 6 ap2 6 k )( a paqaapa 1111 ???? ?????,故
k26a1)pa(a 11 ?? ???
,由 p的任意性可知必有
1aa 1 ??
(mod26)
即 12 6 kaa,k 1 ??? ???
上式说明必有 1gcd{a,26} ?
,不然它将整 除 1,而这是不可能的。
在具体实施时,我们很快会发现一些困
难:
(1) 为了使数字与字符间可以互换,必须
使用取自 0—25之间的整数
(2)由线性代数知识,,其中
为 A的伴随矩阵。由于使用了除法,
在 求 A的逆矩阵时可能会出现分数。不
解决这些困难,上述想法仍然无法实现。
解决的办法是引进同余运算,并用乘法
来代替除法,(如同线性代数中用逆矩
阵代替矩阵除法一样)。
det(A)
AA 1 ?? ?
?A
此外,我们还不难证明这样的 1a? 还是由
a 唯一确定的。事实上设有
126kaa 111 ???和 12 6 kaa 212 ??? ){ 0,.,,,2 6 }a,(a 1211 ???
则 )k26(k)aa(a
211211 ??? ?? 故必有
21 kk ?
(也因为 1gcd{a,26} ?),即 1
211 aa ?? ?
由定理 1,0— 26中除 13以外的奇数均可取作这里的 a
,下表为经计算求得的逆元素
a 1 3 5 7 9 11 15 17 19 21 23 25
1a? 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,再用 对密文解密
??
?
0
1
??
?
3
2 ?
?
???
0
1A 1
??
?
9
8
1A ?
??
?
??
?
8
20
??
?
??
?
14
1
??
?
??
?
25
11
??
?
??
?
21
15
用矩阵 A左乘各向量加密(关 于 26取余)得
??
?
??
?
24
10
??
?
??
?
16
3
??
?
??
?
23
9
??
?
??
?
11
5
得到密文 JXCPI WEK
解,(希尔密码加 密 )用相应数字代替字符,划分为两个元素一
组并表示为向量:
( 希尔密码解密 )
用 A-1左乘求得的向量,即可还原为原来的向量。 (自行验证 )
希尔密码是以 矩阵 法 为基础的,明文与密文的对 应由 n阶矩
阵 A确定。矩阵 A的阶数是事先约定的,与明文分组时每组
字母的字母数量相同,如果明文所含字数 与 n不匹配,则最
后几个分量可任意补足。
A-1的求法
方法 1 利用公式,例如,若取,
则,,(mod26),即
方法 2 利用高斯消去法。将矩 阵 (A,E)中的矩阵 A消为 E,
则原先的 E即被消成了 A-1,
)d e t(
1
A
AA ?? ? ?
?
??
0
1A ?
?
?
3
2
3)d e t( ?A 9)d e t(1 ?A ?
?
???
0
39A 1 ?
?
??
1
2
????? 0
11A
???9
8

???
?
???0
1 ?
?
?
3
2, ?
?
?
0
1
???
?
???1
0 ? (用 9乘第二行并取同 余 ) ??
?
?
???0
1 ?
?
?
1
2, ?
?
?
0
1
???
?
???9
0?
第一行减去第二行 的 2倍并取同余,得
???
?
???0
1 ?
?
?
1
0, ?
?
?
0
1
???
?
???9
8
左端矩阵已化为单位阵,故右端矩阵即为 A-1
希尔密码系统的解密依赖于以下几把钥匙 ( key):
Key1 矩阵 A的阶数 n,即
明文是按几个字母来
划分的。
Key2 变换矩阵 A,只有知
道了 A才可能推算出
Key3 明文和密文由字母表
转换成 n维向量所对
应的非负整数表(上
面,为方便起见,我
们采用了字母的自然
顺序)。
希尔密码体系为破译者设置了多道关口,加大了破译难度。破
译和解密是两个不同的概念,虽然两者同样是希望对密文加以
处理而得到明文的内容,但是他们有一个最大的不 同 ——破
译密码时,解密必需用到的钥匙未能取得,破译密码的一方需
要依 据 密文的长度, 文字的本身特征,以及 行文习惯 等等各
方面的信息进行破译。破译密码虽然需要技术,但更加重要的
是“猜测”的艺术。“猜测”的成功与否直接决定着破译的结
果。
破译希尔密码的关键是猜测文字被转换成成几维向量所、对应
的字母表是怎样的,更为重要的是要设法获取加密矩 阵 A。
( 希尔密码的破译 )
由线性代数的知识可以知道,矩阵完全
由一组基的变换决定,对 于 n阶矩阵 A,
只要猜出密文 中 n个线性无关的向量
ii Apq ?
(i=1,2,…,n )
对应的明文 (i=1,2,…,n )是什么,即
可确定 A,并将密码破译。
在实际计算中,可以利用以下方法:


TnpppP ),.,,,,( 21?, TnT APpppAQ ?? ),.,,,,( 21
1)(,??? TT AQPPAQ
取矩阵 [Q | P],经过一系列初等行变换,将由密文决定 的 n
维矩阵 Q化为 n阶单位阵 I的时候,由明文决定的矩 阵 P自
动化为 (A-1)T,即,
]),[])(,[
(])(,[],[
1111
1
????
?
?? ??
? ???
TT
T
AIAQQQQ
AQQPQ

初等行变换)
例 5 有密文如下,goqbxcbuglosnfal;根据英文的行
文习惯以及获取密码的途径和背景,猜测是两个字
母为一组的希尔密码,前四个明文字母 是 dear,
试破译这段秘文。
解, 前两组明文字 母 de和 ar 对应的二维向量是:
按同一对应整数表,密文中对应这两组的二维向量是:
TT PP )18,1(,)5,4( 21 ??
TApq )15,7(11 ?, TApq )2,17(22 ??, TqqQ ),( 21?
由此可得
])(,[)26( m o d(],[ 1?? ??? ?? TAIPQ 初等行变换)
,对应上例则有
???
?
?
?
?
??
?
??
?
???
?
??
?? ??? ??
???
?
?
?
?
??
?
??
?
???
?
??
?
9
0
5
1,
1
0
0
1
18
5
1
4,
2
15
17
7 初等行变换并取同余
????? 51)( 1 TA ???90,????? 011A ???95
利用这一逆矩阵,可对截获密文进行解密,破译出的电文是
Dear Mac God forbid,
这只是对最简单情况进行的举例,如果加密矩阵的阶数大于 2,
需要的密文应该有较长长度,所需的计算量也是很大的。破
译的关键是猜 中 n及 n个独立的 n维向量,其后求解加密矩阵
的计算量仅为 O(n2 )。
希尔密码体制中有两个要素非常重要:
第一 是字母 与 n维向量进行转换所依
据的非负整数表,本节中所举的是最
自然的情况;当然如果依据其它的整
数表也是完全可以进行的,其情况将
会更复杂一些,破译的难度就会增大。
第二 个要素是加密矩阵,如何定义、
求解这个矩阵对于密码的加密和破译
更加关键。唯一的要求是加密时应选
择行列式值与 26无公因子的矩阵。
RSA公开密钥体制
传统的密码通讯只能在事先约定的双方间进行,双方必须掌
握相同的密钥,而密钥的传送必须使用另外 的“安全信
道”。这样如果要使 n个用户都能够秘密的交换信息,则每
个用户将需要用个密钥,这种巨大的密钥量给密钥的分配与
管理带来了极大的困难;此外在有些情况下,事先约定密钥
还是不可能的。
公开密钥体制的提出就是为了从根本上解决上述问题 。 其
基本思想 是,把密钥划分为公开密钥和秘密密钥两部分,两者
互为逆变换,但几乎不可能从公开密钥推出秘密密钥,每个
使用者均有自己的公开及秘密密钥。
虽然只要能解密的密文,从理论上讲
都是可破译的,但如果破译所需要
的工作量过大,要求花费的时间过
长,以致超过了保密期限,则该密
码系统应当被认为是安全可靠的。
定义 1 设 n为一正整数,将小 于 n且与 n互素的正整数个数
记为 Φ(n),称之为欧拉( Euler L.) Φ函数。
不难证明:若 p,q为两个相异素数,n=p× q,则
φ(n) =(p-1)(q-1)
令 p,q为随机选取的两个大素数(大约为十进 制 100位或更
大),n=pq,n是公开的,而 p,q则是保密的。仅知道欧拉函
数 φ(n) =(p-1)(q-1),但如果不知道因式分解就不能用这个公
式计算。随机选取一个 数 e,e为小于 φ(n)且与它互素的正整
数。利用辗转相除法,可以找到整 数 d和 r,使
ed+rφ(n) =1
即 ed ≡ 1 (mod φ(n))
数 n,e和 d分别称为 模, 加密密钥 和 解密密钥 。 数 n和 e组成公
开密钥的 加密密钥,而其余的 项 p,q,φ(n)和 d 组成了秘密
陷门。很显然,陷门信息包含了四个相关的项。
若知道 φ(n),则由 pq=n
p+q=n-φ(n)+1 )1)()(( ????? qppqn?
可知 p,q是二次方 程 x2+(φ(n)-n-1)x+n=0的根,可以算 出 p
和 q,从而将 n因式分解。所 以 RSA体制的安全性与因式分
解密切相关,若能知 道 n的因子分解,该密码就能被破
译。因此,要选用足够大 的 n,使得在当今的条件下要分解
它足够困难。
为加密消息 m,首先将它分为小 于 n(对二进制数据,选取
小于 n的 2的最大次方幂)的数据块,也就是说,如 果 p和 q
都为十进制 100位的素数,则 n 刚好在 200位以内,因此每
个消息块的长度也应在两百位以内。加密消息 c由类似划分
的同样长度的消息块组成。加密公式为
eii mc )(? (mod n)
要解密消息,取每一个加密 块 c(I)并计算
(mod n)
由公式 ed ≡ 1 (mod φ(n)) 我们有 ed = 1 - rφ(n),因此
≡ ≡ ≡ (mod n)
其中 r为某一整数。这里利用 了 欧拉定理, φ(n)≡ 1(mod n)
根据以上公式从密文恢复出了明文。
dii mm )(?
dic )( edim )( )(1)( nrim ?? im
im
那么 RSA公开密钥体
制是怎样使用的 呢?请
看下例!
设使用者取 定 p=47,q=59,
则 N=pq=2773,φ(n)=(p-1)(q-1)=2668.
取素数 e=17,显然它与 φ(n)互素,加密者知 道 p,q的值,易
得出 d=157。将 (e,n)=(17,2773)作为公开密钥发布;严守机密
的秘密密钥是 (157,2773).现在有人要向此使用者传送一段
(英文)明文信息,例如:
I love zhejiang university
将这段文字转换为数字,不计大小写,每两个词之间为一个
空格符号,空格符对应数 字 00,每个英文字母对应表征其在
字母表中位置的两位数字,例如,A对应 01,B对应 02,…,
Z对应 26,等等。再从头向后,将每四位数字划归一组,不足
时补充空格。如此得到以下十三组数字:
0900 1215 2205 0026 0805 1009 0114
0700 2114 0922 0518 1909 2025
每一组数字视为一个数,用公开密 钥 (17,2773)对其加以变换。
以第一个数为例,由于 n=2773,比这里任何可能出现的四
位数字均大,故只需计算每一数字在 模 2773下的 17次幂。
我们有
?900 ≡ 1510 (mod 2773).
在以上整个过程中,为减少计算量应随时注意取模。这样
900对应的密码是 1510。以这一方法得到的密文电码是:
1510 0417 1524 1445 0542 2692 1684
0761 1644 2488 1787 1877 1672
解密过程与此类似,只不过使用密 钥 (157,2773),直接计
算很烦琐,但用计算机处理这一问题却非常简单。
本例中将四位数字划分为一组,是为了使每组的数字不超
过 n=2773,当使用一个很大 的 n时,每次完全可以处理一
个位数更多的数码组。只要相应的整数小于 n即可。
)))))9 0 0( ( ( ( ()9 0 0( 222217 ?