专题八、信息安全与密码
数论在信息安全与密码学中有重要的应用.在历史上早就将密码作为军事斗争和政治斗争的一种手段.在当今信息化社会中,密码学不仅与军事、政治领域的信息通讯安全有关,而且在经济领域的商业信息往来中也需要某某。人们通过电报、、电子网络等公共渠道传递信息时,要求信息不能被窃取或修改,安全地传送给指定的接收者,就需要将信息以密文的形式传送。
一、 通讯安全中的基本概念
1.明文、密文、密钥
甲方通过公共渠道向乙方传递信息,为使信息不被窃取或篡改,就需要将信息先改变为秘密形式再发送.我们把原信息称为明文,明文的秘密形式称为密文.将明文变为密文的过程称为加密.通过密码将密文译为明文的过程称为解密.密码中的关键信息称为密钥.密钥在某某通讯中具有至关重要的意义与作用.
一切密码系统都由两部分构成:〔1〕一套组成基本密码的通讯方法或程序的规那么。称为通
用系统;〔2〕一个可变换的密钥。它由数字、单词、词组或句子构成。在对明文加密时,密钥控制通用系统的,并决定密文的组成形式,解密时,密钥同样控制着解密系统。虽然密码的外部形式和内部构成可以有着千差万别,但总括起来只有两种基本形式:〔1〕位移式。即只重新排列或调整明文中的字母顺序,而不改变字母本身;〔2〕置换式。即用其他字母代替明文中的字母而顺序保持不变。有时也可以同时使用这两种密码系统来构成一套密码系统。
20世纪40年代以来广泛使用着各种电密码机。许多电密码机都有类似打字机的键盘,并使用一种电转子装置产生一系列不同的混合字母。另外一种类似的机器也研制出来,它可以对大量电码进行加密和解密。
二、传统的密码系统
下面我们介绍在历史上曾经用过的密码系统.
1.位移式密码
位移式即只重新排列或调整明文中的字母顺序,而不改变字母本身的密码系统。
例1. 明文good morning → 密文mgoo rondgin .明文中第1,5,〔2,6〕个字母为密文中第1,2〔3,4〕个字母,依此类推。
2. 置换密码
所谓置换密码,就是将明文中的每一个字母或数字换为另一个字母或数字,明文经代换后即构成密文.代换规那么(即密钥)可以是系统的,也可以是随机的.
例如,在公元前高卢战争期间,罗马大将恺撒就使用了一种系统置换的密码,置换的密钥(规律)为:按英文26个字母的顺序,将明文中的字母后移三格,即用它以后的第三个字母来代替.
A←D,B←E,C←F,……,X←A,Y←B,Z←C。
例2:明文:good morning,那么在上述密码下,密文为:irrg  pruqlqj。如果不知密码,那么窃收到密文也不知所云。
根据数论中的同余理论,我们可以解释恺撒密码。将26个字母按顺序依次编号为:
A=01,B=02,C=03,……,Y=25。Z=26。
设p表示明文中的字母编号,s表示密文中的字母编号,那么恺撒密码就可以用同余式表示:
s≡p+3 〔mod 26〕
同余式中的数字3即密钥,它是解密的关键。只要知道了此密钥,那么只要通过解同余式
p≡s-3≡s+23 〔mod 26〕
就容易由密文s得出明文p(单个字母)。
置换密码的一般形式可以用同余式
s≡p+k 〔mod 26〕
表示。
有时为了迷惑企图破译的一方,通常将密文分为五个字母一组的形式。如例2可改写为 irrgp ruqlq j。
这种置换密码或它的变种在第二次世界大战之前使用了很长一段时期,但是它有严重缺点.它的加密原理是把26 个字母作一个置换,每个字母用另一个字母去替换(故名置换密码体制),例如,明文中所有出现的字母a,在密文中均换成字母d。因此,使用数学和统计技术〔计算机〕就可以破译这种置换密码。破译置换密码的关键在于确定数字k的值(密钥)。破译的方法有两种:〔1〕穷举法。即对k的可能值逐一进行尝试〔关于模n,k的值有n种〕,直到出现有明确意义的明文;〔2〕根据英文字母出现的频率进行解密。因为在英文的日常书面语言中,各个字母使用的频率不同,例如e的频率最高,约为13.04%,其次是t,a,o,I,n,h,r,而字母v,k,j,x,q,z出现最少。通过出密文中出现最多的字母,使之对应于e,去尝试求解,把密文中出现最少的字母分别用v,k,j,x,q,z去进行尝试性求解,再考虑英文词组出现的频率并联系上下文,运用统计分析方法破译置换密码,已不是十分困难的事情。
3.仿射变换密码
仿射变换密码是比置换密码更复杂的一种密码,它将明文p变为密文s的变换由同余式
                          s≡〔mod 26〕                      〔1〕
