一种椭圆曲线密码的高速运算装置和方法

摘要

本发明涉及一种椭圆曲线密码的高速运算装置和方法。本发明主要针对椭圆曲线为模长160～256比特，素域Fp上的通用曲线。本发明的高速运算装置是基于流水脉动双模乘器的特殊硬件结构，该硬件结构由运算、控制和存储三个部分组成，运算部分包含两个并行流水脉动的模乘器和两组加法器。本发明基于这种特殊的硬件结构，重新排列修改的雅可比坐标投影点的点加和点倍流水运算序列，并且使得相继出现的点加和/或点倍运算首尾相接，双模乘器空闲的时间相互补充。从而提高了流水脉动双模乘器的硬件效率，使得点加运算只占用7个模乘运算周期，点倍运算占4个模乘运算周期，最大幅度地减少点加和/或点倍以及点乘运算的时钟周期数。

主权项

一种椭圆曲线密码的高速运算方法，其适合于利用包括流水脉动双模乘器的硬件结构来实现，所述方法按下面的运算步骤来进行点加运算和点倍运算，其中：P＝(X1，Y1，Z1，aZ14)，Q＝(X2，Y2，Z2，aZ24)是椭圆曲线E(Fp)上的两点在雅可比投影坐标下的表示，当Q为固定点时，Z2＝1，则点加运算P+Q＝(X3，Y3，Z3，aZ34)的运算步骤包括：a)模乘器n计算T0＝Z12＝MontMul(Z1，Z1)；b)模乘器n计算T1＝Z13＝MonMul(Z12，Z1)，模乘器s计算U2＝MontMul(X2，Z12)，并且加法器之一计算H＝ModSub(U2，X1)；c)模乘器s计算S2＝MontMul(Y2，Z13)，加法器之一计算r＝ModSub(S2，Y1)；d)模乘器n计算T2＝H2MontMul(H，H)，模乘器s计算Z3＝MontMul(Z1，H)e)模乘器n计算T3＝H3＝MontMul(H2，H)，模乘器s计算T4＝r2＝MontMul(r，r)，加法器之一计算T5＝ModSub(r2，H3)f)模乘器n计算T7＝X1H2＝MontMul(X1，H2)，模乘器s计算T6＝H4＝MontMul(H3，H)，加法器之一计算X3＝ModSub(r2-H3，2X1H2)，另一个加法器计算T8＝ModSub(X1H2，X3)g)模乘器n计算T9＝Y1H3＝MontMul(Y1，H3)，模乘器s计算T10＝r(X1H2-X3)＝MontMul(r，X1H2-X3)，同时加法器之一计算Y3＝ModSub(r(X1H2-X3)，Y1H3)h)模乘器s计算aZ34＝MontMul(aZ14，H4)；并且点倍运算2P＝(X3，Y3，Z3，aZ34)的运算步骤包括：。i)模乘器n计算T0＝X12＝MontMul(X1，X1)，加法器之一计算M＝ModAdd(3X12，aZ14)；j)模乘器n计算T2＝Y1Z1＝MontMul(Y1，Z1)，模乘器s计算T1＝Y12＝MontMul(Y1，Y1)，加法器之一计算Z3＝ModAdd(Y1Z1，Y1Z1)；k)模乘器n计算S＝MontMul(X1，Y12)，模乘器s计算T3＝M2＝MontMul(M，M)，加法器之一计算X3＝ModSub(M2，8S)，另一个加法器计算T4＝MontSub(4S，X3)；1)模乘器s计算T5＝MontMul(M，4S-X3)，模乘器n计算U＝Y14＝MontMul(Y12，Y12)，加法器之一计算Y3＝ModSub(M(4S-X3)，8U)；m)模乘器s计算aZ34＝MontMul(16U，aZ14)，其中，MontMul(X，Y)表示操作数X、Y做Mongtgomery模乘运算，即XYR-1mod p，p是模数，ModAdd(X，Y)表示操作数X、Y做模加运算，即(X+Y)modp，ModSub(X，Y)表示操作数X、Y做模减运算，即(X-Y)modp，并且其中，当点加运算之后出现点倍运算时，当前点加运算的步骤h)和后续点倍运算的步骤i)同时进行；在点倍运算之后出现点倍运算时，当前点倍运算的步骤m)与后续点倍运算的步骤i)同时进行；在点倍运算之后出现点加运算时，当前点倍运算的步骤m)和后续点加运算的步骤a)同时进行，由此相邻的点运算首尾相接，双模乘器空闲的部分相互补充。