基于Paillier和ElGamal算法的雙層同態(tài)密碼系統(tǒng)

王 東，李春平，肖亞光

（廣東白云學(xué)院，廣東 廣州 510450）

密碼學(xué)是應(yīng)用于信息安全的一門科學(xué)技術(shù)。其核心內(nèi)容包括將任何類型的信息隱藏在存儲(chǔ)單元中或?qū)鬏數(shù)男畔⑦M(jìn)行加密或隱藏從而確保信息存儲(chǔ)和傳輸安全的一門技術(shù)。目前計(jì)算機(jī)系統(tǒng)中采用的加密系統(tǒng)分為對(duì)稱性和非對(duì)稱性加密系統(tǒng)兩大類。以DES為代表的對(duì)稱密碼系統(tǒng)對(duì)明文的加密和解密使用相同的密鑰，這意味著發(fā)送者和接收者擁有相同的密鑰，信息傳輸過(guò)程伴隨著密鑰傳輸?shù)倪^(guò)程。對(duì)稱加密系統(tǒng)具有兩大安全風(fēng)險(xiǎn)：一是如何安全地傳輸密鑰，尤其是經(jīng)過(guò)網(wǎng)絡(luò)傳輸?shù)拿荑€面臨著被捕獲的風(fēng)險(xiǎn)；二是加密系統(tǒng)如何管理大量的密鑰。隨著通信終端數(shù)量的不斷攀升，存儲(chǔ)在本地的密鑰越來(lái)越多，安全地管理這些密鑰成為一項(xiàng)巨大的挑戰(zhàn)。

近年來(lái)，隨著云計(jì)算應(yīng)用的普及，人們?cè)诿芪乃阉?、電子投票、移?dòng)代碼和多方計(jì)算等方面的需求日益增加，同態(tài)加密由于具有更好的隱私保護(hù)性，其應(yīng)用場(chǎng)景越來(lái)越多。同態(tài)加密是指一類具有特殊自然屬性的加密方法，同態(tài)加密除能實(shí)現(xiàn)基本的加密操作外，還能在密文之間實(shí)現(xiàn)多種計(jì)算功能。利用同態(tài)加密技術(shù)可以先對(duì)多個(gè)密文進(jìn)行計(jì)算之后再解密，不會(huì)因每個(gè)密文的解密而花費(fèi)高昂的計(jì)算代價(jià)；利用同態(tài)加密技術(shù)也可實(shí)現(xiàn)沒(méi)有密鑰的一方對(duì)密文的計(jì)算，密文計(jì)算無(wú)須經(jīng)過(guò)密鑰方，既可以減少通信成本，也可以轉(zhuǎn)移計(jì)算任務(wù)，又減少了密鑰發(fā)送帶來(lái)的安全風(fēng)險(xiǎn)，計(jì)算成本在發(fā)送端和接收端之間實(shí)現(xiàn)了平衡；使用同態(tài)加密技術(shù)的解密方只能得到最后的解密結(jié)果，但無(wú)法得到每一個(gè)密文的消息，信息的安全性得到顯著提高。

同態(tài)加密技術(shù)的本質(zhì)是指這樣的一種加密函數(shù)，對(duì)明文進(jìn)行環(huán)上的加法和乘法運(yùn)算后再加密，其與加密后對(duì)密文進(jìn)行相應(yīng)的運(yùn)算，實(shí)現(xiàn)等價(jià)的運(yùn)算結(jié)果。由于同態(tài)加密具有這一技術(shù)特點(diǎn)，人們?cè)谖械谌綑C(jī)構(gòu)對(duì)數(shù)據(jù)進(jìn)行處理時(shí)減少了泄露信息的風(fēng)險(xiǎn)。具有同態(tài)性質(zhì)的加密函數(shù)是指兩個(gè)明文a、b滿足Dec（En（a）⊙En（b））=a⊕b的加密函數(shù)，其中En是指加密運(yùn)算，Dec是指解密運(yùn)算，⊙和⊕則分別對(duì)應(yīng)明文和密文域上的運(yùn)算。當(dāng)⊕代表加法時(shí)，稱該加密為加法同態(tài)加密；當(dāng)⊕代表乘法時(shí)，該加密被稱為乘法同態(tài)加密。

