RSA加密算法

公钥与私钥的产生

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

1. 随意选择两个大的素数${\displaystyle p}$ 和${\displaystyle q}$ ，${\displaystyle p}$ 不等于${\displaystyle q}$ ，计算${\displaystyle N=pq}$ 。
2. 根据欧拉函数，求得${\displaystyle r=\varphi (N)=\varphi (p)\times \varphi (q)=(p-1)(q-1)}$ 
3. 选择一个小于${\displaystyle r}$ 的整数${\displaystyle e}$ ，使${\displaystyle e}$ 与${\displaystyle r}$ 互质。并求得${\displaystyle e}$ 关于${\displaystyle r}$ 的模逆元，命名为${\displaystyle d}$ （求${\displaystyle d}$ 令${\displaystyle ed\equiv 1{\pmod {r}}}$ ）。（模逆元存在，当且仅当${\displaystyle e}$ 与${\displaystyle r}$ 互质）
4. 将${\displaystyle p}$ 和${\displaystyle q}$ 的记录销毁。

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

加密消息

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

${\displaystyle c=n^{e}{\bmod {N}}}$ 

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

解密消息

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

${\displaystyle n=c^{d}{\bmod {N}}}$ 

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

解码的原理是

${\displaystyle c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)}$ 

已知${\displaystyle ed\equiv 1{\pmod {r}}}$ ，即 ${\displaystyle ed=1+h\varphi (N)}$ 。那么有

${\displaystyle n^{ed}=n^{1+h\varphi (N)}=n\cdot n^{h\varphi (N)}=n\left(n^{\varphi (N)}\right)^{h}}$ 

若${\displaystyle n}$ 与${\displaystyle N}$ 互素，则由欧拉定理得：

${\displaystyle n^{ed}\equiv n\left(n^{\varphi (N)}\right)^{h}\equiv n(1)^{h}\equiv n{\pmod {N}}}$ 

若${\displaystyle n}$ 与${\displaystyle N}$ 不互素，则不失一般性考虑${\displaystyle n=ph}$ ，以及${\displaystyle ed-1=k(q-1)}$ ，得：

${\displaystyle n^{ed}=(ph)^{ed}\equiv 0\equiv ph\equiv n{\pmod {p}}}$ 

${\displaystyle n^{ed}=n^{ed-1}n=n^{k(q-1)}n=(n^{q-1})^{k}n\equiv 1^{k}n\equiv n{\pmod {q}}}$ 

故 ${\displaystyle n^{ed}\equiv n{\pmod {N}}}$  得证。

签名消息

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

首选取两个互素数${\displaystyle p}$ 和${\displaystyle q}$ , 乘法计算${\displaystyle p*q}$ 得到${\displaystyle N}$ 。

然后计算出欧拉${\displaystyle \Phi (N)}$ ： ${\displaystyle \Phi }$ 函数${\displaystyle \Phi (N)}$ 是小于或等于${\displaystyle N}$ 的正整数中与${\displaystyle N}$ 互质的数的数目。 根据欧拉公式，由于${\displaystyle p}$ 和${\displaystyle q}$ 都是素数，故

${\displaystyle \Phi (N)=(p-1)(q-1)}$ 

这时候我们随机选择一个整数${\displaystyle e}$ ，条件是${\displaystyle 1<e<\Phi (N)}$ ，且${\displaystyle e}$ 与${\displaystyle \Phi (N)}$  互质。 接着我们计算${\displaystyle e}$ 对${\displaystyle \Phi (N)}$ 的模逆元得到${\displaystyle d}$ ：

${\displaystyle e*d\equiv 1(mod\Phi (N))}$ 

这个公式简单的说就是 ${\displaystyle e*d}$ 除以${\displaystyle \Phi (N)}$ 得到的余数为1，这个公式可以转换成

${\displaystyle ed\ \%\ ((p-1)(q-1))=1}$ 

即

${\displaystyle ed=k(p-1)(q-1)+1}$ 

