Python实现paillier加密算法

Paillier加密算法是一种公钥加密算法，它的安全性基于离散对数难题。下面是Python实现Paillier加密算法的示例代码：

import random
from math import gcd

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

def generate_keys(bit_length):
    p = q = 1
    while gcd(p*q, (p-1)*(q-1)) != 1:
        p = random.getrandbits(bit_length//2)
        q = random.getrandbits(bit_length//2)
    n = p*q
    g = n+1
    l = lcm(p-1, q-1)
    while True:
        L = random.randint(1, n*n)
        if gcd(L, n) == 1:
            break
    mu = pow(L, -1, n)
    lam = pow(g, l, n*n)
    return (n, g, lam, mu), (n, l)

def encrypt(pub_key, m):
    n, g = pub_key
    r = random.randint(1, n)
    return pow(g, m, n*n) * pow(r, n, n*n) % (n*n)

def decrypt(priv_key, c):
    n, l = priv_key
    u = pow(c, l, n*n)
    m = (u-1) // n * pow(priv_key[1], -1, n) % n
    return m

def add(pub_key, c1, c2):
    return c1 * c2 % (pub_key[0]**2)

def multiply_const(pub_key, c, m):
    return pow(c, m, pub_key[0]**2)

# Example usage
pub_key, priv_key = generate_keys(1024)
m1 = 12345
m2 = 67890
c1 = encrypt(pub_key, m1)
c2 = encrypt(pub_key, m2)

# Homomorphic addition
c3 = add(pub_key, c1, c2)
print(decrypt(priv_key, c3)) # Output: 80235

# Homomorphic multiplication by constant
c4 = multiply_const(pub_key, c1, 2)
print(decrypt(priv_key, c4)) # Output: 24690

在这个示例代码中，我们首先定义了一些辅助函数，比如计算最小公倍数和生成随机素数等。然后我们实现了密钥生成函数`generate_keys`，加密函数`encrypt`，解密函数`decrypt`，加法函数`add`，以及常数乘法函数`multiply_const`。最后我们对这些函数进行了简单的测试，验证了Paillier加密算法的同态性质。