橢圓曲線加密教學中輔助軟件的開發(fā)與應(yīng)用

方賢進，吳艷婷，王 麗

（安徽理工大學 計算機科學與工程學院，安徽 淮南 232001）

0 引 言

橢圓曲線加密（Elliptic Curve Cryptography,ECC）已經(jīng)廣泛地使用在TLS、PGP和SSH中，這3項技術(shù)是現(xiàn)代IT世界的加密基礎(chǔ)，當今流行的比特幣（BitCoin）、區(qū)塊鏈（Block Chain）等加密貨幣技術(shù)更是以此為基礎(chǔ)。

在中國知網(wǎng)（CNKI）上搜索“橢圓曲線”“教學”兩個關(guān)鍵詞，可檢索到5 835條文獻，但幾乎都是關(guān)于ECC學術(shù)方面的論文，教研類的論文只有郎榮玲、劉建偉等人在《計算機教育》發(fā)表的“信息安全數(shù)學基礎(chǔ)理論教學方法研究”[1]，但也只簡單提及“橢圓曲線密碼體制來源于對橢圓曲線的研究，因此在講授這個部分內(nèi)容時一定要把橢圓曲線的物理意義以及其應(yīng)用講清楚”。

現(xiàn)代密碼學[2]中ECC的教與學存在一定困難，首先橢圓曲線加密涉及橢圓曲線幾何、集合論、Abel群、有限域等數(shù)學知識，另外橢圓曲線加密運算要應(yīng)用模運算、擴展的歐幾里得算法、有限域上的點加運算、倍點運算等，有些運算不僅抽象（例如點的逆元運算、點加運算、2倍點運算等），而且計算量很大（例如有限域上點集合計算、多倍點運算）。在教學過程中筆者發(fā)現(xiàn)，學生覺得橢圓曲線加密算法具有神秘感，難以直觀理解。鑒于此，利用HTML5新功能結(jié)合CSS、jQuery框架開發(fā)基于Web的可視化工具軟件，用于輔助講解橢圓曲線及其代數(shù)與幾何特性、橢圓曲線下Abel群的定義及幾何意義、有限域GF（p）上橢圓曲線點的計算等，為學生更好地理解橢圓曲線加密算法及其應(yīng)用（如加解密、數(shù)字簽名等）奠定基礎(chǔ)。橢圓曲線加密教學方法探討的設(shè)計框架見圖1。

圖2　（a）實數(shù)域上的一般橢圓曲線

圖2　（b）奇異橢圓曲線（4a3+27b2=0）

圖3　橢圓曲線加密教學輔助軟件的功能模塊

1 橢圓曲線及其代數(shù)幾何特性的認識教學

橢圓曲線在代數(shù)學和幾何學上已被廣泛研究了150多年，有堅實的理論基礎(chǔ)。橢圓曲線密碼體制以橢圓曲線為基礎(chǔ)，因此在講解橢圓曲線密碼體制之前，先要讓學生搞清楚橢圓曲線的代數(shù)與幾何特性，這樣才能更好地理解橢圓曲線的基本原理及相關(guān)理論。

無論是實數(shù)域還是有限域上的橢圓曲線，學生都覺得比較抽象。為了讓學生更好地理解橢圓曲線上點的各種運算及其幾何意義，有必要讓學生對各種橢圓曲線的特性有直觀的了解，如關(guān)于x軸的對稱性、根的判別式與奇異曲線等。因此，利用開發(fā)的可視化軟件，在講解橢圓曲線的幾何特性時通過改變html5頁面表單中數(shù)字型輸入框參數(shù)a、b的值，可以形象地得到實數(shù)域上各種不同的橢圓曲線，見圖2（a）、2（b）。

該輔助軟件基于Web架構(gòu)，采用HTML5+jQuery框架的Web前端開發(fā)技術(shù)，不需要后端（Server）支持。軟件的主要功能是橢圓曲線加密基礎(chǔ)理論的輔助教學及可視化，其功能模塊見圖3，具體軟件參見作者個人網(wǎng)站http://star.aust.edu.cn/～xjfang/crypto。

2 橢圓曲線下的Abel群的定義及幾何意義的教學

