Patent ID: 8755517

Claim:
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 ) , ⁢ where m ( u - 1 ) < m ( u - 2 ) < … < m ( 1 ) < m ( 0 ) ; M ( 0 ) = m ( 0 ) ⁡ ( r ) + m ( 0 ) 2 ⁢ ( s ) ; M ( i ) = m ( i ) ⁡ ( r ) + m ( i ) 2 ⁢ ( s ) + ( r ) ⁢ ∑ 0 ≤ j < i ⁢ m j ; and M ( 0 ) = M ( 1 ) = … = M ( u - 1 ) ; wherein m represents the number of bits in the binary representation of the scalar integer, m i represents the number of bits in the i th partition, r represents the number of field multiplications of a point doubling operation, and s represents the number of field multiplications of a point addition operation; 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.