椭圆域曲线运算方法和椭圆域曲线运算器

技术领域

本发明涉及一种椭圆域曲线运算方法和椭圆域运算器。

背景技术

对数据进行加密是一种常用且行之有效的信息安全策略。目前基于有限域上椭圆曲线离散对数问题的非对称密码算法ECC（Emmiptic Curve Cryptography，椭圆曲线密码）被公认为是最高比特强度的公钥密码体制，广泛应用于快速加密、密钥交换、身份验证、数字签名、保密通信等领域，是1985年分别由Mimmer和Kobmitz独立提出的。相对于其他的公钥密码系统（如RSA和EmGamam），椭圆曲线密码系统具有计算速度快、存储空间小、带宽要求低等优点。

椭圆曲线公钥密码算法作为ECC算法中的一种，加密强度为256位，安全性高、存储空间小、可以快速完成签名、密钥交换以及加密应用。

椭圆曲线公钥密码算法相关的运算逻辑可以做为独立的单元进行设计，并且采用层次化的划分方式可以分为有限域运算层以及椭圆曲线运算层。

有限域运算层的主要功能是提供椭圆加密算法所需要的数论运算支持，包括256位大整数模加、模减、模乘、模逆、模幂、比较运算。

椭圆曲线运算层由有限域运算层的各种基础运算按照一定的规则进行排序后构成，包括点加、倍点、点乘、坐标转换等运算。点乘运算是在点加、倍点的基础上实现的，同时需要有限域运算的支持，因此点乘运算速度决定了加密机制运算速度。

当前，提升系统整体运算可以通过两种方法来实现：一、提升有限域运算层的基础运算速度，如中国第CN101782845A号发明申请公开针对点加和倍点算法，重新排列了修改的Jacobian坐标点的点加和倍点运算序列，提出了一种实现点加运算和倍点运算的新方法。

再如中国第CN101221491A号发明专利申请公开利用Jacobian坐标系下椭圆曲线点加的计算公式，提取出相互独立的操作，构造三级流水线电路结构。

二、优化点乘运算电路的基础运算调用方式，如中国第CN1822539A发明申请公开采用32个子寄存器构成寄存器堆作为数据暂存单元，缓解大数模运算过程中寄存器堆的复用问题。

但是上述发明专利申请公开的方案均受运算所限制，只能支持模（Mod）运算，对上层运算产生的中间变量则无能为力。

发明内容

本发明的目的在于提供一种椭圆域曲线运算方法，提高运算速度，本发明还提供了一种椭圆域曲线运算器。

依据本发明的一个方面的一种椭圆域曲线运算方法，用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法，该方法基于模的运算，并同时基于点的运算；

其中基于点的运算为对初始点P的运算，并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式：NAF（kp）=（kpm-1……kp1kp0），其中m为NAF表达式的位宽；

并对初始点P进行倍点，生成的倍点：1P、2P、……np；n为大于等于8小于等于17的自然数；

对NAF（kp）与生成的倍点进行点乘，直到运算完成，输出运算结果。

根据权利要求1所述的椭圆域曲线运算方法，其特征在于，对生成的倍点采用给定的数列通式选择出初始倍点，用于初始的点乘运算，并在后续的点乘运算中，给出点乘运算逻辑；

若按照点乘运算逻辑的路径若逻辑出初始倍点，则直接调用该逻辑出的初始倍点进行运算，若逻辑出其余的倍点，则生成逻辑出的相应倍点后进行点乘运算，直到的运算完成。

依据本发明的另一个方面的一种椭圆域曲线运算器，用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法，包括模的运算器和基于点的运算器；

其中点的运算器为对初始点P的运算器，并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式：NAF（kp）=（kpm-1……kp1kp0），其中m为NAF表达式的位宽；

该点的运算器还包括倍点运算器，对初始点P进行倍点，生成的倍点：1P、2P、……np；n为大于等于8小于等于17的自然数；

以及点乘运算器，对NAF（kp）与生成的倍点进行点乘，直到运算完成，输出运算结果。

依据本发明，涉及到的运算比较全面，采用点乘次数k的新的NAF表示方法，似的k的二进制表示中的非零元素的个数减少，从而减少了点加运算的次数，进而减少了点乘的整体运算时间，而具有比较高的运算效率。

附图说明

图1为依据本发明的一种椭圆域运算装置的结构框图。

图2为基于椭圆加密算法的点乘运算状态转移图。

图3为非临接表达式NAF（k）运算状态转移图。

图4为预计算状态转移图。

具体实施方式

