1978年《ACM通讯》刊发了一篇由Ron Rivest、Adi Shamir和Leonard Adleman共同完成的文章。文章提出了一种新的加密算法，是现在我们所熟知且广泛使用的一种非对称加密算法————RSA加密算法。原文的标题是《A Method for Obtaining Digital Signatures and Public-Key Cryptosystems》，本文是该文章的译文。
【摘要】
本文提出一种新的加密算法，公开该加密算法的加密密钥并不会导致解密密钥的泄漏。由此可以得出两个重要的结论：
1.对一段信息使用加密密钥进行加密，在该信息到预期的接收者之前，不需要用信使或者其他的安全的手段传输解密密钥。只有一个预期的接收者拥有对应的解密密钥，也就只有那一个接收者能够解密这段加密了的信息。
2.使用私有的解密密钥能够唯一的标记一段信息（称为对信息进行签名）。每个人都能够使用对应的公开的加密密钥来验证这段信息的签名。签名不能伪造，签名者也不能在签名之后否认签名的有效性。这在电子邮件系统或者电子转账系统方面有很显著的应用。
加密的过程是将一段信息表示成数字M，计算Me的值，其中e是一个随机数；再计算Me/n的余数，余数就是被加密后的信息，其中n是两个质数p和q的乘积。解密的过程和加密的过程相似，是有一个不同点，需要使用d，其中d由e·d ≡ 1 (mod (p-1)·(q-1))计算得到。这种加密系统的安全性在于将n分解成两个质数在某种程度上是很困难的。
Ⅰ 简介
我们将迎来电子邮件的时代，我们必须确保电子邮件也具备当前“纸质邮件”的两种特性：(a)信息是私密的；(b)能够在信息上签名。我们在这篇论文上论证如何使电子邮件系统也具有这些特性。
我们的方法的核心是提出一种新的加密方法。这种加密使用了“公开密钥”的方法，这是由Whitfield Diffie和Martin Hellman提出的一种开创性的加密思路。自从他们提出了这种加密概念，但没有任何实际的系统实现。我们的研究是受Whitfield Diffie和Martin Hellman文章的启发而进行的。读者如果很熟悉的话可以跳过部分内容，阅读第五部分查看我们对公开密钥加密的实现描述。
II 公开密钥加密
在公开密钥加密系统中，每个用户在一个公共的文件中都有一个加密过程E。这个公共文件是给每个用户在加密的过程中使用的，这个文件如同字典一样。每个用户同时还秘密保存着对应的解密过程D。这些过程有以下四点性质：
(a) 将被加密的信息M解密还能产生M。用公式表示：
D(E(M)) = M —— (5)
(b) 过程E和D都便于进行。
(c)通过公开加密过程E给其他用户不会轻易泄漏计算解密过程D的方法。这意味着在实际中，加密系统中的用户只能使用E加密信息，否则几乎不可能破解得到解密过程D。
(d) 如果信息M先经过解密过程处理，再经过加密过程，得到的结果还是M。
E(D(M)) = M
一个典型的加密（或解密系统）包含加密方法和加密密钥。通常的做法是在密钥的控制下，加密方法将一段信息M转换成特定形式的信息，称为密文C。每个人都使用同样的加密方法；这种加密的安全性取决于密钥的安全性。加密算法的泄漏也就意味着加密密钥的泄漏。
在公开密钥加密算法中，当用户公开加密过程E的同时，也提供了一种非常没效率的解密方法来计算D(C):测试信息M的所有可能，直到找到M使得E(M)=C成立。如果性质(c)满足，这样的测试方法会由于计算量过于庞大以至于这是一种不切实际的做法。
一个加密过程E满足性质(a)-(c)就是一个单向陷阱门；如果同时也满足性质(e)，则这是一个单向可变陷阱门。Diffie和Hellman介绍了单向陷阱门的概念但没有给出任何例子。这些过程叫做“单向”是因为向一个目标进行计算很容易，但反方向计算却很困难。他们被称为可变陷阱门是因为一旦知道陷阱门隐藏的信息，反方向的计算也会很容易。一个单向陷阱门满足性质(d)就一定是可变换的：所有的信息都是其他信息的密文，每一个密文都有它们自己的解密方法。性质(d)只有在签名的时候需要使用。
我们鼓励读者阅读Whitfield Diffie和Martin Hellman的那篇具有创造性的文章来了解更多的背景，可以帮助了解公开密钥加密的思想和密码学领域的其他问题。公开密钥加密算法能够保证私密性以及能对信息签名都得力于Diffie和Hellman的研究。
在我们的场景中，我们假设有A和B（我们所熟知的Alice和Bob）是公开密钥加密系统中的两个用户。我们将A和B的加密和解密过程用EA、DA、EB、DB来表示。
III 私密性
加密是保证通信私密性的常规方法。信息发送者给接收者发送信息之前进行对信息进行加密。接收者（不包括位授权的接收者）知道解密的方法，解密之后得到未被加密的信息。窃听者如果不知道信息解密的方法，那他收到的只是杂乱的“垃圾”（加密之后的密文）。
大量的个人信息和敏感信息存放在数据库中，在电话线中传输加密的数据变得越来越重要了。注意到高效、有质量是加密技术所必备的，但现在的加密系统并不具备这些特性，美国国家标准局采用了一种IBM开发的数据加密标准[13,14]。但新标准不具有性质c，需要使用公开密钥加密的方法。
所有传统的加密算法（包括NBS标准在内的）都不能解决安全分发密钥的问题。密钥分发的问题是在私密通讯开始之前，必须使用其他私密的手段将加密密钥和解密密钥分发给发送者和接收者。传统的做法是发送者使用私密的信使将密钥传送给接收者。但是这样的做法在电子邮件系统中就很慢、成本也不低，所以传统的做法在电子邮件中并不可行。公开密钥加密系统中部需要私密的信使来传送密钥；密钥可以通过不安全的通信信道来分发。
在一个公开密钥加密系统中，Bob要如何发送私密的信息M给Alice呢？首先，Bob先在公共文件中获得Alice公开的加密密钥EA。Alice通过DA(EA(M))=M来计算获得信息M。由于公开加密密钥系统的特性c，只有Alice能够将EA(M)解密。Alice可以用Bob的加密密钥EB给Bob私密的回复，EB是从公共文件中获得。
两个用户够通过查看公共文件就能够在不安全的信道中建立私密的联系。每个用户发送他的加密密钥给其他人。之后，在公开密钥加密系统中，所有的信息被加密密钥加密处理过了。由于从加密密钥计算得到解密密钥是几乎不可能的事情，所以窃听者在信道中无法解密任何信息。（我们假设窃听者不能改变或者增加信道中的信息）。Ralph Merkle已经提出了解决该问题[5]的其他方法。
一个公开加密密钥系统能够作为其他标准加密过程的第一步，例如NBS的加密方法。在NBS系统中，一旦私密的通信信道被建立，最先发送的是NBS的密钥，之后的信息就可以用密钥来加密。如果我们的公开密钥算法的速度比其他标准的加密算法慢，那么这是一个可行性很高的方法。（在特定的机器上运行NBS的加密/解密速度会很快；我们的公开密钥加密算法在通用计算机上会比NBS的更快，因为在二进制的机器上容易进行乘法运算。）
IV 签名
如果电子邮件系统在商业上要取代现有的纸质邮件，那一定要有在电子邮件上“签名”的功能。带有签名信息的接收者能够辨别出信息是否来自发送者（而不是其他人伪造的）。“签名”的做法比只进行用户认证的做法更有效；接收者能够相信“法官”的判断，判断接收到的信息是否来自发送者。为了保证签名的可靠性，他必须使法官相信他自己不会伪造签名。数字签名使得接收者可以自行确认信息是否来自发送者，接收者不需要担心信息是否是其他人伪造的。
电子签名必须是信息依赖的，就像签名者依赖一样。否则接收者可以在给法官展示信息-签名之前修改它们。否则他就有可能将原有签名“剪下”，再将签名“粘贴”其它信息上。
为了让公开密钥加密系统具有签名的功能，加密系统必须是单向可置换的陷阱门（这也证明了性质d），否则解密算法有可能作用在一个非加密的信息上。
在公开密钥加密系统中，Bob要如何给Alice发送一段带签名的信息M呢？Bob首先使用他的解密密钥DB来计算信息M的“签名”：
S=DB(M)
（在公开密钥加密系统中，将一段未加密的信息进行解密操作是可行的，这是由于性质d：每个信息是其他信息的密文。）然后Bob使用EA加密S（这一步是保证通讯的私密性），最后Bob将加密结果EA(S)发送给Alice。Bob不用直接发送原始信息M给Alice，M可以从S计算可得。
Alice收到信息之后，先使用DA将密文解密得到S。她知道这段信息可能的发送者（在我们这个例子中是Bob）；如果必要的话，这可以从签名后的信息S中得到。Alice最后用Bob的加密密钥EB来提取原始信息M，在这个例子中：M=EB(S)
她现在拥有一个信息-签名对（M,S），数字签名就像是文档上的签名。
Bob随后不能否认他曾向Alice发送过信息，因为出了Bobby，没有人能够给出S=DB(M)。Alice能够让“法官”相信EB(S)=M，所以她能证实Bob签名了这个文档。
显然，Alice不能将信息M改为其它版本的M’，这是由于她必须为新的信息M’创新对应的签名S’ = DB(M’)。
因此，Alice收到一段由Bob”签名“的信息，她能够证实这是Bob发送的，但她不能够更改原有的信息。（她同样不能为其它的信息伪造Bob的签名。）
可以基于上述签名的方法完成一个电子检测系统。很容易想象在你的终端有一台加密设备允许你进行签名检查，它可以检查你和收款人收发的电子邮件的签名。只需要在每张支票上加上一个独一无二的支票号，即使收款人伪造了支票，银行也只会相信最早见到的支票。
另一个可能出现的问题是加密设备是否足够的快：在一个电话交谈中，在传输之前对每个单词进行签名要成为可能。
当加密用在上述签名的时候，由于一段信息可能被几种不同的密钥加密，加密设备不要被固定在终端和通讯信道。更好的方法是将加密设备看成“硬件子程序”，在需要的时候才执行。
我们在上面已经假设系统中的每个用户总是能够访问公共的文件。但在计算机网络中，这可能有些困难；“入侵者”可能会伪造公共文件的信息。用户想要确保他们实际使用中，在获取加密密钥的时候得到的是他们想要的密钥，而不是得到“入侵者”的加密密钥。不过这个问题可以解决，只要保证公共文件给用户的文件都是签名过的。每个用户使用公共文件的加密密钥EPF检查签名。为了避免用户自己“寻找”EPF，当一个用户第一次加入到公开密钥加密系统中的时候，给他EPF的描述，并记录下他的加密密钥E。然后他存储下这个加密密钥，从而不再重复查询。我们不需要在两个用户之间使用信使来传递密钥，取而代之的是当用户加入到加密系统中，保证每个用户间单一交流的安全和使用管理者来管理公共文件。另一个解决方案是当用户加入到系统中的时候，给每个新加入的用户一个包含系统中所有用户的加密密钥的文件（这文件像是电话本一样）。
V 加密和解密方法
我们使用一个公钥( e, n )，经过下面几个步骤加密一段信息M。（这里n和e是一对正整数。）
首先，将信息M用0 ~ n-1的整数表示。（如果信息不小于n，将信息分解成若干段，分别加密每一段信息。）使用任何标准的信息编码都可以。这个步骤仅仅是获取信息的整数表示，不对信息进行加密。
然后，通过计算M的e次方除以n的余数，对信息进行加密。也就是计算C = Me mod n ，C就是加密后的密文。
如果要进行解密，计算C的d次方除以n的余数。加密和解密的算法E和D表示成如下：
C = D(C) = Ce (mod n)，解密密文C。
注意，加密不会导致信息变长；密文和原始信息一样都是0 ~ n-1的整数。
加密密钥是由一对正整数( e, n )组成。相似地，解密密钥是由正整数对( d, n )组成。每个用户公开他自己的加密密钥，同时保证对应的解密密钥仅仅只有自己知道。（因为每个用户都有不一样的n, d, e，所以这些整数应被确切的描述成nA，eA，dA。不过，在这里我们只考虑一般的情况并忽略了下标。）
如果你想使用我们的公开密钥加密，要怎么选择加密密钥和解密密钥？
首先计算n，n是两个质数p和q的乘积：
n = p·q
这些质数都非常大，“随机”的质数。虽然你将会公开n，但是由于将n分解成两个质数将很困难，所以p和q被很好的隐藏了。这也就隐藏了从e得到d的方法。
然后你随机选择一个大质数d，d小于(p - 1)·(q - 1)。也就是使得d满足：gcd(d; (p - 1)·(q - 1)) = 1。（gcd是greatest common divisor。）
最后整数e由p、q和d计算得到，e是d对于(p - 1)·(q - 1))的模反元素。所以我们有
e·d ≡ 1 (mod (p-1)·(q-1))
我们在下一部分证明这保证了公式 (1) 和 (2) 成立，也就是加密过程E和解密过程D是相互转换的。第VII部分我们展示如何高效的进行每个操作。
上面提到的方法不要和Diffe、Hellman提出的取幂解决密钥分发问题的技术混在一起。他们的技术允许两个用户在通用的加密系统中传输密钥。这不是基于单向可置换陷阱门。Pohlig和Hellman学习了和我们相关的模式使用了幂次再除以质数求余。
VI 数学基础
我们证明解密算法的正确性，基于Euler和Fermat[7]的一致性：对于一个整数M（信息M）和由相关的质素组成的n：
MΦ(n) ≡ 1 (mod n) —— (3)
这里Φ(n)是欧拉函数，欧拉函数计算小于n的整数中，和n互质的个数。对于一个质素p，Φ(p) = p-1。
在我们的例子中，对于欧拉函数有基本的性质：
Φ(n) = Φ(p)·Φ(q) = (p-1)·(q-1) = n - (p + q) + 1 —— (4)
由于d和Φ(n)互质，所以有一个模反元素e使得：
e·d ≡ 1 (mod Φ(n)) —— (5)
我们现在已经证明等式(1)、(2)成立（也就是如果e和d按照上面的方式选取，解密可以正常进行）。现在
和
从(3)我们可以看到对于所有M，M满足不能被p整除
Mp-1 ≡ 1 (mod p)
并且由于(p-1)整除Φ(n)
Mk·Φ(n)+1 ≡ M (mod p)
当M被p整除的时候，这是很明显的，所以这等式对于所有的M都成立。对于q得出相似的结论
Mk·Φ(n)+1 ≡ M (mod q)
结合这两条等式，对于所有的M，
Me·d ≡ Mk·Φ(n)+1 ≡ M (mod n)