[發明專利]一種基于GPU的多變量密碼算法并行化加速方法

有效

• 申請號: 201810228547.5
• 申請日: 2018-03-20
• 公開（公告）號: CN108510429B
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 龔征;廖國鴻;黎偉杰;馬昌社;劉志杰;羅裴然;黃家敏
• 申請（專利權）人: 華南師范大學
• 主分類號: G06T1/20
• 分類號: G06T1/20;G06F9/38
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

本發明公開了一種基于GPU的多變量密碼算法并行化加速方法，該方法包括下述步驟：S1、對多變量等式的所有項進行同階化操作；S2、生成GF2域上乘法表；S3、將項數表和乘法表映射到GPU的紋理內存；S4、對每一塊數據調用多變量主內核函數進行計算并執行Reduce操作；S5、編寫主函數來調度多變量主內核函數；S6、執行程序，輸出加解密結果，釋放資源。本發明主要通過將多變量的所有項進行同階化并結合Map?Reduce的思想來對多變量密碼體制的密碼算法進行優化，并以SpongeMPH哈希函數算法為例，給出了CUDA平臺下面的實現與性能比較。實驗表明該方案提高了算法的運行效率，可用于加速基于多變量密碼體制的密碼算法。

技術領域

本發明涉及密碼算法的技術領域，更具體地說，涉及一種基于GPU的多變量密碼算法并行化加速方法。

背景技術

圖形處理單元GPU最初被設計用來進行圖像處理，近年來由于CPU功耗的限制以及對計算需求的快速增長，而GPU的計算能力以遠超摩爾定律的速度快速發展，促使GPU被廣泛應用在科學計算領域。

多變量密碼算法是利用有限域上多變量多項式構成的密碼方案。而求解有限域上多變量多項式方程組問題是一個NP-Hard問題，是目前抗量子攻擊的設計思路之一。然而多變量密碼算法的運算量較大，導致效率較低是限制其實用性的一個主要方面。所以，如何提高GPU的執行效率是本領域技術人員研究的方向之一。

發明內容

本發明的主要目的在于克服現有技術的缺點與不足，提供一種基于GPU的多變量密碼算法并行化加速方法，利用GPU結合Map-Reduce的思想來實現多變量密碼算法的并行化，從而提高其執行效率。

為了達到上述目的，本發明采用以下技術方案：

本發明一種基于GPU的多變量密碼算法并行化加速方法，包括下述步驟：

S1、對多變量等式的所有項進行同階化操作；

S2、生成有限域上的生成元表及對數表，通過這兩個表進行查表操作實現有限域的乘法來提高GPU線程計算過程中的一致性，所述的生成元表用table表示,是指q階有限域F上的生成元g生成的前q-1個自然數0,1,2,…,q-2的冪次方與0構成的表即table[i]＝gⁱ且令table[q-1]＝1，table[q]＝g；所述對數表用arc_table表示，是指對于有限域上的任意元素a，有arc_table[a]＝i，其中table[i]＝a，且令arc_table[0]的值為一個大負數，使得0*a＝table[arc_table[0]+arc_table[a]]中arc_table[0]+arc_table[a]恒為負數，而table[負數]的值為0；

S3、將項表、系數表、生成元表及對數表映射到GPU的紋理內存，所述項表是指多變量方程中分別構成每一項的變量的下標，當某一項為a₁x₁x₃x₄,其中x₁x₃x₄為變量，則項表在相應位置存1，3，4，所述系數表是指多變量方程中每一項的系數，與項表一一對應；

S4、對每一塊數據調用多變量主內核函數進行計算并執行Reduce求和操作，所述多變量主內核函數的參數包括待處理數據的地址、當前多項式變量的值的地址及中間臨時數據存放的地址；所述多變量主內核函數的內容包括在GPU里的每個基本調度單位里獲取每一個變量的值，計算每一項運算完的值，然后進行Reduce求和操作，獲取每個多項式的結果并保存到當前多項式的變量數組中

S5、編寫主函數來調度多變量主內核函數，主函數包括設置分塊大小、申請GPU內存空間以及紋理內存綁定，不斷的將分塊數據傳遞給主內核函數，最終將計算結果拷貝回主機端內存，釋放資源；

S6、執行程序，輸出加解密結果，釋放資源。