Exponentiation By Squaring - Montgomery's Ladder Technique

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 x1

The 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?)

    “A funny business, a woman’s career. The things you drop on your way up the ladder so you can move faster. You forget you’ll need them again when you get back to being a woman.”
    —Joseph L. Mankiewicz (1909–1993)

    “A successful social technique consists perhaps in finding unobjectionable means for individual self-assertion.”
    —Eric Hoffer (1902–1983)