《网络信息安全》课件第2章

第2章密码技术2.1密码学基本概念2.2古典密码2.3对称密码2.4公钥密码2.5消息验证和数字签名

习题

2.1密码学基本概念

密码学是研究如何实现数据加密的学科，密码学包括两方面内容，即密码编码学和密码分析学。将数据保密的技术和科学叫做密码编码学，与此对应的是破译密文的技术和科学叫做密码分析学。

假设发送者Alice想安全地发送消息m给接收者Bob，利用加密技术的通信过程如图2-1所示。由于窃听者Eve只能看到加密后的密文信息故不能知道消息m的内容。其中，消息m被称为明文(plaintext)。对需要保密的消息进行编码的过程称为加密，编码的规则称为加密算法，被加密的消息称为密文(ciphertext)，而把密文转变为明文的过程称为解密，解密的规则称为解密算法。

图2-1加密和解密

密码算法是用于加密和解密的数学函数，如果密码算法的保密性是基于算法的保密，这种算法称为受限制的算法，这种算法具有历史意义，但按照现在的安全标准，它们的保密性已远远不够，现代密码学采用密钥来解决这个问题，密钥用K来表示(如图2-2所示)。加密算法和解密算法通常在一对密钥(K)的控制下进行，分别称为加密密钥和解密密钥。

图2-2有密钥的加密和解密

一个现代密码系统(体制)包括所有可能的明文、密文、密钥、加密算法和解密算法，所有这些算法的安全性都基于密钥的安全性，而不是基于算法的细节的安全性。这就意味着算法可以公开，即使窃听者知道你的算法也没有关系，如果他不知道你使用的具体密钥，就不可能阅读到你的消息。密码系统根据密钥可以分为两类，即为对称密钥系统和公钥系统。对称密钥系统就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。公钥系统又称公开密钥系统或非对称密钥系统，有两个密钥，一个是公开的，用K1表示，谁都可以使用，也叫加密密钥；另一个是私人密钥，用K2来表示，只能由采用此系统的人自己掌握，也叫解密密钥。从公开的密钥推不出私人密钥。

数据加密算法有很多种，密码算法标准化是信息化社会发展的必然趋势，是世界各国保密通信领域的一个重要课题。按照发展进程来分，经历了古典密码、对称密钥密码和公开密钥密码阶段。古典密码算法有替代加密、置换加密；对称加密算法包括DES和AES；非对称加密算法包括RSA等。目前在数据通信中使用最普遍的算法有DES算法、RSA算法和PGP算法等。

2.2古

典

密

码

1．代替密码

(1)单表代替密码又可以称为单字母密码：就是明文的一个字符用相应的一个密文字符代替。著名的恺撒密码就是一种简单的代替密码。其加密原理就是每一个明文字符都由其右边第3个字符代替，那么3就是这个算法的密钥，即A由D代替，B由E代替，…，W由Z代替，X由A代替，Y由B代替，Z由C代替。若明文为student，则对应的密文为VWXGHQW(此时密钥为3)。恺撒密码仅有26个可能的密钥，非常的不安全。

由于英文字母中各字母出现的频率有明显的固有特征，而单表代替密码没有把明文中的不同字母的出现频率掩盖起来，因此根据字母频率表可以很容易对替换密码进行破译。代替密码是对所有的明文字母都用一个固定的代替密码进行加密，故也叫单表代替密码。为了防止字母频率分析攻击，随后产生了多表代替密码和多字母代替密码。

(2)多表代替密码由LeonBattista在1568年发明，在美国南北战争中使用。多表代替密码中最著名的一种密码是维吉尼亚密码，Vigenere是法国密码学专家。维吉尼亚密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母，等等。在所有密钥用完后，密钥又再循环使用，其中密钥的长度就是密码的周期，在古典密码学中，密码周期越长越难破译。例如，明文为system，密钥为dog，加密过程如下：

