CN109379191B - 一种基于椭圆曲线基点的点乘运算电路和方法 - Google Patents

Abstract

一种计算椭圆曲线多倍点的电路和方法。在实施例中，所述电路包括：输入模块，获取第一多倍点的第一倍数，其中，所述第一倍数为预定范围内的自然数；ROM模块，包括与固定点的多个第二多倍点各自的第二倍数分别对应的多个地址；地址获取模块，基于第一倍数，获取ROM模块中的至少一个地址，其中，与至少一个地址分别对应的至少一个第二多倍点各自的第二倍数之和等于所述第一倍数；点加运算模块，通过从ROM模块获取所述至少一个第二多倍点各自的坐标，并对至少一个第二多倍点各自的坐标进行点加运算，获取第一多倍点的坐标。本说明书实施例通过对输入多倍点的倍数的合理分组，降低ROM大小的同时减少点加运算的次数，提高运算整体性能。

Description

一种基于椭圆曲线基点的点乘运算电路和方法

技术领域

本说明书实施例涉及椭圆曲线，具体地说涉及基于椭圆曲线基点的点乘运算电路和方法。

背景技术

椭圆曲线是域上亏格为1的光滑射影曲线，椭圆曲线上的点全体构成一个加法群，椭圆曲线上的整点只有有限多个，这些有理点可以通过群上的加法生成。考虑K＝kG，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶，k为小于n的整数，则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。椭圆曲线加密算法由此应运而生。

在金融服务领域，安全是一贯的课题。在金融服务的多个环节均需要用到椭圆曲线加密算法。如何在保证安全的情况下，加速加密算法，已经成为一个课题。

发明内容

根据第一方面，提供一种电路，用于计算椭圆曲线中固定点的多倍点的坐标，所述电路包括：输入模块，配置为，获取第一多倍点的第一倍数，其中，所述第一倍数为预定范围内的自然数；ROM模块，配置为，包括与所述固定点的多个第二多倍点各自的第二倍数分别对应的多个地址，其中，所述多个第二多倍点各自的第二倍数使得：所述预定范围内的任意自然数等于至少一个所述第二倍数之和，其中，所述第二倍数为所述预定范围内的自然数；地址获取模块，配置为，基于所述第一倍数，获取所述ROM模块中的至少一个地址、并将所述至少一个地址输入所述ROM模块，其中，与所述至少一个地址分别对应的至少一个第二多倍点各自的第二倍数之和等于所述第一倍数；点加运算模块，配置为，通过从所述ROM模块获取所述至少一个第二多倍点各自的坐标，并对所述至少一个第二多倍点各自的坐标进行点加运算，获取所述第一多倍点的坐标。

在第一方面的可能实施方式中，所述多个第二多倍点各自的第二倍数以从小到大的顺序被切分为N组，每组包括qM-1个倍数，其中，所述第n+1组中的第m个倍数的值为q^n*M*m、对应的地址为(q^M-1)*n+m，其中，n+1≤N，m≤q^M-1，q为大于等于2的自然数。在第一方面的进一步的可能实施方式中，所述多个第二多倍点各自的第二倍数为预定位数的二进制数、并以从小到大顺序被切分为N组，每组包括2^M-1个倍数，其中，所述第n组中的第m个倍数的值为2^n*M*m、对应的地址为(2^M-1)*n+m，其中，n+1≤N，m≤2^M-1。

在第一方面的可能实施方式中，所述至少一个地址包括第一地址，所述第一地址对应的第二倍数等于所述第一多倍点的第一倍数，所述第一多倍点的坐标为所述第一地址存储的第二多倍点的坐标。

在第一方面的可能实施方式中，所述至少一个地址包括第一地址和第二地址，所述第一地址对应的第二倍数与所述第二地址对应的第二倍数之和等于所述第一多倍点的第一倍数，所述点加运算模块还配置为，通过对第一地址所存储的第二多倍点的坐标与第二地址所存储的第二多倍点的坐标进行点加运算，得到所述第一多倍点的坐标。在第一方面进一步的可能实施方式中，所述坐标为Jacobian射影坐标，所述至少一个第二多倍点包括点P和点Q，所述点加运算模块还配置为，将所述点Q的坐标转换为仿射坐标，并且对点P的Jacobian射影坐标和点Q的仿射坐标执行点加运算。

