python基于RSA的非对称加密体制,p,q为普通素数,p,q,e为可输入数字,明文信息为可输入数字
时间: 2024-02-28 07:52:45 浏览: 119
RSA算法基于非对称加密体制,其中p和q为两个大素数,n=pq为模数,φ(n)=(p-1)(q-1)为欧拉函数值,e为公钥指数,d为私钥指数,满足ed ≡ 1 (mod φ(n))。
加密过程:将明文信息m转换为整数m,计算密文c=m^e mod n。
解密过程:计算明文m=c^d mod n。
下面是一个基于RSA算法的Python代码示例,其中p、q、e、m为可输入数字:
```python
import random
# 判断一个数是否为素数
def is_prime(n):
if n <= 1:
return False
elif n <= 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i+2) == 0:
return False
i += 6
return True
# 生成一个指定位数的素数
def generate_prime(n):
while True:
p = random.randint(2**(n-1), 2**n-1)
if is_prime(p):
return p
# 计算两个数的最大公约数和贝祖等式解
def extended_gcd(a, b):
if a == 0:
return (b, 0, 1)
else:
gcd, x, y = extended_gcd(b % a, a)
return (gcd, y - (b // a) * x, x)
# 计算模反元素
def mod_inv(a, m):
gcd, x, y = extended_gcd(a, m)
if gcd != 1:
raise Exception('Modular inverse does not exist')
else:
return x % m
# 生成公钥和私钥
def generate_keypair(p, q, e):
n = p * q
phi = (p-1) * (q-1)
d = mod_inv(e, phi)
return ((n, e), (n, d))
# 加密函数
def encrypt(message, public_key):
n, e = public_key
m = int(message)
return pow(m, e, n)
# 解密函数
def decrypt(ciphertext, private_key):
n, d = private_key
c = int(ciphertext)
return pow(c, d, n)
# 示例代码
if __name__ == '__main__':
# 输入p、q、e、m
p = generate_prime(64)
q = generate_prime(64)
e = random.randint(2, (p-1)*(q-1)-1)
while True:
try:
d = mod_inv(e, (p-1)*(q-1))
break
except:
p = generate_prime(64)
q = generate_prime(64)
e = random.randint(2, (p-1)*(q-1)-1)
m = input("请输入明文信息:")
# 生成公钥和私钥
public_key, private_key = generate_keypair(p, q, e)
# 加密
ciphertext = encrypt(m, public_key)
print("密文信息为:", ciphertext)
# 解密
plaintext = decrypt(ciphertext, private_key)
print("解密后明文信息为:", plaintext)
```
需要注意的是,此代码示例中使用64位素数,实际使用中应该采用更大的素数以提高安全性。另外,此代码示例中的输入和输出都是字符串类型,需要根据需要进行转换。
阅读全文