加法同态 - Paillier算法
Pailier算法是法国密码学家Paillier于1999年欧密会上发表，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。
数学知识
1、Carmichael函数，当a与n互素时，$a^{λ(n)}$ = 1 mod n
卡迈克尔函数定义：当 n 为 1、2、4、奇素数的次幂、奇素数的次幂的两倍时为欧拉函数，当 n 为 2、4 以外的 2 的次幂时为欧拉函数的一半。
如果n可写为素数的积，即$n=p_1^{a1}p_2^{a2}…p_n^{an}$,则λ(n)=lcm($λ(p_1^{a1}),λ(p_2^{a2}),…,λ(p_n^{an})$)
2、泰勒展开式，y=${(1+n)^x}=∑^x_{k=0}C^k_xn^k = 1+nx+C^2_xn^2 + … $；从$n^2$开始后面的项均可以被$n^2$整数，因此 y = 1+nx mod $n^2$ ，根据同余定理并同除n，可得x = $\frac{(y-1)}{n}$ mod n
3、欧拉函数：计算不大于n且与n互素得正整数得个数，用$\varphi$(n)表示这些正整数的集合并记为 $Z^*_n$
4、计算带幂次素数的欧拉函数：若p为素数，且有$n=p^r$，则$\varphi$(n)=$\varphi$($p^r$) = $p^{r-1}\varphi(p-1)$
5、设m=pq，若p和q互素且大于1，则$\varphi(m)=\varphi(p)\varphi(q)$
6、欧拉定理，a∈$Z_n$（$Z_n$表示小于Z的所有正整数的集合），且a与n互素，即a∈$Z_n^*$，则$a^{\varphi(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}$，且满足g的阶(mod$n^2$)是n的非零倍数
4、公钥(n，g)，私钥为 λ
选择素数 p=7，q=11
计算n=77，λ=30
选择 g=5652
因此，公钥为(77，5652)，私钥为30
加密算法
1、选择 r∈$Z^*_{n}$，因此 r∈$Z^*_{n^2}$
2、计算密文 C = $g^mr^n$ mod ${n^2}$
选择明文 m=42，随机数 r=23
C = $5652^{42}23^{77}$mod 5929
= 4624
解密算法
1、令函数L(x)=$\frac{x-1}{n}$
2、计算明文 m = $\frac{L(c^λmod n^2)}{L(g^λmod n^2}$ mod n
m = $\frac{L(4624^{30}mod 5929)}{L(5652^{30}mod 5929)}$
m = $\frac{L(4852)}{L(3928)}$ mod 77
m = $\frac{63}{51}$ mod 77
m = 63*$51^{-1}$ mod 77
m = 63*74 mod 77
m = 42求逆元的正确性
m = $\frac{a}{b}$ mod n
mb = a mod n
mb$b^{-1}$ = a$b^{-1}$ mod n
因为b$b^{-1}$ mod n = 1
m = a$b^{-1}$ mod n
加解密正确性证明
$c^λmod n^2 = g^{mλ}r^{nλ} mod n^2 = g^{mλ} modn^2 = (1+n)^{mλ} mod n^2$
=(1 + nmλ) mod $n^2$ （由泰勒展开式得）
证明$r^{nλ} mod n^2$ = 1
由卡迈克尔函数得
$λ(n^2)$ = $lcm(λ(p^2),λ(q^2))$
= $lcm(p(p-1),q(q-1))$
= $n*λ(n)$
由卡迈克尔函数可知，p,q都是素数
$a^{λ(n)} =1mod n$
$a^{nλ(n)} =1mod n^2$
同理可得：$g^λ mod n^2 = (1 + nλ) mod n^2$
$L(c^λmod n^2)$ = $\frac{(1 + nmλ - 1 )mod n^2}{n} = mλ mod n^2$
$L(g^λmod n^2)$ = $\frac{(1 + nλ - 1 )mod n^2}{n} = λ mod n^2$
故明文 m = $\frac{L(c^λmod n^2)}{L(g^λmod n^2)}$ = $\frac{mλ}{λ}$ = m
加法同态
E(a) * E(b)
= $(g^ar_1^n mod n^2) * (g^br_2^n mod n^2)$
= $g^{a+b}(r_1 * r_2)^n mod n^2$
= 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、计算欧拉函数$\varphi(n)$
$\varphi(n)$ = (p - 1)(q - 1)
4、计算公钥 e
e 满足的条件：① 1 < e < $\varphi(n)$；② e 与 $\varphi(n)$互素
5、计算私钥 d
e * d = 1 mod($\varphi(n)$)
加密算法
设明文为 A且小于n，密文为 B
B = $A^e$ mod n
解密算法
A = $B^d$ mod n
乘法同态
假设密文为 $B_1$，$B_2$
$B_1$*$B_2$ = $A_1^{e1}$ * $A_2^{e2}$ mod n
= $(A_1$ * $A_2)^e$ mod n
因此，RSA算法满足乘法同态性，密文乘法等于明文乘法
加解密正确性证明
由解密可得，须证明 $A^{ed}$ = A mod n
ed = 1 mod$\varphi(n)$
ed -1 = k$\varphi(n)$，ed = k$\varphi(n)$ + 1
即得 $A^{k\varphi(n)+1}$ = A mod n，并对 A 分两种情况讨论
① 当 A 与 n 互素时
由欧拉定理可得：$A^{\varphi(n)}$ = 1 mod n
$A^{ed}$ mod n = $A^{k\varphi(n)+1}$ mod n = $A$ * $A^{k\varphi(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整除
所有由费马小定理得：$(kp)^{q-1}$ = 1 mod q
由同余乘法性质得：$(kp)^{(q-1)*(p-1)*k}*kp = (kp) mod q$，对于mod q，1的k(p-1)次方依然为1
$\varphi(n)$ = (p-1)(q-1)，ed = k $\varphi(n)$ + 1
所以$(kp)^{ed} = (kp) mod q$
$(kp)^{ed} - (kp) = tq$
$kp((kp)^{ed-1} - 1) = tq$
所以kp能整除tq，而q是素数，因此 t 是 p的倍数
则令 t = $t_1p$
而$(kp)^{ed} = tq + kp$
即$(kp)^{ed} = t_1pq + kp$
即$A^{ed} = t_1n + A$
所以原式$A^{ed}$ mod n = $t_1n+A$ mod n = $A$
因此，加解密正确
乘法同态 - ElGamal算法
密钥生成
1、随机选择大素数p，且要求 p-1 有大素数因子；在选择一个模 p 的本原元 $\alpha$
2、从{1，2，3，…，p-1}中随机选择一个数 d
3、计算 $\beta = \alpha^d mod p$
4、公钥为(p,$\beta,\alpha$)，私钥为 d
加密算法
1、从{1，2，3，…，p-1}中选择一个随机数 k，令 m 为明文
2、计算密文 $C_1=\alpha^k mod p$
3、计算密文 $C_2=m*\beta^k mod p$
4、传输密文（$C_1,C_2$）
解密算法
1、计算明文$m = C_2(C_1^d)^{-1} mod p$
2、$(C_1^d)^{-1}$为求$C_1^d模p的逆元$
加解密正确性证明
m = $C_2(C_1^d)^{-1} mod p$
= $m$ * $\beta^k$ * $(\alpha^{kd})^{-1} mod p$
= $m$ * $\beta^k$ * $(\beta^{k})^{-1} mod p$ (因为$\beta = \alpha^d mod p$)
= m
