编程实现快速模幂运算公钥密码算法

下面是一个使用Python语言实现快速模幂运算公钥密码算法的示例代码：

import random

# 模幂运算函数
def mod_exp(base, exponent, modulus):
    result = 1
    while exponent > 0:
        # 如果指数是奇数，则先乘上一个base
        if exponent % 2 == 1:
            result = (result * base) % modulus
        # 将指数除以2，同时将base平方
        exponent = exponent // 2
        base = (base * base) % modulus
    return result

# 生成公钥和私钥函数
def generate_key_pair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    # 选择一个与phi互质的整数e
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    # 计算e的逆元d
    d = mod_inverse(e, phi)
    # 返回公钥和私钥
    return ((n, e), (n, d))

# 求最大公约数函数
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 encrypt(plaintext, public_key):
    n, e = public_key
    # 将明文转换成整数
    plaintext_int = int.from_bytes(plaintext.encode(), "big")
    # 对明文进行加密
    ciphertext_int = mod_exp(plaintext_int, e, n)
    # 将密文转换成字节串
    ciphertext = ciphertext_int.to_bytes((ciphertext_int.bit_length() + 7) // 8, "big")
    return ciphertext

# 解密函数
def decrypt(ciphertext, private_key):
    n, d = private_key
    # 将密文转换成整数
    ciphertext_int = int.from_bytes(ciphertext, "big")
    # 对密文进行解密
    plaintext_int = mod_exp(ciphertext_int, d, n)
    # 将明文转换成字节串
    plaintext = plaintext_int.to_bytes((plaintext_int.bit_length() + 7) // 8, "big").decode()
    return plaintext

# 测试代码
p = 61
q = 53
public_key, private_key = generate_key_pair(p, q)
plaintext = "Hello, world!"
ciphertext = encrypt(plaintext, public_key)
decrypted_plaintext = decrypt(ciphertext, private_key)
print("公钥:", public_key)
print("私钥:", private_key)
print("明文:", plaintext)
print("密文:", ciphertext)
print("解密后的明文:", decrypted_plaintext)

这个示例代码实现了一个基于RSA算法的公钥密码系统，可以对任意长度的明文进行加密和解密。生成公钥和私钥时，需要选择两个大质数p和q，并计算n=pq和phi=(p-1)(q-1)，然后选择一个与phi互质的整数e作为公钥，计算e的逆元d作为私钥。加密时，将明文转换成整数，使用公钥进行加密，并将密文转换成字节串。解密时，将密文转换成整数，使用私钥进行解密，并将明文转换成字符串。