RSA Timing Attack on "Extra" Montgomery Reduction In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. After implementing a toy example of this attack, I thought I understood it. I created two sets of messages, one set containing messages $m$ where $m^3$ did not require an extra reduction ($M1$) and another set where $m^3$ did require an extra reduction ($M2$). I then augmented a square-and-multiply algorithm to take advantage of Montgomery multiplication while tracking the number of extra reductions that took place over the course of the exponentiation. 

This quick experiment did appear to show that the set in which $m^3$ did not require an extra reduction ($M1$) on average would have less extra reductions than the other set. However, the difference in the two averages would be much larger than one. Most of the paper seems to suggest the timing attack they exploited relied on the timing difference a single extra reduction (e.g. section 7.1).

I believe I see an attack here, but its not the exact situation that the authors describe. It sounds like the authors are suggesting that a square-and-multiply exponentiation algorithm that relied on Montgomery multiplication would use $n$ extra reductions for messages in the set $M1$ and $n+1$ extra reductions for messages in the set $M2$ which does not make sense to me intuitively. Am I misunderstanding this attack?

Edit: After comparing my attack code with others, it turns out I understood the attack just fine and my experiment was different. The difference between my results and the results from the original paper was due to my selection of the Montgomery parameters. The value of $R$ used to put numbers in Montgomery form can have a major effect on the number of reductions required per multiplication.
Montgomery multiplication
Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T &lt; N2^k$, one has: $$T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N$$ where $U = T N' \bmod 2^k$ and $N' =  -N^{-1} \bmod 2^k$.  Further, one has: $$\begin{cases} T+UN \propto 2^k\\ 0\le \frac{T + UN}{2^k} &lt; 2N\end{cases}$$
The last 2 properties show that $R:=T2^{-k} \bmod{N}$ can be computed in two steps as:

$R \gets \frac{T+UN}{2^k}$
If $R \ge N$ then $R \gets R - N\qquad$ (extra subtraction)

Montgomery arithmetic represents an integer $0\le x &lt;N$ as $\tilde{x} = x2^k \bmod N$.  It defines the Montgomery multiplication of two representatives $\tilde{x}$ and $\tilde{y}$ as $$\tilde{x} \otimes \tilde{y} := (\tilde{x}\cdot\tilde{y})2^{-k} \bmod N\tag{*}$$  Observe that letting $z= x\cdot y \bmod N$, one has $\tilde{z} \equiv (x\cdot y)2^k \equiv (\tilde{x}\cdot \tilde{y})2^{-k} \equiv \tilde{x} \otimes \tilde{y}\pmod N$.
Timing attack
Suppose that each Montgomery multiplication, cf. Eq. ($^*$), is done using the above two-step process.  We see that depending on $\tilde{x}$ and $\tilde{y}$, there may be an extra subtraction to get the result $\tilde{z}$ in the range $[0, N)$.
To fix ideas, suppose that the computation of $S = m^d \bmod N$ is carried out with the square-and-multiply algorithm.  The attack can easily be adapted to other exponentiation algorithm. The algorithm takes as input a message $m$ and private exponent $d = (d_{\ell-1}, \dots, d_0)_2$.


$R_0 \gets \tilde{1}$; $R_1 \gets \tilde{m}$
for $i=\ell-1$ downto $0$ do
$\quad R_0 \gets R_0 \otimes R_0$
$\quad$if $d_i = 1$ then $R_0 \gets R_0 \otimes R_1$
endfor
return $\tilde{R_0}$


The goal of the attacker is to recover the value of $d$.  Observe that the square-and-multiply algorithm processes the bits of $d$ from the left to the right.

Let $d = (d_{\ell-1}, \dots, d_0)_2$
At step $j$, the attacker

 already knows bits $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$
 guesses that next bit is $d_j=1$
 chooses $T$ random messages $m_1, \dots, m_T$ and computes $$X_t = m_t^{(d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1},1)_2} \bmod N\quad\text{for $1\le t \le T$}$$
 prepares two sets $$\mathcal{S}_0 = \{m_t \mid \text{subtraction}\}\quad\text{and}\quad \mathcal{S}_0 = \{m_t \mid \text{no subtraction}\}$$
plays all messages in set $\mathcal{S}_0$ and obtains the average running time $\tau(\mathcal{S}_0)$ for an exponentiation; does the same for $\mathcal{S}_1$ and obtains $\tau(\mathcal{S}_1)$
if $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \not\approx 0$ then $d_j=1$ (the guess was correct); if  $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \approx 0$ then $d_j=0$ (the guess was incorrect)

Iterate the attack to find $d_{j-1},\dots$

In the above description, set $\mathcal{S}_0$ denotes the set of messages such that there is an extra subtraction at iteration $i=j$ in Step 4 of the square-and-multiply algorithm (i.e., Montgomery multiplication $R_0 \otimes R_1$) for the computation of $X_t$; set $\mathcal{S}_0$ denotes the set of messages such that there is no extra subtraction at iteration $i=j$ for the computation of $X_t$.
Note that the attacker can evaluate the exponentiation $X_t$ by herself as she knows $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$.  Further, since $d_j$ is assumed to be $1$, the last operation of this exponentiation $X_t$ will be a Montgomery multiplication $R_0 \otimes R_1$ (i.e., Step 4 is executed at iteration $i=j$).
Correctness
If $d_j=1$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ will be greater than the average time for an exponentiation for messages in set $\mathcal{S}_1$ because there is always an extra subtraction for $\mathcal{S}_0$.
If $d_j=0$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ or in set $\mathcal{S}_1$ will be (roughly) the same because the sorting between the two sets looks like random. Remember that the attacker made the guess $d_j = 1$.