实现RSA非对称式加密算法

RSA 是一种非对称加密算法，它可以用于数据加密和数字签名。下面是 RSA 加密算法的实现过程：

1. 选择两个大素数 p 和 q，并计算 n = p*q。
2. 计算欧拉函数 φ(n) = (p-1)*(q-1)。
3. 选择一个小于 φ(n) 的整数 e，使得 e 和 φ(n) 互质。
4. 计算 e 的模反元素 d，即满足 (d*e) mod φ(n) = 1 的整数 d。可以使用扩展欧几里得算法来计算 d。
5. 公钥为 (n, e)，私钥为 (n, d)。
6. 加密时，将消息 m 转换成整数 M，然后计算密文 C = M^e mod n。
7. 解密时，将密文 C 计算出明文 M = C^d mod n。

下面是 Python 实现 RSA 加密算法的代码：

import random

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)

def mod_inverse(a, m):
    d, x, y = extended_gcd(a, m)
    if d != 1:
        raise ValueError("No inverse exists")
    else:
        return x % m

def generate_key_pair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    d = mod_inverse(e, phi)
    return ((n, e), (n, d))

def encrypt(msg, public_key):
    n, e = public_key
    m = int.from_bytes(msg.encode(), 'big')
    c = pow(m, e, n)
    return c.to_bytes((c.bit_length() + 7) // 8, 'big').decode()

def decrypt(cipher, private_key):
    n, d = private_key
    c = int.from_bytes(cipher.encode(), 'big')
    m = pow(c, d, n)
    return m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()

# 选择两个大素数 p 和 q
p = 61
q = 53

# 生成公钥和私钥
public_key, private_key = generate_key_pair(p, q)
print("公钥：", public_key)
print("私钥：", private_key)

# 加密和解密
msg = "Hello, world!"
cipher = encrypt(msg, public_key)
print("密文：", cipher)
plaintext = decrypt(cipher, private_key)
print("明文：", plaintext)

需要注意的是，由于 RSA 加密算法使用了大整数计算，因此在处理大数时需要使用适当的库来避免溢出等问题。在 Python 中，可以使用内置的 `pow()` 函数来计算幂取模，也可以使用第三方库（如 `gmpy2` ）来进行大整数运算。