第五章密码技术5.1密码技术概述密码学(Cryptology)是一门古老而深奥的学科,有着悠久、灿烂的历史。密码技术是研究数据加密、解密及变换的科学,涉及数学、计算机科学、电子与通讯等诸多学科。虽然其理论相当高深,但概念却十分简单。密码技术包含两方面密切相关的内容,即加密和解密。加密就是研究、编写密码系统,把数据和信息转换为不可识别的密文的过程,而解密就是研究密码系统的加密途径,恢复数据和信息本来面目的过程。加密和解密过程共同组成了加密系统。在加密系统中,要加密的信息称为明文(Plaintext),明文经过变换加密后的形式称为密文(Ciphertext)。由明文变为密文的过程称为加密(Enciphering),通常由加密算法来实现。由密文还原成明文的过程称为解密(Deciphering),通常由解密算法来实现。对于较为成熟的密码体系,其算法是公开的,而密钥是保密的。这样使用者简单地修改密钥,就可以达到改变加密过程和加密结果的目的。密钥越长,加密系统被破译的几率就越低。根据加密和解密过程是否使用相同的密钥,加密算法可以分为对称密钥加密算法(简称对称算法)和非对称密钥加密算法(简称非对称算法)两种。通过对传输的数据进行加密来保障其安全性,已经成为了一项计算机系统安全的基本技术,它可以用很小的代价为数据信息提供相当大的安全保护,是一种主动的安全防御策略。5.2传统的加密方法传统的加密方法有三种:替换密码、变位密码以及一次性加密。5.2.1替换密码替代密码是用一组密文字母来代替一组明文字母以隐藏明文,同时保持明文字母的位置不变。最古老的一种替换密码是恺撒密码,恺撒密码又被称为循环移位密码。其优点是密钥简单易记,但由于明文和密文的对应关系过于简单,所以安全性较差。对于恺撒密码的另一种改进办法是,使明文字母和密文字母之间的映射关系没有规律可循。如将26个字母中的每一个都映射成另一个字母,这种方法称为单字母表替换,其密钥是对应于整个字母表的26个字母串。由于替换密码是明文字母与密文字母之间的一一映射,所以在密文中仍然保存了明文中字母的分布频率,这使得其安全性大大降低。小知识:在英文中,e是最常用的字母,接下来是t,o,a,n,i等。最常用的两个字母的组合是th,in,er,re和an。最常见的三个字母的组合是the,ing和ion。5.2传统的加密方法5.2.2变位密码在替换密码中保持了明文的符号顺序,只是将它们隐藏起来,而变位密码却是要对明文字母作重新排序,但不隐藏它们。常用的变位密码有列变位密码和矩阵变位密码。1.列变位密码列变位密码的密钥是一个不含任何重复字母的单词或短语,然后将明文排序,以密钥中的英文字母大小顺序排出列号,最后以列的顺序写出密文。2.矩阵变位密码矩阵变位密码是把明文中的字母按给定的顺序排列在一个矩阵中,然后用另一种顺序选出矩阵的字母来产生密文。5.2传统的加密方法5.2.3一次性加密如果要既保持代码加密的可靠性,又保持替换加密器的灵活性,可采用一次性密码进行加密。首先选择一个随机比特串作为密钥。然后把明文转换成一个比特串,最后逐位对这两个比特串进行异或运算。例如,以比特串“011010101001”作为密钥,明文转换后的比特串为“101101011011”,则经过异或运算后,得到的密钥为“110111110010”。这种密文没有给破译者提供任何信息,在一段足够长的密文中,每个字母或字母组合出现的频率都相同。由于每一段明文同样可能是密钥,如果没有正确的密码,破译者是无法知道究竟怎样的一种映射可以得到真正的明文,所以也就无法破译这样生成的密文。与此同时,一次性加密在实践中也暴露出了许多的缺陷。第一,一次性加密是靠密码只使用一次来保障的,如果密码多次使用,密文就会呈现出某种规律性,就有被破译的可能。第二,由于这种密钥无法记忆,所以需要收发双方随身携带密钥,极不方便。第三,因为密钥不可重复,所以可传送的数据总量受到可用密钥数量的限制。第四,这种方法对丢失信息或信息错序十分敏感,如果收发双方错序,那么所有的数据都将被篡改。5.3常用加密技术介绍5.3.1DES算法数据加密标准DES(DataEncryptionStandard)是美国国家标准局于1977年公布的由IBM公司研制的加密算法。DES被授权用于所有非保密通信的场合,后来还曾被国际标准组织采纳为国际标准。DES是一种典型的按分组方式工作的单钥密码算法。其基本思想是将二进制序列的明文分组,然后用密钥对这些明文进行替代和置换,最后形成密文。DES算法是对称的,既可用于加密又可用于解密。它的巧妙之处在于,除了密钥输入顺序之外,其加密和机密的步骤完全相同,从而在制作DES芯片时很容易达到标准化和通用化,很适合现代通信的需要。DES算法将输入的明文分为64位的数据分组,使用64位的密钥进行变换,每个64位的明文分组数据经过初始置换、16次迭代和逆置换三个主要阶段,最后输出得到64位的密文。在迭代前,先要对64位的密钥进行变换,密钥经过去掉其第8、16、24、。。。、64位减至56位,去掉的那8位被视为奇偶校验位,不含密钥信息,所以实际密钥长度为56位。DES加密概况如图所示:5.3常用加密技术介绍5.3常用加密技术介绍DES算法的初始置换过程为:输入64位明文,按初始置换规则把输入的64位数据按位重新组合,并把输出分为左右两部分,每部分各长32位。即将输入的第58位换到第一位,第50位换到第2位,第12位换到第3位,依此类推,最后一位是原来的第7位。例如:置换前的输入值为D1D2D3。。。。。。D64,则经过初始置换后,左面部分为:D58D50。。。D8,右面部分位:D57D49。。。D7。DES算法的迭代过程为:密钥与初始置换后的右半部分相结合,然后再与左半部分相结合,其结果作为新的右半部分。结合前的右半部分作为新的左半部分。这样一些步骤组成一轮。这种过程要重复16次。在最后一次迭代之后,所得的左右两部分不再交换,这样可以使加密和解密使用同一算法。如图所示:5.3常用加密技术介绍5.3.2IDEA算法国际数据加密算法IDEA(InternationalDataEncryptionAlgorithm)是瑞士的著名学者提出的。IDEA是在DES算法的基础上发展起来的一种安全高效的分组密码系统。IDEA密码系统的明文和密文长度均为64比特,密钥长度则为128比特。其加密由8轮类似的运算和输出变换组成,主要有异或、模加和模乘三种运算。其加密概况如图所示:5.3常用加密技术介绍5.3常用加密技术介绍IDEA密码系统在加密和解密运算中,仅仅使用作用于16比特子块对的一些基本运算,因此效率很高。IDEA密码系统具有规则的模块化结构,有利于加快其硬件实现速度。由于IDEA的加密和解密过程是相似的,所以有可能采用同一种硬件器件来实现加密和解密。IDEA算法的密钥长度为128位,是DES密钥长度的两倍。它能够抵抗差分密码分析方法和相关密钥密码分析方法的攻击。科学家已证明IDEA算法在其8轮迭代的第4轮之后便不受差分密码分析的影响了。假定穷举法攻击有效的话,那么即使设计一种每秒种可以试验10亿个密钥的专用芯片,并将10亿片这样的芯片用于此项工作,仍需1013年才能解决问题。目前,尚无一片公开发表的试图对IDEA进行密码分析的文章。因此,就现在来看应当说IDEA是一种安全性好、效率高的分组密码算法。5.3常用加密技术介绍5.3.3RSA算法RSA算法是公开密钥密码体制中最著名、使用最广泛的一种。首先来对公开密钥密码体制做一了解。公开密钥密码体制,又叫做非对称密钥密码体制,是与传统的对称密钥密码体制相对应的。在传统的加密方法中,加密、解密使用的是同样的密钥,由发送者和接收者分别保存,在加密和解密时使用。通常,使用的加密算法比较简便高效,密钥简短,破译极为困难。但采用这种方法的主要问题是在公开的环境中如何安全的传送和保管密钥。1976年,Diffie和Hellman为解决密钥的分发与管理问题,在“密码学的新方向”一文中,提出了一种新的密钥交换协议,允许在不安全的媒体上通过通讯双方交换信息,安全地传送密钥。在此新思想的基础上,很快出现了公开密钥密码体制。在该体制中,使用一个加密算法E和一个解密算法D,它们彼此完全不同,并且解密算法不能从加密算法中推导出来。此算法必须满足下列三点要求:(1)D是E的逆,即D[E(P)]=P;(2)从E推导出D极其困难;(3)对一段明文的分析,不可能破译出E。5.3常用加密技术介绍从上述要求可以看出,公开密钥密码体制下,加密密钥不等于解密密钥。加密密钥可对外公开,使任何用户都可将传送给此用户的信息用公开密钥加密发送,而该用户唯一保存的私有密钥是保密的,也只有它能将密文恢复为明文。虽然解密密钥理论上可由加密密钥推算出来,但实际上在这种密码体系中是不可能的,或者虽然能够推算出,但要花费很长的时间而成为不可行的,所以将加密密钥公开也不会危害密钥的安全。公开密钥密码体制,是现代密码学最重要的发明和进展。一般理解密码学就是保护信息传递的机密性,但这仅仅是当今密码学的一个方面。对信息发送与接收人的真实身份的验证,对所发出/接收信息在事后的不可抵赖以及保障数据的完整性也是现代密码学研究的另一个重要方面。公开密钥密码体制对这两方面的问题都给出了出色的解答,并正在继续产生许多新的思想和方案。在所有的公开密钥加密算法中,RSA算法是理论上最为成熟、完善,使用最为广泛的一种。RSA算法是由R.Rivest、A.Shamir和L.Adleman三位教授于1978年提出的,RSA就来自于三位教授姓氏的第一个字母。该算法的数学基础是初等数论中的Euler(欧拉)定理,其安全性建立在大整数因子分解的困难性之上。RSA算法是第一个能同时用于加密和数字签名的算法,并且易于理解和操作。RSA算法从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。下面简要的介绍如何运用这种方法。5.3常用加密技术介绍首先准备加密所需的参数:选择两个大的质数p和q,一般的应为100位以上的十进制质数。然后计算n=p×q和z=(p-1)×(q-1)。选择一个与z互为质数的数d。找出e,使得e×d=1modz。其中,(e,n)便是公开密钥,(d,n)便是私有密钥。加密过程为:将明文看作一个比特串,划分成块,使每段明文信息P落在0<P<n之间,这可以通过将明文分成每块有k位的组来实现,并且k为满足2k<n成立的最大整数。对明文信息P进行加密,计算C=Pe(modn)。解密C,要计算P=Cd(modn)。可以证明,在确定的范围内,加密和解密函数是互逆的。为实现加密,需要e和n,为实现解密需要d和n。所以公钥由(e,n)组成,私钥由(d,n)组成。下面是一个简单的例子,我们为明文“SUZANNE”进行加密和解密,如图所示:5.3常用加密技术介绍我们选择了p=3,q=11,则n=33,z=20。因为7和20没有公共因子,所以设d的一个适合的值为d=7。选定这些值后,求解方程7e=1(mod20),得出e=3。然后根据C=P3(mod33)得出明文P的密文C。接收者则根据P=C7(mod33)将密文解密。在上例中,因为质数选择得很小,所以P必须小于33,因此,每个明文块只能包含一个字符。结果形成了一个普通的单字母表替换密码。但它与DES还是有很大区别的,如果p,q的选择为10100,就可得到n=10200,这样,每个明文块就可多达664比特,而DES只有64比特。以上情况并不能说明RSA可以替代DES。相反,它们的优缺点可以很好的互补,RSA的密钥很长,加密速度慢,而采用加密速度快,适合加密较长的报文DES正好弥补了RSA的缺点。即可以把DES用于明文加密,RSA用于DES密钥的加密。这样因使用RSA而耗掉的时间就不会太多。同时,RSA也可以解决DES密钥分配的问题。RSA的缺点主要有:第一,产生密钥很麻烦,受到素数产生技术的限制,因此难以做到一次一密。第二,分组长度太大,为保证安