同态加密算法之paillier算法

他是书安

1247人浏览 · 2023-06-11 15:10:56

他是书安 · 2023-06-11 15:10:56 发布

同态加密算法

半同态加密算法
全同态加密算法

算法过程

秘钥生成，现在假设有两方，分别是A B，两者之间需要进行加密通信。
- 首先A选择两个非常大的素数p q
- 计算p和q的乘积n,n=p*q
- 计算 (p-1)和(q-1)的最小公倍数λ，λ=lcm(p-1,q-1)
- 选择随机数g,g∈ $Z_{n^{2}}^{*}$
- 定义函数 $L(x)=\frac{x-1}{n}$ , 并计算模反元素 $u=L(g^{\lambda }modn^{2})^{-1} mod n$
- 生成公钥对public-key （n,g）
- 生成私钥对private-key (λ,μ)
加密过程，现在假设b要加密明文m，且b已知公钥(n,g)
- 选择一个随机数r,0<r<n
- 计算加密后的密文, $c=(g^{\lambda }\cdot r ^{n})modn^{2}$
解密过程，现在假设c是b方发送的密文
- 计算明文， $m=L(c^{\lambda } mod n^{2})\cdot \mu mod n$

算法理论

算法理论部分参考博主算法理论部分的证明，先去看这位博主的推理过程，下面我给出一些证明过程时我的一些疑问与解答
- 由二项式定理展开可知， $(1+n)^{x}\equiv 1+nx(mod\ n^{2})$
- 可以作出假设，令 $y=(1+n)^{x}mod\ n^{2}$
- 此时可以简化成为， $x\equiv ^{\frac{y-1}{n}}mod\ n^{2}$ (为什么不是 $\frac{y-1}{n}\equiv x mod\ n^{2}$ ) ①
- 此时可以令， $L(\mu ) = \frac{\mu -1}{n }$ ,把y的值带入L(μ)，得到结论
- $L((1+n^{x})mod\ n^{2})\equiv x(mod\ n)$
- 此时，带入当 $(1+n)^{x}=g^{\lambda }$ 时，即 $g=1+n;\ \lambda =x$ ,可以得到结论
- $\mu = \lambda ^{-1}\ ;g=n+1$ ，证明过程如下（纯手敲公式太麻烦啦！！偷个懒哈）
- 此外还能得到结论， $r^{\lambda n}mod\ n^{2}=1$ (此处使用了卡米切尔定理)，证明过程如下
- 此时就可以计算加法的同态性了证明过程如下，用到的公式是这两个
- $\mu = \lambda ^{-1}\ ;g=n+1$
一些疑问与解答
- ZN*是个什么东西，为什么m要在其范围内？
  - ZN∗表示模n的乘法群,也就是{1,2,...,n-1}。由于paillier算法基于RSA算法,要求明文m的范围在n的乘法群内,这是为了满足gcd(m, n)=1,保证m的逆元素存在。如果m超出这个范围,将无法正确解密。
- 为什么g的选择范围在ZN^2*内？
  - 确保任意g^x都在ZN^2∗内;使得c也在ZN^2∗内,以完成正确的加密运算
- 在算法理论部分提到的g=n+1是必须满足的？
  - 是为了简化计算,加快算法速度。它不是必须的,算法也可以选择其他g值,只要保证gcd(L(g^x mod n^2), n)=1(x为任意整数),算法依然正确。
- paillier算法实现的到底是什么？
  - paillier算法实现的是加法同态。我们一般希望密文计算的结果和我们明文计算的结果相同，所以对于密文上是如何计算的不做要求。这时我们在明文上实现了加法的目的，就叫它加法同态。密文乘等于明文加（c1*c2）= m1+m2
- 为什么μ的定义为:μ = L(g^λ mod n^2)^-1 mod n？
  - 1. 在解密过程中,我们需要对密文c进行除以g的λ次方的运算,以恢复明文m。
  - 2. 但是在整数环Zn上只有乘法运算,没有除法运算。所以无法直接进行c / (g^λ)的运算。
- 加密过程为什么要定义为c = g^m * r^n mod n^2呢？为什么加密要模n^2呢？
  - 隐藏明文m的具体值,只泄露模n^2的值,满足算法安全性;
  - 引入随机数r增加密文随机性,提高算法安全性;
  - 2. 使得解密算法成立,可以正确恢复明文m。
    Paillier算法的解密函数为:m = L(c^λ mod n^2) * μ mod n
    这里λ为私钥,μ为计算立方根的辅助参数。
    只有当采用模n^2运算时,c^λ mod n^2才能通过λ求出m的立方根,并且与μ相乘得到m。
    如果采用模n运算,则c^λ mod n无法通过λ求出m的立方根,解密算法将无法工作,无法正确恢复明文m。
  - 1. 保证密文c的大小与明文m相当,从而隐藏明文信息。
    如果直接采用模n,则由于n远大于m,密文c的大小会远大于m,这会泄露明文信息,影响算法的安全性。
    采用模n^2,可以使密文c的大小与m相当,避免泄露明文信息。
- 为什么解密要定义为L(c^λ mod n^2) * μ mod n呢？
  - 得到c^λmodn^2。这一步的目的是将密文c还原到Zn上。然后调用L算法计算乘法逆元,目的是为了在Zn上进行除法运算
  - 将立方根与μ相乘可以消除负解,得到唯一的m;
  - 采用模n运算隐藏m的具体大小,只泄露在[0,n-1]范围内的值,保证安全性。

其实我看完算法后也还有很多不理解，只大概了解了加解密的规则与过程。更多需要深挖的知识我没去看，所以有些疑问不能解答是我水平太低啦！！！如果有问题可以在评论区提问，也可以参考这篇文章哈
https://blog.csdn.net/qq_40589204/article/details/116310125

我觉得过程讲的很细，但是中间有一些规则为什么要这么定义并没有抛出来，这部分还需要自己去找答案。加油！