计算机网络非对称密码体制解析

1976年，Diffie与Hellman在IEEE期刊上提出了划时代的公开密钥密码系统的概念，这个观念为密码学的研究开辟了一个新的方向，有效地解决了秘密密钥密码系统通信双方密钥共享困难的缺点，并引进了创新的数字签名的观念。非对称密码系统（Asymmetric Encryp⁃tion）可为加解密或数字签名系统。由于加密或签名验证密钥是公开的，故称为公钥（Pub⁃lic Key），而解密或签名产生密钥是秘密的，故称为私钥（Private Key）。因为公钥与私钥不同，且公钥与私钥必须存在成对（Key Pair）与唯一对应的数学关系，使得由公钥去推导私钥在计算上不可行，因此非对称密码系统又称为公开密钥系统或双钥系统，其模型如图7-14所示。公钥密码体制的公钥密码算法是基于数学问题求解的困难性而提出的算法，它不再是基于替代和置换的方法。

图7-14　非对称密码模型

公钥密码体制的产生主要基于以下两个原因：一是为了解决常规密钥密码体制的密钥管理与分配的问题；二是为了满足对数字签名的需求。因此，公钥密码体制在消息的保密性、密钥分配和认证领域有着重要的意义。

在公钥密码体制中，公钥是可以公开的信息，而私钥是需要保密的信息。加密算法E和解密算法D也都是公开的。用公钥对明文加密后，只能用与之对应的私钥解密才可以恢复出明文，反之亦然。

公钥密码体制的优、缺点：

优点：网络中的每一个用户只需要保存自己的私钥，N个用户仅需产生N对密钥。密钥少，便于管理；密钥分配简单，不需要秘密的通道和复杂的协议来传送密钥。公钥可基于公开的渠道（如密钥分发中心）分发给其他用户，而私钥则由用户自己保管；可以实现数字签名。

缺点：与对称密码体制相比，公钥密码体制的加密、解密处理速度较慢，在同等安全强度下，公钥密码体制的密钥位数要求更多一些。

公钥密码体制比较流行的主要有两类：一类是基于因子分解难题的，其中最典型的是RSA密码算法；另一类是基于离散对数难题的，如EIGamal公钥密码体制和椭圆曲线公钥密码体制。

1.RSA密码算法

RSA密码算法是美国麻省理工学院的Rivest、Shamir和Adleman三位学者于1978年提出的。RSA密码算法方案是唯一被广泛接受并实现的通用公开密码算法，目前已经成为公钥密码的国际标准。它是第一个既能用于数据加密，也能通用数字签名的公开密钥密码算法。在互联网中，电子邮件收、发的加密和数字签名软件PGP就采用了RSA密码算法。

1）算法描述

RSA密码算法描述如下：

（1）密钥对的产生。

①选取两个大素数p和q。

②计算n＝p·q及n的欧拉函数值Φ（n）＝（p-1）（q-1）。

③然后随机选取整数e（1＜e＜Φ（n）），且满足GCD（e，Φ（n））＝1（GCD表示求最大公约数运算），即Φ（n）和e互素。

④由扩展的欧几里得算法求出d，使e×d＝1modΦ（n）。

⑤形成密钥对，其中公钥为｛e，n｝，私钥为｛d，n｝。p，q是秘密参数，需要保密，如不需要保存，可销毁。

（2）加密过程。加密时要使用接收方的公钥，设接收方的公钥为e，明文m满足0≤m＜n（否则需要进行分组），计算c＝me（mod n），c为密文。

（3）解密过程：计算m＝cd（mod n）。

【例7-10】选取p＝11，q＝13，则

然后，选择e＝17，满足GCD（e，Φ（n））＝GCD（17，120）＝1，计算d＝e-1（mod 120）。因为1＝120-7×17，所以d＝-7＝113（mod 120），则公钥为（e，n）＝（17，143），私钥为d＝113。

假设对明文信息m＝24进行加密，则密文为

(www.xing528.com)

密文c经公开信道发送到接收方后，接收方用私钥d对密文进行解密：

从而正确地恢复出文。

2）安全性分析

（1）RSA的安全性依赖于著名的大整数因子分解的困难性问题。若要求n很大，则攻击者将其成功地分解为p·q是困难的；反之，若n＝p×q，则RSA便被功破。因为一旦求得n的两个素因子p和q，那么立即可得n的欧拉函数值Φ（n）＝（p-1）（q-1），再利用欧几里得扩展算法求出RSA的私钥d＝e-1（modΦ（n））。

