算法介绍

Paillier 算法系统主要包含三个子算法：Gen, Enc, Dec，分别是密钥生成算法、加密算法以及解密算法。

密钥生成

密钥生成的过程如下：

选取大素数 $p,q$，满足 $\operatorname{gcd}(pq, (p-1)(q-1))=1$，其中 $gcd$ 表示最大公约数，实际上这里的$(p-1)(q-1)=\phi(n)$；
计算$n=pq, \lambda = \operatorname{lcm}(p-1,q-1)$，其中 $\operatorname{lcm}$ 表示最小公倍数；
定义 $L(x) = \frac{x-1}{n}$；
随机选取小于 $n^2$ 的正整数 $g$，并使得存在 $\mu = (L(g^\lambda \mod n^2))^{-1} \mod n$；
公钥为 $(n,g)$，私钥为 $(\lambda, \mu)$。

加密

假设明文为 $m$；
随机选择 $r$，满足$r \in Z_{n^2}^{*}$，即 $r$ 在 $n^2$ 下存在乘法逆元。一种充分条件是选取与 $n$ 互质的 $r$ 即可；
计算密文 $c=g^m \cdot r^n \mod n^2$。

解密

解密的过程很简单，为：

计算明文 $m = L(c^\lambda \mod n^2) \cdot \mu \mod n$

算法案例

我们假设 $p=7,q=11$，那么有 $n=77, n^2=5929$，同时呢有 $\lambda = \operatorname{lcm}(6,10) = 30$。我们选个 $g$，假设 $g=5652$ 吧。然后再算一下$\mu$，我这里就没仔细算了。

也就是说公钥为：$(n, g)=(77,5652)$，私钥为$(\lambda, \mu)=(30, 74)$。

然后开始加密了，我们假设明文$m=42$，随机数$r=23$，然后加密过程为：

$c = 5652^{42} \cdot 23^{77} \mod 5929 = 4624$

解密的过程如下：

$\begin{align} m &= L(c^\lambda \mod n^2) \cdot \mu \mod n \\ &= L (4624^{30} \mod 5929) \cdot 74 \mod 77\\ &= L(4852) \cdot 74 \mod 77\\ &= 63 \cdot 74 \mod 77 \\ &= 42 \end{align}$

因此就解密成功了。

运行代码的话，可以用以下代码进行测试：

# @author S.L.

import sunCryptBasis as Crypt
import sympy
import numpy as np


class Paillier:
    def __init__(self, p=0, q=0, g=0):
        self.__p = p
        self.__q = q
        self.__n = self.__p * self.__q
        self.__lambda = sympy.lcm(self.__p - 1, self.__q - 1)

        self.__g = g
        self.__u = sympy.mod_inverse(self.__L(g**self.__lambda % self.__n**2), self.__n)
        print("p,q,n,lambda,g,u = ", self.__p, self.__q, self.__n, self.__lambda, self.__g, self.__u)

    def __L(self, x):
        return (x-1) / self.__n

    def generate_key(self, key_bits=10):
        # choose p and q, and calculate n and lambda

        while True:
            self.__p = sympy.ntheory.generate.randprime(2**key_bits, 2**(key_bits+1))
            self.__q = sympy.ntheory.generate.randprime(2**key_bits, 2**(key_bits+1))
            self.__n = self.__p * self.__q
            if sympy.gcd(self.__n, (self.__p - 1) * (self.__q - 1)) == 1:
                break
        self.__lambda = sympy.lcm(self.__p - 1, self.__q - 1)

        # choose g
        # todo
        while True:
            self.__g = np.random.randint(1, n**2)
            self.__u = sympy.mod_inverse(self.__L(g**self.__lambda % self.__n**2), self.__n)

    def encrypt(self, m, r=0):
        r = sympy.ntheory.randprime(3, self.__n) if r == 0 else r
        return self.__g ** m * r ** self.__n % (self.__n ** 2)

    def decrypt(self, c):
        return self.__L(c**self.__lambda % (self.__n**2)) * self.__u % self.__n

    def get_public_key(self):
        return self.__n, self.__g

    def get_private_key(self):
        return self.__lambda, self.__u

然后下面是加解密测试的代码：

pai = Paillier(p=7, q=11, g=5652)
# pai = Paillier()
# pai.generate_key()
x_1, x_2 = 13, 25

# 加解密测试
print("\n encrypt test")
y_1, y_2 = pai.encrypt(x_1, r=23), pai.encrypt(x_2, r=23) # 这两个r可以不同
x_1, x_2 = pai.decrypt(y_1), pai.decrypt(y_2)
print(x_1, x_2)

输出为：

p,q,n,lambda,g,u =  7 11 77 30 5652 74
Paillier:: initialized

 encrypt test
13 25

性质

Paillier 加密系统主要有以下三个性质：

Homomorphic addition: $[x_1] \cdot [x_2] = [x_1 + x_2]$，也可以写成：$[x_1] \oplus[x_2]=[x_1+x_2]$；
Homomorphic multiplication: $[x_1]^{x_2}=[x_1 \cdot x_2]$，也可以写成：$x_1 \otimes [x_2] = [x_1 \cdot x_2]$；
Homomorphic dot product: 利用上面两个性质，就可以做两个向量的点乘了，参考论文《Privacy Preserving Vertical Federated Learning for Tree-based Models》当中的2.1节介绍。对于向量 $\boldsymbol{x},\boldsymbol{v}$，有：$ \boldsymbol{x} \odot [\boldsymbol{v}] = (x_1 \otimes [v_1]) \oplus … \oplus (x_m \otimes [v_m])=[\boldsymbol{x} \cdot \boldsymbol{v}]$。

加法同态证明

若对于数据 $x_1, x_2$，有：

$\begin{align} [x_1] &= g^{x_1} \cdot r_1^n \mod n^2\\ [x_2] &= g^{x_2} \cdot r_2^n \mod n^2 \end{align}$

则有：

$[x_1][x_2] = g^{x_1+x_2} \cdot (r_1 r_2)^n \mod n^2 = [x_1+x_2]$

乘法同态证明

没看懂，以后看懂了再补充。

性质测试

# 加法同态测试，即 [x_1] * [x_2] = [x_1 + x_2]
print("\n homomorphic test 1")
y_3 = y_1 * y_2
x_3 = pai.decrypt(y_3)
print(x_3)

# 验证 [m_1]^m2 mod n^2 = [m_1 * m_2]
print("\n homomorphic test 2")
n = pai.get_public_key()[0]
x_tmp_1 = pai.decrypt(pai.encrypt(x_1)**x_2 % n**2)
x_tmp_2 = (x_1 * x_2) % n
print(x_tmp_1, x_tmp_2)

输出结果为：

 homomorphic test 1
38

 homomorphic test 2
17 17

第二个都是17是因为要在模 $n$ 的范围内才满足同态性质，因为：$13 \cdot 25 \pmod {77}=17$。

参考内容：

本篇内容到这里就结束了，若想知道更多和信息安全有关的技术可在公众号留言。识别以下二维码可以成为本公众号的小粉丝，关注更多前沿技术。

微信公众号