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:
“Journey to Gethsemane, go and feel the tempter’s power;
Your Redeemer’s conflict see, watch the anguish of this hour;
Do not hide or turn away: learn from Jesus how to pray.”
—James Montgomery (1771–1854)
“Surely it is one of the requisites of a tasteful garb that the expression of effort to please shall be wanting in it; that the mysteries of the toilet shall not be suggested by it; that the steps to its completion shall be knocked away like the sculptor’s ladder from the statue, and the mental force expended upon it be swept away out of sight like the chips on the studio floor.”
—Elizabeth Stuart Phelps (1844–1911)
“The more technique you have, the less you have to worry about it. The more technique there is, the less there is.”
—Pablo Picasso (1881–1973)