同步标量乘法算法

摘要

在计算椭圆曲线方案的点乘(例如kP和sQ)中，分别使用如蒙哥马利算法以达到加和kP+sQ的目的，在分别计算kP和sQ时，若干重复的运算可同时执行。本发明提供一种同步标量乘法算法可减少加倍和加和运算的总数，因而为多标量乘法提供一种高效的算法。P和Q算法的对中的元素被组合成单一对，且k和s的位在每一步中被作为位元对来评估。当k和s的位相等时，仅需要一个加倍运算和一个加和运算来计算当前位；当k和s的位不等时，仅需要一个加倍运算和两个加和运算。

主权项

1.一种在椭圆曲线密码系统中用于同步执行第一标量k乘以椭圆曲线E上的第一点P的第一乘法以及第二标量s乘以上述椭圆曲线E上的第二点Q的第二乘法的方法，该方法包括对于t位元对(ki，si)，根据上述位元对(ki，si)中表示的值来同步执行上述第一、第二乘法中的至少一个重复的运算以由此减少上述乘法中每一步的数学运算的数量，这里t表示上述标量的总位数，i表示上述第一、第二标量正在被评估的当前位。