python基于RSA的非对称加密体制,要求p、q、e为可输入数字,明文信息为任意可输入数字
时间: 2024-02-05 22:13:04 浏览: 72
首先,我们需要生成RSA密钥对,密钥包括公钥和私钥。其中,公钥包括两个参数:n和e,私钥包括两个参数:n和d。
1. 选择两个大质数p和q,并计算n=p*q。
2. 计算欧拉函数φ(n)=(p-1)*(q-1)。
3. 选择一个与φ(n)互质的整数e,1<e<φ(n)。
4. 计算e关于φ(n)的模反元素d,即满足(e*d)%φ(n)=1的整数d。
5. 公钥为(n,e),私钥为(n,d)。
加密过程:
1. 将明文信息m转化为整数,保证0<=m<n。
2. 计算密文c = m^e mod n。
解密过程:
1. 接收到密文c。
2. 计算明文信息m = c^d mod n。
以下是基于RSA的非对称加密体制的Python实现代码:
```python
# 生成RSA密钥对
import random
def is_prime(num):
"""
判断一个数是否为素数
"""
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
def gcd(a, b):
"""
求两个数的最大公约数
"""
while b:
a, b = b, a % b
return a
def extended_gcd(a, b):
"""
求ax + by = gcd(a, b)的解x和y
"""
if b == 0:
return 1, 0, a
x, y, gcd = extended_gcd(b, a % b)
return y, x - (a // b) * y, gcd
def mod_inverse(a, m):
"""
求a关于模m的逆元
"""
x, y, gcd = extended_gcd(a, m)
if gcd != 1:
raise Exception(f"{a}关于模{m}不存在逆元")
return x % m
def generate_key_pair(p, q):
"""
生成RSA密钥对
"""
if not (is_prime(p) and is_prime(q)):
raise Exception("p和q必须为素数")
n = p * q
phi = (p - 1) * (q - 1)
e = random.randint(1, phi - 1)
while gcd(e, phi) != 1:
e = random.randint(1, phi - 1)
d = mod_inverse(e, phi)
return (n, e), (n, d)
# 加密
def encrypt(m, public_key):
n, e = public_key
c = pow(m, e, n)
return c
# 解密
def decrypt(c, private_key):
n, d = private_key
m = pow(c, d, n)
return m
# 示例
p = 61
q = 53
public_key, private_key = generate_key_pair(p, q)
m = 123456
c = encrypt(m, public_key)
print(c)
m = decrypt(c, private_key)
print(m)
```
注意:在实际应用中,RSA加密算法需要使用大数运算,因此需要使用高精度库来进行计算。
阅读全文