基于低復雜度多項式乘法器的智能電能表橢圓曲線加密系統的設計

孫艷玲，邢宇，董賢光，翟曉卉，孫艷鳳，張宏生

(1.國網山東省電力公司營銷服務中心(計量中心)，濟南 250001； 2.國網天津市電力公司薊州供電分公司，天津 301900； 3.國網安徽省電力公司營銷服務中心，合肥 230088)

0 引 言

近年來，隨著國家電網的大規模建設，智能電網作為國家電網系統交通終端一環已經變得越發重要了[1-2]。由于智能電網的規模大，智能電能表與各個環節的網絡存在很多的數據交換，這些數據交換在通信過程中隱存很多安全問題。如何恰當地設計智能電能表適應的安全系統是學術界和工業界一個當前的研究熱點。

圍繞智能電能表的安全問題已經在各個方面逐步展開[3-14]。故障預警系統的設計與開關在最近的文獻[3]中有涉及。基于同態密碼體制的智能電能表安全協議在文獻[4]也有所報道。特別一提的是，文獻[5-10]提出了關于智能電能表的數據安全采集和用戶隱私保護問題。另外，文獻[11-14]展示了智能電能表的安全算法和相關電路系統的研究。總體而言，對于如何給智能電能表配置適當的密碼系統的研究還是有待繼續加強。

橢圓曲線密碼系統(Elliptic Curve Cryptography (ECC))安全問題如圖1所示，由于能夠提供比傳統的密碼系統更強的效果，現在已經成為智能電能表中的安全系統的理想候選者[15-19]。但是由于橢圓曲線密碼系統的計算復雜度較大，并且智能電能表中還有其它的應用資源需要考慮[20]，目前，距離具體應用還有大量的研究工作。

圖1 智能電網中關系于數據通信系統的安全問題Fig.1 Security issues related to a typical data communication system within smart grid

在橢圓曲線密碼系統中最主要的一個運算是基于橢圓曲線上的點加法運算，其中包含了在二進制域(GF(2m))中的加法、開方和乘法運算。在二進制有限域中加法和開方運算都能比較簡單且快速，然而二進制有限域的乘法運算就顯得比較復雜。這就使得密碼系統占有資源面積變大、整體運算時間加長和運算速度減慢。文獻[15-19]相繼推薦了5個不可約多項式用于橢圓曲線密碼器的計算，目前許多的研究工作集中在如何有效實現基于有限域GF(2m)上的乘法器。

基于有限域GF(2m)(二進制域)的多項式乘法器的實現可以主要分為三個基的運算：多項式基、正規基、和復基。對于橢圓曲線密碼系統，特別是對于基于Koblitz曲線的密碼器，基于正規基的多項式運算比其它兩種基具有明顯的效果：基于正規基的GF(2m)開方不需要任何硬件資源(只需要簡單的移位)。但從另一面來說，一個有效的橢圓密碼系統的實現也由一個密碼系統中的主要運算單元的平行度所決定。因此，一個好的密碼系統的實現需要同時優化底層結構和上層算法。

可編程邏輯器件(Field-Programmable Gate Array (FPGA) Device)具有操作簡單和易于重復編程等特點，目前正在智能電網中越來越多地使用。文中根據這一發展趨勢，提出了一種基于FPGA平臺的新型橢圓曲線密碼系統設計方式(適用智能電能表平臺)。該設計從底層的乘法器設計創新出發，擴展到高層橢圓曲線的點計算。設計的結構在具體的FPGA器件上進行驗證通過。該密碼系統與現有的系統相比具有資源占用率低、速度快等特點。因而該設計系統值得在智能電網建設中大力推廣并使用。

1 橢圓曲線密碼系統

橢圓曲線密碼系統是由文獻[21]在1985年提出的。該系統的具體組成和數學背景陳述如下：

1.1 高斯正規基(Gaussian Normal Basis)

高斯正規基是正規基中的一種，由于它的運算復雜度低，近年來受到學術界越來越多的關注[22]。高斯正規基在GF(2m)域下的定義如下：

設N={β,β2, …,βn}，其中，n=2m-1;m是域的次數(β是一個正規基的基本單位)。那么對于任何的一個多項式A在該域下的表達式可為：

(1)

式中A=(a0,a1, ....,am-1)和ai∈GF(2)。高斯正規基的運算較普通的正規基要簡單一點，但是它的開方運算仍然遵循不需要硬件資源這一規則。對于在該基下的兩個多項式A和B，它們的乘積C可以表示為：

(2)

式中R(i,j), 0≤R(i,j)≤m-1, 1≤i≤m-1, 1≤j≤T表示乘法矩陣R(m-1)×T，該乘法矩陣的具體過程可參考文獻[18]。

1.2 橢圓曲線(Koblitz曲線)

一般說來，一個Koblitz曲線可以通常表示為：

Ea,b:y2+xy=x3+ax2+b

(3)

