pailler加密算法python

Paillier加密算法是一种公钥加密算法，其基本原理是利用大数的难以分解性质，将明文加密后得到密文，只有私钥持有者才能解密得到原始明文。以下是一个Python实现Paillier加密算法的示例代码：

import random
import math

# 求最大公约数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 求最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 生成两个大质数p和q
def generate_primes(nbits):
    while True:
        p = random.getrandbits(nbits)
        if is_prime(p):
            break
    while True:
        q = random.getrandbits(nbits)
        if is_prime(q) and p != q:
            break
    return p, q

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

# 计算L函数的值
def L(x, n):
    return (x - 1) // n

# 生成公钥和私钥
def generate_keys(nbits):
    p, q = generate_primes(nbits)
    n = p * q
    g = n + 1
    lcm_pq = lcm(p - 1, q - 1)
    while True:
        x = random.getrandbits(nbits * 2)
        if gcd(x, lcm_pq) == 1:
            break
    mu = pow(L(pow(g, lcm_pq, n * n), n), -1, n)
    return (n, g), (lcm_pq, mu)

# 加密明文m
def encrypt(pubkey, m):
    n, g = pubkey
    r = random.randint(1, n - 1)
    c = pow(g, m, n * n) * pow(r, n, n * n) % (n * n)
    return c

# 解密密文c
def decrypt(privkey, c):
    lcm_pq, mu = privkey
    n = lcm_pq + 1
    m = L(pow(c, lcm_pq, n * n), n) * mu % n
    return m

# 示例代码
nbits = 1024
pubkey, privkey = generate_keys(nbits)
m = 123456789
c = encrypt(pubkey, m)
print("明文：", m)
print("密文：", c)
print("解密后的明文：", decrypt(privkey, c))

需要注意的是，Paillier加密算法的安全性依赖于大数的难以分解性质，因此在实际应用中需要使用足够大的密钥长度。本示例代码使用1024位的密钥长度，可以保证一定的安全性。