Paillier 加法同态加密算法详细介绍-Toy模板网

这篇具有很好参考价值的文章主要介绍了Paillier 加法同态加密算法详细介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Paillier 加法同态加密算法详细介绍

1. 概述

Paillier 同态加密算法是一种非对称加密算法，由 Pascal Paillier 在 1999 年提出。它的独特之处在于其同态特性，即能在加密数据上直接进行运算而无需解密。这使得它在数据隐私保护、安全多方计算等领域有着广泛的应用。

2. 原理

Paillier 加密算法主要包括三个部分：密钥生成、加密和解密。

2.1 密钥生成

选择两个大素数 $p$ 和 $q$ : 这两个数越大，算法越安全。
计算 $\times q$ : 这是公钥的一部分。
计算 λ: λ 是 Carmichael’s totient 函数的输出，即最小公倍数 $\text{lcm}(p-1, q-1)$ 。
选择一个整数 g: g 的选取应满足 $\in \mathbb{Z}_{n^2}^*$ 。

公钥为 $(n, g)$ ，私钥为 $\lambda$ 。

2.2 加密

对于一个明文消息 $m$ ，加密过程如下：

选择一个随机数 $r$ : $r$ 是一个随机数，满足 $\in \mathbb{Z}_n^*$ 。
计算密文 $c$ : 使用公钥 $(n, g)$ 计算 $g^m \times r^n \mod n^2$ 。

2.3 解密

对于一个密文 $c$ ，解密过程如下：

计算 $c^\lambda \mod n^2$ 。
计算 $L (u)$ : 其中 $L$ 是一个特定的函数，定义为 $\frac{x-1}{n}$ 。
计算原始消息 $m$ : 使用私钥 $\lambda$ 和预先计算的 $L(g^\lambda \mod n^2)$ 的模逆元素，计算 $\times \text{modinv}(L(g^\lambda \mod n^2), n) \mod n$ 。

3. Paillier 加密算法的解密过程

假设我们有密文 $c$ ，公钥 $(n, g)$ 和私钥 $\lambda$ 。明文消息为 $m$ ，随机数 $r$ 用于加密过程。

3.1 加密过程回顾

加密过程定义为：

$g^m \cdot r^n \mod n^2$

3.2 解密步骤

计算 $u$

首先计算 $c^\lambda \mod n^2$ 。由于 $c = g^m r^n$ ，我们有：

$(g^m r^n)^\lambda \mod n^2$
利用 Carmichael 函数的性质

由于 $\lambda = \text{lcm}(p-1, q-1)$ ，根据 Carmichael 函数的性质，对于任意 $\in \mathbb{Z}_n^*$ ：

$a^\lambda \equiv 1 \mod n$

这意味着对于 $r^n$ ，有：

$(r^n)^\lambda \equiv 1 \mod n^2$ （把 $r^\lambda = kn+1$ 带入展开）
分析 $u$ 的表达式

通过将 $g^m$ 和 $r^n$ 分开，我们可以重写 $u$ 如下：

$(g^m)^\lambda \cdot (r^n)^\lambda \mod n^2$

我们可以将 $u$ 简化为：

$(g^m)^\lambda \cdot 1 \mod n^2$

$u = (kn+1)^m \mod n^2$
应用 $L$ 函数

接下来，我们应用 $L$ 函数到 $u$ 上。定义 $\frac{x - 1}{n}$ ，我们得到：

$L((kn+1)^m\mod n^2) = \frac{[(kn+1)^m\mod n^2] - 1}{n}=\frac{(1+m \cdot kn \mod n^2)-1}{n}=km \mod n^2$
计算模逆元素 $\mu$

在 Paillier 加密算法中，模逆元素 $\mu$ 是解密过程的关键部分。它是基于 $g$ 的一个特定幂的 $L$ 函数值的模逆元素。
- 计算 $L(g^\lambda \mod n^2)$
  
  首先，我们计算 $g^\lambda$ 在 $mod n^2$ 下的结果，然后应用 $L$ 函数。根据 $L$ 函数的定义（ $\frac{x - 1}{n}$ ），我们有：
  
  $L(g^\lambda \mod n^2) = \frac{(g^\lambda \mod n^2) - 1}{n} =\frac{(1+kn \mod n^2) - 1}{n}$
- 计算 $\mu$
  
  接下来，我们计算 $L(g^\lambda \mod n^2)$ 的模逆元素 $\mu$ ：
  
  $\mu = \text{modinv}(L(g^\lambda \mod n^2), n)$
  
  $\mu = [\frac{(1+kn \mod n^2) - 1}{n}]^{-1}=(k\mod n^2)^{-1}\mod n$
现在，计算原始消息 $m$

$\times \mu \mod n$

因此，通过计算 $\times \mu \mod n$ ，我们可以从加密后的 $c$ 中恢复出原始的明文消息 $m$ 。

4. 同态特性

Paillier 算法的主要特性是它的同态性质。具体来说，它支持同态加法和数乘操作：