明文：system密钥：dogdog密文：vmgwrs其中，密钥字母a、b、c、d、...、x、y、z对应的数字为：0、1、2、3、...、24、25。密钥字母d对应数字3，所以明文字母s在d作用下右移3位，得到密文字母v，明文字母y在o作用下右移14位可以得到密文字母m，依次类推。解密时，密文字母在密钥字母的作用下向前移位即可得到对应的明文字符。多表代替密码结果将使得对单表代替用的字母简单频率分析方法失效，但使用计算机可以轻易破译具有很长周期的代替密码。

(3)多字母代替密码：在前面介绍的两种算法中，明文中的每一个字符都是以单个字母作为代替的对象，如果用多于一个字母代替明文字符就是多字母代替密码，它的优点是容易将字母的频率隐藏，从而抗击字母统计分析。这种密码首先是由Playfair在1854年发明的，另外一个使用相对较多的多字母代替密码例子是Hill密码，但这类密码由于加密过于复杂而且不是非常安全，因此未能广泛应用。

2．换位密码在换位密码中，明文的字母数保持相同，但相互之间的顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。

2.3对

称

密

码

1．对称密码简介 如果一个加密系统的加密密钥和解密密钥相同，或者虽然不相同，但是由其中的任意一个可以很容易地推导出另一个，则该系统所采用的就是对称密码体制。对称密码体制的优点是具有很高的保密强度，可以达到经受较高级破译力量的分析和攻击。但它的密钥必须通过安全可靠的途径传递，密钥管理成为影响系统安全的关键性因素，使它难以满足系统的开放性要求。

对称密码体制根据对明文加密方式的不同而分为分组密码和流密码(又叫序列密码)。序列密码则一次只对明文中的单个位(有时也对字节)加/解密，对输入元素进行连续处理，同时产生连续单个输出元素。而分组密码是先按一定长度如64字节、128字节等对明文进行分组，然后以组为单位进行加/解密，一次处理一块输入明文，每个输入块生成一个输出块，各分组分别在密钥的控制下变换成等长度的密文分组。现代计算机加/解密典型分组长度为64位，这个分组不仅有防止分析破译的足够强度，又可以方便使用。数据加密标准(DES，DataEncryptionStandard)是一种最通用的计算机加密算法，属于分组密码的一种。

2．DES加密数据加密标准是最通用的算法之一，1973年5月美国国家标准局(NBS，NationalBureauofStandyards)公布了一则公告，征求国家密码标准方案。1975年3月NBS公布了IBM公司提供的密码算法，以标准建议的形式在全国范围内征求意见。在经过大量公开讨论之后，该密码算法于1977年1月15日正式被批准为美国联邦信息处理标准，并授权在非密级的政府通信中使用，同年7月15日生效。

DES是一个分组加密算法，以64位为分组对数据加密。64位一组的明文从算法的一端输入，64位的密文从另一端输出。DES是一个对称算法：加密和解密都用同一个算法(除密钥编排不同)。密钥长度也是64位，其中每个第8位都用作奇偶校验，因此实际有效密钥长度为56位，是可以任意改变的56位数。DES算法是公开的，其安全性依赖于密钥的保密程度。

DES算法描述，先进行64位的明文分组操作，将该分组用初始置换IP进行置换，得到一个乱序的64位明文分组，然后将分组分成左、右等长的两边，各为32位长，记作L0和R0。在进行16轮完全类似的迭代运算后(其中F是在运算过程中将数据与密钥结合在一起的函数)，把所得到的左、右长度相等的两半L16和R16交换，从而得到64位数据R16L16，最后再用初始逆置换(IP－1)进行置换，可以得到64位密文分组。加密算法过程如图2-3所示。

图2-3加密算法过程

