# Power analysis and exponentiation by squaring

I am trying to understand how one can retrieve the secret exponent via a simple power analysis.

Lets suppose that the exponentiation by squaring algorithm is implemented in its simplest form :

Function exp-by-squaring(x,n)
if n<0 then return exp-by-squaring(1/x, -n);
else if n=0 then return 1;
else if n=1 then return x;
else if n is even then return exp-by-squaring(x2, n/2);
else if n is odd then return x * exp-by-squaring(x2, (n-1)/2).


As i understand,if i am to probe the consumption while the machine is calculating the exponent i will be able to see the individual operations on the spectrogram. There will be a spike between different operations so i will be able to tell when it entered the "even" condition or when it entered the "odd" condition. This simply gives me an idea about the exponent and not the actual exponent.

So if the secret exponent is 2012 (https://math.stackexchange.com/questions/563708/exponentiation-by-squaring), i will simply see that the even condition was entered 6 times and the odd condition was entered 4 times but how exactly do i use that information to find the secret exponent?

• Hint: execute exp-by-squaring instrumented by printing a S each time x2 is computed (computation of either two last lines) and a M each time x *  is computed (computation of last line). See how what's printed relates to n. – fgrieu Mar 3 '15 at 9:44
• With he exponent 2012, you got: even (1006), even (503), odd (251), odd (125)... (rest is up to you). Even corresponds to a $0$, odd to a $1$. And one correction, it is actually 8 times even and 4 times odd. They did not actually evaluate your algorithm at math SE, but factored in things again, which they had split off previously. – tylo Mar 3 '15 at 14:15