编程实现rabin加密算法加解密

Rabin加密算法是一种非对称加密算法，它是基于大数分解难题的加密算法，其加密过程与RSA算法类似，但解密过程却与RSA不同，需要通过求解模数的因子来实现解密。以下是Rabin加密算法的实现步骤：

1. 选择两个大质数p和q，并计算模数N=p*q。
2. 将明文转化为数字M，使得M小于模数N。
3. 将M的平方对模数N取余，得到C=M^2 mod N，即为密文。
4. 使用数学方法求解模数N的两个因子p和q，然后就可以得到明文M。

解密过程相对于RSA算法更加困难，因为需要通过大数分解来求解模数的两个因子p和q。这也是Rabin加密算法的缺点之一。

以下是一个简单的Python实现Rabin加密算法的代码：

import random

# 生成大质数
def generate_prime():
    while True:
        p = random.randint(100000, 999999)
        if is_prime(p):
            return p

# 判断是否为质数
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# 计算最大公约数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 求解模数的两个因子
def factorize(N):
    x = int(N ** 0.5)
    y = x
    r = 1
    while r != 0:
        x = (x + y) % N
        y = (y ** 2 + r) % N
        r = (r + 1) % N
        d = gcd(abs(x - y), N)
        if d != 1 and d != N:
            return d, N // d

# 加密函数
def encrypt(M):
    p = generate_prime()
    q = generate_prime()
    N = p * q
    C = (M ** 2) % N
    return C, N

# 解密函数
def decrypt(C, N):
    p, q = factorize(N)
    mp = pow(C, (p + 1) // 4, p)
    mq = pow(C, (q + 1) // 4, q)
    yq, xp = gcd(p, q)
    x1 = (yq * p * mq + xp * q * mp) % N
    x2 = N - x1
    return x1, x2

# 测试
M = 1234567890
C, N = encrypt(M)
print("加密后的密文：", C)
M1, M2 = decrypt(C, N)
print("解密后的明文：", M1)