Encryption from RSA

RSA In practice

To speed up RSA encryption we can use a small e, the minimum value is 3, recommended value is 65537, or \(2^{16} + 1\). Needs 17 multiplications.

This gives us asymmetric performance, fast encryption, slow decryption (c. 2000 multiplications). RSA-CRT is a method for slightly speeding up decryption.

There are implementation attacks through side channels, even if mathematically correct:

Kocher 97 - timing attack, measuring the time for decryption can expose the exponent d.

Kocher 99 - Power attack, measuring power consumption of a smartcard while it is computing \(c^d\) can expose \(d\).

BDL 97 - Faults attack, vulnerable to error attacks, one error in decrypting can reveal d. As a result good implementations will check the output against errors before returning the result. This introduces a 10% slowdown so is often turned off, but should be enabled to defend against fault attacks.

Note that you have to make sure there is sufficient entropy in generating keys on startup, attacks can target if insufficient entropy creates common values.