Patent ID: 7864951

Claim:
A method of performing scalar multiplication which uses transition based method when traversing the scalar bits, comprising the steps of: (1) providing an arithmetic processing unit to perform basic elliptic curve doubling (DBL) and addition (ADD) operations; (2) providing three registers Q[0], Q[1] and Q[2]; (3) defining initial point values P and 2P; (4) setting Q[0] equal to P and Q[1] equal to 2P; (5) establishing a current scalar bit value k.sub.i and its predecessor bit value k.sub.iâˆ’1; (6) starting from the next most significant bit, repeating the following steps (7) through (9) until all bits of the scalar are processed; (7) loading the register Q[2] with the contents of Q[0] or Q[1] based on the following: Q[2]=Q[0] if there is a transition from 1 to 0 or from 0 to 1 between the said current scalar bit value k.sub.i and its predecessor bit value k.sub.iâˆ’1 otherwise Q[2]=Q[1] (i.e. Q[2]=Q[1âˆ’(k.sub.i @ k.sub.iâˆ’1)]); (8) performing an ADD operation on the contents of Q[0] and Q[1] and storing the result in Q[0] independently from the scalar bit value; (9) performing a DBL operation on the contents of Q[2] and storing the result in Q[1] independently from the scalar bit value; and, (10) returning Q[1âˆ’k.sub.0].