Patent ID: 8615080

Claim:
A method, for being performed by a computer system, of countering power analysis attacks, said method comprising: receiving a base point on an elliptic curve and a scalar, said base point having a prime order; generating a random integer, wherein said random integer is invertible modulo said order of said base point; obtaining a first factor by multiplying said random integer by said base point; obtaining, at a microprocessor, a second factor by dividing said scalar by said random integer using modular division, wherein a modulus used for said modular division is said order of said base point, said modular division involving a Montgomery Inversion and a Montgomery Multiplication, said Montgomery Inversion involving an Almost Montgomery Inversion, said Almost Montgomery Inversion having a main loop structure having a plurality of branches, each branch of said plurality of branches including a predetermined set of operations executed on a plurality of variables; obtaining a product by multiplying said first factor by said second factor using Montgomery Multiplication; and publishing said product as an elliptic curve scalar multiplication product of said scalar and said base point; wherein a given branch among said plurality of branches is associated with a first answer to a first conditional determination and at least one further conditional determination is associated with a second answer to said first conditional determination, wherein said second answer is an alternative to said first answer and said given branch includes as many additional conditional determinations identical to said first conditional determination as there are possible conditional determinations associated with said second answer.