python实现RSA算法

一、算法简介

RSA算法是一种非对称加密算法，它基于一个简单的数论事实：将两个大质数相乘是容易的，但反过来，对它们的乘积进行因数分解却极其困难。RSA算法由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年共同发明，因此以他们姓氏的首字母命名。

RSA算法的特点总结，以下是一些关键点：

1. 非对称加密：

   • RSA是一种非对称加密算法，使用一对密钥：公钥用于加密，私钥用于解密。这种设计使得RSA非常适合于安全通信，因为公钥可以公开分享，而私钥必须保密。

2. 安全性：

   • RSA的安全性基于大整数分解的困难性。只要密钥长度足够长，目前没有已知的算法能在合理时间内破解RSA加密。

3. 数字签名：

   • RSA算法不仅可以用于加密，还可以用于数字签名。发送者可以用自己的私钥对消息进行签名，接收者可以用发送者的公钥验证签名，确保消息的完整性和来源。

4. 密钥长度：

   • RSA需要较长的密钥长度来保证安全性。随着计算能力的提升，推荐的密钥长度也在不断增加，目前推荐至少使用2048位的密钥长度。

5. 计算效率：

   • 相比于对称加密算法，RSA在加密和解密时的计算效率较低，特别是对于大量数据的处理。因此，RSA通常不用于大量数据的直接加密，而是用于加密对称密钥或进行数字签名。

6. 广泛的应用：

   • RSA算法被广泛应用于互联网安全通信，如SSL/TLS协议中，用于安全地传输敏感信息，如信用卡信息、个人身份信息等。

7. 标准化：

   • RSA算法已经被多个国际标准组织采纳为标准，如ISO/IEC和ITU-T。

8. 密钥管理：

   • 由于RSA使用非对称密钥，密钥管理相对复杂，需要确保私钥的安全存储和传输。

9. 抗量子计算：

   • 随着量子计算的发展，RSA算法可能面临安全威胁。量子计算机理论上能够快速分解大整数，从而破解RSA加密。因此，后量子密码学正在研究能够抵抗量子攻击的加密算法。

10. 灵活性：

    • RSA算法允许用户根据需要选择不同的参数，如密钥长度和加密指数，以满足不同的安全和性能需求。

RSA算法的这些特点使其成为现代密码学中一个非常重要的工具，尽管它也有一些局限性，如计算效率和密钥管理的复杂性。

二、算法描述

2.1 密钥产生

（1）选取两个保密的大素数$p$和$q$
（2）计算模数$n=p\ast q$ 和 $n$的欧拉函数值$\phi (n)=(p-1)(q-1)$
（3）在$(1,\phi (n))$之间任选一整数$e$，使其满足$gcd(e,\phi (n))=1$，即$e$和$\phi (n)$互素
（4）计算$e$在模$\phi (n)$下的乘法逆元$d$，即$e\ast d\equiv 1(\mathrm{mod}\phi (n))$，因为$e$和$\phi (n)$互素，由裴蜀定理可知整数$d$一定且唯一存在
（5） { e , n } \{e,n\} {e,n}作为公钥， { d , n } \{d,n\} {d,n}作为私钥

2.2 加密过程

为了保证加解密的正确性，首先将明文$m$进行分组，每个分组对应的十进制数值应小于模数$n$，即分组长度小于${\log }_{2}n$，然后进行分组加密。$$加密运算：m^e\mathrm{mod}n=c$$

2.3 解密过程

对密文$c$进行分组解密$$解密运算：c^d\mathrm{mod}n=m$$

2.4 证明解密正确性

由加密过程$m^e\mathrm{mod}n=c$和解密过程$c^d\mathrm{mod}n=m$，可知$c^d\mathrm{mod}n=m^{ed}\mathrm{mod}n$
又因为$e\ast d\equiv 1(\mathrm{mod}\phi (n))$，可得$e\ast d=k\phi (n)+1$，$k\in \mathbb{Z}$，所以$c^d\mathrm{mod}n=m^{ed}\mathrm{mod}n=m^{k\phi (n)+1}\mathrm{mod}n$
所以要证$c^d\mathrm{mod}n=m$成立，即证$m^{k\phi (n)+1}\mathrm{mod}n=m$成立，注意:$m<n$
分两种情况讨论：