橢圓曲線上所有的點、點加運算、點的純量乘法構(gòu)成一個Abel群（交換群）。但是，在講解這部分內(nèi)容時，涉及群論的很多概念和知識，如橢圓曲線上所有點及運算構(gòu)成Abel群的單位元概念、逆元概念、點加運算、點的純量乘法運算、點加運算的結(jié)合律、交換律等。如果缺乏形象、直觀地展示與驗證，往往比較枯燥、乏味。

橢圓曲線上兩個不相等的非零點P=（xP ,yP）、Q=（xQ,yQ），它們的點加運算P+Q=R=（xR,yR）的代數(shù)計算公式為

其中m=（yP-yQ）/（xP-xQ）。

為了更清晰地講解點加運算，可以用可視化的方法演示點加運算的代數(shù)計算結(jié)果以及其幾何意義：橢圓曲線上點加運算的幾何意義是連接兩個點P與Q，PQ的延長線與曲線的交點關(guān)于x軸的對稱點即為這兩個不同點P與Q之和。圖4（a）是橢圓曲線 上的兩個點P（1, 2）、Q（3, 4）相加得到點R（-3, 2）及其幾何意義，點R（-3, 2）是PQ延長線與橢圓曲線的交點（-3, -2）的對稱點。圖4（a）同時驗證了橢圓曲線下群的定義一條規(guī)則：橢圓曲線上3個連成一線的非單位元點P、Q、-R，它們的和為P+Q+（-R）=O。圖4（b）演示了橢圓曲線上群的定義的另一條規(guī)則：若P、Q互為逆元，即P與Q關(guān)于x軸對稱，或者說Q=-P，則P+Q=O，其表示無窮遠點O是平行于y軸的直線的一種抽象。

純量乘法又稱為倍點運算，即nP=P+P+ +P，純量乘法的計算基礎(chǔ)是兩個相同點的點加運算。如果P（xP,yP）是橢圓曲線上的點，按照以下規(guī)則計算2P=P+P=R=（xR,yR）。

其中m=（3x2p+a）/2yp。

當純量乘法運算中的n比較大時，其運算是反復(fù)通過倍加（double and add）算法實現(xiàn)的。例如，計算151P，將n=151表示成二進制形式：151=27+24+22+21+20，151P=27P+24P+22P+21P+20P，

2P利用公式（2）計算，4P利用2P計算，以此類推，反復(fù)利用倍加運算完成計算。

圖5（a）是橢圓曲線上點的標量乘法及計算結(jié)果的可視化；圖5（b）表示兩個相同點相加（P+P=2P）的結(jié)果及幾何意義，即過該點做橢圓的切線，切線與橢圓曲線交點的對稱點即為兩個相同點相加的結(jié)果；圖5（b）與5（c）表示兩個相同點的點加運算（P+P）與點P的二倍純量乘法（2P）的結(jié)果與幾何意義的一致性。

圖4　（a）不相同的兩個點的加法運算

圖4　（b）互為逆元的兩個點的加法運算

圖5　（a）點的純量乘法

圖5　（b）兩個相同點相加的幾何意義

圖5　（c）2P純量乘法的幾何意義

3　有限域GF（p）上橢圓曲線點的計算的教學

3.1　有限域GF（p）上橢圓曲線點集合計算演示

橢圓曲線 ，對每個x=0,1,…,p-1計算x3+ax+b（modp），如果其值是一個模p的平方根，則找到橢圓曲線上的兩個點（x,y）、（x,p-y）。該算法的執(zhí)行過程可通過圖5中的可視化工具演示，選擇參數(shù)n=1，對點P橫坐標x的輸入框依次選擇0～p-1，則計算出橢圓曲線在有限域GF（p）上的所有離散點并顯示出來。與實數(shù)域橢圓曲線一樣，在有限域GF（p）上的橢圓曲線的這些離散點及其運算仍然構(gòu)成一個Abel群（交換群）。

3.2　有限域GF（P）上橢圓曲線的點的純量乘法、循環(huán)子群、階及其可視化

有限域GF（p）上一個橢圓曲線所有點構(gòu)成的Abel群中點的數(shù)量稱為群的階，記為N。當p是一個很大的素數(shù)時，可以利用Schoof算法[3]在多項式時間內(nèi)計算N的值。橢圓曲線 上所有離散點構(gòu)成的Abel群的階N=100，見圖6。

圖6　有限域GF（p）上橢圓曲線點集合的計算與可視化

