Montgomery's Ladder Technique
Many algorithms for exponentiation do not provide defence against side-channel attacks. Namely, an attacker observing the sequence of squarings and multiplications can (partially) recover the exponent involved in the computation. This is a problem if the exponent should remain secret, as with many public-key cryptosystems. A technique called Montgomery's Ladder addresses this concern.
Given the binary expansion of a positive, non-zero integer n=(nk-1...n0)2 with nk-1=1 we can compute xn as follows:
x1=x; x2=x2 for i=k-2 to 0 do If ni=0 then x2=x1*x2; x1=x12 else x1=x1*x2; x2=x22 return x1The algorithm performs a fixed sequence of operations (up to log n): a multiplication and squaring takes place for each bit in the exponent, regardless of the bit's specific value.
Read more about this topic: Exponentiation By Squaring
Famous quotes containing the words montgomery, ladder and/or technique:
“Stand up and bless the Lord,
Ye children of His choice;
Stand up, and bless the Lord your God
With heart, and soul, and voice.”
—James Montgomery (1771–1854)
“This monument, so imposing and tasteful, fittingly typifies the grand and symmetrical character of him in whose honor it has been builded. His was “the arduous greatness of things done.” No friendly hands constructed and placed for his ambition a ladder upon which he might climb. His own brave hands framed and nailed the cleats upon which he climbed to the heights of public usefulness and fame.”
—Benjamin Harrison (1833–1901)
“Every notable advance in technique or organization has to be paid for, and in most cases the debit is more or less equivalent to the credit. Except of course when it’s more than equivalent, as it has been with universal education, for example, or wireless, or these damned aeroplanes. In which case, of course, your progress is a step backwards and downwards.”
—Aldous Huxley (1894–1963)