基于ECC與同態加密的加密算法

劉 艷，郎顯赫+，裴少婧

(1.大連大學 遼寧省北斗高精度位置服務技術工程實驗室，遼寧 大連 116622；2.大連大學 大連市環境感知與智能控制重點實驗室，遼寧 大連 116622；3.中原工學院 機電學院，河南 鄭州 450007)

0 引 言

隨著互聯網與云計算的發展，人們在私人信息搜索、移動代碼與電子投票等方面的需求日益增加，同態加密[1]變得更加重要。Rivest等提出RSA加密方案，利用同態加密的性質進行對數據進行加密，之后同態加密技術得到了進一步發展，取得了一些代表性的研究成果，彭長根等[2]基于同態加密提出一種可傳遞的簽名方案，利用同態加密的密文可運算特性實現了可傳遞簽名及驗簽的通用模型。楊玉龍等[3]提出防止SQL注入攻擊的同態加密解決方案，段淑敏等[4]提出基于RSA代理重加密的同態加密方案，楊攀等[5]提出支持密文四則運算的CESIL同態加密方案。但是這些傳統的同態加密方法存在公鑰尺寸過大，計算復雜度高，運算效率低等缺點，不能實際應用于云中，本文針對這一問題，提出一種基于ECC與同態加密技術的加密方案，該方案具有高效的運算效率和高安全強度。

1 同態加密技術

同態加密允許服務器在不知道原始明文的情況下做加密數據的操作，允許對加密后的數據執行特定的數學運算并且解密結果和對應明文進行運算后的結果是一致的，從而保護了數據[6]。數據加密解密基本流程如圖1所示。

圖1 數據加密解密基本流程

假設一個加密系統中加密算法為CK，解密算法為DK，明文為n、m，則同態加密滿足如下屬性

DK(CK(n)*CK(m))=n*m

(1)

DK(CK(n)+CK(m))=n+m

(2)

上述加密方法第一個屬性是乘法同態加密，第二個屬性是加法同態加密，如果兩個屬性同屬滿足，則加密算法成為完全同態加密[7]。由于加法同態加密運算較少，相對于乘法可忽略不計，所以本文僅研究乘法同態加密，為后續進一步密文檢索技術的研究提供技術支撐。

2 橢圓曲線加密技術

橢圓曲線并不是橢圓，之所以稱為橢圓曲線加密是因為它的曲線方程與計算橢圓周長的方程相似。一般橢圓曲線指的是維爾斯特拉斯(Weierstrass)方程所確定的橢圓曲線，形如：y2+axy+by=x3+cx2+dx+e，它是由方程全部解(x,y)加上一個無窮遠點O構成的一個集合。橢圓曲線加密算法的安全性建立在求橢圓曲線離散對數解困難性(ECDLP)[8]之上，設曲線E及曲線上的兩點G和Q，其中Q=xG，求x就是橢圓曲線的離散對數問題[9]。

設基礎域F，x,y屬于F且滿足如下：

y2+axy+by=x3+cx2+dx+e，通過坐標變換轉換為下述形式

E∶y2=x3+ax+b

式中：a、b、x、y屬于有限域Fp，其中p是一個大于3的大質數。假設曲線上的兩點P(x1,y1)，Q(x2,y2)，連接它們的直線L的斜率Δ=(y2-y1)/(x2-x1)。L恰與橢圓曲線相交于另一點R(x3,y3)，則R為Q與P之和的負元，即P+Q=-R。 其中

x3=Δ2-x1-x2

(3)

y3=-x1+Δ(x1-x3)

(4)

點加幾何表示如圖2所示。

圖2 點加幾何表示

為計算點P的兩倍，過P點畫一條切線并找出另一交點S(x3,y3)，則P+P=2P=-S，其中

(5)

(6)

橢圓曲線加密技術是一個很有前途的加密體制，加密時需將明文嵌入橢圓曲線上的隨機一點，解密時需要把橢圓曲線上的點解碼為明文信息，加密解密用公鑰Q和私鑰k進行[10]。橢圓曲線加密過程如圖3所示。

圖3 橢圓曲線加密過程

3 基于ECC的同態加密改進算法

本文提出的改進同態加密算法，兼顧了ECC的低運算復雜度、高安全性與同態加密的密文可操作性。通常加密數據用時僅幾秒甚至幾毫秒，可密鑰存儲在云端會幾年甚至幾十年，攻擊者拿到密文后有足夠的時間來破解。為此，為了加強數據的傳輸及存儲安全性，本文使用不同的私鑰k對明文進行加密，旨在提高基于ECC的同態加密算法的安全性。

設用戶A將上傳并存儲明文 (M1,M2,…,Mn) 到云端，加解密過程如下：

