Making Go's RSA Internals Constant Time
This is essentially a lab notebook, while trying to move Go’s
crypto/rsa module away from the variable-time
math/big.Int, to an
internal constant-time number type.
Key generation is out of the scope for now, and substantially more complicated compared to encryption and decryption. For implementing these, we only need:
ModInv(Only if we use blinding)
If we implement constant-time operations, we can get rid of blinding, and this provides additional incentive, since we don’t need to implement modular inversion, and can remove the blinding logic.
Internal APIs often use
big.Int, and could be shifted to use
our internal type. The public API still needs to use
This would help with some leakages actually, because using
leaks zero padding information.
The concern here is the complexity of making this change.
Unsaturated vs Saturated limbs
Using 63 bit limbs instead of 64 seems to be noticeably (~1.8x) faster for montgomery multiplication, and thus for exponentiation.
5215 ns/op for saturated, and
2851 ns/op for unsaturated.
uint as our word type lets us call
directly, which is a bit nicer. The downside is that we have less
control over using a wrapper type, or using
Modular addition with and without scratch
BenchmarkModAdd-4 10874287 103.3 ns/op
BenchmarkModAddWithScratch-4 10834304 107.2 ns/op
I prefer without scratch anyways, so this is good news.
Without the CRT stuff, things are much slower, but general modular reduction is required to do the CRT, so implemented that will take more work.