在第一方面的可能实施方式中，所述电路是FPGA电路。

根据第二方面，提供一种计算椭圆曲线中固定点的多倍点的坐标的方法，所述方法在电路中执行，所述电路包括ROM模块，其中，所述ROM模块包括与所述固定点的多个第二多倍点各自的第二倍数分别对应的多个地址，其中，所述多个第二多倍点各自的第二倍数使得：预定范围内的任意自然数等于至少一个所述第二倍数之和，其中，所述第二倍数为预定范围内的自然数，所述方法包括：获取第一多倍点的第一倍数，其中，所述第一倍数为预定范围内的自然数；基于所述第一倍数，获取所述ROM模块中的至少一个地址，其中，与所述至少一个地址分别对应的至少一个多倍点各自的倍数之和等于所述第一倍数；基于所述至少一个地址，从所述ROM模块获取所述至少一个第二多倍点各自的坐标；以及，通过对所述至少一个多倍点各自的第二坐标进行点加运算，获取所述第一多倍点的坐标。

在第二方面的可能实施方式中，所述至少一个地址包括第一地址，所述第一地址对应的第二倍数等于所述第一多倍点的第一倍数，所述第一多倍点的坐标为所述第一地址存储的第二多倍点的坐标。

在第二方面的可能实施方式中，所述至少一个地址包括第一地址和第二地址，所述第一地址对应的第二倍数与所述第二地址对应的第二倍数之和等于所述第一多倍点的第一倍数，所述对所述至少一个多倍点各自的坐标进行点加运算包括，通过对第一地址所存储的第二多倍点的坐标与第二地址所存储的第二多倍点的坐标进行点加运算，得到所述第一多倍点的坐标。

在第二方面的可能实施方式中，所述多个第二多倍点各自的第二倍数以从小到大的顺序被切分为N组，每组包括qM-1个倍数，其中，所述第n+1组中的第m个倍数的值为q^n*M*m、对应的地址为(q^M-1)*n+m，其中，n+1≤N，m≤q^M-1，q为大于等于2的自然数。

在第二方面的可能实施方式中，所述坐标为Jacobian射影坐标，所述至少一个第二多倍点包括点P和点Q，所述对所述至少一个第二多倍点的坐标进行点加运算而得到第一多倍点的坐标包括，将点Q的坐标转换为仿射坐标，并且对点P的Jacobian射影坐标和点Q的仿射坐标执行点加运算。

本说明书实施例通过将椭圆曲线固定点的若干多倍点的坐标存储在ROM中，并且输入多倍点的倍数查找ROM获得多倍点坐标；并且对多倍点的倍数的合理分组，使得仅有部分多倍点的倍数被映射到ROM地址，而其它多倍点的坐标则通过已映射多倍点的坐标进行点加运算获得。由此，降低ROM大小的同时减少点加运算的次数，提高运算整体性能。

附图说明

为了使本申请实施例中的技术方案及优点更加清楚明白，以下结合附图对本申请的示例性实施例进行进一步详细的说明，显然，所描述的实施例仅是本申请的一部分实施例，而不是所有实施例的穷举。

图1是椭圆曲线多倍点运算的二进制展开法流程图；

图2为本说明书实施例的电路结构图；

图3是进制数序列和存储模块之间的映射关系示意图；

图4是本说明书实施例的一种计算椭圆曲线多倍点的方法的示意图。

具体实施方式

下面结合附图，对本说明书实施例提供的方案进行描述。

图1是椭圆曲线多倍点运算的二进制展开法流程图。椭圆曲线多倍点运算可以应用于椭圆曲线公钥密码算法SM2中。如图1所示，首先在步骤102输入椭圆曲线上的点P，以及倍点的倍数k。P即为椭圆曲线基点G。k为m比特位宽的大整数，

在步骤104，设Q为多倍点运算的输出，其是椭圆曲线上的点。预先将Q初始化为无穷远点O。设j为循环变量，初始值为l；

