方寧，曹衛(wèi)兵，倪冬鶴，狄冠東,3

（1. 北京梆梆安全科技有限公司，北京 100091；2. 北京電子技術(shù)應(yīng)用研究所，北京100091；3. 青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266071）

1 引言

近年來，移動(dòng)智能設(shè)備的普及和移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展為人們的工作和生活帶來了極大便利，與此同時(shí)，越來越多的個(gè)人信息甚至個(gè)人隱私不可避免地在網(wǎng)絡(luò)交互過程中被傳輸、處理、存儲(chǔ)。由于計(jì)算機(jī)網(wǎng)絡(luò)的開放性、復(fù)雜性和多樣性，移動(dòng)終端面臨的安全風(fēng)險(xiǎn)種類繁多而且不斷更新。

密碼技術(shù)是信息安全的核心和關(guān)鍵技術(shù)，能夠?yàn)楸Ｗo(hù)網(wǎng)絡(luò)空間信息安全提供有效的機(jī)制。其中，非對(duì)稱密碼技術(shù)主要應(yīng)用于身份認(rèn)證、完整性保護(hù)和數(shù)字簽名等場(chǎng)景，在移動(dòng)終端中的使用非常普遍，因?yàn)樗婕傲艘苿?dòng)互聯(lián)網(wǎng)應(yīng)用中絕大多數(shù)安全需求的解決方案。與對(duì)稱密碼體制相比，非對(duì)稱密碼體制具有密鑰管理高效等諸多優(yōu)勢(shì)，但是速度相對(duì)較慢，當(dāng)應(yīng)用于數(shù)據(jù)加密場(chǎng)景時(shí)，適合于數(shù)據(jù)量較小的加密操作。而在移動(dòng)互聯(lián)網(wǎng)應(yīng)用場(chǎng)景中，密碼運(yùn)算的執(zhí)行速度直接決定了終端用戶的使用體驗(yàn)。如何在保證安全性的同時(shí)，進(jìn)一步提高密碼運(yùn)算的執(zhí)行效率和執(zhí)行速度，縮短用戶操作相應(yīng)時(shí)間，一直以來都是移動(dòng)應(yīng)用設(shè)計(jì)與開發(fā)人員研究的熱點(diǎn)問題[1]。在不同的軟硬件體系結(jié)構(gòu)中，可以采用特殊的設(shè)計(jì)方法，利用體系結(jié)構(gòu)特點(diǎn)實(shí)現(xiàn)多種運(yùn)算的加速操作。本文方案利用Android平臺(tái)中的并行運(yùn)算機(jī)制，研究橢圓曲線密碼基本運(yùn)算的加速和優(yōu)化方法。

橢圓曲線密碼是一類常見的非對(duì)稱密碼技術(shù)，具有密鑰長(zhǎng)度較小、運(yùn)算速度快等優(yōu)勢(shì)，被廣泛應(yīng)用在嵌入式設(shè)備、移動(dòng)終端和其他應(yīng)用場(chǎng)景中[2]。橢圓曲線密碼通?；谟邢抻蛑性貥?gòu)建，其基本運(yùn)算包括有限域中元素的加法、乘法、求逆等。而這些運(yùn)算需要以大整數(shù)的加法、乘法、模運(yùn)算作為基礎(chǔ)運(yùn)算。一次橢圓曲線上典型運(yùn)算的實(shí)現(xiàn)，需要調(diào)用多至幾十次的大整數(shù)運(yùn)算[3]。因此，提高大整數(shù)運(yùn)算的執(zhí)行速度，對(duì)于提高橢圓曲線密碼的執(zhí)行效率具有非常重要的意義。此外，大整數(shù)運(yùn)算還具有很多數(shù)值計(jì)算的應(yīng)用，對(duì)于以大整數(shù)運(yùn)算作為基礎(chǔ)的應(yīng)用，尋找快速有效的大整數(shù)計(jì)算方法也非常必要[4]。

大整數(shù)通常指的是數(shù)值超過了程序設(shè)計(jì)語言中一般整數(shù)類型變量表示范圍的整數(shù)，位數(shù)一般在幾百或幾千位。對(duì)于此類數(shù)值的運(yùn)算，需要另外設(shè)計(jì)其表示方法和計(jì)算方法。Java[5]和微軟.NET[6]框架中都有相應(yīng)的大整數(shù)類，用以完成上述任務(wù)。大整數(shù)的各種運(yùn)算中，加法和減法相對(duì)簡(jiǎn)單，乘法最為困難，模運(yùn)算可以轉(zhuǎn)化為乘法實(shí)現(xiàn)[7]。因此，本文針對(duì)大整數(shù)的乘法運(yùn)算這一主要問題，利用Android平臺(tái)的并行運(yùn)算機(jī)制，設(shè)計(jì)了一種高效快速的計(jì)算實(shí)現(xiàn)方法。