(1)用戶A在本地生成橢圓曲線E及曲線上隨機基點G，同時選擇不同的私鑰 (k1,k2,…,kn) 生成公鑰加密明文以加強整體數據的安全性；

(2)用戶A將基點G與私鑰 (k1,k2,…,kn) 進行標量乘運算生成公鑰 (Q1,Q2,…,Qn)，其中Qi=G·ki，客戶端保存私鑰 (k1,k2,…,kn) 到本地；

(3)為了對明文 (M1,M2,…,Mn) 進行加密操作，用戶A要將明文嵌入到選好的橢圓曲線E中，得到明文點 (Pm1,Pm2,…,Pmn)；

(4)用戶A隨機生成整數 (r1,r2,…,rn)，其中隨機數r

C1i=ri·G

(7)

C2i=C3i·Pmi

(8)

C3i=ri·Qi

(9)

加密后的密文為

C1(C11,C21)…Cn(C1n,C2n)

(10)

(11)

(6)用戶A利用本地存儲的私鑰 (k1,k2,…,kn) 解密

(12)

則

(13)

云端只接收了加密后的密文，無其它可用數據，從而防止了私密消息在云端內部的泄露，同時使用不同的私鑰k對明文加密，極大地加強了安全強度。因此，本文算法既有橢圓曲線加密技術算法的高計算效率、高安全強度，也有同態性。

4 實驗結果與分析

為了對本文算法的計算性能進行測試，本文采用i5處理器、8GRAM，并使用JDK1.8模擬客戶端對用戶的私密信息進行加解密，并將密文傳輸到騰訊云平臺中。

4.1 安全性分析

ECC的安全性取決于橢圓曲線群上離散對數的求解，而橢圓曲線離散對數求解的困難性遠大于分解大素數的困難性，所以基于橢圓曲線加密技術的同態加密相對于RSA同態加密有著更高的安全性。例如曲線y2=x3+x+1，P=23，其散射點分布如圖4所示，包括無窮遠點在內的散射點多達28個，呈現了較強的無序性與離散性。實際工程應用多達200個點以上[11]，所以文中所提的加密算法足以保證實際應用加密算法的有效性。

圖4 橢圓曲線散點

相對于一般加密方式，使用同態加密可以在密文上直接運算，即保證了數據安全和數據隱私，又提高了密文傳輸速率。由于橢圓曲線加密技術的密鑰尺寸和系統參數相對于RSA，DSA要小很多，所以ECC所占存儲空間要小很多[12]。橢圓曲線加密技術的安全強度相對于RSA，DSA有非常明顯的優勢，由表1可知，160位密鑰的橢圓曲線加密技術算法安全強度就相當于1024位密鑰的RSA/DSA算法安全強度，有效地解決了因提高安全強度而增加密鑰長度所帶來的工程實現難的問題。使用不同的私鑰k對明文加密的方式，使該方法的安全性在橢圓曲線加密技術的安全性基礎上又有了極大的提高。所以基于ECC的同態加密方法相對于RSA/DSA同態加密方法有更高的安全性和加密性能。

表1 相同安全等級ECC/RSA/DSA所需密鑰長度

4.2 計算性能分析

為了滿足實際工程的安全需求，實驗采用256 bit的有限域P，同時使用不同長度的密鑰對明文進行加密解密時間見表2。

表2 加密/解密時間

基于橢圓曲線加密技術同態加密方法的加密解密部分基于ECC，明文密文運算基于同態加密，由表1、表2易見隨著密鑰長度的增加，基于橢圓曲線加密技術同態加密方法節約空間的優勢明顯，并且隨著加密強度的提高，該加密方法密鑰長度變化不大，因而基于橢圓曲線加密技術的同態加密方法密鑰短的優點是非常明顯的。本文算法和RSA同態加密算法加解密相同明文的平均時間見表3，本文算法的加解密效率相對RSA同態加密算法具有明顯的優勢，RSA加密算法由于受到素數產生技術的限制，導致密鑰產生很麻煩，因此RSA同態加密的運算效率很低[13]。而本文中使用不同長度的密鑰對本文中的方法進行實驗，加密解密效率理想。

表3 本文算法與RSA算法運算100次平均時間

5 結束語

隨著云計算與大數據的迅速發展，安全問題成為了急需解決的問題。本文結合橢圓曲線加密技術與同態加密技術，提出了一種改進的同態加密方法，該方法既有橢圓曲線加密技術算法的高計算效率、短密鑰、高安全強度，也有同態加密的密文可操作特性。使用不同的私鑰k對數據加密，解決了一個私鑰被破解，全部數據都泄露的問題，從而極大地提高了基于橢圓曲線加密技術的同態加密的安全性。