基于Paillier和ElGamal算法的双层同态密码系统

王 东，李春平，肖亚光

（广东白云学院，广东 广州 510450）

密码学是应用于信息安全的一门科学技术。其核心内容包括将任何类型的信息隐藏在存储单元中或将传输的信息进行加密或隐藏从而确保信息存储和传输安全的一门技术。目前计算机系统中采用的加密系统分为对称性和非对称性加密系统两大类。以DES为代表的对称密码系统对明文的加密和解密使用相同的密钥，这意味着发送者和接收者拥有相同的密钥，信息传输过程伴随着密钥传输的过程。对称加密系统具有两大安全风险：一是如何安全地传输密钥，尤其是经过网络传输的密钥面临着被捕获的风险；二是加密系统如何管理大量的密钥。随着通信终端数量的不断攀升，存储在本地的密钥越来越多，安全地管理这些密钥成为一项巨大的挑战。

近年来，随着云计算应用的普及，人们在密文搜索、电子投票、移动代码和多方计算等方面的需求日益增加，同态加密由于具有更好的隐私保护性，其应用场景越来越多。同态加密是指一类具有特殊自然属性的加密方法，同态加密除能实现基本的加密操作外，还能在密文之间实现多种计算功能。利用同态加密技术可以先对多个密文进行计算之后再解密，不会因每个密文的解密而花费高昂的计算代价；利用同态加密技术也可实现没有密钥的一方对密文的计算，密文计算无须经过密钥方，既可以减少通信成本，也可以转移计算任务，又减少了密钥发送带来的安全风险，计算成本在发送端和接收端之间实现了平衡；使用同态加密技术的解密方只能得到最后的解密结果，但无法得到每一个密文的消息，信息的安全性得到显著提高。

同态加密技术的本质是指这样的一种加密函数，对明文进行环上的加法和乘法运算后再加密，其与加密后对密文进行相应的运算，实现等价的运算结果。由于同态加密具有这一技术特点，人们在委托第三方机构对数据进行处理时减少了泄露信息的风险。具有同态性质的加密函数是指两个明文a、b满足Dec（En（a）⊙En（b））=a⊕b的加密函数，其中En是指加密运算，Dec是指解密运算，⊙和⊕则分别对应明文和密文域上的运算。当⊕代表加法时，称该加密为加法同态加密；当⊕代表乘法时，该加密被称为乘法同态加密。

全同态加密是指同时满足加法同态和乘法同态性质，可进行任意多次加法和乘法运算的加密函数。可用数学公式表达为：Dec（f（En（m1），En（m2），…，En（mk）））=f（m1，m2，…，mk），或表达为：f（En（m1），En（m2），…，En（mk））=En（f（m1，m2，…，mk）），当f是任意函数时，就称为全同态加密。

2009年，IBM的研究人员Gentry首次设计出一个真正的全同态加密系统，Gentry提出的全同态加密系统可在不解密的前提下对加密数据进行任何运算，其结果与在明文上的运算结果一致，加密的信息很难被破解，从而保证了该方法的保密性。Gentry的方法与本文提出的基于Pallier算法的同态加密方法原理相似，常用于第三方数据处理服务商，用户存储于第三方的加密数据可被正常地检索、调用和运算，第三方无需与用户频繁交互确认，用户存储的数据由于采用了加密形式进而降低了数据泄露的风险。为提高全同态加密的效率，密码学界对其研究与探索仍在不断推进，同态加密技术正出现在越来越多的工程项目中。

以ElGamal为代表的非对称加密系统在加密和解密信息时采用不同的密钥。加密密钥即发送方和接收方的公钥是公开发送的，发送方使用接收方的公钥发送消息。接收方使用自己的私钥解密密文，即使黑客捕获了公钥也无法破解密文。为避免信息在加密前和解密后明文泄露的风险，本文提出的基于Paillier算法的同态加密（HE）系统解决隐私泄露的问题，该加密系统支持对密文进行双重加密，并经实验证明，对密文加解密的效果与对明文加解密的效果相同，算例精度高，运算速度快。