式中a,b∈GF(2m)并且b≠0。取橢圓曲線上的兩個點P和Q，使得Q=kP(k>1是整數)。那么，點P稱為曲線的基點，Q稱為結果點。一般來說，在曲線上點的運算包含點加運算和點乘運算(點乘運算可以轉為點加運算)。

1.3 點加運算

有很多方法已經被提出來去有效地實現Koblitz橢圓曲線上的點加運算。其中最主要的包括Jacobian投影、標準投影和Lopez-Dahab投影方法。文中設計參考的是Lopez-Dahab投影方法，它的主要過程如下：

假設X、Y和Z表示曲線上的點的坐標，那么整個點加運算的過程如下：

(4)

(5)

(6)

通過這些點的依次運算，就可以得到橢圓曲線密碼系統的綜合運算過程。

2 橢圓曲線密碼系統的新型設計方案

2.1 乘法器和加法器的新型混合設計方式

橢圓曲線密碼系統的硬件實現一般都會用到底層基于GF(2m)域的高斯正規基乘法器和加法器。為了達到較好地實現效果如資源占用低、速度快等，乘法器一般都采用多位串行處理的方法(Digit-Serial)，如圖2所示。圖2中包含了一個乘法器的乘法核心單元和累加單元以取得最終的乘積(其中的一個輸入是以分段的方式接入到乘法器核心單元里面)。累加單元則需要對這些分段得到的乘法結果進行累加并且輸出最終結果。

圖2 一個基于GF(2m)域的高斯正規基乘法器Fig.2 One Guassian normal basis multiplier based on GF(2m)

由于基于高斯正規基的開方運算是沒有硬件資源消耗(只有位的位置轉換)，那么有：

(7)

式中I1和I2為輸入；I為輸出。按照傳統實現方法，式(7)需要先進行I2的開方運算，然后再進行下一步的乘法運算來取得最終結果。

為減少具體應用過程的計算延遲，文中提出一種新型的乘法器和加法器混合設計方法：即把這個開方運算合并到乘法運算里面(因開方只有位的移位而已)。這樣，原來兩個運算就可以合并成為一個新的單獨運算，相對應的設計如圖3所示。

圖3 混合結構的乘法器(新型設計)Fig.3 Hybrid structure based multiplier (new design)

如圖3所示，由于開方的運算不占用資源，原先需要兩個周期的運算(指乘法和開方)現在就可以在一個周期內完成。這樣的設計安排將對整個密碼系統的涉及到乘法和開方的運算進行優化。

同樣，對于以下的運算方式：

I=(I1+I2)2

(8)

式中I1和I2為輸入；I為輸出。按照傳統的實現方法，式(8)需要先進行I1和I2的加法運算，然后再進行下一步的開方運算。

為此，文章提出一種新的混合設計方法，即把這個開方運算合并到加法運算里面(開方只有位的移位而已)。這樣原先的兩個運算就可以轉換成為一個單獨的運算如圖4所示。

圖4 新的混合運算加法器Fig.4 New hybrid adder

為驗證文中提出的混合結構的優勢，文章對圖3和圖4的混合結構采用硬件描述語言(Very High-Speed Integrated Circuit Hardware Description Language, VHDL)進行建模仿真。這兩個設計在FPGA(Altera Cyclone II芯片)平臺上進行仿真驗證，并且通過Altera Quartus II 12.1 軟件測得結果。本設計采用m=100作測試，所得的FPGA結果(主要指占用邏輯資源)如表1所示。

表1 FPGA測試結果Tab.1 FPGA testing result

LE: Logic element，FPGA平臺上的邏輯資源。

由表1可知，采取了混合結構的資源占有和非混合結構(FPGA平臺上)是一樣的。這顯示本設計可以在具體算法中進行使用而不增加額外資源消耗。

2.2 橢圓曲線算法的新型優化

為了更好地融合所提出的混合乘法器和加法器結構，該設計將之前的算法式(4)～式(6)改進如下：

(9)

(10)

(11)

其中，H1=y2Z12，H2=A2和H3=B2這三個運算都可以用之前提出的混合結構來實現。

2.3 信號流程圖

根據文獻[18]，式(4)～式(6)橢圓曲線系統的整體運算，可以用圖5的信號流程圖來表示，如圖5所示。

由圖5中可以看到，整個橢圓曲線系統的算法運行可以由13個階段組成，其中三個階段的主要運行是乘法器(每個階段有M+1個運算周期)。綜合而言，乘法器的執行所占用時間遠遠大于其它運算所占用的時間。所以，整個橢圓曲線密碼系統的計算時間實際上主要由乘法器的執行時間決定。

圖5 信號流程圖Fig.5 Signal flow chart

為降低密碼系統的整個執行時間，文中采用所提出的新設計方式如式(9)～式(11)。如圖6所示，文中采用的新型混合結構的橢圓曲線密碼系統的整個算法的計算時間由之前的12個階段減少到10個階段。這樣，整個算法的計算時間得以有效減少。此外，由于減少了2個計算階段，相應的硬件控制環節和涉及的硬件資源消耗也會降低。

