Patent ID: 8284930

Claim:
A method of operating a cryptographic unit to perform a cryptographic operation in a cryptographic communication system by simultaneously performing a first multiplication of a first scalar k by a first point P on an elliptic curve E, and a second multiplication of a second scalar s by a second point Q on said elliptic curve E, wherein said first scalar k comprises one or more binary bits k i and said second scalar s comprises one or more binary bits s i , wherein i represents a common bit position in said first scalar k and said second scalar s, said cryptographic operation comprising: generating an initial computation pair comprising a first term and a second term by: adding respective first terms from Montgomery forms of the first multiplication and the second multiplication; and adding respective second terms from the Montgomery forms for the first multiplication and the second multiplication; and beginning with the initial computation pair, for each bit pair (k i , s i ), computing a next computation pair using a previous computation pair by: if the bit pair is (0,0) generating the next computation pair by: doubling the first term of the previous computation pair to obtain the first term of the next computation pair; and adding the first term and the second term of the previous computation pair to obtain the second term of the next computation pair; if the bit pair is (1,1), generating the next computation pair by: adding the first term and the second term of the previous computation pair to obtain the first term of the next computation pair; and doubling the second term of the previous computation pair to obtain the second term of the next computation pair; if the bit pair is (0,1), generating the next computation pair by: doubling the first term of the previous computation pair and adding the second point Q to obtain the first term of the next computation pair; and adding the first point P and the second point Q to the first term of the next computation pair; and if the bit pair is (1,0), generating the next computation pair by: doubling the first term of the previous computation pair and adding the first point P to obtain the first term of the next computation pair; and adding the first point P and the second point Q to the first term of the next computation pair.