Rabin算法加解密python

Rabin算法是一种非对称加密算法，其加解密过程与RSA算法类似。下面是Python实现Rabin算法的加解密过程：

1. 生成公私钥对

import random
from math import gcd

def generate_key_pair():
    # 生成两个随机质数p和q
    p = generate_prime_number()
    q = generate_prime_number()

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

    # 选择一个随机数e，要求e与phi(n)互质
    e = random.randint(2, phi_n - 1)
    while gcd(e, phi_n) != 1:
        e = random.randint(2, phi_n - 1)

    # 计算d，使得d为e模phi(n)的逆元
    d = mod_inverse(e, phi_n)

    # 返回公私钥对
    return ((n, e), (n, d))

def generate_prime_number():
    # 生成一个随机数，检查是否为质数
    while True:
        p = random.randint(2**15, 2**16)
        if is_prime(p):
            return p

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 mod_inverse(a, m):
    # 计算a模m的逆元
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return -1

2. 加密数据

def encrypt(plaintext, public_key):
    # 将明文转换为整数
    plaintext_int = int.from_bytes(plaintext.encode(), 'big')

    # 获取公钥n和e
    n, e = public_key

    # 加密数据
    ciphertext_int = pow(plaintext_int, 2, n)

    # 返回密文
    return ciphertext_int.to_bytes((ciphertext_int.bit_length() + 7) // 8, 'big')

3. 解密数据

def decrypt(ciphertext, private_key):
    # 获取私钥n和d
    n, d = private_key

    # 解密数据
    plaintext_int = pow(ciphertext, (p + 1) // 4, p) # 对p取模
    plaintext_int += pow(ciphertext, (q + 1) // 4, q) * n % p # 对q取模
    plaintext_int %= n # 合并结果

    # 将整数转换为明文
    plaintext = plaintext_int.to_bytes((plaintext_int.bit_length() + 7) // 8, 'big').decode()

    # 返回明文
    return plaintext

注意：Rabin算法的安全性存在争议，不建议在生产环境中使用。