Pailier算法是法国密码学家Paillier于1999年欧密会上发表，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。
数学知识
1、Carmichael函数，当a与n互素时，
a
λ
(
n
)
a^{λ(n)}
aλ(n) = 1 mod n
卡迈克尔函数定义：当 n 为 1、2、4、奇素数的次幂、奇素数的次幂的两倍时为欧拉函数，当 n 为 2、4 以外的 2 的次幂时为欧拉函数的一半。
如果n可写为素数的积，即
n
=
p
1
a
1
p
2
a
2
.
.
.
p
n
a
n
n=p_1^{a1}p_2^{a2}...p_n^{an}
n=p1a1p2a2...pnan,则λ(n)=lcm(
λ
(
p
1
a
1
)
,
λ
(
p
2
a
2
)
,
.
.
.
,
λ
(
p
n
a
n
)
λ(p_1^{a1}),λ(p_2^{a2}),...,λ(p_n^{an})
λ(p1a1),λ(p2a2),...,λ(pnan))
2、泰勒展开式，y= ( 1 + n ) x {(1+n)^x} (1+n)x= ∑ k = 0 x ∑^x_{k=0} ∑k=0x C x k C^k_x Cxk n k n^ k nk = 1+nx+ C x 2 C^2_x Cx2 n 2 n^2 n2+ … ；从 n 2 n^2 n2开始后面的项均可以被 n 2 n^2 n2整数，因此 y = 1+nx mod n 2 n^2 n2 ，根据同余定理并同除n，可得x = ( y − 1 ) n \frac{(y-1)}{n} n(y−1) mod n
3、欧拉函数：计算不大于n且与n互素得正整数得个数，用 φ \varphi φ(n)表示这些正整数的集合并记为 Z n ∗ Z^*_n Zn∗
4、计算带幂次素数的欧拉函数：若p为素数，且有 n = p r n=p^r n=pr，则 φ \varphi φ(n)= φ \varphi φ( p r p^r pr) = p r − 1 φ ( p − 1 ) p^{r-1}\varphi(p-1) pr−1φ(p−1)
5、设m=pq，若p和q互素且大于1，则 φ ( m ) = φ ( p ) φ ( q ) \varphi(m)=\varphi(p)\varphi(q) φ(m)=φ(p)φ(q)
6、欧拉定理，a∈ Z n Z_n Zn（ Z n Z_n Zn表示小于Z的所有正整数的集合），且a与n互素，即a∈ Z n ∗ Z_n^* Zn∗，则 a φ ( n ) a^{\varphi(n )} aφ(n) = 1 mod n
密钥生成
1、随机选择大素数p、q，且满足gcd(pq，(p-1)(q-1)) = 1，gcd()函数是求最大公因数
2、计算 n = pq， λ= lcm(p-1，q-1)
3、随机选取 g∈
Z
n
2
∗
Z^*_{n^2}
Zn2∗，且满足g的阶(mod
n
2
n^2
n2)是n的非零倍数
4、公钥(n，g)，私钥为 λ
选择素数 p=7，q=11
计算n=77，λ=30
选择 g=5652
因此，公钥为(77，5652)，私钥为30
加密算法
1、选择 r∈
Z
n
∗
Z^*_{n}
Zn∗，因此 r∈
Z
n
2
∗
Z^*_{n^2}
Zn2∗
2、计算密文 C =
g
m
r
n
g^mr^n
gmrn mod
n
2
{n^2}
n2
选择明文 m=42，随机数 r=23
C = 565 2 42 2 3 77 5652^{42}23^{77} 5652422377mod 5929
= 4624
解密算法
1、令函数L(x)=
x
−
1
n
\frac{x-1}{n}
nx−1
2、计算明文 m =
L
(
c
λ
m
o
d
n
2
)
L
(
g
λ
m
o
d
n
2
\frac{L(c^λmod n^2)}{L(g^λmod n^2}
L(gλmodn2L(cλmodn2) mod n
m = L ( 462 4 30 m o d 5929 ) L ( 565 2 30 m o d 5929 ) \frac{L(4624^{30}mod 5929)}{L(5652^{30}mod 5929)} L(565230mod5929)L(462430mod5929)
m = L ( 4852 ) L ( 3928 ) \frac{L(4852)}{L(3928)} L(3928)L(4852) mod 77
m = 63 51 \frac{63}{51} 5163 mod 77
m = 63* 5 1 − 1 51^{-1} 51−1 mod 77
m = 63*74 mod 77
m = 42求逆元的正确性
m = a b \frac{a}{b} ba mod n
mb = a mod n
mb b − 1 b^{-1} b−1 = a b − 1 b^{-1} b−1 mod n
因为b b − 1 b^{-1} b−1 mod n = 1
m = a b − 1 b^{-1} b−1 mod n
加解密正确性证明
c
λ
m
o
d
n
2
=
g
m
λ
r
n
λ
m
o
d
n
2
=
g
m
λ
m
o
d
n
2
=
(
1
+
n
)
m
λ
m
o
d
n
2
c^λmod n^2 = g^{mλ}r^{nλ} mod n^2 = g^{mλ} modn^2 = (1+n)^{mλ} mod n^2
cλmodn2=gmλrnλmodn2=gmλmodn2=(1+n)mλmodn2
=(1 + nmλ) mod
n
2
n^2
n2 （由泰勒展开式得）
证明 r n λ m o d n 2 r^{nλ} mod n^2 rnλmodn2 = 1
由卡迈克尔函数得
λ ( n 2 ) λ(n^2) λ(n2) = l c m ( λ ( p 2 ) , λ ( q 2 ) ) lcm(λ(p^2),λ(q^2)) lcm(λ(p2),λ(q2))
= l c m ( p ( p − 1 ) , q ( q − 1 ) ) lcm(p(p-1),q(q-1)) lcm(p(p−1),q(q−1))
= n ∗ λ ( n ) n*λ(n) n∗λ(n)
由卡迈克尔函数可知，p,q都是素数
a λ ( n ) = 1 m o d n a^{λ(n)} =1mod n aλ(n)=1modn
a n λ ( n ) = 1 m o d n 2 a^{nλ(n)} =1mod n^2 anλ(n)=1modn2
同理可得：
g
λ
m
o
d
n
2
=
(
1
+
n
λ
)
m
o
d
n
2
g^λ mod n^2 = (1 + nλ) mod n^2
gλmodn2=(1+nλ)modn2
L
(
c
λ
m
o
d
n
2
)
L(c^λmod n^2)
L(cλmodn2) =
(
1
+
n
m
λ
−
1
)
m
o
d
n
2
n
=
m
λ
m
o
d
n
2
\frac{(1 + nmλ - 1 )mod n^2}{n} = mλ mod n^2
n(1+nmλ−1)modn2=mλmodn2
L
(
g
λ
m
o
d
n
2
)
L(g^λmod n^2)
L(gλmodn2) =
(
1
+
n
λ
−
1
)
m
o
d
n
2
n
=
λ
m
o
d
n
2
\frac{(1 + nλ - 1 )mod n^2}{n} = λ mod n^2
n(1+nλ−1)modn2=λmodn2
故明文 m =
L
(
c
λ
m
o
d
n
2
)
L
(
g
λ
m
o
d
n
2
)
\frac{L(c^λmod n^2)}{L(g^λmod n^2)}
L(gλmodn2)L(cλmodn2) =
m
λ
λ
\frac{mλ}{λ}
λmλ = m
加法同态
E(a) * E(b)
=
(
g
a
r
1
n
m
o
d
n
2
)
∗
(
g
b
r
2
n
m
o
d
n
2
)
(g^ar_1^n mod n^2) * (g^br_2^n mod n^2)
(gar1nmodn2)∗(gbr2nmodn2)
=
g
a
+
b
(
r
1
∗
r
2
)
n
m
o
d
n
2
g^{a+b}(r_1 * r_2)^n mod n^2
ga+b(r1∗r2)nmodn2
= E(a +b)
因此，Piallier算法支持加法同态，即密文相乘等于明文相加
RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA的安全性依赖于大数分解，为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。RSA算法的保密强度随其密钥的长度增加而增强。但是，密钥越长，其加解密所耗用的时间也越长
密钥生成
1、选择两个大素数 p，q
2、计算 n = p * q，
3、计算欧拉函数
φ
(
n
)
\varphi(n)
φ(n)
φ
(
n
)
\varphi(n)
φ(n) = (p - 1)(q - 1)
4、计算公钥 e
e 满足的条件：① 1 < e <
φ
(
n
)
\varphi(n)
φ(n)；② e 与
φ
(
n
)
\varphi(n)
φ(n)互素
5、计算私钥 d
e * d = 1 mod(
φ
(
n
)
\varphi(n)
φ(n))
加密算法
设明文为 A且小于n，密文为 B
B =
A
e
A^e
Ae mod n
解密算法
A =
B
d
B^d
Bd mod n
乘法同态
假设密文为
B
1
B_1
B1，
B
2
B_2
B2
B
1
B_1
B1*
B
2
B_2
B2 =
A
1
e
1
∗
A
2
e
2
A_1^{e1}*A_2^{e2}
A1e1∗A2e2 mod n
=
(
A
1
∗
A
2
)
e
(A_1*A_2)^e
(A1∗A2)e mod n
因此，RSA算法满足乘法同态性，密文乘法等于明文乘法
加解密正确性证明
由解密可得，须证明
A
e
d
A^{ed}
Aed = A mod n
ed = 1 mod
φ
(
n
)
\varphi(n)
φ(n)
ed -1 = k
φ
(
n
)
\varphi(n)
φ(n)，ed = k
φ
(
n
)
\varphi(n)
φ(n) + 1
即得
A
k
φ
(
n
)
+
1
A^{k\varphi(n)+1}
Akφ(n)+1 = A mod n，并对 A 分两种情况讨论
① 当 A 与 n 互素时
由欧拉定理可得：
A
φ
(
n
)
A^{\varphi(n)}
Aφ(n) = 1 mod n
A
e
d
A^{ed}
Aed mod n =
A
k
φ
(
n
)
+
1
A^{k\varphi(n)+1}
Akφ(n)+1 mod n =
A
∗
A
k
φ
(
n
)
A*A^{k\varphi(n)}
A∗Akφ(n) mod n = A mod n
由于 A < n，因此加解密正确
② A 与 n 不互素
条件有：A与n不互素，n=pq，p，q均为素数，且 A < n
因此 A=kp 或 kq；举例说明，p=3,q=5,n=15，由于A与n不互素，因此A={3,5,6,9,10,12}，任取A必为q或p的倍数
令A=kp，则 1 < k < q
因为 k < q，且 q是素数，因此 k 与 q 互素
k与q互素，p与q互素，则kq不能被q整除
所有由费马小定理得：
(
k
p
)
q
−
1
(kp)^{q-1}
(kp)q−1 = 1 mod q
由同余乘法性质得：
(
k
p
)
(
q
−
1
)
∗
(
p
−
1
)
∗
k
∗
k
p
=
(
k
p
)
m
o
d
q
(kp)^{(q-1)*(p-1)*k}*kp = (kp) mod q
(kp)(q−1)∗(p−1)∗k∗kp=(kp)modq，对于mod q，1的k(p-1)次方依然为1
φ
(
n
)
\varphi(n)
φ(n) = (p-1)(q-1)，ed = k
φ
(
n
)
\varphi(n)
φ(n) + 1
所以
(
k
p
)
e
d
=
(
k
p
)
m
o
d
q
(kp)^{ed} = (kp) mod q
(kp)ed=(kp)modq
(
k
p
)
e
d
−
(
k
p
)
=
t
q
(kp)^{ed} - (kp) = tq
(kp)ed−(kp)=tq
k
p
(
(
k
p
)
e
d
−
1
−
1
)
=
t
q
kp((kp)^{ed-1} - 1) = tq
kp((kp)ed−1−1)=tq
所以kp能整除tq，而q是素数，因此 t 是 p的倍数
则令 t =
t
1
p
t_1p
t1p
而
(
k
p
)
e
d
=
t
q
+
k
p
(kp)^{ed} = tq + kp
(kp)ed=tq+kp
即
(
k
p
)
e
d
=
t
1
p
q
+
k
p
(kp)^{ed} = t_1pq + kp
(kp)ed=t1pq+kp
即
A
e
d
=
t
1
n
+
A
A^{ed} = t_1n + A
Aed=t1n+A
所以原式
A
e
d
A^{ed}
Aed mod n =
t
1
n
+
A
t_1n+A
t1n+A mod n =
A
A
A
因此，加解密正确
密钥生成
1、随机选择大素数p，且要求 p-1 有大素数因子；在选择一个模 p 的本原元
α
\alpha
α
2、从{1，2，3，…，p-1}中随机选择一个数 d
3、计算
β
=
α
d
m
o
d
p
\beta = \alpha^d mod p
β=αdmodp
4、公钥为(p,
β
,
α
\beta,\alpha
β,α)，私钥为 d
加密算法
1、从{1，2，3，…，p-1}中选择一个随机数 k，令 m 为明文
2、计算密文
C
1
=
α
k
m
o
d
p
C_1=\alpha^k mod p
C1=αkmodp
3、计算密文
C
2
=
m
∗
β
k
m
o
d
p
C_2=m*\beta^k mod p
C2=m∗βkmodp
4、传输密文（
C
1
,
C
2
C_1,C_2
C1,C2）
解密算法
1、计算明文
m
=
C
2
(
C
1
d
)
−
1
m
o
d
p
m = C_2(C_1^d)^{-1} mod p
m=C2(C1d)−1modp
2、
(
C
1
d
)
−
1
(C_1^d)^{-1}
(C1d)−1为求
C
1
d
模
p
的
逆
元
C_1^d模p的逆元
C1d模p的逆元
加解密正确性证明
m =
C
2
(
C
1
d
)
−
1
m
o
d
p
C_2(C_1^d)^{-1} mod p
C2(C1d)−1modp
=
m
∗
β
k
∗
(
α
k
d
)
−
1
m
o
d
p
m*\beta^k*(\alpha^{kd})^{-1} mod p
m∗βk∗(αkd)−1modp
=
m
∗
β
k
∗
(
β
k
)
−
1
m
o
d
p
m*\beta^k*(\beta^{k})^{-1} mod p
m∗βk∗(βk)−1modp (因为
β
=
α
d
m
o
d
p
\beta = \alpha^d mod p
β=αdmodp)
= m
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）