使用Python实现RSA加解密包括大整数幂取模算法

RSA加解密算法是一种非对称加密算法，使用了大整数幂取模算法。下面是Python实现RSA加解密的代码：

import random
import math


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_inv(a, m):
    (d, x, y) = extended_gcd(a, m)
    if d != 1:
        return None
    else:
        return x % m


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


def generate_prime():
    while True:
        p = random.randint(2 ** 511, 2 ** 512)
        if is_prime(p):
            return p


def generate_key():
    p = generate_prime()
    q = generate_prime()
    n = p * q
    phi = (p - 1) * (q - 1)
    while True:
        e = random.randint(2, phi - 1)
        if gcd(e, phi) == 1:
            break
    d = mod_inv(e, phi)
    return (n, e, d)


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


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


if __name__ == '__main__':
    # 生成密钥对
    (n, e, d) = generate_key()
    print("公钥：n =", n, ", e =", e)
    print("私钥：n =", n, ", d =", d)

    # 加密明文
    m = int(input("请输入明文："))
    c = encrypt(m, n, e)
    print("密文：", c)

    # 解密密文
    m = decrypt(c, n, d)
    print("解密结果：", m)

上面的代码实现了RSA加解密算法，并使用了大整数幂取模算法。其中，`gcd`函数实现了求最大公约数的算法，`extended_gcd`函数实现了扩展欧几里得算法，`mod_inv`函数实现了求逆元的算法，`is_prime`函数实现了判断素数的算法，`generate_prime`函数实现了生成素数的算法，`generate_key`函数实现了生成RSA密钥对的算法，`encrypt`函数实现了RSA加密算法，`decrypt`函数实现了RSA解密算法。在主函数中，我们先生成RSA的公钥和私钥，然后输入明文，加密明文并输出密文，最后解密密文并输出解密结果。