同态加法: 对于两个密文 $c_1$ 和 $c_2$ ，其解密结果等同于它们对应明文的和的加密，即 $D(E(m_1) \times E(m_2) \mod n^2) = m_1 + m_2$ 。
同态加法（加密消息与明文整数）: 加密一个消息 $m$ ，然后将这个加密的结果与 $g^k \mod n^2$ （其中 $g$ 是公钥的一部分）相乘。解密这个乘积将得到 $m$ 与 $k$ 的和,即 $\text{D}(E(m) \times g^k \mod n^2) = m + k \mod n$
同态数乘: 对于一个密文 $c$ 和一个明文数 $k$ ，其解密结果等同于密文对应明文的 $k$ 倍的加密，即 $D(E(m)^k \mod n^2) = k \times m$ 。

5. 安全性保障

Paillier 算法的安全性主要依赖于大数分解的困难性。当选择的素数 $p$ 和 $q$ 足够大时，要破解该算法需要解决一个非常困难的数学问题——大数分解问题。因此，在实际应用中，应确保 $p$ 和 $q$ 的选取足够安全。

6. 结论

Paillier 加密算法由于其同态特性，在多方安全计算、数据隐私保护、云计算安全等领域有着重要应用。例如，在电子投票系统中，可以保证投票的隐私性和可验证性；在数据分析中，可以对加密数据进行处理而无需暴露原始数据。

Paillier 同态加密算法提供了一种在加密状态下进行计算的能力，对于保护数据隐私和安全性有着重要意义。尽管其计算过程相对复杂，但它的安全性和独特的同态特性使其在现代加密应用中占有一席之地。文章来源地址https://www.toymoban.com/news/detail-827889.html

7. 代码

import random
from sympy import isprime, mod_inverse


def generate_prime_candidate(length):
    """ 随机生成一个指定长度的奇数 """
    p = random.getrandbits(length)  # 获取一个指定长度的随机位
    p |= (1 << length - 1) | 1  # 确保最高位和最低位为1，从而生成一个奇数
    return p


def generate_large_prime(length):
    """ 生成一个指定长度的大素数 """
    p = 4  # 初始化一个非素数
    while not isprime(p):  # 循环直到找到一个素数
        p = generate_prime_candidate(length)  # 生成一个候选素数
    return p


def lcm(x, y):
    """ 计算两个数的最小公倍数 """
    greater = max(x, y)  # 找到x和y中的较大值
    while True:  # 循环直到找到最小公倍数
        if greater % x == 0 and greater % y == 0:  # 检查是否是公倍数
            return greater
        greater += 1


def generate_keypair(p, q):
    """ 生成Paillier公钥和私钥 """
    n = p * q  # 计算n，Paillier算法的核心参数
    g = n + 1  # 简单选择g为n + 1
    lambda_val = lcm(p - 1, q - 1)  # 计算lambda，使用最小公倍数
    return ((n, g), lambda_val)


def encrypt(pk, m):
    """ 使用公钥pk加密消息m, m < n """
    n, g = pk
    r = random.randint(1, n)  # 随机选择一个数r
    c = pow(g, m) * pow(r, n) % n ** 2  # 计算密文
    return c


def decrypt(pk, sk, c):
    """ 使用私钥sk解密密文c """
    n, g = pk
    lambda_val = sk

    # 计算 u = c^lambda mod n^2
    u = pow(c, lambda_val, n ** 2)

    # 计算 L(u)
    L_u = (u - 1) // n

    # 预先计算 L(g^lambda mod n^2) 的模逆元素
    L_g_lambda_inv = mod_inverse((pow(g, lambda_val, n ** 2) - 1) // n, n)

    # 还原原始消息
    return (L_u * L_g_lambda_inv) % n


def paillier_homomorphic_addition(pk, c1, c2):
    """
    实现Paillier同态加法
    :param c1: 加密的数字m1的密文
    :param c2: 加密的数字m2的密文
    :param n: 公钥的一部分
    :return: 同态加法的结果，即加密的m1+m2
    """
    n, g = pk
    return c1 * c2 % (n ** 2)


p = generate_large_prime(8)
q = generate_large_prime(8)
public_key, private_key = generate_keypair(p, q)
# 加密消息
plaintext1 = 500
plaintext2 = 621
ciphertext1 = encrypt(public_key, plaintext1)
print('密文:', ciphertext1)
print('明文:', decrypt(public_key, private_key, ciphertext1))
ciphertext2 = encrypt(public_key, plaintext2)
print('密文:', ciphertext2)
print('明文:', decrypt(public_key, private_key, ciphertext2))
ciphertext3 = paillier_homomorphic_addition(public_key, ciphertext1, ciphertext2)
print(f'同态明文{plaintext1}+{plaintext2}={plaintext1 + plaintext2}')
print('同态密文:', ciphertext3)
print('同态明文:', decrypt(public_key, private_key, ciphertext3))

print(decrypt(public_key, private_key, ciphertext1 * public_key[1] ** 100))

输出
密文: 411415825
明文: 500
密文: 397559680
明文: 621
同态明文500+621=1121
同态密文: 699397600
同态明文: 1121
600

到了这里，关于Paillier 加法同态加密算法详细介绍的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

Paillier 加法同态加密算法详细介绍