段晓毅 黄 烨 曹佳乐

北京电子科技学院,北京市 100070

RSA、ECC(Elliptic Curve Cryptography)算法是常用的公钥算法,而素数域上的模乘运算[1]是公钥加密算法中的基础算法。

但在密码体系的运算中,其运算操作数一般是任意大整数,即位数为256 bit 或以上的数据结构,算法复杂度较大,已经成为影响当前公钥加密体系发展的重要问题。

素数域中的模乘算法是最费时的计算,所以为了提升公钥密码系统的计算效率,选择计算速度快、资源耗费少的高效硬件模块非常重要[2]。

当前国内外对于大数模乘问题的研究方案大致可分为两种:第一种即利用各类基本算法及其改进算法,通过算法结构构建对应的硬件电路,实现大数模乘功能,例如加法型算法[3]、估商型算法[4]、蒙哥马利算法,其中又以蒙哥马利型算法应用范围最广,相继提出多种改进方式,实现效果良好。

另一种则从硬件结构出发,对于硬件架构进行重构,高效利用计算资源,提升模乘计算速度[5],以FPGA 细粒度映射技术为例[6],此在各类硬件载体上都有相关运用,例如通过加密智能卡实现[7]。

大数模乘在基础研究以及密码学等领域都有大量应用,特别是在公钥密码算法方面[8]。模乘通常情况下表示为:C =(A × B)mod N,其中A、B、N 都为k bit 二进制的大整数。

模乘运算由基本的乘法和计算余数的模运算简化组成,目前主要的运算形式有先计算乘法后再进行模简化运算,以及一边进行乘法同时进行模简化运算这两大类基本实现方式[9]。

若以更细化、更精准的处理方式来划分大数模乘的处理流程的话,大数模乘算法又可分为加法型算法、估商型算法、蒙哥马利型算法这三大类。

蒙哥马利型模乘算法是目前在硬件结构上用于快速实现模乘计算最适合的算法。

本文改进了蒙哥马利算法并将其实现。

蒙哥马利模乘算法是蒙哥马利在1986 年所提出的一种算法[10],主要是为了解决大整数模幂运算问题。

由于模幂与模乘运算可以互相转换,蒙哥马利模乘算法把部分积对任意的n 取模运算转化为对与n 互素的数基R 进行取模,通常都选R=2k,k 是非负整数。

由于R 比n 小得多,对数基R 的取模运算要比对n 的取模运算简单得多[11],所以蒙哥马利模乘算法在RSA 密码算法的研究中得到广泛的应用。

定义模乘算法为MM(x,y),如果模数m 是素数,且满足m>2,则存在一个元素2-1∈Fm,使得2 × 2-1mod m =1。

假设m 是一个k bit 位的素数,那么可以选择一个数R,使得R = 2k且满足x,y∈Fm其中x可表示为:

将式(2.1) 代入模乘计算表达式,得到下式:

由于基本的蒙哥马利模乘算法中不但包含基本的乘法、加法运算,还包含了模逆运算,并不利于计算机的硬件实现。

改进的蒙哥马利模乘算法通过对基本算式的重新表达,配合数论里的基本结论,巧妙避免了复杂运算,易于模乘计算[12]。

由数论知识可知用一个自然数去乘2-1有以下结论:

将式(2.2)中单次运算括号中的部分套用式(2.3),即可得到改进后的蒙哥马利模乘算法[13]MM(x,y),其算法流程如下所示:

改进后的蒙哥马利模乘算法结构简单,易于硬件描述实现,本文就以改进的蒙哥马利模乘算法MM(x,y) 为设计基础,实现蒙哥马利型大数模乘模块功能。

3.1 蒙哥马利型大数模乘模块外部总视图

本方案中的大数模乘模块的外部总视图如图3-1 所示:

图3-1 蒙哥马利型大数模乘模块外部总视图

输入:x、y、m

输出:C

x:参与模乘运算的乘数1,输入范围从1bit-4096bit。

y:参与模乘运算的乘数2,输入范围从1bit-4096bit。

m:参与模乘运算的模数,输入范围从1bit-4096bit。

C:模乘的输出结果, 输出范围从1bit-4096bit。