在步骤106，j＝j-1；然后判断j＝0？

如果j＝0，则进入步骤118，直接输出点Q；否则，进入步骤108，进行2倍点计算Q＝[2]Q；

然后，在步骤110判断k_j。

如果k_j＝1，则进入步骤112，进行点加运算Q＝Q+P，然后返回106；如果k_j＝0则直接返回106。

通过以上多倍点运算的计算流程图可以得出，一次多倍点需要经过多次循环计算后得到最终的输出点Q，其中循环次数由输入整数k的比特位宽决定，在较差情况下一次循环包含一次2倍点运算和一次点加运算。

本说明书的发明人意识到，当多倍点运算中的点为固定点G时，可以通过查找表的方法将其简化为有限次的点加运算，提高计算性能。

图2为本说明书实施例的电路结构图。该电路用于计算椭圆曲线上固定点的多倍点。该电路的部分模块可以采用FPGA系统实现，也可以整个电路均采用FPGA实现。当然，该电路也采用其它的ASIC电路实现。

如图2所示，所述电路包括只读存储ROM模块210，用于存储椭圆曲线关于同一个固定点G的不同多倍点的坐标。只读存储ROM模块210包括若干个存储单元，每个存储单元存储一个多倍点坐标。在多倍点采用X、Y坐标的情形下，可以使每个存储单元同时存储同一个多倍点的X和Y坐标，当然也可以将同一个多倍点的X和Y坐标存储在不同的存储单元中，但是需要确保采用相同或相应的寻址地址，以便从这两个存储单元同时或者异步读取坐标。当然，多倍点采用其它形式的坐标表示法也是可行的。

本说明书实施例建立一个ROM模块和预定范围内的多个自然数的映射关系。多个自然数可以分为第一类数和第二类数。该映射关系使得ROM模块的多个地址中的各地址分别与所述预定范围内的多个第二类数中的一个第二类数对应，且该地址存储有椭圆曲线关于所述固定点的以该第二类数为倍数的多倍点的坐标；在预定范围内的其它各数，例如第一类数，可以表达为至少两个第二类数之和。在一个例子中，预定范围内的多个数是一个进制数序列。

电路还包括输入模块202，输入模块202获取多倍点的倍数k。k为预定范围内的自然数。

电路还包括地址生成模块204，地址生成模块204用于将通过输入模块202输入的多倍点的倍数k获取所述ROM模块中的至少一个地址，其中，所述至少一个地址各自对应的第二类数之和等于多倍点的倍数k。

ROM模块还包括查找子模块，基于所述至少一个地址，从所述ROM模块查找所述至少一个地址分别存储的至少一个多倍点的坐标。

电路还包括点加运算模块206，点加运算模块206用于接收ROM模块210的多倍点的坐标，并且在不止一个多倍点的坐标的情况下，对所述不止一个倍点坐标执行点加运算。

在至少一个地址仅包括第一地址的情况下，所述第一地址对应的一个第二类数等于所述第一多倍点的倍数；所述点加运算模块对第一地址所存储的多倍点的坐标进行点加运算得到所述第一多倍点的坐标。

在所述至少一个地址包括第一地址和第二地址，所述第一地址对应的一个第二类数与所述第二地址对应的一个第二类数之和等于所述第一多倍点的倍数；点加运算模块对第一地址所存储的多倍点的坐标与第二地址所存储的多倍点的坐标进行点加运算得到所述第一多倍点的坐标。

当然，所述至少一个地址也可以包括三个以上的地址，点加运算模块对这三个以上地址所存储的多倍点的坐标进行点加运算得到所述第一多倍点的坐标。

在一个例子中，所述至少一个多倍点包括第三多倍点和第四多倍点，点加运算模块206对Jacobian射影坐标的第三多倍点坐标和转换为仿射坐标后的第四多倍点坐标执行点加运算，得到和多倍点的倍数k对应的多倍点的坐标。

电路还可以包括输出模块208，它将和多倍点的倍数k对应的多倍点的坐标输出。

