基于ECC與同態(tài)加密的加密算法

劉 艷，郎顯赫+，裴少婧

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

0 引 言

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

1 同態(tài)加密技術(shù)

同態(tài)加密允許服務(wù)器在不知道原始明文的情況下做加密數(shù)據(jù)的操作，允許對加密后的數(shù)據(jù)執(zhí)行特定的數(shù)學(xué)運算并且解密結(jié)果和對應(yīng)明文進行運算后的結(jié)果是一致的，從而保護了數(shù)據(jù)[6]。數(shù)據(jù)加密解密基本流程如圖1所示。

圖1 數(shù)據(jù)加密解密基本流程

假設(shè)一個加密系統(tǒng)中加密算法為CK，解密算法為DK，明文為n、m，則同態(tài)加密滿足如下屬性

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

(1)

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

(2)

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

2 橢圓曲線加密技術(shù)

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

設(shè)基礎(chǔ)域F，x,y屬于F且滿足如下：

y2+axy+by=x3+cx2+dx+e，通過坐標(biāo)變換轉(zhuǎn)換為下述形式

E∶y2=x3+ax+b

式中：a、b、x、y屬于有限域Fp，其中p是一個大于3的大質(zhì)數(shù)。假設(shè)曲線上的兩點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)

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

圖3 橢圓曲線加密過程

3 基于ECC的同態(tài)加密改進算法

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

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

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

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

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

(4)用戶A隨機生成整數(shù) (r1,r2,…,rn)，其中隨機數(shù)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)

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

4 實驗結(jié)果與分析

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

4.1 安全性分析

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

圖4 橢圓曲線散點

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

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

4.2 計算性能分析

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

表2 加密/解密時間

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

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

5 結(jié)束語

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