本发明公开一种椭圆曲线点乘硬件快速实现方法，本发明基于蒙哥马利算法的椭圆曲线点乘算法，采用硬件并行运算的特点，在资源消耗量没有明显的增加的情况下，将点乘运算中比较耗时的步骤进行拆分，重新组合，设计出了基点乘法1、基点乘法2和基点乘法3三个新的并行运算模块，同时在方法开始时增加了一个对随机数的预判断，形成了一个新的比较节省时间的点乘硬件实现方法。在资源消耗量没有明显的增加的情况下，提高了运算速度。同时在复杂度适中的情况下，适用于固定点点乘与非固定点点乘，提高了通用性。
1.一种椭圆曲线点乘硬件快速实现方法，其具体步骤如下：
(1)数据输入：通过数据输入端接收来自外部一个随机数和一个二进制域椭圆曲线基点；
(3)获取两倍基点的x坐标值：通过乘法组合运算获取两倍基点的x坐标值，在标准投影坐标下将基点、两倍基点的X坐标值、Z坐标值分别存放在寄存器X1、Z1、X2、Z2中；
(4)调用寄存器中的值：主状态机调用上一次运算结束后存放在寄存器X1、Z1、X2、Z2中的值；
(5)判断位操作：主状态机从随机数的最高位开始往低位进行逐位判断，若随机数当前判断位的值为1，则执行步骤(6)，若为0，则执行步骤(7)；
调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
调用乘法模块求基点x坐标值和寄存器Z1中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中的值相加后求平方，其结果存放在寄存器Z1中；将寄存器X2中的值求四次方，其结果存放在寄存器X2中；将寄存器Z2中的值求四次方，其结果存放在寄存器X1中；
主状态机调用乘法模块求b与寄存器X1中值的乘积，再将乘积结果与寄存器X2中值相加，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值求平方，其结果存放在寄存器X1中；将寄存器Z3、Z4中值相加，其结果存放在寄存器X2中；
调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
调用乘法模块求基点x坐标值和寄存器Z2中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中值相加后求平方，其结果存放在寄存器Z2；将寄存器X1中值求四次方，其结果存放在寄存器X2中；将寄存器Z1中值求四次方，其结果存放在寄存器X1中；
主状态机调用乘法模块求b与寄存器X2中值的乘积，再将乘积结果与寄存器X1中值相加，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值求平方，其结果存放在寄存器X1中；将寄存器Z3和Z4中值相加，其结果存放在寄存器X2中；
主状态机在收到6d)或7d)发出的任意一个完成信号之后，完成以下步骤：
8b)根据当前判断位是否还在随机数内，检查随机数最低位是否已经根据步骤(5)完成了判断，如果完成了判断，则执行步骤(9)，否则，重复执行步骤(4)；
主状态机通过对存放在寄存器X1、Z1中的X坐标值和Z坐标值进行除法运算，得到了点乘的x坐标值；
10a)主状态机调用存放在寄存器X1、Z1、X2、Z2中的值；
调用乘法模块求寄存器Z1中值和基点x坐标值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z2中值和基点x坐标值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z1、Z2中值的乘积，其结果存放在寄存器Z5中；
将基点x坐标值和点乘x坐标值相加，其结果存放在寄存器Z1中；将寄存器Z3、X1中值相加，其结果存放在寄存器Z3中；将寄存器Z4、X2中值相加，其结果存放在寄存器Z4中；将基点x坐标值平方后与基点y坐标值相加，其结果存放寄存器Z2中；
调用乘法模块求寄存器Z3、Z4中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z5、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z5中值和基点x坐标值的乘积，其结果存放在寄存器Z5中；
10e)主状态机将寄存器Z3与Z4中值相加，其结果存放在寄存器Z3中；
10f)主状态机调用求逆模块，对寄存器Z5中值进行一次求逆，将求逆结果存放在寄存器Z5中；
10g)主状态机调用一个乘法模块求寄存器Z5、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
10h)主状态机调用一个乘法模块求寄存器Z4、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
10i)主状态机将寄存器Z3的值与基点的y坐标值相加，得到点乘y坐标值；
(11)输出：将得到的点乘的x坐标值和y坐标值通过数据输出端口进行输出操作。
2.根据权利要求1所述的椭圆曲线点乘硬件快速实现方法，其特征在于，步骤(2)中所述随机数的获取步骤是，主状态机调用预判断模块，从输入的固定位数的随机数最高位开始判断，遇到0继续往低位走，遇到1停止，从停止位对随机数进行截取，得到一个新的可供运算的随机数。
3.根据权利要求1所述的椭圆曲线点乘硬件快速实现方法，其特征在于，步骤(3)中所述乘法组合运算的方法是，主状态机通过调用乘法模块，将基点的x坐标值四次方后加1，再将基点的x坐标值平方，得到在标准投影坐标下两倍基点的X坐标值和Z坐标值；主状态机对X坐标值和Z坐标值进行相除，得到两倍基点的x坐标值。
椭圆曲线点乘硬件快速实现方法
技术领域
[0001] 本发明涉及通信技术领域，更进一步涉及密码学领域中的椭圆曲线点乘硬件快速实现方法。该方法可以用于固定点与非固定点的点乘运算，从而提高椭圆曲线数字签名(ECDSA)，椭圆曲线加解密(ECIES)，椭圆曲线密钥分配(ECDH)和椭圆曲线密钥对生成的运算速度。
背景技术
[0002] 目前，国内外在对于基于椭圆曲线点乘运算上主要有两种方法，梳法和蒙哥马利点乘方法。
[0003] 微软公司在其专利申请文件“椭圆曲线点乘法”(公开号CN 101507176A，申请号200680031543.3，申请日2006.6.29)中提出一种新的用梳法表示k的点乘计算方法，通过将奇整数k转换成二进制，然后再将该二进制配置成梳比特列，并且提出了一种更高效的比已知的梳法保存更少点的梳法变形，梳法变形在抗简单能量分析攻击上具体比较好的表现。这种方法存在的明显不足是，只能适合于固定点的点乘运算，应用范围窄。而且该方法在运算时还需要进行预计算，从而增加在系统外的开销，使得其应用范围有一定的限度。
[0004] 清华大学在其专利申请文件“椭圆曲线密码系统的倍点系统”(公开号CN101262345A，申请号200810055618.2，申请日20081.4)与“椭圆曲线密码系统的点加系统”(公开号CN 101221491A，申请号200810055610.6，申请日2008.1.4)中公开了一种新型的倍点和点加系统，将点乘运算分解为点加和倍点运算，分别投影到仿射坐标系和雅格比投影坐标系，然后在不增加面积的情况下，以流水线结构将点加和倍点组合在一起，从而达到在一个基本层面优化椭圆曲线的点乘性能。该方法存在的不足是，这种点乘运算的组合方法在进行点乘运算时，其复杂度将随k值的增加而增加，而且在点乘运算速度过慢的问题上没有很大的改进。
发明内容
[0005] 本发明的目的在于克服上述现有技术的不足，提出了一种适用于硬件实现的快速点乘方法。该方法可以使点乘运算在满足通用性的前提下能够以较小的面积和较快的速度来完成运算，从而提高了ECDSA，ECIES，椭圆曲线密钥对的生成和ECDH的运算速度。
[0006] 本发明实现的思路是，基于Lopez和Dahab两位学者提出的基于蒙哥马利算法的椭圆曲线点乘算法，利用硬件并行运算的特点，在资源消耗量没有明显的增加的情况下，将点乘运算中比较耗时的步骤进行拆分，重新组合形成一个新的比较节省时间的点乘硬件实现方法。
[0007] 本发明的具体实现步骤如下：
[0008] (1)数据输入：通过数据输入端接收来自外部一个随机数和一个二进制域椭圆曲线基点；
[0009] (2)获取随机数；
[0010] (3)获取两倍基点的x坐标值：通过乘法组合运算获取两倍基点的x坐标值，在标准投影坐标下将基点、两倍基点的X坐标值、Z坐标值分别存放在寄存器X1、Z1、X2、Z2中；
[0011] (4)调用寄存器中的值：主状态机调用上一次运算结束后存放在寄存器X1、Z1、X2、Z2中的值；
[0012] (5)判断位操作：主状态机从随机数的最高位开始往低位进行逐位判断，若随机数当前判断位的值为1，则执行步骤(6)，若为0，则执行步骤(7)；
[0013] (6)基点乘法1运算
[0014] 6a)主状态机同时做以下四个乘法运算：
[0015] 调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
[0016] 6b)主状态机同时做以下五个运算：
[0017] 调用乘法模块求基点x坐标值和寄存器Z1中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中的值相加后求平方，其结果存放在寄存器Z1中；将寄存器X2中的值求四次方，其结果存放在寄存器X2中；将寄存器Z2中的值求四次方，其结果存放在寄存器X1中；
[0018] 6c)主状态机同时做以下三个运算：
[0019] 主状态机调用乘法模块求b与寄存器X1中值的乘积，再将乘积结果与寄存器X2中值相加，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值求平方，其结果存放在寄存器X1中；将寄存器Z3、Z4中值相加，其结果存放在寄存器X2中；
[0020] 6d)发出一个完成信号给步骤(8)；
[0021] (7)基点乘法2运算
[0022] 7a)主状态机同时做以下四个乘法运算：
[0023] 调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
[0024] 7b)主状态机同时做以下五个运算：
[0025] 调用乘法模块求基点x坐标值和寄存器Z2中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中值相加后求平方，其结果存放在寄存器Z2；将寄存器X1中值求四次方，其结果存放在寄存器X2中；将寄存器Z1中值求四次方，其结果存放在寄存器X1中；
[0026] 7c)主状态机同时做以下三个运算：
[0027] 主状态机调用乘法模块求b与寄存器X2中值的乘积，再将乘积结果与寄存器X1中值相加，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值求平方，其结果存放在寄存器X1中；将寄存器Z3和Z4中值相加，其结果存放在寄存器X2中；
[0028] 7d)发出一个完成信号给步骤(8)；
[0029] (8)判断重复条件
[0030] 主状态机在收到6d)或7d)发出的任意一个完成信号之后，完成以下步骤：
[0031] 8a)控制当前判断位向下移一位；
[0032] 8b)根据当前判断位是否还在随机数内，检查随机数最低位是否已经根据步骤(5)完成了判断，如果完成了判断，则执行步骤(9)，否则，重复执行步骤(4)；
[0033] (9)获取点乘的x坐标值
[0034] 主状态机通过对存放在寄存器X1、Z1中的X坐标值和Z坐标值进行除法运算，得到了点乘的x坐标值；
[0035] (10)基点乘法3运算
[0036] 10a)主状态机调用存放在寄存器X1、Z1、X2、Z2中的值；
[0037] 10b)主状态机同时做以下三个乘法运算：
[0038] 调用乘法模块求寄存器Z1中值和基点x坐标值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z2中值和基点x坐标值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z1、Z2中值的乘积，其结果存放在寄存器Z5中；
[0039] 10c)主状态机同时做以下四个运算：
[0040] 将基点x坐标值和点乘x坐标值相加，其结果存放在寄存器Z1中；将寄存器Z3、X1中值相加，其结果存放在寄存器Z3中；将寄存器Z4、X2中值相加，其结果存放在寄存器Z4中；将基点x坐标值平方后与基点y坐标值相加，其结果存放寄存器Z2中；
[0041] 10d)主状态机同时做以下三个乘法运算：
[0042] 调用乘法模块求寄存器Z3、Z4中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z5、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z5中值和基点x坐标值的乘积，其结果存放在寄存器Z5中；
[0043] 10e)主状态机将寄存器Z3与Z4中值相加，其结果存放在寄存器Z3中；
[0044] 10f)主状态机调用求逆模块，对寄存器Z5中值进行一次求逆，将求逆结果存放在寄存器Z5中；
[0045] 10g)主状态机调用一个乘法模块求寄存器Z5、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
[0046] 10h)主状态机调用一个乘法模块求寄存器Z4、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
[0047] 10i)主状态机将寄存器Z3的值与基点的y坐标值相加，得到点乘y坐标值；
[0048] (11)输出：将得到的点乘的x坐标值和y坐标值通过数据输出端口进行输出操作。
[0049] 本发明与现有技术相比具有以下优点：
[0050] 第一，本发明在基点乘法1运算、基点乘法2运算和基点乘法3运算中，采用硬件并行运算的方法，克服了现有技术中运算速度过慢的问题，在资源消耗量没有明显的增加的情况下，提高了运算速度。
[0051] 第二，本发明的所有步骤均不需要对基点进行预计算，克服了现有技术中需要预计算而额外增加资源消耗的问题和预计算只能使用于固定点点乘的问题，在复杂度适中的情况下，适用于固定点点乘与非固定点点乘，提高了通用性。
附图说明
[0052] 图1为本发明方法流程图。
具体实施方式
[0053] 结合附图1，对本发明的步骤做进一步的描述。
[0054] 本发明的实施例选择标准投影坐标下基于二进制正规基的191位椭圆曲线。由于在正规基下的平方和开方就是移位运算，加法在硬件下实现也是一个逐位异或，因此将加法和平方两个运算放到主状态机中进行。
[0055] 步骤1.数据输入：通过数据输入端接收来自外部一个随机数和一个二进制域椭圆曲线基点。
[0056] 步骤2.获取随机数；
[0057] 随机数的获取步骤是，主状态机调用预判断模块，从输入的固定位数的随机数最高位开始判断，遇到0继续往低位走，遇到1停止，从停止位对随机数进行截取，得到一个新的可供运算的随机数。
[0058] 步骤3.获取两倍基点的x坐标值：通过乘法组合运算获取两倍基点的x坐标值，在标准投影坐标下将基点、两倍基点的X坐标值、Z坐标值分别存放在寄存器X1、Z1、X2、Z2中，乘法组合运算的方法是，主状态机通过调用乘法模块，将基点的x坐标值四次方后加1，再将基点的x坐标值平方，得到在标准投影坐标下两倍基点的X坐标值和Z坐标值；主状态机对X坐标值和Z坐标值进行相除，得到两倍基点的x坐标值。
[0059] 步骤4.调用寄存器中的值：主状态机调用上一次运算结束后存放在寄存器X1、Z1、X2、Z2中的值。
[0060] 步骤5.判断位操作
[0061] 主状态机从随机数的最高位开始往低位进行逐位判断，若随机数当前判断位的值为1，则跳转至步骤(6)，若为0，则跳转至步骤(7)。
[0062] 步骤6.基点乘法1运算
[0063] 6a)主状态机同时做以下四个乘法运算：
[0064] 调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
[0065] 6b)主状态机同时做以下五个运算：
[0066] 调用乘法模块求基点x坐标值和寄存器Z1中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中的值逐位异或后循环左移一位，其结果存放在寄存器Z1中；将寄存器X2中的值循环左移两位，其结果存放在寄存器X2中；将寄存器Z2中的值循环左移两位，其结果存放在寄存器X1中；
[0067] 6c)主状态机同时做以下三个运算：
[0068] 主状态机调用乘法模块求b与寄存器X1中值的乘积，再将乘积结果与寄存器X2中值进行逐位异或操作，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值循环左移一位，其结果存放在寄存器X1中；将寄存器Z3、Z4中值进行逐位异或操作，其结果存放在寄存器X2中；
[0069] 6d)发出一个完成信号给步骤(8)；
[0070] 从而得到了在标准投影坐标下当前判断位对应的两个不同迭代形式点乘的X坐标值和Z坐标值，这些坐标值存放在寄存器中X1、Z1、X2、Z2中。
[0071] 步骤7.基点乘法2运算
[0072] 7a)主状态机同时做以下四个乘法运算：
[0073] 调用乘法模块求寄存器X1、Z1中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器X2、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器X1、Z2中值的乘积，其结果存放在寄存器Z5中；调用乘法模块求寄存器X2、Z1中值的乘积；其结果存放在寄存器Z6中；
[0074] 7b)主状态机同时做以下五个运算：
[0075] 调用乘法模块求基点x坐标值和寄存器Z2中值的乘积，将乘积结果存放在寄存器Z3中；调用乘法模块求寄存器Z3、Z4中值的乘积，将结果存放在寄存器Z4中；将寄存器Z5与Z6中值逐位异或后循环左移一位，其结果存放在寄存器Z2；将寄存器X1中值循环左移两位，其结果存放在寄存器X2中；将寄存器Z1中值循环左移两位，其结果存放在寄存器X1中；
[0076] 7c)主状态机同时做以下三个运算：
[0077] 主状态机调用乘法模块求b与寄存器X2中值的乘积，再将乘积结果与寄存器X1中值进行逐位异或操作，其结果存放在寄存器Z2中，其中，b是二进制椭圆曲线Weierstrass方程的一个系数；将寄存器Z5中值循环左移一位，其结果存放在寄存器X1中；将寄存器Z3和Z4中值进行逐位异或操作，其结果存放在寄存器X2中；
[0078] 7d)发出一个完成信号给步骤(8)；
[0079] 从而得到了在标准投影坐标下当前判断位对应的另外两个不同迭代形式点乘的X坐标值和Z坐标值，这些坐标值存放在寄存器中X1、Z1、X2、Z2中。
[0080] 步骤8.判断重复条件
[0081] 主状态机在收到6d)和7d)发出的任意一个完成信号之后，完成以下步骤：
[0082] 8a)控制当前判断位向下移一位；
[0083] 8b)根据当前判断位是否还在随机数内，检查随机数最低位是否已经根据步骤(5)完成了判断，如果完成了判断，则执行步骤(9)，否则，重复执行步骤(4)。
[0084] 步骤9.获取点乘的x坐标值
[0085] 主状态机通过对存放在寄存器X1、Z1中的X坐标值和Z坐标值进行除法运算，得到了点乘的x坐标值。
[0086] 步骤10.基点乘法3
[0087] 10a)主状态机调用存放在寄存器X1、Z1、X2、Z2中的值；
[0088] 10b)主状态机同时做以下三个乘法运算：
[0089] 调用乘法模块求寄存器Z1中值和基点x坐标值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z2中值和基点x坐标值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z1、Z2中值的乘积，其结果存放在寄存器Z5中；
[0090] 10c)主状态机同时做以下四个运算：
[0091] 将基点x坐标值和点乘x坐标值进行逐位异或操作，其结果存放在寄存器Z1中；将寄存器Z3、X1中值进行逐位异或操作，其结果存放在寄存器Z3中；将寄存器Z4、X2中值进行逐位异或操作，其结果存放在寄存器Z4中；将基点x坐标值循环左移一位后与基点y坐标值逐位异或，其结果存放在寄存器Z2中；
[0092] 10d)主状态机同时做以下三个乘法运算：
[0093] 调用乘法模块求寄存器Z3、Z4中值的乘积，其结果存放在寄存器Z3中；调用乘法模块求寄存器Z5、Z2中值的乘积，其结果存放在寄存器Z4中；调用乘法模块求寄存器Z5中值和基点x坐标值的乘积，其结果存放在寄存器Z5中；
[0094] 10e)主状态机将寄存器Z3与Z4中值进行逐位异或操作，其结果存放在寄存器Z3中；
[0095] 10f)主状态机调用求逆模块，对寄存器Z5中值进行一次求逆，将求逆结果存放在寄存器Z5中；
[0096] 10g)主状态机调用一个乘法模块求寄存器Z5、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
[0097] 10h)主状态机调用一个乘法模块求寄存器Z4、Z3中值的乘积，将乘积结果存放在寄存器Z3中；
[0098] 10i)主状态机将寄存器Z3中的值与基点的y坐标值进行逐位异或操作，得到点乘的y坐标值。
[0099] 步骤11.输出：将得到的点乘的x坐标值和y坐标值通过数据输出端口进行输出操作。
