HECC除子標(biāo)量乘并行集群算法設(shè)計

劉海峰 肖超 梁星亮

摘 ?要： 為了加快超橢圓曲線密碼體制（HECC）中除子標(biāo)量乘的運(yùn)算速度，進(jìn)行基于大數(shù)據(jù)技術(shù)的除子標(biāo)量乘并行算法研究。根據(jù)“空間換時間”的策略對除子標(biāo)量乘法常規(guī)方法進(jìn)行改進(jìn)，在任務(wù)規(guī)模為[1016]的條件下，運(yùn)算耗時減少16.28%，提出基于負(fù)載均衡的任務(wù)劃分優(yōu)化方案。此方案分別將Hadoop集群平臺、Spark集群平臺、Spark?GPU集群平臺的并行技術(shù)應(yīng)用于改進(jìn)后的除子標(biāo)量乘算法中，研究并行算法與串行算法的運(yùn)行效率。當(dāng)問題規(guī)模一定時，隨著節(jié)點(diǎn)個數(shù)的增加，不同集群平臺的加速呈上升趨勢，其中Spark?GPU并行算法的增長趨勢最為明顯，當(dāng)節(jié)點(diǎn)個數(shù)為4時，Spark?GPU并行算法的加速比達(dá)到了261.84。通過對比3種集群平臺的并行算法，發(fā)現(xiàn)Spark?GPU可以最有效地縮短運(yùn)算耗時，加快除子標(biāo)量乘法的運(yùn)算速度。

關(guān)鍵詞： 超橢圓曲線密碼體制; 除子標(biāo)量乘; 并行計算; 集群平臺; Spark?GPU; Hadoop

中圖分類號： TN929.52?34; TP393.08 ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）10?0023?04

Design of divisor scalar multiplication parallel clustering algorithm for HECC

LIU Haifeng， ?XIAO Chao， ?LIANG Xingliang

（School of Arts & Sciences， Shaanxi University of Science & Technology， Xian 710021， China）

Abstract： A divisor scalar multiplication parallel algorithm based on the big data technology is studied to speed up the operation rate of the divisor scalar multiplication in the hyperelliptic curve cryptosystem （HECC）. The conventional method of the divisor scalar multiplication is improved according to the "space?for?time" strategy， whose operation time computation is reduced by 16.28% under the condition that the task scale is 1016. A task partition optimization scheme based on load balancing is proposed. The operation efficiencies of the parallel algorithm and serial algorithm are studied by applying the parallel technologies of the Hadoop cluster platform， Spark cluster platform and Spark?GPU cluster platform to the improved divisor scalar multiplication algorithm. When the problem scale is fixed， the acceleration of different cluster platforms emerges in an upward trend with the increase of node quantity， in which the growth trend of the Spark?GPU parallel algorithm is the most obvious， and the speed?up ratio of the Spark?GPU parallel algorithm can reach 261.84 when the node quantity is 4. By comparing the parallel algorithms of three cluster platforms， it is found that the Spark?GPU parallel algorithm can most effectively reduce the operation time consumption and speed up the operation rate of divisor scalar multiplication.

Keywords： HECC; divisor scalar multiplication; parallel calculation; cluster platform; Spark?GPU; Hadoop

0 ?引 ?言

隨著多核時代的到來，并行計算成為提高算法效率的主流技術(shù)之一。Hadoop的計算模型比較簡單，適合數(shù)據(jù)量大但核心計算并不復(fù)雜的處理作業(yè);而對于較復(fù)雜的計算模型，尤其是循環(huán)、迭代任務(wù)的處理效率欠佳。基于內(nèi)存計算的并行計算框架Spark，對于復(fù)雜的大規(guī)模計算任務(wù)實(shí)現(xiàn)輕量級快速處理，可以高效地解決頻繁迭代問題。

