python实现RSA密钥生成
时间: 2023-07-11 16:33:31 浏览: 59
RSA加密算法是一种非对称加密算法,其密钥由公钥和私钥组成,其中公钥用于加密,私钥用于解密。下面是Python实现RSA密钥生成的代码:
```python
import random
import math
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def is_prime(n):
if n == 2 or n == 3:
return True
if n < 2 or n % 2 == 0:
return False
if n < 9:
return True
if n % 3 == 0:
return False
r = int(math.sqrt(n))
f = 5
while f <= r:
if n % f == 0:
return False
if n % (f + 2) == 0:
return False
f += 6
return True
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError("Both numbers must be prime.")
elif p == q:
raise ValueError("p and q cannot be equal")
n = p * q
phi = (p-1) * (q-1)
e = random.randrange(1, phi)
g = gcd(e, phi)
while g != 1:
e = random.randrange(1, phi)
g = gcd(e, phi)
d = modinv(e, phi)
return ((e, n), (d, n))
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise ValueError('Modular inverse does not exist')
else:
return x % m
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
p = 61
q = 53
public_key, private_key = generate_keypair(p, q)
print("Public key: ", public_key)
print("Private key: ", private_key)
```
在上述代码中,generate_keypair()函数用于生成公钥和私钥,其中p和q为两个质数,n为p和q的乘积,phi为(p-1) * (q-1),e为一个介于1和phi之间的随机数,d为e的模phi的逆元。
egcd()函数用于求解模逆元,is_prime()函数用于判断一个数是否为质数,gcd()函数用于求解两个数的最大公约数。