虽然大整数的因子分解是十分困难的，但是随着科学技术的发展，人们对大整数因子分解的能力在不断提高，而且分解所需的成本在不断下降。1994年，一个通过Internet上1 600余台计算机进行合作的小组仅仅工作了8个月就成功分解了129位的十进制数，1996年4月，他们又破译了RSA-130，1999年2月又成功地分解了140 bit的十进制数。1999年8月，阿姆斯特丹的国家数学与计算机科学研究所一个国际密码研究小组通过一台Cray900-16超级计算机和300台个人计算机进行分布式处理，运用二次筛选法花费7个多月的时间成功地分解了155 bit的十进制数（相当于512 bit的二进制数）。这些工作结果使人们认识到，要安全地使用RSA，应当采用足够大的整数n，建议选择p和q大约是100 bit的十进制素数，此时模长n大约是200位十进制数（实际要求n的长度至少是512 bit），e和d选择100 bit左右，密钥｛e，n｝或｛d，n｝的长度大约是300 bit十进制数，相当于1 024 bit二进制数（因为lb 10308＝308×lb 10≈1024）。不同应用可视具体情况而定，如安全电子交易（Secure Electronic Transaction，SET）协议中要求认证中心采用2 048 bit的密钥，其他实体则采用1 024 bit的密钥。

（2）RSA的加密函数是一个单向函数，在已知明文m和公钥｛e，n｝的情况下，计算密文是很容易的；但反过来，在已知密文和公钥的情况下，恢复明文是不可行的。从（1）的分析中得知，在n很大的情况下，不可能从｛e，n｝中求得d，也不可能在已知c和｛e，n｝的情况下求得d或m。

2.Diffie-Hellman密钥交换算法

Diffie和Hellman在1976年发表的论文中提出了公钥密码思想，但没有给出具体的方案，原因在于没有找到单向函数，但在该文中给出了通信双方通过信息交换协商密钥的算法，即Diffie-Hellman密钥交换算法，这是第一个密钥协商算法，用于密钥分配，不能用于加密或解密信息。

1）算法描述

Diffie-Hellman的安全性是基于Zp上的离散对数问题。设p是一个满足要求的大素数，并且g（0＜g＜p）是循环群Zp的生成元，g和p公开，所有用户都可以得到g和p。当两个用户A与B通信时，它们可以通过如下步骤协商通信所使用的密钥。

（1）用户A选取一个大的随机数α（2≤α≤p-2），计算SA＝gα（mod p），并且把SA发送给用户B。

（2）用户B选取一个大随机数β（2≤β≤p-2），计算SB＝gβ（mod p），并且把SB发送给用户A。

（3）用户A收到SB后，计算kAB＝。用户B收到SA后，计算kBA＝。

由于有：kAB＝令k＝kAB＝kBA，这样用户A和B就拥有了一个共享密钥k，就能以k作为会话密钥进行保密通信了。

2）安全性分析

当模p较小时，很容易求出离散对数。依目前的计算能力，当模p达到至少150 bit十进制数时，求离散对数成为一个数学难题。因此，Diffie-Hellman密钥交换算法要求模p至少达到150 bit十进制数，其安全性才能得到保证，但是，该算法容易遭受中间人攻击。造成中间人攻击的原因在于通信双方交换信息时不认证对方，攻击者很容易冒充其中一方获得成功。因此，可以利用数字签名打败中间人的攻击。

3.EIGamal加密算法

EIGamal公钥密码体制是由EIGamal在1985年提出的，是一种基于离散对数问题的公钥密码体制。该密码体制既可用于加密，又可用于数字签名，是除了RSA密码算法之外最有代表性的公钥密码体制之一。由于EIGamal公钥密码体制有较好的安全性，因此得到了广泛的应用。著名的美国数字签名标准DSS就是采用了EIGamal签名方案的一种变形。其算法描述如下：

（1）密钥生成：首先随机选择一个大素数p，且要求p-1有大素数因子（Zp是一个有p个元素的有限域，Z*p是由Zp中的非零元构成的乘法群）是一个生成元。然后再选一个随机数x（1≤x≤p-1），计算y＝gx（mod p），则公钥为（y，g，p），私钥为x。

（2）加密过程：不妨设信息接收方的公私钥对为｛x，y｝，对于待加密的消息m∈Zp，发送方选择一个随机数然后计算c1＝gk（mod p），c2＝myk（mod p），则密文为（c1，c2）。

（3）解密过程：接收方收到密文（c1，c2）后，由私钥x计算因为

所以消息m被恢复。

实际上，EIGamal最大的特点在于它的“非确定性”。由于密文依赖于执行加密过程的发送方所选取的随机数k，所以加密相同的明文可能会产生不同的密文。EIGamal还具有消息扩展因子，即对于每个明文，其密文由两个Zp上的元素组成。EIGamal通过乘以yk来掩盖明文m，同样gk也作为密文的一部分进行传送。因为正确的接收方知道解密密钥x，其可以从gk中计算得到（gk）x＝（gx）k＝yk，从而能够从c2中“去除掩盖”而得到明文m。