梅　宇, 孫霓剛, 李雪佳

(常州大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 常州　213000)

?

適用于字符串加密的全同態(tài)加密方案

梅宇, 孫霓剛, 李雪佳

(常州大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 常州213000)

現(xiàn)有的全同態(tài)加密思想主要實(shí)現(xiàn)對(duì)整數(shù)進(jìn)行加密，在密文的狀態(tài)下可以實(shí)現(xiàn)加、減、乘、除等四則運(yùn)算，將其密文進(jìn)行解密得到的結(jié)果與對(duì)明文做相同運(yùn)算的結(jié)果一致，然而當(dāng)加密對(duì)象為字符串的時(shí)候這些運(yùn)算將變的毫無意義;為了使得全同態(tài)加密算法可以應(yīng)用在字符串中，設(shè)計(jì)了一個(gè)可以適用于字符串加密的全同態(tài)加密算法;首先介紹了全同態(tài)加密算法在整數(shù)上的實(shí)現(xiàn)原理，通過對(duì)中國(guó)剩余定理的證明過程中發(fā)現(xiàn)了中國(guó)剩余定理具備定位字符的能力，然后將中國(guó)剩余定理引入整數(shù)上全同態(tài)加密的思想中;引入的中國(guó)剩余定理便是可以在加密過程中實(shí)現(xiàn)字符串的定位，避免出現(xiàn)加密完成后無法按照原有順序回復(fù)出原文；最后通過舉例論證的方式，驗(yàn)證了實(shí)現(xiàn)字符串全同態(tài)加密算法的的正確性；從而豐富了全同態(tài)加密算法的使用范圍。

中國(guó)剩余定理; 全同態(tài)加密; 字符串

0　引言

全同態(tài)加密思想是由Rivest等人在1978年提出的，希望在不對(duì)密文進(jìn)行解密的條件下，對(duì)密文進(jìn)行任何運(yùn)算，得到的結(jié)果解密后與明文進(jìn)行相應(yīng)運(yùn)算的結(jié)果相同。這個(gè)思想提出后，國(guó)內(nèi)外研究人員進(jìn)行了大量的研究，直到2009年Gentry提出來基于理想格的全同態(tài)加密方案，并對(duì)該方案進(jìn)行了詳細(xì)論述。此后國(guó)內(nèi)外學(xué)者都提出來許多改進(jìn)的全同態(tài)加密方案。但這些方案的加密對(duì)象都是對(duì)整數(shù)進(jìn)行加密。當(dāng)加密對(duì)象為“字符串”的時(shí)候，現(xiàn)有的算法將毫無辦法。

在“大數(shù)據(jù)時(shí)代”，數(shù)據(jù)信息越來越中重要。數(shù)據(jù)的存儲(chǔ)方式最常見的便是以字符串的形式進(jìn)行存儲(chǔ)。因此設(shè)計(jì)出一種可以適用于字符串的全同態(tài)加密算法，不僅可以擴(kuò)展當(dāng)前全同態(tài)加密算法的應(yīng)用范圍，還可以使得全同態(tài)加密更加具備實(shí)用性。通過對(duì)中國(guó)剩余定理的研究發(fā)現(xiàn)，中國(guó)剩余定理具備了對(duì)字符串進(jìn)行定位的功能，這一功能很好地解決了同態(tài)加密在對(duì)字符串加密時(shí)候，出現(xiàn)亂序的現(xiàn)象。因此在文章中通過中國(guó)剩余定理對(duì)字符串進(jìn)行相應(yīng)的處理，然后通過同態(tài)加密算法對(duì)其進(jìn)行處理。最終得到理想的結(jié)果。

1　全同態(tài)加密

全同態(tài)加密用一句話來說就是:可以對(duì)加密數(shù)據(jù)做任意功能的運(yùn)算，運(yùn)算的結(jié)果解密后是相應(yīng)于對(duì)明文做同樣的運(yùn)算結(jié)果。同態(tài)加密有點(diǎn)穿越的意思，從密文空間穿越到明文空間，但穿越的時(shí)候是要被蒙上眼睛的。

Gentry[4-5]構(gòu)造同態(tài)加密的思想包括4個(gè)部分：密鑰生成算法、解密算法、加密算法和評(píng)估算法。所謂的全同態(tài)加密包括兩種基本的同態(tài)類型：加法同態(tài)和乘法同態(tài)。

1.1全同態(tài)加密原理