确定。其中〔a,26〕=1。因为小于26并且与26互素的正整数有12个,按模26同余,b有26种可供选择,所以由〔1〕式确定的仿射变换共有12×26=312种,可见仿射变换比置换密码要复杂,从而破译它也就更困难。
在仿射密码中,密码的收发双方均使用同一把密钥。发送者用这把密钥加密,接受者也用它解密。
注:因26=2×13,故小于26并且与26互素的正整数有 26(=12 个。
4.序列加密密码
第二次世界大战以后,密码体制发生了巨大的变化.由于电子通讯和计算机的发展,信息传输多采用二进制形式.下表是目前国际上通用的国际电码,它把26个英文字母和6个打字机功能符号共32个对象分别表示成二进制下的32个五位数。
幼儿园毕业寄语
字母
A
B
C
D
E
F
G
H
I
J
K
编码
11000
10011
01110
10010
10000
10110
01011
00101
01100
11010
11110
字母
L
M
N
O
P
Q
R
S
T
U
V
编码
01001
00111
来电狂响的演员
00110
00011
01101
11101
01010
10100
00001
11100
01111
字母
W
X
Y
Z
/
具惠善晒成绩单▼
编码
11001
10111
巴图的父亲
10101
10001
00100
教导处教学工作总结01000
00010
11011
00000
11111
罗云熙个人资料
还有一种传统的密码编译法,称为序列加密密码体制。即 密文 = 明文 + 约定数。例如,我们设明文用0、1这两个数字编码,收发双方约定一个数列,明文加上这个数列那么得到密文。
例3. 如果发送信息“good〞,按照国际电码表,“
  明  文  0  1  0  1  1  0  0  0  1  1  0  0  0  1  1  1  0  0  1  0
+) 约定数  0  0  0  1  0  0  1  1  0  1  0  1  1  1  1  0  0  0  1  0
        密  文  0  1  0  0  1  0  1  1  1  0  0  1  1  0  0  1  0  0  0  0
