未来索引
开启左侧

一位大佬用25行代码实现完整的RSA算法

[复制链接]
邢远 发表于 2018-4-10 17:34:41 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
一位大佬用25行代码实现完整的RSA算法
引言
一位大佬用25行代码实现完整的RSA算法
一位大佬用25行代码实现完整的RSA算法
一位大佬用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。利用蒙哥马利方法进行计算

一位大佬用25行代码实现完整的RSA算法
前方高能,我要开始装逼了。看不懂的童鞋请绕道,先去看看理论,具体内容如下:

  • 计算最大公约数

  • 超大整数的超大整数次幂取超大整数模算法(好拗口,哈哈,不拗口一点就显示不出这个算法的超级牛逼之处)

  • 公钥私钥生成

计算最大公约数与扩展欧几里得算法
一位大佬用25行代码实现完整的RSA算法
一位大佬用25行代码实现完整的RSA算法
大整数幂取模算法
一位大佬用25行代码实现完整的RSA算法
一位大佬用25行代码实现完整的RSA算法
一位大佬用25行代码实现完整的RSA算法
公钥私钥生成
rsa.py,生成公钥、私钥、并对信息加密解密。
一位大佬用25行代码实现完整的RSA算法
一位大佬用25行代码实现完整的RSA算法
实测:秘钥长度在2048位的时候,我的thinkpad笔记本T440上面、python2.7环境的运行时间是4秒,1024位的时候是1秒。说明了RSA加密算法的算法复杂度应该是O(N^2),其中n是秘钥长度。不知道能不能优化到O(NlogN)

该会员没有填写今日想说内容.
高级模式
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关注2973

粉丝2842

帖子9204

发布主题
阅读排行 更多
广告位
!jz_fbzt! !jz_sgzt! !jz_xgzt! 快速回复 !jz_sctz! !jz_fhlb! 搜索

智能技术共享平台 - 未来论

关注服务号

进入小程序

全国服务中心:

运维中心:天津

未来之家:天津 青岛 济南 郑州 石家庄

                商务邮箱:xy@mywll.com

Copyright © 2012-2019 未来派 未来论 (津ICP备16000236号-5)