定義一下符號(hào)，E:加密算法,m:明文,e:加密結(jié)果,f:針對(duì)明文的計(jì)算操作。

原理e=E(m),m=E’(e)。針對(duì)E構(gòu)造F使得F(e)=E(f(m)),因此E就是對(duì)于f的同態(tài)加密算法。而全同態(tài)就是指，給出任意的f，都可以構(gòu)造出相應(yīng)的F。全同態(tài)的目的在于找到一個(gè)可以在密文數(shù)據(jù)上進(jìn)行任意次數(shù)的加密算法，是對(duì)密文數(shù)據(jù)進(jìn)行某種操作的結(jié)果等于對(duì)明文做相應(yīng)操作的結(jié)果。

1.2全同態(tài)加密算法實(shí)現(xiàn)

為了簡(jiǎn)便，在本文中使用了Gentry所提出的對(duì)稱全同態(tài)加密算法[6]。

KeyGen(λ) 根據(jù)安全參數(shù)λ產(chǎn)生ηbit的奇數(shù)p作為算法的私鑰。

Encrypt(sk,m) 對(duì)于明文m={0,1}，計(jì)算密c=m+2r+pq其中r為隨機(jī)選取ρbit的整數(shù)，q是一個(gè)很大的整數(shù)。

Decrypt(sk,c) 計(jì)算m=(cmodp)mod2，恢復(fù)明文。

cmodp的值稱為噪聲。如果m+2r

1.3同態(tài)性驗(yàn)證

假設(shè)兩組明文m1,m2分別對(duì)其加密：c1=m1+2r1+pq1,c2=m2+2r2+pq2;則

c1+c2=(m1+2r1+pq1)+(m2+2r2+pq2)=(m1+m2)+2(r1+r2)+p(q1+q2);

c1*c2=(m1+2r1+pq1)*(m2+2r2+pq2)=m1m2+2(2r1r2+r1m1+r2m2)+p[pq1q2+q2(m1+2r1)+q1(m2+2r2)];

當(dāng)(m1+m2)+2(r1+r2)

綜上所述，上面的方案滿足加法同態(tài)與乘法同態(tài)，但是方案存在噪聲，隨著密文的運(yùn)算次數(shù)的增加，噪聲也會(huì)隨之增長(zhǎng)，當(dāng)噪聲大于p/2時(shí)，上述等式便不成立。加法運(yùn)算得到的噪聲等于各自噪聲之和，乘法運(yùn)算得到的噪聲等于各自噪聲之積。對(duì)于如何降低噪聲，使之實(shí)現(xiàn)任意處運(yùn)算不在本文的討論范圍內(nèi)。

2　中國(guó)剩余定理

2.1公式

用現(xiàn)代語(yǔ)言來來描述，中國(guó)剩余定理給出了以下一元線性同余方程組[7]：

有解的判定條件，并用構(gòu)造法給出了在有解的情況下解的具體形式:

中國(guó)剩余定理說明[8-9]，假設(shè)整數(shù)m1,m2…mn兩兩互質(zhì)，對(duì)于任意的整數(shù)a1,a2…an方程組(s)有解，并且通解可以通過以下構(gòu)造：

3　字符串?dāng)?shù)據(jù)的同態(tài)加密算法

3.1算法描述

與整數(shù)的同態(tài)加密不同，整數(shù)加密后能夠?qū)崿F(xiàn)對(duì)密文的加、減、乘、除運(yùn)算對(duì)字符串是毫無意義。了實(shí)現(xiàn)字符串的同態(tài)加密，通過利用中國(guó)剩余定理將字符串轉(zhuǎn)換，然后利用同態(tài)算法進(jìn)行加密處理。具體步驟如下:

(1) 假設(shè)一個(gè)字符串B，截取該字符串中的每一個(gè)字符并將其轉(zhuǎn)換為對(duì)于的ASCII碼，將其對(duì)應(yīng)的ASCII碼分別記為b1,b2,…,bk。(其中k為字符串中字符的個(gè)數(shù))。

(2) 由中國(guó)剩余定理中的要求，選取k個(gè)兩兩互為指數(shù)的正整數(shù)，分別記為:m1,m2,…,mk其中(mi>121)。

(3) 有中國(guó)剩余定理的同余式組:

其中:M=m1*m2*…*mk,Mi=M/mi(i=1,2…,k)，ti=Mi-1(i=1,2,…,k)。x便是需要加密的數(shù)值。