如图1所示，为椭圆域运算装置的基本配置，它由五个部分构成，分别是系统总线数据接口模块、配置接口模块、配置寄存器模块、运算单元模块、数据存储单元模块。

基于所述系统总线数据接口模块，图1所示的椭圆域运算装置在系统中以系统总线从设备的形式出现，挂在应用系统的总线上，构成系统总线的从设备。

通过配置接口模块对辅助操作数、运算类型进行配置，运算完成后读出中断信息。

通过系统总线数据接口模块配置操作数。

运算单元模块负责完成各种运算，包括基于模的加法、减法、乘法、取逆、取幂运算，基于点的加法、乘法运算，并在运算完成后产生中断标志位，构成所述中断信息，以使配置接口模块能够读取运算单元模块的运行状态。

数据存储单元模块由4块单口RAM构成，负责存储初始操作数及运算结果，配合运算单元调度完成数据的正确转移。

其中的操作数可以构成为如下所述的倍点。

在这样的一个实施例中，椭圆域曲线运算器，用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法，包括模的运算器和基于点的运算器；

其中点的运算器为对初始点P的运算器，并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式：NAF（kp）=（kpm-1……kp1kp0），其中m为NAF表达式的位宽；

该点的运算器还包括倍点运算器，对初始点P进行倍点，生成的倍点：1P、2P、……np；n为大于等于8小于等于17的自然数；

以及点乘运算器，对NAF（kp）与生成的倍点进行点乘，直到运算完成，输出运算结果。

如图2所示，整个点乘运算阶段分为三部分，分别为标量k的NAF表达式计算，初始预计算，类迭代乘法计算。

通过对标量k进行重新编码，采用有符号二进制编码来减少二进制编码中的非零元个数，能够有效减少点乘运算中的点加运算次数，达到提升点乘算法效率的目的。

本发明所提出的k的NAF表达式计算电路，采用有符号编码中的非相邻有符号二进制表示编码NAF，使得k的二进制表示中的非零元素的个数减少，减少点加次数，减少点乘运算步骤，电路运算状态转移图如图3所示。

具体如下：

NAF_IDME：k的NAF表达式计算初始化阶段，等待NAF计算启动信号，由所述配置接口模块给出，启动后，进入下一步骤，即NAF_RK；

NAF_RK：将标量k从存储单元3中从低位开始读出，进入循环加法器进行计算，读操作结束后，进入NAF_K；

NAF_K：生成NAF(k) = (k_m-1…k₁k₀)，进入NAF_K2KP；

NAF_K2KP：进行NAF(k)向NAF(kp)的转换，转换完成后进入NAF_DONE；

NAF_DONE：k的NAF计算完成，产生运算完成中断，中断被清0后，进入NAF_IDME，等待下一次运算，以响应新的请求。

计算标量k的 NAF（非邻接形式）表达式的算法1如下：

输入：k

输出：NAF(kp)。 

1. 临时变量c ← k, k的NAF表达式位宽m← 0；向左的箭头表示赋值，即设定一个临时变量c，其初始值是k，而k的NAF表达式的初始位宽为0，m表示k的NAF表示式的位宽。

2. 当c > 0时，重复执行：

2.1 如果c % 2 = = 1，则k_m← 2 ? (c mod 4), c ← c ? k_m;否则k_m← 0；“%”表示数学运算“除法运算后取余数”，“==”表示数学运算符“等于”。 

2.2 c ← c/2, m←m + 1。 “/”表示数学运算“除法运算后取整数”

3. 生成NAF(k) = (k_m-1…k₁k₀)。

4.  i从m-1到0，重复执行 

如果 k_i == 1 && k_i-1 == 0 && k_i-2 == -1则kp_i= 0, kp_i-1=kp_i-2= 1,i ← i - 3； 

否则如果k_i == -1 && k_i-1 == 0 && k_i-2 == 1则kp_i= 0, kp_i-1=kp_i-2= -1,i ← i - 3； 

否则kp_i= k_i, i ← i - 1。 

5. 生成NAF(k_p)=( kp_m-1…kp₁kp₀)

预计算过程如图3所示，对初始点P进行倍点、点加运算，可得到1P、2P … 13P中任意一点，由于可用RAM容量有限，暂存1P、5P、9P、13P点，剩余点则在后续运算过程中动态生成，运算过程状态转移图如图4所示。

PRE_IDME：预计算过程初始化阶段，等待预计算启动信号，进入PRE_RM。

