网络安全与保密（第二版）课件：公钥密码系统

公钥密码系统4.1数论基础4.2RSA密码系统4.3Diffie-Hellman密钥交换4.4数字签名参考文献思考题

公钥密码体制于1976年由W.Diffie和M.Hellman提出[1]，同时，R.Merkle也独立提出了这一体制。这种密码体制采用了一对密钥:加密密钥和解密密钥，且从解密密钥推出加密密钥是不可行的。这一对密钥中，一个可以公开(称之为公钥)，另一个为用户专用(私钥)。

公钥密码系统是基于陷门单向函数的概念。在第3章中，我们介绍了单向函数的概念。单向函数是易于计算但求逆困难的函数，而陷门单向函数是在不知道陷门信息的情况下求逆困难，但当知道了陷门信息时易于求逆的函数。

公钥密码系统可用于以下三个方面：

(1)通信保密。此时将公钥作为加密密钥，私钥作为解密密钥，则通信双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文分析出明文或私钥在计算上是不可行的。如图4-1所示，Bob拥有多个人的公钥。当他需要向Alice发送机密消息时，他用Alice公布的公钥对明文消息加密。当Alice接收到后用她的私钥解密。由于私钥只有Alice本人知道，所以能实现通信保密。图4-1通信保密

(2)数字签名。将私钥作为加密密钥，公钥作为解密密钥，则可实现由一个用户对数据加密而使多个用户解读—数字签名。如图4-2所示，Bob用私钥对明文进行加密并发布，Alice收到密文后用Bob公布的公钥解密。由于Bob的私钥只有Bob本人知道，因此，Alice看到的明文肯定是Bob发出的，从而实现数字签名。

(3)密钥交换。通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。

本章将讨论RSA密码系统和Diffie-Hellman密钥交换，最后介绍数字签名。图4-2数字签名

4.1数论基础

4.1.1素数素数是一种整数，除了1和此整数自身外，没法被其它自然数整除的数。换句话说，只有两个正因数(1和自己)的自然数即为素数。任何大于1的正整数N可以唯一表示成有限个素数的乘积：，其中pi都是素数，其诸方幂ai是正整数，例如100 = 22·52。这就是算术基本定理。

最小的素数是2，它也是唯一的偶素数。最前面的素数依次排列为：2，3，5，7，11，13，17，……。不是素数且大于1的正整数称为合数。

根据素数的定义，在判断一个数N是否是素数时，我们只要用1～N-1去除N，看看能否整除即可。但我们有更好的办法。先找一个数m，使m的平方大于N，再用<=m的素数去除N，如果都不能整除，则N必然是素数。如我们要判断1993是不是素数，50*50 > 1993，那么我们只要用1993去除 <50的素数就可以了。

4.1.2费马小定理

费马小定理(Fermat’sLittleTheorem)是数论中的一个定理，其内容为假如p是素数，a是一个正整数且不能被p整除，那么

证明：构造素数p的完全剩余系P = {1，2，3，4，…，(p-1)}，因为gcd(a，p) = 1，由此可得A={a，2a，3a，4a，…，(p-1)a}中各个元素不等于0，且互不相等。因此，A也是p的一个完全剩余系，只不过是排列顺序不同而已。对两个集合的所有元素分别进行相乘，并对p取模，有

令W=1*2*3*4*…*(p-1)，则。由于gcd(W，p) = 1，可知

例如，对于a = 3，p = 5，有ap-1 = 34 = 81mod5 = 1。

4.1.3欧拉定理

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’stotientfunction、φ函数、欧拉商数等。例如φ(8)=4，因为1，3，5，7均和8互质。

对素数p，显然有φ(p) = p-1。

对于两个互不相等的素数p和q，如果n = p·q，则有φ(n)=(p-1)·(q-1)=φ(p)·φ(q)。例如，φ(10)=φ(2)·φ(5) = 1·4 = 4。这四个数分别是1，3，7，9。

