(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111668723.5 (22)申请日 2021.12.3 0 (71)申请人 华南理工大 学 地址 510640 广东省广州市天河区五山路 381号 (72)发明人 覃健诚　钟宇　陆以勤　程喆　 (74)专利代理 机构 广州粤高专利商标代理有限 公司 44102 代理人 周春丽 (51)Int.Cl. G06F 21/60(2013.01) G06F 7/575(2006.01) G06F 7/501(2006.01) G06F 7/523(2006.01) G06F 7/72(2006.01) (54)发明名称 基于梅森数的密钥交换或公钥密码加密优 化方法及系统 (57)摘要 本发明公开了基于梅森数的密钥交换或公 钥密码加密优化方法及系统， 包括以下步骤： 在 密钥交换或者公钥密码计算的应用场景中， 选取 或构造取模运算mod的模数， 根据模数将取模运 算mod替换为第一取模运算或第二取模运算； 当 选取的模数为梅森数， 或者构造出算法中的模数 刚好是梅森数时， 将取模运算mod替换为第一取 模运算； 当所选取或构造的模数为形态类似于梅 森数的正整数时， 将取模运算mod替换成第二取 模运算。 本发明能够利用梅森数的数学特性， 优 化模加、 模乘、 模幂运算， 显著降低计算的复杂 度， 提高密钥交换、 公钥密码加密解密的速度。 权利要求书3页 说明书8页 附图4页 CN 114417378 A 2022.04.29 CN 114417378 A 1.基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在于， 包括以下步骤： 在密 钥交换或者 公钥密码计算的应用场景中， 选取或构 造取模运算mod 的模数， 根据模 数将取模 运算mod替换为第一取模运算mod1或第二取模运算mod2； 当选取 的模数为梅森数M＝2n‑1， 或者构造出算法中的模 数刚好是梅森数时， 将取模运算mod替换为第一取模运算mod1， 其中 n是正整数； 当所选取或构造的模数为形态类似于梅森数的正整数K＝2n‑L时， 将取模运算mod替换 成第二取模运 算mod2。 2.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 应用场景包括采用基于离散对数难题的算法、 基于素 因数分解难题的算法， 基于离散椭 圆曲线难题的算法以及以模加、 模乘、 模幂运 算为主要运算量的其他算法。 3.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 所述第一取模运 算mod1为 不含除法的快速取模运 算。 4.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 所述第一取模运 算mod1如下： 设模数M是梅森数， 即M＝2n‑1， 其中n为正整数， 第一取模 运算mod1运算的结果与原有的 取模运算mod结果相同： 模加： Y＝A+B  mod1 M＝A+B mod(2n‑1)， 其中A,B表示模加运 算的两个加数； 模乘： Y＝A*B  mod1 M＝A*B mod(2n‑1)， 其中A,B表示模乘运 算的两个乘数； 模幂： Y＝AB mod1 M＝AB mod(2n‑1)， 其中A表示模幂运算的底数， B表示模幂运算的指 数。 5.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 第一取模运 算mod1的运 算流程包括以下步骤： 步骤S101、 取n 位正整数A和n 位正整数B； 步骤S102、 判断是模加运 算还是模乘运 算， 分别转到步骤S10 3、 S104； 步骤S103、 计算取模之前的加法运 算结果Y0＝A+B， 转到步骤S10 5； 步骤S104、 计算取模之前的乘法运 算结果Y0＝A*B； 步骤S105、 把Y0拆分为低n 位Y1、 高n位Y2； 步骤S106、 计算Y＝Y1+Y2； 步骤S107、 判断是否 Y＝M， 如果 不是则转到步骤S109， 其中模数M为 梅森数； 步骤S108、 做溢出情况处 理， 令Y＝0； 步骤S109、 流 程结束， Y就是mod1运 算的结果。 6.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 所述第二取模运 算mod2为 不含除法的快速取模运 算。 7.根据权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在 于， 所述第二取模运 算mod2如下： 模数为正整数K＝2n‑L， 其中n为正整数， L为正整数， 取L<26， 第二取模运算mod2中不带 有除法运 算过程： 模加： Y＝A+B  mod2 K＝A+B mod(2n‑L)， 其中A,B表示模加运 算的两个加数； 模乘： Y＝A*B  mod2 K＝A*B mod(2n‑L)， 其中A,B表示模乘运 算的两个乘数；权　利　要　求　书 1/3 页 2 CN 114417378 A 2模幂： Y＝AB mod2 K＝AB mod(2n‑L)， 其中A表示模幂运算的底数， B表示模幂运算的指 数。 8.根据权利要求1～7任一项所述的基于梅森数的密钥交换或公钥密码加密优化方法， 其特征在于， 第二取模运 算mod2的运 算流程包括以下步骤： 步骤S201、 取n 位正整数A、 n 位正整数B、 6位 正整数L； 步骤S202、 判断是模加运 算还是模乘运 算， 分别转到步骤S20 3、 步骤S204； 步骤S203、 计算取模之前的加法运 算结果Y0＝A+B， 转到步骤S20 5； 步骤S204、 计算取模之前的乘法运 算结果Y0＝A*B； 步骤S205、 把Y0拆分为低n 位Y1、 高n位Y2； 步骤S206、 计算Y＝Y1+Y2*L； 步骤S207、 如果Y <K， 则转到步骤S209， 其中模数 K为形态类似于梅森数的正整数； 步骤S208、 做溢出情况处理， 令Y0＝Y‑K， 而在硬件实现中， 则令Y0＝Y+L‑2n， 然后转到步 骤S205； 步骤S209、 流 程结束， Y为mod2运 算的结果。 9.实现权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法的系统， 其 特征在于： 包括一个或一个以上快速取模运算逻辑电路组件C1， 能够支持所述的第一取模 运算mod1； 所述快速取模运 算逻辑电路组件C1包括： n位寄存器RegA， 用于暂存输入数A； n位寄存器RegB， 用于暂存输入数B； n位加法器AD D1， 用于两数相加， 输出n 位整数和进位标志C； n位乘法器MUL， 用于 两数相乘， 输出2n 位整数； 2n位寄存器RegY 0， 用于暂存中间数据； n位加法器AD D2， 用于完成快速取模计算， 输出n 位整数和进位标志C； 逻辑门电路， 包括 n个与门、 1个非门； n位寄存器RegY， 用于暂存输出 数Y； 所述寄存器RegA、 RegB的0 至n‑1位分别输出到n 位加法器AD D1的两个输入端； 寄存器RegA、 RegB的0 至n‑1位分别输出到n 位乘法器MUL的两个输入端； 加法器AD D1输出到寄存器RegY 0的0至n‑1位， 进位标志C 输出到RegY 0的第n位； 乘法器MUL输出到寄存器RegY 0的0至2n‑1位； 寄存器RegY 0的低n位、 高n位分别输出到n 位加法器AD D2的两个输入端； 加法器ADD2输出到n个与门的一个输入端， 进位标志C输出到1个非门， 非门再输出到n 个与门的另一个输入端； n个与门输出到寄存器RegY的0 至n‑1位。 10.实现权利要求1所述的基于梅森数的密钥交换或公钥密码加密优化方法的系统， 其 特征在于： 包括一个或一个以上快速取模运算逻辑电路组件C2， 能够支持所述的第二取模 运算mod2； 所述的快速取模运 算逻辑电路组件C2包括： n位寄存器RegA， 用于暂存输入数A； n位寄存器RegB， 用于暂存输入数B； n位加法器AD D1， 用于两数相加， 输出n 位整数和进位标志C；权　利　要　求　书 2/3 页 3 CN 114417378 A 3