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:
“The fates are not quite obdurate;
They have a grim, sardonic way
Of granting them who supplicate
The thing they wanted yesterday.”
—Roselle Mercier Montgomery (1874–1933)
“Take motherhood: nobody ever thought of putting it on a moral pedestal until some brash feminists pointed out, about a century ago, that the pay is lousy and the career ladder nonexistent.”
—Barbara Ehrenreich (b. 1941)
“The mere mechanical technique of acting can be taught, but the spirit that is to give life to lifeless forms must be born in a man. No dramatic college can teach its pupils to think or to feel. It is Nature who makes our artists for us, though it may be Art who taught them their right mode of expression.”
—Oscar Wilde (1854–1900)