对于本文系统的输入数据x、y、m 来说,最大可以满足4096 bit,能满足现在对公钥算法强度的要求。

当要进行计算时,输入x、y、m,即可通过此模块计算得到结果C,即:C=x*ymodm,此为所要研究的大数模乘。

3.2 蒙哥马利型大数模乘模块内部结构设计

蒙哥马利型大数模乘模块的内部结构设计如图3-2 所示:

图3-2 蒙哥马利型大数模乘模块内部结构设计

本设计的运算处理步骤是通过四次调用改进的蒙哥马利模乘算法,并且每次调用中输入不同的数据,最终得到没有R-1影响的大数模乘。

在第一、二次调用中,将R2作为第二个乘数来进行代入计算(在相同模数m 的情况下,R2的数值不变,可以重复使用),这一步得到X′=X*Rmodm与Y′=Y*Rmodm;第三次调用中将得到的X′、Y′作为操作数再进行一次蒙哥马利模乘计算,得到S′=X*Y*Rmodm; 第四次调用中,1 作为另一个操作数被代入计算,R 与R-1即可相互抵消,最终得到大数模乘运算结果C=x*ymodm。

3.3 蒙哥马利模乘单元模块设计

如上文介绍,蒙哥马利型大数模乘模块实际上就是在不断重复计算蒙哥马利模乘算法的过程[14],所以设计大数模乘的关键就在于对于蒙哥马利模乘单元模块进行设计实现,也就是说将章节2 中提到的改进后的蒙哥马利模乘算法MM(x,y) 设计为一个基本算法单元,目的是方便后续不断调用,最终整体实现图3-2 所示的蒙哥马利型大数模乘模块。

3.3.1 蒙哥马利模乘单元介绍

如章节2 所介绍的改进的蒙哥马利模乘算法,计算两个k bit 位数的蒙哥马利模乘至少需要到k 个处理时钟,通过观察章节2 中MM(x,y) 算法流程里的步骤2,发现该算法的基本运算过程是从低位到高位,逐bit 地处理数据,即改进算法采取的是全串行处理流程,一个时钟仅进行1 bit 的数据处理。

当处理的数据位数较小时,该算法是比较有效的,所耗时钟周期也较少,然而对于现在的密码算法来说,处理的都是位数较长的数据,例如RSA 应用中就需要1024 bit 以上的大整数相乘,因此该算法在处理位数较长的两个数的模乘计算时,计算速度会较慢。

本文通过设计使得该算法能够在一个时钟周期内完成多位数的数据处理,即在同一个时钟内完成多次的乘法、加法以及移位处理,能够有效地提高算法的效率。

3.3.2 蒙哥马利模乘单元模块设计

本设计中,难点集中在蒙哥马利模乘运算单元模块中,完成对此部分的模块化工作后,即完成了上文介绍的改进蒙哥马利模乘算法中的a=p+x(i)*y部分,在模乘实现的主程序中通过不断循环调用此单元模块,实现对数据的逐位计算处理,提升运算处理效率。

图3-3 展示了蒙哥马利模乘算法单元的模块化程序设计框图。

图3-3 mm_r2mm 模块程序流程图

本文将此程序记为“mm_r2mm”。

在模块中,首先对于数据进行初始化处理,将结果S、位标志符i 赋0;再判断乘数对应的位是否为1,为1 则将输入的乘数y 与S 相加处理,结果赋值给新S,否则S 值保持不变;再判断S 的最低位是否为0,也就是对S 值进行了一个奇偶判断,若为0,则通过将S 值右移一位来实现除2 计算,不为0 则将S 值与模数m 值相加,所得值赋给新S 后再进行右移一位操作,完成单次的数据处理,最后将结果S 的值返回,此即完成整个数据处理流程。

单个模块单元在一个时钟周期内可以完成对于1 bit 数据的处理工作,图3-4 展示了双模块设计方案,用以说明在运算过程中具体的调用方式,便于理解分析。

图3-4 双模块数据处理流程

其中:x[sel]和x[sel]+1 分别为输入数据x的对应位。

双模块思想通过将模块单元mm_r2mm_0 中的输出数据So 作为模块单元mm_r2mm_1 中的输入数据Si,再将模块单元mm_r2mm_1 中的输出数据So 作为模块单元mm_r2mm_0 的输入数据Si。