---

（1）$m$和$n$互素
由欧拉定理可得，$m^{\phi (n)}\equiv 1(\mathrm{mod}n)$，则有$m^{k\phi (n)}\mathrm{mod}n=1^k\mathrm{mod}n=1\mathrm{mod}n$，所以$m^{k\phi (n)+1}\equiv m(\mathrm{mod}n)$，即证$m^{k\phi (n)+1}\mathrm{mod}n=m$成立

---

（2）$m$和$n$不互素
因为$m<n$，所以$m$一定为$p$或$q$的倍数，(如果$m$同时是$p$和$q$的倍数，则$m$一定是$p\ast q$的倍数，与条件$m<n=p\ast q$矛盾)。假设$m=t\ast p$，$t\in {\mathbb{Z}}^{+}$，则有$gcd(m,q)=1$，由欧拉定理可得，$m^{\phi (q)}\equiv 1(\mathrm{mod}q)$，则有$m^{k\phi (q)}\equiv 1(\mathrm{mod}q)$，$m^{k\phi (q)\ast \phi (p)}=m^{k\phi (n)}\equiv 1(\mathrm{mod}q)$
所以存在$r\in \mathbb{Z}$，使得$m^{k\phi (n)}=r\ast q+1$，等式两边同乘$m$，可得$m^{k\phi (n)+1}=m\ast r\ast q+m=(t\ast p)\ast r\ast q+m=t\ast r\ast n+m$
由上述等式，可得$m^{k\phi (n)+1}\equiv m(\mathrm{mod}n)$，即证$m^{k\phi (n)+1}\mathrm{mod}n=m$成立
证毕！

---

三、相关算法

3.1 欧几里得算法

欧几里得算法，又称辗转相除法，是一种用于计算两个非负整数最大公约数（GCD）的古老算法。该算法最早由古希腊数学家欧几里得在其著作《几何原本》中描述，因此得名。

欧几里得算法的基本原理是通过不断用较大的数除以较小的数，并取余数，然后用较小的数和余数继续进行同样的操作，直到余数为0为止。此时，最后的非零余数即为这两个数的最大公约数。

其计算公式可以表示为$gcd(a,b)=gcd(b,a\mathrm{mod}b)$，其中$a$和$b$是两个非负整数。

算法的正确性可以通过数学证明来验证。

例如，假设$x$是$a$和$b$的最大公约数，则$x$能够整除$a$和$b$，表示为$a=k_{1}x,k_1\in \mathbb{Z}$；$b=k_{2}x,k_2\in \mathbb{Z}$；
由于$a\mathrm{mod}b$的结果是$a$除以$b$的余数，根据$a$和$b$的表达式，有$a\mathrm{mod}b=(k_{1}x)\mathrm{mod}(k_{2}x)=x(k_1\mathrm{mod}{k}_2)$，设$m=k_1\mathrm{mod}{k}_2$，则有$a\mathrm{mod}b=xm$，所以$x$也能够整除a$a\mathrm{mod}b$，因此$x$也是$b$和$a\mathrm{mod}b$的最大公约数，这说明$gcd(a,b)=gcd(b,amodb)$成立。

代码实现：递归方式

def gcd(a: int, b: int) -> int:"""欧几里得算法-求两个数的最大公约数（递归版本）:param a: 整数:param b: 整数:return: 返回a、b的最大公约数"""if b == 0:return aelse:return gcd(b, a % b)

代码实现：非递归方式

def gcd(a: int, b: int) -> int:"""欧几里得算法-求两个数的最大公约数（非递归版本）:param a: 整数:param b: 整数:return: 返回a、b的最大公约数"""while b != 0:a, b = b, a % breturn a

3.2 扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm）是欧几里得算法（也称为辗转相除法）的扩展，用于计算两个整数的最大公约数（GCD）以及找到满足裴蜀等式的整数解。具体来说，对于任意两个整数$a$和$b$，该算法不仅能计算出它们的最大公约数$d$，还能找到整数$x$和$y$，使得$ax+by=d$成立。

