Patent ID: 8045705

Claim:
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 i , s 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 i , s 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 i , s i ) to thereby reduce the number of mathematical operations at each step in said multiplications.