US patent 8045705, Antipa Poeluev, double-scalar multiplication

• 1. A method comprising: performing simultaneously in a computer, in an elliptic curve cryptographic system, a first multiplication of a first point P on an elliptic curve E by a first scalar k and a second multiplication of a second point Q on said elliptic curve E by a second scalar s, wherein said scalars k, s comprise different numbers of bits and wherein said performing comprises: generating an initial computation pair by: determining a one of said scalars k, s which comprises fewer bits; padding said one of said scalars with zeros such that bit lengths of the scalars k, s become equal, thereby providing t bit pairs (k.sub.i, s.sub.i), wherein t represents a total number of bits in each of said scalars and i represents a current bit being evaluated in said first and second scalars; and performing Montgomery's method on bit pairs comprising the padding in said one of said scalars and corresponding bits of other of said scalars to generate said initial computation pair; and for remaining bit pairs (k.sub.i, s.sub.i) beginning with a first pair after the padding, simultaneously performing at least one repetitive operation in said first and second multiplications according to values indicated in each respective said bit pair (k.sub.i, s.sub.i) to thereby reduce the number of mathematical operations at each step in said multiplications.
• 8. A cryptographic system comprising: a processor and memory for storing a program, wherein execution of the program in the memory by the processor causes the cryptographic system to perform the following operations: performing simultaneously, in an elliptic curve cryptographic system, a first multiplication of a first point P on an elliptic curve E by a first scalar k and a second multiplication of a second point Q on said elliptic curve E by a second scalar s, wherein said scalars k, s comprise different numbers of bits, and wherein said performing comprises: generating an initial computation pair by: determining a one of said scalars k, s which comprises fewer bits; padding said one of said scalars with zeros such that bit lengths of the scalars k, s become equal, thereby providing t bit pairs (k.sub.i, s.sub.i, wherein t represents a total number of bits in each of said scalars and i represents a current bit being evaluated in said first and second scalars; and performing Montgomery's method on bit pairs comprising the padding in said one of said scalars and corresponding bits of other of said scalars to generate said initial computation pair; and for remaining bit pairs (k.sub.i, s.sub.i) beginning with a first pair after the padding, simultaneously performing at least one repetitive operation in said first and second multiplications according to values indicated in each respective said bit pair (k .sub.i,s.sub.i)to thereby reduce the number of mathematical operations at each step in said multiplications.

Prior art:

• 2000 Schoenmakers (published 2003 Stam). Merges the Montgomery ladder for mP (2 operations per bit) with a Montgomery ladder for nQ (2 operations per bit), obtaining a faster differential addition chain for mP+nQ (only 3.5 operations per bit on average).
• 2001 Akishita. Improves on 2000 Schoenmakers (only 3 operations per bit on average).

The patent specifically recommends computing mP+nQ together with (m+1)P+(n+1)Q, and says that this requires only 1 doubling and on average 1.5 additions per bit. However, many of these additions flunk the differential-addition requirement; this specific approach is clearly slower than, e.g., 2001 Akishita.