一種靈活的橢圓曲線密碼并行化方法

鄔可可,黃國偉,孔令晶

(深圳信息職業(yè)技術學院計算機學院,廣東 深圳 518172)

0 引 言

1980年代中期，Miller[1]和Koblitz[2]分別獨立地提出了橢圓曲線密碼體制(Elliptic Curve Cryptosystems, ECC)。相對于其它的公鑰密碼體制，ECC只需較短的私鑰就可以達到較高的安全級別，所以，近年來ECC受到廣泛關注。在ECC中，標量乘dP是最主要且最耗時的操作。通常，標量乘采用逐比特的二進制方法來計算[3]。給定一個標量d和一個橢圓曲線點P，一個標量乘是由一系列的P點的點加(A)和點倍(D)操作完成，其運行的軌跡依賴于標量d的二進制比特表達式。該標量乘結構包括3個操作級別：標量乘的算法級別、點的算術級別和域的算術級別。本文專注于使用標量乘的算法級別來加速標量乘的計算。由于逐比特的串行操作，使得它的操作時間相對較長，對于標量d(比特長度為k)，二進制方法的時間復雜度達到了(k/2)A+kD。為進一步加速標量乘，各類二進制方法的變形相繼被提出，如各類快速的標量乘方法如NAF方法、窗口NAF方法，以及滑動窗口方法等[4]。

然而，這些串行的標量乘方法已不能適應于日益普及的高性能并行計算系統(tǒng)。為適應高性能系統(tǒng)，并行的標量乘方法是迫切需要的，一些并行的標量乘方法也被提出。文獻[5-6]介紹了基于SIMD處理器結構的高效并行點操作，基于2個或3個并行操作，采用改進的雅可比坐標(X,Y,Z,Z2)來開發(fā)快速并行表達式。文獻[7-8]提出了雙處理器架構的表達式。文獻[9-12]介紹了替換乘方法，它允許更高效的優(yōu)先并行操作的開發(fā)，從而能并行執(zhí)行3個或4個操作的快速并行表達式。文獻[13-17]提出了基于點操作的算術級別的并行化，但只適用于2個處理器并行化處理點加和點倍操作。然而，這些方法依賴于點或域的算術級別，只局限于域上的固定數量的平方和乘的并行化，即指令級別并行化，而不是基于任務級別的劃分，故它們大多只能用于固定少數處理器的并行計算系統(tǒng)(通常為2，3或4個處理器的并行處理器系統(tǒng))，因而難以適用于日益普及的大型并行系統(tǒng)。

本文劃分一個任務(標量乘)為若干個相同類型的子任務(子標量乘)，直到這些子問題分布到并行系統(tǒng)的處理器；然后，將這些子問題的解遞歸地整合成原始問題的解。任務的劃分是靈活閉包的，因此，本文提出的并行標量乘方法是靈活的且基于任務級別的并行化(也就是標量乘算法操作級別并行化)，從而能適用于各種規(guī)模的并行計算系統(tǒng)，而不局限于固定數量的處理器。

1 背 景

計算標量乘dP最常用的是經典的二進制方法[3-4]，它是基于標量的二進制展開式d=(dkdk-1…d2d1)2，其中dk是最高有效位(MSB)，d1是最低有效位(LSB)，k是標量的比特數(即標量長度)。二進制方法有2種實現版本，一種是從標量的LSB到MSB掃描標量，另一種是從標量的MSB到LSB掃描標量，例如后者的計算過程如下：

算法1Binary Method

輸入：d=(dkdk-1…d2d1), P∈E(Fq)

輸出：dP

Q=O;

for i from k to 1 do /*從 MSB到LSB掃描d */

{

Q=2Q; /*DBL*/

if(di=1) then Q=Q+P; /*ADD*/

}

return(Q);

在二進制比特串d中，di=1的概率為50%，也就是算法1以50%的概率執(zhí)行點加操作{Q=Q+P;}，也就是大約k/2次的ADD操作加上k次的DBL操作，記為(k/2)A+kD。

2 提出的劃分與整合模型

在對本文的技術方案作進一步說明之前，首先給出如下的劃分與整合模型：

定義1設x,y是正整數，|y|表示y的二進制比特長度。定義如下函數：

f(x,y)=2(|y|)·x+y

(1)

根據定義1，很容易得出如下引理。

(2)

(3)

為了更好地描述從各個子標量乘整合成最終標量乘的計算過程，根據引理1，可以推導出如下的定理：

(4)

證明：根據定義1和引理1，有如下等式成立：

(5)

在等式(5)的等號兩邊都乘以一個任意的橢圓曲線點P，可以推導出如下的等式成立：

