一种适用于FPGA实现的Montgomery模乘设计方法

摘　要：密码技术是保障信息安全的核心技术，其中公钥密码得到了广泛应用，其基本运算中的乘法运算是最耗时、最关键的运算，设计高效的乘法器对公钥密码的有效实现具有重要意义。为提高公钥密码的计算速率，设计了一种高效且适合于现场可编程门阵列（Field Programmable Gate Array，FPGA）内并行计算、多核调用的Montgomery模乘设计方法，该方法通过预计算的方式减少一次模乘计算耗用的时间，通过查表替代实时计算的方式减少对FPGA内部逻辑资源的占用，详细介绍了所研究、设计的内容及方法的思想、原理和工程实现结果，并从FPGA的资源和速度2个方面与其他文献进行了对比分析，给出了对工作的总结和未来应用展望。

内容目录：

0　引　言
1　Montgomery模乘运算
1.1　基本的Montgomery模乘算法
1.2　基于流水线乘法器的FPGA实现Montgomery模乘方法
1.3　基于CSA模乘加法器的FPGA实现Montgomery模乘方法
2　改进后基于预计算方式实现Montgomery模乘方法
3　实现结果及性能分析
4　结论与展望

０ 引　言 

保障信息安全的核心技术是密码技术，密码技术为解决信息安全问题提供了重要的科学途径，其中公钥密码解决了传统对称密码面临的密钥分发、密钥管理和提供过程中不可否认性的难题，在加/解密、数字签名等方面得到了广泛使用，在密码学中有着持续的发展潜力和良好的应用前景。 

传统的公钥密码算法有椭圆曲线加密算法（Elliptic Curve Cryptography，ECC） 和RSA密码算法两种，主要依赖于公钥基础设施建设，由具有绝对公信力的证书认证中心为用户颁发数字证书，并将其作为安全凭证，依赖数字证书和用户私钥，对要传输的信息进行签名和加密，以此保障信息的安全传输。为避免传统数字证书颁发和验证引起的效率问题，产生了标识密码学理念，该理念提倡将用户的邮箱、地址等身份标识直接作为用户公钥，无须数字证书即可确保公钥的可靠性，让密码方案更加轻便高效。随着我国自主设计的商用标识密码SM9成为行业标准，标识密码成为公钥密码领域内的焦点，并得到广泛的应用，众多学者更是进一步为标识密码引入更为丰富的功能与安全属性。

目前，常见的公钥密码算法设计无论是以 SM9为代表的标识密码算法还是传统的ECC、RSA密码算法，均以模算术运算为基本运算规则，其操作数通常是大整数，具有运算量大、耗时多的弊端，其计算速度成为制约公钥密码推广的瓶颈。其中，RSA密码算法的基本运算由一系列的模乘构成，ECC密码算法的有效实现依赖于椭圆曲线群上的点乘与点加等运算，标识密码算法中涉及复杂的数据结构和数学运算的双线性对，是构造基于身份标识的加密机制的关键技术。因此，模算术运算效率的提升决定了公钥密码系统的运行效率和快速推广的能力，其中模加、模减等运算性能是模乘的数十倍，设计出高效模乘乘法器一直是公钥研究领域的关注焦点。Montgomery模乘算法是一种非常高效的模乘算法，该算法使用一系列的加法和除2来代替取模阶段的模除运算，因此该算法很适合用硬件实现，通过灵活的资源配置可实现并行计算，提高算法的执行效率。

FPGA作为通用可编程芯片，内部集成了丰富的可编程逻辑资源及随机访问存储器（Random Access Memory，RAM）资源，成为高速、高效实现密码算法的绝佳选择，具有可实现并行计算、灵活编程的优点。

本文结合FPGA内部基本结构单元的特性、资源分布特性及公钥密码算法的运算特点，在速度和资源（即面积）两个方面进行优化以寻求二者的折中平衡，设计了一种预先计算并以查表方式快速高效实现Montgomery模乘的方法。

1  Montgomery模乘运算

