零基础完全理解RSA算法并用PYthon语言实现

mlsily

一篇帖子带你完全读懂RSA加密,没用的知识又增加了！
发错版块了怎么办 ，本来是打算用C实现的，但是还是python方便······
0. 前言
前段时间学习了甲鱼老师的解密系列，非常遗憾没有继续更新下去。后来借了一本甲老师课程中提到的《加密与解密》，读到加密算法的部分，发现写的非常简略，并且看雪资料里也没有发帖详细讲解这部分，导致初学者非常难看懂这部分内容。本文将对RSA算法进行非常详细的解析，从最基础的内容开始说，立在使完全零基础的人，看到这篇帖子也能完全理解RSA算法。
这只是一篇新人入门的学习日志，有错误请不吝指出

本篇中 ^符号除^-1的情况代表取模逆元，其余均为幂运算。

1. 算法简介

RSA是一个既能用于数据加密也能用于数字签名的算法，是当前最流行的加密算法。该算法是一种非对称加密算法，即加密和解密使用不同密钥。

2.前置知识：
   （1）模运算 ｛a / b = c 余 d，则称为 d 等于 b 模 a，记作 ： d ≡ b mod a ｝

   （2）模逆元 { 设  d ≡ b mod a  ， e ≡ c mod a  若 d * e mod a= 1 则称 b 和 c 互为 模 a 的逆元，记作a^-1 = b  b ^-1 = a .例：2 mod 5 = 2 ， 3 mod 5 = 3, 2 * 3 =6 6mod5 = 1 。称 3 是 2模5的逆元，2 是 3 模 5 的逆元 3^-1 = 2 ,2 ^-1 = 3.}

   （3） 欧拉函数 φ（n） :小于 n 的 与 n 互质的正整数的个数。  例 φ（7）= 6  因为 7是质数，1 ，2,3,4,5,6都与7互质，一共6个数。

3. 算法原理

取质数 p 和 q
设 n =  p * q
则 φ(n)= φ(p)*φ(q)=(p-1)*(q-1)
取任意正整数 e < φ(n) 且与 φ(n)互质，e为加密密钥。
计算e mod φ(n) 的逆元 设为 k，k为解密密钥。
设要加密的数据为 m（明文） 加密后的数据为 c（密文）
密文 c = m^e mod n
明文 m = c^k mod n


举例说明：
{设 p = 3 ,q = 7
则 n = 3*5 = 21
则 φ(n) = 2 * 6 = 12
设 e = 5
5 mod 12  = 5
5* 5 mod 12 = 1
5 是 5 模12 的逆元，即 解密密钥 k = 5 。
设明文为  m = 10
密文c = 10^5 mod 21  = 100000 mod 21  = 19
明文 m = 19^5 mod 21 = 2476099 mod 21 = 10}

我们注意到加密密钥与解密密钥相同（都等于5），这显然是不安全的。为了保证安全性，我们通常要选取较大的数作为p,q 通常为1024位二进制数以上。

我们再举一个例子：
｛设 p = 61 q = 67
则 n = 4087
则 φ(n) = 60*66 = 3960
设  e = 17
17 mod 3960 = 17
求模逆元，引入扩展欧几里得算法【若a b 互质，则一定有ax+by mod b = 1  可以得到x,y特解】

3960 = 17 * 233 - 1
即 1 = 17*233 mod 3960
17的在模3960上的模逆元17^-1 = 233
根据要读取的数据大小，可以知道明文的取值范围。假如为16位字 则为 0-65535。
设明文  m = 3456
则密文 c = 3456^17 mod 4087
明文 m = c^233 mod 4087｝

我们发现在 p , q取值还只是很小的数字的时候，加密运算的过程已经是非常大的数字运算了。如果在计算机上直接进行多次的幂运算，将会对程序的性能造成极大的影响，此时我们引入了快速模幂算法。
假如我们计算 x^15 mod 21

x^15 = x^7 * x^8 = x^4* x^2* x * x^8 = （x^2）^2* x^2 *x * ((x^2)^2)^2 = ((x^2 * x)^2 * x )^2* x

我们把15写成二进制，会更加直观的看到规律
15 = 1111 b
x^15 =  ((x^2* x)^2* x )^2* x
二进制数从最高位开始，第二位 数字是1 则取底数平方之后乘以x  数字是0 则直接取平方
1111 第 2 位是 1 则 取第一项为 x^2* x，第二位是1 取 则为 （x^2*x)* x 第三位是 1 取 （（x^2* x)^2* x)^2 * x
为了防止数字过大造成的溢出，我们可以把模运算带入到幂运算中间。

即：  ((x^2* x)^2* x )^2 * x = (((((x^2 * x) mod 21 )* x) mod 21 )* x) mod 21

