張佳茜+夏若時+張勇

摘 要：在BG公鑰密碼的基礎上，利用以Blum數(shù)為模的二次同余的平方根不可計算的理論，采用引入隨機數(shù)進行多輪二次同余計算，組成隨機的二進制矩陣并逐位加密的新方法，設計了一種新型的概率公鑰密碼系統(tǒng)。此密碼系統(tǒng)的強度是多項式安全的，加密速度比RSA快，密文膨脹率略大于1，適合加密長消息，能抵抗選擇明文攻擊。

關鍵詞：概率密碼；二次同余；矩陣加密

中圖分類號： TP309.7 文獻標識碼：A

Research of A New Probabilistic Public Key Cryptosystem

Zhang Jia-xi1， Xia Ruo-shi2， Zhang Yong3

（1.Hubei Wuchang Experimental High School， Hubei Wuhan 430060；

2.Wuhan Foreign Languages Schooll， Hubei Wuhan 430022；

3.Wuhan Vocational College of Software and Engineeringl， Hubei Wuhan 430205）

Abstract： Based on the BG public key cryptosystem， a new probabilistic public key cryptosystem is proposed， using the theory of the intractability of solving the square roots in quadratic congruence equation with a Blum integer modulus， making use of the new method by means of introducing a random number in several rounds of quadratic congruence calculation， consisting of binary matrix with random and encrypting data bit by bit. The strength of this cryptosystem is polynomial secure. The encryption speed is faster than RSA， Ciphertext expansion rate is slightly more than 1， being suitable for encrypting long messages and resisting chosen plaintext attack.

Key words： Probabilistic Cryptosystem； Quadratic Congruence； Matric Encryption

1 引言

在密碼學里，公鑰密碼體制有著許多對稱密鑰密碼體制所沒有的優(yōu)勢，它能很好地實現(xiàn)數(shù)字簽名、密鑰分發(fā)、防抵賴及身份認證等。但通常所說的公鑰密碼是確定型的密碼，即當加密密鑰確定后，對于相同的明文只能產(chǎn)生相同的密文。由于公鑰密碼體制都是公開加密密鑰的，因此這種確定型的公鑰密碼無法抵抗選擇明文攻擊。針對這一弱點，1984年S.Goldwasser 和S.Micali發(fā)表了基于“不可逼近陷門謂詞”理論[1]的概率加密（Probabilistic Encryption）的思想，并設計了GM概率密碼體制，但其密文膨脹率是明文的400多倍，而無實用價值。1985年，M.Blum和S.Goldwasser提出了BG概率公鑰密碼系統(tǒng)[2]。該系統(tǒng)將密文膨脹率降低到1+（其中k表示密碼體制中模數(shù)的長度，即安全系數(shù)，l表示明文的長度），能基本符合實際使用的要求。

本文是針對確定型公鑰密碼體制中存在著可能受到選擇明文攻擊的缺陷，專門對概率型的公鑰密碼BG密碼進行了深入地研究，并在其基礎上，對其加密和解密方法進行了重新設計和改進，提出了基于二次同余理論，使用二次同余數(shù)二進制矩陣逐位加密的概率密碼的新算法，能有效防止選擇明文攻擊，同時還具有安全性是多項式安全，密文膨脹率低，加密效率高于RSA，可用于長消息加密等優(yōu)點。

2 二次同余理論中的相關知識

二次同余理論，也叫平方剩余問題，是被廣泛用于密碼學特別是用于概率密碼的數(shù)學理論基礎。

設n是正整數(shù)集，， 。

定義2.1[4] 若，且存在x滿足二次同余式 ，則稱a為模n的二次同余，稱x為模n下a的平方根。模n的所有二次同余的集合記為Qn，若且，則稱a為模n的非二次同余，模n的所有非二次同余的集合記為。

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

定理2.1[16] （歐拉定理）

若 a、n互素，即（a，n）=1，則：

其中為歐拉數(shù)，若n=p·q（p 、 q均為素數(shù)），===

定理2.2[4] 二次同余的判定定理----歐拉準則

設p為素數(shù)，則對任意的，若，當且僅當；

引理1[16] 二次非同余的充分必要條件是。

定理2.3[16] 設p、q為兩個互不相同的素數(shù)， n=p·q，則對任一整數(shù)，有，等價于 且。

此定理說明對于n=p·q（p、q為互不相同的素數(shù)），則a是模n的二次同余的充要條件為：a是模 p的二次同余且a是模q的二次同余。

定理2.4[4] 若p為素數(shù)且，（Qp為模p的所有二次同余的集合），則在模p下有且僅有二個平方根，分別為。endprint

定理2.5[4] 設n=p·q為Blum數(shù)，，則對于有：

①在模n下有四個平方根；

②這四個平方根中僅有一個，其表達式為：

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