全同態(tài)加密是指同時(shí)滿足加法同態(tài)和乘法同態(tài)性質(zhì)，可進(jìn)行任意多次加法和乘法運(yùn)算的加密函數(shù)?？捎脭?shù)學(xué)公式表達(dá)為：Dec（f（En（m1），En（m2），…，En（mk）））=f（m1，m2，…，mk），或表達(dá)為：f（En（m1），En（m2），…，En（mk））=En（f（m1，m2，…，mk）），當(dāng)f是任意函數(shù)時(shí)，就稱為全同態(tài)加密。

2009年，IBM的研究人員Gentry首次設(shè)計(jì)出一個(gè)真正的全同態(tài)加密系統(tǒng)，Gentry提出的全同態(tài)加密系統(tǒng)可在不解密的前提下對(duì)加密數(shù)據(jù)進(jìn)行任何運(yùn)算，其結(jié)果與在明文上的運(yùn)算結(jié)果一致，加密的信息很難被破解，從而保證了該方法的保密性。Gentry的方法與本文提出的基于Pallier算法的同態(tài)加密方法原理相似，常用于第三方數(shù)據(jù)處理服務(wù)商，用戶存儲(chǔ)于第三方的加密數(shù)據(jù)可被正常地檢索、調(diào)用和運(yùn)算，第三方無(wú)需與用戶頻繁交互確認(rèn)，用戶存儲(chǔ)的數(shù)據(jù)由于采用了加密形式進(jìn)而降低了數(shù)據(jù)泄露的風(fēng)險(xiǎn)。為提高全同態(tài)加密的效率，密碼學(xué)界對(duì)其研究與探索仍在不斷推進(jìn)，同態(tài)加密技術(shù)正出現(xiàn)在越來(lái)越多的工程項(xiàng)目中。

以ElGamal為代表的非對(duì)稱加密系統(tǒng)在加密和解密信息時(shí)采用不同的密鑰。加密密鑰即發(fā)送方和接收方的公鑰是公開發(fā)送的，發(fā)送方使用接收方的公鑰發(fā)送消息。接收方使用自己的私鑰解密密文，即使黑客捕獲了公鑰也無(wú)法破解密文。為避免信息在加密前和解密后明文泄露的風(fēng)險(xiǎn)，本文提出的基于Paillier算法的同態(tài)加密（HE）系統(tǒng)解決隱私泄露的問(wèn)題，該加密系統(tǒng)支持對(duì)密文進(jìn)行雙重加密，并經(jīng)實(shí)驗(yàn)證明，對(duì)密文加解密的效果與對(duì)明文加解密的效果相同，算例精度高，運(yùn)算速度快。

為有效解決明文泄密的安全問(wèn)題，本文提出了實(shí)施Paillier和ElGamal密碼系統(tǒng)的雙層疊加技術(shù)方案，并使用Python實(shí)現(xiàn)了該加密系統(tǒng)。文中，我們還分析了Paillier密碼系統(tǒng)的同態(tài)屬性，并分析兩種算法的運(yùn)行時(shí)間和密鑰生成時(shí)間的對(duì)比。Paillier提出的同態(tài)加密系統(tǒng)遵循的特性包括[1]：（1）它基于公鑰密碼系統(tǒng)（PKI），任何知道接收者公鑰的發(fā)送者都可以進(jìn)行加密，但解密過(guò)程只能通過(guò)其對(duì)應(yīng)的私密密鑰來(lái)完成。（2）破解的低概率性，即黑客無(wú)法判斷出兩個(gè)密文是否屬于同一個(gè)明文。（3）它包含加法同態(tài)屬性，即選取參數(shù)，生成公鑰和私鑰，給用戶分配私鑰，使用公鑰對(duì)明文進(jìn)行加密。（4）用戶采用私鑰對(duì)密文進(jìn)行解密[2]。

