适用于字符串加密的全同态加密方案

梅　宇, 孙霓刚, 李雪佳

(常州大学 信息科学与工程学院，江苏 常州　213000)



适用于字符串加密的全同态加密方案

梅宇, 孙霓刚, 李雪佳

(常州大学 信息科学与工程学院，江苏 常州213000)

现有的全同态加密思想主要实现对整数进行加密，在密文的状态下可以实现加、减、乘、除等四则运算，将其密文进行解密得到的结果与对明文做相同运算的结果一致，然而当加密对象为字符串的时候这些运算将变的毫无意义;为了使得全同态加密算法可以应用在字符串中，设计了一个可以适用于字符串加密的全同态加密算法;首先介绍了全同态加密算法在整数上的实现原理，通过对中国剩余定理的证明过程中发现了中国剩余定理具备定位字符的能力，然后将中国剩余定理引入整数上全同态加密的思想中;引入的中国剩余定理便是可以在加密过程中实现字符串的定位，避免出现加密完成后无法按照原有顺序回复出原文；最后通过举例论证的方式，验证了实现字符串全同态加密算法的的正确性；从而丰富了全同态加密算法的使用范围。

中国剩余定理; 全同态加密; 字符串

0　引言

全同态加密思想是由Rivest等人在1978年提出的，希望在不对密文进行解密的条件下，对密文进行任何运算，得到的结果解密后与明文进行相应运算的结果相同。这个思想提出后，国内外研究人员进行了大量的研究，直到2009年Gentry提出来基于理想格的全同态加密方案，并对该方案进行了详细论述。此后国内外学者都提出来许多改进的全同态加密方案。但这些方案的加密对象都是对整数进行加密。当加密对象为“字符串”的时候，现有的算法将毫无办法。

在“大数据时代”，数据信息越来越中重要。数据的存储方式最常见的便是以字符串的形式进行存储。因此设计出一种可以适用于字符串的全同态加密算法，不仅可以扩展当前全同态加密算法的应用范围，还可以使得全同态加密更加具备实用性。通过对中国剩余定理的研究发现，中国剩余定理具备了对字符串进行定位的功能，这一功能很好地解决了同态加密在对字符串加密时候，出现乱序的现象。因此在文章中通过中国剩余定理对字符串进行相应的处理，然后通过同态加密算法对其进行处理。最终得到理想的结果。

1　全同态加密

全同态加密用一句话来说就是:可以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样的运算结果。同态加密有点穿越的意思，从密文空间穿越到明文空间，但穿越的时候是要被蒙上眼睛的。

Gentry[4-5]构造同态加密的思想包括4个部分：密钥生成算法、解密算法、加密算法和评估算法。所谓的全同态加密包括两种基本的同态类型：加法同态和乘法同态。

1.1全同态加密原理

定义一下符号，E:加密算法,m:明文,e:加密结果,f:针对明文的计算操作。

原理e=E(m),m=E’(e)。针对E构造F使得F(e)=E(f(m)),因此E就是对于f的同态加密算法。而全同态就是指，给出任意的f，都可以构造出相应的F。全同态的目的在于找到一个可以在密文数据上进行任意次数的加密算法，是对密文数据进行某种操作的结果等于对明文做相应操作的结果。

1.2全同态加密算法实现

为了简便，在本文中使用了Gentry所提出的对称全同态加密算法[6]。

KeyGen(λ) 根据安全参数λ产生ηbit的奇数p作为算法的私钥。

Encrypt(sk,m) 对于明文m={0,1}，计算密c=m+2r+pq其中r为随机选取ρbit的整数，q是一个很大的整数。

Decrypt(sk,c) 计算m=(cmodp)mod2，恢复明文。

cmodp的值称为噪声。如果m+2r

1.3同态性验证

假设两组明文m1,m2分别对其加密：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)];

当(m1+m2)+2(r1+r2)

综上所述，上面的方案满足加法同态与乘法同态，但是方案存在噪声，随着密文的运算次数的增加，噪声也会随之增长，当噪声大于p/2时，上述等式便不成立。加法运算得到的噪声等于各自噪声之和，乘法运算得到的噪声等于各自噪声之积。对于如何降低噪声，使之实现任意处运算不在本文的讨论范围内。

