一位大佬用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）
页:
[1]