首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    25行代码实现完整的RSA算法

    python3.X版本的请点击这里25行代码实现完整的RSA算法   网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱、让人信服的算法代码实现,即使有代码介绍,也都是直接调用JDK或者Python代码包中的API实现,也有可能并没有把核心放在原理的实现上,而是字符串转数字啦、或者数字转字符串啦、或者即使有代码也都写得特别烂。无形中让人感觉RSA加密算法竟然这么高深,然后就看不下去了。看到了这样的代码我就特别生气,四个字:误人子弟。还有我发现对于“大整数的幂次乘方取模”竟然采用直接计算的幂次的值,再取模,类似于(2 ^ 1024) ^ (2 ^ 1024),这样的计算就直接去计算了,我不知道各位博主有没有运行他们的代码???知道这个数字有多大吗?这么说吧,把全宇宙中的物质都做成硬盘都放不下,更何况你的512M内存的电脑。所以我说他们的代码只可远观而不可亵玩已。   于是我用了2天时间,没有去参考网上的代码重新开始把RSA算法的代码完全实现了一遍以后发现代码竟然这么少,基本上25行就全部搞定。为了方便整数的计算,我使用了Python语言。为什么用Python?因为Python在数值计算上比较直观,即使没有学习过python的人,也能一眼就看懂了代码。而Java语言需要用到BigInteger类,数值的计算都是用方法调用,所以使用起来比较麻烦。如果有同学对我得代码感兴趣的话,先二话不说,不管3X7=22,把代码粘贴进pydev中运行一遍,是驴是马拉出来溜溜。看不懂可以私信我,我就把代码具体讲讲,如果本文章没有人感兴趣,我就不做讲解了。 RSA算法的步骤主要有以下几个步骤:     1、选择 p、q两个超级大的质数 ,都是1024位,显得咱们的程序货真价实。     2、令n = p * q。取 φ(n) =(p-1) * (q-1)。 计算与n互质的整数的个数。     3、取 e ∈ 1 < e < φ(n) ,( n , e )作为公钥对,正式环境中取65537。可以打开任意一个被认证过的https证书,都可以看到。     4、令 ed mod φ(n) = 1,计算d,( n , d ) 作为私钥对。 计算d可以利用扩展欧几里的算法进行计算,非常简单,不超过5行代码就搞定。     5、销毁 p、q。密文 = 明文 ^ e mod n , 明文 = 密文 ^ d mod n。利用蒙哥马利方法进行计算,也叫反复平方法,非常简单,不超过10行代码搞定。     实测:秘钥长度在2048位的时候,我的thinkpad笔记本T440上面、python2.7环境的运行时间是0.035秒,1024位的时候是0.008秒。说明了RSA加密算法的算法复杂度应该是O(N^2),其中n是秘钥长度。不知道能不能优化到O(NlogN)   代码主要涉及到三个Python可执行文件:计算最大公约数、大整数幂取模算法、公钥私钥生成及加解密。这三个文件构成了RSA算法的核心。   这个时候很多同学就不干了,说为什么我在网上看到的很多RSA理论都特别多,都分很多个章节,在每个章节中,都有好多个屏幕才能显示完,这么多的理论,想想怎么也得上千行代码才能实现,怎么到了你这里25行就搞定了呢?北门大官人你不会是在糊弄我们把?其实真的没有,我是良心博主,绝对不会糊弄大家,你们看到的理论确实这么多,我也都看过了,我把这些理论用了zip,gzip,hafuman,tar,rar等很多的压缩算法一遍遍地进行压缩,才有了这个微缩版的rsa代码实现,代码虽少,五脏俱全,是你居家旅行,课程设计、忽悠小白、必备良药。其实里边的几乎每一行代码都能写一篇博客专门进行介绍。   前方高能,我要开始装逼了。看不懂的童鞋请绕道,先去看看理论,具体内容如下:   1. 计算最大公约数   2. 超大整数的超大整数次幂取超大整数模算法(好拗口,哈哈,不拗口一点就显示不出这个算法的超级牛逼之处)   3. 公钥私钥生成

    02

    Python学习笔记整理(二)pytho

    一、Python的数字类型 1、数字常量 python数字类型在程序中如何显示(换句话说,作为常量) 数字            常量 1234,-23,0        一般整数 99999999999L        长整型数(无限大小) 1.23,3,14e-10,4E210    浮点数 0177,0x9ff,0xFF        整数的八进制和十六进制数常量 3+4j,2.0+3.0,3J        复数常量 一般来说,python的数字类型是直接的。有些编程的概念强调如下 整数和浮点数常量: 整数以十进制数字的字符串写法出现。浮点数带一个小数点,也可以加上一个科学计数标志e或E。如果编写一个带有小数点或幂的数字,Python会将它变成一个浮点数对象,并且当这个对象用在表达式中时,将启用浮点数(而不是整数)的运算法则。 长整型数常量 如果整数常量以l或L结尾,那么它就变成了Python长整型数,而且可以任意增大。python2.2和之后版本中,因为当一个整数的值操作32位时,它会自动变换为长整数型,不要着自己输入字母L。当有额外的精度需求时,Python会自动将其升级为长整数型数。 十六进制和八进制数常量 八进制常量以数字0开头,后面接数字0-7构成的字符串。十六进制数常量以0x或0X开头,后面接十六进制数字0-9和A-F。十六进制数字编写成。大小写都可以。八进制数和十六进制数常量都会产生一个整数对象,他们仅仅是特定值不同语法标识而已。 复数 python的复数常量写成实部+虚部的写法,这里虚部都是以j或者J结尾。其中,实部从技术上讲课有可无,所以可以能会单独标识虚部。从内部看来,复数都是通过一对浮点数来标识。但是对复数的所有的数字操作都会按照复数的运算法则进行。 2、内置数据工具扩展 Python处理数字对象的工具 表达式操作符 +、-、*、/、%(计算余数操作符)、**(幂运算),<<左位移,&计算位与的结果 内置数学函数 pow,abs #>> help(pow) 公用模块 random 随机数 math数学模块 名位NumPy的Python扩展提供了高级的数值编程工具。 二、Python表达式操作 表达式是处理数字的最基本工具,当一个数字(或其他对象)与操作符相结合时,Python执行时将计算得到一个值。在Python中表达式是使用通常的数学符号和操作符号写出来。is操作符测试对象身份(也就是内存地址,严格意义上的相等)。lambda创建匿名函数 更多python表达式操作符及程序可以搜索 1、混合操作所遵循的操作符优先级 遵守一般的数学计算规范,先乘除后加减。 书中5.2表的操作符中越靠后优先级越高。 2、括号分组的子表达式 有括号将表达式分组,先计算括号里的表达式,然后再将结果用于整个表达式 3、混合类型自动升级 除了在表达式中混合操作符外,也能混合数字的类型。整数和浮点 20+1.4 最后结果的类型为复杂的数字类型 三、在实际应用中的数字 1、变量和基本表达式 在python中,变量并不需要预算声明。但是在使用之前,至少要被赋值一次值。 2、str和repr显示格式 3、十六进制和八进制数 10进位制转换为8进制或者16进制函数 >>> oct(64) '0100 >>> hex(64)   '0x40 内置函数int函数会将一个数字的字符串变换为一个整数。并可以通过定义的第二个参数来去顶变换后的数字的进制: >>> int('0100'),int('0100',8),int('0x40',16) (100, 64, 64) 4、其他的内置数学工具 pow abs import math import random 四、其他数字类型 1、小数数字 2、集合 2.4版本的的新类型。它是其他对象的集合。 创建一个结合对象,将一个序列或其他的迭代对象传递给内置的set函数 >>> x=set('acd') >>> y=set('bed') >>> x set(['a', 'c', 'd']) >>> 'a' in x True >>> x|y set(['a', 'c', 'b', 'e', 'd']) >>> x-y set(['a', 'c']) >>> x&y set(['d']) 3、布尔型 bool True和False 4、第三方扩展

    04

    使用中国剩余定理(CRT)进行RSA解密

    AI摘要:本文介绍了如何使用中国剩余定理(CRT)高效地进行RSA解密。首先,概述了RSA加密的基本原理,包括密钥对的生成、加密和解密过程。接着,详细解释了中国剩余定理的概念及其在RSA解密中的应用,包括计算模$p$和模$q$下的部分明文、求解$q$的模$p$的逆元$q_{\text{inv}}$,以及如何合并这些结果来得到最终的明文$m$。文章还提供了一个完整的Python实现,展示了如何计算模数$n$、使用inverse函数计算逆元、使用快速幂算法计算部分明文,以及如何合并结果得到明文。通过CRT,RSA解密过程在计算上变得更加高效,因为它允许在较小的模数下进行计算。 使用中国剩余定理(CRT)进行RSA解密

    01
    领券