一种串并结合的素域GF(p)大数模乘器电路

摘要

本发明公开了椭圆曲线加密（ECC）算法领域的一种串并结合的素域GF(p)大数模乘器电路，包括：一个数据左移一位模块，一个数据右移一位模块，一个二选一选择器，四个比较器、一个大数加法器和两个大数减法器。本发明针对传统加密算法特别是素域加密算法中的基本计算单元之一的大数模乘器之相应硬件电路都是串行结构、计算耗时的缺点，提供了串并结合的硬件电路结构。本发明能加快素域大数模乘的运算速度且资源消耗相对较少，实现硬件逻辑结构简单，可用于设计椭圆曲线加密（ECC），RSA等加密算法处理器，适用于在FPGA及ASIC中实现。

权利要求

1.一种串并结合的素域GF(p)大数模乘器电路，用于计算大数模乘式c＝(a·b)mod p，其中0≤a,b

所述大数加法器计算m位宽的c和m位宽的b相加的m+1位结果并设为c，输出端连接到二选一选择器的一个输入端；

所述二选一选择器的另一个输入端输入m位宽的c，第一比较器判断a的最低位是否为

1，判断所得的结果输入到二选一选择器的控制端，二选一选择器当a的最低位为1时输出大数加法器相加所得m+1位宽的c到第二比较器，否则输出m位宽的c到第二比较器；

所述第二比较器比较m位素数p的值和二选一选择器的输出m+1位宽的c的大小，输出端接到第一大数减法器和数据左移一位模块；

所述第一大数减法器在c≥p时，计算c＝c-p，包括m+1位的c与m位的素数p相减；

所述数据左移一位模块将b左移一位，包括将m位的b左移一位得到m+1位的输出b，输出端连接到第三比较器；

所述第三比较器比较素数p的值和数据左移一位模块的输出b的大小，输出端接到第二大数减法器和数据右移一位模块；

所述第二大数减法器在b≥p时，计算b＝b-p；

所述数据右移一位模块将a右移一位，输出端接到第四比较器；右移之后，a的位宽还是保持之前定义的m位，高位补零；

所述第四比较器将a与0值进行比较，如果两者相等则将二选一选择器的相应m位c作为结果输出，否则输出控制信号到第一比较器继续判断a的最低位是否为1。

2.如权利要求1所述串并结合的素域GF(p)大数模乘器电路，其特征在于：执行流程采用状态机实现控制。

说明书

一种串并结合的素域GF(p)大数模乘器电路

技术领域

[0001] 本发明涉及密码学的算法硬件实现领域，特别是涉及一种加密解密算法中的重要功能部件——素域GF(p)大数模乘电路。

背景技术

[0002] 设F是至少含2个元素的集合，对F定义两种运算，“+”和“×”，当代数系统满足封闭性、结合性、单位元、逆元和交换性条件时，被称为一个域。当F的元素为有限个时，称为有限域。当p为素数时，F={0，1，2，……p-1}在mod（p）下关于模运算的加法和乘法构成一个有限群，这个群就记为GF（p）。

[0003] 随着椭圆曲线在公钥密码体制中的应用越来越广泛，人们对于椭圆曲线加密算法的研究也越来越多，具体来说，从算法到软件、硬件的实现都取得了不同程度的突破。椭圆曲线加密算法与RSA加密算法相比，椭圆曲线加密算法拥有更多的技术优点，比如在达到同等密级的情况下密钥较小等，因此椭圆曲线加密算法在某些领域（如快速加密、密钥交换、身份验证、数字签名、移动通信的安全保密）的应用有逐步取代RSA等类型加密算法的趋势。

[0004] 椭圆曲线密码（ECC）是1985年由N.Koblitz和V.Miller提出的。椭圆曲线密码属于公钥密码体制，它可以提供同RSA密码体制同样的功能，与RSA密码体制不同的是，它的安全性建立在椭圆曲线离散对数问题（ECDLP）的困难性之上。现在求解ECDLP最好的算法具有全指数时间复杂度，这意味着对于达到期望的安全程度，椭圆曲线密码可以使用较RSA密码更短的密钥。由于密钥短的优点使得椭圆曲线加解密不仅速度快，而且还能节省能源、通信带宽和存储空间。

