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

有效

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

本申請(qǐng)公開了一種ASIC芯片及蒙哥馬利模乘的實(shí)現(xiàn)方法和裝置，包括：變量接收模塊11，用于獲取第一輸入變量X和第二輸入變量Y，以及模數(shù)P，其中，均使用n位二進(jìn)制數(shù)表示，模數(shù)P為奇數(shù)；變量計(jì)算模塊12，用于基于蒙哥馬利模乘的基底r的位數(shù)k，分別計(jì)算第一輸入變量X、第二輸入變量Y和模數(shù)P的第0至t個(gè)分塊；迭代計(jì)算模塊13，用于基于第一輸入變量X、第二輸入變量Y和模數(shù)P的第0至t個(gè)分塊，按照蒙哥馬利模乘的預(yù)設(shè)迭代算法，進(jìn)行t+1次迭代；靜態(tài)隨機(jī)存取存儲(chǔ)器14，用于存儲(chǔ)第一輸入變量X、第二輸入變量Y和蒙哥馬利模乘的結(jié)果S。采用本方案，減少了存儲(chǔ)輸入輸出所占用的硬件電路的面積，減少了迭代次數(shù)，提高了計(jì)算效率。

技術(shù)領(lǐng)域

本申請(qǐng)涉及計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及一種ASIC(Application SpecificIntegrated Circuit，專用集成電路)芯片及蒙哥馬利模乘的實(shí)現(xiàn)方法和裝置。

背景技術(shù)

蒙哥馬利算法是一種計(jì)算大整數(shù)模乘和模冪的優(yōu)化算法，該算法規(guī)避了大開銷除法和取模操作，使得大整數(shù)模乘和模冪僅用加法、乘法和移位操作實(shí)現(xiàn)，大幅提高了計(jì)算效率。而大整數(shù)模乘和模冪在RSA、Paillier等密碼算法中的頻繁應(yīng)用奠定了蒙哥馬利算法的重要地位。

蒙哥馬利算法的核心算法是蒙哥馬利模乘算法：

mont_mul(X,Y)＝X·Y·R^-1(modP)

計(jì)算大整數(shù)模冪的算法可以通過多次蒙哥馬利模乘解決，因此近年來在硬件上實(shí)現(xiàn)和優(yōu)化蒙哥馬利模乘在計(jì)算機(jī)技術(shù)中占據(jù)重要地位，并且，蒙哥馬利模乘算法也廣泛應(yīng)用于多方安全計(jì)算技術(shù)領(lǐng)域中。

目前，在已知的一種蒙哥馬利模乘算法(算法1)中，將輸入變量表示為在基底r下的分塊，例如，將使用一定位數(shù)n(例如2048)的二進(jìn)制數(shù)表示的輸入變量，拆分為若干個(gè)t(例如16個(gè))預(yù)設(shè)位數(shù)k(例如128位)的數(shù)據(jù)分塊，并設(shè)計(jì)相應(yīng)預(yù)設(shè)位數(shù)(128位)的加法/乘法器單元。使用設(shè)計(jì)的加法/乘法器單元，通過執(zhí)行t次蒙哥馬利模乘的迭代算法，得到最后一次迭代結(jié)果，并將該迭代結(jié)果與模數(shù)P進(jìn)行比較，如果大于等于模數(shù)P，則計(jì)算該迭代結(jié)果減去模數(shù)P，結(jié)果作為蒙哥馬利模乘的結(jié)果。

在上述算法1中，最后需要執(zhí)行比較和減法操作，在硬件視線中占據(jù)較大面積，而且效率較低，因此，現(xiàn)有技術(shù)中對(duì)算法1進(jìn)行了優(yōu)化，提出算法2。

在算法2中，輸入變量均小于2倍的模數(shù)P，使用t+2個(gè)數(shù)據(jù)分塊表示輸入變量和模數(shù)，且輸入變量的最后一個(gè)數(shù)據(jù)分塊，以及模數(shù)的最后兩個(gè)數(shù)據(jù)分塊均為0，通過執(zhí)行t+2次蒙哥馬利模乘的迭代算法，得到最后一次迭代結(jié)果，作為蒙哥馬利模乘的結(jié)果。

采用算法2可以避免比較和減法操作，且理論上可以證明，若模數(shù)P選取n位，輸入變量小于2倍的模數(shù)P時(shí)，蒙哥馬利模乘的輸出小于2倍的模數(shù)P。即算法2的輸入和輸出的位數(shù)可以固定為n+1位。

然而在硬件設(shè)計(jì)上，一般無法直接增加1位，例如n＝2048位時(shí)，硬件使用16塊128位來表示n位大整數(shù)，而n+1位的大整數(shù)則實(shí)際需要17塊128位來表示，這增大了存儲(chǔ)輸入輸出所占用的硬件電路面積和計(jì)算開銷。

發(fā)明內(nèi)容

本申請(qǐng)實(shí)施例提供一種ASIC芯片及蒙哥馬利模乘的實(shí)現(xiàn)方法和裝置，用以解決現(xiàn)有技術(shù)中存在的進(jìn)行蒙哥馬利模乘的計(jì)算效率較低，以及使用硬件電路實(shí)現(xiàn)蒙哥馬利模乘時(shí)硬件電路占用面積較大問題。

本申請(qǐng)實(shí)施例提供一種專用集成電路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；