rsa公钥加密算法代码实现

以下是 Python 代码实现 RSA 公钥加密算法：

import random
import math

# 生成指定位数的质数
def generate_prime_number(num_bits):
    while True:
        p = random.getrandbits(num_bits)
        if is_prime(p):
            return p

# 判断一个数是否为质数
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % 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

# 生成 RSA 公钥和私钥
def generate_rsa_keys(num_bits):
    # 生成两个不同的质数
    p = generate_prime_number(num_bits // 2)
    q = generate_prime_number(num_bits // 2)
    while p == q:
        q = generate_prime_number(num_bits // 2)

    # 计算 n 和 phi(n)
    n = p * q
    phi_n = (p-1) * (q-1)

    # 选择一个公钥 e
    e = random.randrange(2, phi_n)
    while gcd(e, phi_n) != 1:
        e = random.randrange(2, phi_n)

    # 计算私钥 d
    d = mod_inverse(e, phi_n)

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

# 加密函数
def rsa_encrypt(public_key, plaintext):
    n, e = public_key
    return pow(plaintext, e, n)

# 解密函数
def rsa_decrypt(private_key, ciphertext):
    n, d = private_key
    return pow(ciphertext, d, n)

# 测试
if __name__ == '__main__':
    # 生成公钥和私钥
    public_key, private_key = generate_rsa_keys(1024)

    # 明文
    plaintext = 1234567890

    # 加密
    ciphertext = rsa_encrypt(public_key, plaintext)

    # 解密
    decrypted_plaintext = rsa_decrypt(private_key, ciphertext)

    # 输出结果
    print("明文：", plaintext)
    print("密文：", ciphertext)
    print("解密后的明文：", decrypted_plaintext)

说明：

- `generate_prime_number(num_bits)`：生成一个 num_bits 位的质数。
- `is_prime(n)`：判断一个数是否为质数。
- `gcd(a, b)`：求 a 和 b 的最大公约数。
- `mod_inverse(a, m)`：求 a 在模 m 意义下的逆元。
- `generate_rsa_keys(num_bits)`：生成 RSA 公钥和私钥。
- `rsa_encrypt(public_key, plaintext)`：使用公钥进行加密。
- `rsa_decrypt(private_key, ciphertext)`：使用私钥进行解密。
- 测试部分生成一个公钥和私钥，然后对一个明文进行加密和解密。