本说明书实施例通过对输入多倍点的倍数的合理分组，降低ROM大小的同时减少点加运算的次数，提高运算整体性能。

在一个例子中，进制数序列是一个二进制数序列。ROM模块分为N个部分或阵列，每个部分或阵列的存储地址或单元数为2^M-1，N和M均为自然数；任意的多倍点的倍数换算成二进制数，并且以所述M为单位切分为N个切分单元；第n切分单元中的第m值按照映射关系映射为与所述多个地址中的第n部分的第m个地址(或者称为第n阵列的第m个存储单元)对应，该存储单元所存储的坐标所对应多的倍数为2^n*M*m。对应的地址可以记为(2^M-1)*n+m。其中，N和M为自然数，n≤N，m为二进制数且2^m≤2^M。

图3是进制数序列和存储模块之间的映射关系示意图。如图3所示，多倍点的倍数k在转换为二进制数后有32个比特，按4比特(M＝4)为单位进行拆分，可拆分为8个切分单元(N＝8)，即切分单元0-切分单元7。每个切分单元可对应1个存储阵列，即15个存储单元，图中仅仅示意了切分单元0和切分单元1与相应存储阵列之间的对应关系，其它切分单元与存储阵列之间的对应关系依次类推。存储阵列中的每个存储单元存储一个多倍点的坐标，存储单元的标号就是该倍点数。比如切分单元0(n＝0)中的0001(m＝1)对应于第1个存储阵列中的01号存储单元，其中存储了1G的点坐标；切分单元0(n＝0)中的0110(m＝6)对应于第1个存储阵列中的06号存储单元，即存储了6G的点坐标；切分单元1(n＝1)中的1101(m＝13)对应于第2个存储阵列中的13号存储单元(2^1*4*13＝208)，其总序号为208号存储单元，同时它存储了208G的点坐标。

至于其它多倍点的点坐标，没有预先存储，以节约存储空间。这些倍点的点坐标，则需要根据已存储的多倍点的坐标进行点加运算。比如，对于280倍点，280换算为二进制数0001 0010 1000。这个二进制数按照本说明书的切分单元划分法包括了三个切分单元，第三切分单元中0001对应于256倍点，第二切分单元的0010对应于16倍点，第一切分单元的1000对应于8倍点。因此，280倍点可以换算为256倍点+16倍点+8倍点，其中+号表示点加运算。

从图3的例子可以直观看出，切分单元的大小决定了ROM的大小以及需要点加运算的次数，切分单元越大则ROM越大，需要的点加运算次数越少。在具体实施时可以根据需要取两者的折衷。

图3的例子可以容易地扩展到其它进制数序列的情况，比如，十进制数。以三位数为例，可以切分为X00，0X0，00X三个切分单元。直接落入这三个切分单元的数记为第二类数，未能直接落入这三个切分单元的记为第一类数。显然，第一类数可以表达为至少两个第二类数之和。例如，十进制数327可以表达为300+20+7，320为第一类数，300、20和7为第二类数。泛泛地讲，就进制数而言，若干多倍点的倍数按顺序被切分为N组，每组包括q^M-1个倍数，其中，所述第n+1组中的第m个倍数的值为q^n*M*m、对应的地址为(q^M-1)*n+m，其中，n+1≤N，m≤q^M-1，q为大于等于2的自然数。

再回到图2，在一个例子中，ROM模块为只读存储模块，大小为2*960*256比特，每个存储单元的大小为256比特，即ROM的输入输出接口位宽为256比特，其值为(x,y)＝[m*2⁴ⁿ]G，m∈{1,15},n∈{0,63}。X，Y分别存储在两个ROM中的相同地址。

地址生成模块用于生成存储ROM模块的地址，addr＝n*15+k{(n+1)*4-1,n*4}-1；n∈{0,63}。其中，k分为64个切分单元，每一切分单元占用15个ROM地址。n为切分单元号，k{(n+1)*4-1，n*4}的含义是取k的(n+1)*4-1-n*4之间这4个比特中的相应比特。k{3，0}的含义是取k的3-0之间这4个比特中的相应比特。因此，该地址意味着第n个阵列，第k{(n+1)*4-1,n*4}-1个存储单元,即addr＝n*15+m,其中，m＝k{(n+1)*4-1,n*4}-1。

