基于二次剩余的密鑰體制的構(gòu)造①

(安徽理工大學數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001 )

0 引 言

隨著云時代的到來，許多人將自己重要的信息上傳至互聯(lián)網(wǎng)服務(wù)器上，由此而來的互聯(lián)網(wǎng)通訊與共享的數(shù)據(jù)安全性備受關(guān)注。為確保數(shù)據(jù)的安全，首先要做的就是信息加密。在密碼學中加密的方式眾多，公鑰密碼體制因其獨特的優(yōu)點[1],有著不可代替的作用[2]。當選好加密密鑰時，每個明文和每個密文之間的對應(yīng)關(guān)系是雙射的。然而，當把明文進行加密時，對于公鑰密碼體制來說，加密算法的密鑰通常是提前公布出來的。所以，一般而言確定的公鑰密碼體制是很難抵擋住選擇明文的攻擊。對于公鑰密碼體制的這一缺憾，1984年Goldwasser和Micali首次提出了概率密碼體制的概念[3]，但因膨脹率過大沒有實用的價值。文獻[4]和文獻[5]分別提出了基于順序和無序序列的多變量概率公鑰密碼體制，有著良好的隨機性，安全性得到保障。

本文基于二次剩余以及概率加密的思想，對概率公鑰密碼深入研究，構(gòu)造了一種以二次剩余為基礎(chǔ)的多項式加密密鑰體制。新構(gòu)造的二次剩余密鑰體制能夠很好地抵擋選擇明文的攻擊[6]，同時它的密文膨脹率低于Blum和Goldwasser提出的BG密碼體制的密文膨脹率，且密碼體制的安全性不低于RSA公鑰密碼體制的安全性[7]。

1 基本定義與相關(guān)定理

設(shè)n是正整數(shù)集，Zn={x|0x

定義1.2 若n=p·q，其中p和q為兩個互不相同的素數(shù)，并且滿足p≡q≡3mod4，則稱n為Blum數(shù)。

定理1.1[8](歐拉定理)若(a,n)=1，則aφ(n)≡1modn。

定理1.3[9]設(shè)p和q為兩個互不相同的素數(shù)，n=p·q，則對任一整數(shù)a∈Zn*，有a∈Qn，等價于a∈Qp且a∈Qq。

定理1.5[9]設(shè)N=p·q為Blum數(shù)，a∈Qn，則對于x2≡amodN有：

(1)在模N下有4個平方根

(2)這4個平方根有且僅有一個屬于Qn，且

定理1.6 設(shè)N=p·q，其中p和q為兩個互不相同的奇素數(shù)，則分解N計算上等價于求模N的平方根。

2 密碼算法設(shè)計

2.1 密鑰選取

首先：Bob找出兩個較大的素數(shù)p,q(不能公開)，使得p≡q≡3mod4，同時需要計算Blum數(shù)N=p·q

其次：Bob將N公開，作為加密算法中的加密密鑰。

最后：Bob將p,q作為解密算法中的解密密鑰。

2.2 加密算法

步驟1：在Zn上的n次不可約多項式P(x)=a0+a1x+a2x2+…+anxn，明文M為(a0,a1,…,an)，(a0,a1,…,an)為n次不可約多項式的系數(shù)序列。

步驟2： Alice找到Bob提前公布的加密密鑰N，作如下計算：

b0≡a02modN

b1≡a12modN

?

bn≡an2modN

得到序列B=(b0,b1,b2,…,bn)

x0≡k2modN

x1≡x02modN

?

xn+1≡xn2modN

得到序列D=(x1,x2,x3,…,xn+1)

步驟4：再計算出xn+2≡xn+12modN

步驟5：計算E=(b0×x1,b1×x2,…,bn×xn+1)，記c1=b0×x1，c2=b1×x2，…，cn+1=bn×xn+1

步驟6：傳送密文C=(c1,c2,…,cn+1,xn+2)給Bob。

2.3 解密算法

步驟1：Bob獲得Alice發(fā)送的密文C=(c1,c2,…,cn+1,xn+2)之后，根據(jù)定理1.5，依次計算：

?

得到序列D=(x1,x2,x3,…,xn+1)

步驟3：由序列B=(b0,b1,b2,…,bn)以及定理1.5可得：

?

步驟4：最終解出明文M=(a0,a1,…,an)，因此Bob就破譯了Alice發(fā)給他的密文。

3 密碼算法的分析與評價

3.1 正確性分析

3.2 安全性分析

從加密解密過程中不難看出，如果敵方截獲密文和加密密鑰，想要得到明文的相關(guān)信息，就一定要去計算模N下的平方根，由定理1.6，該問題歸結(jié)為分解大合數(shù)為素數(shù)之積的問題，故該加密算法的安全性就等同于RSA加密算法的安全性。同時，我們在加密過程中添加了隨機數(shù)k，使得密文具有隨機性。即我們對一樣的明文使用一樣的加密密鑰，選取不同的隨機數(shù)進行加密時所獲得的密文是有差異的，有效地防止了選擇明文攻擊。所以，這種基于二次剩余的多項式加密的概率公鑰密碼體制的安全性不低于RSA密碼體制的安全性。

3.3 性能分析

從加密解密過程可知，本文設(shè)計的概率公鑰密碼體制主要涉及計算數(shù)模的平方根運算，接下來就對其性能進行分析，主要包括密文膨脹率以及加解密效率兩大方面。

3.3.1 密文膨脹率

3.3.2 加解密效率分析

這種基于二次剩余構(gòu)造的密鑰體制在加密時的時間主要是用在兩次平方求余的計算上，解密是用在兩次模的計算上，其時間復(fù)雜度略高于BG密碼體制，而小于RSA等公鑰密碼體制的時間復(fù)雜度[11]O(k3)。因此，新的概率公鑰密碼體制的加解密效率較高。

4 結(jié) 語

公鑰密碼體制是密碼學中較為普遍且廣泛應(yīng)用的加密體制[12]。對于公鑰密碼算法的加密密鑰而言，通常是提前公布出來的[13]。所以公鑰密碼體制是抵擋不住選擇明文的攻擊。本文以大數(shù)因數(shù)分解的困難性和模Blum數(shù)的二次剩余求平方根的不易性為理論基礎(chǔ)，引入隨機數(shù)，構(gòu)造了一種以二次剩余為基礎(chǔ)的多項式加密密鑰體制。同時，論證了它密碼體制的安全性是不會低于RSA的安全性。利用給出的密碼體制，加解密的效率較高，當傳輸?shù)拿魑妮^長時，它的密文膨脹率近似為1。此外，新構(gòu)造的密鑰體制是針對多項式的概率加密，若是把多項式的系數(shù)序列表示成二次型的矩陣，那么新構(gòu)造的密鑰體制對于圖像加密也同樣適用。