在如今的計算機(jī)網(wǎng)絡(luò)環(huán)境下，密碼技術(shù)已經(jīng)成為安全通信的關(guān)鍵手段。1989年，Neal Koblitz首次提出了超橢圓曲線密碼體制（HECC）的理論，作為橢圓曲線密碼體制（ECC）理論的推廣[1]。與ECC相比，HECC安全性高、所需的基域更小，特別適合在受限系統(tǒng)中使用。然而，除子標(biāo)量乘的運(yùn)算速度直接影響HECC的總體實(shí)現(xiàn)效率，成為HECC的“瓶頸”問題[2]。楊怡琳主要對偶特征域上的超橢圓曲線進(jìn)行了深入的研究，推導(dǎo)出了虧格為2的除子二分算法過程[3]。范欣欣從群運(yùn)算的明確公式、標(biāo)量乘算法的角度對影響HECC性能的諸多因素進(jìn)行了優(yōu)化實(shí)現(xiàn)。但基本上都是一些針對除子標(biāo)量乘的理論研究層面的串行算法，而基于集群平臺的并行算法研究卻相對較少。因此，本文分別將Hadoop，Spark以及Spark?GPU的大數(shù)據(jù)并行處理技術(shù)應(yīng)用到HECC的除子標(biāo)量乘運(yùn)算中，研究并行算法與串行算法的運(yùn)行效率。

1 ?超橢圓曲線密碼體制的數(shù)學(xué)理論

設(shè)[Fq]是有限域[Fq]上的一個閉包，則[Fq]上的超橢圓曲線[C]的[Weierstrass]方程為：

[C： y2+h（x）y=f（x）] ? （1）

式中：定義[g]為超橢圓曲線[C]的虧格;[h（x）]是次數(shù)不大于[g]的多項(xiàng)式;[f（x）]是次數(shù)為[2g+1]的首一多項(xiàng)式，且[h（x），f（x）∈Fq]。特別地，當(dāng)[g=1]時，超橢圓曲線[C]退化為橢圓曲線[4]。

一個除子[D]由曲線[C]上若干點(diǎn)求和取得：

[D=P∈CmpP， mp∈Z] ? （2）

設(shè)[Dn]表示[C]上所有除子的集合，則[Dn]在式（3）規(guī)則下形成一個加法群[5]。

[P∈CmpP+P∈CnpP=P∈C（mp+np）P] ? （3）

曲線[C]上的[Jacobian]商群記為[J（F）=D0P]，商群上的除子標(biāo)量乘，即

[mD=D+D+…+Dm] ?（4）

2 ?除子標(biāo)量乘算法改進(jìn)方案

在超橢圓曲線密碼體制中，密碼學(xué)的核心問題是除子標(biāo)量乘問題，直接影響整個密碼體制的實(shí)現(xiàn)效率[6]。采用常規(guī)循環(huán)計算除子標(biāo)量乘，需要進(jìn)行[m]次除子加法，與[m]聯(lián)系密切。當(dāng)[m]為一個大整數(shù)時，計算效率低。因此，需要進(jìn)行改進(jìn)。將[m]描述為[s]進(jìn)制的表示形式。

[m=an-1sn-1+an-2sn-2+…+a1m+a0] ? （5）

為了減少選取除子倍加算法的次數(shù)，選擇適當(dāng)?shù)恼麛?shù)[k≥1]，令[s=2k]，[n=kN]，則除子標(biāo)量乘[mD]表示為：

[mD=i=1N-1（ai2ki）D ? ? ?=2k（2k…（2k（O+aN-1D）+aN-2D）…+a1D）+a0D] ? ? ? ? ? ? ? ? ? ? ? ? （6）

則迭代格式為：

[T（i）=2kT（i-1）+aN-iD， ?i=1，2，…，NT（0）=O] ?（7）

對于[2kT（i-1）]，每一輪需要[k]次除子倍加運(yùn)算;對于[aN-iD]，首先將[aN-i]表示為[p]位二進(jìn)制形式[aN-i=（bpbp-1…b1）2]，則當(dāng)[aN-i≠0]時，每一輪需要[k]次除子倍點(diǎn)運(yùn)算，需要[aN-i]次除子加法運(yùn)算。由于每一輪需要重復(fù)計算[aN-iD]，消耗了大量的計算時間，需要進(jìn)一步改進(jìn)。

因?yàn)閇aN-i∈{0，1，2，…，2k-1}]，需要計算[2D，][3D，…，（2k-1）D]。其中，[（i+1）D=iD+D，i=1，2，…，2k-2]。采用“以空間換時間”的基本思想，將[2D，3D，…，（2k-1）D]的計算結(jié)果預(yù)先存儲在[U[1]，U[2]，…，U[2k-1]]中，減少時間開銷。

