基于正規(guī)基表示的有限域GF(28)上橢圓曲線點(diǎn)陣群的加密算法

劉海峰，盧開毅，梁星亮

(1.陜西科技大學(xué)電氣與信息工程學(xué)院，陜西 西安，710021；2．陜西科技大學(xué)文理學(xué)院，陜西 西安,710021)

橢圓曲線密碼體制(elliptic curve cryptosystem，ECC)可以使用比RSA密碼體制短得多的密鑰得到相同的安全性，是一種安全性高、計(jì)算量小、所需帶寬要求低的非對(duì)稱加密算法，可以在很大程度上減少處理負(fù)荷，被廣泛用于硬件實(shí)現(xiàn)的加密系統(tǒng)中[1-3]。有限域GF(2m)上的基本運(yùn)算涉及到多項(xiàng)式的模乘運(yùn)算和求逆運(yùn)算[4]，因此有限域GF(2m)上橢圓曲線比有限域GF(P)上橢圓曲線具有更高的復(fù)雜性，從而也有其獨(dú)特的安全性優(yōu)勢(shì)，受到信息安全界的大量關(guān)注。

有限域GF(28)上橢圓曲線的點(diǎn)可以通過(guò)正規(guī)基的形式進(jìn)行表示，有利于算法的硬件實(shí)現(xiàn)，并且由于同一元素在不同正規(guī)基下的表示形式并不一定相同，使得攻擊者獲得有效信息的難度更大，為此本文運(yùn)用群論的概念構(gòu)造有限域GF(28)上的橢圓曲線點(diǎn)陣群，將其應(yīng)用于分組加密算法當(dāng)中，從而得到基于有限域GF(28)上正規(guī)基表示的橢圓曲線點(diǎn)列的分組密碼系統(tǒng)。

1 有限域GF(28)上橢圓曲線概述

1.1 有限域GF(28)上的基本運(yùn)算

GF(28)是一種特殊的有限域，其具有28個(gè)元素，每個(gè)元素都可以表示為8位二進(jìn)制數(shù)，并可以將每個(gè)元素惟一地映射為一個(gè)系數(shù)為0和1的8次以下的一元多項(xiàng)式，其有限域上的多項(xiàng)式加法和乘法等運(yùn)算具有封閉性，在密碼學(xué)、信息安全等領(lǐng)域都是很重要的數(shù)學(xué)工具。有限域GF(28)與GF(2)[x]/p(x)上的元素及元素間相應(yīng)的運(yùn)算具有一一對(duì)應(yīng)的性質(zhì)，其中GF(2)[x]是二元域GF(2)上的一元多項(xiàng)式的全體集合，p(x)是GF(2)上的一個(gè)8次不可約多項(xiàng)式，因此一般來(lái)說(shuō)，討論有限域GF(28)就等價(jià)于討論有限域GF(2)[x]/p(x)。

(2)a(x)-b(x)=a(x)+b(x)。

(4)a(x)-1:當(dāng)且僅當(dāng)a(x)*a(x)-1=1。

(5)a(x)/b(x)=a(x)*b(x)-1。

1.2 有限域GF(28)上橢圓曲線的定義[5]

對(duì)于有限域GF(28)上的橢圓曲線，使用變?cè)拖禂?shù)均在有限域GF(28)上取值的三次方程，并利用有限域GF(28)中的算術(shù)運(yùn)算規(guī)則進(jìn)行計(jì)算。有限域GF(28)上適合于橢圓曲線密碼應(yīng)用的三次方程為:

y2+xy=x3+ax2+b，

其中的變?cè)獂和y以及系數(shù)a和b都是有限域GF(28)中的元素，且所有的計(jì)算均在GF(28)中進(jìn)行。橢圓曲線上的所有整數(shù)對(duì)(x,y)和無(wú)窮遠(yuǎn)點(diǎn)O組成集合E28(a,b)，當(dāng)b≠0時(shí)則可基于集合E28(a,b)定義一個(gè)有限的阿貝爾群。

1.3 有限域GF(28)上橢圓曲線的運(yùn)算規(guī)則

