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

劉海峰，盧開毅，梁星亮

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

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

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

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

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

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

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

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

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

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

對于有限域GF(28)上的橢圓曲線，使用變元和系數(shù)均在有限域GF(28)上取值的三次方程，并利用有限域GF(28)中的算術(shù)運算規(guī)則進行計算。有限域GF(28)上適合于橢圓曲線密碼應用的三次方程為:

y2+xy=x3+ax2+b，

其中的變元x和y以及系數(shù)a和b都是有限域GF(28)中的元素，且所有的計算均在GF(28)中進行。橢圓曲線上的所有整數(shù)對(x,y)和無窮遠點O組成集合E28(a,b)，當b≠0時則可基于集合E28(a,b)定義一個有限的阿貝爾群。

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

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

(1)P+O=P，其中O為無窮遠點。

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

(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 橢圓曲線的離散對數(shù)難題

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

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

2.1 密碼學意義上點陣群的構(gòu)建

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

定義1(點陣相等) 設(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(點陣加法) 設(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(點陣負元) 設(shè)P,Q∈G，其中Pij是矩陣P第i行第j列的元素，Qij是矩陣Q的第i行第j列的元素，若O=P+Q，其中O為元素全為無窮遠點O的零陣，也即O=Pij+Qij(i=1,2,…,r;j=1,2,…,s)，則稱P為Q的負元(或Q為P的負元)，記為P=-Q(或Q=-P)。

下面證明有限域GF(28)上橢圓曲線上的點陣關(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)每個元都有逆元：設(shè)P∈G，則點陣P中的元素Pij都是橢圓曲線上的點，因此必然存在橢圓曲線上的點Qij使得有Pij+Qij=O，因此點陣Q=[Qij]∈G。

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

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

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

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

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

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

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

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

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

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

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

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

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

本文選取8次不可約多項式p(x)=x8+x5+x3+x2+1，并選取有限域GF(2)[x]/p(x)上的一個生成元g=x，可以得到g在模不可約多項式p(x)下各次方冪的運算結(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，通過計算，可以得到此參數(shù)條件下橢圓曲線E28(g8,1)上基于生成元g的方冪表示的總共287個點，如表2所示，其中(x,y)表示實際橢圓曲線上的點(gx,gy)，(′E0′, 0)表示實際橢圓曲線上的點(0,1)。其對應的橢圓曲線E28(g8,1)上的點如圖1所示。

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

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

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

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

表3 字符編碼表

注：space表示空格符。

假設(shè)要加密的字符串為M=hello,It’snicetomeetyou。首先，通過字符與橢圓曲線上點的對應關(guā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個字符，可以得到M=M1+M2+M3+M4，選擇基點G=(g1,g183)，得到G點的階order=48(即有(n·order)G=O，其中O為無窮遠點)，并隨機生成具有7個分量的整數(shù)向量k=30 7 128 201 13 97 58，設(shè)B的私鑰為nB=34，則加密方A通過B的公鑰PB=nBG=(28,172)對消息分組進行加密Cm={kG,Pm+kPB}，最后可得加密后密文消息為C=C1+C2+C3+C4，其中：C1=ΦУΩΨ?、Бぉ颧璃恪膟i;C2=9У∪Ψ0ⅶA┤AcШуΨ;C3=┤УΩΨ?ⅶШ┤ЯсууⅨ;C4=vУΩΨnⅶ↓┤jc!Yσ。從加密結(jié)果來看，顯然，當明文點所對應的k值相同時，其加密之后的密文點對的第一個分量也相同，因此符合預期。加密后的密文點對所對應的生成元g的方冪表示如表4所示，其中(x,y)表示實際橢圓曲線上的點(gx,gy)。

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

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

4 安全性分析

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

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

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

4.2 隨機點列的破解難度

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

同一個有限域GF(2m)上可能會有多個不同的生成元，例如在有限域GF(24)上，選取多項式環(huán)GF(2)[x]上的4次不可約多項式為p(x)=x4+x+1時，可選擇的生成元包括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)上的同一個元素在不同正規(guī)基下會有不同的表現(xiàn)形式，對于有限域GF(2m)來說，情況也類似，因此，只有在知道所選擇的正規(guī)基g之后，才能將正規(guī)基形式表示的點(x,y)還原到真正的橢圓曲線上的點(gx,gy)，由于正規(guī)基選擇的非確定性，從而使得基于正規(guī)基表示的橢圓曲線點陣群的加密算法有更高的安全性。

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

5 結(jié)語

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