一種高效的橢圓曲線密碼標(biāo)量乘算法及其實(shí)現(xiàn)

時麗平，王子健

(河南質(zhì)量工程職業(yè)學(xué)院，河南 平頂山 467000)

0 引 言

橢圓曲線密碼(Elliptic Curve Cryptography, ECC)是于1985年由Koblitz和Miller分別提出的，其安全性是建立在求解橢圓曲線離散對數(shù)問題ECDLP困難性的基礎(chǔ)之上[1-2]。與傳統(tǒng)公鑰密碼相比，橢圓曲線密碼算法具有密鑰長度短、安全性能高、計算量小、處理速度快、存儲空間占用少、帶寬要求低等優(yōu)點(diǎn)，所以橢圓曲線密碼算法當(dāng)前廣泛應(yīng)用于各種存儲受限的環(huán)境中。橢圓曲線密碼中最基本的運(yùn)算是標(biāo)量乘法運(yùn)算，其也是提高橢圓曲線密碼效率的關(guān)鍵運(yùn)算。為有效提高橢圓曲線密碼運(yùn)算效率，國內(nèi)外研究人員也提出了許多提高標(biāo)量乘運(yùn)算效率的方案[3-4]。其中，經(jīng)典的橢圓曲線密碼標(biāo)量乘算法有二進(jìn)制標(biāo)量乘算法、NAF標(biāo)量乘快速算法和基于窗口的NAF標(biāo)量乘快速算法等。橢圓曲線密碼標(biāo)量乘法運(yùn)算是指已知域內(nèi)一整數(shù)k與橢圓曲線上一點(diǎn)P，求解橢圓曲線上另一點(diǎn)Q=kP的運(yùn)算。在具體運(yùn)算執(zhí)行過程中，標(biāo)量乘法運(yùn)算是按照一定的編碼方法掃描標(biāo)量k，然后通過不斷調(diào)用點(diǎn)加運(yùn)算與倍點(diǎn)運(yùn)算來實(shí)現(xiàn)的，而點(diǎn)加運(yùn)算與倍點(diǎn)運(yùn)算則是通過不斷調(diào)用有限域加減法與乘法來完成的。由于大多數(shù)用于提高標(biāo)量乘法運(yùn)算的改進(jìn)方法都是側(cè)重考慮性能，甚至是通過犧牲存儲空間來換取高運(yùn)算效率，使得各種提出的改進(jìn)算法的應(yīng)用受到了限制[5-6]。為有效減少標(biāo)量乘法運(yùn)算的存儲空間，給出了一種基于彼此相反型編碼的標(biāo)量乘算法(Scalar Multiplication algorithm based on Mutual Opposite Form coding, SMMOF)。該算法采用彼此相反型編碼方式對標(biāo)量進(jìn)行重新編碼來實(shí)現(xiàn)標(biāo)量乘法運(yùn)算，而且在滿足約束條件的前提下通過盡可能充分利用SRAM空間可以有效降低IP的面積。與從右向左NAF編碼的標(biāo)量乘算法相比，所給SMMOF算法在保持原有性能的情況下，其IP面積縮減了10%左右。

1 傳統(tǒng)標(biāo)量乘算法分析

經(jīng)典的橢圓曲線密碼標(biāo)量乘算法有平方-乘法標(biāo)量乘算法、NAF編碼標(biāo)量乘算法與基于窗口的NAF標(biāo)量乘算法等。下面從存儲空間和性能兩方面對這三種算法進(jìn)行分析。

1.1 平方-乘法標(biāo)量乘算法

平方-乘法是橢圓曲線密碼中最基本的標(biāo)量乘算法，主要是將標(biāo)量k采用二進(jìn)制編碼的形式進(jìn)行編碼。其編碼形式如下式(1)所示：

(1)

其中，ki為平方-乘法編碼系數(shù)，且有ki∈{0,1}，n為標(biāo)量的二進(jìn)制編碼長度。按照從左向右的掃描方向，則有基于平方-乘法的標(biāo)量乘算法如算法1所示。

算法1 從左向右基于平方-乘法的標(biāo)量乘算法

輸入：標(biāo)量k，橢圓曲線上一點(diǎn)P；

輸出：Q=kP。

1. 令Q=O；

2. 計算標(biāo)量k的二進(jìn)制編碼k=(kn-1,kn-2,…,ki,…,k1,k0)2；

3. 對于i從n-1到0，則重復(fù)執(zhí)行：

3.1Q=2Q;

3.2 如果ki=1，則有Q=Q+P；

4. 返回Q。

