基于模糊冪半群的概率加密方法設(shè)計*

晁海洲，倪翔飛

（1.上海財經(jīng)大學(xué)浙江學(xué)院，浙江 金華 321013；2.浙江師范大學(xué)數(shù)計學(xué)院，浙江 金華 321001）

0 引言

隨著日常生活數(shù)字化的日益加深，信息加密技術(shù)的重要性也越來越凸顯。

按照加密過程是否可逆，一般可將加密方法分為對稱加密和非對稱加密技術(shù)。對稱加密技術(shù)的加密過程可以看做由明文空間到密文空間的一個可逆變換，諸如古典密碼、分組密碼等[1]。他們的加密和解密密鑰是相同的，密鑰作為私有信息被通信雙方密密保存，并不對外公開。對密密通信的竊聽或者破壞者主要通過密文和明文關(guān)系，推斷出私有密鑰而破解整個密碼系統(tǒng)。對稱加密系統(tǒng)很難抵抗暴力破解攻擊，因此假定計算機(jī)能力足夠優(yōu)良，則傳統(tǒng)的對稱加密系統(tǒng)不存在理論上的絕對安全性。非對稱加密技術(shù)主要是以公鑰密碼為代表，諸如依賴計算不可解問題的RSA 和橢圓曲線加密方法[2]等。除此以外通過考慮一密對多明產(chǎn)生了Rabin密碼[1]，反向的考慮一明對多密產(chǎn)生了概率加密方法[3]。非對稱加密技術(shù)核心思想是將對稱的可逆加密變換轉(zhuǎn)化為一個非對稱的不可逆變換，從而使得密碼系統(tǒng)對密鑰私有的依賴性大大降低。但大部分非對稱加密技術(shù)依然基于數(shù)論中計算不可解問題，同樣的隨著計算機(jī)性能的提升，特別是量子計算機(jī)從理論走向?qū)嵱?，傳統(tǒng)非對稱密碼系統(tǒng)也會受到較大的沖擊。

由于每次加密密鑰均不相同，一次一密加密技術(shù)理論上具有不可破譯的良好性能。但在計算機(jī)上很難實現(xiàn)真隨機(jī)選擇，并且一次一密加密系統(tǒng)需要較大的密鑰存儲空間，所以其實現(xiàn)較為困難。比較好的近似一次一密加密技術(shù)是通過移位寄存器實現(xiàn)加密密鑰的變換的序列密碼[4]，但因為移位寄存器具有規(guī)律性，所以可以通過對移位寄存器的工作原理分析而破譯序列密碼。

半群結(jié)構(gòu)在密碼系統(tǒng)設(shè)計中有著廣泛的應(yīng)用[5-7]。本文將在模糊集理論[8]基礎(chǔ)上，利用素數(shù)階群上的模糊冪半群的結(jié)構(gòu)給出一種非對稱加密方法。基于這種方法可以實現(xiàn)密鑰存儲空間較小的一次一密加密。

1 約簡模糊冪半群的結(jié)構(gòu)

作為基礎(chǔ)，本節(jié)首先給出一些模糊集理論的有關(guān)知識和結(jié)論。以下如非特殊聲明，G均為素數(shù)階群，即就是說G是有限循環(huán)可交換的，且每個非單位元均為G的素元。·為G中的二元運算，方便起見稱為G中的乘法。G的一個模糊子集A等價于一個由G到區(qū)間[0,1]的映射，也稱為A的隸屬函數(shù)，一般不加區(qū)別地統(tǒng)一用A表示。函數(shù)值A(chǔ)(x)表示元素x隸屬于G的程度，稱為x在A中的隸屬度?！た砂慈缦路绞綌U(kuò)展為G的兩個模糊子集A,B上的二元運算○，A○B(yǎng)=C，其中C也是G的一個模糊子集，且C(x)=∨{A(y)∧B(z)|yz=x;y,z∈G}。稱○為G的模糊子集間的乘法運算。G的所有模糊子集構(gòu)成的集合在○下滿足結(jié)合律且是封閉的，因此構(gòu)成一個半群，稱為G的模糊冪半群，記為 F(G)。

記 F*(G)是 F(G)中的由所有單位元在A中隸屬度最大的模糊子集構(gòu)成的子集合，即F*(G)={A∈F(G)|A(e)=max{A(x)|x∈G}}。

F*(G)在乘法運算○下是封閉的，因此它是F(G)的一個子半群，我們稱之為G的約簡模糊冪半群。

