During my internship at Cisco Meraki, I was implementing IKE (Internet Key Exchange) for our VPN and while reading up on some of the crypto involved, I found out that one of the requirements of a good multi-precision integer implementation is that it be able to do constant-time modular exponentiation to defend against side-channel attacks and timing attacks. E.g. the implementation shown on Wikipedia for Montgomery’s modular exponentiation does swaps based on a condition, which violates this constant-time requirement.

The solution to this problem is to implement constant-time conditional swap, i.e. to swap if a certain condition is true but in constant-time. For example:

is not constant-time because if `condition` is true, it will take time doing the swap but if it’s false, it will not spend that time doing the swap and hence is susceptibe to timing attacks.

So I was trying to come up with a constant-time swap and the simplest one I could think of was as follows:

## Explanation

This part makes sure that the value of condition is either 0 or 1.

If condition is 0, then make it -1 (`0b111...111`, all bits turned on). If it’s 1, make it 0 (`0b000...000`, all bits turned off).

`condition_a` is equal to `a` if `condition` was false (0). Otherwise it’s 0. Similarly `condition_b` is equal to `b` if `condition` was false (0). Otherwise it’s 0.

If `condition` was 0, then `condition_b` will be equal to `b` and hence the first xor will be equal to `a`. Similarly, if `condition` was 0, then `condition_a` will be equal to `a` and second xor will be equal to `b`. And so on …

If, however, `condition` was not 0, then the swap will happen because `condition_a` and `condition_b` will both be 0.

## AND!

Before someone starts yelling at me for implementing my own crypto - I didn’t. This was just for educational purposes. We use a well-vetted crypto library to handle all crypto.