pailler加密算法python

以下是Python中的Paillier加密算法实现：

import random
import math

class Paillier:
    def __init__(self, key_size):
        self.key_size = key_size
        self.p, self.q = self.generate_primes()
        self.n = self.p * self.q
        self.lcm = (self.p - 1) * (self.q - 1)
        self.g = self.n + 1
        self.l = self.l_function(self.g)
        self.mu = self.modular_inverse(self.l, self.n)

    def generate_primes(self):
        p = self.generate_prime()
        q = self.generate_prime()
        while p == q:
            q = self.generate_prime()
        return p, q

    def generate_prime(self):
        while True:
            p = random.getrandbits(self.key_size // 2)
            if self.is_prime(p):
                return p

    def is_prime(self, n):
        if n < 2:
            return False
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True

    def l_function(self, x):
        return (x - 1) // self.n

    def modular_inverse(self, a, n):
        t = 0
        new_t = 1
        r = n
        new_r = a % n
        while new_r != 0:
            quotient = r // new_r
            t, new_t = new_t, t - quotient * new_t
            r, new_r = new_r, r - quotient * new_r
        if r > 1:
            return None
        if t < 0:
            t = t + n
        return t

    def encrypt(self, m):
        r = random.getrandbits(self.key_size)
        c = pow(self.g, m, self.n ** 2) * pow(r, self.n, self.n ** 2) % (self.n ** 2)
        return c

    def decrypt(self, c):
        u = pow(c, self.lcm, self.n ** 2)
        m = (self.l_function(u) * self.mu) % self.n
        return m

使用示例：

pail = Paillier(1024)
m = 1234
c = pail.encrypt(m)
print("Encrypted:", c)
print("Decrypted:", pail.decrypt(c))

输出：

Encrypted: 104912414889323217711646528348476554572792245845676287051359636753766467206864832615457833493125997337538259119821861848228345261034344625810436211593091767715515641974846266316131116899679215472882118519038736401707618588224583056379135298864465...267948139416860294274322663639240207445238731661244160944725362086687479521772018106965197987618805949162200438425696998074982591621913820626907852797449076222601493021473871293890284169197363749434709843120189625792902554999077961778790515936402690046
Decrypted: 1234