Method for generic-point parallel elliptic curve scalar multiplication

摘要

The method for generic-point parallel elliptic curve scalar multiplication replaces the pre-computation overhead of conventional elliptic curve scalar multiplication by post-computations that can be parallelized. This greatly increases the speed and efficiency of scalar multiplication performed in elliptic curve cryptography. According to the method, when scalar multiplication is required, the scalar integer is partitioned into a plurality of partitions, and calculations in each partition are performed simultaneously or in parallel on separate processors using conventional binary protocols. The bit size of each partition is adjusted to balance the load between the processors, i.e., so that each processor performs substantially the same number of point operations. The resulting calculations from each partition are accumulated or summed to produce the point that is the product of the scalar multiplication.

主权项

1. A method for generic-point parallel elliptic curve scalar multiplication using a cryptographic device, comprising the steps of:
partitioning a scalar integer, represented as a binary number, into a plurality of partitions; adjusting the number of binary bits in each partition to distribute a number of point operations equally among the partitions by simultaneously solving the following set of equations:m=m(u-1)+m(u-2)+…+m(1)+m(0),⁢wherem(u-1) in each partition, computing a partial product of the partitioned scalar integer and a point on an elliptic curve, the partial products being computed simultaneously in parallel by a plurality of separate hardware processors; and accumulating the partial products from the plurality of partitions to obtain the scalar multiplication product of the scalar integer and the point on the elliptic curve.