伽罗瓦域GF(2^128)乘法器的设计

1、伽罗瓦域GF(2128)乘法器的设计2011 年 1 月 22 日摘要伽罗瓦域GF(28)乘法器是Ghash算法(一种用于加解密系统散列算法)的核 心部件，其速度与硬件开销决定着整个 Ghash模块的整体性能。本文通过 Arash Reyhani-Masoleh 提出的一种算法， 进行分析设计， 然后用 Verilog 编程进行仿真， 最后用 Synplify 进行综合。 最后， 通过与一些其他的乘法器实现方法相比较， 可 以知道，本文提供的伽罗瓦域乘法的算法比较简单易懂， 依现在的硬件来看也是 很容易实现。关键词乘法器，伽罗瓦域，系统优化，Verilog语言，综合，Model Sim，Xil

2、inx ISE 仿真AbstractA finite filed multiplier architecture is the central part of the Ghash Algorithm (an algorithm for an outstanding encryption system), whose speed and cost determine the property of the whole Ghash module. In this paper, we use the Verilog Ian guage to impleme nt the GF(2A128) mult

3、iplier with the algorithm proposed by Arash Reyhani-Masoleh. Then, we use the Model Sim for simulation and Synplify for Synthesis. And, through the comparison between several other ways to implement this multiplier, we can draw the conclusion that our way is quite easy to understand and itswontoccup

4、y too much hardware resources.KeywordMultiplier, Finite Yield, Galois Field, Arash Reyhani-Masoleh, Verilog, Simulation, System Optimization, GF(2A128，) Model Sim，Xilinx ISE目录摘要关键词 2Abstract 3Keyword 3目录 31 题目 71.1 内容 71.2 设计要求 72 背景介绍 72.1 伽罗瓦域 72.2 GCM加密解密82.2.1 加密 82.2.2 解密 82.3 Arash Reyhani-Mas

5、oleh 算法 93 设计思路 103.1 初步构想 103.2 程序流程图 114 功能模块 124.1 乘法器主程序 124.1.1计算Q矩阵124.1.2计算Q矩阵的转置 Qt134.1.3计算L矩阵134.1.4计算U矩阵134.1.5计算Qt与U的乘积 QtU134.1.6 计算 QtU 和 L 的和 LQtU144.1.7计算LQtU和dinb的乘积： 144.2 测试模块 144.2.1 initial 块 144.2.2 always 块155 Model Sim 仿真155.1 仿真步骤 155.1.1 创建工程 155.1.2 添加 verilog 文件 165.1.3 编

6、译工程 185.1.4 仿真运行 185.2 波形分析 215.2.1 仿真后主要信号、变量的波形图 215.2.2 mul_128 模块的输入信号和输出信号 215.2.3 dina 和 dinb 输入 215.2.4 Q126:0127:0 的值 22525 Q 的转置 Qt127:0126:0的值225.2.6 dina_old, dinb_old 信号的波形图 235.2.7 说明236 综合 236.1 综合步骤 236.2 结果分析 247 源码与注释 247.1 主程序 247.2 测试程序 278 几种乘法器的比较 288.1 Montgomery 乘法器 288.2 Mast

7、rovito 乘法器 288.3 Karatsuba 乘法器 298.4 正规基乘法器 309 致谢与心得 309.1 组内分工 309.2 心得 319.3 致谢 33参考文献 331题目1.1内容伽罗瓦域GF（2128）乘法器是Ghash算法（一种用于加解密系统散列算法）的核心部 件，其速度与硬件开销决定着整个 Ghash模块的整体性能。本题目的最终目的是： 完成伽罗瓦域GF（2128）乘法器的设计。1.2设计要求1）用verilog语言进行编程，语法要符合可综合设计的要求；2）用modelsim完成系统功能仿真；3） 用synplify或ISE进行综合；4） 完成设计报告。（设计报告中要

8、对现有的几种伽罗瓦域GF（2128）乘法器实 现方法进行比较，分析优劣）2背景介绍2.1伽罗瓦域有限域（或伽罗华域）包含有限个元素，并定义了两种操作一一加法与 乘法，这两种操作都是针对二元的操作。GF（2）是最小的有限域，它只含有 两个域元素一一0和1。加法和乘法都进行模2操作，因此加法等效与逻辑异 或，而乘法等效于逻辑与。有限域可以用非可约多项式P（x） = x Pm丄x亠亠R P0来定义，令卅三GF（ 2m）是P（X）的根，即 p（:,） = 0。则称1,，2,丄为多项式基或标准基，GF（ 2m）中的每个元 素都可以根据多项式基来表示。比如，对于 A二ammda。，可以表示为 m -LA二