[0005] 大数模乘运算是ECC加密算法中的基本运算功能单元之一，在ECC加密算法中得到多次调用，是关键单元之一，它的速度和效率直接影响整个ECC处理器的速度、面积和功耗，所以对模乘器电路硬件结构的设计显得尤为重要。

[0006] 素域GF(p)大数模乘器电路采用传统Blakley算法时，所有操作都是串行的，而随着安全性要求提高，使得大数位宽m线性增加，Blakley算法的串行操作导致其电路延迟线性增加以致不能满足很多应用的实时加密解密需求。

发明内容

[0007] 本发明要解决的技术问题是提供一种串并结合的素域GF(p)大数模乘器电路，能够加快运算速度和节省逻辑资源。

[0008] 为解决上述技术问题，本发明的一种串并结合的素域GF(p)大数模乘器电路，用于计算大数模乘式c＝(a·b)mod p，其中0≤a,b

[0009] 所述大数加法器计算m位宽的c和m位宽的b相加的m+1位结果并设为c，输出端连接到二选一选择器的一个输入端；

[0010] 所述二选一选择器的另一个输入端输入m位宽的c，第一比较器判断a的最低位是否为1的结果输入为二选一选择器的控制端，当a的最低位为1时输出大数加法器相加所得m+1位宽的c到第二比较器，否则输出m位宽的c到第二比较器；

[0011] 所述第二比较器比较二选一选择器的输出c和素数p的值的大小，输出端接到第一大数减法器和数据左移一位模块；

[0012] 所述第一大数减法器在c≥p时，计算c＝c-p；

[0013] 所述数据左移一位模块将b左移一位，输出端连接到第三比较器；

[0014] 所述第三比较器比较数据左移一位模块的输出b和素数p的值的大小，输出端接到第二大数减法器和数据右移一位模块；

[0015] 所述第二大数减法器在b≥p时，计算b＝b-p；

[0016] 所述数据右移一位模块将a右移一位，输出端接到第四比较器；

[0017] 所述第四比较器将a与0值进行比较，如果两者相等则在输出端输出m位的结果c，否则输出控制信号到第一比较器继续判断a的最低位是否为1。

[0018] 而且，执行流程采用状态机实现控制。

[0019] 传统上素域GF(p)大数模乘器电路都是采用的全串行硬件电路结构，本发明的素域GF(p)大数模乘器电路采用串并结合的方式，可以提高运行速度，而且实现逻辑资源少，可适用于FPGA或者ASIC中实现。

附图说明

[0020] 图1是本发明实施例的串并结合的素域大数模乘运算的流程图；

[0021] 图2是本发明实施例的状态机控制素域大数模乘运算的状态图；

[0022] 图3是本发明实施例的串并结合的素域大数模乘运算的数位变化示意图。

具体实施方式

[0023] 下面结合附图与具体实施方式对本发明作进一步详细说明：

[0024] 实施例提供的大数模乘器的基本电路包括第一比较器、大数加法器、二选一选择器、第二比较器、第一大数减法器、数据左移一位模块、第三比较器、第二大数减法器、数据右移一位模块和第四比较器。

[0025] 第一大数减法器和数据左移一位模块并行执行，第二大数减法器和数据右移一位模块并行执行，

[0026] 所述大数加法器计算m位宽的c和m位宽的b相加的m+1位结果并设为c，输出端连接到二选一选择器的一个输入端；

[0027] 所述二选一选择器的另一个输入端输入m位宽的c，第一比较器判断a的最低位是否为1的结果输入为二选一选择器的控制端，当a的最低位为1时输出大数加法器相加所得m+1位宽的c到第二比较器，否则输出m位宽的c到第二比较器；

[0028] 所述第二比较器比较二选一选择器的输出c和素数p的值的大小，输出端接到第一大数减法器和数据左移一位模块，可向第一大数减法器和数据左移一位模块发送控制信号；

[0029] 所述第一大数减法器在c≥p时，计算c＝c-p；