Montgomery模乘算法主要用来避免模乘操作或者约简中耗时的求逆运算，本文对几种较常规的Montgomery模乘算法的实现方式进行了简要介绍。

1.1　基本的Montgomery模乘算法

Montgomery 模乘算法的主要思想是通过简单的移位操作来代替除法，其基本思想是计算原始的算法1如下：

其中，M为K bit的整数，即R为整数，通常取且R>M，X<R，Y<R；为R模M的逆，即 T，u和P为计算过程的变量。

1.2　基于流水线乘法器的FPGA实现Montgomery模乘方法 

常用的Montgomery模乘运算采用流水线乘法器实现的一般方法如下：将长度为K bit的数据按照长度r（K可被r整除）分割为L个数据， 分割后的数据按照权重从小到大依次添加下标进行表示。例如，X可以分割为则P 可以分割为则

遵循1.1节对各计算要素的描述，基于流水线乘法器的Montgomery模乘算法如下：

其中，M为K bit整数，D，m和P为计算过程的变量。

1.3　基于CSA模乘加法器的FPGA实现Montgomery模乘方法

文献[5] 对Montgomery模乘算法进行了改进，设计了一种基于多步CSA加法器实现的Montgomery模乘计算方法，相当于在算法2的基础上将分割字长定为1 bit（即r=1，L=K），该设计通过在一个时钟内做多次CSA加法迭代运算，达到降低一次模乘运算过程所需时钟个数的目的，进而提高模乘运算的速度。

遵循1.1节对各计算要素的描述，基于CSA模乘加法器的Montgomery模乘算法如下：

其中，M为K bit整数，A和P为计算过程的变量。

以上算法将模乘运算简化分解为K个K bit大数的加法，将乘法运算完全转换成加法运算。与乘法运算相比，加法运算更适用于通过FPGA芯片来进行工程实现，同时文献[5]在此基础上，通过在一个时钟内自主进行步长调整完成多次累加的方式，提高了工程实现的执行效率及灵活性。此外，该设计方法中模乘的实现仅使用通用逻辑资源，不依赖任何FPGA提供的IP核，具有很好的可移植性。 

２ 改进后基于预计算方式实现Montgomery模乘方法

在实际的工程应用中，为提高公钥密码算法的计算效率，对应用端提供更快速、高效的密码服务，通常需要在单一芯片中例化多个公钥算法核，以进行多核调度使用，而单个公钥密码算法在执行过程中，也会反复多次、尽可能多地并行调用底层Montgomery模乘运算模块以完成乘法计算，因此如果能通过减少模乘运算所需的时钟周期数的方式提高单算法核效率、 减少或均衡利用FPGA硬件资源，那么就可以使单芯片内集成更多的算法核，对算法计算整体性能的提高起到重要作用。 

算法2和算法3均能在一定程度上达到较高效的工程应用效果，对这2种设计方法进行进一步分析，算法2在一次乘法运算内需进行 2×L次r bit 数据与K bit数据相乘，在公钥算法中K值通常较大，自行设计的长位宽乘法难度大、对开发人员能力的要求较高且通常效率较低，而FPGA提供的乘法器IP核位宽有限，以 Xilinx 公司的 XC7K325T 芯片为例，其提供的乘法算法核最大仅支持64 bit×64 bit的运算，无法直接支撑现有公钥算法的长位宽大数运算的需求，因此，只能选择先拆解再拼装的方式进行大数运算。采用芯片自带乘法器的设计方法，一方面大大增加了设计复杂度，且从低位乘法 拼接成高位乘法的计算过程需要耗费较多的时钟周期；另一方面FPGA芯片内部集成的乘法器资源有限，而在高速计算应用场景下为了提高计算效率，通常需在单一的设计中包含多个例化的Montgomery模乘模块，以支撑在单一算法核中多路模乘计算的并行运行或支撑多个公钥密码算法核各自独立的并行运行，芯片中自带乘法器的硬件资源难以满足该并行使用需求， 因此工程实用过程难以达到预期效果。而算法将算法2中的乘法完全转换成加法，并以分步长的方式在一个时钟周期内完成多步加法运算，运算设计被大幅简化，仅需实现多个长位宽加法即可，且不再需要依靠FPGA内部有限的乘法IP核资源，具有可忽略芯片型号、便于在不同芯片间快速移植的优点。但同时也面临以下问题：一方面，与乘数位宽相等的加法步数计算需占用的FPGA内查找表（Look Up Table，LUT）等逻辑资源较多，大数乘法及多个乘法器例化时耗用的资源成倍增长，难以支撑高速率应用场景下高速、多核并行的计算需求；另一方面，该方法依靠在一个时钟内完成多步加法计算来减少一次运算所需的时钟数，虽然有很多关于大整数加法在FPGA内快速实现的研究，但因其进位链长，通常所能运行的时钟频率不高，而将多步加法计算集中在一个时钟周期内完成也将降低设计整体的工作频率。

