US patent 8284930, Antipa Poeluev, double-scalar multiplication

• 1. 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.sub.i and said second scalar s comprises one or more binary bits s.sub.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.sub.i, s.sub.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.
• 10. A cryptographic unit configured 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.sub.i and said second scalar s comprises one or more binary bits s.sub.i, wherein i represents a common bit position in said first scalar k and said second scalar s, said cryptographic unit comprising: a cryptographic module configured to generate 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.sub.i, s.sub.i), the cryptographic module configured to compute 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.

Prior art: See discussion of 8045705.