2　中国剩余定理

2.1公式

用现代语言来来描述，中国剩余定理给出了以下一元线性同余方程组[7]：

有解的判定条件，并用构造法给出了在有解的情况下解的具体形式:

中国剩余定理说明[8-9]，假设整数m1,m2…mn两两互质，对于任意的整数a1,a2…an方程组(s)有解，并且通解可以通过以下构造：

3　字符串数据的同态加密算法

3.1算法描述

与整数的同态加密不同，整数加密后能够实现对密文的加、减、乘、除运算对字符串是毫无意义。了实现字符串的同态加密，通过利用中国剩余定理将字符串转换，然后利用同态算法进行加密处理。具体步骤如下:

(1) 假设一个字符串B，截取该字符串中的每一个字符并将其转换为对于的ASCII码，将其对应的ASCII码分别记为b1,b2,…,bk。(其中k为字符串中字符的个数)。

(2) 由中国剩余定理中的要求，选取k个两两互为指数的正整数，分别记为:m1,m2,…,mk其中(mi>121)。

(3) 有中国剩余定理的同余式组:

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

(5) 根据全同态加密算法解密后可以得到加密数据x，根据公式bi=xmodmi，可以复原每个字符串中字符多对应的ASCII码值。

3.2算法正确性证明

3.2.1字符串与加密数据的对应关系

从假设可知，对于任意的i∈{1,2,…,k}。由于∀j∈{1,2...k},j≠i，gcd(mi,mj)=1。所以得出gcd(mi,Mi)=1。

因此可以说明存在一个整数ti可以使得bitiMi≡0(modmj)，这样的ti叫做Mi模mi的数论倒数。由此可知[10]：

bitiMi≡bi*1≡bi(modmi)

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

说明x为上述方程组(s)的一个解。

此外，假设x1,x2都是方程组(s)的解,对于任意的i∈{1,2,…,k},x1-x2≡0(modmi)，由条件可知m1,m2,…,mk是互为质数的，得到M=m1*m2*…*mk是整除x1-x2。应此上述方程组(s)的任意两个解之间必然相差M的整数倍数。而另一方面，

x=b1t1M1+b2t2M2+…+bktkMk

是方程组的一个解，应此我们可以得到方程组解所有的形式:

b1t1M1+b2t2M2+…+bktkMk+kM=

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

模M的意义下：其结果为

x=b1t1M1+b2t2M2+...+bktkMk

根据设计的算法第五步计算：bi=xmodmi。即b1=xmodm1,…,bk=xmodmk。分析如下:

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

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

mod mk

因为Mi=M/mi=(m1*m2*…*mk)/mi，由此公式可知，Mi不是mi的整数倍，即Mi/mi有余数，而Mi≠i/mi没有余数。因此b1=xmodm1=(b1t1M1+b2t2M2+…+bktkMk)modmi=(b1t1M1)modm1+(b2t2M2)modm2+…+(bktkMk)modmk=(b1t1M1)modm1=b1t1M1。又因为，ti与Mi模mi的数论倒数，所以tiMi=1(modmi)

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

综上所述，证明了本文提出的利用字符串和加密数值之间的对应关系，在下面的一节中对加密方案的可行性进行分析。

3.2.2对所得方程组解进行同态加密

根据上文提出的字符串同态加密算法的结果，得到了需要加密的x的整数值，将整数x转化为二进制，通过2.2节中提出的同态加密算法，对其结果进行加密。(注：文中的同态加密算法一次只能加密1 bit，效率比较慢。在全同态加密算发相关的文章中，通过各种改进方法一次可以加密多bit。在本文中，为了简化描述，选取了一次加密1 bit的同态加密算法)。因此，可以说明上述同余方程组的解是可以利用同态加密算法的。因此本文提出的方案具有正确性。

方案的安全性是基于近似最大公约数问题，下面给出近似最大公约数问题的定义:

定义:近似最大公约数问题(approximate-GCD problem)。随机选择n个大整数p的近似倍数a1,a2,a3,…,an，根据a1,a2,a3,…,an,求出p的过程就称为近似最大公约数问题。

3.2.3举例论证

