The Paillier Cryptosystem

同态加密–Paillier加密

0x01 基础知识

选择两个长度相同的大素数$p,q$。计算$N=pq$，会有以下三个结论：

1.$gcd(N,\phi(N))=1$

2.选择$a\geq0$,则有$(1+N)^a=(1+aN)modN^2$

3.构造的同构函数$f: \mathbb{Z}_N × \mathbb{Z}^{*}_N →\mathbb{Z}^{*}_{N^2}$。其中$f(a,b)=[(1+N)^a\cdot b^N]modN^2$

0x02 命题证明

• $gcd(N,\phi(N))=1$

  思路：$gcd(p,\phi(N))=1,gcd(q,\phi(N))=1$

  假设$p>q$：

  • 则$p>p-1>q-1$,即$gcd(p,\phi(N))=1$。

  • 若$gcd(p-1,q)≠1$,则$(p-1)/q\geq2$,这与长度相等的条件不符；易知$gcd(q-1,q)=1$；综上$gcd(q,\phi(N))=1$

• 选择$a\geq0$,则有$(1+N)^a=(1+aN)modN^2$

  由二项展开定理展开，进行模运算只剩两项。

  易知$(1+N)$模$N^2$的阶是$N$

• 同构$f$证明

  思路：先证明是函数是双射，再证明保持运算。

  群的封闭性：

  需要保证在此运算能够形成群：

  $\forall a \in \mathbb{Z}_N,b\in\mathbb{Z}^*_N,c=[(1+N)^a\cdot b^N]modN^2$

  因为$gcd((1+N),N^2)=1,gcd(b,N^2)=1,b\in\mathbb{Z}^*_N$

  所以$gcd((1+N)^a\cdot b^N,N^2)=1,c \in\mathbb{Z}^{*}_{N^2}$

  双射证明：

  既单又满

  • 单射证明：$若F(a)=F(b),则a=b$

  假设$f(a,b)=f(c,d)$,则$\frac{f(a,b)}{f(c,d)} =1modN^2$。即$(1+N)^{a-c}(\frac{b}{d})^NmodN^2=1modN^2$

  $$\begin{aligned} &\because b,d\in\mathbb{Z}^*_N \subset \mathbb{Z}^*_{N^2},\therefore b,d存在逆元.\\ &不妨设\ \alpha=\frac{b}{d},\alpha \in \mathbb{Z}^*_{N^2}:\alpha^{\phi(N^2)}modN^2=1modN^2\\ &\phi(N^2)=\phi(p^2q^2)=N^2*(1-1/p)(1-1/q)=pq(p-1)(q-1)=N*\phi(N)\\ &两边同时取\phi(N)次方可得：(1+N)^{(a-c)\phi(N)}(\alpha)^{\phi(N^2)}modN^2=1modN^2 \end{aligned}$$

  即$(1+N)^{(a-c)\phi(N)}modN^2=1modN^2$,由$(1+N)$模$N^2$的阶是$N$,得：

  $N|(a-c)\phi(N)→gcd(N,\phi(N))=1,N|(a-c)$

  由$a,c\in \mathbb{Z}_N$,只有$a=c,N|(a-c)$。

  将$a=c→(1+N)^{a-c}(\frac{b}{d})^NmodN^2=1modN^2$得:$b^N=d^NmodN^2→b^N=d^NmodN$（简单说明：$b^N=d^N+mN^2$两边取模即可）

  由$|\mathbb{Z}^*_N|=\phi(N),gcd(N,\phi(N))=1→h_N(g)=g^N$是双射函数，则$b=d$
  （原定理是：$|\mathbb{G}|=m,\forall t>0,gcd(t,m)=1→h_t(g)=g^t是双射函数$）

  • 满射证明：

  $$\begin{aligned} |\mathbb{Z}^*_{N^2}|&=\phi(N^2)=\phi(p^2q^2)\\ &=N^2*(1-1/p)(1-1/q)\\ &=pq(p-1)(q-1)\\ &=N*\phi(N)\\ &=|\mathbb{Z}_N||\mathbb{Z}^*_N|\\ &=|\mathbb{Z}_N·\mathbb{Z}^*_N| \end{aligned}$$

  • 已知$f$为单射函数，且像与原像数目相同，所以$f$为满射，则$f$为双射。

  运算保持：

  即证$f(a,b)f(c,d)=f(a+c,bd)$：

  $$\begin{aligned} &f(a,b)f(c,d)\\ &=[(1+N)^{a}b^N][(1+N)^{c}d^N]modN^2\\ &=(1+N)^{(a+c)modN}((bd) modN^2)^NmodN^2\\ \end{aligned}$$

  现证$(bd)^NmodN^2=(bd)^NmodN$,令$bd=r+\alpha N,r=(bd)modN$,则：

  $$\begin{aligned} &(r+\alpha N)^NmodN^2\\ &=r^N+N*r^{N-1}\cdot(\alpha N)modN^2\\ &=r^NmodN^2\\ &=((bd)modN)^NmodN^2 \end{aligned}$$

  即$f(a,b)f(c,d)=(1+N)^{(a+c)modN}((bd) modN)^NmodN^2=f(a+c,bd)$