定理2.7[4] 設n為合數(shù)，并且有形如的完全分解，則當且僅當 ，于是當且僅當對任意的素數(shù)pi，i=1，2，3，……k有成立。

可見，若已知n的分解，給定，x模n的二次同余就可以通過確定每個素數(shù)p|n的二次同余來確定，而這是可以通過驗證歐拉準則來確定的。

但是，如果不知道n的分解，確定模n的二次同余就是非常困難的。

定理2.8[4] 設素數(shù)p滿足，且。令 ，

1） 如果y有一個模p的平方根，那么y模p的平方根是±x；

2） 如果y沒有模p的平方根，那么-y有一個模 的平方根，并且-y模p的平方根是±x。

3 密碼算法設計

3.1 二次同余矩陣逐位加密的概率密碼的設計思想

BG密碼加解密速度比具有同等安全系數(shù)的公鑰密碼如RSA、橢圓曲線密碼等要快得多，但是其加密后的密文膨脹率較大，為1+k/l，其中k為模數(shù)n的位數(shù)，即密碼的安全系數(shù)，l為明文的長度。同時，為了使加密后的密文有更好的隨機性，以增加密文破解難度。鑒于此種情況，基于BG密碼的加密思想，在BG密碼的加密過程中，引入一個由隨機數(shù)源起的二次同余數(shù)序列組成的矩陣，并把這個矩陣表示成二進制形式后，通過特定算法，用這個矩陣中的某些位上的元素值來對明文進行異或運算，達到加密的目的。這樣就進一步地加強了加密后密文的隨機性，還提高了破解密碼的復雜性，使密碼安全性增加，又不影響加密的效率和速度。

3.2 密碼具體算法

密碼的具體算法設計如下：

現(xiàn)假設實體A要將明文m加密后傳送給實體B。

（1）算法預處理過程

① 實體B構造兩個不同的大素數(shù)p和q，使得 ，并計算n=p·q，則n為Blum數(shù)。實體B通過PKI（公鑰基礎設施）公開n。

② 實體B將（p、q）作為自己的私鑰保密。

（2）加密算法

（實體A進行的操作）

① 先將明文M表示成二進制數(shù)并劃分成（m1，m2，…，mr）組，每一組mi的長度為t。

② 從PKI中找到實體B公開的公鑰n。并選擇隨機數(shù)s，使，并作如下計算：

（其中i=1，2，3，…，t）

③ 將x1，x2，…xt表示為二進制數(shù)，該二進制數(shù)的位數(shù)為w，并排成如下矩陣：

其中每一個元素，形成一個二進制數(shù)的矩陣，該矩陣有t行w列。

④ 對于每一組明文mi，表示成二進制后形如（bi1bi2…bit），對i=1，2，3，…r，分別計算：

其中j=1，2，3，…t（j表示明文二進制數(shù)的第幾位）

⑤ 將計算出來的ui，j組裝成密文，使分組密文

ci=ui1ui2…uit

i=1，2，3，…r （其中r為明文組數(shù)）

⑥ 再計算出。

⑦ 傳送密文C=（c1，c2，…cr，xt+1）給實體B。

（3）解密算法

（實體B進行的操作）

① 實體B接收到密文C后，由定理2.7，對i=1，2，3，…t分別作如下計算：

② 重復加密過程中的第③步驟，得到矩陣A。

③ 對于每一組密文 ，表示成二進制后形如（ci1，ci2，…cir ），對i=1，2，3，…r，分別計算：

其中j=1，2，3，…t（j表示明文二進制數(shù)的第幾位）

④ 將計算出來的bi，j組裝成明文，得到分組明文mi=（bi1bi2…bit），其中i=1，2，3，…r（r為明文組數(shù)）

⑤ 最后得出明文M=（m1，m2，…，mr），從而恢復出原信息。

4 密碼算法分析與評價

4.1 密碼算法的正確性分析

由于實體B擁有私鑰p和q，由此易得，而由定理2.7，可知對于n=p·q為Blum數(shù)，則對于每一個在模n下有四個平方根并且這四個平方根中僅有一個，其表達式為：，則可以唯一求得xi。因此，可據(jù)此依次求出xi，xi-1，……，x1，x0，故可從密文中的xi+1求得加密矩陣A。

另外，由上述計算得出的 ，可組成二進制矩陣 。對于加密和解密過程來說， 矩陣是完全相同的，同時在加密和解密過程中又采用相同的取法，得到的密鑰也是相同的，從而對明文進行異或加密，再用相同密鑰進行異或解密，可恢復出明文來。

4.2 密碼算法的安全性分析

本密碼算法是多項式安全的。因為對于給定兩個明文和，如果只知道它們是兩個隨機密文和 中之一的明文，則不可能在多項式時間內(nèi)來確定這兩個明文和密文的對應關系。

