(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210919020.3 (22)申请日 2022.08.02 (71)申请人 山东大学 地址 266200 山东省青岛市 即墨区滨 海路 72号 (72)发明人 杨刚强　崔冰洋　计小宇　万志国　 周洪超　熊海良　 (74)专利代理 机构 青岛华慧泽专利代理事务所 (普通合伙) 37247 专利代理师 刘娜 (51)Int.Cl. H04L 9/06(2006.01) H04L 9/08(2006.01) H04L 9/30(2006.01) (54)发明名称 一种SM2蒙哥马利域上的快速模逆芯片实现 装置及方法 (57)摘要 本发明公开了一种SM2蒙哥马利域上的快速 模逆芯片实现装置及方法， 实现装置包括输入寄 存器、 迭代求解器、 快速取模器和输出寄存器； 所 述输入寄存器用于暂时存储外部输入的待求模 逆的整数x的蒙哥马利域数 与椭圆曲线素数 ； 所述迭代求解器包括寄存器A、 P、 U、 V、 K和运算 器， 所述快速取模器包括拆分器、 进位运算电路 和组合器， 所述输出寄存器用于暂时存储向外部 输出的模逆运算结果。 本发明所公开的装置及方 法对于任何256比特输入,其运算的时钟周期数 恒定， 减少侧信道泄露的信息， 提高了硬件装置 的安全性， 有效简化了在实际应用时蒙哥马利域 与整数域 转化的步骤。 权利要求书3页 说明书9页 附图3页 CN 115276960 A 2022.11.01 CN 115276960 A 1.一种SM2蒙哥马利域上的快速模逆芯片实现装置， 其特征在于， 包括输入寄存器、 迭 代求解器、 快速取模器和输出寄存器； 所述输入寄存器用于暂时存储外部输入的待求模逆的整数x的蒙哥马利域数 与椭圆 曲线素数 所述迭代求解器包括寄存器A、 P、 U、 V、 K和运算器， 寄存器A用于存储输入寄存器输入的 蒙哥马利域数a～并存储中间迭代运算结果a， 寄存器P用于存储输入寄存器输入的椭圆曲 线素数p～并存储中间迭代运算结果p， 寄存器U用于存储中间迭代 运算结果u， 寄存器V用于 存储中间迭代 运算结果v并输出最 终运算结果v， 寄存器K用于和一个8比特行波进位加法器 构成计数器； 所述运算器包括2个256比特行波进位减法器， 2个320比特行波进位减法器， 1 个256比特比较器， 2个256比特右移移位器， 2个320比特左移移位器， 6个256比特数据选择 器， 6个320比特数据选择器， 运算器用于根据寄存器A、 P的值a， p的奇偶性与大小关系确 定 参数， 并利用参数 更新寄存器A、 P、 U、 V的值a,p,u,v； 计数器用于计数迭代周期； 所述快速取模器包括拆分器、 进位运算电路和组合器， 所述进位运算电路包括32比特 行波进位加法器、 32比特行波进位减法器、 进位链电路和 3组寄存器， 第一组寄存器为10个 32比特寄存器B0,…,B9， 第二组寄存器为9个32比特寄存器R0,…,R8， 第三组寄存器为8个32 比特寄存 器S0,…,S7； 所述拆分器用于将寄存器V输入的320比特整数v拆分为10个32比特整 数b0,…,b9， 所述寄存器B0,…,B9用于存储10个32比特整数b0,…,b9， 所述寄存器R0,…,R8用 于存储进位运算电路第一 阶段运算结果r0,…,r8， 所述寄存器S0,…,S7用于存储进位运算 电路第二阶段运算结果s0,…,s7； 所述组合器用于将寄存器S0,…,S7的值s0,…,s7从低位到 高位拼接出25 6比特运算结果， 并输出到 输出寄存器中； 所述输出寄存器用于暂时存 储向外部输出的模 逆运算结果。 2.一种SM2蒙哥马利域上的快速模逆芯片实现方法， 采用如权利要求1所述的一种SM2 蒙哥马利域上的快速模 逆芯片实现装置， 其特 征在于， 包括如下 过程： 步骤一， 从外部输入待求模逆的整数x的蒙哥马利域数 与椭圆曲线素数 存储到输入 寄存器中,存 储完毕后进入 迭代求解器中； 步骤二， 进入迭代求解器后， 初始化320比特寄存器U、 V的值u,v分别为1,0， 从输入寄存 器中将待求模逆的整数x的蒙哥马利域数 存储入256比特寄存器A中， 椭圆曲线素数 存储 入寄存器P中； 在每一轮迭代 中， 分别比较当前寄存器A、 P的值a,p的奇偶性与大小关系， 利 用运算器确定参数后， 并利用参数 更新寄存器A、 P、 U、 V的值a,p,u,v； 同时， 初始化一个用于计数的8比特寄存器K的值k为0， 每一个时钟周期其内值自增一， 其自增过程使用一个8比特行波进位加法器实现， 寄存器K和8比特行波进位加法器构成一 个计数器； 利用该计数器计数共256个时钟周期， 每个时钟周期完成一轮迭代运算， 即更新寄存器 A、 P、 U、 V中的值a,p,u,v， 计数到第256个 时钟周期运算完成后 退出迭代， 将此时320比特寄 存器V中的结果v输出 给快速取模器； 步骤三， 在快速取模器中， 首先使用拆分器将输入 的320比特整数v拆分为10个32比特 的整数b0,…,b9， 并存储入10个32比特寄存器B0,…,B9中， 10个32比特寄存器B0,…,B9的值 b0,…,b9进入第一阶段运算， 运算结果存储入9个32比特寄存器R0,…,R8中， 这9个32比特寄权　利　要　求　书 1/3 页 2 CN 115276960 A 2存器R0,…,R8的值r0,…,r8进入第二阶段运算， 运算结果存储入8个32比特寄存器S0,…,S7 中， 最终， 由组合器将这8个32比特寄存器S0,…,S7的值s0,…,s7从低位到高位拼接出256比 特运算结果， 并输出到 输出寄存器中； 步骤四， 输出寄存器将最终的模 逆运算结果输出。 3.根据权利要求2所述的一种SM2蒙哥马利域上的快速模逆芯片实现方法， 其特征在 于， 步骤二中， 参数包括αi, βi,γi,ωi， i表示第i个时钟周期， 参数的确定方法如下： 在a， p均为奇数的情况 下： 当p>5a时， αi＝1， βi＝‑3/2， γi＝0， ωi＝1/2； 当3a<p<5a时， αi＝‑3/2， βi＝1， γi＝1/2， ωi＝0； 当a<p<3a时， αi＝‑1/2， βi＝1， γi＝1/2， ωi＝0； 在a为奇数， p为偶数的情况 下： 当p>4a时， αi＝1， βi＝‑1， γi＝0， ωi＝1/2； 当2a<p<4a时， αi＝‑1， βi＝1， γi＝1/2， ωi＝0； 当a<p<2a时， αi＝0， βi＝1， γi＝1/2， ωi＝0； 在a为偶数， p任意的情况 下： 当p>2.5a时， αi＝1/2， βi＝‑2， γi＝0， ωi＝1； 当2a<p<2.5a时， αi＝‑2， βi＝1/2， γi＝1， ωi＝0； 当1.5a<p<2a时， αi＝1/2， βi＝‑1， γi＝0， ωi＝1； 当a<p<1.5a时， αi＝‑1， βi＝1/2， γi＝1， ωi＝0。 4.根据权利要求3所述的一种SM2蒙哥马利域上的快速模逆芯片实现方法， 其特征在 于， 步骤二中， 寄存器A、 P、 U、 V的值a,p,u,v更新公式如下： 5.根据权利要求2所述的一种SM2蒙哥马利域上的快速模逆芯片实现方法， 其特征在 于， 步骤三中， p＝2256‑2224‑296+264‑1,其模运 算使用以下同余式进行简化： 2256＝2224+296‑264+1 mod p 2288＝2224+2128‑264+232+1 mod p 320比特整数v 满足如下关系： v＝b92288+…+b1232+b0。 6.根据权利要求5所述的一种SM2蒙哥马利域上的快速模逆芯片实现方法， 其特征在 于， 步骤三中， 第一阶段运 算过程如下： 利用同余式化简得到中间同余结果r: r＝v mod p＝[(b9+b8+b7)·2224+b6·2192+b5·2160+(b9+b4)·2128+(b3+b8)·296+(b2‑b8‑ b9)·264+(b1+b9)·232+(b0+b9+b8)]mod p 将r再次分解 为9个32比特整数r0,r1,r2,r3,r4,r5,r6,r7,r8， 即 r＝r82256+…+r1232+r0权　利　要　求　书 2/3 页 3 CN 115276960 A 3