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:
“Yet nightly pitch my moving tent,
A day’s march nearer home.”
—James Montgomery (1771–1854)
“O, when degree is shaked,
Which is the ladder of all high designs,
The enterprise is sick. How could communities,
Degrees in schools, and brotherhoods in cities,
Peaceful commerce from dividable shores,
The primogeniture and due of birth,
Prerogative of age, crowns, scepters, laurels,
But by degree stand in authentic place?
Take but degree away, untune that string,
And hark what discord follows. Each thing meets
In mere oppugnancy.”
—William Shakespeare (1564–1616)
“A successful social technique consists perhaps in finding unobjectionable means for individual self-assertion.”
—Eric Hoffer (1902–1983)