在執(zhí)行效率方面，標(biāo)量k的二進(jìn)制表示中比特位為1的期望值是n/2，則算法1的運(yùn)算量為nD+(n/2)A。由于算法1在混合坐標(biāo)系下的效率更高，所以采用混合坐標(biāo)計算算法1的運(yùn)算量。令M表示模乘運(yùn)算，S表示模平方運(yùn)算，且有S≈0.8M。則可知算法1的運(yùn)算量為n·(4M+6S)+(n/2)·(9M+3S)=14.5nM。在存儲空間方面，算法1只需存儲坐標(biāo)即可。

1.2 NAF算法

二元非相鄰形式(Non-adjacent Form, NAF)[7]編碼是指在標(biāo)量k的二進(jìn)制序列中的每個位包含0、1和-1三種形式，且不會有相鄰的非零元素出現(xiàn)。其具體編碼形式如下式(2)所示：

(1)

其中，ki為NAF編碼系數(shù)，且有ki∈{-1,0,1}以及km-1≠0，m為NAF編碼長度。按照從左向右的掃描方向，則有基于NAF編碼的標(biāo)量乘算法如算法2所示。

算法2 從左向右基于NAF的標(biāo)量乘算法

輸入：標(biāo)量k，橢圓曲線上一點(diǎn)P；

輸出：Q=kP。

1. 令Q=P；

2. 計算h=3k=(hm-1,hm-2,…,h1,h0)，其中hm-1=1。將標(biāo)量k也寫成二進(jìn)制編碼形式k=(km-1,…,ki,…,k1,k0)；

3. 對于i從m-2到0，則重復(fù)執(zhí)行：

3.1Q=2Q；

3.2 如果hi=1且ki=0，則有Q=Q+P；

3.3 如果hi=0且ki=1，則有Q=Q-P；

4. 返回Q。

在執(zhí)行效率方面，標(biāo)量k的NAF編碼長度最多比二進(jìn)制編碼長度多1位，但NAF編碼中平均非零個數(shù)約為1/3。則可知算法2的運(yùn)算量為m·(4M+6S)+(m/3)·(9M+3S)=12.6mM。在存儲空間方面，算法2比算法1需要多存儲一個參數(shù)h=3k。

1.3 NAFw算法

基于窗口的NAF編碼(NAFw)[8]標(biāo)量乘算法是NAF編碼標(biāo)量乘算法的改進(jìn)算法，主要是利用預(yù)計算來提供標(biāo)量乘法運(yùn)算的速度。令窗口寬度w是正整數(shù)，則有NAFw編碼表示形式如下式(3)所示：

(3)

其中，|ki|<2w-1為NAFw編碼系數(shù)且為奇數(shù)，任何連續(xù)的w個位中最多有1位非零，l為NAFw編碼長度。按照從左向右的掃描方向，則有基于NAFw編碼的標(biāo)量乘算法如算法3所示。

算法3 從左到右基于NAFw編碼的標(biāo)量乘算法

輸入：標(biāo)量k，橢圓曲線上一點(diǎn)P；

輸出：Q=kP。

1. 令Q=O；

2. 計算標(biāo)量k的NAFw編碼k=(km-1,…,ki,…,k1,k0)NAFw；

3. 預(yù)計算Pi=iP；//其中，i∈{1,3,5,…,2w-1-1}

4. 對于i從l-1到0，則重復(fù)執(zhí)行：

4.1Q=2Q；

4.2 如果ki>0，則有Q=Q+Pki；

4.3 如果ki<0，則有Q=Q-P-ki；

4. 返回Q。

在執(zhí)行效率方面，標(biāo)量k的NAFw編碼中平均非零個數(shù)約為1/(w+1)。則可知算法2的運(yùn)算量為(l+1)·(4M+6S)+((2w-2-1)+l/(w+1))·(9M+3S)=20.2((2w-2+l)+l/(w+1))M。在存儲空間方面，算法3除了需多存儲一個參數(shù)NAFw(k)，還需要多存儲2w-2個預(yù)計算值?；贜AFw編碼的標(biāo)量乘算法是以額外的存儲空間來換取執(zhí)行效率的提高，不適用于存儲空間受限的密碼設(shè)備中。

2 SMMOF算法設(shè)計

彼此相反型編碼(Mutual Opposite Form, MOF)[9]的定義包括三個方面特點(diǎn)：(1) MOF編碼的最高非零比特為1；(2) MOF編碼除最低非零比特位外，中間比特位的形式為(x0)后接符號與x符號相反的非零比特，或者為(0x)后接與x符號相同的非零比特，不考慮(x0)或(0x)后出現(xiàn)0的情況，其中|x|=1；(3) MOF編碼的最低非零比特可能為最后一個比特。則有基于MOF編碼的標(biāo)量乘算法如算法4所示。

