用大整数幂取模算法和RSA模幂乘算法实现RSA算法

RSA算法是一种非常常见的加密算法，其核心原理是基于大整数幂取模算法和RSA模幂乘算法。下面是用Python实现RSA算法的代码：

import random

def is_prime(num):
    if num <= 1:
        return False
    elif num <= 3:
        return True
    elif num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

def generate_prime_number():
    while True:
        num = random.randint(100, 1000)
        if is_prime(num):
            return num

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

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

def generate_keys():
    p = generate_prime_number()
    q = generate_prime_number()
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = random.randint(3, phi_n - 1)
    while gcd(e, phi_n) != 1:
        e = random.randint(3, phi_n - 1)
    _, d, _ = extended_euclidean_algorithm(e, phi_n)
    if d < 0:
        d += phi_n
    return (n, e), (n, d)

def encrypt(message, public_key):
    n, e = public_key
    return pow(message, e, n)

def decrypt(ciphertext, private_key):
    n, d = private_key
    return pow(ciphertext, d, n)

if __name__ == '__main__':
    message = 123456
    public_key, private_key = generate_keys()
    ciphertext = encrypt(message, public_key)
    plaintext = decrypt(ciphertext, private_key)
    print('Message:', message)
    print('Public key:', public_key)
    print('Private key:', private_key)
    print('Ciphertext:', ciphertext)
    print('Plaintext:', plaintext)

代码中的`generate_prime_number`函数用于生成一个随机的质数，`gcd`函数用于计算两个数的最大公约数，`extended_euclidean_algorithm`函数用于计算两个数的扩展欧几里得算法，`generate_keys`函数用于生成RSA算法的公钥和私钥，`encrypt`函数用于加密明文，`decrypt`函数用于解密密文。

在代码中，我们使用了随机数生成器来生成质数，这是因为RSA算法的安全性取决于质数的大小和随机性。此外，我们还使用了扩展欧几里得算法来计算私钥，这是因为求解模反元素的过程可以用扩展欧几里得算法来实现。

最后，我们测试了RSA算法的加密和解密功能，并输出了测试结果。