拉宾公钥密码 Python实现

拉宾公钥密码（Rabin Cryptosystem）是一种非对称加密算法，它是基于大数分解问题的。下面是一个用Python实现拉宾公钥密码的例子：

import random

# 生成两个大素数p和q
def generate_prime():
    primes = [i for i in range(2, 100) if all(i % j != 0 for j in range(2, int(i**0.5)+1))]
    p = random.choice(primes)
    q = random.choice(primes)
    return p, q

# 计算模反元素
def mod_inverse(a, m):
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# 加密
def encrypt(message, n):
    return (message ** 2) % n

# 解密
def decrypt(ciphertext, p, q):
    n = p * q
    mp = (ciphertext ** ((p + 1) // 4)) % p
    mq = (ciphertext ** ((q + 1) // 4)) % q
    yp = mod_inverse(p, q)
    yq = mod_inverse(q, p)
    r1 = (yp * p * mq + yq * q * mp) % n
    r2 = n - r1
    r3 = (yp * p * mq - yq * q * mp) % n
    r4 = n - r3
    return r1, r2, r3, r4

# 生成公钥和私钥
def generate_keys():
    p, q = generate_prime()
    n = p * q
    return n, p, q

# 测试
message = 123456789
n, p, q = generate_keys()
ciphertext = encrypt(message, n)
plaintexts = decrypt(ciphertext, p, q)

print("加密后的密文：", ciphertext)
print("解密后的明文：", plaintexts)