定義1.1 F*(G)稱為G的約簡模糊冪半群。

設(shè)A∈F(G)，若函數(shù)序列A,A2,A3,…,An,…的極限存在，則稱該極限為模糊集合A的OP-極限。顯然該極限也是G的一個模糊子集，且。利用OP-極限我們得到了約簡模糊冪半的結(jié)構(gòu)。下面不加證明的列出有關(guān)結(jié)論。

定義1.2 稱A和B是同層的，若對于，記 為A～B。

顯然同層關(guān)系是一個等價關(guān)系，且兩個同層的模糊子集具有相同的OP-極限。事實上同層關(guān)系等價類構(gòu)成了 F*(G)的一個子半群。若A∈F*(G)，且有0 ≤t≤h=A(e)，使得。

則 F*(G)中任何模糊子集的OP-極限均具有如上形態(tài)，也就是說 F*(G)中所有模糊子集的OP-極限均可以由參數(shù)h和t完全決定，因此我們將單位元隸屬度為h，其余元素隸屬度為t的OP-極限記為(h,t)lim。(h,t)lim自乘不變，因此(h,t)lim為 F*(G)中的冪等元。當(dāng)A～B時，。

此時有結(jié)論：

定理1.1A～B的充分必要條件為：A(e)=B(e)=h且max{A(x)|x∈G{e}}=max{B{x}|x∈G{e}}=t成立。

由上面定理可知，同層等價類構(gòu)成的子半群中所有元素具有共同的特征參數(shù)h和t，即就是說該子半群完全由h和t所決定。而任一(h,t)lim屬于且只能屬于一個等價類。為方便討論有如下定義：

定義1.3 在 F*(G)中把同層關(guān)系下的等價類子半群稱為 F*(G)的一個平層。若(h,t)lim屬于該平層，則將h稱為該平層的軸高；將t稱為該平層的厚度。軸高為h，厚度為t的平層記為L(h,t)，其中0 ≤h≤1,0 ≤t≤h。

每個平層包含且僅包含一個 F*(G)中的冪等元(h,t)lim，而下面結(jié)論說明 F*(G)中所有的冪等元就是所有的(h,t)lim。

定理1.2 F*(G)中所有冪等元構(gòu)成集合Λ={(h,t)lim|0 ≤h≤1,0 ≤t≤h}。

在OP-極限下約簡模糊冪半群的結(jié)構(gòu)可以完全由它的平層形態(tài)確定下來。約簡模糊冪半群的每一個平層都是以單位元“高度”為軸高，以次大元“高度”為厚度，圍繞唯一的冪等元形成的“盤狀”平層。所有約簡模糊冪半群中的冪等元“個數(shù)”決定了所有的平層“個數(shù)”。將所有平層依次“堆疊”起來就得到了約簡模糊冪半群。即如下面定理所述，F(xiàn)*(G)可以表示成為一族含唯一冪等元的子半群的不交并。

(h,t)lim不僅是 F*(G)中的冪等元，而且是L(h,t)中的零元。即對任意L(h,t)中的模糊集合A，A與(h,t)lim的乘積都等于(h,t)lim本身。

定理1.4 若A∈L(h,t)，則一定有A○(h,t)lim=(h,t)lim。

立即有如下推論。

定理1.5 對任意C∈F(G)和A∈L(h,t)，有C○A○(h,t)lim=C○(h,t)lim。

證明：由于 F*(G)是半群，故C○A○(h,t)lim=C○(A○(h,t)lim)，由定理1.4，立即可得C○A○(h,t)lim=C○(h,t)lim成立。

注意這一結(jié)論在隨后加密方案中扮演著重要的角色。

2 加密方法的實現(xiàn)

由定理1.5 容易發(fā)現(xiàn)，對于確定的A∈F(G)和L(h,t)，任 取B∈L(h,t){(h,t)lim}，則立即有A○B(yǎng)○(h,t)lim恒等于A○(h,t)lim。即就是說在不知道B的情況下，想從A○B(yǎng)中知道A是困難的；但容易從A○(h,t)lim中恢復(fù)出A。由此我們可以得到下面的概率加密方案。

準(zhǔn)備工作。首先選擇合適的素數(shù)p，構(gòu)造p階有限循環(huán)群Gp。記其模糊冪半群為 F(Gp)，約簡模糊冪半群為 F*(Gp)。為便于計算機(jī)算法實現(xiàn)，對F(Gp)和 F*(Gp)進(jìn)行離散化處理，取可能隸屬度為2s個離散值。方便討論起見，隨后仍舊使用F(Gp)和 F*(Gp)表示Gp經(jīng)離散化后的模糊冪半群和約簡模糊冪半群。

