RSA算法描述

​ RSA( Rivest-Shamir-Adleman )是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA 的加密和解密

密钥对：公钥：( e , n ) ; 私钥：( d , n ) 。e: encryption d: decryption n: number

加密：$c = m^e \ mod \ n$

解密：$m = c^d \ mod \ n$

生成密钥对

$n = p \cdot q$

$\varphi (n) = (p - 1) \cdot (q - 1)$

加密钥 e 满足 $gcd(e,\ \varphi(n) ) = 1$ 且 e 是素数

解密钥 d 满足 $e\cdot d\ mod\ \varphi(\,n\,) = 1$ , 即 e 在模 m 上的逆元

RSA 算法证明

（1）m 和 n 互素

利用欧拉定理证明：

​ $c = m^e \ mod \ n$

​ $c^d\ mod\ n = m^{ed}\ mod\ n$ # 等式两边同时取 d 次幂， 再取模；

​ $= m^{k\varphi(n)+1}\ mod\ n$ # 因为 e，d 满足$e\cdot d\ mod\ \varphi(\,n\,) = 1$ ，所以 $ed = k\varphi(n)+1$

​ $= m\ (m^{\varphi(n)}\ mod\ n)^k\ mod\ n$ # 乘法取模的结合律 $m^{\varphi(n)}\ \equiv 1\ mod\ n $

​ $= m\ mod\ n$ # 因为 m 和 n 互素，所以根据欧拉定理，有$m^{\varphi(n)}\ mod\ n = 1$

（2）m 和 n 不互素

因为m，n不互素，意味着m，n有公约数。故 m 只能是 p 或 q 的倍数。由于 m<n , 所以 m 不能是 pq 的倍数。因此无论 m 是 p 的倍数还是 q 的倍数，只需要证明其一，另一个同理可证。

不妨设 m = tp , 其中 t 为整数，则 gcd(m, q) = 1. 由欧拉定理：

​ $m^{\varphi(q)}\equiv 1\ mod\ q$

​ $(m^{\varphi(q)})^{k\varphi(p)}\equiv 1^{\varphi(p)}\ mod\ q$

​ $m^{k\varphi(n)}\equiv 1\ mod\ q$

因此，存在一个整数 r 使得 $m^{k\varphi(n)}= rq+1$ ，此时，等式两边同乘 m = tp 得：

综上所述：无论 m 与 n 是否互素，此算法成立。

代码部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import random

def fastExpMod(b, n, m):
    '''
    return : b^n mod m
    '''
    result = 1
    while n != 0:
        if (n & 1) == 1:  # 按位与操作
            result = (result * b) % m
        b = (b * b) % m
        n = n >> 1  # 位数右移操作
    return result


def Euclid(a, b):
    '''
    欧几里得算法 ax + by = gcd(a,b)
    Return : [x , y , gcd(a,b)]
    '''
    X = [1, 0, a]
    Y = [0, 1, b]
    while Y[2] != 0:
        Q = X[2] // Y[2]
        NEW_Y = [i * Q for i in Y]
        T = list(map(lambda x: x[0] - x[1], zip(X, NEW_Y)))
        X = Y.copy()
        Y = T.copy()
    return X


def fermatPrimeTest(m, k):
    '''
    费马素性检验算法
    m : 给定整数
    k : 安全参数，重复K次
    '''
    if m % 2 == 0:
        return False
    for i in range(k):
        a = random.randint(2, m - 2)
        g = Euclid(a, m)
        if g[2] == 1:
            r = fastExpMod(a, m - 1, m)
            if r == 1:
                continue
            else:
                return False
        else:
            return False
    return True


def findPrime(lower, upper):
    '''
    return : 一个位于upper和lower之间的素数
    '''
    while True:
        n = random.randint(lower, upper)
        if fermatPrimeTest(n, 6) == True:
            return n


def selectE(fn):
    '''
    fn : euler function
    Return : e
    '''
    while True:
        e = random.randint(1, fn)
        temp = Euclid(e, fn)
        if temp[2] == 1:
            return e


def keyGenerate(lower, upper):
    '''
    给定两个素数p和q生成的区间
    return : e,n,d
    '''
    p = findPrime(lower, upper)
    q = findPrime(lower, upper)
    print("p:" + str(p) + "   q:" + str(q))
    # print("q:"+str(q))
    n = p * q
    fn = (p - 1) * (q - 1)
    e = selectE(fn)
    temp = Euclid(e, fn)  # 欧几里得算法求逆元
    d = temp[0]
    if d < 0:  # 由于e和fn互素故一定存在逆元
        d = d + fn  # 保证d为正数
    return e, n, d


def Encryption_Decryption():
    e, n, d = keyGenerate(1000, 10000)  # 密钥生成
    # 更改keyGenerate函数的两个参数，可以改变生成素数的位数大小。
    print("public key (e,n):", end="")
    print("(" + str(e) + "  ,  " + str(n) + ")\n")
    print("private key d: " + str(d) + "\n")
    m = random.randint(1, n)  # m < n m为明文
    print("Plaintext: " + str(m))
    c = fastExpMod(m, e, n)  # 加密  c为密文 m^e mod n
    print("\nEncryption of PlainText: " + str(c))
    x = fastExpMod(c, d, n)  # 解密 c^d mod n
    print("\nDecryption of CipherText: " + str(x))
    if x == m:
        print("\nThe plaintext and ciphertext are the same.")


if __name__ == "__main__":
    Encryption_Decryption()

​