算法4 基于MOF編碼的標(biāo)量乘算法

輸入：標(biāo)量k，橢圓曲線上一點(diǎn)P；

輸出：Q=kP。

1. 計算標(biāo)量k的MOF編碼MOF(k)=(kt-1,kt,…,ki,…,k1,k0)；

2. 從MOF編碼最高位掃描標(biāo)量k，直到找到非零比特記為i；

3. 如果k[i-1]=0，則有Q=P，i=i-2；

如果k[i-1]=1，則有Q=2P，i=i-2；

4. 對于i≥1時，則執(zhí)行：

4.1 如果k[i]=k[i-1]，則有Q=2Q，i=i-1；

4.2 如果k[i]≠k[i-1]且(k[i],k[i-2])=(1,1)，則有Q=2Q，Q=2Q，Q=Q-P，i=i-2；

4.3 如果k[i]≠k[i-1]且(k[i],k[i-2])=(1,0)，則有Q=2Q，Q=Q-P，Q=2Q，i=i-2；

4.4 如果k[i]≠k[i-1]且(k[i],k[i-2])=(0,1)，則有Q=2Q，Q=Q+P，Q=2Q，i=i-2；

4.5 如果k[i]≠k[i-1]且(k[i],k[i-2])=(0,0)，則有Q=2Q，Q=2Q，Q=Q+P，i=i-2；

5. 如果i=0且k[i]=0，則有Q=2Q；

如果i=0且k[i]=1，則有Q=2Q，Q=Q-P；

6. 返回Q。

標(biāo)量k的MOF編碼長度最多比二進(jìn)制編碼長度多1位，且其平均非零個數(shù)約為1/3，可見其繼承了NAF編碼的優(yōu)良性質(zhì)。由于基于MOF編碼的標(biāo)量乘算法可以從左向右動態(tài)生成，所以可以省去存儲標(biāo)量編碼的存儲空間。在執(zhí)行效率方面，算法4與算法2相當(dāng)。在存儲空間方面，算法4不需要額外的存儲空間，與算法1基本相當(dāng)。

3 SMMOF算法實(shí)現(xiàn)

若要達(dá)到最大降低存儲開銷的目的，則要使標(biāo)量乘算法與操作數(shù)放置策略很好配合。算法4所給的SMMOF標(biāo)量乘算法可以很好地減小存儲空間，可以較好地用于存儲空間受限的移動設(shè)備中，具體實(shí)現(xiàn)框架如圖1所示。

圖1 所給SMMOF標(biāo)量乘算法實(shí)現(xiàn)框架圖

其中，MOF編碼輸出模塊主要是從左向右輸出標(biāo)量k的每一位比特，標(biāo)量乘法運(yùn)算狀態(tài)機(jī)根據(jù)輸入的比特產(chǎn)生相應(yīng)的控制信號來調(diào)用倍點(diǎn)運(yùn)算狀態(tài)機(jī)與點(diǎn)加運(yùn)算狀態(tài)機(jī)，最后倍點(diǎn)運(yùn)算狀態(tài)機(jī)與點(diǎn)加運(yùn)算狀態(tài)機(jī)將計算結(jié)果反饋到標(biāo)量乘法運(yùn)算狀態(tài)機(jī)。由于橢圓曲線密碼標(biāo)量乘法運(yùn)算中的操作數(shù)包括坐標(biāo)點(diǎn)、臨時變量曲線參數(shù)等很多且均為很大的數(shù)，所以為減少面積開銷，采用SRAM存放這些操作數(shù)。然而，由于SRAM在一個周期內(nèi)僅能讀取或?qū)懭胍粋€字，所以為了不影響底層域模塊的執(zhí)行效率，應(yīng)把需要同時存取的操作數(shù)存放在不同的SRAM中。標(biāo)量乘算法底層域模塊對于操作數(shù)的放置主要包括如下兩個方面約束：(1) 模加減運(yùn)算A+B=DmodN，其中A,B,D,N存放在不同的SRAM中，但兩個操作數(shù)相同或是某一操作數(shù)為N的除外；(2) 模乘運(yùn)算A×B=TmodN，其中模乘器為二級流水線實(shí)現(xiàn)，要求其同時能對T進(jìn)行讀寫，A,B,T存放在不同的SRAM中，但兩個操作數(shù)相同的除外。因此，采用四塊56×32的單口SRAM與一塊24×32的雙口SRAM。其中，SRAM的操作數(shù)放置策略如表1所示。

