同态加密技术学习

1、概念：同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。
2、同态加密过程：
以云计算应用场景为例，Alice通过Cloud，以同态加密处理数据的整个处理过程大致是这样的：

Alice对数据进行加密。并把加密后的数据发送给Cloud；
Alice向Cloud提交数据的处理方法，这里用函数f来表示；
Cloud在函数f下对数据进行处理，并且将处理后的结果发送给Alice；
Alice对数据进行解密，得到结果。

根据同态加密的算法，可以分为RSA（乘法）、Paillier（加法）等。
3、Paillier同态加密算法：
密钥生成
总共有如下几个步骤：
1、 随机选择两个质数 p 和 q 满足 |p|=|q|=τ|p|=|q|=τ，这个条件保证了 p 和 q 的长度相等。
2、 计算 N=pqN=pq 和 λ=lcm(p−1,q−1)λ=lcm(p−1,q−1)，注：lcm 表示最小公倍数。
3、随机选择 g∈Z∗N2g∈ZN2∗，满足 gcd(L(gλmodN2),N)=1gcd(L(gλmodN2),N)=1，注：gcd 表示最大公约数；Z 表示整数，下标表示该整数集合里有多少个元素；L(x)=x−1NL(x)=x−1N
4、 公钥为 (N,g)(N,g)
5、 私钥为 λλ
加密
对于任意整数 m∈ZNm∈ZN，任意选择随机数r∈Z∗Nr∈ZN∗，密文C=E(m)=gmrNmodN2C=E(m)=gmrNmodN2
解密
对于密文 C∈Z∗N2C∈ZN2∗，解密得到明文 m 的计算如下：
m=L(CλmodN2)L(gλmodN2)modNm=L(CλmodN2)L(gλmodN2)modN
加法同态
对于任意明文 m1,m2∈ZNm1,m2∈ZN，假设 E(m1)=gm1rN1modN2E(m1)=gm1r1NmodN2 和 E(m2)=gm2rN2modN2E(m2)=gm2r2NmodN2，有
E(m1)E(m2)=gm1+m2(r1r2)NmodN2=E(m1+m2modN)E(m1)E(m2)=gm1+m2(r1r2)NmodN2=E(m1+m2modN)
这个性质表明 Paillier 加密方案具有加法同态性。
4、Paillier同态加密算法的python实现

from phe import paillier  # 开源库
import time  # 做性能测试
# 测试paillier参数
print("默认私钥大小：", paillier.DEFAULT_KEYSIZE)  # 2048
# 生成公私钥
public_key, private_key = paillier.generate_paillier_keypair()
# 测试需要加密的数据
message_list = [12, 100]
# 加密操作
time_start_enc = time.time()
encrypted_message_list = [public_key.encrypt(m) for m in message_list]
time_end_enc = time.time()
print("加密耗时ms：", time_end_enc - time_start_enc)
# 解密操作
time_start_dec = time.time()
decrypted_message_list = [private_key.decrypt(c) for c in encrypted_message_list]
time_end_dec = time.time()
print("解密耗时ms：", time_end_dec - time_start_dec)
print("原始数据:", decrypted_message_list)

a1, b1 = message_list  # a1,b1分别为对应原始数据
# 测试加法和乘法同态
a2, b2 = encrypted_message_list  # a2,b2分别为对应密文

print("a1 a2 = ", a1, a2)
print("b1 b2 = ", b1, b2)
# 密文加明文
print("a1+5=", a1 + 5, "，dec(a2+5)=", private_key.decrypt(a2 + 5))
# 密文加密文
print("a1+b1=", a1 + b1, "，dec(a2+b2)=", private_key.decrypt(a2 + b2))
# 密文乘明文
print("a1*2 = ", a1 * 2, "，dec(a2*2) = ", private_key.decrypt(a2 * 2))
# 密文乘密文（不支持）
print("a1*b1 = ", a1 * b1, "，dec(a2*b2) = ", private_key.decrypt(a2 * b2))

输出结果：
4、RSA同态加密算法：
密钥生成
1、 随机找两个质数 P 和 Q，越大越安全，并计算乘积 n=P∗Qn=P∗Q。P 和 Q 的乘积的二进制位数代表 RSA 加密的位数，一般来说都要有 1024 或 2048 位。

2、 计算 n 的欧拉函数 ϕ(n)ϕ(n)，表示在小于等于 n 的正整数中，与 n 构成互质关系的数的个数。比如 1~8 中，和 8 互质的有 1,3,5,7，所以 ϕ(8)=4ϕ(8)=4，如果 p 和 q 为质数，那么他们的乘积的欧拉函数有一个特殊的性质，公式为 ϕ(n)=ϕ(P∗Q)=ϕ(P−1)ϕ(Q−1)=(P−1)(Q−1)ϕ(n)=ϕ(P∗Q)=ϕ(P−1)ϕ(Q−1)=(P−1)(Q−1)。

3、选取 e，要大于 1 小于 ϕ(n)ϕ(n)，并且 e 与 ϕ(n)ϕ(n) 要互质。

4、计算出一个整数 d，使得 (ed−1) % ϕ(n)=0(ed−1) % ϕ(n)=0，即 e∗de∗d 除以 ϕ(n)ϕ(n) 的余数为 1，实际上转化为找到二元一次方程 ed+kϕ(n)=1ed+kϕ(n)=1 的一组解（求 d 和 k），具体使用的是扩展欧几里得算法。

于是我们可以得到：

公钥 (n, e)
私钥 (n, d)

在这样的条件下，如果想要根据 n 和 e 算出 d，就只能暴力破解，位数越长，玻璃破解时间越长。
加密
我们现在有个这么几个关键的数值：n, e, d。要使用公钥 (n, e) 加密，首先要求被加密的数字必须是整数且小于 n（如果是字符串，可以逐个取 ascii 码或 unicode 值，并且中间用非数字和字母分割即可）。假设我们需要加密的数字是 A，则加密之后的 B 为（为了区别使用大写）：

Ae % n=BAe % n=B

如果没有 d，那么是很难从 B 中恢复 A 的。
解密

如果我们拥有私钥 (n, d)，那么对于 B，就可以通过下面的公式计算出 A：

Bd % n=ABd % n=A

乘法同态相对 Paillier 来说还要更加简单一些，我们只要把两个加密后的数字相乘即可，代码片段如下：

print('接下来加密计算 2 x 20')
print('加密 2')
enc1 = rsa.core.encrypt_int(2, public_key.e, public_key.n)
print(enc1)
print('加密 20') # 40471062776583530669631608186743860028386032505372124150562694293213549812024
enc2 = rsa.core.encrypt_int(20, public_key.e, public_key.n)
print(enc2) # 16915103439566807805446086181091224947678993169521653470724152014464992293178
print('相乘')
result = enc1 * enc2
print(result) # 684572213175112282577113686759405066981454950839007710126450052851088805616753069318980764721622690261112227625923822693220128510206043466290770597572272
print('解密结果')
decrypt_result = rsa.core.decrypt_int(result, private_key.d, public_key.n)
print(decrypt_result) # 40

本篇博客参考：https://blog.csdn.net/watson2017/article/details/121630306