为有效解决明文泄密的安全问题，本文提出了实施Paillier和ElGamal密码系统的双层叠加技术方案，并使用Python实现了该加密系统。文中，我们还分析了Paillier密码系统的同态属性，并分析两种算法的运行时间和密钥生成时间的对比。Paillier提出的同态加密系统遵循的特性包括[1]：（1）它基于公钥密码系统（PKI），任何知道接收者公钥的发送者都可以进行加密，但解密过程只能通过其对应的私密密钥来完成。（2）破解的低概率性，即黑客无法判断出两个密文是否属于同一个明文。（3）它包含加法同态属性，即选取参数，生成公钥和私钥，给用户分配私钥，使用公钥对明文进行加密。（4）用户采用私钥对密文进行解密[2]。

为确保语义安全，在Pailliers密码系统中选择使用加密的随机值。采用随机值使攻击者难以区分两条数据M1和M2是密文还是明文。电子投票系统是Paillier密码系统的重要应用场景之一，Paillier密码系统可确保远程电子投票系统的通信安全[3]。Boneh-Goh-Nissim加密系统也是一种支持同态加密算法，该系统是一种基于双线性映射的公钥密码方案，支持任意次加法同态和一次乘法同态运算。方案中的加法同态方法与Paillier算法的思想相似，而一次乘法同态基于双线性映射的运算。由于双线性映射运算会导致密文所在的群发生变化，因此Boneh-Goh-Nissim方法仅支持一次乘法同态运算，但仍能够对乘法后的密文做进一步的加法同态运算。与其他全同态加密技术相比，Boneh-Goh-Nissim加密系统能取得更快的加密速度，其自身的架构也更紧凑[4]。基于有限域的离散对数特性的ElGamal密码系统于1985年由塔希尔·盖莫尔提出，ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法，GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法，ElGamal加密算法可以被定义在任何循环群G上。它的安全性取决于破解G上的离散对数难题的难度[5]。

1 双层同态密码系统原理

本研究提出的双层同态密码系统是基于Paillier和ElGamal方法的组合。这两种算法均可被Python程序实现，这两种密码算法都是基于公钥（PKI）方案的非对称密码系统。Paillier算法满足加法同态，ElGamal算法满足乘法同态。本研究将这两种方法合理搭配使用实现两层加密系统的设想以确保从根本上解决数据隐私的问题。本密码系统首先使用了Paillier算法对消息明文进行加密，然后再使用ElGamal算法对加密消息进行二次加密，从而产生经过二次加密的更安全的数据。而在接收方，接收方对加密数据采用ElGamal算法的私钥进行解密，得到Paillier的密文，由于Paillier的同态特性，接收方将对密文进行操作以确保明文不被泄露。

本方法设计的主要功能点如下：gcd（a，b），计算两个数a和b的最大公约数；lcm（a，b），计算随机数g的最小公倍数；gen_key（），生成较大的随机数；power（a，b，c），计算模幂；encrypt（），将明文加密为密文；decrypt（），将密文解密为明文。

1.1 Pailliers同态密码系统

加法同态加密由密钥生成算法、加密算法和解密算法三种算法组成。三种算法的原理如下：

1.1.1 产生密钥过程

首先，选两个大质数p，q，保证gcd（pq，（p-1）（q-1））=1，再计算n=p*q，λ=lcm（p-1，q-1），后用除法运算定义，并随机选一个小于n2的正整数g，并求得μ=（L（gλmod n2））-1mod n，得出公钥为（n，g）和私钥为（λ，μ）。

1.1.2 加密过程

首先取明文m是0≤m＜n的正整数，再随机选择r满足0＜r＜n且（其中，r，n互质为充分条件），计算密文c=gmrnmod n2。

1.1.3 解密过程

解密计算的公式为：m=L（cλmod n2）*μmod n，其中，c是密文且值域为区间。

1.2 ElGamal密码系统

ElGamal加密体制的公私密钥生成过程如下：

（1）随机选择一个满足安全要求的大素数p，并生成有限域Zp的一个生成元；

（2）选一个随机数x（1＜r＜p-1），计算y=gx（mod p），则公钥为（y，g，p），私钥为x。

1.2.1 加密过程

