RSA加密演算法查看源代码讨论查看历史
 |
RSA加密演算法是一种非对称加密演算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。
對极大整数做因数分解[1] 的难度決定了 RSA 算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的:信息:訊息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的-信息:訊息实际上是不能被破解的。
1983年9月12日麻省理工学院在美国为RSA算法申请了专利。这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被發表了，在世界上大多数其它地区这个专利权不被承认。
正确性证明
首选取两个互质数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公钥为(e,n),私钥为(d,n)。
加密原文x得到密文
- m = x^e \% n
解密公式为
- x = m^d \% n
证明解密逻辑：
证明 x = m^d \% n ，就是证明 m^d \% n - x = 0
m^d%n-x //如何=0，往下分解：
=(x^e%n)^d%n-x //代入加密原文
=x^ed%n-x //根据模运算公式：a ^ b % p = ((a % p)^b) % p
=x^(k(p-1)(q-1)+1)%n-x //代入ed的值
=x*(x^(k(p-1)(q-1))-1)%n //x挪到括号外，条件x<n
根据费马小定理公式：a^(p-1) - 1可以被p整除。 所以x^(k(q-1))^(p-1) - 1 可以被p整除，x^(k(p-1))^(q-1) - 1 可以被q整除。 所以x^(k(p-1)(q-1)) - 1 可以被pq整除，也就是可以被N整除。 就是x*(x^(k(p-1)(q-1))-1)%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年彼得·秀爾（Peter Shor）证明一台量子计算机可以在多項式時間内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀爾的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）
假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。
签名消息
RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值（Message digest），然后用她的私钥“加密”（如同前面“加密消息”的步骤）这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”（如同前面“解密消息”的步骤）这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那麼Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。