圖6 新的信號流程圖(虛線框內是混合結構)Fig.6 New signal flow chart (dotted block is the hybrid structure)

2.4 橢圓曲線密碼系統的新型結構

該硬件結構是由圖6的信號流程圖直接印射而得，基于新的信號流程圖上的橢圓曲線密碼系統的新型硬件結構如圖7所示。

圖7 最終的橢圓曲線密碼系統架構Fig.7 Finalized structure for ECC

由于圖6所示的整個的橢圓曲線密碼系統需要4個乘法器和2個加法器，圖7中的硬件結構主要由三大塊組成：控制器、運算器和寄存器。控制器主要是產生相對應的控制信號以進行各個運算周期的調配。運算器則是包含了基本的運算單元如乘法器和加法器。寄存器主要的作用是進行各個運算周期之間的數據讀入和讀出。在具體的運行過程中，該三大塊組件需要進行合理協調以得到正確結果。

3 FPGA平臺上的測試和驗證

為驗證本設計的優異性能，設計好的結構如圖7所示，用硬件描述語言(VHDL)進行編程建模。然后，所設計的結構在FPGA Altera Stratix II EP2S180F10 20C3芯片上進行測試和驗證(在具體的測試中文章采用了m=163和m=233)。為展示本設計的優異性能，文章把所測試的結果與現有的文獻[15-18]進行比較，結果展示在表2中。值得注意的是現有的文獻主要報導了m=163的結果。但隨著安全技術的進步，選擇較大的m(與安全級別直接相關)將有更廣泛的應用空間。

表2 FPGA平臺測試結果比較Tab.2 Comparison of testing results on the FPGA platform

其中，面積的大小由ALM(Adaptive Logic Module，FPGA平臺上的基本邏輯資源)的數量決定，最高頻率的單位是MHz。m值的大小主要反應密碼系統的安全級別(通常m越大系統越安全)。但是比較則是需要按相同的m值下的性能進行比較。現有文獻[15-18]只報導了m=163時的結果。面積×時間=ALM的數量×(延遲周期/頻率)。該參數通常用來衡量一個設計的綜合面積和時間復雜度。

由表2可知，文章所提出的結構與之前的結構相比(相同的m值情況)具有更好的時間和資源利用效率。考慮到本設計也降低了橢圓曲線的計算周期，最終的時間使用改進力度將大幅超過之前報道的結果。同時，由于本設計采用了高斯基的多項式乘法器，本設計的最終占用邏輯資源與之前的設計相比也有較大幅度的降低(比如，在m=163情況下，相比文獻[15-18]，文中設計有164-7581ALM的節省)。

除此之外，該設計也具有延遲時間低的特點(延遲時間=延遲周期/頻率)。如表2所示，文中的頻率比之前的結構具有較好的可比性。同時，該設計的延遲周期相對比較少。因此，該設計的綜合延遲時間小于其它參考設計的延遲時間。

綜合而言，文中所提出的橢圓曲線密碼系統比之前的報道結果在時間和資源使用上都有較大幅度的改進。如表2所示，文中采用了面積×時間的綜合復雜度指標來衡量各個方案的實現復雜度(該指標在其它參考文獻中也被使用[15-18])。表2的數值表明文中設計的密碼器比現有結構至少低了18.2%的綜合復雜度(面積和時間上)。

除此之外，文章所設計的橢圓曲線密碼系統結構也在智能電能表上進行驗證測試。文中將所設計的結構嵌入智能電能表的測試平臺進行輸入輸出測試。在進行1 000次的輸入測試過程中，得到的輸出結果與預想完全吻合(正確率達到100%)。

終上所述，該設計的新型橢圓曲線密碼系統具有計算周期少、運算速度快和占用面積小等特點。因此，該設計方案比較適合于在智能電能表(或者類似平臺)上的應用。考慮到智能電網同時還包括了其它方面的組成部件[20-23]，未來在這一方面的研究可以擴展到如何更好的與周圍的部件協同運行。此外，考慮到智能電能表的具體應用環境(客戶終端一環)，加強所設計密碼系統的防攻擊能力(如側道攻擊等)也是未來研究的一個主要方向。

4 結束語

文章提出了一種應用于智能電能表平臺的新型橢圓密碼系統設計方法。該密碼系統的設計方案主要由底層的運算單元結構設計創新、上層算法流程的優化更新和最終新型硬件結構設計而組成。文中對所得到的相對應硬件結構進行了基于FPGA平臺上的具體測試，并且取得了比之前文獻所報導結構更好的結果。此外，該密碼系統在具體的測試也驗證了其在智能電能表中的應用可行性。

文章的具體創新點為：(1)提出新的有限域乘法器和加法器混合結構設計方式；(2)提出新的橢圓曲線算法實現方式；(3)提出基于新算法的橢圓曲線密碼硬件設計方案和整體架構。文章所提出的密碼系統新型設計方案具有延遲少、速度快和面積小等特點，適合在智能電網中的智能電能表上大規模推廣使用。