同态加密–Paillier加密

0x01 基础知识

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

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

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

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

0x02 命题证明

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

    思路:gcd(p,ϕ(N))=1,gcd(q,ϕ(N))=1gcd(p,\phi(N))=1,gcd(q,\phi(N))=1

    假设p>qp>q

    • p>p1>q1p>p-1>q-1,即gcd(p,ϕ(N))=1gcd(p,\phi(N))=1

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

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

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

    易知(1+N)(1+N)N2N^2的阶是NN

  • 同构ff证明

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

    群的封闭性:

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

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

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

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

    双射证明:

    既单又满

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

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

    b,dZNZN2,b,d存在逆元.不妨设 α=bd,αZN2:αϕ(N2)modN2=1modN2ϕ(N2)=ϕ(p2q2)=N2(11/p)(11/q)=pq(p1)(q1)=Nϕ(N)两边同时取ϕ(N)次方可得:(1+N)(ac)ϕ(N)(α)ϕ(N2)modN2=1modN2\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)(ac)ϕ(N)modN2=1modN2(1+N)^{(a-c)\phi(N)}modN^2=1modN^2,由(1+N)(1+N)N2N^2的阶是NN,得:

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

    a,cZNa,c\in \mathbb{Z}_N,只有a=c,N(ac)a=c,N|(a-c)

    a=c(1+N)ac(bd)NmodN2=1modN2a=c→(1+N)^{a-c}(\frac{b}{d})^NmodN^2=1modN^2得:bN=dNmodN2bN=dNmodNb^N=d^NmodN^2→b^N=d^NmodN(简单说明:bN=dN+mN2b^N=d^N+mN^2两边取模即可)

    ZN=ϕ(N),gcd(N,ϕ(N))=1hN(g)=gN|\mathbb{Z}^*_N|=\phi(N),gcd(N,\phi(N))=1→h_N(g)=g^N是双射函数,则b=db=d
    (原定理是:G=m,t>0,gcd(t,m)=1ht(g)=gt是双射函数|\mathbb{G}|=m,\forall t>0,gcd(t,m)=1→h_t(g)=g^t是双射函数

    • 满射证明:

    ZN2=ϕ(N2)=ϕ(p2q2)=N2(11/p)(11/q)=pq(p1)(q1)=Nϕ(N)=ZNZN=ZNZN\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}

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

    运算保持:

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

    f(a,b)f(c,d)=[(1+N)abN][(1+N)cdN]modN2=(1+N)(a+c)modN((bd)modN2)NmodN2\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)NmodN2=(bd)NmodN(bd)^NmodN^2=(bd)^NmodN,令bd=r+αN,r=(bd)modNbd=r+\alpha N,r=(bd)modN,则:

    (r+αN)NmodN2=rN+NrN1(αN)modN2=rNmodN2=((bd)modN)NmodN2\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)NmodN2=f(a+c,bd)f(a,b)f(c,d)=(1+N)^{(a+c)modN}((bd) modN)^NmodN^2=f(a+c,bd)

0x03 加密体系

其他说明:

  • 定义:

    Res(N2)={xNxZN2}={(0,b)bZN}yRes(N2),root(y)={(a,b)aZN},root(y)=NRes(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

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

  • 困难假设:

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

准备过程:

  • Input:1n1^n
  • Output:N,p,qN,p,q
  • Set:公钥NN,私钥{N,ϕ(N)}\{N,\phi(N)\}

加密过程:

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

解密过程:

  • 设置c^=cϕ(N)modN2\hat{c}=c^{\phi(N)}modN^2
  • 设置m^=(c^1)/N\hat{m}=(\hat{c}-1)/N (此处是整数上的算数运算,除以NN,不是乘N1N^{-1}
  • 计算m=m^ϕ(N)1 modNm =\hat{m}\cdot\phi(N)^{-1}\ modN

0x04 图片版

现在不用了

0x05 安全性证明

现代密码基于计算安全:

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

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

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

  • 允许很小的成功概率(概率小于多项式倒数的增长,就可忽略)

CPA安全性证明:

(条件)已知从ZN2Z^*_{N^2}中区分出Res(N2)Res(N^2)是困难的,则:

过程:

两种情况:

结论:

0x06 Python 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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"))