Patent ID: 8422685

Claim:
A method for elliptic curve scalar multiplication of a private key k with a point P for communications in an electronic communications system encrypted using elliptic curve cryptography, comprising the steps of: (a) representing an elliptic curve private key k in binary form as k=(k m-1 , . . . , k 0 ), wherein m is an integer and k m-1 is a most significant bit of k; (b) defining an integer value u and a rational number v, wherein v = m u ; (c) appending (uv−m) zero bits to a left side of the binary representation of k to form an appended elliptic curve private key; (d) partitioning the appended elliptic curve private key into u partitions, each of the partitions having a length v, such that k=k (u-1) ∥k (u-2) ∥ . . . ∥k (1) ∥k (0) ; (e) distributing each of the partitions to a respective one of u is parallel processors; (f) computing by a computing device a scalar multiplication product kP as kP=2 v ( . . . 2 v (2 v k (u-1) P+k (u-2) P)+ . . . . +k (1) P)+k (0) P, where k (i) P=2( . . . 2(2k iv+v−1 P+k iv+v−2 P)+ . . . +k iv+1 P)+k iv+0 P for 0≦i≦u−1, each k (i) P being computed on a respective one of the u parallel processors, the computations of k (i) P being computed simultaneously in parallel.