在k命中一个以上切分单元或者对应的存储阵列时，地址可以表达为至少两个地址之和，即

addr1＝n1*15+k{(n1+1)*4-1,n1*4}-1和addr2＝n2*15+k{(n2+1)*4-1,n2*4}-1。换言之，k按照映射规则得到对应的至少两个椭圆曲线点P，记为P1(X1,Y1,Z1)，P2(X2,Y2,Z2)。

点加运算模块实现椭圆曲线点P1(X1,Y1,Z1)和点P2(X2,Y2,Z2)的加法运算，得到点P3(X3,Y3,Z3)。在一个例子中，为了避免模除运算并减少计算量，其中点P1采用Jacobian坐标表示，点P2采用仿射坐标表示，即Z2＝1，输出点P3采用Jacobian坐标表示。加法运算如下：

注：公式中的运算均为模运算。

从上述公式中可以看出，点加运算可以分解为17个模乘运算和9个模加减运算组成。点加运算模块可以包含1个采用流水线设计的模乘运算单元，1个流水线设计的模加减运算，充分分析上述运算的数据依赖关系得到点加运算的最优化的调度方案，优先调度模乘运算，模加减运算与模乘并行执行。

图4是本说明书实施例的一种计算椭圆曲线多倍点的方法的示意图。所述方法在电路中执行，所述电路包括ROM模块，其中，所述ROM模块包括与所述固定点的多个第二多倍点各自的第二倍数分别对应的多个地址，其中，所述多个第二多倍点各自的第二倍数使得：预定范围内的任意自然数等于至少一个所述第二倍数之和，其中，所述第二倍数为预定范围内的自然数。如图4所示，所述方法包括：在步骤S404，根据多倍点的倍数k获取ROM模块中的至少一个地址；其中，与所述至少一个地址分别对应的至少一个多倍点各自的倍数之和等于所述第一倍数。

在步骤S406，基于所述至少一个地址，从所述ROM模块获取所述至少一个多倍点各自的坐标。

在步骤S408，确定有几个多倍点的坐标？如果有一个多倍点的坐标，则进入步骤S422，将当前多倍点的坐标作为所述第一多倍点的坐标。

如果有一个以上的多倍点坐标，则进入步骤S412，对这些多倍点的坐标进行点加运算。

在一个例子中，多个多倍点包括点P和点Q。对Jacobian射影坐标的点P的坐标和转换为仿射坐标后的点Q的坐标执行点加运算。点加运算采用Jacobian坐标和仿射坐标混合的方式，避免模除运算并减少模乘和模加的运算量。

有关计算椭圆曲线多倍点的方法的细节，可以参考前文结合图1-3的描述。在此不复赘述。

本说明书以SM2算法为例进行说明，其椭圆曲线参数为256bit，同样适用于其他椭圆曲线的点乘运算。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的技术方案的基础之上，所做的任何修改、等同替换、改进等，均应包括在本发明的保护范围之内。

Claims (10)

1.一种电路，用于计算椭圆曲线中固定点的多倍点的坐标，所述电路包括：

输入模块，配置为，获取第一多倍点的第一倍数，其中，所述第一倍数为预定范围内的自然数；

ROM模块，配置为，包括与所述固定点的多个第二多倍点各自的第二倍数分别对应的多个地址，其中，所述多个第二多倍点各自的第二倍数使得：所述预定范围内的任意自然数等于至少一个所述第二倍数之和，其中，所述第二倍数为所述预定范围内的自然数，其中，所述多个第二多倍点各自的第二倍数以从小到大的顺序被切分为N组，每组包括q^M-1个倍数，N和M为自然数，其中，第n+1组中的第m个倍数的值为q^n*M*m、对应的地址为(q^M-1)*n+m，其中，n+1≤N，m≤q^M-1，q为大于等于2的自然数；