初始置换是在第一轮迭代前执行，对输入64位分组实现如图2-4所示变换。此图顺序为从上到下，从左到右。例如，初始置换把明文的第58位换到第一位，把50位换到第二位，以次类推。产生子密钥Ki，如果不考虑每一个字节的第八位(即校验位)，DES的密钥可以由64位减少到56位。在DES加密算法中，将用户提供的64位初始密钥经过一系列的处理得到K1、K2、…、K16，分别作为1～16轮运算的16个子密钥。先将64位密钥去掉8个校验位，用密钥置换(图2-5)剩下的56位密钥；再将56位分成两个部分，各28位，然后根据轮数(图2-6)，这两部分分别循环左移1位或2位。

图2-4初始置换表IP图2-5密钥置换表

图2-6密钥每轮移动的位数

移动后，将两部分合并成56位再通过压缩置换(如图2-7所示)，从而得到48位子密钥。

图2-7压缩置换

这样经过16次运算就可以得到迭代运算所需的16个48位子密钥。

F函数是由数据扩展、与子密钥的异或运算、S盒代替、P盒置换组成，输入是由32位数据和48位的子密钥组成，下面分别介绍这几种运算：数据扩展也可以称为E盒扩展(如图2-8)，此运算将数据的右半部分Ri从32位扩展到48位，可以产生与密钥同长度的数据进行异或运算，同时也可以使输入的一位影响两个替换，从而使输出对输入的依赖性传播得更快。

图2-8扩展置换E异或，就是将扩展后的48位输出数据E(Ri)和压缩后的子密钥Ki作异或运算。

S盒代替，就是将异或得到的48位结果分成八个6位的块，每一块作为每个S盒的输入，同时每个S盒产生一个4位的输出，这样8个S盒就可以产生32位的输出(如图2-9所示)。

图2-9S盒构成对于每一个Si，由6位输入中的第1和第6位组成的二进制数确定Si的行，中间其余的4位二进制数用来确定Si的列。Si中相应的行、列位置的十进制数的4位二进制数用来作为输出。例如，某个S2输入为101001，则行数和列数的二进制数分别表示11和0100，即十进制数下的第3行和第4列，而在S盒2中第3行第4列的十进制数为3，用4位二进制数表示为0011，所以S2的输出为0011，从而可以用值0011代替101001。经过S盒置换，对8个4位分组进行重新组合，可以形成一个32位的分组。

P置换，即将S盒代替运算后的32位输出按照P盒表(如图2-10)进行置换，该置换把每输入位对应到输出位上，任何一位不能被置换二次，也不能被忽略。例如，将第29位移动到第5位处，而把第5位移动到第13位处，以次类推。

图2-10P盒置换

初始逆置换是初始置换的逆过程，就是将最后一轮迭代所得64位数据R16L16用初始逆置换IP－1(如图2-11)进行置换，产生64位密文分组。

图2-11逆置换

DES解密，明文虽然经过许多轮的代替、置换、异或和循环移动之后，产生对应的密文，但由于经过精心选择各种操作，因此加密和解密可以使用相同的算法，惟一不同的是各轮密钥使用的次序相反，比如各轮加密密钥分别是K1、K2、K3、…、K16，那么，解密密钥就是K16、K15、…、K3、K2、K1。

DES工作模式有四种：电子密本(ECB)，密码分组链接(CBC)，密文反馈(CFB)和输出反馈(OFB)。这四种模式中ECB方式比较简单，也最容易受到攻击，但在流行的商业软件中，仍然是最常用的方式。

3．DES算法中的关键函数设计

1)函数F的设计函数F的基本功能就是“扰乱(confusion)”输入，因此，对于F来说，其非线性越高越好，也就是说，要恢复F所做的“扰乱”操作越难越好。其他的设计准则还包括严格雪崩准则(SAC)和比特独立准则(BIC)。所谓SAC，就是要求算法具有良好的雪崩效应，输入当中的一个比特发生变化都应当使输出产生尽可能多的比特变化。严格地说，就是当任何单个输入比特位i发生变换时，一个S盒的第j比特输出位发生变换的概率应为1/2，且对任意的i,j都应成立。BIC的意思是当单个输入比特位i发生变化时，输出比特位j,k的变化应当互相独立，且对任意的i,j,k均应成立。SAC和BIC可以有效地增强F函数的“扰乱”功能。

