3.3 公钥密码体制_电子商务安全（第2版）-QQ阅读男生都市网

上QQ阅读APP看书，第一时间看更新

3.3 公钥密码体制

3.3.1 公钥密码体制概述

1976年，Diffie和Hellman在“密码学的新方向”（New Directions in Cryptography）一文中提出了公钥密码的思想，开创了公钥密码学的新纪元。公钥密码提出后，立刻受到了人们的普遍关注。从1976年以来，各国学者已经提出了大量公钥密码体制的实现算法。这些算法的安全性都是基于复杂的数学难题的。对于某种数学难题，如果利用通用的算法计算出密钥的时间越长，那么基于这一数学难题的公钥密码体制就被认为越安全。根据所基于的数学难题来分类，公钥密码体制可以分为以下三类。

1）基于大整数分解问题（IFP）的公钥密码体制，如RSA体制和Rabin体制。

2）基于有限域上离散对数问题（DLP）的公钥密码体制，其中主要包括ElGamal类加密体制和签名方案，Diffie-Hellman密钥交换方案，Schnorr签名方案和Nyberg-Ruppel签名方案等。

3）基于椭圆曲线离散对数问题（ECDLP）的公钥密码体制，其中主要包括椭圆曲线型的Diffie-Hellman密钥交换方案，椭圆曲线型的MQV密钥交换方案和椭圆曲线型的数字签名算法。

利用公钥密码体制，通信双方无须事先交换密钥就可以进行保密通信。公钥密码体制可以提供以下功能：

1）机密性（Confidentiality）：通过数据加密来保证非授权人员不能获取机密信息。

2）认证（Authentication）：通过数字签名来验证对方的真实身份。

3）数据完整性（Data Integrity）：通过数字签名来保证信息内容不被篡改或替换。

4）不可抵赖性（Nonrepudiation）：通过数字签名来实现，使发送者不能事后否认他发送过消息，消息的接收者可以向第三方证实发送者确实发出了消息。

公钥密码体制采用的加密密钥（公钥）和解密密钥（私钥）是不同的。由于加密密钥是公开的，密钥的分配和管理就很简单，而且能够很容易地实现数字签名，因此能够满足电子商务应用的需要。在实际应用中，公钥密码体制并没有完全取代对称密码体制，这是因为公钥密码体制是基于某种数学难题的，计算非常复杂，它的运行速度远比不上对称密码体制。因此，在实际应用中可以利用二者各自的优点，采用对称密码体制加密文件，采用公钥密码体制加密“加密文件”的密钥，这就是混合加密体制。混合加密体制较好地解决了运算速度和密钥分配管理的问题。

3.3.2 RSA算法

1977年，Ron Rivest、Adi Shamir和Leonard Adleman提出了公钥密码算法—RSA。它既能用于加密，又能用于数字签名，易于理解和实现，是第一个较为完善的公钥密码体制。RSA的安全性基于大数分解的困难性。

1.RSA密码体制描述

选取两个不同的大素数p和q，为了获得最大程度的安全性，p和q的长度一样。计算它们的乘积

n=pq

令φ（n）=（p-1）（q-1）。

随机选取一个整数e，1≤e≤φ（n），（φ（n）,e）=1。因为（φ（n）,e）=1，所以在模φ（n）下，e有逆元d=e^-1modφ（n）。

e和n为公钥，d是私钥。两个素数p和q不再需要，可以销毁，但绝不能泄露。

（1）加密

加密消息m时，首先将它分成比n小的数据分组。对于其中任一个分组x，加密公式为

y=x^emod n

（2）解密

解密消息时，对于任一个密文块y，计算

x=y^dmod n

因为

y^dmod n=（x^e）^dmod n=x^edmod n=x^kφ^（ⁿ^）⁺¹mod n=x，

所以该公式能恢复为明文x。

加密和解密运算都是模n指数运算。因为n很大，所以必须使用一些有效算法来完成Z_n中的计算，而且所需要的计算时间将依赖于n的二元表示的位数，即n的长度。假定n的长度为k，则k=「|log₂n|+1。使用标准的算术技术不难看出，两个k比特的整数的加法能在时间O（k）内完成，乘法能在O（k²）内完成。一个长度至多为2k的整数的模n运算能在时间O（k²）内完成。假定x,y∈Z_n，那么xymodn可以按照下述方法计算：先计算积xy（xy是一个长度为2k的整数），然后对xy进行模n归约。这两步可以在时间O（k²）内完成，该计算称为模乘法。x^cmodn的计算可以使用c-1次模乘法完成。然而，如果c很大的话，这种做法就不是很有效的。“反复平方—乘”算法是计算模指数的一种有效算法。这种算法计算x^cmodn至多需要2l次模乘法，这里的l是c的长度。因为l≤k，所以x^cmodn能在时间O（k³）内完成。

