基于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密碼系統的同態特性，并對密碼系統的運行時間和密鑰生成時間進行了對比，本研究發現，隨著質數長度的增加，密鑰運算和密鑰生成時間的表現更好。隨著近年來云計算應用的日益普及，用戶在密文搜索、電子投票、移動代碼和多方同步計算等方面的需求日益增加，同態加密方法在保證信息安全方便變得更加重要，數據存儲與傳輸環節適用同態加密方法的場景將越來越多。