《伽罗瓦域GF(2^128)乘法器的设计.doc》由会员分享，可在线阅读，更多相关《伽罗瓦域GF(2^128)乘法器的设计.doc（33页珍藏版）》请在金锄头文库上搜索。
1、伽罗瓦域GF(2128)乘法器的设计2011年1月22日摘要伽罗瓦域GF(2128)乘法器是Ghash算法(一种用于加解密系统散列算法)的核心部件，其速度与硬件开销决定着整个Ghash模块的整体性能。本文通过Arash Reyhani-Masoleh 提出的一种算法，进行分析设计，然后用Verilog编程进行仿真，最后用Synplify 进行综合。最后，通过与一些其他的乘法器实现方法相比较，可以知道，本文提供的伽罗瓦域乘法的算法比较简单易懂，依现在的硬件来看也是很容易实现。关键词乘法器，伽罗瓦域，系统优化，Verilog语言，综合，Model Sim，Xilinx ISE，仿真Abstract
2、A 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 language to implement the GF(2128) multiplier with the algor
3、ithm 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 its wont occupy too much hardware
4、 resources.KeywordMultiplier, Finite Yield, Galois Field, Arash Reyhani-Masoleh, Verilog, Simulation, System Optimization, GF(2128)，Model Sim，Xilinx ISE目录摘要2关键词2Abstract3Keyword3目录41 题目71.1 内容71.2 设计要求72 背景介绍72.1 伽罗瓦域72.2 GCM加密解密82.2.1 加密82.2.2 解密82.3 Arash Reyhani-Masoleh 算法93 设计思路103.1 初步构想103.2 程
5、序流程图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编译工程185.1.4仿真运行185.2 波形分析215.2.1 仿真后主要信号、变量的波形图215.2.
6、2 mul_128模块的输入信号和输出信号215.2.3 dina和dinb输入215.2.4 Q126:0127:0的值225.2.5 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 Mastrovito乘法器288.3 Karatsuba乘法器298.4 正规基乘法器309 致谢与心得309.1 组内分工309.2 心得319.3 致谢33
7、10 参考文献331 题目1.1 内容伽罗瓦域GF(2128)乘法器是Ghash算法(一种用于加解密系统散列算法)的核心部件，其速度与硬件开销决定着整个Ghash模块的整体性能。本题目的最终目的是：完成伽罗瓦域GF(2128)乘法器的设计。1.2 设计要求1） 用verilog语言进行编程，语法要符合可综合设计的要求；2） 用modelsim完成系统功能仿真；3） 用synplify 或ISE进行综合；4） 完成设计报告。（设计报告中要对现有的几种伽罗瓦域GF(2128)乘法器实现方法进行比较，分析优劣）2 背景介绍2.1 伽罗瓦域 有限域（或伽罗华域）包含有限个元素，并定义了两种操作加法与乘
8、法，这两种操作都是针对二元的操作。GF（2）是最小的有限域，它只含有两个域元素0和1。加法和乘法都进行模2操作，因此加法等效与逻辑异或，而乘法等效于逻辑与。有限域可以用非可约多项式来定义，令GF（2m）是的根，即。则称为多项式基或标准基，GF（2m）中的每个元素都可以根据多项式基来表示。比如，对于,，可以表示为，其中即为基下的坐标。假设，则。2.2 GCM加密解密2.2.1 加密令n和u表示一对特殊的非负整数，因此，明文的总位数为：（n1）128+u,1u128.明文包括n个位字符串，最后一个字符串的位数是u位，其他字符串都是128位。这些字符串分别表示为：P1，P2,，Pn-1,P+n,我们
9、称这些位字符串为数据块，即使最后一个位字符串可能不是一个完整的数据块。类似的，密文分别表示为：C1,C2,，Cn-1，C+n,最后一块数据块 C+n的位数为u。冗余验证数据A分别表示为A1,A2,，Am-1,A+m，最后一个位字符串A+m可能不是整块且长度为v,m和v表示一对特殊的非负整数，因此A的总位数为：（m1）128+v,1v128。验证加密操作定义如下：连续计数值由函数incr()产生。把该函数变量值最右边32位当做非负整数，并且最低有效位在右边，加法操作主要是针对这最右边的32位。准确地说，incr(F|I)的值为F|I+1 mod 232）。函数GHASH的定义是GHASH（H，A
10、，C）=Xm+n+1，A和C的格式如前所述，变量Xi，i=0，m+n+1，定义如下：2.2.2 解密 验证解密操作与加密操作相类似，不同的是算散列值和加密的顺序颠倒了。具体定义如下面方程所示： 比较由解密操作计算出的标签T与标签T。如果两者相等（包括长度和值），那么密文将被返回。否则，返回特殊标识符FALL。2.3 Arash Reyhani-Masoleh 算法 对于有限域GF（2m）乘法C=AB，Arash Reyhani-Masoleh等人证明，乘积C的坐标可以通过一个带矩阵Q的方程计算出来。该方程为：，其中是的根，而T表示矩阵的转置。矩阵Q的准确定义与证明可以在1中找到，矩阵Q仅取决非
11、可约多项式。Ghash的多项式。下面我们直接给出GF（2128）中的矩阵Q。 对于域GF（2m）,矩阵L如下： （1）对于域GF（2m）,矩阵U如下： （2） 由（1）（2）可知，在已知输入A的情况下，可以很容易地得到矩阵L，U，因此，根据，我们即可算出有限域乘法的乘积。3 设计思路3.1 初步构想伽罗瓦域乘法器的核心是这个公式：所以，我们要做的工作就是如何实现一步一步地按照这个公式把输入的两个128位并行数据计算得出结果。根据背景介绍里面的算法描述，我们知道，Q矩阵是只与GF(2m)中的m有关，而本文的m是固定的，为128，所以，Q矩阵的所有值都是固定了的。那么，我们可以在初始化语句里面就把
12、Q矩阵计算出来。另外，考虑到计算的时候用的是Q矩阵的转置，那么，在初始化程序断里面就可以把Qt也一并求出来。还是根据算法描述可以知道，L矩阵和U矩阵是只与输入的dina有关，那么，我们可以设置一个always语句，检测dina的输入，任何时候只要dina有输入，那么程序就立即计算出对应的L矩阵和U矩阵。当然，还需要编写一段复位语句，使程序的所有变量、参数等等复位。另外，由于仿真一般最开始都是先复位，也相当于初始化，那么，可以把计算Q和Qt两个矩阵的代码放到复位语句块里面。考虑到为了降低芯片的计算量，我们可以是在每个时钟周期的上升沿检测复位信号rst和使能信号en，当复位信号rst为低电平的时候
13、，进行复位操作，如果不是低电平，再检测使能信号en，如果en为高电平（表明允许计算）才继续下一步。这时可以设置一个标志位flag，以检测本次的输入与上次的输入是否一样（假设相等的时候flag=0），如果flag=0，表明上次输入的dina和dinb与本次的相等，那么，也不继续进行下面的运算；只有当flag=1时，才进行伽罗瓦域乘法。根据，我们应该先计算Qt与U的乘积QtU，然后计算QtU和L的和LQtU，最后计算LQtU和dinb的乘积，即为dina和dinb的伽罗瓦域乘积。同时，考虑到verilog不支持类似于C语言的二维数组这种数据类型，只能使用存储器类型，即，不能对存储器的每一个字节单独
14、操作，那么，必须使用一些中间变量来获取存储器的值，计算出结果之后再写回到存储器，这部分会占程序的大部分，而且很容易出错。由以上分析可知，只有在每个时钟周期的上升沿时候，检测到(rst=0)&(en=1)&(flag=1)的时候，才计算dina和dinb的伽罗瓦域乘积。计算出dout之后，置ready_o为高电平，表明dout线上的信号为有效值。最后，由于这仿真的波形比较复杂，手工设置输入信号太麻烦，也达不到要求，所以，我们需要编写一段testbench文件来测试主程序。Testbench文件应该达到以下要求：1， 标准的时钟方波信号，可以通过always #50 clk=clk； 实现；2，复位操作可以使在initial里面加入以下语句：rst=1；#20 rst=0；#60 rst=1；3，使能位置高电平，通过#60 en=1； 实现；4，dina和dinb的输入。3.2 程序流程图 根据初步构想，我画出以下的程序流程图，简单地描述程序的运行状态。 4 功能模块4.1 乘法器主程序4.1.1 计算Q矩阵Q0127:0=128he10000