(5) 根據(jù)全同態(tài)加密算法解密后可以得到加密數(shù)據(jù)x，根據(jù)公式bi=xmodmi，可以復(fù)原每個(gè)字符串中字符多對(duì)應(yīng)的ASCII碼值。

3.2算法正確性證明

3.2.1字符串與加密數(shù)據(jù)的對(duì)應(yīng)關(guān)系

從假設(shè)可知，對(duì)于任意的i∈{1,2,…,k}。由于?j∈{1,2...k},j≠i，gcd(mi,mj)=1。所以得出gcd(mi,Mi)=1。

因此可以說明存在一個(gè)整數(shù)ti可以使得bitiMi≡0(modmj)，這樣的ti叫做Mi模mi的數(shù)論倒數(shù)。由此可知[10]：

bitiMi≡bi*1≡bi(modmi)

?j∈{1,2,...,n},j≠i，bitiMi≡0(modmj)。因此x=b1t1M1+b2t2M2+…+bktkMk滿足以下等式:

說明x為上述方程組(s)的一個(gè)解。

此外，假設(shè)x1,x2都是方程組(s)的解,對(duì)于任意的i∈{1,2,…,k},x1-x2≡0(modmi)，由條件可知m1,m2,…,mk是互為質(zhì)數(shù)的，得到M=m1*m2*…*mk是整除x1-x2。應(yīng)此上述方程組(s)的任意兩個(gè)解之間必然相差M的整數(shù)倍數(shù)。而另一方面，

x=b1t1M1+b2t2M2+…+bktkMk

是方程組的一個(gè)解，應(yīng)此我們可以得到方程組解所有的形式:

b1t1M1+b2t2M2+…+bktkMk+kM=

所以可以得到方程組的解的集合：

模M的意義下：其結(jié)果為

x=b1t1M1+b2t2M2+...+bktkMk

根據(jù)設(shè)計(jì)的算法第五步計(jì)算：bi=xmodmi。即b1=xmodm1,…,bk=xmodmk。分析如下:

b1=xmodm1=(b1t1M1+b2t2M2+…+bktkMk)modmi=

( b1t1M1) mod m1+( b2t2M2) mod m2+…+(bktkMk)

mod mk

因?yàn)镸i=M/mi=(m1*m2*…*mk)/mi，由此公式可知，Mi不是mi的整數(shù)倍，即Mi/mi有余數(shù)，而Mi≠i/mi沒有余數(shù)。因此b1=xmodm1=(b1t1M1+b2t2M2+…+bktkMk)modmi=(b1t1M1)modm1+(b2t2M2)modm2+…+(bktkMk)modmk=(b1t1M1)modm1=b1t1M1。又因?yàn)椋瑃i與Mi模mi的數(shù)論倒數(shù)，所以tiMi=1(modmi)

所以得到b1=b1,同理可知,b2=b2,b3=b3,…,bk=bk。

綜上所述，證明了本文提出的利用字符串和加密數(shù)值之間的對(duì)應(yīng)關(guān)系，在下面的一節(jié)中對(duì)加密方案的可行性進(jìn)行分析。

3.2.2對(duì)所得方程組解進(jìn)行同態(tài)加密

根據(jù)上文提出的字符串同態(tài)加密算法的結(jié)果，得到了需要加密的x的整數(shù)值，將整數(shù)x轉(zhuǎn)化為二進(jìn)制，通過2.2節(jié)中提出的同態(tài)加密算法，對(duì)其結(jié)果進(jìn)行加密。(注：文中的同態(tài)加密算法一次只能加密1 bit，效率比較慢。在全同態(tài)加密算發(fā)相關(guān)的文章中，通過各種改進(jìn)方法一次可以加密多bit。在本文中，為了簡(jiǎn)化描述，選取了一次加密1 bit的同態(tài)加密算法)。因此，可以說明上述同余方程組的解是可以利用同態(tài)加密算法的。因此本文提出的方案具有正確性。

方案的安全性是基于近似最大公約數(shù)問題，下面給出近似最大公約數(shù)問題的定義:

定義:近似最大公約數(shù)問題(approximate-GCD problem)。隨機(jī)選擇n個(gè)大整數(shù)p的近似倍數(shù)a1,a2,a3,…,an，根據(jù)a1,a2,a3,…,an,求出p的過程就稱為近似最大公約數(shù)問題。

3.2.3舉例論證