假設敵手截獲了密文和 ，想破譯出明文的部分或全部信息，則必須計算數(shù)模n的平方根，然而根據(jù)定理2.6。當n足夠大時，求模n的平方根，等價于求大數(shù)n分解為兩個不同的奇素數(shù)的難度，這在計算上是不可行的。也就是其密碼強度就是RSA的密碼強度，是多項式安全的。同時，由于經(jīng)過隨機數(shù)產(chǎn)生的矩陣的復雜轉(zhuǎn)換，密文的隨機性更好，即多次加密不相同的明文時，得到的密文跟明文的差異沒有固定地特征變化，因此本密碼強度不低于RSA的密碼強度。

4.3 密碼的加、解密效率分析

本密碼在加密時的時間開銷主要為平方求余計算，解密時是模的冪運算，其時間復雜度等同于BG密碼，而遠小于RSA等公鑰密碼系統(tǒng)的時間復雜度O（k3）。效率較高。endprint

4.4 密文膨脹率分析

密文膨脹率是指被加密后得到的密文與原來明文之間的比率。這里所設計的密碼，是將明文（m1，m2，…，mr）經(jīng)加密變換為c1，c2，…cr，xt+1，可見密文膨脹率為1+w/（t·r），w為xt+1的二進制位數(shù)，t為明文分組每組的二進制長度，r為明文分組的組數(shù)。當明文越長時，其密文膨脹率越接近于1。但一般而言，其膨脹率不高于BG密碼的密文膨脹率，略大于1。

4.5 密碼算法評價

（1）可防止選擇明文攻擊。本算法由于遵循了概率密碼思想，在加密過程中引入了隨機數(shù)，對于相同明文使用相同密鑰加密后得到的密文是不相同的。因此可以有效地防止選擇明文攻擊。

（2）有更好的隨機性，增大了破解的難度。同時因為采用了矩陣變換加密密鑰，使加密密鑰更具有很好的隨機性，信息隱蔽性更好，加大了解密的難度。對采用明文攻擊或密文攻擊等攻擊方法的難度比BG密碼更大。

（3）時間復雜度低于RSA，數(shù)據(jù)膨脹率接近于1，可用于加密長消息。但本密碼在加大解密難度的同時，并沒有增加其加、解密的時間復雜度，其時間復雜度仍等同于BG密碼，比RSA和橢圓曲線密碼等公鑰密碼的時間復雜度要低。正因為有這樣的優(yōu)點，所以，本密碼體系適合對長文檔的加密，并且文檔越長，密文的膨脹率越低，越接近于1，效率越高。

參考文獻

[1] S Goldwasser， S Micali.Probabilistic Encryption.Journal of Computer and System Sciences，1984，28（2）：207-229.

[2] Blum M， Goldwasser S.An efficient probabilistic public-key encryption scheme which hidesall partial information.Advances in Cryptology Procedings of CRYPTO，84 （LNCSI96），1985：289-299.

[3] Atul Kahate.Cryptography and Network Security.Tata McGraw-Hill.2002.

[4] 王小非，崔國華，李俊，湯學明.一個數(shù)據(jù)膨脹率為1的概率公鑰密碼系統(tǒng)[J].計算機科學，2007，34（1）：117～119.

[5] 陳振宇，王麗維.信息安全在公鑰密碼體制中的實現(xiàn)技術[J].現(xiàn)代計算機，2008.9： 60～61，69.

[6] J.Wade Trappe， Lawrence C.Washington.Introduction to Cryptography with Co-

ding Theory， Post&Telecom Press ，2004.6

[7] 王濱，張遠洋.一次性口令身份認證方案的研究[J].計算機工程，2006，32（14）：149-150.

[8] 李大興，張澤增.一種基于RSA的公開密鑰密碼體制及其安全性[J].計算機學報，1989.4：279～288.

[9] 洪帆，崔國華，付小青.信息安全概論[M].華中科技大學出版社，2005.9.

[10] Daemen，L.R.Knudsenand，VRjjmen.The Block CIPher Square Fast Sotfware Encry-

ption .Desringer Verlag haiaf Israel，Januay.1997：149～165.

[11] Neal Koblitz.Elliptic Curve Cryptosystems.Mathematics of Computation/American Mathematical Society， 2007， 48（177）：203～209.

[12] 賴溪松，韓亮，張真誠.計算機密碼學及其應用[M].北京：國防工業(yè)出版社，2001.

[13] William Stallings，白國強.網(wǎng)絡安全基礎應用與標準[M].北京：清華大學出版社，2007.1.

[14] 何敬民.概率加密方法的設計[J].計算機研究與發(fā)展，1989.9：61～65.

[15] 王尚平，王育民. Blum-Goldwasser概率公鑰密碼體制的一種改進方案[J].西安電子科技大學學報，2001，8（28）：24～27.

[16] Katz J， Yung M. Characterization of Security Notions for Probabilistic Private-Key Encryption[EB/OL].J.Cryptology，Springer-Verlag，2005，DOI：10·1007/s00145-005-0310-8.endprint