这一操作实现了模块单元间的数据连接传递,将运算结果传递到下一次计算中,保证运算处理的连续性,配合步进信号对数据位进行选择控制,循环实现迭代运算,直至处理到数据的最后一位。

表3-1 说明了步进控制信号在数据选择时的作用,展示了具体的数据位处理过程。

表3-1 步进信号Sel 与各处理位数的关系

3.4 蒙哥马利模乘模块总设计实现

本部分介绍改进后的蒙哥马利模乘算法,即MM(x,y) 的设计实现过程,以此实现蒙哥马利模乘计算功能,具体流程如图3-5 所示。

图3-5 蒙哥马利模乘模块总程序框图

表3-2 说明了在程序框图中出现各定义值及其在程序中的作用,方便对程序流程进行解释说明。

表3-2 框图中各信号定义及作用

配合表3-2 的说明,对程序流程的介绍如下:

第一步对于程序的启动条件进行判断,当req 启动信号值为1 且步进选择信号为0 时(数据可从最低位开始处理),满足启动条件,此时进行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,完成一次步进中两位数据处理结果的传递,传递进行下一次步进处理;

第二步进行位数判断处理,如果运算到数据的最后两位,即满足这一判断条件,就说明了运算处理已接近完成,此时再进行最后一次模块单元处理,完成后的迭代运算结果也就是模块单元mm_r2mm_1 的输出值sid_w,若不满足则返回到模块程序,继续进行数据处理;

第三步进行一次条件减法处理,如果模块输出值sid_w 大于等于模数m 的值,则将sid_w-m的值作为最终的运算结果赋值给res,否则直接将作为运算结果赋给res;最后将输出结果标志位val 置1,步进选择信号sel 置0,结束本次程序运算。

本程序设计的主要运算处理集中在对数据逐bit 位进行迭代运算的处理过程,也就是上文提到的“mm_r2mm_0/1”模块程序,如果对于算法运算处理效率不满意,理论上是可以通过增加模块单元的个数,改变步进,使得在一个时钟周期内进行多次数据处理,进而减少总的迭代次数,减少总的时钟周期,进而提升运算效率。

从理论上分析,模块的单元数量与运算处理效率是成正比的,模块单元数量越多,运算处理效率越高,4 单元、8 单元、甚至16 单元都是可行的,但是过多引入模块单元会引入更多的中间变量,在定义与调用时不利于整体程序的实现,同时在实际应用时会占用更多的存储资源。

综合考虑资源消耗与处理效率,本文设计将模块的单元数量设置为2。

需要说明的一点是,为了便于在功能仿真阶段中通过时序图来准确对比出时钟消耗数,在本设计中引入的启动信号req 与输出结果标志信号val 也发挥了一定作用,通过观察输出波形中的指定返回信号,即可快速统计出在功能仿真环节运算消耗的总时钟数,关于这一内容以及功能仿真所需要的相关文件的编写设计将在下一章节作具体介绍说明。

4.1 算法基本结构的正确性验证

模乘运算应用最基本的形式为X*Ymodm,通过模乘算法的基本定理易知:如果将计算X 与Y 的值互换后,计算结果是不会改变的。借鉴这一想法,通过互换x、y 的值,观察最终的运算结果是否保持不变,在一定程度上也能够说明算法运算结构的正确性。

故本文在功能仿真环节将x 与y 值互换后进行运算仿真,仿真结果如下图4-1、4-2 所示,结果未发生改变,说明了算法结构的正确性。

图4-1 x、y 值未互换仿真结果

4.2 算法运算结果的正确性验证

本文设计的蒙哥马利型模乘法器能够完成形如x*y*R-1modm的算法运算,其中R 为常数,取值为:R= 2k,与数据位数的选择有关。

通过观察其算法形式可以得出一个验证方法:如果将y 的取值确定为2k,那么算法的运算形式就转换为x*2k*2-kmodm,由于x 值小于模数m,则可知最终计算值为x。

在这一想法的基础上,通过设定一组低位数据来进行验证运算,如果系统仿真运算结果与理论分析一致,则系统运算结果的正确性就得到了保障。

