RSA加密算法1.docVIP

Unicode（统一码、万国码、单一码、标准万国码） RSA加密演算法 维基百科，自由的百科全书 跳转到： 导航, 有哪些信誉好的足球投注网站 RSA加密演算法是一种非对称加密演算法。在公钥加密标准和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相应的算法，但他的发现被列入机密，一直到1997年才被發表。 對极大整数做因数分解的难度決定了RSA算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算技术和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 1983年麻省理工学院在美国为RSA算法申请了专利。这个专利2000年9月21日失效。由于该算法在申请专利前就已经被發表了，在世界上大多数其它地区这个专利权不被承认。 操作 公鑰和私鑰的產生 假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰： 隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。 根據歐拉函數，不大於N且與N互質的整數個數為(p-1)(q-1) 選擇一個整數e與(p-1)(q-1)互質，並且e小於(p-1)(q-1) 用以下這個公式計算d：d× e ≡ 1 (mod (p-1)(q-1)) 將p和q的記錄銷毀。 (N,e)是公鑰，(N,d)是私鑰。(N,d)是秘密的。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。 加密消息 假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c： 计算c并不复杂。Bob算出c后就可以将它传递给Alice。 解密消息 Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n： 得到n后，她可以将原来的信息m重新复原。 解码的原理是 以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由费马小定理可证明（因为p和q是质数） ??? 和 ??? 这说明（因为p和q是不同的质数，所以p和q互质） 签名消息 RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message diget)，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。 安全 假设偷听者乙获得了甲的公钥N和e以及丙的加密消息c，但她无法直接获得甲的密钥d。要获得d，最简单的方法是将N分解为p和q，这样她可以得到同余方程d× e ≡ 1 (mod (p-1)(q-1))并解出d，然后代入解密公式 导出n（破密）。但至今为止还没有人找到一个多項式時間的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。 至今为止也没有人能够证明对N进行因数分解是唯一的从c导出n的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。） 因此今天一般认为只要N足够大，那么駭客就没有办法了。 假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N。今天对N的要求是它至少要1024位长。 1994年彼得·秀爾（Peter Shor）证明一台量子计算机可以在多項式時間内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀爾的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法） 假如有人能够找到