密鑰空間的選擇。利用B對明文A加密需要先選擇 F*(Gp)的一個平層L(h,t)。取0 ≤t≤h≤1，得到L(h,t)。事實上我們不需要保存整個子半群L(h,t)，只需要保存L(h,t)的生成集即可。任一加密密鑰B均可由生成集生成。記L(h,t)的生成集為Λ，記L(h,t)=＜Λ＞。則加密密鑰空間即為＜Λ＞{(h,t)lim}。確定了加密密鑰空間，則解密密鑰即為唯一的(h,t)lim。

明文集合的確定。一般加密方案中均假定明文空間沒有限制，僅僅考慮加密、解密密鑰及加密、解密方法，也就是說在這個加密映射中對定義域和值域無太多限制，僅僅針對對應(yīng)規(guī)則進(jìn)行討論。事實上，實際傳輸中的信息往往是存在于有限多狀態(tài)或者可以由有限狀態(tài)表示出來。因此經(jīng)過適當(dāng)選擇可用明文的表示，在一定程度上也可以起到對信息的保護(hù)。假設(shè)實際傳輸中有意義的基本明文字段有m個，其余明文信息均可由該m個基本明文字段構(gòu)造，則我們只需要考慮如何加密傳輸這有限m個明文即可。通過映射 M 將m個明文字段對應(yīng)到F(Gp)L(h,t)中的m個模糊子集上，從而得到相應(yīng)的明文集合。明文在 F(Gp)中的分布應(yīng)能使得通過B加密后的更好的隱藏明文信息，監(jiān)聽者從密文A○B(yǎng)中很難猜測出相應(yīng)的明文A；同時接受者要能容易從密文A○B(yǎng)中恢復(fù)出明文A。

顯然A不能落在L(h,t) 中，因為此時必有A(e)=h和max{A(x)|X≠e}=t，從而立即A○B(yǎng)∈L(h,t)，即A○(h,t)lim=(h,t)lim，此時接受者也無法利用A○(h,t)lim從密文A○B(yǎng)中恢復(fù)出明文A。

若對兩明文A1,A2∈F(G)有對同一平層L(h,t)，A1○(h,t)lim=A2○(h,t)lim，則利用同一密鑰B∈L(h,t)，兩個明文會產(chǎn)生同樣密文。此時接收者是無法區(qū)分明文A1和A2的。因此明文選擇必須避免這樣的情況發(fā)生。若A和B與(h,t)lim乘積相同，則稱為同義的。同義構(gòu)成等價類。明文選擇在每個同義等價類中只能選擇一個。

若有A1,A2∈F(G)和B1∈L(h1,t1)，B2∈L(h2,t2)，使得A1○B(yǎng)1=A2○B(yǎng)2，稱之為對不同密鑰空間產(chǎn)生了碰撞。則此時在不知道密鑰是B1還是B2時，很難通過密文破解密碼系統(tǒng)。因此明文集合選擇應(yīng)以對不同密鑰空間產(chǎn)生盡可能多的碰撞為宜。

解密表。發(fā)送密文A○B(yǎng)被接收者接收后，解密過程中接受者只需要進(jìn)行運算A○B(yǎng)○(h,t)lim即可。在這個過程中由于零元性質(zhì)實際上已經(jīng)破壞了原來明文信息內(nèi)容，因此乘積結(jié)果并不直接等于明文本身。因此實際上解密過程需要先算出所有明文與(h,t)lim乘積的結(jié)果，再和密文與(h,t)lim乘積結(jié)果比較，從而完成解密。為此可以先預(yù)算出所有明文與(h,t)lim乘積的結(jié)果并保存、生成解密表。記明文為Aλ時對應(yīng)的解密表內(nèi)容為Dλ，則整個解密表為集合Λ={Dλ}。

雙方確定素數(shù)P和數(shù)2s，構(gòu)造 F(Gp)和F*(Gp)，并在 F(Gp) F*(Gp)中確定并保存有限明文集合。

