查看“︁RSA加密演算法”︁的源代码

{{多個問題|
{{disputed|time=2014-06-04T05:10:33+00:00}}
{{expert|time=2014-06-04T05:10:33+00:00}}
}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
{{Infobox block cipher
| name          = RSA
| designers     = [[羅納德·李維斯特]]<br>[[阿迪·薩莫爾]]<br>[[倫納德·阿德曼]]
| publish date  = 1977
| type          = 公钥加密算法
| derived from  =
| derived to    =
| related to    =
| certification = PKCS#1, ANSI X9.31, IEEE 1363
| key size      =2048 - 4096 位 （常规情况）
| block size    =
| structure     =
| rounds        = 1
| cryptanalysis = 传统计算机：[[普通数域筛选法]]<br />量子计算机：[[秀尔算法]]<br />RSA-250（829位）已经被攻破
}}
[[File:Adi Shamir 2009 crop.jpg|thumb|175px|RSA的作者之一：[[阿迪·萨莫尔]]]]
'''RSA加密演算法'''是一种[[非对称加密演算法]]，在[[公开密钥加密]]和[[电子商业]]中被广泛使用。RSA是由[[罗纳德·李维斯特]]（Ron Rivest）、[[阿迪·萨莫尔]]（Adi Shamir）和[[伦纳德·阿德曼]]（Leonard Adleman）在1977年一起提出的。当时他们三人都在[[麻省理工学院]]工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。<ref>{{Cite web|url = http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Calderbank.pdf|title = The RSA Cryptosystem: History, Algorithm, Primes|date = 2007-08-20|accessdate = |website = |publisher = |last = Calderbank|first = Michael|archive-date = 2016-12-13|archive-url = https://web.archive.org/web/20161213074659/http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Calderbank.pdf|dead-url = yes}}</ref>

1973年，在[[政府通信总部|英国政府通讯总部]]工作的数学家[[克利福德·柯克斯]]（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。<ref>{{Cite web|url=https://www.gchq.gov.uk/sites/default/files/document_files/Cliff%20Cocks%20paper%2019731120.pdf|title=A Note on Non-Secret Encryption|last=Cocks|first=C.C.|authorlink=Clifford Cocks|date=1973-11-20|website=www.gchq.gov.uk|access-date=2017-05-30|archive-date=2017-02-16|archive-url=https://web.archive.org/web/20170216051604/https://www.gchq.gov.uk/sites/default/files/document_files/Cliff%20Cocks%20paper%2019731120.pdf|dead-url=no}}</ref>

對极大整数做[[因数分解]]的難度決定了 RSA 算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的-{zh-hans:信息;zh-tw:訊息}-的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到2020年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的-{zh-hans:信息;zh-tw:訊息}-实际上是不能被破解的。

1983年9月12日麻省理工学院在[[美国]]为RSA算法申请了[[专利]]。<ref>{{Citation|title=Cryptographic communications system and method|date=1977-12-14|url=https://patents.google.com/patent/US4405829A/en|accessdate=2018-04-09|archive-date=2019-02-17|archive-url=https://web.archive.org/web/20190217170435/https://patents.google.com/patent/US4405829A/en|dead-url=no}}</ref>这个专利于2000年9月21日失效。<ref>{{cite web |url=http://www.rsa.com/press_release.aspx?id=261 |title=RSA Security Releases RSA Encryption Algorithm into Public Domain |accessdate=2010-03-03 |deadurl=yes |archiveurl=https://web.archive.org/web/20070621021111/http://www.rsa.com/press_release.aspx?id=261 |archivedate=2007-06-21 |df= }}</ref>由于该算法在申请专利前就已经被發表了<ref name="SIAM">{{cite journal |url=http://www.msri.org/people/members/sara/articles/rsa.pdf |journal=SIAM News |volume=36 |issue=5 |date=June 2003 |title=Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders |first=Sara |last=Robinson |access-date=2018-04-09 |archive-date=2017-01-16 |archive-url=https://web.archive.org/web/20170116044746/http://www.msri.org/people/members/sara/articles/rsa.pdf |dead-url=yes }}</ref>，在世界上大多数其它地区这个专利权不被承认。

== 操作 ==

=== 公钥与私钥的产生 ===
假設[[愛麗絲與鮑伯|Alice]]想要通過不可靠的媒體接收Bob的私人訊息。她可以用以下的方式來產生一個'''公鑰'''和一個'''私鑰'''：

#隨意選擇兩個大的[[質數]]<math>p</math>和<math>q</math>，<math>p</math>不等於<math>q</math>，計算<math>N=pq</math>。
#根據[[欧拉函数|歐拉函數]]，求得<math>r=\varphi (N) = \varphi (p)\times\varphi (q)=(p-1)(q-1)</math>
#選擇一個小于<math>r</math>的整數<math>e</math>，使<math>e</math>与<math>r</math>互质。並求得<math>e</math>关于<math>r</math>的[[模反元素]]，命名为<math>d</math>（求<math>d</math>令<math>ed \equiv 1 \pmod{r}</math>）。（模反元素存在，当且仅当<math>e</math>与<math>r</math>互质）
#將<math>p</math>和<math>q</math>的記錄銷毀。

<math>(N,e)</math>是公鑰，<math>(N,d)</math>是私鑰。Alice將她的公鑰<math>(N,e)</math>傳給Bob，而將她的私鑰<math>(N,d)</math>藏起來。

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

: <math> c = n^e \bmod{N} </math>

这里的 <math>c</math> 可以用[[模幂]]算法快速求出来。Bob算出<math>c</math>后就可以将它传递给Alice。

=== 解密消息 ===
Alice得到Bob的消息<math>c</math>后就可以利用她的密钥<math>d</math>来解码。她可以用以下这个公式来将<math>c</math>转换为<math>n</math>：

:<math> n = c^d \bmod {N} </math>

与 Bob 计算 <math>c</math> 类似，这里的 <math>n</math> 也可以用[[模幂]]算法快速求出。得到<math>n</math>后，她可以将原来的信息<math>m</math>重新复原。

解码的原理是

:<math> c^d \equiv n^{e \cdot d}\ (\mathrm{mod}\ N)</math>

已知<math>ed \equiv 1 \pmod{r}</math>，即 <math>ed=1+h\varphi (N)</math>。那么有

: <math> n ^ {ed} = n ^ {1 + h \varphi(N)} = n \cdot n ^ {h \varphi(N) } = n \left( n ^ {\varphi(N)} \right) ^ h </math>

若<math> n </math>與<math> N </math>互質，則由[[欧拉定理 (数论)|欧拉定理]]得：

: <math> n ^ {ed} \equiv n \left( n ^ {\varphi(N)} \right) ^ h \equiv n (1) ^ h \equiv n \pmod{N} </math>

若<math> n </math>與<math> N </math>不互質，則不失一般性考慮<math> n = ph </math>，以及<math> ed -1 = k(q-1) </math>，得：
: <math> n ^ {ed} = (ph) ^ {ed} \equiv 0 \equiv ph \equiv n \pmod p </math>
: <math> n ^ {ed} = n ^{ed - 1} n = n^{k(q - 1)} n = (n^{q - 1})^k n \equiv 1^k n \equiv n \pmod{q} </math>
故 <math> n ^ {ed} \equiv n \pmod N </math> 得證。

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

== 正确性证明 ==

首选取两个互质数<math>p</math>和<math>q</math>,
乘法计算<math>p * q</math>得到<math>N</math>。

然后计算出欧拉<math>\Phi (N)</math>：
<math>\Phi</math>函数<math>\Phi (N)</math>是小于或等于<math>N</math>的正整数中与<math>N</math>互质的数的数目。
根据欧拉公式，由于<math>p</math>和<math>q</math>都是质数，故
: <math> \Phi (N) = (p - 1)(q - 1) </math>

这时候我们随机选择一个整数<math>e</math>，条件是<math>1 < e < \Phi(N)</math>，且<math>e</math>与<math>\Phi(N)</math> 互质。
接着我们计算<math>e</math>对<math>\Phi(N)</math>的模逆元得到<math>d</math>：
: <math> e * d \equiv 1(mod \Phi(N)) </math>
这个公式简单的说就是 <math>e * d</math>除以<math>\Phi(N)</math>得到的余数为1，这个公式可以转换成
: <math> ed \ \%\  ((p - 1) (q - 1)) = 1 </math>
即
: <math> ed = k(p-1)(q-1)+1 </math>

---------------------------------------------------------

于是，RSA公钥为<math>(N,e)</math>,私钥为<math>(N,d)</math>。

加密原文<math>m</math>得到密文
: <math> x = m^{e} \% N </math>
解密公式为
: <math> m = x^{d} \% N </math>

---------------------------------------------------------

'''证明解密逻辑：'''

在 <math> m<N </math> 的狀況下证明<math> m = x^{d} \% N </math>，就是证明<math> x^{d} \% N - m = 0 </math>

<math> x^{d}%N-m </math>

<math> =(m^{e}%N)^{d}%N-m </math>

<math> =m^{ed}%N-m  \quad \because a ^ b % p = ((a % p)^b) % p </math>

<math> =m^{k(p-1)(q-1)+1}%N-m </math>

<math> =m*(m^{k(p-1)(q-1)}-1)%N </math>

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

<math> a^{p-1} \equiv 1 (mod\ p)</math>

<math> \Rightarrow (m^{k(q-1)})^{p-1} \equiv 1 (mod\ p)</math>

<math> \Rightarrow (m^{k(p-1)})^{q-1} \equiv 1 (mod\ q) </math>

<math> \Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ pq) </math>

<math> \Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ N) </math>

<math> \Rightarrow m*(m^{k(p-1)(q-1)}-1)%N=0 </math>

当m与N不互质时，不妨设公因子为p，即<math>m=ph_1 (h_1<q)</math>

假設q整除m。因此<math>q \mid ph_1</math>，因為q與p互質，根據[[歐幾里德引理]]，<math>q \mid h_1</math>。所以<math>q \le h_1</math>，而這與<math>h_1<q</math>矛盾，所以q不整除m。

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

<math> a^{p-1} \equiv 1 (mod\ p)</math>

<math> \Rightarrow m^{q-1} \equiv 1 (mod\ q)</math>

<math> \Rightarrow m^{k(p-1)(q-1)} \equiv 1 (mod\ q)</math>

<math> \Rightarrow m^{k(p-1)(q-1)}-1=qh_2</math>

<math> \Rightarrow m*(m^{k(p-1)(q-1)}-1)%N=ph_1*qh_2%N=Nh_1h_2%N=0 </math>,证明完成。

== 安全性 ==
假设偷听者Eve获得了Alice的公钥<math>N</math>和<math>e</math>以及Bob的加密消息<math>c</math>，但她无法直接获得Alice的密钥<math>d</math>。要获得<math>d</math>，最简单的方法是将<math>N</math>分解为<math>p</math>和<math>q</math>，这样她可以得到[[线性同余方程|同余方程]]<math>de \equiv 1 (\mathrm{mod}(p-1)(q-1))</math>并解出<math>d</math>，然后代入解密公式
: <math> c^d \equiv n\ (\mathrm{mod}\ N) </math> 
导出''n''（破密）。但至今为止还没有人找到一个多項式時間的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见[[因数分解]]）。

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

因此今天一般认为只要<math>N</math>足够大，那么駭客就没有办法了。

假如<math>N</math>的长度小于或等于256[[位]]，那么用一台[[个人电脑]]在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的<math>N</math>。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL<ref>{{Cite web|url=http://cs.tau.ac.il/~tromer/twirl/|title=TWIRL (The Weizmann Institute Relation Locator)|accessdate=2018-04-16|last=Tromer|first=Eran|work=cs.tau.ac.il|archive-date=2018-04-20|archive-url=https://web.archive.org/web/20180420195428/http://www.cs.tau.ac.il/~tromer/twirl/|dead-url=no}}</ref>，使人们开始质疑1024位长的N的安全性，目前推荐<math>N</math>的长度至少为2048位。<ref>[http://www.emc.com/emc-plus/rsa-labs/historical/has-the-rsa-algorithm-been-compromised.htm Has the RSA algorithm been compromised as a result of Bernstein's Paper?] {{Wayback|url=http://www.emc.com/emc-plus/rsa-labs/historical/has-the-rsa-algorithm-been-compromised.htm |date=20130923062442 }} What key size should I be using?</ref>

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

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

== 实现细节 ==

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

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

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

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

=== 速度 ===

比起[[高級加密標準|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位元<ref>{{Cite web|title=Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019)|url=https://www.keylength.com/en/4/|accessdate=2020-04-22|work=www.keylength.com|archive-date=2020-04-04|archive-url=https://web.archive.org/web/20200404041712/https://www.keylength.com/en/4/|dead-url=no}}</ref>。實作上，強制設置金鑰長度為2048位元的稱RSA或RSA2(意即RSA version 2)，而未強制設定的稱RSA1以資區別，兩者差異主要在金鑰長度。

== 已公开的或已知的攻击方法 ==
=== 大数因数分解 ===
{{see also|RSA数}}
最常见的针对RSA的攻击是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花费五个月时间（约8000 [[每秒指令|MIPS]]年）、224 CPU小时，在一台有3.2G{{what|中央内存}}的Cray C916计算机上完成。<ref>{{Cite web |url=http://lukenotricks.blogspot.se/2009/08/solo-desktop-factorization-of-rsa-512.html |title=存档副本 |accessdate=2018-04-09 |archive-date=2017-07-01 |archive-url=https://web.archive.org/web/20170701081906/http://lukenotricks.blogspot.se/2009/08/solo-desktop-factorization-of-rsa-512.html |dead-url=yes }}{{需要更好来源}}</ref>

RSA-155表示如下：
 39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
 727842468219535093544305870490251995655335710209799226484977949442955603
 
 = 3388495837466721394368393204672181522815830368604993048084925840555281177×
   11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解<ref>{{cite web |url= http://eprint.iacr.org/2010/006.pdf |title= Factorization of a 768-bit RSA modulus |date= 2010年1月7日 |accessdate= 2010年1月10日 |archive-date= 2010年3月31日 |archive-url= https://web.archive.org/web/20100331141639/http://eprint.iacr.org/2010/006.pdf |dead-url= yes }}</ref>。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：
 123018668453011775513049495838496272077285356959533479219732245215172640050726
 365751874520219978646938995647494277406384592519255732630345373154826850791702
 6122142913461670429214311602221240479274737794080665351419597459856902143413
 
 = 3347807169895689878604416984821269081770479498371376856891
   2431388982883793878002287614711652531743087737814467999489×
   3674604366679959042824463379962795263227915816434308764267
   6032283815739666511279233373417143396810270092798736308917

=== 时间攻击 ===
1995年，[[丹·博內]]和{{link-en|大衛·布魯姆利|David Brumley}}提出了一种出人意料的攻击方式：假如[[愛麗絲與鮑伯|Eve]]（竊密者）对[[愛麗絲與鮑伯|Alice]]的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出''d''。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的，而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。<ref>[http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf Remote timing attacks are practical. ] {{Wayback|url=http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf |date=20110728122336 }}. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.</ref>

== 相關條目 ==
* [[公开密钥加密]]
* [[橢圓曲線密碼學]]
* [[量子電腦]]
* [[秀爾演算法]]
* [[米勒-拉宾检验|米勒-拉賓質數判定法]]
* [[迪菲-赫爾曼密鑰交換]]
* [[模幂]]
* [[快速幂]]
* [[扩展欧几里得算法]]

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
* [http://www.rsasecurity.com RSA, The Security Division of EMC]{{Wayback|url=http://www.rsasecurity.com/ |date=20090106053636 }}
* [http://www.guideep.com/read?guide=5676830073815040 RSA算法详解]{{Wayback|url=http://www.guideep.com/read?guide=5676830073815040 |date=20160408120553 }}

{{密碼學|public-key}}

[[Category:非对称密钥算法]]
[[Category:数字签名方案]]