同态加密算法实现及推导

一、 *理解并验证加解密算法*

（一） 同态加密算法的主要背景

同态加密提供了一种对加密数据进行处理的功能。也就是说其他人可以对加密后的数据进行处理，在这个过程中不会泄露任何原始的内容，在数据处理完成之后再进行解密，得到的正是对原始数据进行相同处理后的结果。

（二） 关键算法

同态加密算法可以分为部分同态、全同态、加法同态、乘法同态、近似同态几种。接下来对其具体算法进行详细解释：

1. 加法同态加密：支持密文的加法运算。给定两个密文，可以得到它们对应明文和的加密版本，而不需要知道原始明文。RSA加密就是一种天然的加法同态加密系统。
2. 乘法同态加密：与加法同态相对应，乘法同态加密支持密文的乘法运算。可以将两个密文相乘，得到的结果等同于将它们各自的明文相乘后再加密的结果。
3. 部分同态加密：部分同态加密方案指的是仅支持单一类型运算（加法或乘法）的同态加密。例如，RSA是一种部分同态加密系统，因为它仅支持加法同态。同理，ElGamal加密是另一种部分同态加密系统，它支持乘法同态。
4. 全同态加密（FHE）：全同态加密是最强大的同态加密形式，它允许在密文上进行无限次的加法和乘法运算，因此可以构建任意复杂的计算而无需解密。2009年，Craig Gentry首次提出了全同态加密的概念。尽管全同态加密非常强大，但现有的实现通常相对缓慢，不适用于实时或大规模计算。
5. 近似同态加密（AHE）：近似同态加密是一种支持在密文上执行准确或近似运算的加密方法。它对于机器学习和数据分析尤其有用，因为这些领域中的算法有时可以容忍轻微的计算不精确性。它允许在结果的精度和计算效率之间进行权衡。

（三） 应用领域

同态加密的应用场景可以包括几个方面：

1. 云计算安全：用户可以加密自己的数据并将其上传到云端，云服务提供者可以在不了解数据内容的情况下对其进行处理。这保护了数据在处理过程中的隐私性。
2. 保护隐私的数据挖掘和分析：允许公司在不泄露个人信息或敏感数据的前提下，对用户数据进行分析和挖掘。
3. 安全的多方计算：多个参与者可以共同进行数据分析或运算，而无需透露各自的输入。例如，两个公司可能想要合作确定它们的客户群有多少重叠，而不泄露各自的客户名单。
4. 电子投票系统：在电子投票应用中，同态加密可以用来确保投票的隐私性和完整性，同时还能验证投票结果的正确性。
5. 安全的医疗记录管理：医生或研究人员可以在不直接访问患者详细信息的情况下，进行诊断或研究。
6. 金融服务：金融机构可以在不暴露交易细节的情况下，处理加密的交易和查询。
7. 加密货币：同态加密可以提供对加密货币交易的隐私保护，同时允许验证交易的有效性而不需要解密。
8. 供应链管理：企业可以在保护相关数据隐私的同时，验证供应链中的计算和数据的正确性。

（四） 演算及验证过程

1. 演算样例1

(1) 演算过程

p= 7 ,q= 11 ,n= 77 ,g= 5652 ,m= 42 ,r= 23

步骤1：Paillier系统加密过程

c = (5652)^42*(23)^77 mod 5929

c = (4019)*(606) mod 5929 = 2435514 mod 5929 = 4624

(2) 验证过程

步骤2-Paillier系统解密中间过程-L（.）求解

λ(77) = lcm(6,10) = 30

L(5652^30 mod 5929) = L(3928)

L(3928) = (3928-1)/77 = 51

步骤3： Paillier系统加密过程-计算µ

µ = 51^-1 mod 77 = 74 mod 77

Paillier加密系统解密过程-解密出最终结果

m = L(4624^30 mod 5929)*74 mod 77 = 42

2. 演算样例1

(1) 演算过程

p= 11 ,q= 13 ,n= 143 ,g= 3544 ,m= 72 ,r= 61

步骤1：Paillier系统加密过程

c = (3544)^72*(61)^143 mod 20449

c = (1093)*(4033) mod 20449 = 4408069 mod 20449 = 11534

(2) 验证过程

步骤2-Paillier系统解密中间过程-L（.）求解

λ(143) = lcm(10,12) = 60

L(3544^60 mod 20449) = L(11727)

L(11727) = (11727-1)/143 = 82

步骤3： Paillier系统加密过程-计算µ

µ = 82^-1 mod 143 = 75 mod 143

Paillier加密系统解密过程-解密出最终结果

m = L(11534^60 mod 20449)*75 mod 143 = 72

3. 演算样例3

(1) 演算过程

p= 29 ,q= 51 ,n= 1479 ,g= 2061 ,m= 39 ,r= 21

步骤1：Paillier系统加密过程

c = (2061)^39*(21)^1479 mod 2187441

c = (302256)*(1384272) mod 2187441 = 418404517632 mod 2187441 = 1740357

(2) 验证过程

步骤2-Paillier系统解密中间过程-L（.）求解

λ(1479) = lcm(28,50) = 700

L(2061^700 mod 2187441) = L(787815)

L(787815) = (787815-1)/1479 = 532

步骤3： Paillier系统加密过程-计算µ

µ = 532^-1 mod 1479 = 670 mod 1479

Paillier加密系统解密过程-解密出最终结果

m = L(1740357^700 mod 2187441)*670 mod 1479 = 39

二、 *实现算法对应关键函数*

1. 模幂运算

2. L(x)函数

3. 逆元计算

4. λ函数

5. 加解密运算未封装

三、 *完整实现同态加密算法*

主函数即功能函数截图

主函数调用

运行效果截图