|
5.3.1 古典密码算法
古典密码大都比较简单，这些加密方法是根据字母的统计特性和语言学知识加密的，在可用计算机进行密码分析的今天，很容易被破译。虽然现在很少采用，但研究这些密码算法的原理，对于理解、构造和分析现代密码是十分有益的。表5-1给出了英文字母在书报中出现的频率统计。
|
表5-1 英文字母在书报中出现的频率
|
|
字母
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
|
频率
|
13.05
|
9.02
|
8.21
|
7.81
|
7.28
|
6.77
|
6.64
|
6.64
|
5.58
|
4.11
|
3.60
|
2.93
|
2.88
|
|
字母
|
N
|
O
|
P
|
Q
|
R
|
S
|
T
|
U
|
V
|
W
|
X
|
Y
|
Z
|
|
频率
|
2.77
|
2.62
|
2.15
|
1.51
|
1.49
|
1.39
|
1.28
|
1.00
|
0.42
|
0.30
|
0.23
|
0.14
|
0.09
|
|
古典密码算法主要有代码加密、替换加密、变位加密、一次性密码簿加密等几种算法。
1．代码加密
代码加密是一种比较简单的加密方法，它使用通信双方预先设定的一组有确切含义的如日常词汇、专有名词、特殊用语等的代码来发送消息，一般只能用于传送一组预先约定的消息。
密文：飞机已烧熟。
明文：房子已经过安全检查。
代码加密的优点是简单好用，但多次使用后容易丧失安全性。
2．替换加密
将明文字母表M中的每个字母替换成密文字母表C中的字母。这一类密码包括移位密码、替换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。这种方法可以用来传送任何信息，但安全性不及代码加密。因为每一种语言都有其特定的统计规律，如英文字母中各字母出现的频度相对基本固定，根据这些规律可以很容易地对替换加密进行破解。以下是几种常用的替换加密算法。
1）移位密码是最简单的一类代替密码，将字母表的字母右移k个位置，并对字母表长度作模运算，其形式为：ek(m)=(k+m)=c mod q，解密变换为：dk(c)=(m-k)=m mod q。凯撒(Caesar)密码是对英文26个字母进行移位代替的密码，其q=26。这种密码之所以称为凯撒密码，是因为凯撒使用过k=3的这种密码。
2）乘数密码也是一种替换密码，它将每个字母乘以一个密钥k，ek(m)=km mod q，其中k和q是互素的，这样字母表中的字母会产生一个复杂的剩余集合，若是和q不互素，则会有一些明文字母被加密成相同的密文字母，而且不是所有的字母都会出现在密文字母表中。异或运算（XOR）也常用于替换加密，加密：c=m XOR k，解密：m=c XOR k。
3）多名或同音替换。每个字母可加密或替换成多个密文字母，这种方法是一种一对多的映射关系，可以挫败一般的频度分析攻击。
3．变位加密
变位加密不隐藏明文的字符，即明文的字母保持相同，但其顺序被打乱重新排列成另一种不同的格式，由于密文字符与明文字符相同，密文中字母的出现频率与明文中字母的出现频率相同，密码分析者可以很容易地由此进行判别。虽然许多现代密码也使用换位，但由于它对存储要求很大，有时还要求消息为某个特定的长度，因而比较少用。以下介绍几种常见的变位加密算法。
1）简单变位加密。预先约定好一组数字表示密钥，将文字依次写在密钥下，再按数字次序重新组织文字实现加密，也有人喜欢将明文逆序输出作为密文。例如
密钥：5 2 4 1 6 3 (密文排列次序)
明文：信息安全技术
密文：技息全信术安
2）列变位法。将明文字符分割成个数固定的分组（如5个一组，5即为密钥！），按一组一行的次序整齐排列，最后不足一组用任意字符填充，完成后按列读取即成密文。如明文是：InformationSecurityTechnology，则分组排列为：
I n f o r
m a t i o
n S e c u
r i t y T
e c h n o
l o g y
则密文是：ImnrelnaSicoftethgoicynyrouTo ,这里的密钥是数字5。解密过程则是按列排列密文，再按行读取即可。
3）矩阵变位加密。将明文中的字母按给定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。一般为按列变换次序，如原列次序为1234，现为2413。如将明文Network Security按行排列在3×6矩阵中，如下所示：
1 2 3 4 5 6
N e t w o r
k S e c u
r i t y
给定一个置换： ，根据给定的次序，按5、2、6、4、1、3的列序重新排列，得到：
5 2 6 4 1 3
o e r w N t
c u e k S
i y r t
所以，密文为：oerwNtc uekS i yrt。解密过程正好相反，按序排列密文后，通过列置换再按行读取数据即可。
4．一次性密码簿加密
一次性密码簿加密具有代码加密的可靠性，又保持了替换加密的灵活性，密码簿每一页都是不同的代码表，可用一页上的代码来加密一些词，用后销毁，再用另一页加密另一些词，直到全部的明文完成加密，破译的唯一方法就是获取一份相同的密码簿。
一次性密码簿加密，要求密码簿至少不小于明文长度，即不得重复用来加密明文的不同部分，否则密文就会呈现出某种规律性，也就可能被破译。一般这种加密方法只用于高度保密的场合下，因为如何将至少同长度的密码簿护送到接收端是一个大代价的行动。
5.3.2 单钥加密算法
传统加密方法的统计特性是此类算法致命的缺陷。为了提高保密强度，可将这几种加密算法结合使用，形成秘密密钥加密算法。由于可以采用计算机硬件和软件相结合来实现加密和解密，算法的结构可以很复杂，有很长的密钥，使破译很困难，甚至不可能。由于算法难以破译，可将算法公开，攻击者得不到密钥，也就不能破译，因此这类算法的保密性完全依赖于密钥的保密，且加密密钥和解密密钥完全相同或等价，又称为对称密钥加密算法，其加密模式主要有序列密码（也称流密码）和分组密码两种方式。
流密码是将明文划分成字符（如单个字母），或其编码的基本单元（如0、1数字），字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流解密。流密码的强度完全依赖于密钥流序列的随机性和不可预测性，其核心问题是密钥流生成器的设计，流密码主要应用于政府和军事等国家要害部门。根据密钥流是否依赖于明文流，可将流密码分为同步流密码和自同步流密码，目前，同步流密码较常见。由于自同步流密码系统一般需要密文反馈，因而使得分析工作复杂化，但其具有抵抗密文搜索攻击和认证功能等优点，所以这种流密码也是值得关注的研究方向。
分组密码是将明文消息编码表示后的数字序列x1，x2，…，xi，…，划分为长为m的组x=(xo，xl，…，xm-1)，各组(长为m的矢量)，分别在密钥k=(ko，k1，…，kL-1)控制下变换成等长的输出数字序列y=(yo，y1，…，yn-1)(长为n的矢量)，其加密函数E：Vn×K→Vn，Vn是n维矢量空间，K为密钥空间。它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是还与一组长为m的明文数字有关。在相同密钥条件下，分组密码对长为m的输入明文组所实施的变换是等同的，所以只需要研究对任一组明文数字的变换规则。这种密码实质上是字长为m的数字序列的代替密码。通常取n=m，若n>m，则为有数据扩展的分组密码，若n<m，则为有数据压缩的分组密码。
围绕单钥密钥体制，密码学工作者已经开发了众多行之有效的单钥加密算法，并且对基于这些算法的软硬件实现进行了大量的工作。常用的单钥加密算法有DES算法、IDEA算法。
1．数据加密标准DES算法
DES算法的发明人是IBM公司的W.Tuchman和C.Meyer，于1971-1972年研制成功。美国商业部的国家标准局NBS于1973年5月和1974年8月两次发布通告，公开征求用于电子计算机的加密算法，经评选从一大批算法中采纳了IBM的LUCIFER方案，该算法于1976年11月被美国政府采用，DES随后被美国国家标准局和美国国家标准协会(American National Standard Institute，ANSI)承认。1977年1月以数据加密标准DES（Data Encryption Standard）的名称正式向社会公布，并于1977年7月15日生效。
DES算法是一种对二元数据进行加密的分组密码，数据分组长度为64bit(8byte)，密文分组长度也是64bit，没有数据扩展。密钥长度为64bit，其中有效密钥长度56bit，其余8bit为奇偶校验。DES的整个体制是公开的，系统的安全性主要依赖密钥的保密，其算法主要由初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器构成。56位DES加密算法的框图如图5-9所示。
|
|
|
图5-9 56位DES加密算法的框图
|
DES加密算法框图明文加密过程如下：
1）将长的明文分割成64位的明文段，逐段加密。将64位明文段首先进行与密钥无关的初始变位处理。
2）初始变位后结果，要进行16次的迭代处理，每次迭代的框图相同，但参加迭代的密钥不同，密钥共56位，分成左右两个28位，第i次迭代用密钥Ki参加操作，第i次迭代完后，左右28位的密钥都作循环移位，形成第i+1次迭代的密钥。
3）经过16次迭代处理后的结果进行左、右32位的互换位置。
4）将结果进行一次与初始变位相逆的还原变换处理得到了64位的密文。
上述加密过程中的基本运算包括变位、替换和异或运算。DES算法是一种对称算法，既可用于加密，也可用于解密。解密时的过程和加密时相似，但密钥使用顺序刚好相反。
DES是一种分组密码，是两种基本的加密组块替代和换位的细致而复杂的结合，它通过反复依次应用这两项技术来提高其强度，经过共16轮的替代和换位的变换后，使得密码分析者无法获得该算法一般特性以外更多的信息。对于DES加密，除了尝试所有可能的密钥外，还没有已知的技术可以求得所用的密钥。
DES算法可以通过软件或硬件实现。
DES算法的安全性。DES的出现是密码学上的一个创举，由于其公开了密码体制及其设计细节，因此其安全性完全依赖于其所用的密钥，关于DES的安全问题，学术界有过激烈的争论，普遍的印象是密钥仅有56bit有点偏短。Diffie和Hellman曾设想花千万美元造一台专用机，渴望一天内找到DES的一个密钥，其基本思想是穷举，即强行攻击（需要255次尝试）。此外，1990年，Eli Biham和Adi Shamir提出用“微分分析法”对DES进行攻击，实际需要247次尝试，也只有理论上的价值。后来，有人提出一种明文攻击法——“线性逼近法”，它需要243对明文-密文对，在这样强的要求条件下，要十多台工作站协同工作花费十几天才能完成攻击。表5-2为不同条件下DES攻击时间的预测。
|
表5-2 不同条件下DES攻击时间的预测
|
|
攻击者类型
密钥长度
|
个人攻击
|
小组攻击
|
院校网络攻击
|
大公司
|
军事情报机构
|
|
计算资源
（假设）
|
1台高性能计算机
|
16台高性能计算机
|
256台高性能计算机
|
大型机
（百万美元级）
|
大型机
（百万美元级）及先进攻击技术
|
|
40 bit
|
数周
|
数日
|
数小时
|
数毫秒
|
数微秒
|
|
56 bit
|
数百年
|
数十年
|
数年
|
数小时
|
数秒钟
|
|
64 bit
|
数千年
|
数百年
|
数十年
|
数日
|
数分钟
|
|
80 bit
|
不可能
|
不可能
|
不可能
|
数百年
|
数百年
|
|
128 bit
|
不可能
|
不可能
|
不可能
|
不可能
|
数千年
|
|
在1977年，人们估计要耗资2000万美元才能建成一个专门计算机用于DES的解密，而且需要12h的破解才能得到结果。1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。1997年1月，用了96天时间，成功地破解了用DES加密的一段信息；一年之后的记录是41天；1998年7月，“第二届DES挑战赛（DES Challenge II-2）” 把破解DES的时间缩短到了只需56h；“第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5h 。总之，随着各种针对DES新攻击手法的不断出现，DES已感觉到了实际的威胁，也许DES即将完成其历史使命。尽管如此，自DES正式成为美国国家标准以来，已有许多公司设计并推广了实现DES算法的产品，有的设计专用LSI器件或芯片，有的用现成的微处理器实现，有的只限于实现DES算法，有的则可以运行各种工作模式。
2．国际数据加密算法IDEA
近年来，新的分组加密算法不断出现，IDEA就是其中的杰出代表。IDEA是International Data Encryption Algorithm的缩写，即国际数据加密算法。它是根据中国学者朱学嘉博士与著名密码学家James Massey于1990年联合提出的建议标准算法PES(Proposed Encryption Standard)改进而来的。它的明文与密文块都是64bit，密钥长度为128bit，作为单钥体制的密码，其加密与解密过程相似，只是密钥存在差异，IDEA无论是采用软件还是硬件实现都比较容易，而且加、解密的速度很快。
IDEA算法是面向块的单钥密码算法，它的安全性与DES类似，不在于算法的保密，而是密钥的安全性。
IDEA的密钥长为128bit，采用穷举搜索进行破译，则需要进行2128次尝试，这将是用同样方法对付DES的272倍工作量。目前，尚未见到成功对IDEA进行攻击的报道，有关学者进行分析也表明IDEA对于线性和差分攻击是安全的。此外，将IDEA的字长由16bit加长为32bit，密钥相应长为256bit，采用232模加，232+1模乘，可以进一步强化IDEA的安全性能。
3．单钥密码算法性能分析
前面详细介绍了单钥密码体制的典型代表DES算法和IDEA算法，其他一些有意义的算法有SAFER K-64(Secure And Fast Encryption Routine)、GOST、RC-4、RC-5、Blowfish、CAST-128等。为了提高单钥密码的安全性，人们还将分组密码算法通过组合以得到新的分组密码算法，但这种组合密码的安全性必须经仔细检验后才能付诸实用，如二重DES加密、三重DES加密等。
由于各种加密算法的具体实现方法互不相同，因此其性能也存在较大差异，表5-3对单钥密码体制的主要算法在总体实现、速度、安全性能和改进措施几个方面进行了比较，并基于比较结果给出了各算法合适的应用场合。
|
表5-3 单钥密码算法性能比较表
|
|
名称
|
实现方式
|
运算速度
|
安 全 性
|
改进措施
|
应用场合
|
|
DES
|
40-56bit
密钥
|
一般
|
完全依赖密钥，易受穷举搜索法攻击
|
双重、三重DES，AES
|
适用于硬件实现
|
|
IDEA
|
128bit密钥
8轮迭代
|
较慢
|
军事级，可抗差值分析和相关分析
|
加长字长为32bit、密钥为256bit，采用232模加、232+1模乘
|
适用于ASIC设计
|
|
GOST
|
256bit密钥
32轮迭代
|
较快
|
军事级
|
加大迭代轮数
|
S盒可随机秘
密选择，便于软件实现
|
|
Blowfish
|
256-448bit
密钥、16轮迭代
|
最快
|
军事级、可通过改变密钥长度调整安全性
|
|
适合固定密钥场合，不适合常换密钥和智能卡
|
|
RC4
|
密钥长度可变
|
快DESl0倍
|
对差分攻击和线性攻击具有免疫能力，高度非线性
|
密钥长度放宽到64bit
|
算法简单，易于编程实现
|
|
RC5
|
密钥长度和迭代轮数均可变
|
速度可根据
三个参数的
值进行选择
|
六轮以上时即可抗线性攻击、通过调整字长、密钥长度和迭代轮数可以在安全性和速度上取得折中
|
引入数据相倚转
|
适用于不同字长的微处理器
|
|
CASTl28
|
密钥长度可变、16轮迭代
|
较快
|
可抵抗线性和差分攻击
|
增加密钥长度、形成CAST256
|
适用于PC机和
UNIX工作站
|
|
5.3.3 双钥加密算法
双钥密码体制的加密密钥和解密密钥不相同，它们的值不等，属性也不同，一个是可公开的公钥，另一个则是需要保密的私钥。双钥密码体制的特点是加密能力和解密能力是分开的，即加密与解密的密钥不同，或从一个难以推出另一个。它可以实现多个用户用公钥加密的消息只能由一个用户用私钥解读，或反过来，由一个用户用私钥加密的消息可被多个用户用公钥解读。其中前一种方式可用于在公共网络中实现保密通信；后一种方式可用于在认证系统中对消息进行数字签名。
双钥加密算法的主要特点如下：
1）用加密密钥PK对明文m加密后得到密文，再用解密密钥SK对密文解密，即可恢复出明文m，即
DSK(EPK(m))＝m
2）加密密钥不能用来解密，即：
DPK(EPK(m))≠m ；DSK(ESK(m))≠m
3）用SK加密的信息只能用PK解密；用PK加密的信息只能用SK解密。
4）从已知的PK不可能推导出SK。
5）加密和解密的运算可对调，即
EPK(DSK(m))＝m
双钥密码体制大大简化了复杂的密钥分配管理问题，但公钥算法要比私钥算法慢得多(约1000倍)。因此，在实际通信中，双钥密码体制主要用于认证（比如数字签名、身份识别等）和密钥管理等，而消息加密仍利用私钥密码体制。下面介绍双钥密码体制的杰出代表――RSA加密算法。
1．RSA算法
RSA体制是由R.L.Rivest、A.Shamir和L.Adleman设计的用数论构造双钥的方法，它既可用于加密，也可用于数字签名。RSA得到了世界上的最广泛应用，ISO在1992年颁布的国际标准X.509中，将RSA算法正式纳入国际标准。1999年，美国参议院已经通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。在Internet中广泛使用的电子邮件和文件加密软件PGP(Pretty Good Privacy)也将RSA作为传送会话密钥和数字签名的标准算法。RSA算法的安全性建立在数论中“大数分解和素数检测”的理论基础上。
（1）大数分解
双钥密码体制算法按由公钥推算出密钥的途径可分为两类：一类是基于素数因子分解问题的(如RSA算法)，它的安全性基于100位十进制数以上的所谓“大数”的素数因子分解的难题，这是一个至今没有有效快速算法的数学难题。另一类是基于离散对数问题的(如EIGamal算法)，其安全性基于计算离散对数的困难性。离散对数问题是指模指数运算的逆问题，即找出一个数的离散对数。一般地，计算离散对数是非常困难的。
RSA算法运用了数论中的Euler同余定理：即a、r是两个互质的自然数，则az=1 (mod r),其中z为与r互质的且不大于r的自然数，称z为r的Euler指标函数。
（2）RSA算法表述
假定用户A欲送消息m给用户B，则RSA算法的加／解密过程为：
1）首先用户B产生两个大素数p和q(p、q是保密的)。
2）用户B计算n=pq和φ(n)=(p-1)(q-1)(φ(n)是保密的)。
3）用户B选择一个随机数e(0<e<φ(n))，使得(e，φ(n))=1，即e和φ互素。
4）用户B通过计算得出d，使得d*e mod φ(n)=1(即在与n互素的数中选取与φ(n)互素的数，可以通过Euclidean算法得出。d是用户B自留且保密的，用作解密密钥)。
5）用户B将n及e作为公钥公开。
6）用户A通过公开渠道查到n和e。
7）对m施行加密变换，即EB(m)=me mod n=c。
8）用户B收到密文c后，施行解密变换
DB(c)=cd mod n=(me mod n)d mod n=med mod n=m mod n
下面举一个简单的例子用于说明这个过程：令26个英文字母对应于0到25的整数，即a-00，b-01，…，y-24，z-25。设，m=inclub，则m的十进制数编码为：m=08 13 02 11 20 01。设n=3×11=33,p=3,q=11, φ(n)=2×10=20。取e=3，则d=7将n=33和e=3公开，保留d=7。
用户A查到n和e后，将消息m加密：
EB(i)=083 mod 33= 17,
EB(n)=133 mod 33= 19,
EB(c)=023 mod 33= 8,
EB(l)=113 mod 33= 11,
EB(u)=203 mod 33= 14,
EB(b)=013 mod 33= 1,
则 c= EB(m) = 17 19 08 11 14 01,它对应的密文为
c=rtilob
当用户B接到密文c后施行解密变换：
DB(r) = 177 mod 33= 8，即明文i，
DB(t) = 197 mod 33= 13，即明文n，
DB(i) = 087 mod 33= 2，即明文c，
DB(l) = 117 mod 33= 11，即明文l
DB(o) = 147 mod 33= 20，即明文u,
DB(b) = 017 mod 33= 1，即明文b。
（3）RSA安全性分析
RSA的保密性基于一个数学假设：对一个很大的合数进行质因数分解是不可能的！若RSA用到的两个质数足够大，可以保证使用目前的计算机无法分解。即RSA公开密钥密码体制的安全性取决于从公开密钥（n，e）计算出秘密密钥（n，d）的困难程度。想要从公开密钥（n，e）算出d，只能分解整数n的因子，即从n找出它的两个质因数p和q，但大数分解是一个十分困难的问题。RSA的安全性取决于模n分解的困难性，但数学上至今还未证明分解模就是攻击RSA的最佳方法。尽管如此，人们还是从消息破译、密钥空间选择等角度提出了针对RSA的其他攻击方法，如迭代攻击法、选择明文攻击法、公用模攻击、低加密指数攻击、定时攻击法等，但其攻击成功的概率微乎其微。
出于安全考虑，在RSA中，建议使用1024bit的n，对于重要场合n应该使用2048位。
2．ElGamal算法
RSA算法是基于素数因子分解的双钥密码，而ElGamal算法则是基于离散对数问题的另一种类型的双钥密钥，它既可用于加密，也可用于签名。
（1）ElGamal算法方案
1985年，ELGamal第一次在有限域上基于离散对数问题设计了原始的ElGamal数字签名方案。
令p是使在GF（p）域计算离散对数在多项式时间内是不可行的大素数。引进集合Zp ={0,1,2,…，p}及其子集Zp*={0,1,2,…，p-1}。令g∈Zp*，是本原元，定义：密钥集K={（p,g,x,y）:y=gx mod p}，这里p,g,y是公钥，x是用户选择的私钥，x∈Zp*且gcd(x,p-1)=1。即产生密钥对时，首先选择一个素数p，两个Zp*中的随机数g和x, 计算 y = gx mod p ，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
（2）ElGamal加、解密及其安全性
选择随机数k∈zp-1，且(k，p-1)=1，计算：y1=gkmod p(随机数k被加密)，y2=myk mod p，这里，m是发送明文组。密文则由y1和y2级连构成，即密文C=y1‖y2。这种加密方式的特点是，密文由明文和所选随机数k来决定，因而是非确定性加密，一般称之为随机化加密，对同一明文由于不同时刻的随机数k不同而给出不同的密文，这样做的代价是使数据扩展1倍。
在收到密文组C后，ElGamal的解密是通过下列计算得到明文的：
ElGamal算法的安全性是基于zP*中有限群上的离散对数的困难性的。研究表明，mod p生成的离散对数密码可能存在陷门，这会造成有些“弱”素数p下的离散对数较容易求解，但密码学家也发现可以较容易地找到这类陷门以避免选用可能产生脆弱性的这些素数。
3．双钥算法小结
双钥密钥体制的密钥管理和分配较简单，尤其可方便地用于数字签名和认证。虽然其算法都较复杂，运算量巨大，但其仍不失为一种非常有前途的加密体制，它的出现是密码学发展史上的划时代事件。上面我们分析了双钥密码体制的典型代表RSA算法和ElGamal算法，还有其他一些有意义的算法，如LUC密码、Rabin密码，以及DSA密码等。
对于RSA体制，可以将其推广为有多个密钥的双钥体制，即在多个密钥中选用一部分密钥作为加密密钥，而另一些作为解密密钥。同样地，RSA还可以推广为多签名体制，如有k1、k2和k3三个密钥，可将k1作为A的签名私密钥，k2作为B的签名私密钥，k3作为公开的验证签名用密钥，实现这种多签名体制，需要一个可信赖中心对A和B分配秘密签名密钥。
|