2)S盒设计

S盒的设计在对称分组密码研究领域中起着举足轻重的作用。本质上，S盒的作用就是对输入向量进行处理，使得输出看起来更具随机性，输入和输出之间应当是非线性的，很难用线性函数来逼近。显然，S盒的尺寸是一个很重要的特性。S盒越大，越容易抵制差分和线性密码分析。在实践当中，通常选择n在8～10之间。

Mister和Adams提出了很多的S盒设计原则，其中包括要求S盒满足SAC和BIC的原则，以及S盒的所有列的全部线性组合应当满足一类称为Bent函数的高度非线性布尔函数的原则。Bent函数具有很多有趣的特性，其中，高度非线性和最高阶的严格雪崩准则对于S盒的设计尤为重要。

Nyberg提出了以下几种S盒的设计和实践原则：

(1)随机性：采用某些伪随机数发生器或随机数表格来产生S盒的各个项。

(2)随机测试：随机选择S盒各个项，然后按照不同准则测试其结果。

(3)数学构造：根据某些数学原理来产生S盒。其好处就是可以根据数学上的严格证明来抵御差分和线性密码分析，并且可以获得很好的扩散(Diffusion)特性。

2.4公

钥

密

码

1.公钥密码简介在对称密钥密码体制中，加密运算与解密运算使用同样的密钥。通常使用的加密算法比较简便高效、密钥简短、破译极其困难。但是，在公共的计算机网络上安全地传送和保管密钥是一个严峻的问题。

为了解决上述问题，1976年由WhitefieldDiffie和MartinHellman首先提出公开密钥密码学的概念。同时，RalphMerkle也独立地提出了这一体制。它的基本思想是采用一对密钥，加密密钥和解密密钥(且从加密密钥推出解密密钥是不可行的)，在这一对密钥中，一个可以公开(称为公钥)，另一个为私人专用(称为私钥)，它是基于陷门单向函数的概念。如果对一个函数f的定义域上的任意一个x都容易计算f(x)，但对f的值域上的任意一个y，f-－1(y)在计算上是不可行的，就称f是单向函数。如果进一步给定某些辅助信息，计算f-－1(y)又变得容易，则称f是陷门单向函数。这个辅助信息也就是私人密钥。

2.RSA密码系统到目前为止，使用最广泛的公开密钥系统是RSA公开密钥密码系统，它是由R.Rivest、A.Shamir和L.Adleman提出的。RSA的取名就是来自于这三位发明者的姓的第一个字母，后来，他们在1982年创办了以RSA命名的公司RSADataSecurityInc.和RSA实验室，该公司和实验室在公开密钥密码系统的研究和商业应用推广方面具有举足轻重的地位。

RSA密码系统的安全是基于大整数分解因子的难度，其公开密钥(现在一般是1024位甚至更长)和私人密钥是一对大素数的函数。一般来说，求一对大素数的乘积相对比较容易，但要对这个乘积进行因式分解则非常困难。因此，可以把一对大素数的乘积作为公开密钥公布，而把素数作为私钥，从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。

建立RSA密码系统过程如下：

(1)选取两个大素数p和q，p和q的位数差不多大小。

(2)计算乘积n＝pq和Ф(n)＝(p－1)(q－1)。

(3)随机选取加密密钥e，使e和(p－1)(q－1)互素，也即gcd(e,Ф(n))＝1。

(4)计算解密密钥d，以满足ed＝1modФ(n)，即e与d互逆，d与n是互素的。

(5)加密函数为：E(x)＝memodn，解密函数为：D(x)＝cdmodn，其中m是明文，c是密文。

(6){e，n}为公开密钥，d为私人密钥，p、q不再需要，可以丢弃，但不能泄露。一般n的长度是1024位或者更长。

