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

    “But ‘tis a common proof
    That lowliness is young ambition’s ladder,
    Whereto the climber-upward turns his face;
    But when he once attains the upmost round
    He then unto the ladder turns his back,
    Looks in the clouds, scorning the base degrees
    By which he did ascend.”
    —William Shakespeare (1564–1616)

    “In love as in art, good technique helps.”
    —Mason Cooley (b. 1927)