有限域GF(28)上橢圓曲線上點(diǎn)的運(yùn)算規(guī)則如下。對(duì)所有的點(diǎn)P,Q∈E28(a,b)：

(1)P+O=P，其中O為無(wú)窮遠(yuǎn)點(diǎn)。

(2)若P=(xP,yP)，則有P+(xP,xP+yP)=O。因此-P=(xP,xP+yP)為P的負(fù)元。

(3)若P=(xP,yP)，Q=(xQ,yQ)，且有P≠Q(mào)，P≠-Q，則R=P+Q=(xR,yR)由以下規(guī)則確定：

xR=λ2+λ+xP+xQ+a，

yR=λ(xP+xR)+xR+yP，

其中

λ=(yQ+yP)(xQ+xP)-1。

(4)若P=(xP,yP)，則R=2P=(xR,yR)由以下規(guī)則確定：

xR=λ2+λ+a，

其中

1.4 橢圓曲線的離散對(duì)數(shù)難題

使用橢圓曲線作為公鑰密碼體制的基礎(chǔ)是定義在有限域GF(2m)上橢圓曲線的點(diǎn)集可以構(gòu)成阿貝爾群，由此可以定義其上的離散對(duì)數(shù)。橢圓曲線的離散對(duì)數(shù)難題，即在已知橢圓曲線上一點(diǎn)P和Q=kP時(shí)(其中P,Q∈E2m(a,b))，要計(jì)算k的值就只能找到指數(shù)級(jí)時(shí)間復(fù)雜度的算法，而無(wú)法用多項(xiàng)式時(shí)間復(fù)雜度的算法進(jìn)行求解[6]。

2 基于有限域GF(28)上點(diǎn)陣群的橢圓曲線加密算法設(shè)計(jì)

2.1 密碼學(xué)意義上點(diǎn)陣群的構(gòu)建

本文在楊軍[7]提出的橢圓曲線點(diǎn)陣群概念的基礎(chǔ)之上，構(gòu)建一種具有密碼學(xué)意義的有限域GF(28)的橢圓曲線點(diǎn)陣群[8]。令K=F28為有限域GF(28)。E/K為定義在K上的橢圓曲線，E(K)是橢圓曲線E/K上所有的點(diǎn)連同無(wú)窮遠(yuǎn)點(diǎn)O構(gòu)成的有限加群，考慮集合G={A|A∈Mr×s(E(K))}，其中Mr×s(E(K))表示元素是E(K)上點(diǎn)的r×s規(guī)模之矩陣的集合。

定義1(點(diǎn)陣相等) 設(shè)P,Q∈G，其中Pij是矩陣P第i行第j列的元素，Qij是矩陣Q的第i行第j列的元素，若有Pij=Qij(i=1,2,…,r;j=1,2,…,s)，則稱P和Q相等，記為P=Q。

定義2(點(diǎn)陣加法) 設(shè)P,Q∈G，其中Pij是矩陣P第i行第j列的元素，Qij是矩陣Q的第i行第j列的元素，若R=P+Q，則有Rij=Pij+Qij(i=1,2,…,r;j=1,2,…,s)。

定義3(點(diǎn)陣負(fù)元) 設(shè)P,Q∈G，其中Pij是矩陣P第i行第j列的元素，Qij是矩陣Q的第i行第j列的元素，若O=P+Q，其中O為元素全為無(wú)窮遠(yuǎn)點(diǎn)O的零陣，也即O=Pij+Qij(i=1,2,…,r;j=1,2,…,s)，則稱P為Q的負(fù)元(或Q為P的負(fù)元)，記為P=-Q(或Q=-P)。

下面證明有限域GF(28)上橢圓曲線上的點(diǎn)陣關(guān)于加法“+”構(gòu)成群〈G,+〉。

(1)封閉性：設(shè)P,Q∈G，則顯然P+Q=([Pij]+[Qij])∈G成立。

(2)結(jié)合律：設(shè)P,Q,R∈G，則顯然有(P+Q)+R=([Pij]+[Qij])+[Rij]=[Pij]+([Qij]+[Rij])=P+(Q+R)。