PRE_RM：将点P（x_p，y_p，z_p）从存储单元3中读入到存储单元1和存储单元2中，将蒙哥马利乘法辅助算子R，从存储单元4读入到存储单元2中，读操作结束后，进入PRE_DP。

PRE_DP：对存储单元1中的数据进行倍点运算，运算完成后，判断倍点运算次数信号pre_dp_cnt，若为初次运算，则产生2P点后进入PRE_DPM；若为2次运算，则产生4P点后进入PRE_DPM；若为3次运算，则产生8P点后，进入PRE_MZ2B；若为4次运算，则产生12P点后，进入PRE_MZ2B。pre_dp_cnt进行步长为1的累加。

PRE_MZ2B：判断倍点运算次数信号pre_dp_cnt与点加运算次数信号pre_ap_cnt。pre_dp_cnt为2次运算同时pre_ap_cnt为初次运算，进入PRE_AP，其它情况则进入PRE_M1P。

PRE_AP：对存储单元2中的数据进行点加运算，运算完成后，判断点加运算次数信号pre_ap_cnt，若为初次运算，则产生5P点后进入PRE_DPM；若为2次运算，则产生6P点后进入PRE_M6P；若为3次运算，则产生8P点后，进入PRE_CPA；若为4次运算，则产生12P点后，进入PRE_CPA。

PRE_M1P：将P点从存储单元3中读入到存储单元1，与存储单元2中的xP点进行加法运算，生成P+xP点，运算完成后进入PRE_MZ2B。

PRE_M6P：将存储单元2中的6P点读入到存储单元1中，准备进行12P点计算，读入完成后，进入PRE_DP。

PRE_CPA：判断读次数信号pre_rd_cnt，若pre_rd_cnt为0，进入PRE_DPM；若pre_rd_cnt为1，进入PRE_M4P；若pre_rd_cnt为2，则进入PRE_DPM。判断完成后，pre_rd_cnt进行步长为1的累加。

PRE_DPM：将存储单元2中的结果读入到存储单元3中，读出完成后，判断倍点运算次数信号pre_dp_cnt与点加运算次数信号pre_ap_cnt。pre_dp_cnt为2次运算，同时pre_ap_cnt为初次运算，进入PRE_DP；pre_dp_cnt为3次运算，同时pre_ap_cnt为初次运算，进入PRE_M1P；pre_dp_cnt为3次运算，同时pre_ap_cnt为2次运算，进入PRE_MZ2B；pre_dp_cnt为4次运算，同时pre_ap_cn为4次运算，且pre_rd_cnt为1，进入PRE_CPA；pre_dp_cnt为4次运算，同时pre_ap_cnt为4次运算，且pre_rd_cnt为2进入PRE_DONE。

PRE_DONE：预计算完成，产生运算完成中断，中断被清0后，进入PRE_IDME，等待下一次运算。

系统整体算法2如下：

输入：标量k，每个字所占位宽w，点 P。 

输出：Q = kP。 

1. 预计算：

对 i从 1到 2^w-3，计算P_i ← iP。

2.  Q ← 0。 

3.  i 从m-1 到0，重复执行 

3.1 若kp_i= 0，则t←1, u←0； 

否则，寻找一个最大的t≤w使得u←kp_i,…, kp_i-t+1是奇数。 

3.2 Q ← 2^tQ 

3.3 若u > 0，则Q ← Q + P_u； 

否则，若u< 0，则Q ← Q + P_-u。

4.4  i ← i - t。 

5.  返回Q。

从上述方案可以看出：

本方法适用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法。 为了满足椭圆加密算法性能的要求，采用软硬件协同工作的方式实现椭圆加密算法，将耗时的关键运算用本方法直接实现，其余部分用外部控制器的软件实现。采用本方法，有以下有益效果：

1、涉及运算全面，可以实现基于模的加法、减法、乘法、取逆、取模、取幂运算；可以实现基于点的加法、乘法运算；同时可以进行RSA相关的基于模的2048位的加法、减法、比较、乘法运算，所有运算接口向外开放，可以通过总线寄存器接口进行配置，灵活性大；

2、本方法利用了点乘次数k的新的NAF表示方法，使得k的二进制表示中的非零元素的个数减少，所以进行点加运算的次数就会减少，减少了点乘的整体运算时间；

3、本方法在预计算阶段，采用4点计算法，可保证后续运算点在最短时间内完成，同时又不占用过多的数据存储空间。

关于倍点的个数，在前述的预计算中有所体现，其数量的多寡跟硬件配置和加密的复杂程度相关，本领域的技术人员据此可进行选择，推荐8~17个，在硬件有更好的配置时，可以选择更多的个数。