# 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 "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.

• On how many upper bits? – kelalaka Aug 24 '20 at 7:17
• Only the lower 8-10 bits start to produce a correct result, no matter how long the exponent. – Richard Aug 24 '20 at 7:29

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.