Maple在二進(jìn)制域橢圓曲線密碼中的應(yīng)用*

劉星江，曾 玲

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

Maple是一個具有強(qiáng)大的符號運算能力、數(shù)值計算能力和圖形處理能力的交互式計算機(jī)代數(shù)系統(tǒng)。它可以借助鍵盤和顯示器代替原來的筆和紙來進(jìn)行各種科學(xué)計算、數(shù)學(xué)推理、猜想的證明等。Maple最早由加拿大滑鐵盧大學(xué)的符號計算機(jī)研究小組于上世紀(jì)八十年代開發(fā)出來，由于其在高精度數(shù)值計算和符號計算方面的優(yōu)勢，自問世以來就常用于解決各種各樣的數(shù)學(xué)問題，比如微積分、線性代數(shù)、組合論等。

Maple在數(shù)值計算方面和其他程序設(shè)計語言（比如C語言）有很大的不同，最主要的不同是Maple中定義的變量沒有類型區(qū)別，同時變量的位寬沒有嚴(yán)格的限制要求。例如，在C語言中定義的整型變量一般為32比特或者64比特，而在Maple中定義的整型變量沒有這個限制。關(guān)于Maple的詳細(xì)內(nèi)容可參見文獻(xiàn)[1]。

由于Maple中對變量的位寬沒有限制，所以對處理大整數(shù)的運算來說，Maple顯得非常方便。利用這個特點采用Maple實現(xiàn)RSA密碼算法（Rivest，Shamir，Adleman一起提出的一種非對稱加密算法）、橢圓曲線密碼（Elliptic Curve Cryptography，ECC）等將是非常方便快捷的。在文獻(xiàn)[2]中，介紹了Maple在素數(shù)域橢圓曲線密碼中的應(yīng)用。本文主要介紹Maple在二進(jìn)制域橢圓曲線密碼中的應(yīng)用。

1 二進(jìn)制域上的運算及Maple實現(xiàn)

設(shè)p是一個素數(shù)，m是一個正整數(shù)。由有限域理論（可參見文獻(xiàn)[3]）知道，在同構(gòu)意義下存在唯一的pm元域，記作Fpm。特別地，當(dāng)p=2時，有限域F2m就稱為二進(jìn)制域。對于二進(jìn)制域F2m可以如下構(gòu)造。

首先，選擇一個二元域F2上的m次不可約多項式f(z)，f(z)在二元域上的多項式環(huán)F2[z]中生成一個主理想(f(z))，商環(huán)F2[z]/(f(z))即是二進(jìn)制域F2m。具體地說，二進(jìn)制域F2m中的元素即是二元域上次數(shù)小于m次的多項式，其中的加減乘除運算則是模不可約多項式f(z)的模加、模減、模乘、模除運算。下面分別介紹這些運算在Maple中的實現(xiàn)。

1.1 模加減

由于二元域中加法和減法完全相同，所以二進(jìn)制中的模加與模減也完全相同，即是兩個多項式同次項系數(shù)做異或運算即可。在Maple中可以如下實現(xiàn)。

1.2 模乘

如上所述，二進(jìn)制域中的乘法運算即是多項式的模乘運算，在Maple中可以如下實現(xiàn)。

1.3 模逆

由于模除運算可以轉(zhuǎn)換成一次模逆運算加上一次模乘運算，實現(xiàn)了模逆運算便可以實現(xiàn)模除運算。對于模逆運算來說，由于在二進(jìn)制域中對任意的非零元a∈F2m，有a2m-1=1（可參見文獻(xiàn)[3]）。所以a-1=a2m-2。這樣就把模逆運算轉(zhuǎn)換成了模乘運算。在Maple中模逆運算可以如下實現(xiàn)。

2 二進(jìn)制域上橢圓曲線運算及Maple實現(xiàn)

設(shè)m是一個正整數(shù)，二進(jìn)制域F2m上的非奇異橢圓曲線E可以由如下方程定義：

其中b≠0（可參見文獻(xiàn)[4]）。

令E(F2m)表示該橢圓曲線上的所有有理點添加上一個無窮遠(yuǎn)點∞組成的集合。在該集合E(F2m)上定義如下的加法運算：

（1）對任意一點P∈E(F2m)，有P+∞=∞+P=P；

（2）對任意一點P=(x,y)=E(F2m)，有P+(x,x+y)=(x,x+y)+P=∞，這里稱(x,x+y)為P的負(fù)點，記為-P；

（3）（ 點 加 運 算 ） 設(shè)P=(x1,y1)∈E(F2m)，Q=(x2,y2)∈E(F2m)，且P≠±Q，則P+Q=(x3,y3)，這里x3=λ2+λ+x1+x2+a，y3=λ(x1+x3)+x3+y1，其中λ=(y1+y2)/(x1+x2)；

