2022年RSA加密算法 .pdf

RSA 加密算法该算法于 1977 年由美国麻省理工学院mit(massachusetts institute of technology)的 ronal rivest ，adi shamir和 len adleman三位年轻教授提出，并以三人的姓氏rivest ， shamir 和adlernan 命名为 rsa 算法。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。与diffie-hellman算法相比， rsa 算法具有明显的优越性，因为它无须收发双方同时参与加密过程，且非常适合于电子函件系统的加密。rsa 算法可以表述如下：(1) 密钥配制。假设m 是想要传送的报文，现任选两个很大的质数p 与 q，使得：(12-1) ；选择正整数e，使得 e 与(p 1)(q 1)互质；这里 (p1)(q 1)表示二者相乘。再利用辗转相除法，求得d，使得：(12-2) ；其中 x mod y 是整数求余运算，其结果是x 整除以 y 后剩余的余数，如5 mod 3 = 2 。这样得：(e，n)，是用于加密的公共密钥，可以公开出去；以及(d，n)，是用于解密的专用钥匙，必须保密。(2) 加密过程。使用(e，n)对明文 m 进行加密，算法为：(12-3) ；这里的 c 即是 m 加密后的密文。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - (3) 解密过程。使用(d，n)对密文 c 进行解密，算法为：(12-4) ；求得的 m 即为对应于密文c 的明文。rsa 算法实现起来十分简捷，据说英国的一位程序员只用了3 行 perl 程序便实现了加密和解密运算。rsa 算法建立在正整数求余运算基础之上，同时还保持了指数运算的性质，这一点我们不难证明。例如：(12-5) ；(12-6) 。rsa 公共密钥加密算法的核心是欧拉(euler) 函数 。对于正整数n，(n)定义为小于n且与 n 互质的正整数的个数。例如(6) = 2，这是因为小于6 且与 6 互质的数有1 和 5 共两个数；再如(7) = 6，这是因为互质数有1，2，3， 5，6 共 6 个。欧拉在公元前300 多年就发现了函数的一个十分有趣的性质，那就是对于任意小于n 且与 n 互质的正整数m， 总有 m (n) mod n = 1 。 例如，5(6) mod 6 = 52 mod 6= 25 mod 6 =1 。也就是说，在对n 求余的运算下，(n) 指数具有周期性。当 n 很小时，计算(n)并不难，使用穷举法即可求出；但当n 很大时，计算(n)就十分困难了，其运算量与判断n 是否为质数的情况相当。不过在特殊情况下，利用函数的两个性质，可以极大地减少运算量。性质 1：如果 p 是质数，则(p) = (p 1)。性质 2：如果 p 与 q 均为质数，则(pq) = (p) (q) = (p1)(q 1)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - rsa 算法正是注意到这两条性质来设计公共密钥加密系统的，p 与 q 的乘积 n 可以作为公共密钥公布出来，而n 的因子 p 和 q 则包含在专用密钥中，可以用来解密。如果解密需要用到 (n)，收信方由于知道因子p 和 q，可以方便地算出(n) = (p1)(q 1)。如果窃听者窃得了n，但由于不知道它的因子p 与 q，则很难求出(n)。这时，窃听者要么强行算出(n)，要么对 n 进行因数分解求得p 与 q。然而，我们知道，在大数范围内作合数分解是十分困难的，因此窃密者很难成功。有了关于 函数的认识，我们再来分析rsa 算法的工作原理：(1) 密钥配制。设m 是要加密的信息，任选两个大质数p 与 q，使得 ；选择正整数e，使得 e 与 (n) = (p 1)(q 1)互质。利用辗转相除法，计算d，使得 ed mod (n) = ，即 ed = k (n) +1，其中 k 为某一正整数。公共密钥为 (e，n)，其中没有包含任何有关n 的因子 p 和 q 的信息。专用密钥为 (d，n)，其中 d 隐含有因子p 和 q 的信息。(2) 加密过程。使用公式(12-3) 对明文 m 进行加密，得密文c。(3) 解密过程。使用(d，n)对密文 c 进行解密，计算过程为：cd mod n = (me mod n)d mod n = med mod n = m(k (n) + 1) mod n= (mk (n) mod n)(m mod n) = m 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - m 即为从密文c 中恢复出来的明文。例如，假设我们需要加密的明文代码信息为m = 14 ，则：选择 e = 3 ，p = 5 ，q = 11 ；计算出 n = p q = 55 ，(p1)(q 1) = 40 ，d = 27 ；可以验证： (ed) mod (p 1)(q 1) = 81 mod 40 = 1；加密： c = me mod n = 143 mod 55 = 49；解密： m = cd mod n = 4927 mod 55 = 14。关于 rsa 算法，还有几点需要进一步说明：(1) 之所以要求e 与(p1)(q 1)互质，是为了保证ed mod (p 1)(q 1)有解。(2) 实际操作时，通常先选定e，再找出并确定质数p 和 q，使得计算出d 后它们能满足公式 (12-3) 。常用的e 有 3 和 65537 ，这两个数都是费马序列中的数。费马序列是以17世纪法国数学家费马命名的序列。(3) 破密者主要通过将n 分解成 p q 的办法来解密， 不过目前还没有办法证明这是唯一的办法，也可能有更有效的方法，因为因数分解问题毕竟是一个不断发展的领域，自从rsa算法发明以来， 人们已经发现了不少有效的因数分解方法，在一定程度上降低了破译rsa 算法的难度，但至今还没有出现动摇rsa 算法根基的方法。(4) 在 rsa 算法中， n 的长度是控制该算法可靠性的重要因素。目前129 位、甚至 155位的 rsa 加密勉强可解，但目前大多数加密程序均采用231、308 甚至 616 位的 rsa 算法，因此 rsa 加密还是相当安全的。据专家测算，攻破512 位密钥 rsa 算法大约需要8 个月时间；而一个768 位密钥 rsa算法在 2004 年之前无法攻破。现在，在技术上还无法预测攻破具有2048 位密钥的 rsa 加名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 密算法需要多少时间。美国lotus 公司悬赏1 亿美元，奖励能破译其domino 产品中 1024位密钥的rsa 算法的人。 从这个意义上说， 遵照 set 协议开发的电子商务系统是绝对安全的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -