基于Android平臺并行運算機制的密碼運算加速方案1

方寧，曹衛兵，倪冬鶴，狄冠東,3

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

1 引言

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

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

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

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

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

2 大整數乘法并行計算方案

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

2.1 存儲結構

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

2.2 對應相乘

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

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

圖1 按單元相乘結果矩陣

在串行計算中，要計算得到上述矩陣結果需要進行lenA×lenB次計算，而在并行計算機制中的計算次數為

2.3 斜向相加

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

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

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

圖2 斜向相加過程

2.4 取模進位

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

2.5 對并行計算次數的進一步優化

在 RenderScript框架中，每次調用并行計算機制時，都要從內存向GPU緩存傳遞數據，該過程會造成一定的時間開銷。分析上述方案的計算過程發現，雖然在邏輯上可以劃分為對應相乘和斜向相加兩個階段，但實際上可以將其合并為一次并行計算機制的調用，從而降低系統時間開銷，進一步優化計算過程的執行效率。

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

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

3 實驗

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

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

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

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

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

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

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

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

表1 測試結果

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

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

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

實驗結果如表1所示。

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

圖3 初始化時間表比較

圖4 計算時間比較

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

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

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

4 結束語

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