RSA加密算法

RSA
概述
设计者	罗纳德·李维斯特; 阿迪·萨莫尔; 伦纳德·阿德曼
首次发布	1977
认证	PKCS#1, ANSI X9.31, IEEE 1363
密码细节
密钥长度	2048 - 4096 位（常规情况）
重复回数	1
最佳公开破解
	传统计算机：普通数域筛选法; 量子计算机：秀尔算法; RSA-250（829位）已经被攻破

RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。^[1]

1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。^[2]

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

1983年9月12日麻省理工学院在美国为RSA算法申请了专利。^[3]这个专利于2000年9月21日失效。^[4]由于该算法在申请专利前就已经被发表了^[5]，在世界上大多数其它地区这个专利权不被承认。

操作

公钥与私钥的产生

假设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)$ 互质。接着我们计算 $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<N$ 的状况下证明 $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)$

假设q整除m。因此 $q\mid ph_{1}$ ，因为q与p互素，根据欧几里德引理， $q\mid h_{1}$ 。所以 $q\leq h_{1}$ ，而这与 $h_{1}<q$ 矛盾，所以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_{1}*qh_{2}\%N=Nh_{1}h_{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^[6]，使人们开始质疑1024位长的N的安全性，目前推荐 $N$ 的长度至少为2048位。^[7]

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

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

实现细节

密钥生成

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

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

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

此外密钥 $d$ 必须足够大，1990年有人证明假如 $p$ 大于 $q$ 而小于 $2q$ （这是一个很常见的情况）而 $d<{\frac {1}{3}}\times N^{\frac {1}{4}}$ ，那么从 $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位^[8]。实现上，强制设置密钥长度为2048位的称RSA或RSA2(意即RSA version 2)，而未强制设置的称RSA1以资区别，两者差异主要在密钥长度。

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

大数因数分解

最常见的针对RSA的攻击是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花费五个月时间（约8000 MIPS年）、224 CPU小时，在一台有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]

参考文献

^ Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20. （原始内容 (PDF)存档于2016-12-13）.
^ Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 1973-11-20 [2017-05-30]. （原始内容存档 (PDF)于2017-02-16）.
^ Cryptographic communications system and method, 1977-12-14 [2018-04-09], （原始内容存档于2019-02-17）
^ RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始内容存档于2007-06-21）.
^ Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5) [2018-04-09]. （原始内容 (PDF)存档于2017-01-16）.
^ Tromer, Eran. TWIRL (The Weizmann Institute Relation Locator). cs.tau.ac.il. [2018-04-16]. （原始内容存档于2018-04-20）.
^ Has the RSA algorithm been compromised as a result of Bernstein's Paper? （页面存档备份，存于互联网档案馆） What key size should I be using?
^ Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-22]. （原始内容存档于2020-04-04）.
^ 存档副本. [2018-04-09]. （原始内容存档于2017-07-01）. ^{[需要较佳来源]}
^ Factorization of a 768-bit RSA modulus (PDF). 2010年1月7日 [2010年1月10日]. （原始内容 (PDF)存档于2010年3月31日）.
^ Remote timing attacks are practical. （页面存档备份，存于互联网档案馆）. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.

外部链接

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

[1] Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20. （原始内容 (PDF)存档于2016-12-13）.

[2] Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 1973-11-20 [2017-05-30]. （原始内容存档 (PDF)于2017-02-16）.

[3] Cryptographic communications system and method, 1977-12-14 [2018-04-09], （原始内容存档于2019-02-17）

[4] RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始内容存档于2007-06-21）.

[SIAM-5] Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5) [2018-04-09]. （原始内容 (PDF)存档于2017-01-16）.

[6] Tromer, Eran. TWIRL (The Weizmann Institute Relation Locator). cs.tau.ac.il. [2018-04-16]. （原始内容存档于2018-04-20）.

[7] Has the RSA algorithm been compromised as a result of Bernstein's Paper? （页面存档备份，存于互联网档案馆） What key size should I be using?

[8] Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-22]. （原始内容存档于2020-04-04）.

[9] 存档副本. [2018-04-09]. （原始内容存档于2017-07-01）. ^{[需要较佳来源]}

[10] Factorization of a 768-bit RSA modulus (PDF). 2010年1月7日 [2010年1月10日]. （原始内容 (PDF)存档于2010年3月31日）.

[11] Remote timing attacks are practical. （页面存档备份，存于互联网档案馆）. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]