本节简要介绍表2-1中列出的公钥密码算法，重点介绍RSA算法。

1. RSA

RSA是由Ron Rivest、AdiShamir和Len Adleman 3位作者1977年在MIT开发出来的，并于1978年首次发表。自此，RSA算法已成为最广泛接受和实施的公钥加密算法。RSA是一种块密码，其明文和密文是介于1到n-1之间的整数，n是某个大整数。

对于明文块M和密文块C，加密和解密的形式如下：

C = Me mod n

M = Cd mod n =（Me）d mod n = Med mod n

发送方和接收方都知道n和e的值，但只有一方知道d的值。这是一个使用公钥PU = {e，n}和私钥PR = {d，n}的公钥加密算法。该算法必须满足以下要求才能用于公钥加密。

（1）可以找到整数e、d、n，使得对所有M < n，Med mod n = M。

（2）对所有M < n，计算Me和Cd相对比较容易。

（3）知道e和n，计算d是不可行的。

前两个要求容易满足，当e和n的值很大时，第3个要求也能够得到满足。

这里主要讨论第一个要求，需要找出如下关系式：

Med mod n = M

如果e和d是模φ（n） 的乘法逆元，上述关系成立。其中φ（n） 是欧拉函数。对于素数p和q，当n = pq时，φ（pq）=（p-1）（q-1）称为n的欧拉函数，它的值是小于n并与n互素的正整数的个数。e和d是模φ（n）的乘法逆元，可表示如下（要求e和d都和φ（n） 互素）：

ed mod φ（n）= 1或d-1= eφ（n）

以下是RSA算法的构造过程：

（1）选择p、q。要求p和q都是素数，且p≠q。

（2）计算n = pq。n是加密和解密时使用的模。

（3）计算φ（n） =（p-1）（q-1）。

（4）选择整数e。要求e和φ（n） ）互素，且1 < e <φ（n） 。

（5）计算d。ed modφ（n） = 1。

到这里就确定了：公钥PU = {e，n}，私钥PR = {d，n}。

加密时：对于明文M < n，计算密文C = Me mod n。

解密时：对于密文C < n，计算明文M = Cd mod n。

这里有一个简单的例子。假如选择p、q为3和11，则n = pq = 33，φ（n） =（p-1）（q-1）=20。选择e = 3，因为3 < 20且3和20最大的公约数是1，满足条件。根据等式3d mod 20= 1计算d = 7。所以，公钥PU = {3，33}，私钥PR = {7，33}。

假如明文M = 5，则

C = Me mod n = 53 mod 33 = 125 mod 33 = 26

验证解密，则

M = Cd mod n = 267 mod 33 = [（261 mod 33）×（262 mod 33）×（264 mod 33）] mod 33

计算：

261 mod 33 =26

262 mod 33 =16

264 mod 33 =（16×16）mod 33 = 25

267 mod 33 =（26×16×25）mod 33 =5(www.daowen.com)

解密成功。

有4种可能的方法可以攻击RSA算法，其中比较知名的有2种。第1种方法是蛮力攻击：试遍所有可能的私钥。RSA算法防御此类攻击的方式与其他密码系统是一样的：使用更大的密钥空间。所以e和d的位数越多越安全。但是，因为密钥的生成和加密/解密所需的计算都比较复杂，密钥越大，系统运行得越慢。

第2种方法是将n分解成两个素数p、q。因为一旦得到p和q，就可以计算φ（n） 。而公钥e是公开的，所以可以通过ed modφ（n） = 1计算出私钥d。由于大数n具有很大的素因子，因此分解问题非常困难。尽管如此，它已经不如以前那么困难了。发生在1977年的著名事件恰好反映了这种情况。RSA的3位发明者挑战“Scientific American”的读者，请读者破解他们发表在Martin Gardner的“数学游戏”专栏中的密文。恢复明文则可以获得100美元的奖金。他们预计在4×1016年之内都不可能有人破解出来。但是，1994年4月，一个研究小组利用连接到Internet上的1 600多台计算机，只用了8个月的时间就破解了。这个挑战使用的公钥长度（n的长度）是129位的十进制数，即约428 bit的二进制数。这样的结果并没有让RSA的使用变得无效，它仅仅意味着应该采用长度更大的密钥。目前，对几乎所有的应用来说，1024 bit的密钥长度（大约300位十进制数）被认为足够安全。