给定一个字符串AB，则A的ASCII码值为：b1=41，B的ASCII码值为:b2=42;随机取两个互为质数的m1=122,m2=123。由中国剩余定理得出同余方程组:

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。根据上述中国剩余定理的通解公式:

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

=14 925

将x转换为二进制为11 1010 0100 1101。将该二进制从左到右依次即为:C13,C12,C11,…,C0。对每一位进行文中提到的同态加密算法进行加密，在这里只选取C0，C1作为代表。

选取特定的数值，设p=11,q=5,C0=m0=1,C1=m1=0,随机选去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;

…

所以对二进制数据加密的结果为:………..57,58解密后的结果:11 1010 0100 1101,恢复为十进制为14925。根据bi=xmodmi恢复出原来字符串所对应的ASCII码值。

b1=xmodm1=14925mod122 =41,对应的字符是A；

b2=xmodm2=14925mod123=42,对应的字符是B；

因此，对字符串加密进行了复原，但这只是对单个字符串进行加密的，当然也可以对字符串进行运算如A+B和A*B等运算，运算的步骤和单个字符串的步骤相同，通过类型的方法即可恢复，由于篇幅问题，在本文中就不作展开论述。只是我们要注意同态加密的条件：噪声要小于p/2，必须是在选取参数的时候注意。

3.2.4实验结果与分析

上一个小节中对适用于字符串的全同态加密算法的正确性进行验证。通过对字符串“AB”代入文中所设计的算法，通过了转化、加密、解密等步骤最终完整的恢复出了字符串“AB”，没有打破原文字符串的顺序，实验的结果与预期所设计的一样。证明了文中所提出的适用于字符串的全同态加密的正确性。在实验过程对选取字符串“AB”将其转化为ASCII码，然后通过中国剩余定理将字符串所对应的ASCII码，转化成一个整数X，最后通过对X使用同态加密算法，得到密文Y。在解密阶段，根据算法提出的公式进行解密，这样便可以得到了字符串“AB”所对应的ASCII码，便于恢复出相应的字符串。

通过对整个实验结果和过程进行分析，虽然实验的结果是正确时。但是在算法的加密阶段，对二进制数据的加密是按照一位一位进行加密的，这样的效率肯定不高。为了提高算法的加密的效率，有一个改进的思想，在全同态加密算法实现的时候，加密公式为：c=m+2r+pq。将其修改为c=m+4r+pq。同时对解密公式进行修改为=(cmodp)mod4。这样可以对二进制数据每次可以加密两位数据，在一定的程度上提高了加密的效率。对相应算法的改进，还需考虑到算法参数的选取、算法噪声的分析等多个方面，同时也为以后的研究提供了方向。

4　结束语

本文所提出的利用中国剩余定理实现字符串的同态加密算法，在具体的实现过程中还是会存在一些问题，比如：素数的选取和存储等问题以及x值过大的问题，都对同态加密算法的效率产生比较大的影响。但在安全性方面，它还是保留了整数同态加密特点。

全同态加密技术是一种能对密文数据进行数学运算的加密机制，在数据库加密和云服务中有比较广泛的应用。本文提出的方案，实现对字符串进行加密，丰富了同态加密的应用范围，在同态加密的原理上对其进行扩展，并验证了算法的正确性。但还存在一些不足之处，是以后所研究的重点。

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

[2] 石中盘，蔡萃燕.面向数据库加密的秘密同态算法的研究[J].计算机应用研究,2009,26(4):1535-1537.

[3] 陈智罡，王箭.全同态加密研究[J].计算机应用研究,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] 林如磊，王箭,等.整数上全同态加密方案的改进[J].计算机应用研究,2013,30(5):1515-1519.

[7] 杨坤伟,李吉亮,等. 中国剩余定理在密码学中的研究[J].计算机技术与发展,2014,24(1):238-241.

[8] 陈代梅，范希辉,等.基于同余方程和中国剩余定理的混淆算法[J].计算机应用研究.2015,32(1): 1588-1592.

[9] 杨波. 现代密码学[M].北京:清华大学出版社,2003.

[10] 陈泽文，张龙军，王育民.一种基于中国剩余定理的群签名方案[J].电子学报,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。

国家自然科学基金(61103172)。

梅宇(1989-),男,硕士研究生,主要从事信息安全，密码学方向的研究。