(3)存在單位元：設(shè)P∈G，則O+P=P+O。

(4)每個(gè)元都有逆元：設(shè)P∈G，則點(diǎn)陣P中的元素Pij都是橢圓曲線上的點(diǎn)，因此必然存在橢圓曲線上的點(diǎn)Qij使得有Pij+Qij=O，因此點(diǎn)陣Q=[Qij]∈G。

根據(jù)以上的證明，可得有限域GF(28)上橢圓曲線上的點(diǎn)構(gòu)成的集合滿足群的概念，可以構(gòu)造密碼學(xué)意義上的橢圓曲線點(diǎn)陣群。

2.2 橢圓曲線加密算法設(shè)計(jì)

假設(shè)A要給B發(fā)送消息，則雙方需要先確定好有限域GF(28)上的不可約多項(xiàng)式p(x)以及橢圓曲線的參數(shù)a和b，從而得到相應(yīng)橢圓曲線上點(diǎn)的集合E28(a,b)。然后選取基點(diǎn)G，并通過(guò)雙方的私鑰nA、nB分別產(chǎn)生A、B雙方的公鑰PA=nAG、PB=nBG。

(2)解密階段：加密階段A使用了B的公鑰PB，B要對(duì)密文進(jìn)行解密，則需要用密文點(diǎn)陣Cm的第二列減去第一列與B的私鑰nB的乘積，從而實(shí)現(xiàn)解密，也即有Pm+kPB-nB(kG)=Pm+k(nBG)-nB(kG)=Pm。

A通過(guò)將點(diǎn)陣kPB與點(diǎn)陣Pm相加來(lái)偽裝消息，因?yàn)橹挥蠥知道k，所以即使PB是公鑰，除了A之外任何人都不能去除偽裝kPB，鑒于橢圓曲線的離散對(duì)數(shù)難題，攻擊者要想從G和kG中求出k是很難的，并且在使用了基于點(diǎn)陣群的橢圓曲線之后，每次分組加密時(shí)的k是一個(gè)向量而不是一個(gè)單獨(dú)的數(shù)值，因此要同時(shí)破解k的t個(gè)分量難度更大，從而攻擊者想要恢復(fù)消息明文的難度也越大。

3 基于有限域GF(28)上點(diǎn)陣群的橢圓曲線加密算法實(shí)現(xiàn)

3.1 有限域GF(28)上元素的正規(guī)基表示

有限域GF(28)上元素的正規(guī)基表示[9]也即在8次不可約多項(xiàng)式p(x)確定之后，可以找到有限域上的一個(gè)生成元g，使得有p(g)=0，并且GF(2)[x]/p(x)-{0}的元素可以表示為{g0,g1,g2,…,g28-1}，其中生成元g∈GF(28)。通過(guò)正規(guī)基的表示，特別是當(dāng)正規(guī)基是最優(yōu)正規(guī)基[10]的時(shí)候，有限域GF(28)上的運(yùn)算可以得到很大程度的簡(jiǎn)化。

(1)平方運(yùn)算：平方運(yùn)算可以簡(jiǎn)化成循環(huán)移位運(yùn)算，從而有利于硬件實(shí)現(xiàn)。

(2)模逆運(yùn)算：通過(guò)分治法，求逆運(yùn)算可以轉(zhuǎn)化為乘法運(yùn)算和移位運(yùn)算的結(jié)合。

(3)模乘運(yùn)算：如果選擇的正規(guī)基是最優(yōu)正規(guī)基，則可以采用效率更高的方法實(shí)現(xiàn)模乘運(yùn)算。

由于有限域GF(28)上的模乘運(yùn)算和模逆運(yùn)算相對(duì)于有限域GF(p)上的運(yùn)算更為復(fù)雜，而將該域上的元素用正規(guī)基的形式表示有利于提高計(jì)算效率，因此目前基于有限域GF(2m)上的快速算法仍然是研究的熱點(diǎn)問(wèn)題。