為確保語(yǔ)義安全，在Pailliers密碼系統(tǒng)中選擇使用加密的隨機(jī)值。采用隨機(jī)值使攻擊者難以區(qū)分兩條數(shù)據(jù)M1和M2是密文還是明文。電子投票系統(tǒng)是Paillier密碼系統(tǒng)的重要應(yīng)用場(chǎng)景之一，Paillier密碼系統(tǒng)可確保遠(yuǎn)程電子投票系統(tǒng)的通信安全[3]。Boneh-Goh-Nissim加密系統(tǒng)也是一種支持同態(tài)加密算法，該系統(tǒng)是一種基于雙線性映射的公鑰密碼方案，支持任意次加法同態(tài)和一次乘法同態(tài)運(yùn)算。方案中的加法同態(tài)方法與Paillier算法的思想相似，而一次乘法同態(tài)基于雙線性映射的運(yùn)算。由于雙線性映射運(yùn)算會(huì)導(dǎo)致密文所在的群發(fā)生變化，因此Boneh-Goh-Nissim方法僅支持一次乘法同態(tài)運(yùn)算，但仍能夠?qū)Τ朔ê蟮拿芪淖鲞M(jìn)一步的加法同態(tài)運(yùn)算。與其他全同態(tài)加密技術(shù)相比，Boneh-Goh-Nissim加密系統(tǒng)能取得更快的加密速度，其自身的架構(gòu)也更緊湊[4]?；谟邢抻虻碾x散對(duì)數(shù)特性的ElGamal密碼系統(tǒng)于1985年由塔希爾·蓋莫爾提出，ElGamal加密算法是一個(gè)基于迪菲-赫爾曼密鑰交換的非對(duì)稱加密算法，GnuPG和PGP等很多密碼學(xué)系統(tǒng)中都應(yīng)用到了ElGamal算法，ElGamal加密算法可以被定義在任何循環(huán)群G上。它的安全性取決于破解G上的離散對(duì)數(shù)難題的難度[5]。

1 雙層同態(tài)密碼系統(tǒng)原理

本研究提出的雙層同態(tài)密碼系統(tǒng)是基于Paillier和ElGamal方法的組合。這兩種算法均可被Python程序?qū)崿F(xiàn)，這兩種密碼算法都是基于公鑰（PKI）方案的非對(duì)稱密碼系統(tǒng)。Paillier算法滿足加法同態(tài)，ElGamal算法滿足乘法同態(tài)。本研究將這兩種方法合理搭配使用實(shí)現(xiàn)兩層加密系統(tǒng)的設(shè)想以確保從根本上解決數(shù)據(jù)隱私的問(wèn)題。本密碼系統(tǒng)首先使用了Paillier算法對(duì)消息明文進(jìn)行加密，然后再使用ElGamal算法對(duì)加密消息進(jìn)行二次加密，從而產(chǎn)生經(jīng)過(guò)二次加密的更安全的數(shù)據(jù)。而在接收方，接收方對(duì)加密數(shù)據(jù)采用ElGamal算法的私鑰進(jìn)行解密，得到Paillier的密文，由于Paillier的同態(tài)特性，接收方將對(duì)密文進(jìn)行操作以確保明文不被泄露。

本方法設(shè)計(jì)的主要功能點(diǎn)如下：gcd（a，b），計(jì)算兩個(gè)數(shù)a和b的最大公約數(shù)；lcm（a，b），計(jì)算隨機(jī)數(shù)g的最小公倍數(shù)；gen_key（），生成較大的隨機(jī)數(shù)；power（a，b，c），計(jì)算模冪；encrypt（），將明文加密為密文；decrypt（），將密文解密為明文。