在数论中，欧拉定理(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明，若n，a为正整数，且n，a互素，gcd(a，n)=1，则

证明：对于集合Zn = {x1，x2，…，xφ(n)}，其中xi(i = 1，2，…，φ(n))是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系。考虑集合S = {a*x1(modn)，a*x2(modn)，…，a*xφ(n)(modn)}，则S = Zn。

(1)由于a，n互质，xi也与n互质，则a*xi也一定与n互质，因此，对于任意的xi，a*xi(modn)必然是Zn的一个元素。

(2)对于Zn中两个元素xi和xj，如果xi≠xj，则a*xi(modn)≠a*xj(modn)，这个由a、n互质和消去律可以得出。

所以，很明显，S = Zn。

既然这样，那么

考虑上面等式左边和右边：

而和n互质，根据消去律，可以从等式两边约去，就得到

4.2RSA密码系统

公开密钥加密的第一个算法是由RalphMerkle和MartinHellman开发的背包算法[2]，它只能用于加密，后来AdiShamir将其改进使之能用于数字签名。背包算法的安全性不好，也不完善。随后不久就出现了第一个较完善的公开密钥算法RSA[3](根据其发明者命名，即R.L.Rivest,A.Shamir和L.Adleman)。

RSA密码系统的安全性是基于大数分解的困难性。我们知道，求一对大素数的乘积很容易，但要对这个乘积进行因式分解非常困难。因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥。从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等。这在许多密码学教材中都有所论述，本书不作讨论。

下面介绍RSA密码系统的细节。选择两个不同的大素数p和q(一般都为100位左右的十进制数字)，计算乘积

n=p·q

和欧拉函数值

·

随机取一整数e，1＜e＜φ(n)，且e和φ(n)互素。此时可求得d以满足

则

这样可以把e和n作为公开密钥，d作为私人密钥。其中，p、q、φ(n)和d就是秘密的陷门(4项并不是相互独立的)，这些信息不可以泄露。

RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成合适大小的数据分组，然后对分组分别进行加密。每个分组的大小应该比n小。

设ci为明文分组mi加密后的密文，则加密公式为

ci = mie(modn)

解密时，对每一个密文分组进行如下运算

这种加/解密方案的可行性证明可以参考文献[3]。这里将举一个简单的例子来说明RSA的加/解密过程。选p = 5，q = 11，则

于是明文空间为在闭区间[1,54]内且不能被5和11整除的数(如果明文m同n不是互为素数，就有可能出现消息暴露情况，即me = mmodn，这样我们就可能通过计算n与加密以后的m的最大公约数来分解出n。通常一个明文同n有公约数的概率小于1/p + 1/q，因此，对于大的p和q来说，这种概率是非常小的。)。选择e =7，则d = 23。由加/解密公式可以得到加密表如表4-1所示。

可以看出RSA加密实质是一种Zn→Zn的单表代换。

4.3Diffie-Hellman密钥交换

4.3.1Diffie-Hellman算法Diffie-Hellman算法是第一个公开密钥算法，发明于1976年[1]。Diffie-Hellman算法能够用于密钥分配，但不能用于加密或解密信息。

Diffie-Hellman算法的安全性在于在有限域上计算离散对数非常困难。在此先简单介绍一下离散对数的概念。定义素数p的本原根(PrimitiveRoot)为一种能生成1～p-1所有数的一个数，即如果a为p的本原根，则

两两互不相同，构成1～p-1的全体数的一个排列。对于任意数b及素数p的本原根a，可以找到一个唯一的指数i，满足

称指数i为以a为底模p的b的离散对数。

如果Alice和Bob想在不安全的信道上交换密钥，则可以采用如下步骤(见图4-3)：

(1) Alice和Bob协商一个大素数p及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′ = Xymodp。

k和k′ 是恒等的，因为k =Yxmodp=(ay)xmodp=(ax)ymodp=Xymodp=k′。图4-3Diffie-Hellman密钥交换

线路上的搭线窃听者只能得到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′ 即为秘密密钥。

4.3.2中间人攻击

Diffie-Hellman密钥交换容易遭受中间人攻击：

(1) Alice发送公开值(a和p)给Bob，攻击者Carol截获这些值并把自己产生的公开值发送给Bob。

(2) Bob发送公开值给Alice，Carol截获它然后用自己公开值发送给Alice。

(3) Alice和Carol计算出二人之间的共享密钥k1。

(4) Bob和Carol计算出另外一对共享密钥k2。

这时，Alice用密钥k1给Bob发送消息；Carol截获消息后用k1解密就可读取消息；然后将获得的明文消息用k2加密(加密前可能会对消息作某些修改)后发送给Bob。对Bob发送给Alice的消息，Carol同样可以读取和修改。造成中间人攻击的原因是Diffie-Hellman密钥交换不认证对方。利用数字签名可以挫败中间人攻击。

4.3.3认证的Diffie-Hellman密钥交换

密钥交换双方通过数字签名和公钥证书相互认证可以挫败中间人攻击。在密钥交换之前，密钥交换的双方Alice和Bob各自拥有公钥/私钥对和公开密钥证书。下面是Alice和Bob产生共享秘密密钥的过程：

(1) Alice产生随机数x并发送给Bob。

(2) Bob产生随机数y并根据Diffie-Hellman协议计算出共享秘密密钥k。然后Bob对x、y签名并用k加密签名。最后把加密的签名和y一起发送给Alice。

(3) Alice计算出k，用k解密Bob发送给他的消息并验证Bob的签名。对x、y签名并用k加密签名后发送给Bob。

(4) Bob解密消息并验证Alice的签名。

4.3.4三方或多方Diffie-Hellman

Diffie-Hellman密钥交换协议很容易扩展到三方或多方的密钥交换。下例中，Alice、Bob和Carol一起产生秘密密钥，如图4-4所示。图4-4三方或多方的密钥交换

(1) Alice选取一个大随机整数x，计算X = axmodp，然后把X发送给Bob；

(2) Bob选取一个大随机整数y，计算Y =aymodp，然后把Y发送给Carol；

(3) Carol选取一个大随机整数z，计算Z =azmodp，然后把Z发送给Alice；

(4) Alice计算Z′ =Zxmodp并发送Z′ 给Bob；

(5) Bob计算X′ =Xymodp并发送X′ 给Carol；

(6) Carol计算Y′ =Yzmodp并发送Y′ 给Alice；

(7) Alice计算k =Y′xmodp；

(8) Bob计算k =Z′ymodp；

(9) Carol计算k =X′zmodp。

共享秘密密钥k等于axyzmodp。这个协议很容易扩展到更多方。

4.4数字签名

4.4.1基本概念在计算机通信中，当接收者接收到一个消息时，往往需要验证消息在传输过程中没有被篡改；有时接收者需要确认消息发送者的身份。所有这些都可以通过数字签名来实现。

数字签名可以用来证明消息确实是由发送者签发的，而且，当数字签名用于存储的数据或程序时，可以用来验证数据或程序的完整性。它和传统的手写签名类似，应满足以下条件：

(1)签名是可以被确认的，即收方可以确认或证实签名确实是由发方签名的；

(2)签名是不可伪造的，即收方和第三方都不能伪造签名；

(3)签名不可重用，即签名是消息(文件)的一部分，不能把签名移到其它消息(文件)上；

(4)签名是不可抵赖的，即发方不能否认他所签发的消息；

(5)第三方可以确认收发双方之间的消息传送但不能篡改消息。

使用对称密码系统可以对文件进行签名，但此时需要可信任的第三方仲裁。公开密钥算法也能用于数字签名。此时，发方用私钥对文件进行加密就可以获得安全的数字签名。在实际应用中，由于公开密钥算法的效率较低，发送方并不对整个文件签名，而只对文件的散列值签名。

一个数字签名方案一般由两部分组成：签名算法和验证算法。其中签名算法或签名密钥是秘密的，只有签名人知道，而验证算法是公开的。

4.4.2数字签名算法

1991年8月，美国NIST公布了用于数字签名标准DSS的数字签名算法DSA，1994年12月1日正式采用为美国联邦信息处理标准[5]。

DSA中用到了以下参数：

(1) p为L位长的素数，其中，L为512～1024之间且是64倍数的数。

(2) q是160位长的素数且为p-1的因子。

(3) g=h(p-1)/qmodp，其中，h是满足1＜h＜p-1且h(p-1)/qmodp大于1的整数。

(4) x是随机产生的大于0而小于q的整数。

(5) y=gxmodp。

(6) k是随机产生的大于0而小于q的整数。

前三个参数p、q、g是公开的；x为私钥，y为公钥；x和k用于数字签名，必须保密；对于每一次签名都应该产生一次k。

对消息m签名

r和s就是签名。验证签名时，计算

如果v = r，则签名有效。

有关DSA更详细的描述如DSA素数的产生等请参考[5]。

4.4.3RSA签名方案

前面提到RSA可以用于数字签名。根据4.1节中的描述，我们可以获得私钥d，公钥e和n。则对消息m签名为

其中，H(m)计算消息m的消息摘要，可由散列函数SHA-1或MD5得到；r即为对消息的签名。

验证签名时，验证

若上式成立，则签名有效。整个签名过程如图4-5所示。

图4-5RSA数字签名

4.4.4其他数字签名方案

许多公开密钥算法都可以用于数字签名中。更多的签名方案可以参考文献[4]、[6]及相关资料。

参考文献

[1]W.Diffie,M.Hellman.Newdirectionsincryptography.IEEETrans.Inform.Theory,1976,IT-22(6),644–654[2]ArtoSalomaa.Public-KeyCryptography.Springer-Verlag,1990[3]L.Adleman,R.Rivest,A.Shamir.Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems.CommunicationsoftheACM,1978,27:120-126

[4]BruceSchneier.AppliedCryptography:Protocols,Algorithms,andSourceCodeinC.2ndedition,JohnWiley&Sons,1996

[5]NationalInstituteofStandardsandTechnology,FIPSPUB186.DigitalSignatureStandard(DSS).U.S.DepartmentofCommerce,May1994

[6]王育民，刘建伟.通信网的安全—理论与技术.西安：西安电子科技大学出版社，1999

思考题

[1]已知RSA密码体制的公开密钥为n = 55，e = 7，试加