Fix Barrett reduction input bound

In the long ago when I wrote the Barrett code I must have missed that
Barrett works for any input < 2^2k where k is the word size of the
modulus. Fixing this has several nice effects, it is faster because it
replaces a multiprecision comparison with a single size_t compare, and
now the branch does not reveal information about the input or modulus,
but only their word lengths, which is not considered sensitive.

Fixing this allows reverting the change make in a57ce5a4fd2 and now
RSA signing is even slightly faster than in 2.8, rather than 30% slower.

1 files changed, 5 insertions, 4 deletions

diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index 8f8067004..f58269d01 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -32,10 +32,11 @@ Barrett Reduction
 --------------------
 
 The Barrett reduction code is written to avoid input dependent branches. The
-Barrett algorithm only works for inputs that are most the square of the modulus;
-larger values fall back on a different (slower) division algorithm. This
-algorithm is also const time, but the branch allows detecting when a value
-larger than the square of the modulus was reduced.
+Barrett algorithm only works for inputs up to a certain size, and larger values
+fall back on a different (slower) division algorithm. This secondary algorithm
+is also const time, but the branch allows detecting when a value larger than
+2^{2k} was reduced, where k is the word length of the modulus. This leaks only
+the size of the two values, and not anything else about their value.
 
 RSA
 ----------------------