[0030] 所述数据左移一位模块将b左移一位，输出端连接到第三比较器；

[0031] 所述第三比较器比较数据左移一位模块的输出b和素数p的值的大小，输出端接到第二大数减法器和数据右移一位模块，可向第二大数减法器和数据右移一位模块发送控制信号；

[0032] 所述第二大数减法器在b≥p时，计算b＝b-p；

[0033] 所述数据右移一位模块将a右移一位，输出端接到第四比较器；

[0034] 所述第四比较器将a与0值进行比较，如果两者相等则在输出端输出m位的结果c，否则输出控制信号到第一比较器继续判断a的最低位是否为1。

[0035] 具体实施时，可以设置相应寄存器辅助运行，如设置存储a，b和c的寄存器ain1_reg、ain2_reg和yout_r，可以在参与相应运算时调用，也可以存储相应计算结果。图1所示的流程图由图2所示的状态机控制，此状态机可通过硬件电路实现。状态机控制素域模乘运算的过程分为6个状态，首先，系统复位之后进入S0状态，存储a，b和c的寄存器ain1_reg、ain2_reg和yout_r都为0（图中记为!rst_n/ain1_reg=0,ain2_reg=0,yout_r=0）。当启动信号启动之后，状态跳转到S1状态，并且将a的值放入寄存器ain1_reg，将b的值扩展一位放入寄存器ain2_reg中（图中记为load/ain1_reg=a,ain2_reg={1′b0,b}，1′b0表示1位的二进制数0）。将a、b、c的值进行扩位处理是方便后续的左移操作。当判断ain1_reg0＝1时（ain1_reg0表示寄存器ain1_reg的第0位），就跳转到S2状态，并且将m+1位的寄存器yout_r和m+1位的寄存器ain2_reg做加法运算送给寄存器yout_r（即yout_r=yout_r+ain2_reg）。之后比较m+1位的寄存器yout_r和m位素数p的大小，如果yout_r≥p（即c≥p），则跳转到S3状态，并且同时执行m+1位的yout_r和m位素数p的减法操作（即yout_r=yout_r-p）和ain2_reg的左移操作（即ain2_reg=ain2_reg<<1）。接着比较m+1位的寄存器ain2_reg和m位素数p的大小，如果ain2_reg≥p（即b≥p），则跳转到S4状态，并且同时执行m+1位的寄存器ain2_reg与m位素数p的减法操作（即ain2_reg=ain2_reg-p）和m位寄存器ain1_reg的右移操作（ain1_reg=ain1_reg>>1）。最后判断ain1_reg是否值为0，如果是的，则跳转到S5状态，并且将去掉最高位的寄存器yout_r的结果（即yout[m-1:0]=yout_r[m:0]）送给m位寄存器yout中作为最终的输出结果，否则（即ain1_reg≠0），又会跳转到S1状态，重复上述的步骤继续执行。

[0036] 大数模乘表示形式一般为：

[0037] c＝(a·b)modp   其中0≤a,b

[0038] 其中a,b,p都是位宽为m的二进制无符号大数。a,b,p的m位分别记为am-1，am-2…a1,a0，bm-1,bm-2…b1,b0，pm-1，pm-2…p1,p0。模乘器由两部分运算组成，先对a和b作乘法运算，然后再模上p。

[0039] 1983年Blakley基于该计算表达式提出了一种加法型模乘算法，其设计思想是将模乘转化为一系列加法运算，为使最终结果c小于p，每次计算的中间结果都需要做取模运算。

[0040] Blakley算法如下：

[0041] 输入：a＝{am-1,am-2…a1,a0}

[0042] b＝{bm-1,bm-2…b1,b0}

[0043] p＝{pm-1,pm-2…p1,p0}

[0044] c＝0

[0045] 输出：c＝(a·b)mod p

[0046] 其中，c＝{cm-1，cm-2…c1,c0}

[0047] 运算过程如下：

[0048] 1、c＝0;

[0049] 2、For i＝0to(N-1)；