本文在继承算法2与算法3优点的基础上，突破其工程实现的局限，对模乘的运算环节进行了重新拆分和整合，提出了一种通过先预先计算、后查表的方式进行模乘计算的方法，即基于算法2，预先计算长度为K bit的大整数M、X 分别与字长为r的所有整数相乘的结果，生成预计算的2个预计算表，每个表的容量均为后续运算只需对2个预计算表进行算法查找，并基于算法进行相应的加法操作、r bit的小位宽乘法操作即可完成1次Montgomery模乘计算。

遵循1.1节对各计算要素的描述，基于预计算方式的Montgomery模乘算法如下（其中L=K/r）：

其中，M为K bit整数，D，m和P为计算过程的变量。

计算过程如图1所示。

图1　改进后的Montgomery模乘实现

改进后的算法将1次Montgomery模乘运算分解为预计算查找表的生成过程和循环迭代的加法、移位、小数乘法、查表运算过程2个部分。将原本复杂的数学计算流程简化为简单的查表流程，在减少整体计算所需时钟周期的同时，将原算法3中对FPGA逻辑资源的大量占用部分转化为丰富的RAM资源，达到对FPGA内可工程实现资源的均衡利用的目的。

在FPGA中，加法、移位、小数乘法和查表等运算的执行效率高，因此预计算查找表的生成方式是本设计方法的关键所在。本文以一种对 256 bit 被乘数进行移位、每个时钟周期内2个大整数相加的方式设计了一种查找表的快速生成方法（4个时钟周期完成1次查找表的生成计算），其他更优秀的设计方法将更快捷、高效地生成预计算查找表，如采用更高效率的加法器、编码器等设计，能更有效地提高模乘运算整体的运行速度，但该项设计不在本文的研究范围内，故不对其一一进行说明。由于在FPGA中，对数 据的倍乘运算可以采用移位的方式简单实现，非倍乘部分可采用倍乘结果结合加法运算实现，因此本设计将生成预计算表的乘法转化为一系列的移位和加法操作。同时，考虑到预计算表的容量与r的取值相关，预计算表含个数据，即r的取值关系到预计算表大小及生成预计算表所需的时钟周期。若r取值过大，则预计算表耗费过多FPGA的存储资源及生成时间，且考虑到本设计方法中K应被r整除。当r取值为4时，乘法更易于转化为一系列的移位和加法操作，预计算表的计算生成方式更为简单，同时公钥算法中大数的长度普遍为4的倍数，综合分析将本设计方法中r的值固定为4较为合适。本文选取在ECC、标识等密码算法实现中常用的256 bit Montgomery模乘进行说明，以r取为4时，K bit的整数M的预计算表生成为例，其生成转换过程如图2所示。

图2 r值取4时以整数M为例的预计算表生成

由图2可知，被乘数的数值每发生1次变化，即可以生成预计算表。预计算表的生成过程通过简单移位和1次加法计算（耗用3组长整数加法的逻辑资源，各自独立实现2个长整数的 1 次相加）即可以完成，且每个过程的计算结果可以并行计算得出，在4个周期内即可以完成 1 个256 bit Montgomery模乘 4×256 bit 预计算查找表的生成，过程简单且高效。预计算表生成后， 再通过64次的查表并辅以简单的加法、1个乘数固定的4位小数乘法、移位等计算即可完成 1 次Montgomery乘法运算（从生成预计算表到 生成结果共耗用68个时钟周期）。

