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

有效

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

1.一種基于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、執行程序，輸出加解密結果，釋放資源。

2.根據權利要求1所述基于GPU的多變量密碼算法并行化加速方法，其特征在于，步驟S1中，同階化操作具體為：

通過引入值為1的多余變量與低階的項進行相乘來使其等于多項式的階，從而在一次性內核函數調用中用相同的操作計算每一個多項式的項及求和，避免因為分支結構導致GPU的性能下降；

同時，引入值為0的多余項，使得每個方程的項數數量是Block的倍數；所述Block是CUDA上的定義,在OpenCl上則為work-gruop。

3.根據權利要求1所述基于GPU的多變量密碼算法并行化加速方法，其特征在于，步驟S2中，生成有限域上的乘法表的步驟如下：

對于mod n域中，若g為生成元，則n與g的最大公約數為1，則可通過擴展歐幾里得算法求出生成元g的值，從而枚舉g⁰,g¹,…,g^(p-2)來獲得乘法表及逆表。

4.根據權利要求1所述基于GPU的多變量密碼算法并行化加速方法，其特征在于，步驟S3中，還包括下述內容：

在CPU端先對數據進行預處理，即用冗余項0*x_tx_tx_t填充項表和系數表，使得每個方程的項數剛好是GPU的block數*每個block擁有的線程數，便于在步驟S4中的Reduce求和操作，其中假設多變量系統中含有變量x₀，x₁,…,x_t-1，并添加值為1的額外的自定義變量x_t；然后將這幾個數組用異步操作拷貝到GPU端內存，再與紋理內存綁定。

5.根據權利要求1所述基于GPU的多變量密碼算法并行化加速方法，其特征在于，步驟S4中，其中，所述待處理數據地址、當前多項式每一個變量的值存放的地址均為無符號字符向量指針(uint8_t*)；

所述中間臨時數據存放的地址為無符號32位整型指針(uint32_t*)。