3 ms·
> It's better to use a constant time algorithm, but that's harder to do in a curve generic way and has a pretty significant performance impact (particular befor
by fuklief 2y ago
> It's better to use a constant time algorithm, but that's harder to do in a curve generic way and has a pretty significant performance impact (particular before the safegcd paper).
Crypto noob here, but isn't modular inverse the same as modular exponentiation through Fermat's little theorem? I.e., x^-1 mod n is the same as computing x^{n - 2} mod n which we know how to do in a constant-time way with a Montgomery ladder.
Or is that too slow?
- nullc 2y agoThe powering ladder is unfortunately quite slow compared to the obvious vartime algorithm which is what temps these things to have a vartime algorithim in the first place, though too slow depends on the application. It doesn't help that these chips are underpowered to begin with. Aside, for the FLT powering ladder n need needs to be prime, but it isn't when there is a cofactor, though there is a generalization that needs phi(n)... I probably shouldn't have made a comment on the issue of being curve specific since the problem is worse for sqrt().