于是，RSA公钥为${\displaystyle (N,e)}$ ,私钥为${\displaystyle (N,d)}$ 。

加密原文${\displaystyle m}$ 得到密文

${\displaystyle x=m^{e}\%N}$ 

解密公式为

${\displaystyle m=x^{d}\%N}$ 

证明解密逻辑：

在 ${\displaystyle m<N}$  的状况下证明${\displaystyle m=x^{d}\%N}$ ，就是证明${\displaystyle x^{d}\%N-m=0}$ 

${\displaystyle x^{d}\%N-m}$ 

${\displaystyle =(m^{e}\%N)^{d}\%N-m}$ 

${\displaystyle =m^{ed}\%N-m\quad \because a^{b}\%p=((a\%p)^{b})\%p}$ 

${\displaystyle =m^{k(p-1)(q-1)+1}\%N-m}$ 

${\displaystyle =m*(m^{k(p-1)(q-1)}-1)\%N}$ 

当m与N互质时，根据费马小定理公式

${\displaystyle a^{p-1}\equiv 1(mod\ p)}$ 

${\displaystyle \Rightarrow (m^{k(q-1)})^{p-1}\equiv 1(mod\ p)}$ 

${\displaystyle \Rightarrow (m^{k(p-1)})^{q-1}\equiv 1(mod\ q)}$ 

${\displaystyle \Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ pq)}$ 

${\displaystyle \Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ N)}$ 

${\displaystyle \Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=0}$ 

当m与N不互质时，不妨设公因子为p，即${\displaystyle m=ph_{1}(h_{1}<q)}$ 

假设q整除m。因此${\displaystyle q\mid ph_{1}}$ ，因为q与p互素，根据欧几里德引理，${\displaystyle q\mid h_{1}}$ 。所以${\displaystyle q\leq h_{1}}$ ，而这与${\displaystyle h_{1}<q}$ 矛盾，所以q不整除m。

此时m与q互质，根据费马小定理公式

${\displaystyle a^{p-1}\equiv 1(mod\ p)}$ 

${\displaystyle \Rightarrow m^{q-1}\equiv 1(mod\ q)}$ 

${\displaystyle \Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ q)}$ 

${\displaystyle \Rightarrow m^{k(p-1)(q-1)}-1=qh_{2}}$ 

${\displaystyle \Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=ph_{1}*qh_{2}\%N=Nh_{1}h_{2}\%N=0}$ ,证明完成。

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

${\displaystyle c^{d}\equiv n\ (\mathrm {mod} \ N)}$ 

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

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

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

假如${\displaystyle N}$ 的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的${\displaystyle N}$ 。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL^[6]，使人们开始质疑1024位长的N的安全性，目前推荐${\displaystyle N}$ 的长度至少为2048位。^[7]

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

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

密钥生成

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

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

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

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

速度

比起AES、3DES和其它对称算法来说，RSA要慢得多。实际的运用（如TLS）一般结合了对称加密（如AES）和非对称加密（如RSA）两者。

密钥分配

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

NIST建议的RSA密钥长度为至少2048位^[8]。

大数因数分解

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

RSA-155表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

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

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

时间攻击

1995年，丹·博内（英语：Dan Boneh）和大卫·布鲁姆利（英语：David Brumley）提出了一种非常意想不到的攻击方式：假如Eve（窃密者）对Alice的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出d。这种攻击方式之所以会成立，主要是因为在进行加密时所进行的模指数运算是一个比特一个比特进行的，而比特为1所花的运算比比特为0的运算要多很多，因此若能得到多组信息与其加密时间，就会有机会可以反推出私钥的内容。^[11]

• 公开密钥加密
• 椭圆曲线密码学
• 量子电脑
• 秀尔算法
• 米勒-拉宾素数判定法
• 迪菲-赫尔曼密钥交换
• 快速幂
• 扩展欧几里得算法

• RSA, The Security Division of EMC（页面存档备份，存于互联网档案馆）
• RSA算法详解（页面存档备份，存于互联网档案馆）