用python实现rsa算法

实现 RSA 算法可以使用 python 自带的数学库，例如 `math` 和 `random`，也可以使用第三方的数学库，例如 `pycryptodome`。

具体的实现步骤如下：

1. 选择两个大质数 p 和 q，并计算出 n = p * q，以及 φ(n) = (p - 1) * (q - 1)。
2. 选择一个整数 e，使得 1 < e < φ(n) 且 e 与 φ(n) 互质。
3. 计算出 d，使得 d * e ≡ 1 (mod φ(n))。
4. 利用 n 和 e，以及利用 n 和 d 对原文进行加密和解密。

以下是一个简单的 Python 代码实现：

import math

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def encrypt(m, e, n):
    c = pow(m, e, n)
    return c

def decrypt(c, d, n):
    m = pow(c, d, n)
    return m

def generate_keys(p, q):
    n = p * q
    phi_n = (p - 1) * (q - 1)

    e = 3
    while gcd(e, phi_n) != 1:
        e += 2

    d = 2
    while (d * e) % phi_n != 1:
        d += 1

    return ((e, n), (d, n))

public, private = generate_keys(61, 53)
print("Public key: ", public)
print("Private key: ", private)

message = 42
encrypted_message = encrypt(message, *public)
print("Encrypted message: ", encrypted_message)

decrypted_message = decrypt(encrypted_message, *private)
print("Decrypted message: ", decrypted_message)

请注意，这是一个简单的 RSA 实现，不应该用于生产环境，因为它存在一些安全漏洞，例如暴力攻击。