图4-2 x、y 值互换后仿真结果

在这一步的验证中,设定x=10000000,m=11110001,对应十六进制数x=80,m=F1,本应设置y=28=256,但由于本文设计中x、y、m应满足位数相同这一条件,故只能设置y=27=128,最终的运算结果为:

通过Modelsim 软件进行测试,仿真测试结果如下图4-3 所示,实际测试结果与理论分析值吻合,进一步说明了系统运算的正确性。

图4-3 运算正确性验证仿真测试图

4.3 Modelsim 功能仿真分析

在上一部分中该算法模块运算正确性得以验证,确保该系统的计算功能在算法结构上的正确无误,但仅仅停留在对于小位数的计算处理中,因此在本部分中对于本文所设计的蒙哥马利模乘器,在Modelsim SE 10.4 软件中输入测试多组数据,展示计算处理功能的完备性。

首次输入的测试数据类型为256bit 位二进制数,具体数值如下:

同时为了本系统的测试数据的完备性,以及展现系统在处理不同位数的大数模乘时运算时间上的差异性,本文又在原来256 bit 位的基础上,另行测试了以下三组数据,分别从512 bit、1024 bit、4096 bit 不同位数展现本系统的仿真效果,配合启动信号req 以及输出结果标志信号val,即可得出具体的仿真运算处理时间,此内容由于在之前的部分中已经进行过展示,因此在本部分就不再赘述。

本部分主要展示所得的具体仿真结果,分别如图4-5、图4-6、图4-7 所示。

图4-4 256 位仿真测试结果

图4-5 512 bit 仿真测试结果

图4-6 1024 bit 仿真测试结果

经过设计测试,蒙哥马利大数模乘计算系统理论上能够计算的最大位数为4096 bit 二进制数,通过修改相关位宽K 参数,即可完成限定位数内任意位数的大数模乘运算,在文本文件中修改输入测试数据x、y 以及m 的具体数值,即可通过仿真任务窗口进行相关计算数值的输出展示。

当前各主流公钥密码算法如RSA,以及各类椭圆曲线加密算法都主要涉及到大数之间的运算,尤其是模乘、模幂计算,而此类计算资源消耗大、运算处理时间长,成为制约系统处理速度的瓶颈。

本文则以蒙哥马利模乘算法为理论依据,研究设计了大数模乘模块,以Verilog 硬件描述语言编写算法程序,并利用Modelsim 软件进行仿真功能测试,最后利用Altera 对此设计进行综合,完成研究。

与已有的大数模乘研究方案相比,本文设计具有以下优点:

1. 算法设计原理简单,设计结构简介,易于硬件实现;

2. 将串行改进为并行运算,利用模块化思想使得数据处理效率得到较大提升,理论提升了二倍的处理速度;

3. 在功能仿真环节,通过编写测试文件的方式读取输入数据,简化了数据输入形式;

4. 数据处理位数区间充沛,可完成1 至4096 bit 范围内的蒙哥马利模乘计算,并将运算结果输出反馈。

通过总结与比较,现阶段本模块还存在一些不足需要改进完善,需要完成模幂运算,以进一步满足RSA 等密码算法的大数运算要求。

猜你喜欢蒙哥马利数模位数基于FMEA分析的数模混合电路多道脉冲幅度控制算法电子设计工程(2022年20期)2022-10-28蒙哥马利小哥白尼(军事科学)(2021年6期)2021-11-02五次完全幂的少位数三进制展开数学年刊A辑(中文版)(2021年4期)2021-02-12连续自然数及其乘积的位数分析喀什大学学报(2020年6期)2021-01-28整车数模开发流程解析汽车实用技术(2019年20期)2019-11-06Pro/E软件在机械设计管道数模建立中的应用机械管理开发(2018年11期)2018-11-28遥感卫星CCD相机量化位数的选择航天返回与遥感(2014年4期)2014-07-31叶丽娅的年龄读者·校园版(2013年10期)2013-05-14蒙哥马利与艾森豪威尔打赌青年文摘·上半月(1990年8期)1990-01-01蒙哥马利元帅的军事人才观军事历史(1988年5期)1988-08-20