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 "measurements". My attack is successful in guessing the exponent, as long as I use a "right-to-left" 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.