RSA加密算法

2018-07-27 10:04:08 所属分类：算法

RSA的作者之一：阿迪·萨莫尔（Adi Shamir）

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

1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。^[2]

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

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

操作

公钥与私钥的产生

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

随意选择两个大的质数 ${displaystyle p}$ 和 ${displaystyle q}$ ， ${displaystyle p}$ 不等于 ${displaystyle q}$ ，计算 ${displaystyle N=pq}$ 。
根据欧拉函数，求得 ${displaystyle r=varphi (N)=varphi (p)varphi (q)=(p-1)(q-1)}$
选择一个小于 ${displaystyle r}$ 的整数 ${displaystyle e}$ ，使 ${displaystyle e}$ 与 ${displaystyle r}$ 互质。并求得 ${displaystyle e}$ 关于 ${displaystyle r}$ 的模反元素，命名为 ${displaystyle d}$ （求 ${displaystyle d}$ 令 ${displaystyle edequiv 1{pmod {r}}}$ ）。（模反元素存在，当且仅当 ${displaystyle e}$ 与 ${displaystyle r}$ 互质）
将 ${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 cequiv n^{e}{pmod {N}}}

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

解密消息

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

{displaystyle nequiv c^{d} (mathrm {mod} N)}

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

解码的原理是

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

已知 ${displaystyle edequiv 1{pmod {r}}}$ ，即 ${displaystyle ed=1+hvarphi (N)}$ 。由欧拉定理得：

{displaystyle n^{ed}=n^{1+hvarphi (N)}=nleft(n^{varphi (N)}right)^{h}equiv n(1)^{h}{pmod {N}}equiv n{pmod {N}}}

签名消息

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

安全

假设偷听者乙获得了甲的公钥 ${displaystyle N}$ 和 ${displaystyle e}$ 以及丙的加密消息 ${displaystyle c}$ ，但她无法直接获得甲的密钥 ${displaystyle d}$ 。要获得 ${displaystyle d}$ ，最简单的方法是将 ${displaystyle N}$ 分解为 ${displaystyle p}$ 和 ${displaystyle q}$ ，这样她可以得到同余方程 ${displaystyle de=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年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰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}$ 永远不应该被使用。

速度

比起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的运算要多很多，因此若能得到多组消息与其加密时间，就会有机会可以反推出私钥的内容。^[8]

典型密钥长度

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

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

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

RSA-158表示如下：

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

参考文献

^ Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20.
^ Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 20 November 1973 [2017-05-30].
^ Cryptographic communications system and method, 1977-12-14 [2018-04-09]
^ RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始内容存档于June 21, 2007）.
^ Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5).
^ Tromer, Eran. TWIRL (The Weizmann Institute Relation Locator). cs.tau.ac.il. [2018-04-16].
^ Has the RSA algorithm been compromised as a result of Bernstein's Paper? What key size should I be using?
^ Remote timing attacks are practical. . SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.
^ http://lukenotricks.blogspot.se/2009/08/solo-desktop-factorization-of-rsa-512.html
^ Factorization of a 768-bit RSA modulus (PDF). 2010年1月7日 [2010年1月10日].

外部链接

RSA, The Security Division of EMC
RSA算法详解

公开密钥加密

算法

整数分解	Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa

离散对数	Cramer–Shoup DH DSA ECDH ECDSA EdDSA EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS SM2

其他	AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern Naccache–Stern knapsack cryptosystem NTRUEncrypt NTRUSign Three-pass protocol XTR

理论

离散对数
椭圆曲线密码学
Non-commutative cryptography
RSA problem

标准化

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B

论题

数字签名
OAEP
密钥指纹
PKI
Web of trust
Key size
Post-quantum cryptography

密码学

密码学历史密码分析密码体制密码学主题列表

对称密钥加密分组密码流加密公开密钥加密密码散列函数消息认证码随机数隐写术

语义安全完善保密性信息论安全性

分类主题专题