鄔可可,黃國偉,孔令晶

(深圳信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)學(xué)院,廣東 深圳 518172)

0 引 言

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

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

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

1 背 景

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

算法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);

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

2 提出的劃分與整合模型

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

定義1設(shè)x,y是正整數(shù)，|y|表示y的二進(jìn)制比特長度。定義如下函數(shù)：

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

(1)

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

(2)

(3)

為了更好地描述從各個(gè)子標(biāo)量乘整合成最終標(biāo)量乘的計(jì)算過程，根據(jù)引理1，可以推導(dǎo)出如下的定理：

(4)

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

(5)

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

(6)

根據(jù)定理1，可以遞歸地并行計(jì)算2n個(gè)橢圓曲線點(diǎn)的每2個(gè)相鄰點(diǎn)加，直到計(jì)算最后2個(gè)點(diǎn)的點(diǎn)加運(yùn)算。

3 提出的并行化方法

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

3.1 并行化步驟

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

d=(dkdk-1…d2d1)2

(7)

2)由此標(biāo)量乘dP被劃分成2n個(gè)子標(biāo)量乘，且這些子標(biāo)量乘可由二進(jìn)制方法實(shí)現(xiàn)，劃分的過程如下：

(8)

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

…

(9)

整合過程如圖2所示。

圖2 橢圓曲線點(diǎn)的整合過程

3.2 并行化方法

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

算法2靈活的標(biāo)量乘并行化方法

輸出：dP

1) Q=O;

2) for j=1 to 2ndo in parallel

3) {/*調(diào)用二進(jìn)制方法計(jì)算子標(biāo)量乘*/

}

4) for i=n-1 downto 0 do

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

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

4 復(fù)雜度分析

(10)

(11)

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

(12)

對x求g(x)偏導(dǎo)數(shù)如下：

(13)

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

(14)

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

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

(15)

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

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

5 實(shí)例應(yīng)用

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

5.1 劃分與整合模型

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

圖3 折半劃分標(biāo)量2次

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

5.2 并行化過程

基于標(biāo)量折半模型，標(biāo)量乘dP=38749P能被劃分為4個(gè)子標(biāo)量乘，這4個(gè)子標(biāo)量乘能被并行地調(diào)用二進(jìn)制方法來計(jì)算。如下式所示：

(16)

通過調(diào)用二進(jìn)制方法來計(jì)算4個(gè)子標(biāo)量乘，得到4個(gè)橢圓曲線點(diǎn)的并行輸出。

根據(jù)定理1，遞歸并行地計(jì)算著4個(gè)橢圓曲線點(diǎn)中的每2個(gè)點(diǎn)的點(diǎn)加，直到只需計(jì)算最后2個(gè)點(diǎn)的點(diǎn)加。標(biāo)量乘dP=38749P的并行化過程如圖5所示。

圖5 標(biāo)量乘的并行化過程

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

6 算法比較

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

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

表1 各種標(biāo)量乘并行方法比較

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

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

7 結(jié)束語

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

[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.