基于组合式二维字串行处理器的GF(2m)乘法和平方实现及其性能优化

.Σ埃及信息学杂志23（2022）239用于GF ~（2m）上乘法和平方的组合式二维字基串行输入/串行输出脉动处理器Atef Ibrahima，b，a沙特阿拉伯Alkharj Sattam Bin Abdulaziz王子大学计算机工程和科学学院计算机工程系b加拿大不列颠哥伦比亚省维多利亚维多利亚大学ECE系阿提奇莱因福奥文章历史记录：收到2020年2022年1月9日接受2022年1月28日在线提供保留字：字串行脉动阵列格林密码处理器有限域乘法有限域平方超低功耗器件嵌入式消费电子设备ASICA B S T R A C T本文提出了一种组合的二维字为基础的串行输入/串行输出脉动处理器域乘法和平方GF（2m），以提高硬件利用率和功耗。建议的处理器提取通过应用非线性调度和投影函数的算法依赖图。提取的处理器具有可扩展性，使设计人员更灵活地控制处理器的大小和执行时间。本文提出的组合式二维字串行设计和现有最佳设计的ASIC实现结果表明，本文提出的结构实现了相当大的面积节省和能耗节省，分别达到93.7%和98.2%。这使得它更适合于资源受限的消费电子设备中的加密原语的受限实现，例如手持设备、可穿戴和可植入医疗设备、智能卡、无线传感器节点、物联网（IoT）中的受限节点和射频识别（RFID）设备。©2022 The Bottoms.出版社：Elsevier B.V.代表计算机与信息学院开罗大学。 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。1. 导言和相关工作有限域算术运算在许多应用中是重要的，例如RSA密码学[1]、癫痫曲线密码学（ECC）[2]、纠错码[3]和基于配对的密码学（PBC）[4]。GF（2m）域乘法在模幂、求逆/除法等域运算中是非常重要的，大多数先前报道的GF（2m）上的乘法器具有高面积和时间复杂度，这使得它们在资源受限的消费电子设备中的实现具有高度挑战性[5因此，重要的是要多...* 通讯作者：沙特阿拉伯阿尔哈尔杰萨塔姆·本·阿卜杜勒阿齐兹王子大学计算机工程与科学学院计算机工程系，16278阿尔哈尔杰。电子邮件地址：aa. psau.edu.sa，atef@ece.uvic.ca开罗大学计算机和信息系负责同行审查。针对这类应用的plier架构。字串行乘法器结构在文献中报道，以解决这个问题。它们在速度和面积复杂性之间进行权衡，因此它们为设计人员提供了更大的灵活性，以达到所需的设计。字串行乘法器的结构分为四种类型：串行输入/串行输出（SISO）结构、串行输入/串行输出（SIPO）结构、串行输入/串行输出（PISO）结构和可扩展结构。文献[9文献[14文献[18]中报道了具有PISO结构的字串行T型高斯正规基（GNB）乘法器。[19-25]中报告了可扩展的脉动乘法器结构模幂运算是密码算法的基本组成部分。有两种用于计算模幂的二进制方法：最高有效位（MSB）优先方法和最低有效位（LSB）优先方法。在LSB优先方法中，模乘和平方操作可以同时执行以减少处理时间。文献中有许多尝试将乘法和平方运算结合在统一的结构中，以提高性能和硬件利用率[7，8，26]。据我们所知，建议的组合乘法器平方器结构是专用的https://doi.org/10.1016/j.eij.2022.01.0011110-8665/©2022 THE COURORS. Elsevier B.V.代表开罗大学计算机和信息学院出版。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.comA. 易卜拉欣埃及信息学杂志23（2022）239240.Σð Þ¼ð ð Þ ð ÞÞ ð Þ←þð Þ¼ð ð Þ ð ÞÞ ð Þ.Σ.¼M-1Σ·· ·←ð·· ·Þ1 0← ð···ÞX.布勒姆日ð Þ ð Þð Þ¼M-1.Σ1 0G xJj1M-14：ri <$ri-1di-1ci-1Jð Þ ð Þ ð Þthth1 0JJ用于高速应用并且不针对资源受限的应用。在本文中，我们提出了基于字的二维SISO脉动处理器的组合域乘法和平方GF（2m）。它计算乘法和平方运算，同时使用一个统一的硬件核心。所提出的处理器可以被管理为具有最小的尺寸，以适应所有的资源受限的应用程序，有更多的限制面积和功耗。此外，它具有规则的结构和局部互连，使其更适合于VLSI实现。通过将非线性调度和投影函数应用于算法依赖图[27-32]来提取所提出的处理器这些非线性函数提供了控制处理器工作负载和执行时间所需的灵活性。本文的组织结构如下。第二节对GF_（2m）上的多项式乘法平方组合算法作了简要的说明。第3节开发了相关的依赖图（DG）。第4节介绍了探索的二维字为基础的SISO脉动处理器。 第5节提供了所提出的设计和现有的字串行设计的最佳面积和延迟的复杂性。第6节结束了这项工作。2. 多项式乘平方组合算法G F. 2米长GF（2m）上乘法和平方的算法1.输入：C x、D x和G x多。输出量：RxCx：DxmodGx平方输出：Q xC x：C xmodG x初始化：R0<$0;Q0<$0;C0 <$Cx;D<$Dx;G<$Gx算法：1：16i6m2：Ci¼Ci-1：xmodGx3 ： Ri←Ri-1di-1Ci-14 ：QiQi-1ci-1Ci-15 ：结束算法2 GF（2m）上乘法和平方的比特级算法输入：Cx、Dx和Gx多。输出：R×C×D×设Cx和Dx是GF2m中的两个多项式，Gx是标准基表示中的不可约多项式.这些多项式可以表示为：R0r0Q0¼。q0Mr0r00 00···q0q0←0 ···00C0¼。c0···c0c0←0cm-1·· ·c1c0M-1Cx1/4M-1ci xið1ÞD←dm-1···d1d0G gm-1g1g 0算法：Dx dixi 21/41：16i6m2：对于06j6m- 13：cið Þ ¼gix我ci-15：qi<$qi-1ci-1ci-1其中c i; d i; g i2 GF<$2GF。GF2上的多项式乘法和平方可以定义如下：RxCxDxmodGx4QxCxCxmodGx5可以使用Choi在[7]中提出的组合算法（算法1）来计算乘积Rx和Qx。该算法计算三个部分多项式Cx、Rx和Qx。变量C i、R i和Q i用于指示在迭代i时，Cx;Rx和Qx。di-1和ci-1分别表示输入多项式Dx和Cx的系数。初始变量R0和Q0被赋值为零并且初始变量C0被分配输入多项式Cx的系数。在for循环的每次i迭代中，中间变量更新如下：变量Ci通过左移Ci-1并使用不可约多项式G约化来更新。● 通过将Ci-1乘以系数di-1并将获得的结果与Ri-1相加来更新变量Ri。● 变量Qi通过将Ci-1乘以系数Ci-1并将获得的结果加到Qi-1来更新。j j j6：结束7：结束算法2是算法1的比特级表示。Cij1代表了在i处的C位反覆项目。还有ri和qi分别表示第i迭代时R和Q的第i位。注意，hj1i表示j1要以m为模进行约简。3. 依赖图算法1是正则迭代算法（IRA）的示例。参考文献[27]展示了如何获得RIA算法的依赖图（DG）。 图图1示出了基于算法2的DG，用于GF2m中的组合多项式乘法平方。图1中的节点表示二维整数域D中的点，其中索引i和j分别指示行和列，并且具有范围：16i6m;06j6m-1 206 m该图是针对当m 5比特时的情况。该算法具有三个输入变量C、D和G;以及两个输出变量R和Q.变量R、Q和G由垂直线表示。变量C由斜线（红线）表示输入比特XM●ð3Þ1/4JXJA. 易卜拉欣埃及信息学杂志23（2022）2392410C140C240C340C44001 C1240C24043C450C4407 C5840963¼¼---WM-1WWJJjnplmm，i-1，，m-1-j，17d0，c0d、 c其中16 i 6 m l和l6 j d_m_e，MUX M_C和M_G将存储在FIFO-C中的计算的C字和存储在FIFO-G中的G字传递到脉动阵列，每个时间步长一个字。这些字与计算的R和Q字一起存储在FIFO-R和FIFO-Q，和的广播话的Ci-1;Di和-i1i 1Ci-1;kwi6kkk k1 kw;16k6dme-1，用于更新i-1j图7所示的fer在图6的脉动阵列的所有浅蓝色PE中被启用（y0），以水平地传递计算出的w位Ci-1;kwi6图6右侧所示的信号z等于零，以将图3的DG的右边缘所示的C的零值馈送到脉动阵列。在剩余的时刻，该控制信号等于1。6. 通过时间实例nP，m，jm=1-1k，得到的输出图第七章浅蓝色PE SISO二维脉动阵列的细节R和Q的字将以字串行方式加载，一个在每个时间步，分别在图5所示的寄存器R和Q中。i-1m-1ci-1di-1ij+1rjii-1ji-1jIjggi-1j这里应该考虑的一个重要注意事项是，R、Q和G的垂直w位字以及Ci-1、Di-1和Ci-1的水平w位字在收缩周期数组如图 所 示。第 六章这由D寄存器表示（正方形）显示在这个图中。这使得一个时间步长的差异之间的PE以上的D寄存器（正方形）和他们下面的 这个时间差是由于C的中间字，由图中所示的系统阵列的左列（蓝色单元格）引起的。 6、从第二个开始生产时间步长和R、Q、G、Ci-1、Di-1和Ci-1的字应该被延迟，如图6所示，以同步操作。这导致完成组合乘法/平方计算所需的额外时间步长，如之前在等式10中所解释的。（八）、5. 复杂度比较在本节中，我们比较了所提出的二维图八、浅橙色PE详细说明SISO二维脉动阵列。字串行乘法平方器结构和最佳RCQ和CCCCRQCQA. 易卜拉欣埃及信息学杂志23（2022）2392462¼¼¼¼¼¼¼¼¼¼W现有的字串行乘法器结构[12，17，33，34]的面积和时间复杂度。该面积是根据三态缓冲器、2输入与门、2输入异或门、2输入多路复用器和触发器的数量来估计的。时间由延迟和关键路径延迟（CPD）表示。比较结构的估计面积和时间复杂度在表1中给出。本表中使用的符号可定义如下：1. w是字的大小2. TA是2输入与门的延迟。3. TX是2输入XOR门的延迟。4. TMUX是2对1 MUX的延迟。5. F1/47m6. F2¼2w2 2wdm=w 4w 17. F3¼2w3wdm=w2w8. L1¼w=we2dm=we9. s11¼T A已记录日志2we100TX10. s2¼TA2TX11. s3¼TAATX12. s41/4带宽1/4带宽A1/4带宽X1/4带宽MUX为了公平比较，我们为每个设计结构添加了输入/输出寄存器的面积复杂度。表1中的设计是使用VHDL代码描述的，并且针对m409和w（8;16; 32）的不同值进行了合成，以获得真实的实现结果。我们用于合成NanGate（15 nm，0.8 V）Open Cell Library和Synopsys工具版本2005.09-SP2。 我们对所有使用的基元使用典型的角点（VDD=0.8 V和Tj25°C）和单位驱动强度。所得结果列于表2中。用于比较所提出的和现有的字序列设计的设计度量可以定义如下：1. 延迟：完成一个操作所需的时钟周期总数2. 面积（A）：是以2输入NAND门的等效面积表示的估计设计面积。3. CPD：是合成的关键路径延迟。4. 时间（T）：是完成单个操作所需的总计算时间。5. 功率（P）：是在1 KHZ下获得的消耗功率6. 能量（E）：是通过功率（P）乘以总计算时间（T）获得的消耗能量。为了进行公平的比较，[12，17，33，34]的比较乘法器结构应该依次执行乘法和平方操作，并且这使这些设计的时间和消耗功率/能量的合成结果加倍，如表2所示。通过观察表2中的结果，我们可以得出以下结论：1）所提出的设计结构在不同的w值下节省了面积（在w值下的百分比从9.1%到92.6%不等 8，w时为11.6%至93.7%16，和20.7%至91.9%，在w32）比现有的设计。2)Pan[12]的设计在w8时比其他设计（包括所提出的设计）节省了40%的时间。3)Xie[17]的设计比其他最佳设计（包括建议的设计）节省了0.6%和26.5%的时间（分别在w16和w（4）在不同的w值下（w= 8时为9.6%~ 97.3% ， w = 16 时 为 17.1%~ 97.5% ， w =32 时 为 29.0%~98.2%），本文提出的设计结构比现有的设计节能正如我们所注意到的，所提出的设计具有较低的面积，这使得所提出的设计适合于在资源受限的消费电子设备中的应用，诸如手持设备、可穿戴和可植入医疗设备、无线传感器节点、智能卡、IoT中的受限节点以及射频识别（RFID）设备。表1不同字串行字段乘法器之间的比较设计三态AND XOR MUX 触发器延迟CPDXie[17]0 2mw2mw6 m-6 m6 0 4mw4m 2w 2dm=we 2d log2we2TXPan[12]0mpmpmw2mw0F12dpm=wes1华[33]0w2w24- 5w110F26wdm=we2s2Chen[34]0w2ww22w2F3L1s3拟议w3w22w3w2 w 4 w d m=we -18 w d m = w e21 s4(1) 3输入异或门的面积为1：5×2输入异或门。(2) [34]的乘法器使用与2输入MUX具有相同晶体管计数的开关表2m/409和不同w值的不同字串行字段乘法器的实现结果。乘法器W延迟面积（A）[Kgates]CPD[ps]时间（T）[ns]功率（P）[nW]能量（E）[fJ]谢[17]832492.9850.816.46225.563.7116172146.9650.88.74375.53.283298195.1350.84.98477.42.38潘[12]84897.46206.39.90252.912.501636123.93244.48.80320.072.823224164.34282.56.78425.092.88[33]第三十三话82595847.9973.419053.474.3582.881612979210.4073.49526.735.8555.73326489619.9173.44763.3711.1553.11陈[34]81194610.1655.2659.425.113.3716367813.5155.2203.038.381.7032157226.5855.286.7715.951.38提出827057.26215.7583.473.882.26166779.19407.7276.015.121.413217015.78791.7134.597.280.98A. 易卜拉欣埃及信息学杂志23（2022）239247.Σ.Σ6. 总结和结论本文提出了一种新的高效的二维字基SISO脉动处理器，可在GF2m上并行执行乘法和平方运算。所提出的系统处理器结构共享数据路径，这导致节省更多的面积和功率资源。我们将非线性调度和投影函数应用到算法依赖图中，以探索所提出的脉动处理器核心。应用的非线性调度和投影函数给设计者更大的灵活性来控制处理器的工作负载和执行时间。处理器核心中脉动阵列的大小不依赖于字段大小，这使得所提出的设计更适合于在嵌入式和超低功耗设备中实现。所提出的二维组合字串行处理器脉动结构和现有的最佳字串行乘法设计的实现结果表明，所提出的结构实现了显着的节省面积和消耗的能量在不同值的嵌入字大小。这使得它更适合于在资源受限的消费电子设备中加密原语的受限实现，例如手持设备、可穿戴和可植入医疗设备、无线传感器节点、智能卡、物联网中的受限节点和射频识别（RFID）设备。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。确认作者感谢沙特阿拉伯教育部研究创新主任通过项目编号（IF-PSAU-2021/01/17867）资助这项研究工作。引用[1] 作 者 ：J. L.一 种获 得 数 字 签 名 和 公 钥 密 码 系 统 的 方 法 。 Mag CommunACM1978;21（2）：120-6.[2] LidlR，Niederreiter H. 有限域导论和他们的应用. 英国剑桥：剑桥大学出版社，1994年。[3] Reed IS，Solmon G.某些有限域上的多项式码。SIAM J ApplMath 1960;8：300-4.[4] Boneh D，Franklin MK. Weil配对的身份加密SIAM JComput 2003;32（3）：586-615.[5] 邱昌文，李清英，邓爱文，林俊明. GF（2 m）上蒙哥马利乘法的 并发 错 误检 测。IEICETrans Fundam ElectronCommun Comput Sci 2006;E89-A（2）：566-74.[6] Kim KW ，Jeon JC.使用细胞脉动结构的多项式基乘法器。IETE J Res 2014;60（2）：194-9.[7] 崔S，李K.用于GF（2 m）上快速求幂的高效脉动模乘器/平方器。 IEICE ElectronExpress 2015;12（11）：1-6.[8] KimKW，Kim SH. 用于gf（2m）上乘法和平方的高效位并行脉动结构。IEICEElectron Express2018;15（2）：1-6.[9] Kim CH，Hong CP，Kwon S.有限域GF（2m）上的数字串行乘法器。IEEETransVery Large Scale Integr（VLSI）Syst 2005;13（4）：476-83.[10] 张文，张文，等.一类特殊gf（2 m）的低复杂度数字序列收缩Montgomery乘法器.计算 机 学 报 ， 2000 ， 24 （ 1 ） ： 113 - 114. IEEE Trans Very Large ScaleIntegr（VLSI）Syst 2010;18（5）：847-52.[11] 郭俊华，王春霖. gf（2m）中用于求逆和除法的硬件高效脉动结构。IEE ProcComput Digital Techniques1998;145（4）：272-8.[12] Pan JS，Lee CY，Meher PK.低延迟数字串行和数字并行脉动乘法器，用于大二进制扩展字段。IEEE Trans Circ Syst-I 2013;60（12）：3195-204.[13] 李春英，范春春，袁世明。新的数字串行三操作数乘法器在二进制扩展领域的高性能应用。2017年第二届IEEE计算智能与应用国际会议。 p. 498- 502[14] Hariri A，Reyhani Masoleh A.二进制扩展域上移位多项式基乘法的数字串行结构。在：Proc. LNCS Intl WorkshopArithmetic of Finite Fields（WAIFI）. p. 103比16[15] Kumar S，Wollinger T，Paar C.基于曲线密码学的最佳数字串行乘法器。IEEETrans Comput2006;55（10）：1306-11.[16] Lee C-Y超数字串行心脏收缩乘数超过gf（2米）。第六届国际遗传进化计算会议，日本北九州; 2012年。pp. 509-513..[17] Xie J，Meher PK，Mao Z. NIST推荐的五项式的gf（2 m）上的低延迟高吞吐量收缩乘数。IEEE Trans Circuits Syst 2015;62（3）：881-90.[18] 放大图片作者：Namin AH，Wu H，Ahmadi M.一种使用正规基的字级有限域乘法器。IEEE Trans Comput2011;60（6）：890-5.[19] 作者：Lee C-Y，Chiou CW，Lin JM，Chang CC.可缩放和心脏收缩的Montreal乘法器由三项式生成。IET电路器件系统2007;1（6）：477-84.[20] 陈玲玲，张培，李振英，杨玉坤。GF（2 m）上的可缩放和收缩对偶基乘法器。 IntJ Innov Comput Inf Control 2011;7（3）：1193-208.[21] Orlando G，Paar C.一种FPGA超串行伽罗瓦域乘法器及其在公钥算法中的应用。InProc. IEEE Symp. - Field自定义组件1999. pp. 232-239..[22] [10]李文辉，李文辉，李文辉.用于安全应用和轻量级加密架构的双基超串行乘法器。IEEE Trans Circ Syst-II2014;61（2）：125-9.[23] Gebali F，Ibrahim A. GF（2 m）上基于三项式的高效可扩展串行乘法器。 IEEETrans Very Large Scale Integr VLSI Syst 2015;23（10）：2322-6.[24] Ibrahim A，Gebali F，El-Simary H，Nassar A.高性能，低功耗架构的可扩展基2蒙哥马利模乘算法。 Can J Electr Comput Eng 2009;34（4）：152-7.[25] Ibrahim A，Gebali F.基于gf2m的可扩展和统一的数字串行处理器阵列结构。IEEETrans CircuitsSyst I Regul Pap 2017;22（11）：2894-906.[26] Kim KW ， Lee JD. GF （ 2m ） 上 乘 法 与 平 方 的 有效 统 一 半 脉 动 阵 列。 IEICEElectron Express2017;14（12）：1-10.[27] 杰巴利湾算法与并行计算机New York，USA：John Wiley.[28] Ibrahim A ， Elsimary H ，Gebali F. 有限 域除 法的 新型 脉动阵 列结 构。 IEICEElectron Express2018;15（11）：1-11.[29] Ibrahim A，Elsimary H，Aljumah A，Gebali F.轮廓隐马尔可夫模型的可重构硬件加速器。阿拉伯科学工程杂志2016;41（8）：3267-77。[30] 易卜拉欣有限域除法的可扩展数字串行处理器阵列架构。Microelectron J 2019;85：83-91.[31] Ibrahim A，Alsomani T，Gebali F. GF（2 m）域乘与求逆的统一脉动阵列结构。Comput Electr Eng J-Elsevier2017;61：104-15.[32] Ibrahim A，Alsomani T，Gebali F.一种新的有限域求逆脉动阵列结构。 Can JElectr Comput Eng 2017;40（1）：23-30.[33] 华永永，林俊明，邱永华，李清英，刘永华。基于hankel矩阵和karatsuba算法的gf（2m）上低空间复杂度数字串行对偶基收缩乘法器。IET Inf Secur2013;7（2）：75-86.[34] 作者：Chen C-C，Lee C-Y，Lu E-H. GF（2 m）上的可伸缩和收缩蒙哥马利乘法器。IEICE Trans Fundam Electron Commun Comput Sci 2008;E91-A （7）：1763-71.