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?)
“As long as she is young and personable, every woman may cherish the dream that she may leap up the social ladder and dim the sheen of luxury by sheer natural loveliness; the few examples of such a feat are kept before the eye of the public.”
—Germaine Greer (b. 1939)
“The audience is the most revered member of the theater. Without an audience there is no theater. Every technique learned by the actor, every curtain, every flat on the stage, every careful analysis by the director, every coordinated scene, is for the enjoyment of the audience. They are our guests, our evaluators, and the last spoke in the wheel which can then begin to roll. They make the performance meaningful.”
—Viola Spolin (b. 1911)