0x03 加密体系

其他说明：

• 定义:

  $$Res(N^2)=\{x^N|x\in\mathbb{Z^*_{N^2}}\}=\{(0,b)|b\in\mathbb{Z^*_N}\}\\ \forall y \in Res(N^2),root(y)=\{(a,b)|a\in\mathbb{Z_N}\},|root(y)|=N$$

• $r\in \mathbb{Z^*_{N^2}}$是随机分布的，$[r^NmodN^2]\in Res(N^2)$是随机分布的。

• 困难假设：

  • 从$\mathbb{Z^*_{N^2}}$区分$Res(N^2)$是困难的。
  • 分解$N$是困难的(求解$\phi(N)$)

准备过程：

• Input:$1^n$
• Output:$N,p,q$
• Set:公钥$N$，私钥$\{N,\phi(N)\}$

加密过程：

• 任选$r \in \mathbb{Z}^*_{N}$
• 计算$c = (1+N)^{m}\cdot r^{N}mod N^2$

解密过程：

• 设置$\hat{c}=c^{\phi(N)}modN^2$
• 设置$\hat{m}=(\hat{c}-1)/N$ （此处是整数上的算数运算，除以$N$，不是乘$N^{-1}$）
• 计算$m =\hat{m}\cdot\phi(N)^{-1}\ modN$

0x04 图片版

现在不用了

0x05 安全性证明

现代密码基于计算安全：

• 在可接受时间范围内破解
• 破解的概率很低

计算安全比完美安全“松弛”的地方：

• 安全性抵抗有效的敌手（多项式时间的，关于参数n的概率多项式时间PPT）

• 允许很小的成功概率（概率小于多项式倒数的增长，就可忽略）

CPA安全性证明：

（条件）已知从$Z^*_{N^2}$中区分出$Res(N^2)$是困难的，则：

过程：

两种情况：

结论：

0x06 Python 示例

from Crypto.Util.number import getPrime,getRandomRange,long_to_bytes,bytes_to_long,inverse
from libnum import gcd
N,p,q,phi_N= 0,0,0,0
BitsLen=128
def Init(BitsLen):
    global N,p,q,phi_N
    p = getPrime(BitsLen)
    q = getPrime(BitsLen)
    N = p*q
    phi_N = (p-1)*(q-1)
    print("PubKey N:",N)

def Encrypto(message,N):
    m = str.encode(message)
    m = bytes_to_long(m)
    r = getRandomRange(2,N-1)
    while(gcd(r,N)!=1):
        r = getRandomRange(2,N-1)
    N2 = pow(N,2)
    c = pow((1+N),m,N2)*pow(r,N,N2)%N2
    print("Cipher c:",c)
    return c

def Decrypto(c,N,phi_N):
    N2 = pow(N,2)
    c1 = pow(c,phi_N,N2)
    m1 = divmod(c1-1,N)[0]
    m = m1*inverse(phi_N,N)%N
    return long_to_bytes(m)

if __name__ =='__main__':
    mess ="A sample of Paillier!"
    Init(128)
    c=Encrypto(mess,N)
    print("Message :",str(Decrypto(c,N,phi_N),encoding="utf8"))