RSA加密消息m时，首先将消息分成大小合适的数据分组，然后对分组分别进行加密，每个分组的长度均应该比n的位数要小。举例，选择两个小的素数取p＝11，q＝13，p和q的乘积为n＝p×q＝143，算出另一个数Ф(n)＝(p－1)(q－1)＝120；再选取一个与z＝120互质的数，例如e＝7，对于这个e值，可以算出另一个值d＝103满足e×d＝1modz；其实7×103＝721除以120确实余1。(n,e)和(n,d)这两组数分别为公开密钥和私人密钥。设想A需要发送机密信息(明文，即未加密的报文)m＝85给B，A已经从公开媒体得到了B的公开密钥(n,e)＝(143,7)，于是A算出加密值c＝me

modn＝857mod143＝123并发送给B。B在收到“密文”(即经加密的报文)c＝123后，利用只有B自己知道的私人密钥(n,d)＝(143,123)计算123123mod143，得到的值就是明文(值)85，实现了解密。在RSA的加/解密过程中都涉及到求一个大整数的幂，然后模n，所以加/解密的速度会比较慢，不论在硬件实现时还是软件实现时，RSA比DES要慢很多。一般公钥密码系统用于以下几个方面：通信保密、数字签名和密钥交换。

3．Diffie-Hellman密钥交换

Diffie-Hellman算法是第一个公开密钥算法，发明于1976年。Diffie-Hellman算法能够用于密钥分配，但不能用于加密或解密信息。Diffie-Hellman算法的安全性在于在有限域上计算离散对数非常困难。在此先简单介绍一下离散对数的概念。定义素数p的本原根(PrimitiveRoot)为一种能生成1～p－1所有数的一个数，即如果a为p的本原根，则amodp，a2modp，…，ap－1modp两两互不相同，构成1～p－1的全体数的一个排列(例如p＝11，a＝2)。对于任意数b及素数p的本原根a，可以找到一个惟一的指数i，满足：b＝aimodp，0≤i≤p−1称指数i为以a为底模p的b的离散对数。如果Alice和Bob想在不安全的信道上交换密钥，他们可以采用如下步骤：

(1) Alice和Bob协商一个大素数p及其本原根a，a和p可以公开。

(2) Alice秘密产生一个随机数x，计算X＝axmodp，然后把X发送给Bob。

(3) Bob秘密产生一个随机数y，计算Y＝aymodp，然后把Y发送给Alice。

(4) Alice计算k＝Yxmodp。

(5)Bob计算k′＝Xy

modp。

k和k′是恒等的，因为k＝Yxmodp＝(ay)xmodp＝(ax)ymodp＝Xymodp＝k′。线路上的搭线窃听者只能得到a、p、X和Y的值，除非能计算离散对数，恢复出x和y，否则就无法得到k，因此，k为Alice和Bob独立计算的秘密密钥。下面用一个例子来说明上述过程。Alice和Bob需进行密钥交换，则：

(1)二者协商后决定采用素数p＝353及其本原根a＝3。

(2) Alice选择随机数x＝97，计算X＝397mod353＝40，并发送给Bob。

(3) Bob选择随机数y＝233，计算Y＝3233mod353＝248，并发送给Alice。

(4) Alice计算k＝Yxmodp＝24897mod353＝160。

(5) Bob计算k′＝Xymodp＝40233mod353＝160。k和k′即为秘密密钥。2.5消息验证和数字签名

1.Hash函数公钥密码体制最重要的一个应用是数字签名，而数字签名常常需要和单向散列函数结合起来使用。散列函数(Hash函数)是把不固定长度输入串(M是变长的消息串)转换成固定长度输出串(散列值h)的一种函数，即h＝H(M)，其中h的长度是m。单向散列函数是在一个方向上工作的散列函数，其安全性主要在于它的单向性，必须具有如下性质：

(1)对于给定的M，很容易计算其散列值h。(2)对于给定的h，根据H(M)＝h得出M在计算上是不可行的。(3)对于给定的M，要找到另一消息M′，并满足H(M)＝H(M′)在计算上是不可行的。