表1 SRAM的操作數(shù)放置策略

在操作數(shù)放置策略中，將每一塊單口SRAM分成3個部分，每一部分用來存放一個大數(shù)，而雙口SRAM作為整體存放一個大數(shù)。其中，a與N為曲線參數(shù)，k為標(biāo)量，Px與Py為橢圓曲線某點(diǎn)坐標(biāo)，這些參數(shù)是在計算前必須向ECC IP輸入的參數(shù)。Const為點(diǎn)加運(yùn)算中需用到的一個重要參數(shù)，其取值對于固定曲線而言是不變的，所以可將其作為常量預(yù)先計算出來；R2為點(diǎn)加運(yùn)算中用到的一個重要參數(shù)，但由于其僅用于預(yù)計算，因而可在后面運(yùn)算中提前釋放存儲空間用于存放其他臨時變量。Sx、Sy與Sz主要是用于存放最后標(biāo)量乘法運(yùn)算的結(jié)果。tmp0專門用于存放模乘運(yùn)算的臨時結(jié)果T，其他tmp主要都是用于存放倍點(diǎn)運(yùn)算與點(diǎn)加運(yùn)算中的臨時變量。

4 算法性能分析

在素數(shù)域ECCIP中采用所給SMMOF標(biāo)量乘算法以及從右向左的NAF編碼標(biāo)量乘算法[10]，且操作數(shù)的放置符合約束條件，然后比較其IP的性能和占用面積。下面表2給出了IP運(yùn)行頻率在100 M赫茲時，所給SMMOF標(biāo)量乘算法與從右向左的NAF編碼標(biāo)量乘算法在不同NIST橢圓曲線下的標(biāo)量乘法運(yùn)算的性能。

表2 100M赫茲時NAF編碼標(biāo)量乘與所給SMMOF標(biāo)量乘的執(zhí)行效率比較(次/s)

由表2可以看出，采用所給SMMOF標(biāo)量乘算法的IP基本能夠保持原來的性能，甚至是優(yōu)于基于從右向左的NAF編碼標(biāo)量乘算法的IP性能?；赟MIC 0.18 μm工藝，100 M赫茲頻率，采用Synopsys dc對所給SMMOF標(biāo)量乘算法及基于從右向左的NAF編碼標(biāo)量乘算法的IP進(jìn)行綜合。基于從右向左的NAF編碼標(biāo)量乘算法IP的面積為95k門，其中SRAM需要52k門左右；所給SMMOF標(biāo)量乘算法IP的面積為86k門，其中SRAM需要45k門左右。由此可見，采用所給SMMOF標(biāo)量乘算法IP的面積要比基于從右向左的NAF編碼標(biāo)量乘算法IP的面積減小了約10%。因此，所給SMMOF標(biāo)量乘算法可以在不犧牲性能的前提下有效縮減IP面積，可很好地應(yīng)用在資源受限的密碼設(shè)備中。

5 結(jié) 語

橢圓曲線密碼算法是應(yīng)用最為廣泛的公鑰密碼算法之一，其中標(biāo)量乘法運(yùn)算的性能是影響其應(yīng)用的關(guān)鍵運(yùn)算。為有效降低標(biāo)量乘法運(yùn)算的存儲空間，給出了一種基于MOF編碼的標(biāo)量乘算法。所給SMMOF標(biāo)量乘算法主要是利用MOF編碼對標(biāo)量進(jìn)行重新編碼，可以動態(tài)地實(shí)現(xiàn)從左向右的標(biāo)量乘算法，與基于NAF編碼標(biāo)量乘算法相比具有大致相當(dāng)?shù)膱?zhí)行效率，與基于平方-乘法的標(biāo)量乘算法相比具有基本類似的存儲空間。所給SMMOF算法可以在不犧牲性能的前提下有效降低存儲空間。操作數(shù)存放策略是在滿足約束條件的前提下盡可能充分利用全部SRAM空間，通過比較采用從右向左的NAF標(biāo)量乘算法IP與采用所給SMMOF標(biāo)量乘算法IP的性能和面積，可以看出采用所給SMMOF標(biāo)量乘算法IP的面積比采用從右向左的NAF標(biāo)量乘算法IP的面積減少了10%左右，同時還能夠保持與從右向左的NAF標(biāo)量乘算法相當(dāng)?shù)男阅?。因此，所給SMMOF算法可很好地應(yīng)用在資源受限的密碼設(shè)備中，具有較好理論研究價值和實(shí)際推廣應(yīng)用價值。