1.RSA加密

1.1 RSA

RSA是目前使用最广泛的公钥密码体制之一。它是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA算法的安全性基于RSA问题的困难性，也就是基于大整数因子分解的困难性上。但是RSA问题不会比因子分解问题更加困难，也就是说，在没有解决因子分解问题的情况下可能解决RSA问题，因此RSA算法并不是完全基于大整数因子分解的困难性上的。

1.2 RSA为什么安全。

ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
n=pq。只有将n因数分解，才能算出p和q。

2. 加密算法实现

2.1 加密过程

首选取两个互质数 p q
那么p * q 得到 N
这时我要计算出φ(N)
φ函数φ(N)是小于或等于N的正整数中与N互质的数的数目。

根据欧拉公式，我知道

φ(N) = (p-1)*(q-1)

这个公式简单的说就是 e*d除以φ(N)得到的余数为1

这个公式可以转换成

e*d - 1 = kφ(n)

所以，已知 e = 7 φ(n) = 120

7d - 120*k = 1
我们要获得d和k的话,需要使用扩展欧几里得算法
以下是扩展欧几里德算法的Python实现：


def ext_euclid(a, b):     
    if b == 0:         
        return 1, 0, a     
    else:         
        x, y, q = ext_euclid(b, a % b) 
        # q = gcd(a, b) = gcd(b, a%b)         
        x, y = y, (x - (a // b) * y)         
        return x, y, q

120 = 7 * 17 + 1
17 = 17 * 1
1 = 120 * 1 + 7 * (-17)
1 = 120 * 1 + 7 *(-17)
最终得出，d = -17 k = 1

虽然我们得到了 d=-17但在rsa中 d必须是一个正整数，在工程中，RSA的pq会无穷大过公钥质数e ，所以根本不会出现这种状况。但是如果出现负数，我们会将它翻转

if(d<0)
    d=d+φ(n)

所以得到 e对φ(n)的模逆元为 120 + （-17）也就是103

RSA中公钥就是 N，e 而私钥就是N，d

我们上面的例子公钥 (143,7) 私钥(143, 103)

加密

m^e ≡ c (mod n)

要加密的m = 13

13^7 = 117 (mod 143)

解密

c^d ≡ m (mod n)

要解密的是c = 117

117^103 = 13 (mod 143)

上面可以用快速幂取余来计算出余数

c^d ≡ m (mod n)

#include <stdio.h>
long PowerMod (int a, int b, int c) {
    int  ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        b = b/2;       //   b>>=1;
        a = (a * a) % c;
    }
    return ans;
}

2.2. Python实现

import math
# 在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
# 求解出d
# 第一步，随机选择两个不相等的质数p和q。
# 选择473398607161和4511491。（实际应用中，这两个质数越大，就越难破解。）
p = 473398607161
q = 4511491
# 第二步，计算p和q的乘积n。
n = p*q
# n的长度就是密钥长度。n写成二进制是111011...1011010101011，一共有63位，
# 所以这个密钥就是63位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
# 第三步，计算n的欧拉函数[N]φ(n)。
N = (p-1)*(q-1)
# 第四步，随机选择一个整数e，条件是1< e < [N]φ(n)，且e与φ(n) 互质。
# 这里选择e=17,可以在1<e<N里面选择
e=17
# 第五步，求d，就是计算e对于[N]φ(n)的模反元素d。
# 所谓"模反元素"就是指有一个整数d，可以使得ed被[N]φ(n)除的余数为1
# 　ed - 1 = k*N,k是一个正整数
# 　e*d ≡ 1 (mod N) 等价,这里使用扩展欧几里得算法实现,首先定义扩展欧几里得算法函数
def ext_euclid(a, b):#a==e,b==N
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a // b) * y)
        return x, y, q
print(ext_euclid(e,N))

2.2 gmpy2库实现

gmpy2是一个C编码的Python扩展模块，它支持多精度算术。gmpy2是原始gmpy模块的后继者。

import gmpy2
p = 473398607161
q = 4511491
e = 17
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(d)