RSA加密演算法是一种非对称加密演算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
1973年，在政府通信总部工作的数学家在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。
對极大整数做因数分解的難度決定了 RSA 算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的-{zh-hans:信息;zh-tw:訊息}-的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到2020年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的-{zh-hans:信息;zh-tw:訊息}-实际上是不能被破解的。
1983年9月12日麻省理工学院在美国为RSA算法申请了专利。这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被發表了，在世界上大多数其它地区这个专利权不被承认。
操作
公钥与私钥的产生
假設Alice想要通過不可靠的媒體接收Bob的私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：
#隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
#根據歐拉函數，求得r=\varphi (N) = \varphi (p)\times\varphi (q)=(p-1)(q-1)
#選擇一個小于r的整數e，使e与r互质。並求得e关于r的模反元素，命名为d（求d令ed \equiv 1 \pmod{r}）。（模反元素存在，当且仅当e与r互质）
#將p和q的記錄銷毀。
(N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。
加密消息
假设Bob想给Alice送消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的非负整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：
: c = n^e \bmod{N}
这里的 c 可以用模幂算法快速求出来。Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：
: n = c^d \bmod {N}
与 Bob 计算 c 类似，这里的 n 也可以用模幂算法快速求出。得到n后，她可以将原来的信息m重新复原。
解码的原理是
: c^d \equiv n^{e \cdot d}\ (\mathrm{mod}\ N)
已知ed \equiv 1 \pmod{r}，即 ed=1+h\varphi (N)。那么有
: n ^ {ed} = n ^ {1 + h \varphi(N)} = n \cdot n ^ {h \varphi(N) } = n \left( n ^ {\varphi(N)} \right) ^ h
若 n 與 N 互質，則由欧拉定理得：
: n ^ {ed} \equiv n \left( n ^ {\varphi(N)} \right) ^ h \equiv n (1) ^ h \equiv n \pmod{N}
若 n 與 N 不互質，則不失一般性考慮 n = ph ，以及 ed -1 = k(q-1) ，得：
: n ^ {ed} = (ph) ^ {ed} \equiv 0 \equiv ph \equiv n \pmod p
: n ^ {ed} = n ^{ed - 1} n = n^{k(q - 1)} n = (n^{q - 1})^k n \equiv 1^k n \equiv n \pmod{q}
故 n ^ {ed} \equiv n \pmod N 得證。
签名消息
RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值（Message digest），然后用她的私钥“加密”（如同前面“加密消息”的步骤）这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”（如同前面“解密消息”的步骤）这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那麼Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。
正确性证明
首选取两个互质数p和q,
乘法计算p * q得到N。
然后计算出欧拉\Phi (N)：
\Phi函数\Phi (N)是小于或等于N的正整数中与N互质的数的数目。
根据欧拉公式，由于p和q都是质数，故
: \Phi (N) = (p - 1)(q - 1)
这时候我们随机选择一个整数e，条件是1 ，且e与\Phi(N) 互质。
接着我们计算e对\Phi(N)的模逆元得到d：
: e * d \equiv 1(mod \Phi(N))
这个公式简单的说就是 e * d除以\Phi(N)得到的余数为1，这个公式可以转换成
: ed \ \%\ ((p - 1) (q - 1)) = 1
即
: ed = k(p-1)(q-1)+1
于是，RSA公钥为(N,e),私钥为(N,d)。
加密原文m得到密文
: x = m^{e} \% N
解密公式为
: m = x^{d} \% N
证明解密逻辑：
在 m 的狀況下证明 m = x^{d} \% N ，就是证明 x^{d} \% N - m = 0
x^{d}%N-m
=(m^{e}%N)^{d}%N-m
=m^{ed}%N-m \quad \because a ^ b % p = ((a % p)^b) % p
=m^{k(p-1)(q-1)+1}%N-m
=m*(m^{k(p-1)(q-1)}-1)%N
当m与N互质时，根据费马小定理公式
a^{p-1} \equiv 1 (mod\ p)
\Rightarrow (m^{k(q-1)})^{p-1} \equiv 1 (mod\ p)
\Rightarrow (m^{k(p-1)})^{q-1} \equiv 1 (mod\ q)
\Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ pq)
\Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ N)
\Rightarrow m*(m^{k(p-1)(q-1)}-1)%N=0
当m与N不互质时，不妨设公因子为p，即m=ph_1 (h_1
假設q整除m。因此q \mid ph_1，因為q與p互質，根據歐幾里德引理，q \mid h_1。所以q \le h_1，而這與h_1矛盾，所以q不整除m。
此时m与q互质，根据费马小定理公式
a^{p-1} \equiv 1 (mod\ p)
\Rightarrow m^{q-1} \equiv 1 (mod\ q)
\Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ q)
\Rightarrow m^{k(p-1)(q-1)}-1=qh_2
\Rightarrow m(m^{k(p-1)(q-1)}-1)%N=ph_1qh_2%N=Nh_1h_2%N=0 ,证明完成。
安全性
假设偷听者Eve获得了Alice的公钥N和e以及Bob的加密消息c，但她无法直接获得Alice的密钥d。要获得d，最简单的方法是将N分解为p和q，这样她可以得到同余方程de \equiv 1 (\mathrm{mod}(p-1)(q-1))并解出d，然后代入解密公式
: c^d \equiv n\ (\mathrm{mod}\ N)
导出n（破密）。但至今为止还没有人找到一个多項式時間的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。
至今为止也没有人能够证明对N进行因数分解是唯一的从c导出n的方法，直到今天也还没有找到比它更简单的方法。（至少没有公开的方法。）
因此今天一般认为只要N足够大，那么駭客就没有办法了。
假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL，使人们开始质疑1024位长的N的安全性，目前推荐N的长度至少为2048位。
1994年，彼得·秀爾证明一台量子计算机可以在多項式時間内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀爾的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）
假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。
实现细节
密钥生成
首先要使用概率算法来验证随机产生的大的整数是否質数，这样的算法比较快而且可以消除掉大多数非質数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个質数。
除此之外这样找到的p和q还要满足一定的要求，首先它们不能太靠近，此外p-1或q-1的因子不能太小，否则的话N也可以被很快地分解。
此外寻找質数的算法不能给攻击者任何信息，这些質数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出p和q一半的位的话，那么他们就已经可以轻而易举地推算出另一半。
此外密钥d必须足够大，1990年有人证明假如p大于q而小于2q（这是一个很常見的情况）而d，那么从N和e可以很有效地推算出d。此外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位元。實作上，強制設置金鑰長度為2048位元的稱RSA或RSA2(意即RSA version 2)，而未強制設定的稱RSA1以資區別，兩者差異主要在金鑰長度。
已公开的或已知的攻击方法
大数因数分解
最常见的针对RSA的攻击是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花费五个月时间（约8000 MIPS年）、224 CPU小时，在一台有3.2G的Cray C916计算机上完成。
RSA-155表示如下：
39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603
= 3388495837466721394368393204672181522815830368604993048084925840555281177×
11658823406671259903148376558383270818131012258146392600439520994131344334162924536139
2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。
RSA-768表示如下：
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
= 3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489×
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917
时间攻击
1995年，丹·博內和提出了一种出人意料的攻击方式：假如Eve（竊密者）对Alice的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出d。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的，而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。
相關條目
- 公开密钥加密
- 橢圓曲線密碼學
- 量子電腦
- 秀爾演算法
- 米勒-拉賓質數判定法
- 迪菲-赫爾曼密鑰交換
- 模幂
- 快速幂
- 扩展欧几里得算法
参考文献
外部链接
- [http://www.rsasecurity.com RSA, The Security Division of EMC]
- [http://www.guideep.com/read?guide=5676830073815040 RSA算法详解]
评论 (0)