操作

公钥与私钥的产生

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：

随意选择两个大的质数p{\displaystyle p}和q{\displaystyle q}，p{\displaystyle p}不等于q{\displaystyle q}，计算N=pq{\displaystyle N=pq}。

根据欧拉函数，求得r=φ φ -->(N)=φ φ -->(p)φ φ -->(q)=(p− − -->1)(q− − -->1){\displaystyle r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)}

选择一个小于r{\displaystyle r}的整数e{\displaystyle e}，使e{\displaystyle e}与r{\displaystyle r}互质。并求得e{\displaystyle e}关于r{\displaystyle r}的模反元素，命名为d{\displaystyle d}（求d{\displaystyle d}令ed≡ ≡ -->1(modr){\displaystyle ed\equiv 1{\pmod {r}}}）。(模反元素存在，当且仅当e{\displaystyle e}与r{\displaystyle r}互质）

将p{\displaystyle p}和q{\displaystyle q}的记录销毁。

(N,e){\displaystyle (N,e)}是公钥，(N,d){\displaystyle (N,d)}是私钥。Alice将她的公钥(N,e){\displaystyle (N,e)}传给Bob，而将她的私钥(N,d){\displaystyle (N,d)}藏起来。

加密消息

假设Bob想给Alice送一个消息m{\displaystyle m}，他知道Alice产生的N{\displaystyle N}和e{\displaystyle e}。他使用起先与Alice约好的格式将m{\displaystyle m}转换为一个小于N{\displaystyle N}，且与N{\displaystyle N}互质的整数n{\displaystyle n}，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n{\displaystyle n}。用下面这个公式他可以将n{\displaystyle n}加密为c{\displaystyle c}：

计算c{\displaystyle c}并不复杂。Bob算出c{\displaystyle c}后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c{\displaystyle c}后就可以利用她的密钥d{\displaystyle d}来解码。她可以用以下这个公式来将c{\displaystyle c}转换为n{\displaystyle n}：

得到n{\displaystyle n}后，她可以将原来的信息m{\displaystyle m}重新复原。

解码的原理是

已知ed≡ ≡ -->1(modr){\displaystyle ed\equiv 1{\pmod {r}}}，即 ed=1+hφ φ -->(N){\displaystyle ed=1+h\varphi (N)}。 由欧拉定理得：

签名消息

RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值（Message digest），然后用她的私钥加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。

安全

假设偷听者乙获得了甲的公钥N{\displaystyle N}和e{\displaystyle e}以及丙的加密消息c{\displaystyle c}，但她无法直接获得甲的密钥d{\displaystyle d}。要获得d{\displaystyle d}，最简单的方法是将N{\displaystyle N}分解为p{\displaystyle p}和q{\displaystyle q}，这样她可以得到同余方程de=1(mod(p− − -->1)(q− − -->1)){\displaystyle de=1(\mathrm {mod} (p-1)(q-1))}并解出d{\displaystyle d}，然后代入解密公式

导出n（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。

至今为止也没有人能够证明对N{\displaystyle N}进行因数分解是唯一的从c{\displaystyle c}导出n{\displaystyle n}的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。）

因此今天一般认为只要N{\displaystyle N}足够大，那么黑客就没有办法了。

假如N{\displaystyle N}的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N{\displaystyle N}。今天对N{\displaystyle N}的要求是它至少要1024位长。

1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的派生算法。（即依赖于分解大整数困难性的加密算法）

假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。

实现细节

密钥生成

首先要使用概率算法来验证随机产生的大的整数是否质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。

除此之外这样找到的p{\displaystyle p}和q{\displaystyle q}还要满足一定的要求，首先它们不能太靠近，此外p− − -->1{\displaystyle p-1}或q− − -->1{\displaystyle q-1}的因子不能太小，否则的话N{\displaystyle N}也可以被很快地分解。

此外寻找质数的算法不能给攻击者任何信息，这些质数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出p{\displaystyle p}和q{\displaystyle q}一半的位的话，那么他们就已经可以轻而易举地推算出另一半。

此外密钥d{\displaystyle d}必须足够大，1990年有人证明假如p{\displaystyle p}大于q{\displaystyle q}而小于2q{\displaystyle 2q}(这是一个很经常的情况）而dN14{\displaystyle d ，那么从N{\displaystyle N}和e{\displaystyle e}可以很有效地推算出d{\displaystyle d}。此外e=2{\displaystyle e=2}永远不应该被使用。

速度

比起DES和其它对称算法来说，RSA要慢得多。实际上Bob一般使用一种对称算法来加密他的信息，然后用RSA来加密他的比较短的对称密码，然后将用RSA加密的对称密码和用对称算法加密的消息送给Alice。

密钥分配

和其它加密过程一样，对RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设Eve交给Bob一个公钥，并使Bob相信这是Alice的公钥，并且她可以截下Alice和Bob之间的信息传递，那么她可以将她自己的公钥传给Bob，Bob以为这是Alice的公钥。Eve可以将所有Bob传递给Alice的消息截下来，将这个消息用她自己的密钥解密，读这个消息，然后将这个消息再用Alice的公钥加密后传给Alice。理论上Alice和Bob都不会发现Eve在偷听他们的消息。今天人们一般用可靠的第三方机构签发证书来防止这样的攻击。

时间攻击

1995年有人提出了一种非常意想不到的攻击方式：假如Eve对Alice的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出d。这种攻击方式之所以会成立，主要是因为在进行加密时所进行的模指数运算是一个比特一个比特进行的，而比特为1所花的运算比比特为0的运算要多很多，因此若能得到多组消息与其加密时间，就会有机会可以反推出私钥的内容。

典型密钥长度

1997年后开发的系统，用户应使用1024位密钥，证书认证机构应用2048位或以上。

已公开的或已知的攻击方法

针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits)被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。

RSA-158表示如下：

2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：

相关条目

公开密钥加密

量子计算机

秀尔算法

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。