Editing Exponentiation by squaring (section)

==Montgomery's ladder technique==
Many algorithms for exponentiation do not provide defence against [[side-channel attack]]s. 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 cryptography|public-key cryptosystems]]. A technique called "[[Peter Montgomery (mathematician)|Montgomery's]] ladder"<ref name="ladder">{{cite journal |last=Montgomery |first=Peter L. |date=1987 |title=Speeding the Pollard and Elliptic Curve Methods of Factorization |journal=Math. Comput. |volume=48 |number=177 |pages=243–264 |doi=10.1090/S0025-5718-1987-0866113-7 |url=https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf |doi-access=free }}</ref> addresses this concern.

Given the [[binary expansion]] of a positive, non-zero integer ''n'' = (''n''<sub>''k''−1</sub>...''n''<sub>0</sub>)<sub>2</sub> with ''n''<sub>k−1</sub> = 1, we can compute ''x<sup>n</sup>'' as follows:
 x<sub>1</sub> = x; x<sub>2</sub> = x<sup>2</sup>
 '''for''' i = k - 2 to 0 '''do'''
     '''if''' n<sub>i</sub> = 0 '''then'''
         x<sub>2</sub> = x<sub>1</sub> * x<sub>2</sub>; x<sub>1</sub> = x<sub>1</sub><sup>2</sup>
     '''else'''
         x<sub>1</sub> = x<sub>1</sub> * x<sub>2</sub>; x<sub>2</sub> = x<sub>2</sub><sup>2</sup>
 '''return''' x<sub>1</sub>

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. A similar algorithm for multiplication by doubling exists.

This specific implementation of Montgomery's ladder is not yet protected against cache [[timing attack]]s: memory access latencies might still be observable to an attacker, as different variables are accessed depending on the value of bits of the secret exponent. Modern cryptographic implementations use a "scatter" technique to make sure the processor always misses the faster cache.<ref>{{cite journal |last1=Gueron |first1=Shay |title=Efficient software implementations of modular exponentiation |journal=Journal of Cryptographic Engineering |date=5 April 2012 |volume=2 |issue=1 |pages=31–43 |doi=10.1007/s13389-012-0031-5 |s2cid=7629541 |url=https://eprint.iacr.org/2011/239.pdf}}</ref>