３ 实现结果及性能分析 

为分析本文所提出的设计方法的实现效果，分别在Xilinx 公司Virtex7系列的XC7VX330T器件和Virtex5的XC5VLX30T器件上，以256 bit Montgomery模乘为例对本文设计方法完成实际的工程设计，同时收集了其他文献中的同长度、多 种类型相关设计成果，以便进行性能的对比分析。 

本文所设计的模乘方法及其他文献中的相关工程实现的资源开销和性能情况如表1所示，分别从时钟频率、完成一次模乘所需要的时钟数和时间，以及硬件占用的资源开销和类型等 几项性能指标进行了详细的对比分析。

表1　资源开销和性能情况与其他文献的比较（位宽256 bit）

与文献[6]相比，本文设计方法在对LUT逻辑资源占用相差不大的情况下，能够以更高的工作频率、更少的时钟数将一次模乘的计算速度提升超过1/3，在同等硬件资源情况下，具有较明显的计算速度优势。与文献[7]相比，本文设计方法在仅使用文献[7]中约63%逻辑资源的 情况下，达到了文献[7]中超过90%的一次模乘速率，在多核并行调用时，具有达到相同计算速度所需资源面积更小的优势。且与文献[6]和文献[7]中大量采用可移植性差且面积受限的数字信号处理器（Digital Signal Processor，DSP）资源相比，本文设计方法采用了更易于移植且资源更丰富的RAM资源，在硬件资源的综合利用方面更贴近FPGA器件内部的结构特性，也更便于在芯片内例化更多的模乘模块。与文献[8]相比，本文设计方法在仅使用文献[8]中不到 20%逻辑资源的情况下，以更高的工作频率将一次模乘的计算速度提升了超过3.6倍，在计算速度和资源占用方面均具有较大优势。综合上述比对分析可知，本文设计方法在硬件资源的均衡占用、运算速率优化方面均有较大的优势， 且具有很好的可移植性，更适用于公钥密码算法对模乘多组例化、并行调度。 

4 结论与展望 

本文对Montgomery模乘算法原理进行了分析与改进，通过对已有的部分工程实现成果进行优化的方式，提出了一种提高Montgomery模乘计算效率的方法。以预计算的方式减少了单时钟周期内的复杂计算，提升了FPGA的工作时钟频率并降低整体计算耗用时间；通过查表替代实时大数计算的方式，平衡减少对FPGA内部LUT逻辑资源的占用。该方法在提高计算速度的同时，能够均衡地利用FPGA内部硬件资源，使得在单一芯片内可例化更多组Montgomery模乘模 块，即可以支撑单个公钥算法尽可能多地并行执行乘法运算，进而提高自身运算性能，也能更好地支撑在同等硬件资源情况下，单一设备内集成更多组公钥算法核，以提供更高效便捷的公钥密码服务。此外，模乘运算速率的提升打破了标识密码算法当前计算效率的瓶颈，为进一步取代传统公钥体制提供了有利支撑。

引用格式：刘贺,王小骥,刘星江,等.一种适用于FPGA实现的Montgomery模乘设计方法[J].信息安全与通信保密,2024(5):54-61.
作者简介 >>>
刘　贺，男，学士，高级工程师，主要研究方向为保密通信系统；
王小骥，男，学士，正高级工程师，主要研究方向为保密通信系统； 
刘星江，男，硕士，高级工程师， 主要研究方向为通信保密； 
杨　竞，男，博士，高级工程师， 主要研究方向为网络空间安全、密码学。
选自《信息安全与通信保密》2024年第5期（为便于排版，已省去原文参考文献）
重要声明：本文来自信息安全与通信保密杂志社，经授权转载，版权归原作者所有，不代表锐成观点，转载的目的在于传递更多知识和信息。