[發明專利]一種基于FPGA的poseidon哈希算法的優化系統

在審

• 申請號: 202210415929.5
• 申請日: 2022-04-20
• 公開（公告）號: CN114757034A
• 公開（公告）日: 2022-07-15
• 發明（設計）人: 王偉
• 申請（專利權）人: 麥田云網（杭州）信息技術有限公司
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F7/72;G06F21/76
• 代理公司: 成都慕川專利代理事務所(普通合伙) 51278
• 代理人: 李小金

1.一種基于FPGA的poseidon哈希算法的優化系統，其特征在于，在FPGA內對poseidon算法參數及流程優化和底層蒙哥馬利模乘優化兩方面進行優化；其中在poseidon哈希算法參數及流程優化中通過常量計算、矩陣計算、常量及矩陣選擇和算法流程優化；在底層蒙哥馬利模乘優化中將蒙哥馬利算法輸入值由標準值轉化為蒙哥馬利形式，蒙哥馬利算法包括模乘、約減和冪模運算；

蒙哥馬利算法中的約減采用的模塊包括約減取模模塊、約減乘法器模塊、約減加法器模塊、約減除法器模塊和約減減法器模塊。在進行約減時，輸入參數后依次通過約減取模模塊、約減乘法器模塊、約減加法器模塊和約減除法模塊進行一輪約減，并在經過若干輪次約減后判斷輸出數，并對高于閾值的輸出參數通過約減減法器模塊處理后輸出；

蒙哥馬利算法中的冪模采用的模塊在采用蒙哥馬利約減運算模塊的基礎上，還包括平方運算模塊、截斷模塊、冪模加法器模塊和冪模減法器模塊，在進行冪模運算時，參數經過平方運算模塊進行處理后，通過截斷模塊將其分為直接處理數據和約減處理數據，其中約減處理數據經過上述的蒙哥馬利算法中約減的模塊處理后輸入冪模加法器模塊內，直接處理數據也輸出至冪模加法器模塊內，隨后判斷輸出數，并對高于閾值的輸出參數通過冪模減法器模塊處理后輸出；

蒙哥馬利算法中的模乘采用的模塊在采用蒙哥馬利約減運算模塊的基礎上，還包括加乘器模塊、模乘取模模塊、模乘加法器模塊和模乘減法器模塊，在進行模乘運算時，參數經過加乘模塊進行處理后發送至約減運算模塊進行處理，其中的約減運算模塊內的約減加法器模塊替換為模乘加法器進行運算，并經過若干輪相同處理方式后，判斷輸出數，并對高于閾值的輸出參數通過模乘減法器模塊處理后輸出。

2.根據權利要求1所述的一種基于FPGA的poseidon哈希算法的優化系統，其特征在于，所述常量計算采用的SPN結構中，由于交換線性變換階段和常量計算都是線性的，通過交換計算順序，進行等價轉換。

3.根據權利要求1所述的一種基于FPGA的poseidon哈希算法的優化系統，其特征在于，所述矩陣計算中的交換線性變換階段，計算與MDS矩陣的乘積時，使用多線程及并行計算，提高矩陣運算效率。

4.根據權利要求1所述的一種基于FPGA的poseidon哈希算法的優化系統，其特征在于，所述算法流程優化時，將poseidon哈希算法的輸入定為11個256bit大整數，輸出定為1個256bit大整數，進行實現和優化，算法流程如下：

S1：將11個輸入值擴充為12個256bit大整數；

S2：在12個輸入值加前12個常量；

S3：進行4輪Full S-Box，每輪Full S-Box包含12個指數運算，12個加法運算，以及矩陣乘積，返回12個大整數；

S4：進行57輪Partial S-Box，每輪Partial S-Box包含1個指數運算，1個加法運算，以及稀疏矩陣乘法，返回12個大整數；

S5：進行3輪Full S-Box，每輪Full S-Box包含12個指數運算，12個加法運算，以及矩陣乘積，返回12個大整數；

S6：進行最后一輪Full S-Box，包含12個指數運算，以及矩陣乘積，返回12個大整數；

S7：輸出第二個元素，為256bit大整數。