[發(fā)明專利]一種ASIC芯片及蒙哥馬利模乘的實現(xiàn)方法和裝置

有效

• 申請?zhí)枺?/td>: 202210337620.9
• 申請日: 2022-04-01
• 公開（公告）號: CN114706557B
• 公開（公告）日: 2023-03-10
• 發(fā)明（設(shè)計）人: 劉文心;李藝;王雪強
• 申請（專利權(quán)）人: 華控清交信息科技（北京）有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72;G06F15/78
• 代理公司: 北京市廣友專利事務(wù)所有限責(zé)任公司 11237
• 代理人: 李欣

1.一種專用集成電路ASIC芯片，其特征在于，包括：

變量接收模塊，用于獲取第一輸入變量X和第二輸入變量Y，以及模數(shù)P，其中，所述第一輸入變量X、所述第二輸入變量Y、所述模數(shù)P以及蒙哥馬利模乘的結(jié)果，均使用n位二進(jìn)制數(shù)表示，所述模數(shù)P為奇數(shù)，且所述第一輸入變量X和所述第二輸入變量Y均小于所述模數(shù)P，且2^n-1P2ⁿ-2^n-k；

變量計算模塊，用于基于蒙哥馬利模乘的基底r的位數(shù)k，分別計算所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第0至t個分塊，其中，基底r為2的k次方，n能夠被k整除，n除以k的商值為t，所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第t個分塊均為0；

迭代計算模塊，用于基于所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第0至t個分塊，按照計算公式S＝X·Y·2^-(n+k)mod P，以及蒙哥馬利模乘的預(yù)設(shè)迭代算法，進(jìn)行t+1次迭代，得到蒙哥馬利模乘的結(jié)果S；

靜態(tài)隨機存取存儲器，用于存儲所述第一輸入變量X、所述第二輸入變量Y和所述蒙哥馬利模乘的結(jié)果S；

所述迭代計算模塊，具體用于采用如下公式，按照i和j分別依次取值為0-t進(jìn)行迭代，計算蒙哥馬利模乘的結(jié)果S：

S_i+1＝S_i+1/r；

S＝S_t+1；

其中，x_j為第一輸入變量X的第j個分塊，y_j為第二輸入變量Y的第j個分塊，p_j為模數(shù)P的第j個分塊，r^j表示r的j次方。

2.一種蒙哥馬利模乘的實現(xiàn)方法，其特征在于，應(yīng)用于專用集成電路ASIC芯片，包括：

獲取第一輸入變量X和第二輸入變量Y，以及模數(shù)P，其中，所述第一輸入變量X、所述第二輸入變量Y、所述模數(shù)P以及蒙哥馬利模乘的結(jié)果，均使用n位二進(jìn)制數(shù)表示，所述模數(shù)P為奇數(shù)，且所述第一輸入變量X和所述第二輸入變量Y均小于所述模數(shù)P，且2^n-1P2ⁿ-2^n-k；

基于蒙哥馬利模乘的基底r的位數(shù)k，分別計算所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第0至t個分塊，其中，基底r為2的k次方，n能夠被k整除，n除以k的商值為t，所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第t個分塊均為0；

基于所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第0至t個分塊，按照計算公式S＝X·Y·2^-(n+k)mod P，以及蒙哥馬利模乘的預(yù)設(shè)迭代算法，進(jìn)行t+1次迭代，得到蒙哥馬利模乘的結(jié)果S；

所述基于所述第一輸入變量X、所述第二輸入變量Y和所述模數(shù)P的第0至t個分塊，按照S＝X·Y·2^-(n+k)mod P的計算公式，以及蒙哥馬利模乘的預(yù)設(shè)迭代算法，進(jìn)行t+1次迭代，得到蒙哥馬利模乘的結(jié)果S，包括：

采用如下公式，按照i和j分別依次取值為0-t進(jìn)行迭代，計算蒙哥馬利模乘的結(jié)果S：

S_i+1＝S_i+1/r；

S＝S_t+1；

其中，x_j為第一輸入變量X的第j個分塊，y_j為第二輸入變量Y的第j個分塊，p_j為模數(shù)P的第j個分塊，r^j表示r的j次方。