改進(jìn)后的算法共需要[2k+nk+n-1]次除子加法運(yùn)算，需要[n]次除子倍加運(yùn)算。研究發(fā)現(xiàn)，一次除子倍加耗時約為除子加法的[12]，則時間復(fù)雜度為[f（k）=2k+nk+32n-1]。改進(jìn)后算法的運(yùn)算量[f（k）]遠(yuǎn)遠(yuǎn)小于常規(guī)循環(huán)的計算量[m]，說明改進(jìn)后算法大大減小了計算量。對[f（k）]求導(dǎo)，令[f′（k）=2kln 2-nk2=0]，得到[n=2kk2ln 2]。可以看出，當(dāng)加密密鑰的長度[n]為48～96位之間時，[k=3]時，最接近50，算法的效率達(dá)到最佳。

3 ?除子標(biāo)量乘并行算法設(shè)計

3.1 ?基于負(fù)載均衡的子任務(wù)劃分方案優(yōu)化設(shè)計

為達(dá)到負(fù)載均衡，計算[mD]時，將大整數(shù)[m]均勻分割成[p]個子任務(wù)。假設(shè)[subtaski]代表劃分后的子任務(wù)規(guī)模，前[p-1]個子任務(wù)規(guī)模均為[x]，[subtaskp]為[y]，將最優(yōu)方案表示為[x*，y*]，則需要求解如下整數(shù)優(yōu)化問題：

[minx-y（p-1）x+y=mx，y∈Z*] ? （8）

通過求解該優(yōu)化問題，得到改進(jìn)后的劃分方案為：[x*=mp+1， ?mp-mp≥0.5mp， ? ? ? ? 其他] ? ? （9）

[y*=m-（p-1）x*] ? （10）

3.2 ?基于Hadoop，Spark，Spark?GPU的除子標(biāo)量乘并行化設(shè)計

利用Hadoop并行集群平臺進(jìn)行除子標(biāo)量乘算法并行化設(shè)計，主要流程如下：

1） 從HDFS上獲取大整數(shù)[m]、除子[D];

2） 初始化除子標(biāo)量乘的存儲單元T，創(chuàng)建用于計算除子標(biāo)量乘的工作單元DSMJob;采用基于負(fù)載均衡的子任務(wù)劃分優(yōu)化方案對大整數(shù)[m]進(jìn)行劃分，并且將劃分后的子任務(wù)[（subtaski）D]分發(fā)給[Mapi];

3） [Mapi]根據(jù)改進(jìn)后的除子標(biāo)量乘算法，對于子任務(wù)進(jìn)行計算：

① 已知子任務(wù)的加密密鑰長度[n]，根據(jù)[n=2kk2ln 2]，估計得到最佳參數(shù)[k];

② 將[2D，3D，…，（2k-1）D]的計算結(jié)果預(yù)先存儲在數(shù)組U中;

③ 進(jìn)行計算除子標(biāo)量乘的迭代運(yùn)算，迭代完成后得到[Mapi]的計算結(jié)果[（subtaski）D]。

4） 將計算后的結(jié)果通過Reduce進(jìn)行匯總合并，得到最終需要的除子標(biāo)量乘算法結(jié)果，即

[mD=T=i=1p（subtaski）D]

利用Spark并行實(shí)現(xiàn)除子標(biāo)量乘，總體上也是采用“Map”和“Reduce”的思想。然而，與Hadoop不同的是，針對所有子任務(wù)，Hadoop與磁盤進(jìn)行多次交互，而Spark在內(nèi)存中對彈性分布式數(shù)據(jù)集RDD進(jìn)行計算，中間不需與磁盤交互[7]。

基于CPU與GPU混合并行計算系統(tǒng)已經(jīng)逐漸成為國內(nèi)外高性能計算領(lǐng)域的熱點(diǎn)研究方向。利用GPU強(qiáng)大的并行處理能力，結(jié)合Spark并行集群平臺，可以大幅度提升計算性能[8]。CPU與GPU混合并行計算框架如圖1所示。

圖1 ?CPU與GPU混合并行計算框架

基于Spark?GPU集群平臺的除子標(biāo)量乘并行算法計算流程如下：

1） CPU根據(jù)計算資源分布情況以及負(fù)載均衡機(jī)制，向各worker節(jié)點(diǎn)分配子任務(wù)。worker節(jié)點(diǎn)接收到程序指令和任務(wù)分配信息后，將操作指令傳遞到GPU，以線程為單位計算除子標(biāo)量乘。每個節(jié)點(diǎn)計算完成后，將計算結(jié)果保存在顯存[9]。