3.2 橢圓曲線加密算法實(shí)現(xiàn)

本文選取8次不可約多項(xiàng)式p(x)=x8+x5+x3+x2+1，并選取有限域GF(2)[x]/p(x)上的一個(gè)生成元g=x，可以得到g在模不可約多項(xiàng)式p(x)下各次方冪的運(yùn)算結(jié)果，如表1所示。

由表1可知，正規(guī)基g=x在模p(x)下的1～255次方冪剛好可以生成GF(2)[x]/p(x)-{0}上的所有元素一次且僅一次(其中g(shù)0=g255)。這里選取橢圓曲線方程的參數(shù)為a=g8=x5+x3+x2+1，b=g0=1，通過(guò)計(jì)算，可以得到此參數(shù)條件下橢圓曲線E28(g8,1)上基于生成元g的方冪表示的總共287個(gè)點(diǎn)，如表2所示，其中(x,y)表示實(shí)際橢圓曲線上的點(diǎn)(gx,gy)，(′E0′, 0)表示實(shí)際橢圓曲線上的點(diǎn)(0,1)。其對(duì)應(yīng)的橢圓曲線E28(g8,1)上的點(diǎn)如圖1所示。

表1 模p(x)下生成元g的各次方冪

表2 橢圓曲E28(g8,1)上基于生成元g的方冪表示的287個(gè)點(diǎn)

圖1 橢圓曲線E28(g8,1)上的點(diǎn)

從圖1可以看出，同一列上只有兩個(gè)互為負(fù)元的點(diǎn)，即除了無(wú)窮遠(yuǎn)點(diǎn)O以外，其他的點(diǎn)都是成對(duì)出現(xiàn)的。本文選取287個(gè)互異的可見字符進(jìn)行字符編碼，如表3所示，使表3中的字符與表2中287個(gè)點(diǎn)建立一一對(duì)應(yīng)的雙射關(guān)系。

表3 字符編碼表

注：space表示空格符。

假設(shè)要加密的字符串為M=hello,It’snicetomeetyou。首先，通過(guò)字符與橢圓曲線上點(diǎn)的對(duì)應(yīng)關(guān)系，可以得到明文字符串的字符所對(duì)應(yīng)的點(diǎn)分別為(2,104)，(240,65)，(241,52)，(241,52)，(38,68)，(11,90)，(′E0′, 0)，(55,6)，(210,242)，(223,182)，(210,240)，(′E0′, 0)，(3,153)，(225,245)，(1,183)，(240,65)，(′E0′, 0)，(210,242)，(38,68)，(′E0′, 0)，(3,180)，(240,65)，(240,65)，(210,242)，(′E0′, 0)，(227,142)，(38,68)，(4,197)。然后，將明文消息M分成4組，每組7個(gè)字符，可以得到M=M1+M2+M3+M4，選擇基點(diǎn)G=(g1,g183)，得到G點(diǎn)的階order=48(即有(n·order)G=O，其中O為無(wú)窮遠(yuǎn)點(diǎn))，并隨機(jī)生成具有7個(gè)分量的整數(shù)向量k=30 7 128 201 13 97 58，設(shè)B的私鑰為nB=34，則加密方A通過(guò)B的公鑰PB=nBG=(28,172)對(duì)消息分組進(jìn)行加密Cm={kG,Pm+kPB}，最后可得加密后密文消息為C=C1+C2+C3+C4，其中：C1=ΦУΩΨⅰⅶⅳ┤Яс∧yi;C2=9У∪Ψ0ⅶA┤AcШуΨ;C3=┤УΩΨ?ⅶШ┤ЯсууⅨ;C4=vУΩΨnⅶ↓┤jc!Yσ。從加密結(jié)果來(lái)看，顯然，當(dāng)明文點(diǎn)所對(duì)應(yīng)的k值相同時(shí)，其加密之后的密文點(diǎn)對(duì)的第一個(gè)分量也相同，因此符合預(yù)期。加密后的密文點(diǎn)對(duì)所對(duì)應(yīng)的生成元g的方冪表示如表4所示，其中(x,y)表示實(shí)際橢圓曲線上的點(diǎn)(gx,gy)。