有限域GF（p）上橢圓曲線點的純量乘法的代數(shù)計算與實數(shù)域上一樣（參見2.1節(jié)），但是有限域上橢圓曲線的純量乘法具有自身的特殊性，見圖7。

假設(shè)有橢圓曲線 ，其上的一個P（3,6），若對P進行純量乘法計算會發(fā)現(xiàn)其結(jié)果只有5個不同的值（O,P,2P,3P,4P），并且循環(huán)出現(xiàn)。

可以驗證純量乘法在加法運算下是封閉的，即對有限域上橢圓曲線的某個點P迭代地進行純量乘法得到的點集合構(gòu)成一個循環(huán)子群，P稱為循環(huán)子群的生成元（generator）或基元（base point）。有限域 GF（p）上的橢圓曲線的循環(huán)子群是橢圓曲線加密算法及其他加密系統(tǒng)的基礎(chǔ)。

由P生成的橢圓曲線上子群的階是指一個最小的正整數(shù)n，滿足nP=O。例如，橢圓曲線 上的一個點P（12,3）生成的子群的階是50，見圖8。

圖7　有限域上橢圓曲線點的純量乘法的特性

圖8　有限域橢圓曲線上點的集合、點P作為生成元構(gòu)成的子群及其階

3.3　有限域上GF（p）上橢圓曲線的點加運算及其可視化

有限域GF（p）上的橢圓曲線點加運算與實數(shù)域的差別是所有計算都是在模p下進行，但是由于有限域GF（p）上橢圓曲線的點都是離散的，從直觀的角度不存在幾何意義上3個點連成一線的問題。因此，有限域GF（p）上的橢圓曲線點加運算的幾何意義是不同于實數(shù)域。有限域GF（p）上橢圓曲線上的3個離散點p、Q、R連成一線是指3個點的坐標滿足線性方程y=mx+c（modp），其中參數(shù)m、c可由其中兩個點的坐標計算確定。

因此，有限域上GF（p）上橢圓曲線兩個點相加P+Q=R的幾何意義是：首先由P、Q確定斜率為m的一組平行線(滿足線性方程y=mx+c（modp）），若橢圓曲線的點集合中某個離散點R’落在某一條平行線上，則R’關(guān)于x軸的對稱點R就是P+Q的結(jié)果。橢圓曲線 上的兩個點P（16,20）、Q（41,120）進行點加運算，計算斜率c=83，得到滿足方程 的一組平行線，在點集合中容易驗證R’=（86, 46）滿足該方程，則R’的逆元R=（86, -46）=（86,-46+127）=（86, 81）即為點P與Q相加的結(jié)果，見圖9。

4 結(jié) 語

筆者針對橢圓曲線加密教學過程中若干難點問題設(shè)計了幾個教學內(nèi)容，包括橢圓曲線及其代數(shù)幾何特性的認識與可視化、橢圓曲線下的Abel群運算規(guī)則的幾何意義可視化教學、有限域GF（p）上橢圓曲線點集合計算與可視化教學、有限域GF（p）上橢圓曲線的點的純量乘法、循環(huán)子群、階及其可視化、有限域上GF（p）上橢圓曲線的點加運算與可視化等。橢圓曲線加密教學中的輔助工具軟件可訪問筆者的課程建設(shè)網(wǎng)站http://star.aust.edu.cn/～xjfang/crypto/。 下 一 步 擬 進行ECC基本參數(shù)生成、明文映射到橢圓曲線上的點的算法、加解密算法、數(shù)字簽名算法等相關(guān)教學內(nèi)容的可視化設(shè)計，并力爭達到工業(yè)級別的ECC加解密教學演示系統(tǒng)、數(shù)字簽名教學演示系統(tǒng)。

圖9　有限域GF（p）上的橢圓曲線點加運算的可視化

參考文獻：

[1]郎榮玲, 劉建偉, 金天. 信息安全數(shù)學基礎(chǔ)理論教學方法研究[J]. 計算機教育, 2012(17): 33-35.

[2]谷利澤, 鄭世慧, 楊義先. 現(xiàn)代密碼學教程[M]. 北京: 北京郵電大學出版社, 2015.

[3]SchoofP R. Counting points on elliptic curves over fnite felds[J]. Journal de Théorie des Nombres de Bordeaux, 1995(7): 219-254.in France.