扩展欧几里得算法基于裴蜀定理：对于任意两个不全为0的整数$a$和$b$，必存在整数$x$和$y$，使得$ax+by=gcd(a,b)$成立，其中$gcd(a,b)$表示$a$和$b$的最大公约数。

推论： 如果$a$和$b$是不全为0的整数且$gcd(a,b)=1$，则当且仅当存在整数$x$和$y$，使$ax+by=gcd(a,b)$成立

算法通过递归的方式，使用辗转相除法逐步缩小问题规模，直到找到最大公约数，并同时计算出对应的$x$和$y$

应用场景

1. 求解线性不定方程：扩展欧几里得算法可以用来求解形如$ax+by=c$的线性不定方程，其中$a$、$b$和$c$是已知整数，$x$和$y$是未知整数。
2. 求模逆元：在模运算中，扩展欧几里得算法可以用来求解乘法逆元，即找到一个整数$x$使$ax\equiv 1(\mathrm{mod}n)$，其中$n$是模数。
3. 求解线性同余方程：扩展欧几里得算法还可以用于求解线性同余方程，即形如$ax\equiv b(\mathrm{mod}n)$的方程。

代码实现：递归方式

def ext_gcd(a: int, b: int) -> tuple:"""扩展欧几里得算法-求乘法逆元(递归版本):param a: 整数:param b: 整数:return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd"""if b == 0:return (a, 1, 0)else:gcd, x1, y1 = ext_gcd(b, a % b)x = y1y = x1 - (a // b) * y1return (gcd, x, y)

代码实现：非递归方式

def ext_gcd(a: int, b: int) -> tuple:"""扩展欧几里得算法-求乘法逆元（非递归版本）:param a: 整数:param b: 整数:return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd"""x0, x1, y0, y1 = 1, 0, 0, 1while b != 0:q, a, b = a // b, b, a % bx0, x1 = x1, x0 - q * x1y0, y1 = y1, y0 - q * y1gcd, x, y = a, x0, y0return gcd, x, y

3.3 模重复平方算法

模重复平方算法（Modular Exponentiation by Repeated Squaring）是一种用于高效计算模幂的算法，特别适用于处理大整数幂运算。该算法的核心思想是通过将指数二进制分解，然后利用平方和乘法来计算幂的值。

该算法的优势在于其时间复杂度为$O(\log b)$ ，显著提高了大整数幂运算的效率。因此，它在密码学中有着广泛的应用，尤其是在RSA加密算法中，用于快速计算大整数的模幂。

具体来说，模重复平方算法的基本步骤如下：计算$a^b\mathrm{mod}n$

1. 指数二进制分解：首先将指数$b$转换成二进制表示。例如，如果$b=560$，其二进制表示为$1000110000$
2. 初始化结果：初始化结果变量$d$为1，底数变量$a$为给定的底数
3. 循环计算：从高位到低位遍历指数的二进制表示。首先对当前结果变量$d$进行平方运算对模数$n$取余；如果$b_i=1$，则再将当前结果变量$d$乘以底数a 并对模数$n$取余；
4. 最终结果：当所有位都处理完毕后，得到的结果即为$a^b\mathrm{mod}n$

例如：$7^{560}\mathrm{mod}561$

$i$		9	8	7	6	5	4	3	2	1	0
$b_i$		1	0	0	0	1	1	0	0	0	0
$c$	0	1	2	4	8	17	35	70	140	280	560
$d$	1	7	49	157	526	160	241	298	166	67	1

代码实现：

def quick_mod(a: int, b: int, mod: int) -> int:"""模重复平方算法-大数的模幂运算:param a: 底数:param b: 指数:param mod: 模数:return: 返回余数d"""c, d = 0, 1# 将 b 转为二进制字符串bin_b = bin(b)[2:]for i in bin_b:c = c * 2d = d * d % modif i == '1':c = c + 1d = (d * a) % modreturn d

3.4 Miller-Rabin 素性检测算法

Miller-Rabin素性检测算法是一种用于判断一个数是否为素数的概率性算法。该算法基于费马小定理的逆定理，并通过随机化方法来提高素性检测的准确性。Miler-Rabin算法的核心思想是利用费马小定理及其扩展形式。

算法检测过程
给定奇数$n\ge 3$和安全参数/检测次数$k$，记$n-1=2^{s}d$，$d$为奇数

1. 随机选取整数$a$，$2\le a\le n-2$，计算$x_0\equiv a^d(\mathrm{mod}n)$
2. 如果$x_0=1$或$x_0=n-1$，则通过检验，$n$可能为素数，回到$1$；否则，计算$x_1\equiv x_0^2(\mathrm{mod}n)$
3. 如果$x_1=n-1$，则通过检验，可能为素数，回到1；否则，计算$x_2\equiv x_1^2(\mathrm{mod}n)$；
4. 如此继续计算$x_i$下去，直到计算到$x_{s-1}$;如果$x_{s-1}=n-1$，则通过检验，可能为素数，回到1；否则，$n$为合数
5. 上述过程重复$k$次

代码实现：

def miller_rabin(n: int, k: int = 100) -> bool:"""使用 Miller-Rabin 算法判断一个整数是否为素数:param n: 待检测的整数:param k: 迭代次数，k 越大，准确率越高:return: 如果 n 是素数，返回 True；否则返回 False"""# 特殊情况处理if n <= 1:return Falseif n <= 3:return Trueif n % 2 == 0:return False# 将 n-1 写成 2^r * d 的形式r, d = 0, n - 1while d % 2 == 0:r += 1d //= 2# 进行 k 次迭代for _ in range(k):a = random.randint(2, n - 2)x = pow(a, d, n)if x == 1 or x == n - 1:continuefor _ in range(r - 1):x = pow(x, 2, n)if x == n - 1:breakelse:return Falsereturn True

四、算法实现

import randomdef int2bytes(integer: int) -> bytes:"""整数转换成字节串:param integer::return: 返回字节串"""# 1.计算所需的最小字节数if integer == 0:len = 1else:len = int((integer.bit_length() + 7) // 8)# 2.整数转换为字节串byte_string = integer.to_bytes(len, byteorder='big')return byte_stringdef calculate_block_size(n: int) -> int:"""计算块大小:param n: 模数n:return: 返回块大小，单位:字节/块"""return (n.bit_length() - 1) // 8def gcd(a: int, b: int) -> int:"""欧几里得算法-求两个数的最大公约数:param a: 整数:param b: 整数:return: 返回a、b的最大公约数"""while b != 0:a, b = b, a % breturn adef ext_gcd(a: int, b: int) -> tuple:"""扩展欧几里得算法-求乘法逆元:param a: 整数:param b: 整数:return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd"""x0, x1, y0, y1 = 1, 0, 0, 1while b != 0:q, a, b = a // b, b, a % bx0, x1 = x1, x0 - q * x1y0, y1 = y1, y0 - q * y1gcd, x, y = a, x0, y0return gcd, x, ydef miller_rabin(n: int, k: int = 100) -> bool:"""使用 Miller-Rabin 算法判断一个整数是否为素数:param n: 待检测的整数:param k: 迭代次数，k 越大，准确率越高:return: 如果 n 是素数，返回 True；否则返回 False"""# 特殊情况处理if n <= 1:return Falseif n <= 3:return Trueif n % 2 == 0:return False# 将 n-1 写成 2^r * d 的形式r, d = 0, n - 1while d % 2 == 0:r += 1d //= 2# 进行 k 次迭代for _ in range(k):a = random.randint(2, n - 2)x = pow(a, d, n)if x == 1 or x == n - 1:continuefor _ in range(r - 1):x = pow(x, 2, n)if x == n - 1:breakelse:return Falsereturn Truedef gen_prime(bits: int) -> int:"""随机生成指定位数的素数:param bits: 指定随机生成素数的位数:return: 返回指定位数的随机生成素数"""while True:# 1.生成一个随机的bits的位奇数candidate = random.getrandbits(bits)candidate |= (1 << (bits - 1)) | 1  # 确保最高位和最低位为1# 2.使用Miller-Rabin素性检测算法判断是否为素数if miller_rabin(candidate):return candidatedef quick_mod(a: int, b: int, mod: int) -> int:"""模重复平方算法-大数的模幂运算:param a: 底数:param b: 指数:param mod: 模数:return: 返回余数d"""c, d = 0, 1# 将 b 转为二进制字符串bin_b = bin(b)[2:]for i in bin_b:c = c * 2d = d * d % modif i == '1':c = c + 1d = (d * a) % modreturn ddef gen_key(bits: int = 1024) -> tuple:"""生成密钥对:param bits: 指定生成p,q两个质因数的位数:return: (e,n),(d,n)"""# 1.生成p和q两个质因数p = gen_prime(bits)while True:q = gen_prime(bits)if p != q:break# 2.计算除数n和n的欧拉函数值phin = p * qphi = (p - 1) * (q - 1)# 3.生成与phi互质的公钥e# e=65537while True:e = random.randint(2, phi - 1)# 判断是e、phi否互质if gcd(e, phi) == 1:break# 4.计算私钥d# 确保d是正数并且在 phi 的范围内d = ext_gcd(e, phi)[1] % phireturn (e, n), (d, n)def rsa_encrypt(m: bytes, public_key: int, n: int) -> tuple:"""RSA加密函数:param m: 明文:param public_key: 公钥:param n: 模数:return: 返回加密明文"""# 1.计算块的大小# 保证每明文块的十进制数小于n,单位:字节/块block_size = calculate_block_size(n)# 2.进行加密bytes_encrypted_blocks = []int_encrypted_blocks = []for i in range(0, len(m), block_size):# 取出单个明文快block = m[i:i + block_size]# 将明文块转换为整数int_block = int.from_bytes(block, byteorder='big')# 对明文快进行加密int_encrypted_block = quick_mod(int_block, public_key, n)int_encrypted_blocks.append(int_encrypted_block)# 整数转成字节串bytes_encrypted_block = int2bytes(int_encrypted_block)bytes_encrypted_blocks.append(bytes_encrypted_block)return bytes_encrypted_blocks, int_encrypted_blocks  # 字节串列表/整数列表def rsa_decrypt(c: list, private_key: int, n: int) -> tuple:"""RSA解密函数:param c: 密文:param public_key: 私钥:param n: 模数:return: 返回解密密文"""# 1.计算块的大小block_size = calculate_block_size(n)# 2.进行解密bytes_decrypted_blocks = []int_decrypted_blocks = []for block in c:# 将密文块转换为整数int_block = int.from_bytes(block, byteorder='big')# 对密文块进行解密int_decrypted_block = quick_mod(int_block, private_key, n)int_decrypted_blocks.append(int_decrypted_block)# 整数转成字节串bytes_decrypted_block = int2bytes(int_decrypted_block)bytes_decrypted_blocks.append(bytes_decrypted_block)return bytes_decrypted_blocks, int_decrypted_blocks  # 字节串列表/整数列表if __name__ == '__main__':# 1.生成密钥对public_key, private_key = gen_key()print(f'公钥e:{public_key[0]}')print(f'私钥d:{private_key[0]}')print(f'模数n:{private_key[1]}')# 2.加密m = '你好，世界！Hello world!'m_ = m.encode()print(f'待加密明文:{m}')print(f'待加密明文-字节:{m_}')print(f'待加密明文-数字:{int.from_bytes(m_, byteorder='big')}')c = rsa_encrypt(m_, public_key[0], public_key[1])print(f'加密明文-字节:{b''.join(c[0])}')print(f'加密明文-数字:{c[1]}')# 3.解密m = rsa_decrypt(c[0], private_key[0], private_key[1])print(f'解密密文:{b''.join(m[0]).decode()}')print(f'解密密文-字节:{b''.join(m[0])}')print(f'解密密文-数字:{m[1]}')

五、演示效果