2.RSA密码体制的安全性分析

密码分析者对RSA密码体制的一个明显的攻击是分解n。如果能做到这一点，那么很容易就能计算出φ（n），然后通过计算d=e^-1modφ（n）来获得私钥d。因此，如果RSA密码体制是安全的，那么必须保证n=pq是足够大的，使得分解它在计算上不可行的。目前的分解算法能分解的整数已经达到130位的十进制数。因此，基于安全性考虑，用户选择的素数p和q应当大约都为100位的十进制数，那么n=pq将是200位的十进制数。RSA的一些硬件实现使用一个512bit长的模，然而一个512bit长的模相当于大约154位的十进制数，所以从长远的角度来看，512bit模并不能提供足够高的安全性。

已知n时计算φ（n）与分解n的问题是等价的，而且当p和q未知时没有有效算法可以计算出群中元素的e次方根。因此人们猜测破译RSA密码体制多项式等价于分解n，但是这一点仍未被证明。因此，RSA密码体制的安全性是建立在整数分解问题之上的。整数分解方面的算法研究已经取得了很大的进展，两种可行的算法是椭圆曲线算法和多项式平方筛选算法。以目前的知识和技术，如果p和q是100位的十进制数，分解n即为不可能的。

如果密码分析者能够计算φ（n），那么他一定能分解n，从而破译该体制。这是由于可以通过下列方程组获得因子p和q

n=pq

φ（n）=（p-1）（q-1）

这个方程组可以转化为方程：p²-[n-φ（n）+1]p+n=0。

这个方程的两个根便是p和q，即n的因子。因此，密码分析者如果能够获得φ（n）的值，那么他就能分解n，从而破译该系统。也就是说，计算φ（n）并不比分解n容易。事实上，如果知道φ（n）并不需要去分解n，只要用Euclid算法就可以由加密密钥e计算出解密密钥

d=e ^-1modφ（n）

求解私钥d和分解大整数n是等价的。也就是说，给定私钥d，可以分解n；反过来，给定n的分解形式，也可以恢复私钥d。

RSA密码体制受到了严重威胁。1999年8月27日，阿姆斯特丹国立数学和计算机科学研究所的研究人员用一台克雷900-16超级计算机、300台个人计算机以及专门设计的软件用6个星期就破译了RSA-155密码。

3.3.3 Diffie-Hellman算法

Diffie和Hellman在一篇具有独创性的论文中首次提出了公钥算法，给出了公钥密码学的定义，该算法也被称为Diffie-Hellman密钥交换。很多商业产品都使用了这种密钥交换技术。该算法的目的是使两个用户能安全地交换密钥，随后使用该密钥对消息进行加密。

Diffie-Hellman算法的有效性是建立在计算离散对数是很困难的这一基础之上，简单地说，可如下定义离散对数。首先定义素数p的本原根。素数p的本原根是一个整数，且其幂可以产生1到p-1之间的所有整数。也就是说，若a是素数p的本原根，则

amod p, a² mod p, …, a^p^-1 mod p

各不相同，它是整数1到p-1的一个置换。

对任意整数b和素数p的本原根a，可以找到唯一的指数，使得

b≡aⁱ（mod p），0≤i≤（p-1）

指数i称为b的以a为底的模p离散对数，记为dlog_a_,_p（b）。

1.Diffie-Hellman密码体制描述

在这种方法中，素数q及其本原根α是两个公开的整数。假定用户A和B希望交换密钥，那么用户A选择一个随机整数X_A＜q，并计算。类似地，用户B也独立地选择一个随机整数X_B＜q，并计算。A和B保持其X是私有的，但对另一方而言，Y是公开可访问的。用户A计算并将其作为密钥，用户B计算并将其作为密钥。这两种计算所得的结果是相同的

至此A和B完成了密钥的交换。此外，由于X_A和X_B是私有的，所以攻击者只能通过q、α、Y_A和Y_B来进行攻击。这样，他就必须求离散对数才能确定密钥。例如，要对用户B的密钥进行攻击，攻击者就必须先计算

X_B=d log_α_,_q（Y_B）

然后，他就可以像用户B那样计算出密钥K。

Diffie-Hellman密钥交换的安全性建立在求关于素数的模幂运算相对容易，而计算离散对数却非常困难的基础之上，对于大素数，求离散对数被认为是不可行的。

图3.14给出的简单协议使用了Diffie-Hellman计算方法。假定A希望与B建立连接，并使用密钥对该次连接中的消息进行加密。用户A生成一次性密钥X_A，计算Y_A，并发送Y_A给B；用户B也生成私钥X_B，计算Y_B，并发送Y_B给A，这样A和B都可以计算出密钥。当然前提是，A和B事先应已知公开的q和α，如可由用户A选择q和α，并随着第一条消息发送给B。

