Montgomery Powering Ladder and Side Channel Attacks: Is it practically (im-)possible to analyze where intermediate values are stored?
Each bit of the exponent decides where intermediate results are stored.


Not necessarily.

One approach is to use a primitive known as a (constant access) conditional swap.  This primitive takes the values R and S, and swaps them if the bit in the exponent is 1, and leaves them alone if they are 0.  Naturally, this is done with constant accesses (even if the bit is 0, you still read and write R and S) and constant time; it's pretty straight-forward to implement (and is considerably quicker than the Bignum operations the rest of the algorithm uses)

With this primitive, the pseudocode looks like:

CSWAP R, S
R &lt;- R*S
S &lt;- S*S
CSWAP R, S


If the exponent bit is 0, we can ignore the CSWAP's, and this is exactly the Montgomery Ladder 'bit 0' logic.

If the exponent bit is 1, then we effectively do this logic:

R' = S, S' = R   /* First CSWAP */
R' &lt;- R'*S'
S' &lt;- S'*S'
R = S', S = R'   /* Second CSWAP */


Renaming variables, this simplifies to:

S &lt;- S*R
R &lt;- R*R


Which is the 'bit 1' Montgomery logic (as * is commutative).

Hence, we've implemented both sides of the ladder with constant memory accesses.

If we write out the full ladder, we'll see that there are adjacent CSWAPs based on different bits of the exponent; it's obvious how those could be combined to further simplify things.