一位大佬用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）