(6)

根據定理1，可以遞歸地并行計算2n個橢圓曲線點的每2個相鄰點加，直到計算最后2個點的點加運算。

3 提出的并行化方法

首先根據劃分與整合模型，給出標量乘并行化的步驟，最后給出一種靈活的并行化標量乘方法。

3.1 并行化步驟

基于上述劃分與整合模型，標量乘并行化步驟如下：

d=(dkdk-1…d2d1)2

(7)

2)由此標量乘dP被劃分成2n個子標量乘，且這些子標量乘可由二進制方法實現，劃分的過程如下：

(8)

3)兩兩遞歸地計算這2n個橢圓曲線點的點加，直到計算最后2個點的點加，這個過程叫橢圓曲線點的整合過程。根據定理1，這2n個橢圓曲線點的整合過程為：

…

(9)

整合過程如圖2所示。

圖2 橢圓曲線點的整合過程

3.2 并行化方法

根據劃分與整合的并行化步驟，給出一種靈活的標量乘并行化方法，其算法描述如下：

算法2靈活的標量乘并行化方法

輸出：dP

1) Q=O;

2) for j=1 to 2ndo in parallel

3) {/*調用二進制方法計算子標量乘*/

}

4) for i=n-1 downto 0 do

for j=2i+1downto 2 by 2 do in parallel

該方法是劃分一個任務(標量乘)為若干個相同類型的子任務(子標量乘)，直到這些子問題分布到并行系統(tǒng)的各個處理器。然后，這些子問題的解被遞歸地整合成原始問題的解。任務的劃分是靈活閉包的，因此，本文提出的并行標量乘方法是靈活的且基于任務級別的并行化(也就是標量乘算法操作級別并行化)，從而能適用于各種規(guī)模的并行計算系統(tǒng)。

4 復雜度分析

(10)

(11)

既然標量d的比特長度k在一個加密解密環(huán)境中是不變的，那么tp的最小值只取決于標量折半的次數n。根據等式(11)中的項(k/2n+1+n)，定義如下函數：

(12)

對x求g(x)偏導數如下：

(13)

當g′(x)=0，也即x=log k+log (ln 2)-1時，g(x)取得最小值。因此，當xlog k+log (ln 2)-1時，函數g(x)是遞增的。這樣，最優(yōu)的折半次數為：

(14)

為簡單起見，本文取最優(yōu)折半次數nopt=log k-2。因此，可以根據并行計算系統(tǒng)的處理器的數量，來選定最優(yōu)的n值。

當一個并行系統(tǒng)的可利用處理器的數量不少于2n=2log k-2=k/4，得到最優(yōu)的折半次數n=log k-2。根據處理器的數量，給出該算法的時間復雜度tp如下：

(15)

其中p(等于2n)為一個并行系統(tǒng)的可利用處理器的數量。當并行處理器數量p較多時，該算法的時間復雜度遠小于二進制方法的(k/2)A+kD。

例如，如果標量d的比特長度k=256，那么最優(yōu)的折半次數n=log2256-2=6。當p<26時，應該折半標量log2p次，以獲得最優(yōu)的時間復雜度為tpmin=(256/2p+log p)A+256D。然而當p≥26時，應該折半標量6次，以獲得最優(yōu)的時間復雜度tpmin=8A+256D，比經典的二進制方法的128A+256D減少了大約30%的時間復雜度。

5 實例應用

本實例描述本文的快速靈活的標量乘方法的并行化過程。為簡單起見，不妨假設標量d=(38749)10=(1001011101011101)2，則標量d的比特長度為k=16。

5.1 劃分與整合模型

根據等式(14)，最優(yōu)的折半次數nopt=log 16-2=2，則折半標量為2次，如圖3所示。

圖3 折半劃分標量2次

根據引理1，在這4個子標量中兩兩遞歸并行整合子標量，直到整合最后2個子標量為初始的標量d。標量整合模型如圖4所示。

5.2 并行化過程

基于標量折半模型，標量乘dP=38749P能被劃分為4個子標量乘，這4個子標量乘能被并行地調用二進制方法來計算。如下式所示：

(16)

通過調用二進制方法來計算4個子標量乘，得到4個橢圓曲線點的并行輸出。

根據定理1，遞歸并行地計算著4個橢圓曲線點中的每2個點的點加，直到只需計算最后2個點的點加。標量乘dP=38749P的并行化過程如圖5所示。

圖5 標量乘的并行化過程

根據等式(14)，最優(yōu)的時間復雜度為tp=16D+4A。然而，串行的二進制方法達到ts=16D+8A。

6 算法比較