解密時(shí)B先將密文點(diǎn)對(duì)的兩個(gè)相鄰分量分別轉(zhuǎn)換成橢圓曲線E28(g8,1)上的點(diǎn)，然后用他的私鑰nB=34來(lái)計(jì)算Cm2-nBCm1=Pm+kPB-nB(kG)=Pm即可得到明文所對(duì)應(yīng)的橢圓曲線上的點(diǎn)，最后通過(guò)查表轉(zhuǎn)換，即可得到解密后的明文M=hello, It’s nice to meet you。

表4 橢圓曲線E28(g8,1)上基于生成元g的方冪表示的密文點(diǎn)對(duì)

4 安全性分析

4.1 有限域GF(28)的豐富性

橢圓曲線加密算法的安全性首先表現(xiàn)在它所確定的有限域的豐富性。在有限域GF(28)中，當(dāng)選取的8次不可約多項(xiàng)式p(x)不同時(shí)，得到的有限域也不相同，即一旦確定了有限群，可供選取的橢圓曲線是非常豐富的。通過(guò)計(jì)算可以得到多項(xiàng)式環(huán)GF(2)[x]上的8次不可約多項(xiàng)式共有30個(gè)，其降冪排列時(shí)對(duì)應(yīng)的系數(shù)向量如表5所示，因此一共可以構(gòu)成30個(gè)不同的有限域GF(2)[x]/p(x)。

表5 多項(xiàng)式環(huán)GF(2)[x]上所有8次不可約多項(xiàng)式的系數(shù)向量

4.2 隨機(jī)點(diǎn)列的破解難度

4.3 正規(guī)基的非確定性

同一個(gè)有限域GF(2m)上可能會(huì)有多個(gè)不同的生成元，例如在有限域GF(24)上，選取多項(xiàng)式環(huán)GF(2)[x]上的4次不可約多項(xiàng)式為p(x)=x4+x+1時(shí)，可選擇的生成元包括g1=x，g2=x+1，g3=x2，g4=x2+1，g5=x3+1，g6=x3+x+1，g7=x3+x2+1，g8=x3+x2+x，其在模p(x)下的1～15次方冪的系數(shù)向量如表6所示。

從表6中可以看出，不同生成元gi的1～15次方都可以生成GF(24)-{0}中的所有元素一次且僅一次，因此可知有限域GF(24)上的同一個(gè)元素在不同正規(guī)基下會(huì)有不同的表現(xiàn)形式，對(duì)于有限域GF(2m)來(lái)說(shuō)，情況也類似，因此，只有在知道所選擇的正規(guī)基g之后，才能將正規(guī)基形式表示的點(diǎn)(x,y)還原到真正的橢圓曲線上的點(diǎn)(gx,gy)，由于正規(guī)基選擇的非確定性，從而使得基于正規(guī)基表示的橢圓曲線點(diǎn)陣群的加密算法有更高的安全性。

表6 模p(x)下的不同生成元各次方冪的系數(shù)向量

5 結(jié)語(yǔ)

橢圓曲線密碼體制是現(xiàn)有公鑰密碼體制中單位比特加密強(qiáng)度最高的算法。有限域GF(28)上橢圓曲線的點(diǎn)可以通過(guò)正規(guī)基的形式來(lái)表示，本文在選定多項(xiàng)式環(huán)GF(2)[x]上的8次不可約多項(xiàng)式p(x)之后，將有限域GF(28)上的元素用所選擇生成元g的正規(guī)基表示，使模逆運(yùn)算和模乘運(yùn)算等得以簡(jiǎn)化，提高了加密算法效率。運(yùn)用群論的概念建立有限域GF(28)上的橢圓曲線點(diǎn)陣群，將其應(yīng)用于分組加密算法中，從而構(gòu)建了基于有限域GF(28)上正規(guī)基表示的橢圓曲線點(diǎn)列的分組密碼系統(tǒng)，分析表明其具有較高的安全性。