RSA加密演算法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

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

操作[编辑]

公钥与私钥的产生[编辑]

假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰

  1. 隨意選擇兩個大的質數pqp不等於q,計算N=pq
  2. 根據歐拉函數,求得r=\varphi(N) = \varphi(p)\varphi(q)=(p-1)(q-1)
  3. 選擇一個小于r的整數e,求得e关于r模反元素,命名为d。(模反元素存在,当且仅当er互质)
  4. pq的記錄銷毀。

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

加密消息[编辑]

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

 n^e \equiv c\ (\mathrm{mod}\ N)

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

解密消息[编辑]

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

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

得到n后,她可以将原来的信息m重新复原。

解码的原理是

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

以及ed = 1 (\mathrm{mod} p-1)ed = 1 (\mathrm{mod} q-1)。由欧拉定理可证明(因为pq是质数)

 n^{e \cdot d} \equiv n\ (\mathrm{mod}\ p)     和      n^{e \cdot d} \equiv n\ (\mathrm{mod}\ q)

这说明(因为pq不同的质数,所以pq互质)

 n^{e \cdot d} \equiv n\ (\mathrm{mod}\ pq)

签名消息[编辑]

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

安全[编辑]

假设偷听者乙获得了甲的公钥Ne以及丙的加密消息c,但她无法直接获得甲的密钥d。要获得d,最简单的方法是将N分解为pq,这样她可以得到同余方程de=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。今天对N的要求是它至少要1024位长。

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

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

实现细节[编辑]

密钥生成[编辑]

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

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

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

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

速度[编辑]

比起DES和其它对称算法来說,RSA要慢得多。实际上Bob一般使用一种对称算法来加密他的信息,然后用RSA来加密他的比较短的对称密码,然后将用RSA加密的对称密码和用对称算法加密的消息送给Alice。

这样一来对随机数的要求就更高了,尤其对产生对称密码的要求非常高,因为否则的话可以越过RSA来直接攻击对称密码。

密钥分配[编辑]

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

时间攻击[编辑]

1995年有人提出了一种非常意想不到的攻击方式:假如Eve对Alice的硬件有充分的了解,而且知道它对一些特定的消息加密时所需要的时间的话,那么她可以很快地推导出d。這種攻擊方式之所以會成立,主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的,而位元為1所花的運算比位元為0的運算要多很多,因此若能得到多組訊息與其加密時間,就會有機會可以反推出私鑰的內容。

典型密钥长度[编辑]

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

已公开的或已知的攻击方法[编辑]

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

2002年,RSA-158也被成功因数分解。

RSA-158表示如下:

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

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

RSA-768表示如下:

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

相關條目[编辑]

参考文献[编辑]

  1. ^ Factorization of a 768-bit RSA modulus. 2010年1月7日 [2010年1月10日]. 
  uhyyrtyjuky

外部链接[编辑]