與其他并行系統(tǒng)類似，ECC也能以不同的算法級別來適用于不同的并行架構體系。文獻[5-17]采用FPGA或ASIC等硬件實現，不具有靈活擴展性，因此不適用于大規(guī)模的并行系統(tǒng)。

現有的并行標量乘方法都是基于點或域操作級別的并行化，只適用于固定數量處理器(通常為2,3或4個處理器)的并行系統(tǒng)。本文的標量乘算法級別的并行化方法適應具有靈活數量處理器的并行計算系統(tǒng)，且具有很好的靈活性。各種標量乘并行方法比較如表1所示。

表1 各種標量乘并行方法比較

并行的標量乘方法并行處理器數量靈活性雅可比坐標并行表達式[5?6]2，3否雙處理器架構表達式[7?8]2否替換乘方法[9?12]2，3，4否基于點操作的算術級別的并行化方法[13?17]2否本文提出的并行化方法2n是

本文的方法是基于最高的操作級別，現有的標量乘并行化方法也能集成到本文的方法中來進一步加快運算速度。而現有的標量乘并行化技術大多是基于橢圓曲線點或域操作的并行化。從某種意義上說，本文的方法對現有的并行標量乘方法是兼容的。因此，本文的并行標量乘方法的性能總能優(yōu)于現有的并行標量乘方法。

7 結束語

串行的標量乘方法在并行系統(tǒng)中效率低下，并且現有的并行標量乘方法又局限于固定數量處理器的并行系統(tǒng)。本文提出的快速靈活的橢圓曲線標量乘并行化方法能適應各種規(guī)模的并行系統(tǒng)。既然本文提出的標量乘并行化技術是基于標量乘的算法級別，而不局限于橢圓曲線群結構，因此提出的劃分與整合模型同樣能適用于RSA加密系統(tǒng)的模冪運算的并行化處理。

[1] Miller V S. Use of elliptic curves in cryptography[C]// LNCS Advances in Cryptology. 1985,218:417-426.

[2] Koblitz N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,48(177):203-209.

[3] Knuth D E. The Art of Computer Programming Volume 2: Seminumerical Algorithms[M]. 3rd ed. Beijing: Tsinghua University Press, 2002:461-465.

[4] Hankerson D, Menezes A, Vanstone S. Guide to Elliptic Curve Cryptography[M]. Springer-Verlag, London, 2004:95-123.

[5] Aoki K, Hoshino F, Kobayashi T, et al. Elliptic curve arithmetic using SIMD[C]// Proceedings of International Conference on Information Security. 2001:235-247.

[6] Izu T, Takagi T. Fast elliptic curve multiplications with SIMD operations[C]// Proceedings of International Conference on Information Security. 2002:217-230.

[7] Izu T, Takagi T. A fast parallel elliptic curve multiplication resistant against side channel attacks[C]// Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems. 2002:280-296.

[8] Izu T. Fast elliptic curve multiplication resistant against side channel attacks[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005,88(1):161-171.

[9] Mishra P K. Pipelined computation of scalar multiplication in elliptic curve cryptosystems[C]// Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems. 2004:328-342.

[10] Longa P, Miri A. Fast and flexible elliptic curve point arithmetic over prime fields[J]. IEEE Transactions on Computers, 2008,57(3):289-302.

[11] Al-Otaibi A, Al-Somani T F, Beckett P. Efficient elliptic curve parallel scalar multiplication methods[C]// 2013 8th International Conference on Computer Engineering & Systems(ICCES). 2013:116-123.

[12] Azarderakhsh R, Reyhani-Masoleh A. Parallel and high-speed computations of elliptic curve cryptography using hybrid-double multipliers[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(6):1668-1677.

[13] Bos J W. Low-latency elliptic curve scalar multiplication[J]. International Journal of Parallel Programming, 2012,40(5):532-550.

[14] Realpe-Munoz P C, Velasco-Medina J. High-performance elliptic curve cryptoprocessors over GF(2m) on Koblitz curves[J]. Analog Integrated Circuits and Signal Processing, 2015,85(1):129-138.

[15] Al-Somani T F. High-performance generic-point parallel scalar multiplication[J]. Arabian Journal for Science and Engineering, 2017,42(2):507-512.

[16] Asif S, Kong Yinan. Highly parallel modular multiplier for elliptic curve cryptography in residue number system[J]. Circuits, Systems, and Signal Processing, 2017,36(3):1027-1051.

[17] Oliveira T, Lopez J, Rodriguez-Henriquez F. The Montgomery ladder on binary elliptic curves[J]. Journal of Cryptographic Engineering, 2017,7(4):1-18.