智能家居
标题: 一位大佬用25行代码实现完整的RSA算法 [打印本页]
作者: 邢远 时间: 2018-4-10 17:34
标题: 一位大佬用25行代码实现完整的RSA算法
引言RSA算法的步骤主要有以下几个步骤：
选择 p、q两个超级大的质数
令n = p * q。取 φ(n) =(p-1) * (q-1)。
取 e ∈ 1 < e < φ(n) ，( n , e )为公钥对
令 ed mod φ(n) = 1，取得d，( n , d ) 为私钥对。 利用扩展欧几里的算法进行计算。
销毁 p、q。密文 = 明文 ^ e mod n ， 明文 = 密文 ^ d mod n。利用蒙哥马利方法进行计算
前方高能，我要开始装逼了。看不懂的童鞋请绕道，先去看看理论，具体内容如下：
计算最大公约数与扩展欧几里得算法大整数幂取模算法公钥私钥生成rsa.py，生成公钥、私钥、并对信息加密解密。
实测：秘钥长度在2048位的时候，我的thinkpad笔记本T440上面、python2.7环境的运行时间是4秒，1024位的时候是1秒。说明了RSA加密算法的算法复杂度应该是O（N^2），其中n是秘钥长度。不知道能不能优化到O（NlogN）
| 欢迎光临 智能家居 (https://bbs.mywll.com/) |
Powered by Discuz! X3.4 |