RSA加密演算法 -{H|zh-cn:重定向;zh-tw:重新导向;}- RSA加密演算法是一种非对称加密演算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。 1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。 对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的-{zh-hans:信息;zh-tw:讯息}-的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到2020年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的-{zh-hans:信息;zh-tw:讯息}-实际上是不能被破解的。 1983年9月12日麻省理工学院在美国为RSA算法申请了专利。这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。 操作. 公钥与私钥的产生. 假设Alice想要通过不可靠的媒体接收Bob的私人讯息。她可以用以下的方式来产生一个公钥和一个私钥： formula_20是公钥，formula_21是私钥。Alice将她的公钥formula_20传给Bob，而将她的私钥formula_21藏起来。 加密消息. 假设Bob想给Alice送消息formula_24，他知道Alice产生的formula_25和formula_8。他使用起先与Alice约好的格式将formula_24转换为一个小于formula_25的非负整数formula_29，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为formula_29。用下面这个公式他可以将formula_29加密为formula_32： formula_33 这里的 formula_32 可以用模幂算法快速求出来。Bob算出formula_32后就可以将它传递给Alice。 解密消息. Alice得到Bob的消息formula_32后就可以利用她的密钥formula_13来解码。她可以用以下这个公式来将formula_32转换为formula_29： formula_40 与 Bob 计算 formula_32 类似，这里的 formula_29 也可以用模幂算法快速求出。得到formula_29后，她可以将原来的信息formula_24重新复原。 解码的原理是 formula_45 已知formula_15，即 formula_47。那么有 formula_48 若formula_49与formula_50互质，则由欧拉定理得： formula_51 若formula_49与formula_50不互质，则不失一般性考虑formula_54，以及formula_55，得： formula_56 formula_57 故 formula_58 得证。 签名消息. RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值（Message digest），然后用她的私钥“加密”（如同前面“加密消息”的步骤）这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”（如同前面“解密消息”的步骤）这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。 正确性证明. 首选取两个互质数formula_1和formula_2, 乘法计算formula_61得到formula_25。 然后计算出欧拉formula_63： formula_64函数formula_63是小于或等于formula_25的正整数中与formula_25互质的数的数目。 根据欧拉公式，由于formula_1和formula_2都是质数，故 formula_70 这时候我们随机选择一个整数formula_8，条件是formula_72，且formula_8与formula_74 互质。 接着我们计算formula_8对formula_74的模逆元得到formula_13： formula_78 这个公式简单的说就是 formula_79除以formula_74得到的余数为1，这个公式可以转换成 formula_81 即 formula_82 于是，RSA公钥为formula_20,私钥为formula_21。 加密原文formula_24得到密文 formula_86 解密公式为 formula_87 证明解密逻辑： 在 formula_88 的状况下证明formula_87，就是证明formula_90 formula_91 formula_92 formula_93 formula_94 formula_95 当m与N互质时，根据费马小定理公式 formula_96 formula_97 formula_98 formula_99 formula_100 formula_101 当m与N不互质时，不妨设公因子为p，即formula_102 假设q整除m。因此formula_103，因为q与p互质，根据欧几里德引理，formula_104。所以formula_105，而这与formula_106矛盾，所以q不整除m。 此时m与q互质，根据费马小定理公式 formula_96 formula_108 formula_109 formula_110 formula_111,证明完成。 安全性. 假设偷听者Eve获得了Alice的公钥formula_25和formula_8以及Bob的加密消息formula_32，但她无法直接获得Alice的密钥formula_13。要获得formula_13，最简单的方法是将formula_25分解为formula_1和formula_2，这样她可以得到同余方程formula_120并解出formula_13，然后代入解密公式 formula_122 导出"n"（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。 至今为止也没有人能够证明对formula_25进行因数分解是唯一的从formula_32导出formula_29的方法，直到今天也还没有找到比它更简单的方法。（至少没有公开的方法。） 因此今天一般认为只要formula_25足够大，那么骇客就没有办法了。 假如formula_25的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的formula_25。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL，使人们开始质疑1024位长的N的安全性，目前推荐formula_25的长度至少为2048位。 1994年，彼得·秀尔证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法） 假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。 实现细节. 密钥生成. 首先要使用概率算法来验证随机产生的大的整数是否质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。 除此之外这样找到的formula_1和formula_2还要满足一定的要求，首先它们不能太靠近，此外formula_132或formula_133的因子不能太小，否则的话formula_25也可以被很快地分解。 此外寻找质数的算法不能给攻击者任何信息，这些质数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出formula_1和formula_2一半的位的话，那么他们就已经可以轻而易举地推算出另一半。 此外密钥formula_13必须足够大，1990年有人证明假如formula_1大于formula_2而小于formula_140（这是一个很常见的情况）而formula_141，那么从formula_25和formula_8可以很有效地推算出formula_13。此外formula_145永远不应该被使用。 速度. 比起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位元。实作上，强制设置金钥长度为2048位元的称RSA或RSA2(意即RSA version 2)，而未强制设定的称RSA1以资区别，两者差异主要在金钥长度。 已公开的或已知的攻击方法. 大数因数分解. 最常见的针对RSA的攻击是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花费五个月时间（约8000 MIPS年）、224 CPU小时，在一台有3.2G的Cray C916计算机上完成。 RSA-155表示如下： 39505874583265144526419767800614481996020776460304936454139376051579355626529450683609 727842468219535093544305870490251995655335710209799226484977949442955603 = 3388495837466721394368393204672181522815830368604993048084925840555281177× 11658823406671259903148376558383270818131012258146392600439520994131344334162924536139 2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。 RSA-768表示如下： 123018668453011775513049495838496272077285356959533479219732245215172640050726 365751874520219978646938995647494277406384592519255732630345373154826850791702 6122142913461670429214311602221240479274737794080665351419597459856902143413 = 3347807169895689878604416984821269081770479498371376856891 2431388982883793878002287614711652531743087737814467999489× 3674604366679959042824463379962795263227915816434308764267 6032283815739666511279233373417143396810270092798736308917 时间攻击. 1995年，和提出了一种出人意料的攻击方式：假如Eve（窃密者）对Alice的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出"d"。这种攻击方式之所以会成立，主要是因为在进行加密时所进行的模指数运算是一个位元一个位元进行的，而位元为1所花的运算比位元为0的运算要多很多，因此若能得到多组讯息与其加密时间，就会有机会可以反推出私钥的内容。