同态加密算法实现及推导
一、 *理解并验证加解密算法*
(一) 同态加密算法的主要背景
同态加密提供了一种对加密数据进行处理的功能。也就是说其他人可以对加密后的数据进行处理,在这个过程中不会泄露任何原始的内容,在数据处理完成之后再进行解密,得到的正是对原始数据进行相同处理后的结果。
(二) 关键算法
同态加密算法可以分为部分同态、全同态、加法同态、乘法同态、近似同态几种。接下来对其具体算法进行详细解释:
- 加法同态加密:支持密文的加法运算。给定两个密文,可以得到它们对应明文和的加密版本,而不需要知道原始明文。RSA加密就是一种天然的加法同态加密系统。
- 乘法同态加密:与加法同态相对应,乘法同态加密支持密文的乘法运算。可以将两个密文相乘,得到的结果等同于将它们各自的明文相乘后再加密的结果。
- 部分同态加密:部分同态加密方案指的是仅支持单一类型运算(加法或乘法)的同态加密。例如,RSA是一种部分同态加密系统,因为它仅支持加法同态。同理,ElGamal加密是另一种部分同态加密系统,它支持乘法同态。
- 全同态加密(FHE):全同态加密是最强大的同态加密形式,它允许在密文上进行无限次的加法和乘法运算,因此可以构建任意复杂的计算而无需解密。2009年,Craig Gentry首次提出了全同态加密的概念。尽管全同态加密非常强大,但现有的实现通常相对缓慢,不适用于实时或大规模计算。
- 近似同态加密(AHE):近似同态加密是一种支持在密文上执行准确或近似运算的加密方法。它对于机器学习和数据分析尤其有用,因为这些领域中的算法有时可以容忍轻微的计算不精确性。它允许在结果的精度和计算效率之间进行权衡。
(三) 应用领域
同态加密的应用场景可以包括几个方面:
- 云计算安全:用户可以加密自己的数据并将其上传到云端,云服务提供者可以在不了解数据内容的情况下对其进行处理。这保护了数据在处理过程中的隐私性。
- 保护隐私的数据挖掘和分析:允许公司在不泄露个人信息或敏感数据的前提下,对用户数据进行分析和挖掘。
- 安全的多方计算:多个参与者可以共同进行数据分析或运算,而无需透露各自的输入。例如,两个公司可能想要合作确定它们的客户群有多少重叠,而不泄露各自的客户名单。
- 电子投票系统:在电子投票应用中,同态加密可以用来确保投票的隐私性和完整性,同时还能验证投票结果的正确性。
- 安全的医疗记录管理:医生或研究人员可以在不直接访问患者详细信息的情况下,进行诊断或研究。
- 金融服务:金融机构可以在不暴露交易细节的情况下,处理加密的交易和查询。
- 加密货币:同态加密可以提供对加密货币交易的隐私保护,同时允许验证交易的有效性而不需要解密。
- 供应链管理:企业可以在保护相关数据隐私的同时,验证供应链中的计算和数据的正确性。
(四) 演算及验证过程
- 演算样例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
- 演算样例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
(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
二、 *实现算法对应关键函数*
- 模幂运算
- L(x)函数
- 逆元计算
- λ函数
- 加解密运算未封装
三、 *完整实现同态加密算法*
主函数即功能函数截图
主函数调用
运行效果截图