目前的大整數(shù)乘法計(jì)算方法中，大部分是基于串行算法的。在 Android平臺(tái)上采用這些方法時(shí)，利用的是CPU的計(jì)算資源?，F(xiàn)有的大整數(shù)乘法并行計(jì)算技術(shù)主要利用的是 CUDA（compute unified device architecture）框架[8]。該框架是NVIDIA推出的運(yùn)算平臺(tái)，使設(shè)備中的圖形處理器（GPU，graphics processing unit）能夠解決復(fù)雜的計(jì)算問題。Android系統(tǒng)不支持CUDA框架，因此無法使用現(xiàn)有技術(shù)。本文使用的是Android平臺(tái)的RenderScript編程框架[9]。RenderScript是一套Android平臺(tái)上運(yùn)行3D渲染和處理密集型計(jì)算任務(wù)的編程框架，主要面向的是具有并行數(shù)據(jù)處理特點(diǎn)的計(jì)算任務(wù)，可以將計(jì)算任務(wù)并行化，將其分配給移動(dòng)設(shè)備上所有可用的處理器單元，如多核的CPU、GPU等。RenderScript編程框架具有極高的設(shè)備無關(guān)性和可移植性，能夠在運(yùn)行Android平臺(tái)的任何移動(dòng)設(shè)備中部署使用。Android系統(tǒng)從3.0版本開始集成了RenderScript，從4.3版本開始將其作為系統(tǒng)中唯一的并行計(jì)算編程框架。

2 大整數(shù)乘法并行計(jì)算方案

GPU的優(yōu)勢(shì)在于GPU的眾核架構(gòu)支持大量的并發(fā)線程同時(shí)執(zhí)行不同輸入的相同指令，因此并行算法的設(shè)計(jì)思路是：將復(fù)雜的大數(shù)乘法問題分割成若干子問題，分配給GPU不同的核心并行處理，最后整合所有核心的計(jì)算結(jié)果得到最終結(jié)果。并行計(jì)算方案設(shè)計(jì)的關(guān)鍵問題是子任務(wù)的劃分。劃分方法既要分解串行計(jì)算過程中最耗時(shí)的主要計(jì)算任務(wù)，同時(shí)還要保證所有子任務(wù)能夠獨(dú)立、互不影響地被執(zhí)行。本文將大數(shù)乘法算法分為對(duì)應(yīng)相乘、斜向相加、進(jìn)位整合3個(gè)步驟，其中包含兩次子任務(wù)劃分。

2.1 存儲(chǔ)結(jié)構(gòu)

首先需要設(shè)計(jì)能夠支持并行計(jì)算子任務(wù)劃分的存儲(chǔ)結(jié)構(gòu)。為了完成并行處理的運(yùn)算，本文采用線性存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)乘法運(yùn)算的因子、中間結(jié)果和最終計(jì)算結(jié)果。與傳統(tǒng)方案類似，仍然使用整數(shù)數(shù)組存儲(chǔ)大整數(shù)[10]。對(duì)于參與運(yùn)算的兩個(gè)操作數(shù)A和B，使用數(shù)組A[]和B[]按照從高位到低位的順序分別對(duì)其進(jìn)行存儲(chǔ)，用lenA和lenB分別表示數(shù)組長(zhǎng)度。構(gòu)造二維數(shù)組map[lenA＋1][lenB＋1]存放對(duì)應(yīng)乘法運(yùn)算的中間結(jié)果，其中下標(biāo)為0的行和列元素作為預(yù)留元素以便處理可能出現(xiàn)的進(jìn)位。使用數(shù)組ans[]保存最終的乘法運(yùn)算結(jié)果，其長(zhǎng)度計(jì)為lenAns。

2.2 對(duì)應(yīng)相乘

按照上述存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)，使用式(1)即可完成乘法運(yùn)算。

將二維數(shù)組視為矩陣對(duì)象，其中元素的值與操作數(shù)的對(duì)應(yīng)關(guān)系如圖1所示。

圖1 按單元相乘結(jié)果矩陣

在串行計(jì)算中，要計(jì)算得到上述矩陣結(jié)果需要進(jìn)行l(wèi)enA×lenB次計(jì)算，而在并行計(jì)算機(jī)制中的計(jì)算次數(shù)為

2.3 斜向相加

在map數(shù)組的基礎(chǔ)上，需要進(jìn)行一系列加法運(yùn)算得到最終的乘法結(jié)果。ans數(shù)組中各個(gè)元素的計(jì)算公式如式(2)所示。