与RSA密码体制相同，ElGamal方法在加密时首先将明文比特串分组，使得每个分组对应的十进制数小于p，即分组长度小于log2P，然后对每个明文分组分别加密。具体过程为：首先，发送方得到接收方的公钥（y，g，p），再把消息m分组为长度为L（L＜log2P）的消息分组，取m=m1m2...mt，并对第i块消息（1≤i≤t）随机选择整数ri，1＜ri＜p-1，计算，将密文发送给接收方。

1.2.2 解密过程

实验证明，ElGamal加密过程需要2次模指数运算和1次模乘积运算，解密过程需要模指数运算，求逆运算和模乘积运算各一次。每次加密运算都需选择一个随机数，所以密文的生成与明文的内容与所选择的随机数有关，对于同一明文，不同的时刻生成不同的密文。另外，ElGamal加密方法扩展了消息的长度，即密文的长度是对应明文长度的两倍。

2 结果与分析

为证明Paillier密码系统的有效性及其同态特性，本研究进行了密码唯一性测试、解密测试、不同明文解密测试、同态测试、运行时间和密码系统的密钥生成时间等测试。为了测试p和q（质数）的16位长度值，取p=56711和q=77477。

2.1 密码唯一性测试

选取5组纯文本进行加密测试，纯文本分别为9、9、9、25、25，随 机 数 为：57342、64389、52906、27843、74437，加 密 后 的 密 文 为：6482410849035749、8475285035861743、6395629462029423、986452010832 4623、8462958298322048。从该组测试结果看出，密文的唯一性取决于随机值。即使明文相同，随机值不同也会生成不同的密文。

2.2 解密测试

将上一组的5个密文：6482410849035749、8475285035861743、6395629462029423、986452010832 4623、8462958298322048进行解密，得出真实的明文结果，实验证明解密成功。

2.3 运行时间和密钥生成时间

当质数p和q的长度为50时，采用Pailliers算法的加密总时间按输入明文长度20、40、60、80、100对应为：0.000673、0.000989、0.001034、0.001389、0.001857；采用ElGamal算法的加密总时间按输入明文长度20、40、60、80、100对应为：0.003497、0.003899、0.004571、0.004781、0.005014。采用Pailliers算法的密钥生成时间 按 输 入 明 文 长 度20、40、60、80、100对 应 为：0.000993、0.001049、0.001554、0.002770、0.002789；采用ElGamal算法的密钥生成时间按输入明文长度20、40、60、80、100对应为：0.000998、0.001995、0.003579、0.002002、0.002396。

2.4 同态检验

测试同态属性采用的同态函数是：D（E（m1，r1）E（m2，r2）mod n2）=（m1+m2）mod n，的值m1+m2的值 分 别 选 取 为：25 + 50、35687226 +6598325、4393798144+1023，对应的密文分别是：3658403675921 648、5748923549871943、7593648234671976，解密得出的明文分别为：75、42285551、708。其中，由于消息值大于n值，得出的明文708的结果是错误的，这与同态的属性相符合。

当质数p和q长度为90时，采用Pailliers算法的加密总时间按输入明文长度20、40、60、80、100对应为：0.000673、0.000989、0.001034、0.001389、0.001857；采用ElGamal算法的加密总时间按输入明文长度20、40、60、80、100对应为：0.003497、0.003899、0.004571、0.004781、0.005014。采用Pailliers算法的密钥生成时间 按 输 入 明 文 长 度20、40、60、80、100对 应 为：0.000993、0.001049、0.001554、0.002770、0.002789；采用ElGamal算法的密钥生成时间按输入明文长度20、40、60、80、100对应为：0.000373、0.000549、0.000854、0.000985、0.001284。

值得注意的是，当质数p和q长度增加时，密钥运算和密钥生成时间减少，这说明加密和解密时间随着质数长度的增加反而减少了。

3 结束语

为降低隐私泄露的风险，本研究使用Python程序实现了一个基于Paillier和ElGamal算法的双层密码系统。此外，本研究还分析证明了Paillier密码系统的同态特性，并对密码系统的运行时间和密钥生成时间进行了对比，本研究发现，随着质数长度的增加，密钥运算和密钥生成时间的表现更好。随着近年来云计算应用的日益普及，用户在密文搜索、电子投票、移动代码和多方同步计算等方面的需求日益增加，同态加密方法在保证信息安全方便变得更加重要，数据存储与传输环节适用同态加密方法的场景将越来越多。