1.1 Pailliers同態(tài)密碼系統(tǒng)

加法同態(tài)加密由密鑰生成算法、加密算法和解密算法三種算法組成。三種算法的原理如下：

1.1.1 產(chǎn)生密鑰過(guò)程

首先，選兩個(gè)大質(zhì)數(shù)p，q，保證gcd（pq，（p-1）（q-1））=1，再計(jì)算n=p*q，λ=lcm（p-1，q-1），后用除法運(yùn)算定義，并隨機(jī)選一個(gè)小于n2的正整數(shù)g，并求得μ=（L（gλmod n2））-1mod n，得出公鑰為（n，g）和私鑰為（λ，μ）。

1.1.2 加密過(guò)程

首先取明文m是0≤m＜n的正整數(shù)，再隨機(jī)選擇r滿足0＜r＜n且（其中，r，n互質(zhì)為充分條件），計(jì)算密文c=gmrnmod n2。

1.1.3 解密過(guò)程

解密計(jì)算的公式為：m=L（cλmod n2）*μmod n，其中，c是密文且值域?yàn)閰^(qū)間。

1.2 ElGamal密碼系統(tǒng)

ElGamal加密體制的公私密鑰生成過(guò)程如下：

（1）隨機(jī)選擇一個(gè)滿足安全要求的大素?cái)?shù)p，并生成有限域Zp的一個(gè)生成元；

（2）選一個(gè)隨機(jī)數(shù)x（1＜r＜p-1），計(jì)算y=gx（mod p），則公鑰為（y，g，p），私鑰為x。

1.2.1 加密過(guò)程

與RSA密碼體制相同，ElGamal方法在加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于p，即分組長(zhǎng)度小于log2P，然后對(duì)每個(gè)明文分組分別加密。具體過(guò)程為：首先，發(fā)送方得到接收方的公鑰（y，g，p），再把消息m分組為長(zhǎng)度為L(zhǎng)（L＜log2P）的消息分組，取m=m1m2...mt，并對(duì)第i塊消息（1≤i≤t）隨機(jī)選擇整數(shù)ri，1＜ri＜p-1，計(jì)算，將密文發(fā)送給接收方。

1.2.2 解密過(guò)程

實(shí)驗(yàn)證明，ElGamal加密過(guò)程需要2次模指數(shù)運(yùn)算和1次模乘積運(yùn)算，解密過(guò)程需要模指數(shù)運(yùn)算，求逆運(yùn)算和模乘積運(yùn)算各一次。每次加密運(yùn)算都需選擇一個(gè)隨機(jī)數(shù)，所以密文的生成與明文的內(nèi)容與所選擇的隨機(jī)數(shù)有關(guān)，對(duì)于同一明文，不同的時(shí)刻生成不同的密文。另外，ElGamal加密方法擴(kuò)展了消息的長(zhǎng)度，即密文的長(zhǎng)度是對(duì)應(yīng)明文長(zhǎng)度的兩倍。

2 結(jié)果與分析

為證明Paillier密碼系統(tǒng)的有效性及其同態(tài)特性，本研究進(jìn)行了密碼唯一性測(cè)試、解密測(cè)試、不同明文解密測(cè)試、同態(tài)測(cè)試、運(yùn)行時(shí)間和密碼系統(tǒng)的密鑰生成時(shí)間等測(cè)試。為了測(cè)試p和q（質(zhì)數(shù)）的16位長(zhǎng)度值，取p=56711和q=77477。

2.1 密碼唯一性測(cè)試

選取5組純文本進(jìn)行加密測(cè)試，純文本分別為9、9、9、25、25，隨 機(jī) 數(shù) 為：57342、64389、52906、27843、74437，加 密 后 的 密 文 為：6482410849035749、8475285035861743、6395629462029423、986452010832 4623、8462958298322048。從該組測(cè)試結(jié)果看出，密文的唯一性取決于隨機(jī)值。即使明文相同，隨機(jī)值不同也會(huì)生成不同的密文。

