Adapting RSA Timing Attack for Square And Multiply from right-to-left vs left-to-right I'm trying to reconstruct the fairly well-known RSA timing attack by Kocher. I'm working with simulated timing data, so I have completely noise-free &quot;measurements&quot;. My attack is successful in guessing the exponent, as long as I use a &quot;right-to-left&quot; square and multiply method, i.e. an algorithm as follows (R=b^d mod m, with d having w bits):
R = 1
for i from 0 to w-1:
  if getbit(d, i) == 1:
    R = R * b mod m
  b = b * b mod m

The attack hinges on the conditional reduction when using Montgomery modular arithmetic, which my simulation uses. For each bit, I simulate the two paths (bit is zero/one) and group my measurements by whether an additional reduction was performed. I choose the path which shows the larger difference of means between the groups. Another criteria that works well is checking which path reduces the empirical variance of all measurements when I subtract the time taken by the square+mult vs just square.
Now I'm trying to adapt the attack to a left-to-right square and multiply:
R = 1
for i from w-1 to 0:
  R = R * R mod m
  if getbit(d, i) == 1:
    R = R * b mod m

I can't seem to find a suitable criteria to choose between the two paths when iteratively guessing the bits. When I just press on, correcting wrongly guessed bits as I go along, the attack still works on the lower bits, but is completely wrong (always guessing 1) for the higher bits in the beginning. I can't find any sources on how to adapt the attack to this kind of square and multiply algorithm.
I was finally able to adapt the attack. The solution is to use the reduction of the squaring of the following bit as a discriminator between the two groups. That is we split into two paths, i.e. (R^2 mod m)^2 mod m and (R^2*b mod m)^2 mod m. For each path we create two groups by whether the final mod has an additional reduction. Finally we check which two groups has a higher difference of means, just like the right-to-left variant. This works very nicely, except for the last bit, which we can simply solve by checking for a difference in variance as before.