Rsa加密原理与简单实现

源码：https://gitee.com/Cheney822/programmes/blob/master/rsa.py

1背景

1.1 数据加密

指的是根据一定规则，将数据处理成不规则的数据，使得人们除非有了关键的钥匙以及得知这个规则，难于得知无规则数据的真实含义。这个一定规则 就是加密算法，这个钥匙就是密钥。

数据加密分为对称密钥加密以及非对称密钥加密：

• 对称密钥加密： 双方共同持有这个密钥，发送方用这个密钥按照指定的算法将数据加密，再发出去；接收方用这个密钥将接收到的数据解密，以得到真实的数据含义。由于双方都持有这个密钥，而且内容相同，所以叫对称密钥
• 非对称密钥加密：这种加密方式的密钥是一对，发送方用其中的一把钥匙将数据加密，再发出去；接收方用这对密钥的另一把钥匙将数据解密，以得到真实的数据含义。发送方持有密钥中的一把钥匙，接收方持有另外一把。接收方持有的钥匙叫 私钥, 而接收方持有的这把钥匙叫公钥 。两把钥匙不一样，所以叫做非对称密钥加密，也叫做公开密钥算法。

1.2 非对称密钥加密

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制 。
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK 。
正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般

推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。
RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥.

2概要设计

2.1 函数

程序涉及到的函数及功能如下：

2.2 接口

程序文件对外开放的方法有三个，分别是加解密和获取密钥。

• 首先是获取密钥newkeys函数，该函数获取一个参数nbits用来指定密钥的位数。函数返回两个list，每个list内有两个元素，分别为[N, e], [N, d]。
• 然后是加密函数，该函数接受两个参数，分别为：待加密的明文和公钥。待加密的信息为Bytes类型，公钥为[int, int]类型，返回值为一个list，其中的每一项分别对应bytes的每一位。
• 最后是解密函数，该函数与加密函数类似。不同之处在于其接受的密文是list类型（对应加密的返回值），返回的是bytes类型（对应用户输入系统的数据类型）
  加解密过程中数据的变化如下图所示：

以上对外的接口内部会调用内部函数（以__开头），外部在使用时不建议直接调用。

2.3 流程

RSA算法的具体描述如下：

（1）任意选取两个不同的大素数p和q计算乘积

（2）任意选取一个大整数e，满足
|

整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）

（3）确定的解密钥d，满足

即

是一个任意的整数；所以，若知道e和 ，则很容易计算出d ；

（4）公开整数n和e，秘密保存d ；

（5）将明文m（m |

（6）将密文c解密为明文m，解密算法为:

然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密

3详细设计

生成密钥

• 第一步，随机选择两个不相等的质数p和q。
• 第二步，计算p和q的乘积n。
• 第三步，计算n的欧拉函数φ(n)。φ(n) = (p-1)(q-1)
• 第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
• 第五步，计算e对于φ(n)的模反元素d。所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
• 第六步，将n和e封装成公钥，n和d封装成私钥。

3优化的判断素数方法

主要优化的规则

• 1.大于3的素数一定在6的倍数前一个或后一个（如素数37在36的后面）
• 2.要判断n是否为素数，只需要让n从2开始，依次除到根号n即可
• 3.在进行“让n从2开始，依次除到根号n”过程中，若n除以2的余数不为0，可以直接跳过[2, sqrt(n)]里面的所有偶数

复杂度分析

1.最基础的算法：也就是让n从2开始判断，一直到n-1
若遇到的数是素数时，此时需要进行n-2次判断
当遇到的不是素数时，要进行a（2 也就是说时间复杂度为n

2.改进后的算法：
根据规则二，判断素数只要从[2，sqrt(n)]即可，此时复杂度为sqrt(n)
根据规则3，无论如何都可以不判断2之后的偶数（当n大于2，当n除尽2时，n不为素数，之后不需要判断，如果n除不尽2时，之后的偶数不要判断）
假设n可以除尽2和不可以除尽2概率相等，那此时复杂度为sqrt(n)/4
根据规则一，只有1/3的数要进行判断，此时复杂度为sqrt(n)/12
也就是说时间复杂度为sqrt(n)/12

快速幂取模运算

输入x,n,p，如何计算xn mod p？

暴力的做法就是直接将n个x乘起来，最终mod p。理论上来说，这样做显然是可以的，但是很明显，这样做的话，程序要循环n次，也就是说它的时间复杂度是O(n)，如果n非常大，算法的效率就特别低，为此引入列快速幂运算。

快速幂的本质就是：底数不断取2次幂，指数不断除2次幂，直到指数除到为1，计算完毕。原先的n次幂运算，它的时间复杂度为O(n)，而如果是快速幂运算，时间复杂度就被降到了O(log2n)。

但是，这个过程中，如果指数的奇数的话，就没有办法除2次幂。对于整数的除，都是整除。例如求2的5次方，经过一次快速幂，它并不会变成4的2.5次方，而是4的2次方，因为4整除2等于2。跟实际还是差了一个4的0.5次方，也就是“原底数”。

每一次到奇数幂时，就会有这些原底数被漏乘，最终形成一群因为是奇数幂而漏乘的“底数群”。因此，我们需要对奇数次幂的情况进行特判，存储这些没乘上的底数群，最终return的时候将它们都乘上。

由上，引入一个每一次处理奇数次幂时，未被底数乘上的待乘底数群。这个底数群的初始值为1，当为奇数次幂时，这个未乘的底数群就以乘以目前的底数的形式进行更新。最后，这个未乘的底数群乘幂为1时不包含奇数幂时遗漏的底数的不完全结果，就是快速幂的最终结果。

然后再加入取模操作即可。

扩展欧几里得算法

​ 欧几里得算法是求最大公约数的算法, 也就是辗转相除法。记 gcd(a,b) 为a和b的最大公约数，欧几里得算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。

应用在RSA加密算法求逆元中：

​ 首先我们知道，再求两个数的最大公约数的时候可以用欧几里得算法。在欧几里得算法中，通过辗转相除，当余数为0的时候最后的除数就是两个数的最大公约数。

​ 而在其扩展算法中，我们已知两个数的最大公约数，我们已知 ax = 1(mod p),展开就是 ax mod p = 1，首先我们先求 p = x1 * a + p1，然后p = a，a = p1，迭代下去

​ 知道pi = 1（i表示出了i次）为之，然后就可以得出 1 = p - xi * a，此时的a和p已经不是我们初始的a和p了，我们需要往前推，推到 1= yp + x*a 为止，此时得出的x就是a的逆元。

​ 如果逆元x为负数，或者比p大，要对其就行取余操作。

4运行测试

4.1获取密钥

4.2加密

4.3解密

4.4完整操作

结果：