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

（1. 北京梆梆安全科技有限公司，北京 100091；2. 北京電子技術應用研究所，北京100091；3. 青島大學計算機科學技術學院，山東 青島 266071）

1 引言

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

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

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

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

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

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

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

2.1 存儲結構

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

2.2 對應相乘

按照上述存儲結構設計，使用式(1)即可完成乘法運算。

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

圖1 按單元相乘結果矩陣

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

2.3 斜向相加

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

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

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

圖2 斜向相加過程

2.4 取模進位

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

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

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

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

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

3 實驗

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

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

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

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

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

1) 生成長度為N的兩個隨機大整數(shù)。

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

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

表1 測試結果

4) 確認計算結果正確的條件下，針對每個長度N的大整數(shù)進行3組測試，記錄初始化時間和計算時間的平均值。

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

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

實驗結果如表1所示。

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

圖3 初始化時間表比較

圖4 計算時間比較

從圖3中可以明顯看出，大整數(shù)長度低于900 bit時使用RSBigInteger類的測試程序初始化速度不占優(yōu)勢。這是因為初始化函數(shù)中要提前構造用于GPU并行計算使用的存儲對象。但是使用BigInteger類的測試程序初始化時間是呈線性增長的，而使用RSBigInteger類的測試程序的增速非常緩慢。

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

測試結果表明，小規(guī)模數(shù)據的計算并不適合使用并行計算機制，因為輸入輸出時間占比過高將導致并行計算的優(yōu)勢無法發(fā)揮。對于超過300 bit的大整數(shù)而言，使用并行計算機制是非常合適的，而且長度越大，其效果越明顯。

4 結束語

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