Square-and-multiply computes modular exponentiation efficiently by scanning the exponent from its most significant bit to its least significant bit. Starting with 1, it squares the answer for every bit and multiplies by x when the bit is 1. section 10.4.2
The optimization has a security cost: the conditional multiplication creates an observable operation pattern. Timing or power traces can therefore reveal which exponent bits are 1, including sensitive RSA exponents. section 10.4.2
Table 10.1 Square-and-multiply algorithm for exponent \(42 = (101010)_2\)
| Previous answer | Bit processed | Previous answer squared | Multiplied by \(x\) | New answer |
| \(1\) | \(1\) | \(1\) | \(x\) | \(x^1 = x^{(1)_2}\) |
| \(x\) | \(0\) | \(x^2\) | - | \(x^2 = x^{(10)_2}\) |
| \(x^2\) | \(1\) | \(x^4\) | \(x^5\) | \(x^5 = x^{(101)_2}\) |
| \(x^5\) | \(0\) | \(x^{10}\) | - | \(x^{10} = x^{(1010)_2}\) |
| \(x^{10}\) | \(1\) | \(x^{20}\) | \(x^{21}\) | \(x^{21} = x^{(10101)_2}\) |
| \(x^{21}\) | \(0\) | \(x^{42}\) | - | \(x^{42} = x^{(101010)_2}\) |
Trace exponent 42 = (101010)₂ from the initial answer through each square, optional multiplication, and resulting power. section 10.4.2
