3.3 公钥加密（非对称密码）

公钥加密最初是由Diffie和Hellman在1976年提出的，是几千年来文字加密的第一次真正革命性的进步。非对称加密（公开密钥加密）是指在加密过程中，密钥被分解为一对。这对密钥中的任何一把都可作为公开密钥通过非保密方式向他人公开，而另一把作为私有密钥进行保存。公开密钥用于对信息进行加密，私有密钥则用于对加密信息进行解密。

首先需要说明的是，认为公钥加密比常规加密更具安全性是不正确的。实际上，任何加密方案的安全性都依赖于密钥的长度和解密所需的计算工作量。从防止密码分析的角度来看，常规加密和公钥加密并没有任何一点能使一个比另一个优越。

大体说来，公钥加密系统的使用有3个方面：加密/解密——发送方可以用接收方的公钥加密信息；数字签名——发送方用其私钥“签署”信息（通过对消息或作为消息函数的小块数据应用加密算法来进行签署），通过数字签名可以实现对原始报文的鉴别和不可抵赖；密钥交换——双方互相合作时可以进行会话密钥的交换。目前，公钥加密主要用在消息验证和密钥分发方面。

公钥加密算法有多种，目前最常用的有RSA和DH（Diffie-Hellman）。

3.3.1 RSA公钥加密

RSA体制是1978年由Rivest、Shamir和Adleman提出的第一个公钥密钥体制（PKC），也是迄今理论上最为成熟完善的一种公钥体制。它的安全性是基于大整数的分解。

RSA体制加密首先选择一对不同的素数p和q，计算n=p*q，f=（p-1）*（q-1），并找到一个与f互素的数d，计算其逆a，即d*a=1（模f），则密钥空间K=（n，p，q，a，d）。若用M表示明文，C表示密文，则加密过程：C=M^amodn；解密过程：M=C^dmodn。n和a是公开的，而p，q，d是保密的。

现在用一个简单的例子来说明RSA公开密钥系统的工作原理。首先选择两个素数p=7，q=17；然后计算n=p*q=7*17=119；再计算f=（p-1）*（q-1）=6*16=96；选择d，d是96的相对素数，但比96小，本例中d=5；最后确定a，使d*a=1（模96），而且a<96。找到a=77，因为77*5=385=4*96+1。

由上可得密钥公钥KU=（77，119），私钥KR=（5，119）。若对明文65（a的ASCII码）使用这些密钥，由于加密要求，求明文65的77次幂，得到3.929420092337977833652367108777e+139，除以119的余数为39，所以密文为39。解密时，39⁵mod119=90224199mod119=65。

上面的例子只是示意性的，真正应用时，两个素数通常均大于10¹⁰⁰。虽然知道公钥可以得到获得私钥的途径，但是需要将模数因式分解成组成它的素数，对于足够长的密钥，这是很困难的，可以说基本上不可能实现。RSA实验室目前建议：对于普通公司，使用密钥的大小为1024位；对于极其重要的资料，使用双倍大小，即2048位；对于日常应用，768位的密钥长度已足够，因为当前技术还无法破解它。用运算速度为100万次/秒的计算机分解500位的n，计算机操作次数为1.3×10³⁹，需要的运算时间为41222729578893962455606291.2227296年，约4.2×10²⁵年。1994年RSA129（129个数字公钥，即428位的公钥）被分解，花费了5000年机时，是利用Internet上一些计算机的空闲CPU周期花了8个月完成的。1995年，Blacknet密钥（384位）被分解，用了几十台工作站和一台MarPar，共用400年机时，仅历时3个月。随着时间的推移，可能被分解的密钥长度还会增加。但是不是值得某些人和组织去花费巨大的人力、物力破译某一个密码就有待商榷了。

破坏RSA的方法一种是蛮力攻击——尝试所有可能的密钥，另一种就是分解它的两个素数的乘积，但不管哪种方法，对于现在所用位数的密码的破译还是无法实现。所以至少几年内RSA的安全是可靠的，RSA从1977年保持到现在还没有被攻破就说明它不像有些人说的那样脆弱。

因为RSA密钥的生成、加密/解密的计算比较复杂，所以密钥越大系统运行速度也就越慢，所以在网络应用中同DES算法结合使用，对数据量大的明文采用DES算法来加密与解密，而对签名信息和DES算法的密钥这种数据量小的信息采用RAS算法。

3.3.2 DH（Diffie-Hellman）公钥加密

DH公钥算法是由Diffie与Hellman在1976年提出的，也叫Diffie-Hellman密钥交换，在许多商业产品中都采用这种加密体制作为密钥交换体制。

Diffie-Hellman算法如下：设p为一个大素数，且p-1有大素数因子，选a为p的一个原根（即a的幂可以生成从1到p-1的所有整数，也即amodp，a²modp，…，a^p-1modp各不相同，可以以某种方式重新排列从1到p-1的所有整数）。找到大素数p和原根a，在应用时，用户A若与B进行通信，首先A选择随机私钥X_A（X_A<p）并计算出Y_A（Y_A=a^XAmod p），同样用户B选择随机私钥X_B（X_B<p）并计算出Y_B（Y_B=a^XBmodp），双方都把X作为私钥，把Y发送给对方。那么，用户A计算出密钥K=Y_B^XAmodp，用户B计算出密钥K=Y_A^XBmodp，读者可通过上面的条件推一下，这两个结果是相同的，这样双方就交换了密钥，而且能保证X值都是私有的。而要通过已知的p，a，Y_A，Y_B，计算出X，对于较大的素数，几乎是不可能的。

下面通过摘自[WELS88]的一个示例来说明DH的加密过程。选择p=71，a=7，用户A选择私钥X_A=5，X_B=12，则YA=7⁵mod71=51，Y_B=7¹²mod71=4，在双方发送Y后，双方都可计算出通用密钥K=Y_B^XAmod71=Y_A^XBmod71=30。而攻击者从公钥{51，4}中很计算出通用密钥30。

但这一密钥交换容易受到伪装攻击。如果A和B正在寻求交换公钥，第三人C可能每次都介入交换。A认为公钥Y_A正发送给B，但事实上被C截获，C向B发送一个别人的公钥，B认为公钥Y_B正发送A，但被C截获，B得到的也不再是A的公钥，这样C截获从A来的信息，有A/C密钥解密并修改，再使用B/C密钥转发给B，但A和B并不知发生的一切。

为了防止这种情况，1992年，Diffie和其他人共同开发了经认证的Diffie-Hellman密钥协议。在这个协议中，必须使用现有的私钥/公钥对与公钥元素相关的数字证书，由数字证书验证交换的初始公共值。