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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

2 密碼算法設(shè)計(jì)

2.1 密鑰選取

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

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

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

2.2 加密算法

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

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

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：再計(jì)算出xn+2≡xn+12modN

步驟5：計(jì)算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，依次計(jì)算：

?

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

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

?

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

3 密碼算法的分析與評(píng)價(jià)

3.1 正確性分析

3.2 安全性分析

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

3.3 性能分析

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

3.3.1 密文膨脹率

3.3.2 加解密效率分析

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

4 結(jié) 語

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