带入例题
17 =  10001
c = ((((3456^2 mod 4087)^2mod 4087)^2 mod 4087)^2 * 19764) mod 4087 = 825

233 = 1110 1001
825^233  mod 4087 = (((((((825^2 * 825)^2 * 825)^2)^2* 825)^2*825)^2)^2)^2*c mod 4087 = 3456

这样的方法看起来已经很快了，可是当我们要进行运算的幂有几十、上百位的时候，这样的计算速度还是远远不够的。

这里我们就需要引入欧拉定理:
　　　对于互质的整数a和n，有a^φ(n) ≡ 1 (mod n)

(草履虫都能看懂的推导过程
我们计算 2^4; mod 5
因为 2 与 5 互质
所以  当φ(5) 遍历模5的缩系时，2*φ(5)也遍历模5的缩系。
即： 模 5 的缩系 φ(5) = 1,2,3,4
①2*1 mod5  ≡ 2, 2*2 mod5 ≡ 4 , 2*3 mod 5  ≡ 1 ,2*4mod 5  ≡ 3 , 同样遍历了φ(5)。
②把结果相乘 2 * 4 * 1 * 3 * 2^4 mod5 = 2 * 4 * 1 * 3 mod 5 即 4！mod 5 .
① 相乘 等于 2*1 * 2*2 * 2*3 * 2*4 = 2^4 * 4！mod 5
即 2^4* 4！mod5 ≡ 4！mod 5
即 2^4 mod5 ≡ 1）

我们再用一个例题说明如何用欧拉定理对运算进行简化：

计算 85^735 mod 385
带入欧拉定理，原式等于 85^(735mod φ(385)) mod 385
385 = 5 * 7 *11 , φ(385) = 4 * 6 * 10 = 240

85^(735mod φ(385)) mod 385 = 85……(735mod 240 ) mod 385  = 85^15 mod 385
385 = 5 * 7 *11
上式= 85^15 mod 5 ≡ 85^15 mod 7 ≡ 85^15 mod 11

85^15 mod 5 = 0 ，85^15 mod 7 =  1， 85^15 mod 11 = 10

即 x / 5 = 0, x / 7 余 1， x / 11 余 10，即 5x = 7y +1 = 11z + 10 , 用中国剩余定理求解三元一次方程。
（中国剩余定理（CRT）， 其他项的乘积乘以一个可以使模本项等于1 的系数，再把这个数乘以本项，之后遍历所有项并求和，最后再模所有项的乘积，即为所求方程的一个特解（网页对符号的支持实在是很难不让人吐槽，只能文字描述一下了）。
设 5x + 0 = 7y +1 = 11z + 10 = a
a = 【0（因为 a mod 5 = 0 ） * 7 * 11 * 3( 因为 7*11 = 77,77*3 = 231 mod 5 = 1) + 1( a mod 7 = 1) * 5* 11 * 6 ( 5* 11 = 55 , 55 * 6 mod 7 = 1) + 10(a mod 11 = 10)* 5 * 7  * 6 ( 5 * 7 =35 , 35 * 6 mod 7 = 1)】 mod (5 * 7 *11)
=( 0 + 330 + 2100 ) mod 385
= 120
即 方程的特解为 120 通解为 120 + 385k
85^735 mod 385 = 120

通过上面的式子括号内的解释，大家应该已经完全理解了中国剩余定理，也就理解了模幂在计算机中的计算方式。这种计算方法使得RSA的加解密过程性能提升50%以上。
对上面的例子进行观察，可以发现，我们选定的加密密钥e如果正好是φ(n)的倍数，那么加密过程将会瞬间完成。通过对程序的追踪，我们不难得出φ(n)是e的倍数关系，这将使求出 p ， q 的值变得容易，加密的安全性大大降低。

4 . 生成两个素数 p 和 q。
至此，大家已经完全弄懂了RSA加密算法的全部内容。但是想要写出RSA的程序，还有一个问题，那就是如何选取p 和 q 的值，换句话说，就是如何保证我们随机生成的两个大整数是质数。
当前计算机普遍采用的是米勒拉宾素性检验方法。
米勒拉宾素性检验首先引入费马小定理：P 为素数，对不是p的倍数的整数a 有 a^(P-1) mod P = 1。 这可以由欧拉定理简单推导得来。
反过来看，当我们选取任意一个数字 a 大于1 小于 n-1 ，有 a^(n-1) mod n =1 ,那么 n 有概率是素数。
我们具体实现这个过程。
设 n 是一个 ≥ 3 的奇数。
设置循环次数为t
for (0 to t)
① 随机选取任意的 a ，使 n-2 ≥ a ≥2 (因为当a = 1 或 n-1 时，a mod n = ±1, ±1 的偶数次幂等于1，模n恒等于1，a不取 n-1 或 1 。)
    如果 a^(n-1) mod n = 1
    则 n 可能为素数。
    上式 = a^(n-1) - 1 mod n= 0
    平方差公式展开
    = (a^(n-1 / 2)+1)*(a^(n-1/2) - 1)
    展开k次，直到 n-1 / 2*k 是一个奇数。
    =(a^(n-1 / 2)+ 1)*(a^((n-1)/(2*2))+ 1)······*(a^(n-1/2k)-1)     （这其实就是上面的快速幂算法）
    当这个式子中的任意一项 Mod n = ± 1 的时候 那么整个式子 mod n 都等于 1 。
    即  if a^(n-1/2k)-1 mod n = 1 (因为前面是减一，所以这里是 1。)，则判断a 是一个素数，直接跳出到①，进入下一次循环，重新选取 a
    if   if a^(n-1/2k)-1 mod n ！= -1，继续向下运算 a^(n-1/2（k-1）)-1 mod n，= -1则判断a 是一个素数，跳出，不等于则继续向下运算。
    直到运算到 a^(n-1 / 2)+ 1 mod != 1 则判断 n 为合数
我们把这个过程略为优化，并以伪代码形式表达即为：
0.n-1 /2^s *k             // 把原式分解成 s 项，k为奇数项
1.for(0 to t)
2.random a (2,n-2)
3.g = gcd (a,n)           // 用欧几里得算法的求最大公约数要比计算模幂快的多，所以可以先计算最大公约数，排除n是合数的可能）
4.if g > 1
        return false
5.z = a^k mod n
6.if z = ± 1
        goto 1                 // a的奇数次幂mod n 等于1 ，即式子最后一项等于 1 直接判断 a为素数，跳到下次循环。
7.for (0 to 项数 s-1)
        z = z^2 mod n          //平方即是式子的前一项
        if z == n - 1        // n - 1 在mod n的情况下即是 - 1
                goto 2.
        else
                return false
米勒拉宾方法是一直随机检验方法，我们可以证明它的正确概率 ≥75%，说好的零基础，这里就不展开概率证明了（再次吐槽网页的符号）。
实际正确概率要远大于这个75%，但其求证具体数值需要黎曼猜想为前提。

5. RSA 基于 python的代码实现

import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a                                // 欧几里得算法求最大公约数

def lcm(a, b):
    return abs(a * b) // gcd(a, b)                   //求φ(n)

def is_prime(n, k=5):                     // 循环5次的素性检验
    if n <= 1:                     
        return False                           //   1不是质数，返回false
    elif n <= 3:
        return True                           //   2, 3 都是质数，返回ture
    elif n % 2 == 0 or n % 3 == 0:
        return False                         //   2 , 3 的倍数不是质数 返回false 在一定程度上可以提高算法的效率
    d = n - 1                                
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1                                                // 0.n-1 /2^s *k                                     
    for _ in range(k):                                        // 1.for(0 to t)
        a = random.randint(2, n-2)                    // 2.random a (2,n-2)
        x = pow(a, d, n)                                 //  5.z = a^k mod n 
        if x == 1 or x == n-1:                           // 6.if z = ± 1
            continue
        for _ in range(r-1):                              // 7.for (0 to 项数 s-1)
            x = pow(x, 2, n)
            if x == n-1:
                break
        else:
            return False
    return True

def generate_prime_number(length, k=5):                                  //length：生成的 n 的长度
    while True:
        p = random.randint(2**(length-1), 2**length-1)
        if is_prime(p, k):
            return p

def generate_key_pair(length):
    p = generate_prime_number(length//2)                                //  生成长度为 输入参数//2的 p 值
    q = generate_prime_number(length//2)                                //  生成长度为 输入参数//2的 q 值
    n = p * q
    L = lcm(p-1, q-1)                                                // φ(n)
    e = random.randint(2, L-1)                                // 2到 φ(n)-1之中随机生成密钥，保证不会出现 φ(n)的倍数                                
    while gcd(e, L) != 1:                        
        e = random.randint(2, L-1)                                // 密钥e 与 φ(n)互质
    d = pow(e, -1, L)                                                // 求密钥 e mod φ(n) 的 逆元 d ，即为解密密钥
    return ((e, n), (d, n))                        

def encrypt(message, public_key):
    e, n = public_key                                
    m = int.from_bytes(message.encode(), byteorder='big')                // 对要加密的明文进行编码，以大端形式转换为一个整数                 RSA通常搭配MD5等其他摘要算法，把要加密的信息分组成一个整数数组，并不需要再次编码
    c = pow(m, e, n)                                                                                 // 加密。python内置函数 pow的算法上面有讲解
    return c.to_bytes((c.bit_length() + 7) // 8, byteorder='big')                        //讲加密后的数字转换成字节，//8以保证是一个整数字节

def decrypt(ciphertext, private_key):
    d, n = private_key                                                                                
    c = int.from_bytes(ciphertext, byteorder='big')                                        //同样的方式进行解密
    m = pow(c, d, n)
    return m.to_bytes((m.bit_length() + 7) // 8, byteorder='big').decode()

# 示例使用
message = "Hello, World!"
key_length = 2048

# 生成密钥对
public_key, private_key = generate_key_pair(key_length)

# 加密消息
encrypted_message = encrypt(message, public_key)
print("加密后的消息:", encrypted_message)

# 解密消息
decrypted_message = decrypt(encrypted_message, private_key)
print("解密后的消息:", decrypted_message)

6. RSA 的安全性分析
① RSA加密的过程是 c = m^e mod n , 当我们知道加密密钥 e ，想知道解密密钥 d ，过程是 d = e^-1 mod φ(n), 通过对过程的观察，如果我们知道 φ(n)的值，那么就会很容易得到解密密钥。
φ(n) = (p-1)*(q-1)
显而易见，在我们知道 n 的值的情况下，对 n进行因式分解，可以得到p和q的值。
那么，如果对 n 进行因式分解是困难的，那么RSA就是安全的，如果对n进行因式分解是困难，那么RSA就是不安全的。
当前尚且未证明对一个大整数分解是困难的，也未证明大整数分解是不困难的。
即RSA即不能证明安全，也不能证明不安全。
同时，也未证明对 n 进行因式分解是破解RSA的最佳方法。
那么，我们要尽量避免n 被容易分解。
m < n ,当 m 与 n不互质时，gcd(m,n) 即可轻易分解 n ，所以要避免 m 与 n 不互质。
m 与 n 不互质的概率为 (n - φ(n)) / n = (n-(p-1)*(q-1))/n = (n-p*q -p - q +1)/n
p * q = n, 上式 = (1- p -q )/n , 概率取绝对值  ≈ （p+q)/n = (p+q)/p*q =1/p+1/q
想使1/p+1/q 取最小值，则 p 和 q 应该取相近的两个质数。对n进行因式分解的方法同样也利用这个原则，这里不多做介绍。

② c = m^e mod n
对 m 同时使用两个互质的公钥 e1, e2进行加密，得到密文 c1,c2。
即 c1 = m^e1 mod n , c2 = m^e2 mod n
当 e1 e2 互质，由欧几里得算法可以推出裴蜀定理，一定存在整数a,b，使得a*e1+b*e2 =1。
a,b其中必定有一个数为负，设a为负数，有：
        (c1^-1(模n的逆元) )^-a mod n = m^(a*e1) mod n
        c2^b mod n  = m^(b*e2) mod n
        ((c1^-1)*^-a * c2^b) mod n = m^(a*e1 +b*e2) mod n = m^1 mod n = m

即 绕过解密密钥 d ，直接得到明文 m 。 这显然是不安全的。
所以每次加密，都应该重新生成 p和q的值。

③ c = m^e mod n
对 m 使用公钥 e 进行加密，分别选取不同的模 n1 , n2 , n3
有：
        c1 = m^e mod n1
        c2 = m^e mod n2
        c3 = m^e mod n3
       
用中国剩余定理求解：m^e =  [  c1*n2*n3*((n2*n3)^-1 mod n1) + c2*n1*n3*((n1*n3)^-1 mod n2)+c3*n1*n2*((n1*n2)^-1 mod n3) ]  mod n1*n2*n3
对上式开e次方，即可求解明文m ,同样绕过了解密密钥。
所以，选取加密密钥e的时候，要避免e的数字过小，或者使用摘要算法生成不同的m（加盐）。

④ c = m^e mod n
有m1,m2两段数据，m1^e mod n * m2^e mon d = m1*m2 mon n 。这说明RSA是具有同态性的。
已知密文数据 c
        设 x = (a^e)*(c^e) mod n   （a是一段已知的数据，即加盐）
        对x 进行解密，设：y = x^d mon n
         x = (a^e)*(c^e) mod n = (a* m)^e mod n
带入y，有：
        y = ((a*m)^e^d ）mod n = (a*m) mod n
        m = a * m * (a^-1 mod n)
可以搭配其他加密算法，改变同态性。以后会在其他篇更新。
⑤ 设  c1 = m^e mod n
        c2 = c1^e mod n
        c3 = c2^e mod n
        cn = cn-1 ^e mod n
由于RSA中的模运算的剩余类是一个有限循环群，必定有 cn+1^e = c ,则cn+1 = m
这种方法类似因式分解方法，不能被证明是复杂的，也不能被证明是简单的