一種基于有限域乘法單群的公鑰密碼算法及實(shí)現(xiàn)*

江寶安

（1.重慶移通學(xué)院，重慶 401520；2.重慶郵電大學(xué)，重慶 400065）

0 引言

1976 年，Diffie 和Hellman提出了密碼交換概念，為公鑰密碼學(xué)提供了理論基礎(chǔ)。1985 年，Elgamal[1,2]提出了一種公鑰密碼體制，其安全性基于求離散對(duì)數(shù)的困難問(wèn)題上，是一種國(guó)際公認(rèn)的較理想的公鑰密碼體制，是目前應(yīng)用在保密通信和數(shù)字簽名領(lǐng)域的有效的安全算法。ElGamal 公鑰方案的提出是密碼學(xué)的一個(gè)巨大的突破，是繼安全性基于大整數(shù)分解的困難問(wèn)題的RSA[3,4]算法提出后，又一個(gè)里程碑事件。

ElGamal 公鑰密碼體制是建立在有限域Zp上的，系統(tǒng)參數(shù)的選擇受到一定的限制。本文提出一種建立在有限域乘法群上的公鑰密碼算法。p為素?cái)?shù)，該乘法群的階為2p-1，且為梅森素?cái)?shù)，則該乘法群為有限單群。在此基礎(chǔ)上的DH 公鑰密碼體制，其安全性也是基于求離散對(duì)數(shù)的困難的問(wèn)題上，但是此離散對(duì)數(shù)是基于有限擴(kuò)域上的，區(qū)別于ElGamal的有限域Zp。

本文算法繼承ElGamal 公鑰密碼體制的優(yōu)點(diǎn)，又有算法簡(jiǎn)單、參數(shù)選擇靈活、計(jì)算速度快、執(zhí)行效率高等優(yōu)點(diǎn)，具有極大的理論和實(shí)際應(yīng)用價(jià)值。

1 ElGamal 公鑰密碼方案

1.1 參數(shù)初始化

取大素?cái)?shù)p，取p-1 階生成元a∈，取隨機(jī)數(shù)k1，0

1.2 加密過(guò)程

（1）發(fā)送方A 隨機(jī)選擇數(shù)k1，0

1.3 解密過(guò)程

2 一種新的基于有限域乘法單群的公鑰密碼

本文提出了一種新的基于有限域乘法單群的公鑰密碼[5,6]。有限域的乘法群的階為n=||=2p-1，p為素?cái)?shù)且使得n=2p-1為梅森素?cái)?shù)，具體取值如圖1所示。則乘法群為有限單群，任何一個(gè)元素a∈的階為n，即anmodq=1（q為p次不可約本原多項(xiàng)式），a+a=0。

圖1 梅森素?cái)?shù)及部分模2 本原不可約多項(xiàng)式

新算法的具體流程如下文所述。

p為素?cái)?shù)且使得n=2p-1 為梅森素?cái)?shù)，推薦p取521，1 279 或2 281，相應(yīng)的p次不可約本原多項(xiàng)式為q=x521+x32+1，x1279+x216+1 或x2281+x715+1（x為多項(xiàng)式不定元）。隨機(jī)取元素a∈(a≠1)，則anmodq=1，(p,n,q,a)為公開(kāi)的系統(tǒng)參數(shù)（若a不公開(kāi)，破譯難度更高）。發(fā)送方A 隨機(jī)取私鑰1

2.1 乘法型加解密

如圖2 所示，發(fā)送方A 生成密文c=m·modq，接收方B 使用私鑰k2解密：

圖2 乘法公鑰密碼

2.2 加法型加解密

筆者已經(jīng)對(duì)該算法完成軟硬件仿真驗(yàn)證，軟件采用MATLAB 仿真，最高已驗(yàn)證p=9 689的加解密，可以轉(zhuǎn)化成C 語(yǔ)言或者匯編語(yǔ)言等，并且可應(yīng)用于不同的平臺(tái)。硬件采用線(xiàn)性反饋移位寄存器實(shí)現(xiàn)，需要p個(gè)寄存器，所需時(shí)間為p個(gè)時(shí)鐘周期，計(jì)算速度快。

3 算法實(shí)例

3.1 實(shí)例1

取p=5，本原多項(xiàng)式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)算，整個(gè)加密解密最耗時(shí)的主要是模冪運(yùn)算。當(dāng)加密解密多項(xiàng)式已預(yù)先算出時(shí)，采用帶反饋的移位寄存器可同時(shí)實(shí)現(xiàn)乘除運(yùn)算即模乘運(yùn)算，加密解密時(shí)間均為p個(gè)時(shí)鐘周期。

3.2 實(shí)例2

3.2.1 硬件實(shí)現(xiàn)關(guān)鍵技術(shù)

加密硬件實(shí)現(xiàn)如圖3 所示，當(dāng)p個(gè)比特明文m串行輸入結(jié)束后，p個(gè)寄存器的值即為密文；解密硬件實(shí)現(xiàn)如圖4 所示，當(dāng)p個(gè)比特密文c串行輸入結(jié)束后，p個(gè)寄存器的值即為解密明文。加解密所需時(shí)間均為p個(gè)時(shí)鐘周期。

圖3 加密硬件實(shí)現(xiàn)（用移位寄存器和異或門(mén)）

圖4 解密硬件實(shí)現(xiàn)（用移位寄存器和異或門(mén)）

3.2.2 實(shí)例

取p=7，本原多項(xiàng)式為q(x)=1+x+x7=[11000001]，明文為m(x)=1+x+x4=[1100100]，加密多項(xiàng)式為g(x)=x2+x3=[0011000]，解密多項(xiàng)式為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)（用移位寄存器和異或門(mé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)（用移位寄存器和異或門(mén)）

實(shí)例2 用移位寄存器和異或門(mén)的硬件實(shí)現(xiàn)的電路如圖7 所示，仿真結(jié)果如圖8 所示。

圖7 實(shí)例2 具體加密硬件實(shí)現(xiàn)電路（用移位寄存器和異或門(mén)）

圖8 實(shí)例3 具體加密硬件實(shí)現(xiàn)電路仿真波形

4 算法軟件實(shí)現(xiàn)程序（MATLAB 仿真）

主程序以p=31 乘法加密解密為例，以下是MATLAB 源程序：

5 結(jié)語(yǔ)

現(xiàn)有的典型的公鑰密碼算法如RSA、ElGamal和橢圓密碼ECC 都有各自的優(yōu)缺點(diǎn)，適應(yīng)不同的應(yīng)用場(chǎng)合，在多種文獻(xiàn)中有詳細(xì)的介紹和說(shuō)明[7-14]。本文在有限域乘法單群的基礎(chǔ)上，提出了新的公鑰密碼算法。該算法本身基于模2 運(yùn)算，只需要用移位寄存器和異或門(mén)就可實(shí)現(xiàn)，不需要構(gòu)建長(zhǎng)整數(shù)運(yùn)算，也不需要計(jì)算有限域原根[15]，相較傳統(tǒng)的ElGamal 和RSA 公鑰算法具有系統(tǒng)參數(shù)選擇靈活、計(jì)算速度快、安全性高等優(yōu)點(diǎn)，具有廣泛的理論和實(shí)際應(yīng)用價(jià)值。