[發明專利]一種并行環境下高吞吐量的模逆計算方法及系統

有效

• 申請號: 202110090167.1
• 申請日: 2021-01-22
• 公開（公告）號: CN112799637B
• 公開（公告）日: 2023-03-14
• 發明（設計）人: 朱輝;黃煜坤;李暉;劉興東;李臨風
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F7/72
• 分類號: G06F7/72;G06F21/64
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪

本發明屬于信息安全技術領域，公開了一種并行環境下高吞吐量的模逆計算方法及系統，接受a₁，a₂，...，a_m共m個待求逆值和模數p，輸出共m個模逆值，包括三個階段：數據劃分階段、并行求逆階段和數據組整合階段；所述并行環境下高吞吐量的模逆計算系統包括：基于并行平臺計算資源的數據劃分模塊、基于同時模逆算法的并行求逆模塊、基于映射關系的數據組整合模塊、基于歷史運行結果的性能分析模塊。本發明利用同時模逆算法將模逆運算轉化為模乘運算的特性，減輕高并發模逆時線程束分化現象，針對串行同時模逆算法無法充分發揮并行平臺全部性能的問題，設計并行同時模逆算法，使并行環境下模逆運算吞吐量有較大提升。

技術領域

本發明屬于信息安全技術領域，尤其涉及一種并行環境下高吞吐量的模逆計算方法及系統。

背景技術

目前，隨著電子商務的發展，電商平臺每秒需要進行越來越大規模的數字簽名運算，以保證交易的安全性。GPU(Graphics Processing Unit)作為一種通用的高性能并行計算平臺，非常適合用于對此類高并發量的業務的加速計算。然而在GPU這種分支預測能力弱的并行環境下，模逆運算這種需要進行大量分支判斷的算法，是提高數字簽名算法總吞吐量的一大瓶頸。

目前常用的模逆計算方法有基于拓展歐幾里得算法和基于費馬小定理的模逆法，然而這些常用的模逆計算法應用于并行計算平臺的效果并不理想?；谫M馬小定理的模逆法由于其高昂的計算開銷，通常不被考慮使用。由于拓展歐幾里得算法需要大量的分支判斷，如果只是簡單地并行運行拓展歐幾里得算法，將會導致嚴重的線程束分化，不能達到理想的高吞吐量的效果。經典的同時模逆算法雖然在進行大批量的模逆運算時，能夠將模逆運算轉化為開銷更小的模乘運算，從而只需進行一次模逆，但整個算法是串行執行的不能發揮并行計算平臺的全部計算性能。

目前，針對上述問題，已經提出的解決方案有：

(1)基于GPU與CPU異構結構的橢圓曲線數字簽名方法，專利號為CN201910375545.3，該方法在GPU上利用費馬小定理計算模逆，由于費馬小定理需要進行開銷非常高昂的模冪運算，此方案不適合在模乘計算能力弱的計算設備上實現。

(2)SM2數字簽名生成算法的實現方法及裝置，專利號為CN201310445395.1，該裝置通過CPU預先計算模逆值并存儲的方式，讓GPU可以直接從全局內存中讀取到需要計算的模逆值，但此方案只適用于能夠預測模逆輸入的算法，不能實時計算模逆值。

(3)論文An Efficient Elliptic Curve Cryptography Signature Server WithGPU Acceleration，DOI為：10.1109/TIFS.2016.2603974，該論文提出的解決方案是通過CPU與GPU相結合，使用分支預測能力更強的CPU運行同時模逆算法計算模逆。然而這種方案需要CPU與GPU間的通信交互，且大大增加了任務調度的復雜程度，在實際實現過程中難以優化到理想的效果。

通過上述分析，現有技術存在的問題及缺陷為：

(1)由于并行計算平臺分支預測能力弱的特性，經典的基于拓展歐幾里得算法的模逆算法應用于并行計算平臺的效果并不理想?；谫M馬小定理的模逆法需要進行開銷非常高昂的模冪運算，不適合在模乘計算能力弱的設備上實現；

(2)利用擅長分支預測的CPU計算模逆雖然能在模逆性能上有優秀的表現，但其與并行計算平臺的交互會帶來不可忽略的額外計算開銷，且CPU與GPU線程調度的問題也會大大增加實現的難度。

(3)串行運行的同時模逆算法，雖然能在一定程度上緩解線程束分化的問題，并減少一定的運算量，但該算法無法發揮并行計算平臺的全部性能。

解決以上問題及缺陷的難度為：如何設計一種適合并行計算平臺運行的且計算開銷低的高吞吐量模逆計算方法。