給定一個(gè)字符串AB，則A的ASCII碼值為：b1=41，B的ASCII碼值為:b2=42;隨機(jī)取兩個(gè)互為質(zhì)數(shù)的m1=122,m2=123。由中國(guó)剩余定理得出同余方程組:

M=m1*m2=122*123=15 006;則M1=M/m1=123，M2=M/m2=122；由tiMi≡1(modmi)可知:t1M1≡1(modm1)可推出t1=1，t2M2≡1(modm2)推出t2=122。根據(jù)上述中國(guó)剩余定理的通解公式:

(41*1*123+42*122*122)mod15 006

=14 925

將x轉(zhuǎn)換為二進(jìn)制為11 1010 0100 1101。將該二進(jìn)制從左到右依次即為:C13,C12,C11,…,C0。對(duì)每一位進(jìn)行文中提到的同態(tài)加密算法進(jìn)行加密，在這里只選取C0，C1作為代表。

選取特定的數(shù)值，設(shè)p=11,q=5,C0=m0=1,C1=m1=0,隨機(jī)選去r1=1,則有以下等式成立:

C0=Enc(m0)=m0+2r1+pq=1+2*1+11*5=58;

C0(modp)=58mod11=3;

m0’=3mod2=1;

C1=Enc(m1)=m1+2r1+pq=0+2*1+11*5=57;

C1(modp)=57mod11=2;

m1’=2mod2=0;

…

所以對(duì)二進(jìn)制數(shù)據(jù)加密的結(jié)果為:………..57,58解密后的結(jié)果:11 1010 0100 1101,恢復(fù)為十進(jìn)制為14925。根據(jù)bi=xmodmi恢復(fù)出原來字符串所對(duì)應(yīng)的ASCII碼值。

b1=xmodm1=14925mod122 =41,對(duì)應(yīng)的字符是A；

b2=xmodm2=14925mod123=42,對(duì)應(yīng)的字符是B；

因此，對(duì)字符串加密進(jìn)行了復(fù)原，但這只是對(duì)單個(gè)字符串進(jìn)行加密的，當(dāng)然也可以對(duì)字符串進(jìn)行運(yùn)算如A+B和A*B等運(yùn)算，運(yùn)算的步驟和單個(gè)字符串的步驟相同，通過類型的方法即可恢復(fù)，由于篇幅問題，在本文中就不作展開論述。只是我們要注意同態(tài)加密的條件：噪聲要小于p/2，必須是在選取參數(shù)的時(shí)候注意。

3.2.4實(shí)驗(yàn)結(jié)果與分析

上一個(gè)小節(jié)中對(duì)適用于字符串的全同態(tài)加密算法的正確性進(jìn)行驗(yàn)證。通過對(duì)字符串“AB”代入文中所設(shè)計(jì)的算法，通過了轉(zhuǎn)化、加密、解密等步驟最終完整的恢復(fù)出了字符串“AB”，沒有打破原文字符串的順序，實(shí)驗(yàn)的結(jié)果與預(yù)期所設(shè)計(jì)的一樣。證明了文中所提出的適用于字符串的全同態(tài)加密的正確性。在實(shí)驗(yàn)過程對(duì)選取字符串“AB”將其轉(zhuǎn)化為ASCII碼，然后通過中國(guó)剩余定理將字符串所對(duì)應(yīng)的ASCII碼，轉(zhuǎn)化成一個(gè)整數(shù)X，最后通過對(duì)X使用同態(tài)加密算法，得到密文Y。在解密階段，根據(jù)算法提出的公式進(jìn)行解密，這樣便可以得到了字符串“AB”所對(duì)應(yīng)的ASCII碼，便于恢復(fù)出相應(yīng)的字符串。

通過對(duì)整個(gè)實(shí)驗(yàn)結(jié)果和過程進(jìn)行分析，雖然實(shí)驗(yàn)的結(jié)果是正確時(shí)。但是在算法的加密階段，對(duì)二進(jìn)制數(shù)據(jù)的加密是按照一位一位進(jìn)行加密的，這樣的效率肯定不高。為了提高算法的加密的效率，有一個(gè)改進(jìn)的思想，在全同態(tài)加密算法實(shí)現(xiàn)的時(shí)候，加密公式為：c=m+2r+pq。將其修改為c=m+4r+pq。同時(shí)對(duì)解密公式進(jìn)行修改為=(cmodp)mod4。這樣可以對(duì)二進(jìn)制數(shù)據(jù)每次可以加密兩位數(shù)據(jù)，在一定的程度上提高了加密的效率。對(duì)相應(yīng)算法的改進(jìn)，還需考慮到算法參數(shù)的選取、算法噪聲的分析等多個(gè)方面，同時(shí)也為以后的研究提供了方向。

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

