加法同态 - Paillier算法

      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=p1a1​p2a2​...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) (gar1n​modn2)∗(gbr2n​modn2)
= 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算法

      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 t1​p
而 ( 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=t1​pq+kp
即 A e d = t 1 n + A A^{ed} = t_1n + A Aed=t1​n+A
所以原式 A e d A^{ed} Aed mod n = t 1 n + A t_1n+A t1​n+A mod n = A A A
因此，加解密正确

乘法同态 - ElGamal算法

密钥生成
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