（4）（倍點運算）設(shè)P=(x1,y1)∈E(F2m)，且P≠ -P，則2P=(x3,y3)，這里x3=λ2+λ+a，y3=x12+λx3+x3，其中λ=x1+y1/x1。

在該加法運算下E(F2m)便組成一個交換群。

設(shè)P∈E(F2m)，k是一個正整數(shù)，Q=kP是k個點P相加。已知k和點P計算點Q是比較容易的，其計算過程成為橢圓曲線上的點乘運算。反之，已知點P和點Q計算k是比較困難的，它稱為橢圓曲線上的離散對數(shù)問題。該離散對數(shù)問題是一大數(shù)學(xué)難題，橢圓曲線密碼體制也正是基于該難題來構(gòu)建的。

在關(guān)于橢圓曲線的各種密碼協(xié)議中，點乘運算都是其中運算量最大的運算部分。而點乘運算又可以由多次的點加運算和倍點運算組成，在上述定義中可以看到每次點加和倍點運算都包含了一次運算量較大的模逆。為了提高運算效率，把模逆省去，同時也為了讓無窮遠(yuǎn)點有坐標(biāo)表示，可以采用射影坐標(biāo)來表示橢圓曲線上的點，這里采用LD射影坐標(biāo)（以下簡稱LD坐標(biāo)）表示，可參見文獻(xiàn)[4-5]。普通坐標(biāo)與LD坐標(biāo)之間的相互轉(zhuǎn)換關(guān)系如下。

普通坐標(biāo)轉(zhuǎn)換成LD坐標(biāo)：

LD坐標(biāo)轉(zhuǎn)換成普通坐標(biāo)：

由此可見，普通坐標(biāo)轉(zhuǎn)換成LD坐標(biāo)是容易的，LD坐標(biāo)轉(zhuǎn)換成普通坐標(biāo)可如下實現(xiàn)。

在LD坐標(biāo)下的點加和倍點運算規(guī)則參見文獻(xiàn)[4-5]，這里不再贅述。點加和倍點在Maple中可如下實現(xiàn)。

（1）倍點運算：

（2）點加運算：

有了點加和倍點運算后，點乘運算便容易實現(xiàn)，這里采用從左向右掃描點乘標(biāo)量的方式實現(xiàn)，具體如下。

（3）點乘運算：

3 橢圓曲線密碼體制的Maple實現(xiàn)

橢圓曲線密碼作為一種公鑰密碼體制，具有數(shù)字簽名、密鑰協(xié)商、公鑰加密等功能。它可以用于確保數(shù)據(jù)來源的可靠性、不可抵賴性、不可偽造性、不可篡改性等。關(guān)于橢圓曲線相關(guān)的密碼協(xié)議可參見文獻(xiàn)[6-8]。

下面將以數(shù)字簽名為例，討論如何在Maple中實現(xiàn)橢圓曲線數(shù)字簽名協(xié)議（Elliptic Curve Digital Signature Algorithm，ECDSA）。ECDSA簽名協(xié)議分為兩個部分，一部分是簽名生成算法，輸入私鑰、消息的雜湊值、隨機(jī)數(shù)，簽名運算輸出簽名值；一部分是驗證簽名算法，輸入公鑰、消息的雜湊值、簽名值，驗簽運算返回該簽名的有效性。關(guān)于ECDSA協(xié)議的詳細(xì)內(nèi)容可參見文獻(xiàn)[4]。

首先選擇一個二進(jìn)制域F2m，取其中的模數(shù)多項式為z4+z+1，然后再選擇其上的一條橢圓曲線y2+xy=x3+z3x2+(z3+1)，選擇其上的點G=(z3,1)為基點，它的階n=11。選擇簽名用的私鑰d=5，它對應(yīng)的公鑰為Q=(z3+z+1,z)。

3.1 簽名生成

簽名運算需要輸入私鑰、待簽名的雜湊值和簽名用的隨機(jī)數(shù)。這里選擇待簽名的雜湊值e=6，隨機(jī)數(shù)k=7，簽名過程如下。

首先計算點乘：

把kG的橫坐標(biāo)轉(zhuǎn)換成整數(shù)，得到15，再模n約減，即得簽名值r=4，簽名值s可如下計算得到。

最終得到簽名值為(r,s)=(4,10)。

3.2 驗證簽名

首先判斷簽名值是否均在(1,n-1)中，如否，則拒絕該簽名。然后計算

把R的橫坐標(biāo)轉(zhuǎn)換成整數(shù)，得到15，再模n約減，即得rbar=4。即rbar=r，所以驗證簽名通過。

4 結(jié) 語

為了敘述方便，上述選擇了較小的不可約多項式來展示了整個ECDSA協(xié)議的運算過程。事實上，目前滿足安全性需求的不可約多項式的次數(shù)均在百次以上。高次的多項式運算方法完全相同，只是運算需要的時間更長而已。