另外两种攻击RSA的途径分别是计时攻击和选择密文攻击。前者依赖于解密算法的运行时间，后者利用RSA算法的特性。对这两种攻击的讨论超出了本书的范围。

2. Diffie-Hellman密钥交换

Diffie-Hellman密钥交换算法是最早的公开密钥算法，其安全性建立在有限域中计算离散对数的困难性的基础上。Diffie-Hellman算法可以用于密钥的分配：通信双方可以用这个算法产生一个秘密的密钥。但该算法不能用于加密和解密消息。

在进一步介绍这个算法之前，先介绍一下离散对数的概念。首先定义素数n的原根。素数n的原根是一个整数，其幂可以产生1～n-1的所有整数。也就是说，若g是素数n的原 根，则

g mod n，g2 mod n，g3 mod n，...，gn-1 mod n

各不相同，并且是1～n-1的一个置换。

对任意小于n的整数x和n的原根g，可以找到唯一的指数i，使得

x = gi mod n

式中 0≤i ≤（n-1），

指数i称为x的以g为底的模n的离散对数。

Diffie-Hellman密钥交换算法的原理很简单。通信双方（如Alice和Bob）约定一个素数n和一个整数g，g < n且g是n一个原根。这两个整数不用保密；Alice和Bob可以通过某种非安全的通道来约定这两个数。这两个数甚至可以由一群用户共享。

产生秘密密钥的过程如下：

（1）Alice选择一个随机整数a（要求a < n），并计算

X = ga mod n

（2）Bob选择一个随机整数b（要求b < n），并计算

Y = gb mod n

（3）Alice向Bob发送X，Bob 向Alice 发送Y（注意：Alice必须保密a，而Bob必须保密b）。

（4）Alice计算

k = Ya mod n

（5）Bob 计算

k′ = Xb mod n

k和k′ 都等于gab mod n。偷听Alice和Bob交换的X和Y的任何人都不能计算出这个值，他们只能知道n、g、X和Y。除非能计算离散对数从而恢复a和b，否则无法求解出k。k即为Alice和Bob各自独立计算出的秘密密钥。

这里a、b分别是Alice和Bob的私钥，X、Y分别是Alice和Bob的公钥。

使用这个算法时，n应该是一个大素数，至少512 bit，使用1024 bit更好。这个算法的缺点是容易受到中间人攻击。简单地说，就是第三方（如Dark）可以选择两个私钥da、db，然后计算出对应的两个公钥Xa和Xb。Dark拦截Alice和Bob之间交换的X和Y，并伪装Bob向Alice发送Xa，伪装Alice向Bob发送Xb。结果，Alice和Bob认为他们之间共享了一个密钥。但是实际情况是，Dark分别与Alice和Bob之间各共享了一个密钥。此后Alice和Bob之间交换的所有消息都能够被Dark解密，并且Dark还能够修改他们发送给对方的消息。

3. 数字签名标准（DSS）

DSS（Digital Signature Standard）是由美国国家标准与技术研究所（NIST）发布的，它给出了一种新的数字签名技术，即数字签名算法DSA。DSS最初在1991年被提出，1993年根据公众对其安全性的反馈意见对它进行了一些修改。1996年对它又做了少量修正。DSS使用了一种被设计成仅提供数字签名功能的算法。与RSA不同，DSS不能用于加密/解密和密钥交换。

4. 椭圆曲线密码（ECC）

大多数使用公钥密码来进行加密和数字签名的产品及标准都使用RSA算法。为了保障RSA使用的安全，最近这些年RSA密钥的长度一直在持续增加，这给使用RSA的应用增加了较重的处理负担。特别是对执行大量安全交易的电子商务网站而言更是如此。在20世纪末、21世纪初出现了一种具有竞争力的密码系统开始挑战RSA—— 椭圆曲线密码（Elliptic Curve Cryptography）ECC。并且，有些国际组织已经开始考虑标准化ECC了。

与RSA相比，ECC的主要吸引力在于它似乎可以用短得多的密钥提供同等的安全性，从而可以降低处理开销。另一方面，尽管关于ECC的理论已经存在一段时间了，但直到21世纪初才开始出现这方面的产品，并且对它的密码分析主要集中在对其脆弱点的探索。因此，人们对ECC信任程度还比不上RSA。