同步标量乘法算法

摘要

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

主权项

一种在加密单元中通过同步执行第一标量k乘以椭圆曲线E上的第一点P的第一乘法以及第二标量s乘以上述椭圆曲线E上的第二点Q的第二乘法来执行加密操作的方法，其中所述第一标量k包括一个或多个二进制的位ki，以及所述第二标量s包括一个或多个二进制的位si，其中所述标量k和s包括相同数目的位，i表示所述第一标量k和所述第二标量s中的公共位的位置，所述方法包括：通过下列步骤产生包括第一项和第二项在内的初始运算对：将来自第一乘法和第二乘法的蒙哥马利式子的各个第一项相加；将来自第一乘法和第二乘法的蒙哥马利式子的各个第二项相加；以及以所述初始运算对开始，针对每个位元对(ki，si)，通过下列步骤使用前一运算对来计算下一运算对：如果位元对为(0，0)，则通过下列操作产生下一运算对：将前一运算对的第一项加倍以获得下一运算对的第一项；以及将前一运算对的第一项和第二项相加以获得下一运算对的第二项；如果位元对为(1，1)，则通过下列操作产生下一运算对：将前一运算对的第一项和第二项相加以获得下一运算对的第一项；以及将前一运算对的第二项加倍以获得下一运算对的第二项；如果位元对为(0，1)，则通过下列操作产生下一运算对：将前一运算对的第一项加倍并加上第二点Q，以获得下一运算对的第一项；以及将第一点P和第二点Q与下一运算对的第一项相加；如果位元对为(1，0)，则通过下列操作产生下一运算对：将前一运算对的第一项加倍并加上第一点P，以获得下一运算对的第一项；以及将第一点P和第二点Q与下一运算对的第一项相加。