2） 在Spark集群平臺中，顯存的計算結(jié)果以特定的形式轉(zhuǎn)化為RDD數(shù)據(jù)塊，Reduce將所有worker節(jié)點(diǎn)求和匯總。

4 ?實(shí)驗(yàn)設(shè)計與分析

本實(shí)驗(yàn)平臺的集群由1個控制節(jié)點(diǎn)和4臺計算節(jié)點(diǎn)組成，所有節(jié)點(diǎn)配置都相同，有4核CPU（主頻：1.80 GHz）、8 GB內(nèi)存和60 GB硬盤，控制節(jié)點(diǎn)和計算節(jié)點(diǎn)間以速度約為10 Mb/s的10Base?T以太網(wǎng)互聯(lián)。Hadoop的版本為2.6.0，Spark的版本為1.6.1，Hadoop程序使用java編寫，java版本為1.7，Spark程序使用scala編寫，版本為2.10.6。

設(shè)[Cp]是有限域[Fq]上的超橢圓曲線，且[p=1019+51]，超橢圓曲線[C]的表示形式如下：

[C：y2=x5+3 141 592 653 589 793 238x4+ ? ? ? ? ? ?4 626 433 832 795 028 841x3+971 639 937 510 582 097x2+ ? ? ? ? ? ?49 445 923 078 164 062 986x+2 089 986 280 348 253 421]

此曲線的階為：

9 999 999 998 287 192 967 145 227 700 028 166 080

設(shè)[a（x）=x3+x2+2，b（x）=6x2+6x]，則[D=a（x），b（x）∈JCq（Fq）]。為了便于研究不同問題規(guī)模下算法的時間效率，設(shè)置3組計算任務(wù)[miD]，[mi]分別為[104，1010，1016]。分別基于3種不同平臺進(jìn)行并行計算，并行的計算節(jié)點(diǎn)為1 節(jié)點(diǎn)、2 節(jié)點(diǎn)、3 節(jié)點(diǎn)、4 節(jié)點(diǎn)。采用改進(jìn)算法對計算任務(wù)[miD]進(jìn)行測試，記錄運(yùn)行時間。共進(jìn)行4類實(shí)驗(yàn)：

實(shí)驗(yàn)1：基于普通平臺的改進(jìn)算法測試，與常規(guī)算法進(jìn)行對比;

實(shí)驗(yàn)2：基于Hadoop平臺的改進(jìn)算法測試;

實(shí)驗(yàn)3：基于Spark平臺的改進(jìn)算法測試;

實(shí)驗(yàn)4：基于Spark?GPU平臺的改進(jìn)算法測試。

基于普通平臺的改進(jìn)算法與常規(guī)算法的耗時比如圖2所示。

圖2 ?算法改進(jìn)前后的耗時比

觀察圖2發(fā)現(xiàn)，隨著任務(wù)規(guī)模的增加，耗時比逐漸增大，當(dāng)任務(wù)規(guī)模為[1016]時，耗時比達(dá)到了1.195。

以任務(wù)規(guī)模為[1010]的情況為例，研究不同節(jié)點(diǎn)個數(shù)時，3種平臺的加速比隨著節(jié)點(diǎn)個數(shù)的變化趨勢如圖3所示。

圖3 ?不同節(jié)點(diǎn)個數(shù)的加速比

以節(jié)點(diǎn)數(shù)N=2為例，研究不同任務(wù)規(guī)模時，3種平臺的加速比隨著問題規(guī)模的變化趨勢如圖4所示。

圖4 ?不同任務(wù)規(guī)模的加速比

由圖3可知，在相同問題規(guī)模情況下，隨著節(jié)點(diǎn)個數(shù)的增加，不同平臺的加速比也逐漸增加。基于Spark?GPU集群平臺進(jìn)行并行計算時，加速比增長最為明顯。當(dāng)節(jié)點(diǎn)個數(shù)為4時，基于Spark?GPU集群平臺并行算法的加速比達(dá)到了261.84。

