python实现RSA算法

RSA算法是一种非对称加密算法，它的实现过程包括以下步骤：

1. 生成两个大素数 p、q，计算 n=pq，φ(n)=(p-1)(q-1)；
2. 选择一个整数 e，1<e<φ(n)，使得 gcd(e,φ(n))=1；
3. 计算 d=e⁻¹(mod φ(n))，即 d为e在模φ(n)下的逆元；
4. 将 n 和 e 公开，d 保密。加密时：C=M^e (mod n)，解密时：M=C^d (mod n)。

下面是Python实现RSA算法的示例代码：

import random
def gcd(a, b):
if a == 0:
return b
return gcd(b%a, a)
def inverse(a, m):
a = a%m
for i in range(1, m):
if (a*i) % m == 1:
return i
return 1
def is_prime(n):
if n<=1 or (n>2 and n%2==0):
return False
k = int(n**0.5)+1
for i in range(3, k, 2):
if n%i == 0:
return False
return True
def gen_prime():
while True:
p = random.randint(100, 1000)
if is_prime(p):
return p
def gen_key():
p = gen_prime()
q = gen_prime()
n = p*q
f = (p-1)*(q-1)
while True:
e = random.randint(1, f)
if gcd(e, f) == 1:
break
d = inverse(e, f)
return ((n, e), (n, d))
def encrypt(m, pub_key):
n, e = pub_key
c = pow(m, e, n)
return c
def decrypt(c, priv_key):
n, d = priv_key
m = pow(c, d, n)
return m
if __name__ == '__main__':
msg = 123
pub_key, priv_key = gen_key()
c = encrypt(msg, pub_key)
m = decrypt(c, priv_key)
print("Original Message:", msg)
print("Encrypted Message:", c)
print("Decrypted Message:", m)