Attack against modular inversion operation using side-channels? I'm building a device that performs a modular inversions using a secret modulus. I would like to know if it is possible to recover all or part of this modulus by side-channels (timing, power, EMR, etc.).
All information I found related to side-channels in modular arithmetic applies to modular exponentiation.
The algorithm used for inversion is the standard Extended Euclidean algorithm.
The attacker may be able to measure, for example, computing time. He does not have access to the output, nor to the modulus. He knows only the value that will be inverted.
Update: found a relevant reference
Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continuous fraction), there may be some leakage there.
It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting by is $p$, and that the value you want to invert is $x$:

Select a random number $r$ that is $0 &lt; r &lt; p$ and is relatively prime to $p$ (and the latter condition is trivial if $p$ is prime)

Compute $blind = r \times x \mod p$

Compute the modulus inverse $blindinv = blind^{-1} \mod p$ (using the Extended Euclidean algorithm)

Return the value $result = r \times blindinv \mod p$


It is easy to see that this computes the modulus inverse correctly, and the value given to the underlying modulus inverse function is uncorrelated to the original value $x$ (and that the additional cost of the two modular multiplications is trivial compared to the cost of the modular inverse).
Is this really required?  I don't know; however, it seems to me that the above is so cheap that even if there is a chance of weakness, this randomization looks warranted.
Now, this hides the value being inverted from the attacker, but it doesn't apply a blinding factor to $p$; however while the time taken on average (given unknown inputs) by the EE algorithm does vary somewhat based on the modulus, it is a much weaker function (and gives far less information).  Blinding $p$ would be considerably more expensive; whether you would want to do so depends on the risk of any such leakage (e.g., if it's the country's missile defense codes, you probably will be willing to pay the additional costs), as well as how much you can afford additional costs.
If you are willing to pay the additional cost, the obvious way would be to select a value $r'$ that's relatively prime to $x$ (e.g., a prime larger than $p$), and in steps two and three, compute
$blind = r \times x$
$blindinv = blind^{-1} \mod (p \times r')$
(and the rest of the algorithm stays the same; the $\bmod$ operation in the next step will discard the extra information included by the $r'$ factor)
Assuming you pick $r'$ values about the same size as $p$ (or slightly larger), you would approximately double the cost.