(4)寻找任意的M，M′，使得H(M)＝H(M′)在计算上不可行的(抗碰撞条件)。

为了对不定长的输入产生定长的输出，并且最后的结果要与所有的字节相关，许多单向散列函数都采用了分块填充链接的方式，其结构是迭代渐进型的，这种散列函数将输入数据分成n块固定长度(每块长度为k)的分组。单向散列函数建立在压缩函数f的基础上。给定一长度为k的输入，单向函数输出长为m散列值，压缩函数的输入是消息分组和文本前一分组的输出(对第一个分组，其输入为消息分组和初始化向量)，输出是到该点的所有分组的散列。即分组Mi的散列值为：hi＝f(Mi,hi－1)

该散列值和下一轮的消息分组一起，作为压缩函数下一轮的输入。最后一分组的散列就成为整个消息的散列。有结论可以得出，如果压缩函数是无碰撞的，那么上述方法得到的Hash函数也是无碰撞的。因此，Hash函数的核心技术是设计无碰撞压缩函数。同样，密码分析对算法的攻击重点也是对f内部结构的分析，常常需要先找出f的碰撞。

MD表示消息摘要(MessageDigest)，MD4算法是由RonRivest提出的一个单向散列函数，MD5是MD4的改进版，该算法对输入的任意长度消息产生128位散列值，MD5曾经是使用最普遍的安全散列算法，但从密码分析角度来看，MD5被认为已经不再安全了。因此现在比较流行的算法是散列值长度160位SHA-1和RIPEMD-160。

2．消息验证与密钥相关的单向散列函数通常称为MAC，即消息验证码。MAC具有与前面讨论的单向散列函数相同的特性，但MAC还包括一个秘密密钥，即MAC＝fk(M)，散列值是输入值和密钥的函数。其中M是输入串，k为通信双方的密钥，f为单向散列函数。

MAC可为拥有共享密钥的双方在通信中验证消息的完整性，也可以被单个用户用来确定他的文件是否已经被改动，或是否被感染了病毒。

3．数字签名数字签名就是附加在数据单元上的一些数据，或是对数据单元所作的密码变换。这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性，并保护数据，防止被人进行伪造。它是对电子形式的消息进行签名的一种方法，一个签名消息能在通信网络中传输。基本要求如下：

(1)签名是可信的。

(2)签名不可伪造。

(3)签名不可重用，签名是文件的一部分，不能移到别的文件上去。

(4)签名的文件是不可改变的，在文件上签名以后就不能改变。

(5)签名是不可抵赖的。

目前使用比较多的数字签名有两类：一类是使用对称密码系统和需要仲裁者的签名方法；还有一类是基于公开密钥体制的数字签名，一般目前使用最多的是基于公开密钥体制的数字签名。一般数字签名方案由两部分组成：签名算法和验证算法。在实际应用中，由于公开密钥算法的执行效率比较低，因此为了节约时间，数字签名协议经常和单向散列函数一起使用，发送方并不对整个文件签名，而只是对文件的散列值签名。签名的过程如下：

(1)发送者产生文件的单向散列值。

(2)发送者用其私人密钥对散列加密，以实现对发送文件的签名。

(3)发送者将文件和散列签名发送给接收者。

(4)接收者根据发送者发送的文件产生文件的单向散列值，然后用数字签名算法对散列值运算，同时用发送者的公开密钥对签名的散列解密。如果签名的散列值与其产生的散列值匹配，则签名是有效的。

前面提到的公开密钥算法RSA也可以用于数字签名。令n＝p1p2，p1和p2是大素数，令消息为M，选e并计算出d使ed≡1mod((n)，公开n和e，将p1、p2和d保密。

K＝(n,p,q,e,d)。对消息M的签字为：S＝Sigk(M)＝[H(M)]dmodn，签名过程如图2-12所示。

图2-12RSA算法实现的数字签名过程

验证签名过程如图2-13所示，对给定的M和S，可按下式验证：H(M)≡Semodn

图2-13验证RSA数字签名过程