Method for elliptic curve scalar multiplication

A method for elliptic curve scalar multiplication of a private key k with a point P, comprising the steps of:

• (a) precomputing a plurality of points on an elliptic curve, each of the points corresponding to scalar multiplication of the point P with different partition sizes;
• (b) partitioning the elliptic curve private key k into a plurality of partitions of random sizes;
• (c) for each of the partitions, performing scalar multiplication of the key partition with the precomputed point corresponding to the size of the key partition to obtain a plurality of intermediate scalar multiplication products;
• (d) in step (c), randomly performing the scalar multiplication for at least one of the partitions in binary form and for the remainder of the partitions in Non-Adjacent Form (NAF);
• (e) selecting a random bit r;
• (f) in performing bit operations in steps (c) and (d), when a bit ki of the private key k is equal to zero, performing a dummy addition when the random bit r is equal to 1 and not performing a dummy addition when the random bit r is equal to 0;
• and
• (g) adding the plurality of intermediate scalar multiplication products to obtain the scalar multiplication product kP.

A cryptographic device for elliptic curve scalar multiplication in an elliptic curve cryptosystem implemented over an insecure communications channel, the device comprising:

• (a) means for precomputing a plurality of points on an elliptic curve, each of the points corresponding to scalar multiplication of the point P with different partition sizes;
• (b) means for partitioning the elliptic curve private key k into a plurality of partitions of random sizes;
• (c) for each of the partitions, means for performing scalar multiplication of the key partition with the precomputed point corresponding to the size of the key partition to obtain a plurality of intermediate scalar multiplication products;
• (d) means for randomly performing the scalar multiplication for at least one of the partitions in binary form and for the remainder of the partitions in Non-Adjacent Form (NAF);
• (e) means for selecting a random bit r;
• (f) means for performing a dummy addition when the random bit r is equal to 1 and not performing a dummy addition when the random bit r is equal to 0 if the bit ki of the private key k is equal to zero;
• and
• (g) means for adding the plurality of intermediate scalar multiplication products to obtain the scalar multiplication product kP.