Patent Document ID: 20120237021
Application ID: 13426004
Patent Flag: 0

Claim One:
1. A method for performing elliptic curve cryptography on a cryptographic module using a Montgomery ladder to compute a point addition of more than two point multiples, each point multiple comprising a point and a scalar having m bits, the method comprising: a) initializing a representation A of the multiples; b) generating an initial state B based on the representation A; c) generating, for a first bit of the m bits, from the representation A and the initial state B: i) a first transition relation F and a second transition relation G, ii) an updated state C, and iii) a difference representation D 0 ; d) repeatedly, for each of the remaining bits of the m bits, from the representation A, the first transition relation F, the second transition relation G, and the updated state C updating: i) the first transition relation F and the second transition relation G, ii) the updated state C, and iii) a difference representation D n for that remaining point multiple; e) identifying a final state B from the last updated state C and a final first transition relation F from the last updated first transition relation F and a final second transition relation G from the last updated second transition relation G; and, e) computing an x-coordinate of the point addition using the final state B, the final first transition relation F, the final second transition relation G and the difference representations D n .