加密過程。消息接受者在 F*(Gp)中選擇平層L(h,t)，保存(h,t)lim作為解密密鑰，計算所有明文與(h,t)lim乘積，保存為解密表，并經(jīng)安全信道發(fā)送參數(shù)h,t。消息發(fā)送方恢復(fù)平層L(h,t)的生成集合并保存。消息發(fā)送方通過平層L(h,t)的生成集合產(chǎn)生加密密鑰B，加密所需要傳輸?shù)拿魑牡玫紸○B(yǎng)=C。經(jīng)公開信道傳送密文C。

解密過程。收到C后，消息接收方計算C○(h,t)lim，比較解密表，得到明文A。

3 性能分析

本文提出的加密方案是一種一次一密的非對稱私鑰概率加密方案。下面將本方案與對稱私鑰加密方案、序列密碼、公鑰加密方案等進(jìn)行比較。

對稱私鑰加密方案可以看做由私密鑰產(chǎn)生對應(yīng)關(guān)系得到的明文空間到密文空間的可逆映射。其特點是算法復(fù)雜度低、易于實現(xiàn)。但對稱私鑰加密方案對密鑰保密性要求很高，當(dāng)私密鑰被竊取則加密系統(tǒng)將失去安全性；同時對稱私鑰加密對應(yīng)一個可逆映射，這就意味著當(dāng)已知足夠的明文-密文對，即可通過統(tǒng)計分析破解加密系統(tǒng)。本文提出的方案密鑰是非對稱的，攻擊者很難通過對明文-密文對的統(tǒng)計分析破解系統(tǒng)；但由于約簡模糊冪半群的特征，若密鑰B被竊密者截獲則容易利用約簡模糊冪半群的結(jié)構(gòu)特點分析得到解密密鑰從而破解系統(tǒng)。因此本方案對密鑰保密性要求較高，是一種私鑰加密體系。

序列密碼一般是由移位寄存器生成密鑰序列對明文加密、解密的。其特點是易于實現(xiàn)，計算復(fù)雜度較低，且由于每次生成的加密密鑰不同使得加密方案安全性較好，能抵抗明文-密文對攻擊。但序列密碼作為對稱私鑰密碼，解密密鑰需要和加密密鑰一致，這就導(dǎo)致序列密碼一般要求高度的時鐘同步，這在很多環(huán)境中難于實現(xiàn)；另外由于移位寄存器的結(jié)構(gòu)相對固定，因此通過對其結(jié)構(gòu)的分析就能夠攻破序列密碼體系。本文提供的方案與序列密碼類似的地方在于可以實現(xiàn)一次一密加密過程，因此類似于序列密碼，想要通過密文和明文-密文對破解密碼體系一般來說是困難的。同時由于其非對稱性，加密密鑰和解密密鑰不相同，因此時鐘同步性上要求不高，適應(yīng)環(huán)境更廣泛。同時由于對不同密鑰空間碰撞的存在，使得想通過統(tǒng)計分析或者針對使用的模糊冪半群結(jié)構(gòu)分析破解密碼系統(tǒng)是困難的。但相對于移位寄存器，計算半群乘法運算復(fù)雜度較高。

公鑰密碼方案是通過單向陷門函數(shù)產(chǎn)生非對稱的加密、解密密鑰進(jìn)行保密通信的。由于從加密密鑰很難破解出解密密鑰，因此加密密鑰是可以公開的。不需要通過安全的私有傳輸信道傳送加密密鑰。共要密碼方案最大的優(yōu)點就是保密通信對信道的密鑰傳輸信道的安全性要求很低。但大部分共要密碼方案所產(chǎn)生的的密鑰對是相對固定的，對不同明文消息的加密、解密采用相同的密鑰。這使得保密系統(tǒng)在采用統(tǒng)計分析方法進(jìn)行的攻擊下容易被攻破。本文方案具有類似于非對稱密鑰的特征，但由于代數(shù)結(jié)構(gòu)的存在，加密密鑰須通過安全私有信道發(fā)送，故相比較公鑰密碼方案對密鑰傳送信道要求較高。但其可實現(xiàn)一次一密的特性能較好地抵抗統(tǒng)計分析攻擊。

4 結(jié)語

本文給出了一種利用素數(shù)階有限循環(huán)群上的約簡模糊冪半群構(gòu)造的加密方案。該方案屬于私鑰密碼方案，但同時兼具一次一密和概率加密的特性。相較于一般序列密碼，該密碼方案對時鐘同步?jīng)]有要求；相較于一般私鑰密碼和一般公鑰密碼，該密碼對統(tǒng)計分析破解方法具有較好抵抗能力。