RSA加密算法实现python

RSA加密算法是非对称加密算法，它的实现需要以下步骤：

1. 选择两个不同的大素数 p 和 q。
2. 计算 n = p * q，其中 n 是模数。
3. 计算欧拉函数 φ(n) = (p-1) * (q-1)。
4. 选择一个整数 e，使得 1 < e < φ(n)，且 e 与 φ(n) 互质。
5. 计算 e 的模反元素 d，满足 (d * e) % φ(n) = 1。
6. 公钥为 (e, n)，私钥为 (d, n)。
7. 加密时，将明文 m 转换为整数，计算密文 c = (m^e) % n。
8. 解密时，将密文 c 计算为明文 m = (c^d) % n。

下面是一个简单的Python代码实现RSA加密算法：

import random

def is_prime(num):
    # 判断一个数是否为素数
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def gcd(a, b):
    # 计算最大公约数
    while b != 0:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    # 计算模反元素
    if gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

def generate_keypair():
    # 生成公钥和私钥
    p = random.randint(100, 1000)
    while not is_prime(p):
        p = random.randint(100, 1000)
    q = random.randint(100, 1000)
    while not is_prime(q) or q == p:
        q = random.randint(100, 1000)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = random.randint(2, phi_n - 1)
    while gcd(e, phi_n) != 1:
        e = random.randint(2, phi_n - 1)
    d = mod_inverse(e, phi_n)
    return ((e, n), (d, n))

def encrypt(message, public_key):
    # 加密
    e, n = public_key
    encrypted_message = [pow(ord(c), e, n) for c in message]
    return encrypted_message

def decrypt(encrypted_message, private_key):
    # 解密
    d, n = private_key
    decrypted_message = [chr(pow(c, d, n)) for c in encrypted_message]
    return "".join(decrypted_message)

# 测试
message = "Hello, RSA!"
public_key, private_key = generate_keypair()
encrypted_message = encrypt(message, public_key)
decrypted_message = decrypt(encrypted_message, private_key)

print("原始消息:", message)
print("加密后:", encrypted_message)
print("解密后:", decrypted_message)

以上代码仅为简单示例，实际应用中需要考虑更多的安全性问题，并且可能需要处理大整数计算的限制。在使用时请注意谨慎处理私钥，避免私钥泄露导致加密信息被解密。