[0050] 3、{

[0051] 4、c＝2c+a*bN-1-i；

[0052] 5、if(c≥p)；

[0053] 6、c＝c-p；

[0054] 7、if(c≥p)；

[0055] 8、c＝c-p；

[0056] 9、}

[0057] 10、Return c。

[0058] 由Blakley算法可知，其所有运算都是串行的，在速度上有很大的制约。本发明提出串并结合的方式来提高速度。

[0059] 本发明算法如下：

[0060] 输入：a＝{am-1,am-2…a1,a0}

[0061] b＝{bm-1，bm-2…b1,b0}

[0062] p＝{pm-1,pm-2…p1,p0}

[0063] c＝0

[0064] 输出：c＝(a·b)mod p

[0065] 其中，c＝{cm-1，cm-2…c1,c0}

[0066] 运算过程如下：

[0067] 1、c＝0；

[0068] 2、若a≠0，重复执行步骤3至步骤7；

[0069] 3、若a0＝1，则c＝c+b，然后进入步骤4，否则直接进入步骤4；

[0070] 4、若c≥p，则c＝c-p，然后进入步骤5，否则直接进入步骤5；

[0071] 5、b＝b＜＜1，b＜＜1表示将b左移一位；

[0072] 6、若b≥p，则b＝b-p，然后进入步骤7，否则直接进入步骤7；

[0073] 7、a＝a＞＞1，a＞＞1表示将a右移一位；

[0074] 8、若a＝0，则执行步骤9，否则返回步骤3；

[0075] 9、返回（c）。

[0076] 以上算法中，在第3步，需要一个m+1位的加法器，在第4步和第6步都需要进行比较操作，需要两个m+1位的比较器，同时还需要两个m+1位的减法器。第4步和第5步，第6步和第7步的执行次数都为一次，而且每两个步骤之间相互不产生影响，本发明硬件结构将这4个步骤并行运算。

[0077] 参见图3，所述的串并结合的模乘器电路的运算流程是：串并结合的模乘器电路初始化时a＝{a[m-1],…a[1],a[0]},b＝{b[m-1],…b[1],b[0]},p＝{p[m-1],…p[1],p[0]}，即a，b，p的m位分别记为a[m-1],…a[1],a[0]，b[m-1],…b[1],b[0]，p[m-1],…p[1],p[0]。输出c也是一个m位宽的数，值为零。第一次运算时，m位宽的c（图中记为c[m-1:0]）和m位宽的b（图中记为b[m-1:0]）相加的m+1位结果（图中记为c+b[m:0]）和m位的c作为二选一选择器（MUX）的输入，然后根据a的最低位a[0]是否为1的判断来选择(SEL)输出，如果a的最低位是1，则输出m位的c和m位的b相加的结果并相应地存放到m+1位寄存器yout_r中（图中记为yout_r[m:0]），否则输出m位的c值存放到m+1位寄存器yout_r，寄存器yout_r的最高位，即第m位，在硬件实现中会自动补0。接着将m+1位的寄存器yout_r和m位的素数p（图中记为p[m-1:0]）进行比较，如果前者比后者大，则执行减法和左移运算，减法就是m+1位的c（图中记为c[m:0]）与m位的素数p相减，左移就是将m位的b左移一位。因为减法运算和移位运算每次只执行一次，并且两者是彼此独立的，所以可以同时执行两条这两步运算的，这里就充分说明了此发明的并行性特点。将m位的b（图中记为b[m-1:0]）进行左移得到m+1位的输出b（图中记为b[m:0]），然后将m+1位b继续和m位的素数p进行比较，如果前者比后者大，则执行减法和右移运算，减法就是m+1位的b与m-1位的素数p相减，右移就是将m位的a（图中记为a[m-1:0]）右移一位。减法运算和移位运算每次也只执行一次，并且两者是彼此独立的，所以也是可以同时执行两条这两步运算的，这里也充分说明了此发明的并行性特点。最后将m位的a（图中记为a[m-1:0]）进行右移（右移之后，a的位宽还是保持之前定义的m位，高位补零）得到的输出值和0值进行比较，如果两者相等，则输出m位的结果yout（图中记为yout[m-1:0]）。到此，模乘运算结束。

[0078] 本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。