由圖4可知，在相同數(shù)量節(jié)點(diǎn)情況下，隨著問題規(guī)模的增長，加速比曲線隨著問題規(guī)模增加逐漸上升。其中，基于Spark?GPU并行算法加速比增長最為明顯。當(dāng)問題規(guī)模為[1016]時，Spark?GPU對應(yīng)的加速比達(dá)到了56.19。

5 ?結(jié) ?論

通過4組實(shí)驗(yàn)，可以得到如下結(jié)論：

1） 根據(jù)改進(jìn)后算法和常規(guī)算法的耗時比，說明改進(jìn)后的算法縮短了計算時間，提高了運(yùn)算效率;

2） 通過研究不同節(jié)點(diǎn)個數(shù)時，3種平臺的加速比隨著節(jié)點(diǎn)個數(shù)的變化趨勢，發(fā)現(xiàn)隨著節(jié)點(diǎn)個數(shù)的增加，不同平臺的加速比也逐漸增加，且基于Spark?GPU平臺的并行算法加速比增長最為明顯;

3） 通過研究不同問題規(guī)模時，3種平臺的加速比隨著問題規(guī)模的變化趨勢，發(fā)現(xiàn)加速比曲線隨著問題規(guī)模增加逐漸上升。

參考文獻(xiàn)

[1] KOBLITZ N. Hyperelliptic cryptosystems [J]. Journal of cryptology， 1989， 1（3）： 139?150.

[2] KOBLITZ N. A family of Jacobians suitable for discrete log cryptosystems [C]// Proceedings of Conference on the Theory and Application of Cryptology. New York： Springer， 1990： 94?99.

[3] 楊怡琳.超橢圓曲線上快速標(biāo)量乘算法研究[D].杭州：杭州電子科技大學(xué)，2014.

YANG Yilin. Research on fast scalar multiplication algorithm on hyperelliptic curves [D]. Hangzhou： Hangzhou Dianzi University， 2014.

[4] 郝艷華，范欣欣，王育民.虧格為3的超橢圓曲線除子加法的并行算法[J].計算機(jī)科學(xué)，2007，34（8）：114?119.

HAO Yanhua， FAN Xinxin， WANG Yumin. Parallelizing explicit formula in Genus 3 hyperelliptic curves [J]. Computer science， 2007， 34（8）： 114?119.

[5] 朱艷蕊.超橢圓曲線標(biāo)量乘快速算法研究[D].成都：西南交通大學(xué)，2013.

ZHU Yanrui. Research on fast algorithm of superelliptic curve scalar multiplication [D]. Chengdu： Southwest Jiaotong University， 2013.

[6] 游林.一類超橢圓曲線上的快速除子標(biāo)量乘[J].電子學(xué)報，2008，36（10）：2049?2054.

YOU Lin. Fast divisor scalar multiplications on a class of hyperelliptic curves [J]. Acta electronica sinica， 2008， 36（10）： 2049?2054.

[7] 李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學(xué)報，2011，39（11）：2635?2642.

LI Jianjiang， CUI Jian， WANG Dan， et al. Survey of MapReduce parallel programming model [J]. Acta electronica sinica， 2011， 39（11）： 2635?2642.

[8] 江小平，李成華，向文，等.K?means聚類算法的MapReduce并行化實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2011，39（z1）：120?124.

JIANG Xiaoping， LI Chenghua， XIANG Wen， et al. Parallel implementing of K?means clustering algorithm using MapReduce programming mode [J]. Journal of Huazhong University of Science and Technology （Natural science）， 2011， 39（S1）： 120?124.

[9] 周情濤，何軍，胡昭華，等.基于GPU的Spark大數(shù)據(jù)技術(shù)在實(shí)驗(yàn)室的開發(fā)應(yīng)用[J].實(shí)驗(yàn)室研究與探索，2017，36（1）：112?116.

ZHOU Qingtao， HE Jun， HU Zhaohua， et al. Department and application of the GPU?based Spark big data technology in laboratory [J]. Research and exploration in laboratory， 2017， 36（1）： 112?116.

[10] 楊冬進(jìn)，婁建安，黃天辰.鋰電池內(nèi)阻測量的電路設(shè)計及其算法仿真[J].電子設(shè)計工程，2017，25（24）：129?133.

YANG Dongjin， LOU Jianan， HUANG Tianchen. The circuit design of lithium battery internal resistance measurement and algorithm simulation [J]. Electronic design engineering， 2017，25（24）： 129?133.