江寶安
(1.重慶移通學(xué)院,重慶 401520;2.重慶郵電大學(xué),重慶 400065)
1976 年,Diffie 和Hellman提出了密碼交換概念,為公鑰密碼學(xué)提供了理論基礎(chǔ)。1985 年,Elgamal[1,2]提出了一種公鑰密碼體制,其安全性基于求離散對數(shù)的困難問題上,是一種國際公認(rèn)的較理想的公鑰密碼體制,是目前應(yīng)用在保密通信和數(shù)字簽名領(lǐng)域的有效的安全算法。ElGamal 公鑰方案的提出是密碼學(xué)的一個巨大的突破,是繼安全性基于大整數(shù)分解的困難問題的RSA[3,4]算法提出后,又一個里程碑事件。
ElGamal 公鑰密碼體制是建立在有限域Zp上的,系統(tǒng)參數(shù)的選擇受到一定的限制。本文提出一種建立在有限域乘法群上的公鑰密碼算法。p為素數(shù),該乘法群的階為2p-1,且為梅森素數(shù),則該乘法群為有限單群。在此基礎(chǔ)上的DH 公鑰密碼體制,其安全性也是基于求離散對數(shù)的困難的問題上,但是此離散對數(shù)是基于有限擴(kuò)域上的,區(qū)別于ElGamal的有限域Zp。
本文算法繼承ElGamal 公鑰密碼體制的優(yōu)點(diǎn),又有算法簡單、參數(shù)選擇靈活、計算速度快、執(zhí)行效率高等優(yōu)點(diǎn),具有極大的理論和實(shí)際應(yīng)用價值。
取大素數(shù)p,取p-1 階生成元a∈,取隨機(jī)數(shù)k1,0 (1)發(fā)送方A 隨機(jī)選擇數(shù)k1,0 本文提出了一種新的基于有限域乘法單群的公鑰密碼[5,6]。有限域的乘法群的階為n=||=2p-1,p為素數(shù)且使得n=2p-1為梅森素數(shù),具體取值如圖1所示。則乘法群為有限單群,任何一個元素a∈的階為n,即anmodq=1(q為p次不可約本原多項式),a+a=0。 圖1 梅森素數(shù)及部分模2 本原不可約多項式 新算法的具體流程如下文所述。 p為素數(shù)且使得n=2p-1 為梅森素數(shù),推薦p取521,1 279 或2 281,相應(yīng)的p次不可約本原多項式為q=x521+x32+1,x1279+x216+1 或x2281+x715+1(x為多項式不定元)。隨機(jī)取元素a∈(a≠1),則anmodq=1,(p,n,q,a)為公開的系統(tǒng)參數(shù)(若a不公開,破譯難度更高)。發(fā)送方A 隨機(jī)取私鑰1 如圖2 所示,發(fā)送方A 生成密文c=m·modq,接收方B 使用私鑰k2解密: 圖2 乘法公鑰密碼 筆者已經(jīng)對該算法完成軟硬件仿真驗證,軟件采用MATLAB 仿真,最高已驗證p=9 689的加解密,可以轉(zhuǎn)化成C 語言或者匯編語言等,并且可應(yīng)用于不同的平臺。硬件采用線性反饋移位寄存器實(shí)現(xiàn),需要p個寄存器,所需時間為p個時鐘周期,計算速度快。 取p=5,本原多項式q(x)=x5+x2+1,數(shù)組形式q(x)=[100101],隨機(jī)選擇a=x4+x2+1=[10101],=a 算法復(fù)雜度分析:模平方運(yùn)算a2modq有快速算法,需要O(p)次比特運(yùn)算,模乘a·bmodq運(yùn)算需要O(p2)次比特運(yùn)算,模冪ak·modq運(yùn)算需要O(p3)次比特運(yùn)算,整個加密解密最耗時的主要是模冪運(yùn)算。當(dāng)加密解密多項式已預(yù)先算出時,采用帶反饋的移位寄存器可同時實(shí)現(xiàn)乘除運(yùn)算即模乘運(yùn)算,加密解密時間均為p個時鐘周期。 3.2.1 硬件實(shí)現(xiàn)關(guān)鍵技術(shù) 加密硬件實(shí)現(xiàn)如圖3 所示,當(dāng)p個比特明文m串行輸入結(jié)束后,p個寄存器的值即為密文;解密硬件實(shí)現(xiàn)如圖4 所示,當(dāng)p個比特密文c串行輸入結(jié)束后,p個寄存器的值即為解密明文。加解密所需時間均為p個時鐘周期。 圖3 加密硬件實(shí)現(xiàn)(用移位寄存器和異或門) 圖4 解密硬件實(shí)現(xiàn)(用移位寄存器和異或門) 3.2.2 實(shí)例 取p=7,本原多項式為q(x)=1+x+x7=[11000001],明文為m(x)=1+x+x4=[1100100],加密多項式為g(x)=x2+x3=[0011000],解密多項式為h(x)=x+x2+x3+x4+x6=[0111101],加密密文為c(x)=m(x)·g(x)modq=1+x+x2+x4+x6=[1110101],加密硬件實(shí)現(xiàn)如圖5所示。 圖5 實(shí)例2 中 p=7 加密硬件實(shí)現(xiàn)(用移位寄存器和異或門) 解密明文為d(x)=c(x)·h(x)modq=1+x+x4=[1100100]=m(x),解密硬件實(shí)現(xiàn)如圖6 所示。 圖6 實(shí)例2 中 p=7 解密硬件實(shí)現(xiàn)(用移位寄存器和異或門) 實(shí)例2 用移位寄存器和異或門的硬件實(shí)現(xiàn)的電路如圖7 所示,仿真結(jié)果如圖8 所示。 圖7 實(shí)例2 具體加密硬件實(shí)現(xiàn)電路(用移位寄存器和異或門) 圖8 實(shí)例3 具體加密硬件實(shí)現(xiàn)電路仿真波形 主程序以p=31 乘法加密解密為例,以下是MATLAB 源程序: 現(xiàn)有的典型的公鑰密碼算法如RSA、ElGamal和橢圓密碼ECC 都有各自的優(yōu)缺點(diǎn),適應(yīng)不同的應(yīng)用場合,在多種文獻(xiàn)中有詳細(xì)的介紹和說明[7-14]。本文在有限域乘法單群的基礎(chǔ)上,提出了新的公鑰密碼算法。該算法本身基于模2 運(yùn)算,只需要用移位寄存器和異或門就可實(shí)現(xiàn),不需要構(gòu)建長整數(shù)運(yùn)算,也不需要計算有限域原根[15],相較傳統(tǒng)的ElGamal 和RSA 公鑰算法具有系統(tǒng)參數(shù)選擇靈活、計算速度快、安全性高等優(yōu)點(diǎn),具有廣泛的理論和實(shí)際應(yīng)用價值。1.2 加密過程
1.3 解密過程
2 一種新的基于有限域乘法單群的公鑰密碼
2.1 乘法型加解密
2.2 加法型加解密
3 算法實(shí)例
3.1 實(shí)例1
3.2 實(shí)例2
4 算法軟件實(shí)現(xiàn)程序(MATLAB 仿真)
5 結(jié)語