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:
“Hay! now the day dawis;
The jolie Cok crawis;
Now shroudis the shawis,
Throw Natur anone.
The thissell-cok cryis
On lovers wha lyis.
Now skaillis the skyis:
The nicht is neir gone.”
—Alexander Montgomery (1540?–1610?)
“George Shears ... was hanged in a barn near the store. The rope was thrown over a beam, and he was asked to walk up a ladder to save the trouble of preparing a drop for him. “Gentlemen,” he said, “I am not used to this business. Shall I jump off or slide off?” He was told to jump.”
—For the State of Montana, U.S. public relief program (1935-1943)
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)