9、、ajjai - 0,1，其中ai即为基下的坐标。假设=1/ ,2,“丁，i =0a - a0 , a! , a2 , ,am，贝U A = a。2.2 GCM加密解密2.2.1加密令n和u表示一对特殊的非负整数，因此，明文的总位数为：（n 1）128+u,1 u 128.明文包括n个位字符串，最后一个字符串的位数是u位，其他字符串都是128位。这些字符串分别表示为：Pi, P2, , ,Pn-i,P+n,我们称这些位字符串为数据块，即使最后一个位字符串可能不是一个完整的数据 块。类似的，密文分别表示为：C1,C2, , ,G-1 , Cn,最后一块数据块C + n的位数为u。冗余验证数据A分

10、别表示为Ai,A2, , ，Am-i,A+m，最后一个位字符串A*m可能不是整块且长度为v,m和v表示一对特殊的非负整数，因此A的总 位数为：（m 1） 128+v,1 v 12 8。验证加密操作定义如下：128二 E(K ,0)YYiCiIV | 0311GH ASH (Hincr (Yif,for二 Pi 二 E (K ,Yi) forIVlen (IV ) = 96) otherw isei = 1, ，ni =1,，n - 1二 Pn 二 MSBU(E(K ,Yn)T = M SBt(G H ASH ( H , A,C )二 E (K ,Y0)连续计数值由函数incr（）产生。把该函数

11、变量值最右边 32位当做非负整 数，并且最低有效位在右边，加法操作主要是针对这最右边的 32位。准确地 说，incr（F|I）的值为 F|I+1 mod 232）。函数GHASH的定义是GHASH（ H，A，C） =Xm+n+1，A和C的格式如前所 述，变量X，i=0，, ，m+n+1，定义如下：0(XiAi)凶*128 _v(XmA(Am |0)出Xi = ) =0的根，b =b,b1,bmT，而T表示矩阵的转置。矩阵Q的准确定义与证明可以在1 中找到，矩阵Q仅取决非可约多项式p(： ) oGhash的多项式p(： )F面我们直接给出GR2128)(1)(1)中的矩阵Qo对于域GF(2m)，

12、矩阵L如下:aa1a。00a2a1aa m-2ama1a。-am 4am-2a2a10a191100a0010a0000 0000000091200000000000000 111000011211110000100000 011100001220111000010000 000111001230011100001000 000111001240001110000100 00001110125 0000111000010 000001111261110011000001 00000011127Q 二(1)对于域GF (2m)，矩阵U如下:00am 2am 1a2a3aia2(2)00am上am

13、 _1由(1) (2)可知，在已知输入T=ctA的情况下，可以很容易地得到矩阵 L, U, 因此，根据C = J(L QTU )b，我们即可算出有限域乘法的乘积。3设计思路3.1初步构想伽罗瓦域乘法器的核心是这个公式：C = ： T (L QTU )b所以，我们要做的工作就是如何实现一步一步地按照这个公式把输入的两个 128位并行数据计算得出结果。根据背景介绍里面的算法描述，我们知道，Q矩阵是只与GF(2Am中的m有 关，而本文的m是固定的，为128,所以，Q矩阵的所有值都是固定了的。那么， 我们可以在初始化语句里面就把 Q矩阵计算出来。另外，考虑到计算的时候用 的是Q矩阵的转置，那么，在初始

14、化程序断里面就可以把Qt也一并求出来。还是根据算法描述可以知道，L矩阵和U矩阵是只与输入的dina有关，那么， 我们可以设置一个always语句，检测dina的输入，任何时候只要dina有输入， 那么程序就立即计算出对应的 L矩阵和U矩阵。当然，还需要编写一段复位语句，使程序的所有变量、参数等等复位。另外， 由于仿真一般最开始都是先复位，也相当于初始化，那么，可以把计算Q和Qt两个矩阵的代码放到复位语句块里面。考虑到为了降低芯片的计算量，我们可以是在每个时钟周期的上升沿检测复 位信号rst和使能信号en,当复位信号rst为低电平的时候，进行复位操作，如 果不是低电平，再检测使能信号 en，如果

15、en为咼电平(表明允许计算)才继续 下一步。这时可以设置一个标志位flag，以检测本次的输入与上次的输入是否一 样(假设相等的时候flag=0)，如果flag=O,表明上次输入的dina和dinb与本次 的相等，那么，也不继续进行下面的运算；只有当flag=1时，才进行伽罗瓦域乘法。根据cT (l qtu )b ,我们应该先计算Qt与U的乘积QtU,然后计算QtU 和L的和LQtU，最后计算LQtU和dinb的乘积，即为dina和dinb的伽罗瓦域乘 积。同时，考虑到verilog不支持类似于C语言的二维数组这种数据类型，只能 使用存储器类型，即,不能对存储器的每一个字节单独操作，那么，必须使

16、用一 些中间变量来获取存储器的值， 计算出结果之后再写回到存储器， 这部分会占程 序的大部分，而且很容易出错。由以上分析可知，只有在每个时钟周期的上升沿时候，检测到 (rst=O)&(en=1)&(flag=1)的时候，才计算 dina和dinb的伽罗瓦域乘积。计 算出dout之后，置ready_o为高电平，表明dout线上的信号为有效值。最后， 由于这仿真的波形比较复杂， 手工设置输入信号太麻烦， 也达不到要 求，所以，我们需要编写一段testbe nch文件来测试主程序。Testbe nch文件应该 达到以下要求：1， 标准的时钟方波信号，可以通过 always #5O clk=clk；

17、实现； 2，复位操作可以使在 initial 里面加入以下语句：rst=1；#2O rst=O； #6O rst=1；3，使能位置高电平，通过 #6O en=1； 实现；4， dina 和 dinb 的输入。3.2 程序流程图根据初步构想， 我画出以下的程序流程图， 简单地描述程序的运 行状态。Always初始化计算L计算UIf(rst)lf(e n=1)always(p osedge clk)复位操作lf(flag=1)计算Q和Qt计算QtU计算LQtU计算dout并输出4功能模块4.1乘法器主程序4.1.1计算Q矩阵Q0127:0=128he100000000000000000000000

18、0000000;for(i=1;i1;Q121127:0=128he1000000000000000000000000000070;Q122127:0=Q121127:01;Q123127:0=Q122127:01;Q124127:0=Q123127:01;Q125127:0=Q124127:01;Q126127:0=128he6080000000000000000000000000003;4.1.2 计算 Q 矩阵的转置 Qtfor(i=0;i128;i=i+1)beginfor(j=0;j127;j=j+1)begintemp127:0=Qj127:0;temp4126-j=temp127

19、-i;if(j=126) Qti126:0=temp4126:0; end end4.1.3计算L矩阵always(dina)beginL127127:0=dina127:0; for(i=0;i127;i=i+1) L126-i127:0=L127-i127:01;for(j=1;j1;end4.1.5计算Qt与U的乘积QtUfor(i=0;i128;i=i+1)begintemp4126:0=Qti126:0;for(j=0;j128;j=j+1)beginfor(k=0;k127;k=k+1)begintemp127:0=Uk127:0;temp1127-j=temp1127-jF(te

20、mp4126-k &temp127-j);endif (j=127) QtUi127:0=temp1127:0;endend4.1.6计算 QtU和L的和LQtUfor(i=0;i128;i=i+1)begintemp127:0=Li127:0;temp1127:0=QtUi127:0;for(j=0;j128;j=j+1)begintemp2j=temp|jAtemp1|j;if(j=127) LQtUi127:0=temp2127:0;endend4.1.7计算LQtU和dinb的乘积：for(i=0;i128;i=i+1)begintemp1127:0=LQtUi127:0;for(j=

21、0;j128;j=j+1)temp2127-i=temp2127-iF(temp1127-j&temp127-j);end4.2 测试模块4.2.1 initial 块initialbeginclk=0;en=0;rst=1;dout127:0=0;#20rst=0;#60rst=1; en=1;#100dina=128b0;dinb=128b0;#200dina=128h4283_1ec2_2177_7424_4b72_21b7_84d0_d49c;din b=128hb83b533708bf535d0aa6e52980d53b78;#70dout=128h9e2213794cbee3890

22、2b8e6ae8cd41a9f;#130 din a=128h90000000000000000000000000000012;din b=128h00000000000000000000000000000002; #70doutarTiplesBrawse.Default Library NameCopy Settings From|F7M odel S imB. 2/modelsim.in iB rowse.Copy Library Mappingj r Reference LibraryOK Oncel |5.1.2 添加verilog文件这一步的目的是将verilog文件添加到创建好的

23、工程中。要添加的文件可以是先前已经用UltraEdit编写好存放于电脑某个目录下的，也可以现在输入。输 入的工具可以是Modelsim自带的代码输入工具，但最受欢迎的是UltraEditStart SimulateDesign VHDL | Verilog | Libraries DF OthersPath*NameType.tesmuLI 28 Module-workLibrasmul_12BModule F:/M odelS im6.2/eicample$/wo(k F: /M odelS im6.2/MjAorksAnuL129- vF： /W odelS imE. 2/M5/Works

24、?test_mul_1top_testModulesv_tdLibrary11312000LibraryieeeLibrarymod8hirn_libLibrarystrlI ihriruF: odelS im6.2/MyWork$/te$Lmul_1 M0DEL_TECHA7sv_td $MODEL_TECH/.Mal2000 $MODEL_TECHA；ieee $M0DEL_TECH/.7modelsim_lb twnnFi Trrn/ /stn-Design Unit(x)_work. test_mul_ 128Resoluti ondefaultOptimization ptinniz

25、ation Dptions.|* Enable optimizationOK | Cancel选择testbench文件，此处为test_mul_128，点击“OKWorkspace：“Objects* Instancetest mul 128Db审gn unitDesign unit typetest mul 128 Moduler mulView DeclarationModuleView Irtanftiation128 ProcessnAddAdd Al Signals Io WaveCreate WaveAdd to WaveCopyAdd 怕 DatafhiAFFindAdd to

26、 ListAdd to WatchExpand SelectedCollapse SelectedEspand AllLogLQtUQt U QtU L read5J_o dinb_old (Sri.alH dout lemp2 temp! temp4 tempwave窗口中单击右键，选择将所有信号（或你希望观察的信号）添加到Ubieclsd!X|TNameVdueLQtU时 QtxffiXKXKKXXH酣 Q焦已X翩*昭附2 U* QdJL L*盘料嚣J rwdy_oXE丿dnb_ol(ilXXKXXXXXXXKdria_olddoutXHSCXMKMHXMKIgf-J tempCXXSCK

27、KXXKXXK3磐tempiQ-J temf4XXKX丹他保BJternpX畑畑咖&魂enSIX斗ct.SIXdrbXX刪侧啊阳磐丿dina* rstSIXi耳4 kXJ flagx” iXn| wave - default* Aest mul 12S/mul/clk4 Aest_mul_12E/mul/rst* /lest_mul_128/mul/enAest_mul_12S/mii?d./te?t_nnuL12B/mul/d,Ae$t_muM28/mul7r.Aest_mul_l 加 /Et_rriul_12SAnii/dlAest_mul_128/mul/d.Aest mul 128Zm

28、ul/t. /tejt_nnul_128Anirf/t.Aest_mul_12BZmul/t.Aest_inul_12SZmul/t.Aest_muL128/mul/iAest_mul_126/mul/jAe3t_mu|_126/mul/kAest_muL128/mul/f.Aest_mul_12e?clk /test_mul_126/r?tAesLmuLI 28/enAest_mul_12S7dina0 nsCursoi 1I i i i I i 11 i ii I i i i I i 11 i I i i i i H i i I i i200Onssimulater unrun all，出

29、现如下波形:NEt_mu|_28fcA /te$t_mul_J28/r3t A)est_mul_120/enAest_uL128/(frib Aest_nKJI_128/(10VDrfNo DH Ho THo DarHq Dtf Na Di NaDiiXij522 mul_128模块的输入信号和输出信号由图可以看出，最开始的时候rst置低电平进行复位操作，然后为高电平， 同时使能信号en也变高，表示现在可以接受输入了。 dina和dinb最开始输入全 是0，dout大概延迟一个时钟周期之后输出，同时ready_o信号变为高电平，表明dout线上的数据时dina和dinb的伽罗瓦域乘积。占 Am

30、Lmutlck* Aii_mJ_12eAst* Aesl_mul_l 2B/en 0 JI&SLlMJI 朗闭叶3 g扌#1 强LniMLTSfl 曲旳D-J /leslmiJlZB/daul28Aafe_o-NcD二L JLMrNdD 就Li _ n _*riTC0OTnTCC03DC(LLUjjTT2-wwi nnrvL-nFi r. J=111.1IfflXUC匚:r Me r l -Nq U4podmi讥mj胆DOQgQDOOCK miiiXOOJEijCCOZIJC(CiJJCCO.叫hE斗IglHKpiacJCOTJCccojocm toDCO：iiaCi：i：ODdi：i：ijO

31、OMiJiCU：05.2.3 dina 和 dinb输入din a=128h42831ec2217774244b7221b784d0d49c; din bnul_128/clk-Ho Dat：IJ /tesl_niul_128Ast-No Dat* /tesLmuL12B/enNo D*t-B-J /test_mul_128/dina-No Datt142831 ec2217774244b7221 b784d0d49c畑规_mul2B/dinbNo DatS-J /le$t_nnul287dcnJt-Nc DotoooooooooooodoooooooooooooooooooEM逼囲述剛科翻砲

32、艇iESH-No DatIIIIII这是输入为:din a=128h90000000000000000000000000000012; din b=128h000000000000000000000000000000002; 时的输出dout:dout= 128h200000000000000000000000000000a3依然是与理论计算值相等。J /lest_mul_128/clcJo DarZltst_muLl 2S/istNo UatJ2S/enJoDalP- AesLmuLI 28/driaI-Ju ijlfj丿/test_md_128VdinbNo DalO-J2 田 doutN

33、oD* /lest_mL4_l 2S/Feadv_o Jo Dat丽丽 CWDCijOCiOOCiU 而5100012524 Q126:0127:0的值通过验证一些截图给出的 15组Q的值，可知Q与理论值相等。7642110J怙冈:旳孔叩00000翌響3闿摯翌型里摯蜩翌ggg eGOeOOOOOOOOOOOOlDel ODOOOOOOOOOOOI1 C2000000c00a000l3840QOOOOOOOOGOOI70I30000000000000IelOOOOOOOOOOOOOOlQggQQggQQggogpgg!点和EE ,De1000l 1c2000i ：384000lawnOOOOOO

34、I0000001X000000LiODDClOljOm55B5Mun心ooucoMBuoo页 u lOijjQOui 10000001 10000001w. W iQOe nil Es Bza 面01c2000(x)0000000i03640000000000001070300000000000010e1 ODOOOOOOOOOOOi1c20000000000000i38400000000000001 70EOOOODDOOOOOODI e100000000(X)00001：o?osooc|oooooo:ooooooo)oooooo()ooo：OelOOOdOOOOOO(qOOOOOOODOO

35、ODOOpOOO：1c2000q000000：384000d000000cBOODOCO 3000000()0007O8ooa0o0Q)0aQi00000I0o0Cioot)o00:el oooooooooootiJOOOOOObOOOOOOiJDOO5 垃UOQCWOCiOOiOCWUUUDCICWUUjWU5.2.5 Q 的转置 Qt127:0126:0的值通过验证给出的15组Qt的值可以知道Qt与理论值相等。 - .M - - - 76543 210 - _ - - - - a I I a ; r - -438000000000000010700000000000000) OeOOOOO

36、OOOOOOOOOl1 cOOOOOOOOOODOOOi3000000000000000170000000000000001GOOOOOOOOOOOOOOOi ADUoociuooDuaacwi页 ma as om mm 墜 丽d5ou血和血uo imo丽兄卩瓦丽丽。阪 auociHuDooDum 远 botnCiDOOCiD DODD DDCitnODO mW恤DemamEmmromgmbmesMtrnjoOmocisjciocoKcobcnmcoo 亚 i5.2.6 dina_old, dinb_o Id信号的波形图有图可以看出每次计算出dout的值之后，dina_old和dinb_old

37、都成功地立即 获得了当前的dina和dinb,为了与下次输入的dina和dinb相比较，当二者相等 的时候程序不进行计算，只是保持原来的输出。1：| “：0冲川0；可：妙0；山：门冲门：| ：人:引厂”卄皿巴：-”II菽:占皿|工加60工|工门工门工mu5.2.7说明其他的一些中间变量，比如L、 U、temp等等，由于光看波形不好验证是否正确，所以我没有把这些信号的波形拿来验证，只取了一些简单的来验证。当然，最主要的是输出 dout正确，那中间的过程不出意外应该是没有问题的，所以也就不必去一一验证了。6综合6.1综合步骤（由于时间问题、程序编写不规范等等问题，最终没有完成综合）6.2 结果分析估计是一大片一大片的门门门门门门门门门门门门门门门门门门7 源码与注释7.1 主程序主程序： mul_128(clk, rst, en, dina, dinb, dout, ready_o)/*乘法器主程序输入两个 128 位并行数和 b 、以及功能信号，可得到乘法结果 cmodule mul_128(clk,/ 时钟信号，方波rst,/ 复位信号，低电平有效en,/ 使能信号，高电平有效dina,/a 输入口dinb,/b 输入口dout,/ 输出端口ready_o);/ 输出有效端，高电平有效inputclk,rst,en;/ 输入