該過程可以被形象地認(rèn)為是將map數(shù)組對(duì)應(yīng)的矩陣對(duì)象傾斜 45°后累加垂直方向上的所有元素。如果未發(fā)生進(jìn)位，需要進(jìn)行累加操作的數(shù)組單元數(shù)量，即ans數(shù)組的長(zhǎng)度為lenAns＝lenA+lenB－1；如果出現(xiàn)進(jìn)位，則該長(zhǎng)度為lenA+lenB。

圖2為lenA和lenB分別為3時(shí)的斜向相加過程。

圖2 斜向相加過程

2.4 取模進(jìn)位

經(jīng)過上述過程得到ans數(shù)組元素并未進(jìn)行進(jìn)位操作，最終需要的是一個(gè)經(jīng)過進(jìn)位整理的ans數(shù)組，以便繼續(xù)用于計(jì)算或者轉(zhuǎn)換輸出。因此，需要從ans數(shù)組的最高單元（計(jì)算結(jié)果的最低單元）開始，進(jìn)行循環(huán)取模和進(jìn)位操作。循環(huán)取模進(jìn)位結(jié)束后，就得到了最終計(jì)算結(jié)果的數(shù)組。

2.5 對(duì)并行計(jì)算次數(shù)的進(jìn)一步優(yōu)化

在 RenderScript框架中，每次調(diào)用并行計(jì)算機(jī)制時(shí)，都要從內(nèi)存向GPU緩存?zhèn)鬟f數(shù)據(jù)，該過程會(huì)造成一定的時(shí)間開銷。分析上述方案的計(jì)算過程發(fā)現(xiàn)，雖然在邏輯上可以劃分為對(duì)應(yīng)相乘和斜向相加兩個(gè)階段，但實(shí)際上可以將其合并為一次并行計(jì)算機(jī)制的調(diào)用，從而降低系統(tǒng)時(shí)間開銷，進(jìn)一步優(yōu)化計(jì)算過程的執(zhí)行效率。

具體方法為取消map數(shù)組的存儲(chǔ)單元，將map數(shù)組中所有元素的計(jì)算過程合并到原來的并行斜向相加的過程中。即在完成矩陣元素map[i][j]的計(jì)算后，即刻將其累加到ans數(shù)組的對(duì)應(yīng)元素中。

上述優(yōu)化方法大大縮減了對(duì)存儲(chǔ)空間的依賴，將并行計(jì)算機(jī)制的調(diào)用次數(shù)減少為原來的50%。

3 實(shí)驗(yàn)

在Android平臺(tái)中使用RenderScript框架實(shí)現(xiàn)本文方案分為兩步。第一步是創(chuàng)建計(jì)算核心文件，該文件中包含編譯指示聲明、對(duì)應(yīng)的Java類說明和主體計(jì)算函數(shù)定義。主體計(jì)算函數(shù)是將計(jì)算任務(wù)并行化的重要手段，被上層的Java類調(diào)用。第二步是創(chuàng)建使用該計(jì)算核心的Java類，這里需要聲明一個(gè) RenderScript變量，對(duì)其分配資源并初始化后用其調(diào)用主體計(jì)算函數(shù)。

本文采用常見的Android Studio作為開發(fā)工具[11]，編碼實(shí)現(xiàn)上文中的方案。通過設(shè)置編譯配置文件“build.gradle”，在“config”中增加“renderscriptTargetApi”和“renderscriptSupport ModeEnabled”兩個(gè)字段，使Android Studio支持RenderScript框架的使用。

首先進(jìn)行核心層的實(shí)現(xiàn)。本文將核心文件代碼包含在核心文件 mul.rs中，在該文件代碼中定義了一個(gè)宏、6個(gè)全局變量、一個(gè)全局靜態(tài)變量和兩個(gè)運(yùn)算接口。定義了一個(gè)靜態(tài)的長(zhǎng)整形數(shù)組，用于臨時(shí)保存結(jié)果的斜向相加后的計(jì)算結(jié)果。并行乘法接口將串行算法中的for循環(huán)遍歷求解數(shù)組的過程變?yōu)椴⑿姓{(diào)用求解每一個(gè)結(jié)果數(shù)組元素的過程。計(jì)算結(jié)果存到了臨時(shí)長(zhǎng)整形數(shù)組中，以保證數(shù)據(jù)不溢出，并起到了拓寬取值范圍的作用。編寫完核心文件后，編譯生成對(duì)應(yīng)Java類，用于提供上層Java類與核心進(jìn)行交互的媒介。

RenderScript核心層實(shí)現(xiàn)完畢后，在Java層封裝一個(gè)RSBigInteger類與核心交互，并提供規(guī)范的上層API[12]；進(jìn)而定義RSBigInteger類的乘法接口，其方法實(shí)現(xiàn)中定義了 forEach_multiply方法，實(shí)現(xiàn)對(duì)核心文件mul.rs中的multiply方法對(duì)并行執(zhí)行調(diào)用。

最終，本文將編譯完成的運(yùn)算庫進(jìn)行發(fā)布，并編寫了測(cè)試程序使用RSBigInteger類調(diào)用運(yùn)算庫，測(cè)試其實(shí)際計(jì)算性能。本文采用紅米2標(biāo)準(zhǔn)版手機(jī)作為測(cè)試硬件，其系統(tǒng)版本為5.1.1，CPU為高通 MSM8916四核處理器，GPU為高通Adreno306。在同樣的設(shè)備上，本文編寫了使用原生的JavaBigInteger類的另一個(gè)測(cè)試程序，執(zhí)行完全相同的計(jì)算任務(wù)，對(duì)計(jì)算結(jié)果進(jìn)行比較。實(shí)驗(yàn)步驟如下。

1) 生成長(zhǎng)度為N的兩個(gè)隨機(jī)大整數(shù)。

