From d7ee2dd5ff65086171c02b2a7e7504914ff8332d Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sat, 4 Dec 2021 23:25:16 +0700 Subject: Faster const-time inversion --- crypto/src/math/raw/Mod.cs | 42 +++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-) diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs index 49ac91351..d4d1f716d 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -67,13 +67,13 @@ namespace Org.BouncyCastle.Math.Raw Encode30(bits, m, 0, M, 0); Array.Copy(M, 0, F, 0, len30); - int eta = -1; + int delta = 0; int m0Inv32 = (int)Inverse32((uint)M[0]); int maxDivsteps = GetMaximumDivsteps(bits); for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30) { - eta = Divsteps30(eta, F[0], G[0], t); + delta = Divsteps30(delta, F[0], G[0], t); UpdateDE30(len30, D, E, t, m0Inv32, M); UpdateFG30(len30, F, G, t); } @@ -298,38 +298,38 @@ namespace Org.BouncyCastle.Math.Raw } } - private static int Divsteps30(int eta, int f0, int g0, int[] t) + private static int Divsteps30(int delta, int f0, int g0, int[] t) { - int u = 1, v = 0, q = 0, r = 1; + int u = 1 << 30, v = 0, q = 0, r = 1 << 30; int f = f0, g = g0; for (int i = 0; i < 30; ++i) { Debug.Assert((f & 1) == 1); - Debug.Assert((u * f0 + v * g0) == f << i); - Debug.Assert((q * f0 + r * g0) == g << i); + Debug.Assert(((u >> (30 - i)) * f0 + (v >> (30 - i)) * g0) == f << i); + Debug.Assert(((q >> (30 - i)) * f0 + (r >> (30 - i)) * g0) == g << i); - int c1 = eta >> 31; + int c1 = delta >> 31; int c2 = -(g & 1); - int x = (f ^ c1) - c1; - int y = (u ^ c1) - c1; - int z = (v ^ c1) - c1; + int x = f ^ c1; + int y = u ^ c1; + int z = v ^ c1; - g += x & c2; - q += y & c2; - r += z & c2; + g -= x & c2; + q -= y & c2; + r -= z & c2; - c1 &= c2; - eta = (eta ^ c1) - (c1 + 1); + c2 &= ~c1; + delta = (delta ^ c2) - (c2 - 1); - f += g & c1; - u += q & c1; - v += r & c1; + f += g & c2; + u += q & c2; + v += r & c2; g >>= 1; - u <<= 1; - v <<= 1; + q >>= 1; + r >>= 1; } t[0] = u; @@ -337,7 +337,7 @@ namespace Org.BouncyCastle.Math.Raw t[2] = q; t[3] = r; - return eta; + return delta; } private static int Divsteps30Var(int eta, int f0, int g0, int[] t) -- cgit 1.4.1