1、第 30 卷 第 4 期北京电子科技学院学报2022 年 12 月Vol.30 No.4Journal of Beijing Electronic Science and Technology InstituteDec.2022大数模乘硬件模块的研究与实现段晓毅 黄 烨 曹佳乐北京电子科技学院,北京市 100070摘 要:当前主流公钥密码算法如 RSA、各类椭圆曲线加密算法等都会涉及到大数运算,特别是模乘、模幂运算。此类计算资源消耗大、运算处理时间长,成为制约密码算法运行速度的瓶颈,因此设计一款高效的大数模乘模块对于促进公钥密码体系的应用就显得尤为重要。蒙哥马利算法是一种常用的大数模乘算法,基
2、于其算法设计的大数模乘模块结构简单、运算效率较高,且易于硬件实现。本文以蒙哥马利算法为基础,结合数论知识,提出了一种改进的蒙哥马利算法,改进后的蒙哥马利模乘算法结构简单,易于硬件描述实现,然后利用 Verilog 硬件描述语言完成算法设计,最后进行功能仿真测试,完成蒙哥马利大数模乘硬件模块研究与实现。关键词:蒙哥马利算法;模乘;FPGA;硬件描述语言中图分类号:TM344.1 文献标识码:A文章编号:1672-464X(2022)4-15-23 基金项目:高精尖学科建设基金(项目编号:20210032Z0401,20210033Z0402)作者简介:段晓毅(1979-),男,副教授,博士,主要
3、研究方向:信息安全。黄 烨(1999-),女,硕士在读,主要研究方向:信息安全。曹佳乐(2000-),男,本科,主要研究方向:信息安全。1 简介 RSA、ECC(Elliptic Curve Cryptography)算法是常用的公钥算法,而素数域上的模乘运算1是公钥加密算法中的基础算法。但在密码体系的运算中,其运算操作数一般是任意大整数,即位数为 256 bit 或以上的数据结构,算法复杂度较大,已经成为影响当前公钥加密体系发展的重要问题。素数域中的模乘算法是最费时的计算,所以为了提升公钥密码系统的计算效率,选择计算速度快、资源耗费少的高效硬件模块非常重要2。当前国内外对于大数模乘问题的研究
4、方案大致可分为两种:第一种即利用各类基本算法及其改进算法,通过算法结构构建对应的硬件电路,实现大数模乘功能,例如加法型算法3、估商型算法4、蒙哥马利算法,其中又以蒙哥马利型算法应用范围最广,相继提出多种改进方式,实现效果良好。另一种则从硬件结构出发,对于硬件架构进行重构,高效利用计算资源,提升模乘计算速度5,以 FPGA 细粒度映射技术为例6,此在各类硬件载体上都有相关运用,例如通过加密智能卡实现7。大数模乘在基础研究以及密码学等领域都有大量应用,特别是在公钥密码算法方面8。模乘通常情况下表示为:C=(A B)mod N,其中 A、B、N 都为 k bit 二进制的大整数。模乘运算由基本的乘法
5、和计算余数的模运算简化组成,北京电子科技学院学报2022 年目前主要的运算形式有先计算乘法后再进行模简化运算,以及一边进行乘法同时进行模简化运算这两大类基本实现方式9。若以更细化、更精准的处理方式来划分大数模乘的处理流程的话,大数模乘算法又可分为加法型算法、估商型算法、蒙哥马利型算法这三大类。蒙哥马利型模乘算法是目前在硬件结构上用于快速实现模乘计算最适合的算法。本文改进了蒙哥马利算法并将其实现。2 改进的蒙哥马利模乘算法 蒙哥马利模乘算法是蒙哥马利在 1986 年所提出的一种算法10,主要是为了解决大整数模幂运算问题。由于模幂与模乘运算可以互相转换,蒙哥马利模乘算法把部分积对任意的 n 取模运
6、算转化为对与 n 互素的数基 R 进行取模,通常都选 R=2k,k 是非负整数。由于 R 比 n 小得多,对数基 R 的取模运算要比对 n 的取模运算简单得多11,所以蒙哥马利模乘算法在 RSA 密码算法的研究中得到广泛的应用。定义模乘算法为 MM(x,y),如果模数 m 是素数,且满足 m2,则存在一个元素 2-1 Fm,使得 2 2-1mod m=1。假设 m 是一个 k bit 位的素数,那么可以选择一个数 R,使得 R=2k且满足 x,y Fm其中 x 可表示为:x=xk-12k-1+xk-22k-2+x020(2.1)将式(2.1)代入模乘计算表达式,得到下式:MM(x,y)=(xy
7、)2k-1(mod m)=(xk-1y2k-1+xk-2y2k-2+x0y20)(2k)-1mod m=(0+x0y)2-1+x1y)2-1+x2y)2-1+)2-1+xk-1y)2-1mod m(2.2)由于基本的蒙哥马利模乘算法中不但包含基本的乘法、加法运算,还包含了模逆运算,并不利于计算机的硬件实现。改进的蒙哥马利模乘算法通过对基本算式的重新表达,配合数论里的基本结论,巧妙避免了复杂运算,易于模乘计算12。由数论知识可知用一个自然数去乘 2-1有以下结论:a2-1=a2mod m,a 为偶数a2-1=(a+m)2mod m,a 为奇数(2.3)将式(2.2)中单次运算括号中的部分套用式(
8、2.3),即可得到改进后的蒙哥马利模乘算法13MM(x,y),其算法流程如下所示:MM(x,y)1:令 p=02:for i=0 to k-1 loopa=p+x(i)yif(a mod 2)=0 then p=a2else p=(a+m)23:if p m then z=p-melse z=p改进后的蒙哥马利模乘算法结构简单,易于硬件描述实现,本文就以改进的蒙哥马利模乘算法 MM(x,y)为设计基础,实现蒙哥马利型大数模乘模块功能。3蒙哥马利型大数模乘模块的总体设计3.1 蒙哥马利型大数模乘模块外部总视图本方案中的大数模乘模块的外部总视图如图 3-1 所示:输入:x、y、m输出:Cx:参与模
9、乘运算的乘数 1,输入范围从 1bit-4096bit。61第 30 卷大数模乘硬件模块的研究与实现 图 3-1 蒙哥马利型大数模乘模块外部总视图y:参与模乘运算的乘数 2,输入范围从 1bit-4096bit。m:参与模乘运算的模数,输入范围从 1bit-4096bit。C:模 乘 的 输 出 结 果,输 出 范 围 从 1bit-4096bit。对于本文系统的输入数据 x、y、m 来说,最大可以满足 4096 bit,能满足现在对公钥算法强度的要求。当要进行计算时,输入 x、y、m,即可通过此模块计算得到结果 C,即:C=xymod m,此为所要研究的大数模乘。3.2 蒙哥马利型大数模乘模
10、块内部结构设计蒙哥马利型大数模乘模块的内部结构设计如图 3-2 所示:图 3-2 蒙哥马利型大数模乘模块内部结构设计本设计的运算处理步骤是通过四次调用改进的蒙哥马利模乘算法,并且每次调用中输入不同的数据,最终得到没有 R-1影响的大数模乘。在第一、二次调用中,将 R2作为第二个乘数来进行代入计算(在相同模数 m 的情况下,R2的数值不变,可以重复使用),这一步得到 X=XRmod m 与 Y=YRmod m;第三次调用中将得到的 X、Y作为操作数再进行一次蒙哥马利模乘计算,得到 S=XYRmod m;第四次调用中,1 作为另一个操作数被代入计算,R 与R-1即可相互抵消,最终得到大数模乘运算结
11、果C=xymod m。3.3 蒙哥马利模乘单元模块设计如上文介绍,蒙哥马利型大数模乘模块实际上就是在不断重复计算蒙哥马利模乘算法的过程14,所以设计大数模乘的关键就在于对于蒙哥马利模乘单元模块进行设计实现,也就是说将章节 2 中提到的改进后的蒙哥马利模乘算法MM(x,y)设计为一个基本算法单元,目的是方便后续不断调用,最终整体实现图 3-2 所示的蒙哥马利型大数模乘模块。3.3.1 蒙哥马利模乘单元介绍如章节 2 所介绍的改进的蒙哥马利模乘算法,计算两个 k bit 位数的蒙哥马利模乘至少需要到 k 个处理时钟,通过观察章节 2 中 MM(x,y)算法流程里的步骤 2,发现该算法的基本运算过程
12、是从低位到高位,逐 bit 地处理数据,即改进算法采取的是全串行处理流程,一个时钟仅进行1 bit 的数据处理。当处理的数据位数较小时,该算法是比较有效的,所耗时钟周期也较少,然而对于现在的密码算法来说,处理的都是位数较长的数据,例如RSA 应用中就需要 1024 bit 以上的大整数相乘,因此该算法在处理位数较长的两个数的模乘计算时,计算速度会较慢。本文通过设计使得该算法能够在一个时钟周期内完成多位数的数据处理,即在同一个时钟内完成多次的乘法、加法以及移位处理,能够有效地提高算法的效率。3.3.2 蒙哥马利模乘单元模块设计本设计中,难点集中在蒙哥马利模乘运算单元模块中,完成对此部分的模块化工
13、作后,即完成了上文介绍的改进蒙哥马利模乘算法中的 a=p+x(i)y 部分,在模乘实现的主程序中通过不断循环调用此单元模块,实现对数据的逐位计算处理,提升运算处理效率。图 3-3 展示了蒙哥马利模乘算法单元的模块化程序设计框图。71北京电子科技学院学报2022 年图 3-3 mm_r2mm 模块程序流程图本文将此程序记为“mm_r2mm”。在模块中,首先对于数据进行初始化处理,将结果 S、位标志符 i 赋 0;再判断乘数对应的位是否为 1,为1 则将输入的乘数 y 与 S 相加处理,结果赋值给新 S,否则 S 值保持不变;再判断 S 的最低位是否为 0,也就是对 S 值进行了一个奇偶判断,若为
14、 0,则通过将 S 值右移一位来实现除 2 计算,不为 0 则将 S 值与模数 m 值相加,所得值赋给新 S 后再进行右移一位操作,完成单次的数据处理,最后将结果 S 的值返回,此即完成整个数据处理流程。单个模块单元在一个时钟周期内可以完成对于 1 bit 数据的处理工作,图 3-4 展示了双模块设计方案,用以说明在运算过程中具体的调用方式,便于理解分析。图 3-4 双模块数据处理流程其中:xsel和 xsel+1 分别为输入数据 x的对应位。双模块思想通过将模块单元 mm_r2mm_0 中的输出数据 So 作为模块单元 mm_r2mm_1 中的输入数据 Si,再将模块单元 mm_r2mm_1
15、 中的输出数据 So 作为模块单元 mm_r2mm_0 的输入数据 Si。这一操作实现了模块单元间的数据连接传递,将运算结果传递到下一次计算中,保证运算处理的连续性,配合步进信号对数据位进行选择控制,循环实现迭代运算,直至处理到数据的最后一位。表 3-1 说明了步进控制信号在数据选择时的作用,展示了具体的数据位处理过程。表 3-1 步进信号 Sel 与各处理位数的关系步进信号 Sel 值mm_r2mm_0mm_r2mm_1001223445.K-2K-2K-13.4 蒙哥马利模乘模块总设计实现本部分介绍改进后的蒙哥马利模乘算法,即MM(x,y)的设计实现过程,以此实现蒙哥马利模乘计算功能,具体
16、流程如图 3-5 所示。表 3-2 说明了在程序框图中出现各定义值及其在程序中的作用,方便对程序流程进行解释说明。表 3-2 框图中各信号定义及作用信号名称作用req启动信号,控制运算程序sel步进选择信号,控制模块程序输入sid_rmm_r2mm_0 模块输入sid_wmm_r2mm_1 模块输出res输出运算结果val输出结果标志位配合表 3-2 的说明,对程序流程的介绍如下:第一步对于程序的启动条件进行判断,当req 启动信号值为 1 且步进选择信号为 0 时(数81第 30 卷大数模乘硬件模块的研究与实现 图 3-5 蒙哥马利模乘模块总程序框图据可从最低位开始处理),满足启动条件,此时进行 3.3.2 章节中模块程序的处理(mm_r2mm_0/1),进行数据的迭代处理,同时将 sel 步进选择信号进行 sel=sel+2 的处理,同时再将第 1 个模块单元 mm_r2mm_0 的输出值作为第 2 个模块单元 mm_r2mm_1 的输入数据,实现单次数据处理的传递,再将 mm_r2mm_1 的模块输出值 sid_w 赋给 mm_r2mm_0 的模块输入值 sid_r,完成一次步进
