Patent Document ID: 8243919
Application ID: 12039996
Patent Flag: 1

Claim One:
1. A method, for being performed by a computer system, of publishing an elliptic curve scalar multiplication product of a scalar and a base point on an elliptic curve in a manner that counters power analysis attacks, said base point having a prime order, said method comprising: receiving said base point and said scalar; 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 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 first swap operation, wherein an address, to which a first variable of said plurality of variables refers, is exchanged with an address to which a second variable of said plurality of variables refers; a second swap operation, wherein an address, to which a third variable of said plurality of variables refers, is exchanged with an addresses to which a fourth variable of said plurality of variables, refers; a first shift operation, wherein bits in a variable of said plurality of variables are shifted right; and a second shift operation, wherein bits in a variable of said plurality of variables are shifted left; obtaining a product by multiplying said first factor by said second factor using Montgomery Multiplication; and publishing said product; wherein the above steps are performed by a micro-processor.