同态加密概念
同态加密（Homomorphic Encryption，简称HE）是很久以前密码学界就提出来的一个Open
Problem。早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L.
Dertouzos就以银行为应用背景提出了这个概念[RAD78]。其中Ron Rivest和Leonard
Adleman分别就是著名的RSA算法（一种非对称加密算法）中的R和A。至于中间的S，Adi
Shamir，现在仍然在为密码学贡献新的工作。
什么是同态加密？
提出第一个构造出全同态加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry给出的直观定义最好：
A way to delegate processing of your data, without giving away access to it. 一种在不放弃访问权限的情况下委托数据处理的方法。
这是什么意思呢？一般的加密方案关注的都是数据存储安全。即，我要给其他人发送数据，或者要在计算机上存数据，需要对数据进行加密后再发送或者存储。没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够正确解密，得到原始的内容。我们注意到，这个过程中用户是不能对加密结果做任何操作的，只能进行存储、传输。对加密结果做任何操作，都将会导致错误的解密，甚至解密失败。
但同态加密方案关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行加工处理，但是加工处理过程不会泄露任何原始内容。同时，拥有密钥的用户对加工处理过的数据进行解密后，得到的正好是明文数据处理后的结果。
🙋♂️个🌰理解
有个A用户买到了一大块金子，她想让工人把这块金子打造成一个项链。但是工人在打造的过程中有可能会偷金子啊，因此能不能有一种方法，既让工人可以对金块进行加工（delegate
processing of your data），又无法得到任何金子（without giving away access to it）
A可以这么做：
● 将金子锁在一个密闭的盒子里面，这个盒子安装了一个手套。
● 工人可以带着这个手套，对盒子内部的金子进行处理。但盒子是锁着的，工人不仅拿不到金块，连处理过程中掉下的任何金子都拿不到。
● 加工完成后。A拿回这个盒子，把锁打开，就得到了金子。
这个盒子的样子大概是这样的：
这里面的对应关系是：
● 盒子：加密算法
● 盒子上的锁：用户密钥
● 将金块放在盒子里面并且用锁锁上：将数据用同态加密方案进行加密
● 加工：应用同态特性，在无法取得数据的条件下直接对加密结果进行处理
● 开锁：对结果进行解密，直接得到处理后的结果
同态加密具体如何定义？
我们以云计算应用场景为例：
Alice通过Cloud，以同态加密（以下简称HE）处理数据的整个处理过程大致是这样的：
Alice对数据进行加密。并把加密后的数据发送给Cloud；
Alice向Cloud提交数据的处理方法，这里用函数f来表示；
Cloud在函数f下对加密数据进行处理，并且将处理后的结果发送给Alice；
Alice对数据进行解密，得到结果。
据此，我们可以很直观的得到一个HE方案应该拥有的函数：
KeyGen函数：密钥生成函数。这个函数应该由Alice运行，用于产生加密数据Data所用的密钥Key。当然了，应该还有一些公开常数PP（Public Parameter）；
Encrypt函数：加密函数。这个函数也应该由Alice运行，用Key对用户数据Data进行加密，得到密文CT（Ciphertext）；
Evaluate函数：评估函数。这个函数由Cloud运行，在用户给定的数据处理方法f下，对密文进行操作，使得结果相当于用户用密钥Key对f(Data)进行加密。
Decrypt函数：解密函数。这个函数由Alice运行，用于得到Cloud处理的结果f(Data)。
那么， f函数应该是什么样子的呢？根据函数f的限制条件不同，HE方案实际上分为了两类：
● 全同态加密(Fully Homomorphic Encryption，简称 FHE)：这意味着HE方案支持任意给定的f函数，只要这个f函数可以通过算法描述，用计算机实现。显然，FHE方案是一个非常棒的方案，但是计算开销极大，暂时还无法在实际中使用。
● 类同态加密(Somewhat Homomorphic Encryption，简称 SWHE) 或部分同态加密(partial homomorphic encryption, 简称PHE)：这意味着HE方案只支持一些特定的f函数。SWHE方案稍弱，但也意味着开销会变得较小，容易实现，现在已经可以在实际中使用。
主流同态加密算法原理
满足有限运算同态性而不满足任意运算同态性的加密算法称为半同态加密。典型的半同态加密特性包括乘法同态、加法同态、有限次数全同态等。
乘法同态加密算法
简单理解：
在实际应用中，密文乘法同态性的需求场景不多，因此乘法同态性通常偶然存在于已有的经典加密算法中。满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法等。
① RSA算法
RSA算法是最为经典的公钥加密算法，至今已有40余年的历史，其安全性基于大整数分解困难问题。在实际应用中，RSA算法可采用RSA_PKCS1_PADDING、RSA_PKCS1_OAEP_PADDING等填充模式，根据密钥长度（常用1024位或2048位）对明文分组进行填充，而只有不对明文进行填充的原始RSA算法才能满足乘法同态特性。由于原始的RSA不是随机化加密算法，即加密过程中没有使用随机因子，每次用相同密钥加密相同明文的结果是固定的。因此，利用RSA的乘法同态性实现同态加密运算会存在安全弱点，攻击者可能通过选择明文攻击得到原始数据。
一些基本的数学知识
质数（素数） p：只有1和他本身能被自己整除。
互质：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系,比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
欧拉函数φ(n)：小于n的正整数中，与n互质的整数的个数。例如φ(8)=4（因为小于8的正整数中只有1,3,5,7与8互质）
若n为质数，则φ(n)=n-1
n如果可以分为两个质数（p,q）的乘积，则φ(n)=φ(p*q)=φ§φ(q)=(p-1)(q-1)
欧拉定理：如果两个正整数a和n互质，则：a^φ(n)≡1 mod n。特别的，当n为质数时： a^(n-1)≡1 mod n
模反元素: 如果两个正整数a和n互质，那么一定可以找到整数b，满足：a×b≡1 mod n（ab-1 被n整除，或者说ab被n除的余数是1）这时，b就叫做a的"模反元素"。
RSA的具体过程
假设alice想要通过rsa算法在公网上，将消息加密传递给bob，他们应该怎么做呢？分为以下几个步骤：
1.bob生成公私钥，将公钥在网上公开，私钥自己保存
2.alice通过bob的公钥加密明文消息m，得到密文c，并将密文c传递给bob
3.bob用自己的私钥解密密文c，得到明文m
秘钥的产生
bob选择两个保密的大质数p和q（这里假设是p=61,q=53）
计算n=p×q=61×53=3233，φ(n)=φ(p*q)=φ§φ(q)=(p-1)(q-1)=60×52=3120
这里 n的长度就是秘钥的长度 。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。
选一个整数e，满足1< e < φ(n)，且e与φ(n) 互质
bob就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
求解e关于φ(n)的模反元素d（由于e与φ(n)互质，所以d一定存在）
ed ≡ 1 (mod φ(n)) 等价于 ed - 1 = kφ(n)，这里就是17d-1 =3120k，求得(d,k)=(2753,-15)，即 d=2753。
n和e封装成公钥，n和d封装成私钥
这个例子中 n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）
加密
假设alice要向bob发送明文信息m，则用bob的公钥 (n=3233,17,e=17) 对m进行加密。
并且加密时必须将明文进行比特串分组，保证每个分组对应的十进制数小于n，即保证m<n。
c ≡ m^e (mod n)
这里m假设是65，那么可以算出下面的等式：65^17 ≡ 2790 (mod 3233)
于是，c等于2790，alice就把2790发给了bob。
解密
bob拿到c(2790)以后，就用自己的私钥(n=3233, d=2753) 进行解密。
m ≡ c^d (mod n)
那么，bob算出 2790^2753 ≡ 65 (mod 3233)
因此，bob知道了alice加密前的原文就是65。
验证了 RSA 算法的乘法同态性
给出两个明文m1和m2，使用上述方法加密后得到两个密文，
c1= E(m1) =m1^𝑒 (𝑚𝑜𝑑 𝑛)，
c2= E(m2) = m2^𝑒 (𝑚𝑜𝑑 𝑛)，
将两个密文相乘得到：c1∗ c2= E(m1) ∗E(m2) = m1^𝑒∗ m2^𝑒 (𝑚𝑜𝑑 𝑛)，
由于E(m1m2) = (m1m2)(𝑚𝑜𝑑 𝑛)，所以可以得出E(m1m2) = E(m1) ∗ E(m2)，
验证了 RSA 算法的乘法同态性。