2.2 解密測(cè)試

將上一組的5個(gè)密文：6482410849035749、8475285035861743、6395629462029423、986452010832 4623、8462958298322048進(jìn)行解密，得出真實(shí)的明文結(jié)果，實(shí)驗(yàn)證明解密成功。

2.3 運(yùn)行時(shí)間和密鑰生成時(shí)間

當(dāng)質(zhì)數(shù)p和q的長(zhǎng)度為50時(shí)，采用Pailliers算法的加密總時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.000673、0.000989、0.001034、0.001389、0.001857；采用ElGamal算法的加密總時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.003497、0.003899、0.004571、0.004781、0.005014。采用Pailliers算法的密鑰生成時(shí)間 按 輸 入 明 文 長(zhǎng) 度20、40、60、80、100對(duì) 應(yīng) 為：0.000993、0.001049、0.001554、0.002770、0.002789；采用ElGamal算法的密鑰生成時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.000998、0.001995、0.003579、0.002002、0.002396。

2.4 同態(tài)檢驗(yàn)

測(cè)試同態(tài)屬性采用的同態(tài)函數(shù)是：D（E（m1，r1）E（m2，r2）mod n2）=（m1+m2）mod n，的值m1+m2的值 分 別 選 取 為：25 + 50、35687226 +6598325、4393798144+1023，對(duì)應(yīng)的密文分別是：3658403675921 648、5748923549871943、7593648234671976，解密得出的明文分別為：75、42285551、708。其中，由于消息值大于n值，得出的明文708的結(jié)果是錯(cuò)誤的，這與同態(tài)的屬性相符合。

當(dāng)質(zhì)數(shù)p和q長(zhǎng)度為90時(shí)，采用Pailliers算法的加密總時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.000673、0.000989、0.001034、0.001389、0.001857；采用ElGamal算法的加密總時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.003497、0.003899、0.004571、0.004781、0.005014。采用Pailliers算法的密鑰生成時(shí)間 按 輸 入 明 文 長(zhǎng) 度20、40、60、80、100對(duì) 應(yīng) 為：0.000993、0.001049、0.001554、0.002770、0.002789；采用ElGamal算法的密鑰生成時(shí)間按輸入明文長(zhǎng)度20、40、60、80、100對(duì)應(yīng)為：0.000373、0.000549、0.000854、0.000985、0.001284。

值得注意的是，當(dāng)質(zhì)數(shù)p和q長(zhǎng)度增加時(shí)，密鑰運(yùn)算和密鑰生成時(shí)間減少，這說(shuō)明加密和解密時(shí)間隨著質(zhì)數(shù)長(zhǎng)度的增加反而減少了。

3 結(jié)束語(yǔ)

為降低隱私泄露的風(fēng)險(xiǎn)，本研究使用Python程序?qū)崿F(xiàn)了一個(gè)基于Paillier和ElGamal算法的雙層密碼系統(tǒng)。此外，本研究還分析證明了Paillier密碼系統(tǒng)的同態(tài)特性，并對(duì)密碼系統(tǒng)的運(yùn)行時(shí)間和密鑰生成時(shí)間進(jìn)行了對(duì)比，本研究發(fā)現(xiàn)，隨著質(zhì)數(shù)長(zhǎng)度的增加，密鑰運(yùn)算和密鑰生成時(shí)間的表現(xiàn)更好。隨著近年來(lái)云計(jì)算應(yīng)用的日益普及，用戶在密文搜索、電子投票、移動(dòng)代碼和多方同步計(jì)算等方面的需求日益增加，同態(tài)加密方法在保證信息安全方便變得更加重要，數(shù)據(jù)存儲(chǔ)與傳輸環(huán)節(jié)適用同態(tài)加密方法的場(chǎng)景將越來(lái)越多。