将密文用国际电码表翻成字母,就成为Lcie。注意这里明文“good〞中两个相同字母“o〞被加密成两个不同的字母“c、i〞,所以这不是置换加密。其中密文由明文 + 约定数,按模2的加法〔即1+1=0,1+0=0+1=1,0+0=0〕得到。这个约定数即密钥。用同余式表示即为:
密文(数)≡ 明文(数)+ 约定数。(mod 2)
对方收到密文后,同样用密钥相加〔由于模2的减法等于加法,因此一台机器既可用来加密又可解密〕,即
明文(数)≡ 密文(数)+ 约定数。(mod 2)
这个约定数〔周期数列〕应是伪随机数列。它可以按某种规那么随机改变,使得破译更加困难。在二战期间,德国人用这种方法编译密码,数学家图灵利用数学原理,发明了一种破译机器,帮助英国多次破译出德国人用这种方法发出的密码,为盟国赢得战场的主动权,屡屡重创敌人。
三、现代密码系统,RSA密码体制
1.对编码体制的思考
如何设计编码〔即加密〕体制?仅靠“小心谨慎〞是不够的。现在密码分析者有大量的理论和技术可供使用,他们既有功能强大的计算设备,又有复杂的数学和统计技术,恺撒用过的那种简单的密码肯定是极不安全的。不管选择什么方法编码,只要在编好的密文中存在某种“可被辨认〞的模式,高级的统计分析方法一般不难破译它。为了使信息能安全地到达
接受者处〔可能远隔千里〕,关键在于这种隐藏着的规那么应埋的足够深,以防被敌人发现。
所有现代密码体制都要使用计算机,一般都假定敌人拥有强大的计算机来分析你的信息,所以你的密码体制必须足够复杂,以防计算机的攻击。为了使所设计的密码体制尽可能安全,它应该由两个部分组成:一个加密程序和一把钥匙。前者是典型的计算机程序〔或专门设计的计算机〕;后者〔钥匙〕通常是一个秘密选定的数。加密程序将依赖这把选定的钥匙对信息编码加密,使得只有知道这把钥匙的人才能解开密文。所以,尽管敌人可能知道你所使用的加密体制而仍无法破译密文,要想破译就必须知道你的密钥。正如一个生产保险柜和锁的工厂,敌人可能知道你的锁是怎样设计的,但是不知道锁的字码仍然无法打开你的保险柜。例如,在序列密码体制中,加密体制可以公开,但是所用的伪随机序列〔钥匙〕一定要某某。
在典型的“密钥体制〞中,信息发送者和接受者事先约定好某种密钥,然后利用它互送信息,只要双方保守钥匙的秘密,该体制一般应该是安全的。例如,美国人设计的数据加密标准DES〔Data Encryption Standard〕就是这种体制,它的钥匙是一个数,其二进制表示
有56个数,即这把钥匙是由56个0或1构成的序列。这种DES加密体制共有256可能的钥匙,虽然没有人对DES体制是如何工作的加以某某,从理论上讲,任何人只要试遍了所有可能的钥匙,就能到哪把钥匙在起作用,但数256如此之大,以至于想试遍所有的钥匙实际上是不可能的。事实上这个数字还没有大到足以保证绝对安全的程度,只不过对任何密码体制都必须兼顾安全性和使用的方便性两个方面的需要。
虽然目前广泛使用着DES,但该体制存在明显的缺陷:在使用前,发送者和使用者必须商定好他们要使用的密钥,因为不愿通过任何通讯渠道传送密钥〔安全因素〕,所以他们必须见面并选定钥匙〔或雇用一个可靠的信使来传送密钥〕。因此这种体制不适合未曾见面的个人之间的通讯。特别地,它不适合现代社会中诸如国际间的银行、商务活动,因为他们往往需要把某某信息发送到世界各地的未曾见过面的人。
2. 密码体制的新方向
1975年,美国的两位密码专家W.迪菲(W.Diffie)和M.赫尔曼(M.E.Hellman)在一篇重要的论文“New Directions Crytography〞〔密码术的新方向〕中提出一种新型的密码体制:公开
密钥的密码系统。这种体制甚至于把加密方法和加密密钥都公开,任何人都可以知道。在公开的密码系统中,编码方法需要两把钥匙而不是一把,其中一把用于加密,另一把用于解密〔好象一把锁要用一把钥匙把它锁上,用另一把钥匙才能把它打开〕。
传统的某某系统,信息的收发双方有相同的加密密钥和解密密钥,而且加密密钥和解密密钥二者也是相同的,密钥需要严格某某不能丢失。这样,整个系统的密钥数量往往很大,难以分配和管理。另一方面,信息的收方可以修改内容,发方也可以否认自己所发内容,双方可能由此产生争执。公开密钥体制的最重要之处有两点:一是将加密密钥和解密密钥分开,加密密钥可以公开,而解密密钥那么严格某某。二是这一体制可以发送签了名的信息。因此,公开密钥体制的提出,解除了上述传统密码系统存在的缺陷,这是密码学中的重大突破,已经成为现代密码学的一个主要研究方向。