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.

2020-05-07

Necessary Methods

Key generation is out of the scope for now, and substantially more complicated compared to encryption and decryption. For implementing these, we only need:

• CmpGeq
• CmpZero
• ModInv (Only if we use blinding)
• ModExp
• ModMul
• ModAdd
• ModSub

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

Internal APIs often use big.Int, and could be shifted to use our internal type. The public API still needs to use big.Int though, for compatability.

This would help with some leakages actually, because using big.Int leaks zero padding information.

The concern here is the complexity of making this change.

2020-05-08

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.

We have 5215 ns/op for saturated, and 2851 ns/op for unsaturated.

Using uint

Using uint as our word type lets us call bits.Add and bits.Mul directly, which is a bit nicer. The downside is that we have less control over using a wrapper type, or using uint64.

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.

2020-05-09

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.