图3.14 Diffie-Hellman密钥交换

下面是使用Diffie-Hellman算法的另外一个例子。假定有一组用户（如LAN中的用户），且每个用户都生成一个在较长时间内有效的密钥X_i（用户i），并计算公开的Y_i。这些公开值与公开的全局变量q和α一起保存于某中心目录中，在任何时刻用户j都可以访问用户i的公开值，计算出密钥并将消息加密后发送给用户i。若该中心目录是可信的，则这种形式的通信既可以保证保密性，又可以保证某种程度的真实性。因为只有i和j可以确定密钥，所有其他用户均不能读取加密后的消息，但是这种方法无法抵御重放攻击。

2.Diffie-Hellman密码体制的安全性分析

Diffie-Hellman算法不能抵抗中间人攻击。假定Alice和Bob希望交换密钥，而Darth是攻击者，攻击过程如下。

1）为了进行攻击，Darth先生成两个随机的私钥和，然后计算相应的公钥和。

2）Alice将Y_A传递给Bob。

3）Darth截获了Y_A，将传递给Bob。Darth计算。

4）Bob收到，计算。

5）Bob将Y_B传递给Alice。

6）Darth截获了Y_B，将传递给Alice。Darth计算。

7）Alice收到，计算。

此时，Bob和Alice想，他们已经共享了密钥，但实际上，Bob和Darth共享密钥K₁，而Alice和Darth共享密钥K₂。接下来，Alice和Bob之间的通信以下列方式泄密。

1）Alice发了一份加了密的消息M：E（K₂, M）。

2）Darth截获了该加密消息，解密并恢复出M。

3）Darth将E（K₁, M）或E（K₁, M′）发送给Bob，其中M′是任意的消息。第一种情况，Darth只是简单地窃听通信，而不是改变它。第二种情况，Darth想修改给Bob的消息。

Diffie-Hellman算法不能抵抗上述的攻击，因为该算法没有对通信的参与方进行认证。

3.3.4 ECC算法

ECC是基于椭圆曲线离散对数问题的各种公钥密码体制。最早是在1985年分别由V.S.Miller和Neal Koblitz独立提出的。自1985年以来，ECC受到了全世界密码学家、数学家和计算机科学家的密切关注。一方面，由于没有发现ECC明显的安全漏洞；另一方面，在提高ECC的实现效率上取得了长足的进步。现在，ECC已成为效率最高的公钥密码体制。

相对于RSA和DSA等系统，ECC吸引人的最主要原因是目前解决椭圆曲线离散对数问题（ECDLP）的已知最好的算法也是完全指数时间的。与之相比，RSA和DSA等其他公钥密码系统所基于的数学问题，如因数分解问题（IFP）和离散对数问题（DLP）都属于亚指数时间算法。与RSA和DSA等体制相比，ECC具有如下优势。

（1）安全性更高

加密算法的安全性能通过算法的抗攻击强度来反映。表3.8描述了ECC和其他几种公钥密码算法抗攻击强度的比较。可以看到，与其他公钥算法相比，ECC的抗攻击性具有绝对的优势。如160bit的ECC可提供与1024bit的RSA/DSA相当的安全强度，而210bit的ECC则与2048bit的RSA/DSA具有相同的安全强度。

表3.8 ECC与RSA/DSA抗攻击性能比较

注：其中MIPS年表示每秒钟运行一百万次指令的计算机运行一年的工作量。

（2）计算量小，处理速度快

虽然在RSA中可以通过选取较小的公钥（如选取3为公钥）的方法提高公钥处理的速度，即提高加密和签名验证的速度，使其在加密和签名验证上与ECC有可比性，但在私钥的处理速度上（解密和签名），ECC比RSA/DSA要快。而且随着安全强度的提高，ECC比RSA/DSA运算的速度提高得更快。

（3）需要的存储空间少

ECC的密钥尺寸和系统参数与RSA/DSA相比要小得多，意味着它所占的存储空间也要少得多。这对于在IC卡和无线环境中的应用具有特别重要的意义。

（4）带宽要求低

当对长消息进行加解密时，三类密码体制有相同的带宽要求，但应用于短消息时，ECC对带宽的要求则要低得多。带宽要求低使ECC在无线网络中具有广阔的应用前景。

由上面的几点可以看到，随着计算能力的提高和密钥长度的增加，ECC相对其他公钥密码系统具备一定的优势。其每比特更高的安全性所带来的优点包括：更高的速度，更低的能量消耗，节约带宽，提高存储效率。这些优点在一些对于带宽、处理器能力或存储有限制的应用中显得尤为重要。