本文所提出的利用中國(guó)剩余定理實(shí)現(xiàn)字符串的同態(tài)加密算法，在具體的實(shí)現(xiàn)過程中還是會(huì)存在一些問題，比如：素?cái)?shù)的選取和存儲(chǔ)等問題以及x值過大的問題，都對(duì)同態(tài)加密算法的效率產(chǎn)生比較大的影響。但在安全性方面，它還是保留了整數(shù)同態(tài)加密特點(diǎn)。

全同態(tài)加密技術(shù)是一種能對(duì)密文數(shù)據(jù)進(jìn)行數(shù)學(xué)運(yùn)算的加密機(jī)制，在數(shù)據(jù)庫(kù)加密和云服務(wù)中有比較廣泛的應(yīng)用。本文提出的方案，實(shí)現(xiàn)對(duì)字符串進(jìn)行加密，豐富了同態(tài)加密的應(yīng)用范圍，在同態(tài)加密的原理上對(duì)其進(jìn)行擴(kuò)展，并驗(yàn)證了算法的正確性。但還存在一些不足之處，是以后所研究的重點(diǎn)。

[1] Riverst R,Shamir A,Dertouzos M. On data banks privacy homomorphisms[J]. Foundations of Secure Computation,1978,7(1): 169-177.

[2] 石中盤，蔡萃燕.面向數(shù)據(jù)庫(kù)加密的秘密同態(tài)算法的研究[J].計(jì)算機(jī)應(yīng)用研究,2009,26(4):1535-1537.

[3] 陳智罡，王箭.全同態(tài)加密研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(6):1624-1631.

[4] Gentr Y. Fully homomorphic encryption using ideal lattices[A]. Proc of the 41st Annual ACM symposium on Theory of Compting[C]. NewYork:ACM Press,2009:169-178.

[5] Boneh D,Gentr,Ygentr Y. A fully homomorphic encryption scheme [D]. Stanford:Stanford University,2009.

[6] 林如磊，王箭,等.整數(shù)上全同態(tài)加密方案的改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究,2013,30(5):1515-1519.

[7] 楊坤偉,李吉亮,等. 中國(guó)剩余定理在密碼學(xué)中的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(1):238-241.

[8] 陳代梅，范希輝,等.基于同余方程和中國(guó)剩余定理的混淆算法[J].計(jì)算機(jī)應(yīng)用研究.2015,32(1): 1588-1592.

[9] 楊波. 現(xiàn)代密碼學(xué)[M].北京:清華大學(xué)出版社,2003.

[10] 陳澤文，張龍軍，王育民.一種基于中國(guó)剩余定理的群簽名方案[J].電子學(xué)報(bào),2004,32(7):1062-1065.

Fully Homomorphic Encryption Scheme Applied to String Computer Engineering

Mei Yu, Sun Nicang, Li Xuejia

(School of Information Science & Engineering,Changzhou University,Changzhou213000,China)

Existing full state encryption thought is mainly encrypted integers. Under the secret state,it can conduct add,subtract,multiply,divide and other operations. The results of private texts decryptions are consistent with the results of plain text. However,when the encrypted object becomes the string,these operations will become meaningless. In order to make full state encryption algorithm can be used in the string,the design applies to a whole string of state encryption algorithm. Firstly it introduced full state encryption algorithm theory on integers. During the prove process of Chinese Remainder Theorem,it could be found that Chinese Remainder Theorem has ability to locate character and then introduced Chinese remainder theorem into integer full state encryption thoughts. Introduced Chinese remainder theorem can locate strings in the encryption process and avoid the problem that after the completion of encryption,it could not return to original text based on original order. Finally,by way of example argument,it proved the correctness of string full text encryption algorithm. Thus the application range of full text encryption algorithm could be enriched.

Chinese remainder theorem; fully homomorphic encryption; character string

1671-4598(2016)04-0195-04DOI：10.16526/j.cnki.11-4762/tp.2016.04.057

TP309

A

2015-10-20；

2015-11-12。

國(guó)家自然科學(xué)基金(61103172)。

梅宇(1989-),男,碩士研究生,主要從事信息安全，密碼學(xué)方向的研究。