地址获取模块，配置为，基于所述第一倍数，获取所述ROM模块中的至少一个地址、并将所述至少一个地址输入所述ROM模块，其中，与所述至少一个地址分别对应的至少一个第二多倍点各自的第二倍数之和等于所述第一倍数；

点加运算模块，配置为，通过从所述ROM模块获取所述至少一个第二多倍点各自的坐标，并对所述至少一个第二多倍点各自的坐标进行点加运算，获取所述第一多倍点的坐标。

2.如权利要求1所述的电路，其中，所述多个第二多倍点各自的第二倍数为预定位数的二进制数、并以从小到大顺序被切分为N组，每组包括2^M-1个倍数，其中，第n+1组中的第m个倍数的值为2^n*M*m、对应的地址为(2^M-1)*n+m，其中，n+1≤N，m≤2^M-1。

3.如权利要求1所述的电路，其中，所述至少一个地址包括第一地址，所述第一地址对应的第二倍数等于所述第一多倍点的第一倍数；所述第一多倍点的坐标为所述第一地址存储的第二多倍点的坐标。

4.如权利要求1所述的电路，其中，所述至少一个地址包括第一地址和第二地址，所述第一地址对应的第二倍数与所述第二地址对应的一个第二倍数之和等于所述第一多倍点的第一倍数；所述点加运算模块还配置为，通过对第一地址所存储的第二多倍点的坐标与第二地址所存储的多倍点的坐标进行点加运算，得到所述第一多倍点的坐标。

5.如权利要求4所述的电路，其中，所述坐标为Jacobian射影坐标，所述至少一个第二多倍点包括点P和点Q，所述点加运算模块还配置为，将所述点Q的坐标转换为仿射坐标，并且对点P的Jacobian射影坐标和点Q的仿射坐标执行点加运算。

6.如权利要求1所述的电路，其中，所述电路是FPGA电路。

7.一种计算椭圆曲线中固定点的多倍点的坐标的方法，所述方法在电路中执行，所述电路包括ROM模块，其中，所述ROM模块包括与所述固定点的多个第二多倍点各自的第二倍数分别对应的多个地址，其中，所述多个第二多倍点各自的第二倍数使得：预定范围内的任意自然数等于至少一个所述第二倍数之和，其中，所述第二倍数为预定范围内的自然数，其中，所述多个第二多倍点各自的第二倍数以从小到大的顺序被切分为N组，每组包括q^M-1个倍数，N和M为自然数，其中，第n+1组中的第m个倍数的值为q^n*M*m、对应的地址为(q^M-1)*n+m，其中，n+1≤N，m≤q^M-1，q为大于等于2的自然数，所述方法包括：

获取第一多倍点的第一倍数，其中，所述第一倍数为预定范围内的自然数；

基于所述第一倍数，获取ROM模块中的至少一个地址；其中，与所述至少一个地址分别对应的至少一个多倍点各自的倍数之和等于所述第一倍数；

基于所述至少一个地址，从所述ROM模块获取所述至少一个第二多倍点各自的坐标；以及

通过对所述至少一个多倍点各自的坐标进行点加运算，获取所述第一多倍点的坐标。

8.如权利要求7所述的方法，其中，所述至少一个地址包括第一地址，所述第一地址对应的第二倍数等于所述第一多倍点的第一倍数，所述第一多倍点的坐标为所述第一地址存储的第二多倍点的坐标。

9.如权利要求7所述的方法，其中，所述至少一个地址包括第一地址和第二地址，所述第一地址对应的第二倍数与所述第二地址对应的第二倍数之和等于所述第一多倍点的第一倍数；所述对所述至少一个多倍点各自的坐标进行点加运算包括，通过对第一地址所存储的第二多倍点的坐标与第二地址所存储的第二多倍点的坐标进行点加运算，得到所述第一多倍点的坐标。

10.如权利要求7所述的方法，其中，所述坐标为Jacobian射影坐标，所述至少一个第二多倍点包括点P和点Q，所述对所述至少一个第二多倍点的坐标进行点加运算而得到第一多倍点的坐标包括，将点Q的坐标转换为仿射坐标，并且对点P的Jacobian射影坐标和点Q的仿射坐标执行点加运算。

Images