2) 分別使用兩個(gè)測(cè)試程序初始化兩個(gè)大整數(shù)實(shí)例，記錄初始化耗時(shí)。

3) 分別使用兩個(gè)測(cè)試程序做 50次乘法計(jì)算，記錄執(zhí)行時(shí)間和計(jì)算結(jié)果。

表1 測(cè)試結(jié)果

4) 確認(rèn)計(jì)算結(jié)果正確的條件下，針對(duì)每個(gè)長(zhǎng)度N的大整數(shù)進(jìn)行3組測(cè)試，記錄初始化時(shí)間和計(jì)算時(shí)間的平均值。

5) 改變N的值，重復(fù)上述過程。

（注：測(cè)試中N的取值為100，300，500，800，1 000，3 000，5 000）。

實(shí)驗(yàn)結(jié)果如表1所示。

使用JavaBigInteger類和RSBigInteger類的測(cè)試程序在初始化操作方面的時(shí)間比較如圖 3所示，其計(jì)算時(shí)間比較如圖4所示。

圖3 初始化時(shí)間表比較

圖4 計(jì)算時(shí)間比較

從圖3中可以明顯看出，大整數(shù)長(zhǎng)度低于900 bit時(shí)使用RSBigInteger類的測(cè)試程序初始化速度不占優(yōu)勢(shì)。這是因?yàn)槌跏蓟瘮?shù)中要提前構(gòu)造用于GPU并行計(jì)算使用的存儲(chǔ)對(duì)象。但是使用BigInteger類的測(cè)試程序初始化時(shí)間是呈線性增長(zhǎng)的，而使用RSBigInteger類的測(cè)試程序的增速非常緩慢。

從圖4中可以看出，隨著計(jì)算量的增大，傳統(tǒng)基于CPU的串行算法的BigInteger類耗時(shí)呈指數(shù)型增長(zhǎng)，而使用并行計(jì)算算法的 RSBigInteger類耗時(shí)增速卻非常緩慢。因此在數(shù)據(jù)量足夠大時(shí)，GPU并行計(jì)算的優(yōu)勢(shì)非常明顯。

測(cè)試結(jié)果表明，小規(guī)模數(shù)據(jù)的計(jì)算并不適合使用并行計(jì)算機(jī)制，因?yàn)檩斎胼敵鰰r(shí)間占比過高將導(dǎo)致并行計(jì)算的優(yōu)勢(shì)無法發(fā)揮。對(duì)于超過300 bit的大整數(shù)而言，使用并行計(jì)算機(jī)制是非常合適的，而且長(zhǎng)度越大，其效果越明顯。

4 結(jié)束語

本文研究了利用 Android平臺(tái)中的RenderScript并行運(yùn)算機(jī)制實(shí)現(xiàn)大整數(shù)乘法快速運(yùn)算的方法，設(shè)計(jì)并實(shí)現(xiàn)了一種適合并行處理的大整數(shù)乘法運(yùn)算存儲(chǔ)結(jié)構(gòu)和運(yùn)算執(zhí)行邏輯。該方案以矩陣的方式分割并處理大整數(shù)對(duì)象，可以并行地同步完成所有乘法和加法運(yùn)算，進(jìn)而快速得到乘法運(yùn)算結(jié)果。本文方案能夠?yàn)闄E圓曲線密碼等密碼運(yùn)算提供高效快速的基本操作，實(shí)現(xiàn)Android平臺(tái)密碼運(yùn)算的加速與優(yōu)化。實(shí)驗(yàn)結(jié)果表明，與Android平臺(tái)中原生的Java大整數(shù)運(yùn)算庫相比，本文方案在執(zhí)行速度上具有明顯優(yōu)勢(shì)。