safegcd: more conservative final reduction

1 files changed, 139 insertions, 44 deletions

diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
index 41977f9d8..d9465aab6 100644
--- a/crypto/src/math/raw/Mod.cs
+++ b/crypto/src/math/raw/Mod.cs
@@ -82,15 +82,18 @@ namespace Org.BouncyCastle.Math.Raw
             Debug.Assert(-1 == signF | 0 == signF);
 
             CNegate30(len30, signF, F);
-            CNegate30(len30, signF, D);
 
-            Decode30(bits, D, 0, z, 0);
-
-            int signD = D[len30 - 1] >> 31;
+            int signD = CNegate30(len30, signF, D);
             Debug.Assert(-1 == signD | 0 == signD);
 
-            signD += (int)Nat.CAdd(len32, signD, z, m, z);
-            Debug.Assert(0 == signD & 0 != Nat.LessThan(len32, z, m));
+            // TODO 'D' should already be in [P, -P), but absent a proof we support [-2P, 2P)  
+            signD = CSub30(len30, ~signD, D, M);
+            signD = CAdd30(len30,  signD, D, M);
+            signD = CAdd30(len30,  signD, D, M);
+            Debug.Assert(0 == signD);
+
+            Decode30(bits, D, 0, z, 0);
+            Debug.Assert(0 != Nat.LessThan(len32, z, m));
 
             return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G));
         }
@@ -162,16 +165,26 @@ namespace Org.BouncyCastle.Math.Raw
             if (!IsOne(lenFG, F))
                 return false;
 
-            Decode30(bits, D, 0, z, 0);
-
             int signD = D[lenDE - 1] >> 31;
             Debug.Assert(-1 == signD | 0 == signD);
 
+            // TODO 'D' should already be in [P, -P), but absent a proof we support [-2P, 2P)  
+            if (signD < 0)
+            {
+                signD = Add30(len30, D, M);
+            }
+            else
+            {
+                signD = Sub30(len30, D, M);
+            }
             if (signD < 0)
             {
-                signD += (int)Nat.AddTo(len32, m, z);
+                signD = Add30(len30, D, M);
             }
-            Debug.Assert(0 == signD && !Nat.Gte(len32, z, m));
+            Debug.Assert(0 == signD);
+
+            Decode30(bits, D, 0, z, 0);
+            Debug.Assert(!Nat.Gte(len32, z, m));
 
             return true;
         }
@@ -200,22 +213,71 @@ namespace Org.BouncyCastle.Math.Raw
             return s;
         }
 
-        private static void CNegate30(int len, int cond, int[] D)
+        private static int Add30(int len30, int[] D, int[] M)
         {
-            Debug.Assert(len > 0);
-            Debug.Assert(D.Length >= len);
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+            Debug.Assert(M.Length >= len30);
 
-            int last = len - 1;
-            long cd = 0L;
+            int c = 0, last = len30 - 1;
+            for (int i = 0; i < last; ++i)
+            {
+                c += D[i] + M[i];
+                D[i] = c & M30; c >>= 30;
+            }
+            c += D[last] + M[last];
+            D[last] = c; c >>= 30;
+            return c;
+        }
 
+        private static int CAdd30(int len30, int cond, int[] D, int[] M)
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+            Debug.Assert(M.Length >= len30);
+
+            int c = 0, last = len30 - 1;
             for (int i = 0; i < last; ++i)
             {
-                cd += (D[i] ^ cond) - cond;
-                D[i] = (int)cd & M30; cd >>= 30;
+                c += D[i] + (M[i] & cond);
+                D[i] = c & M30; c >>= 30;
             }
+            c += D[last] + (M[last] & cond);
+            D[last] = c; c >>= 30;
+            return c;
+        }
+
+        private static int CNegate30(int len30, int cond, int[] D)
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
 
-            cd += (D[last] ^ cond) - cond;
-            D[last] = (int)cd;
+            int c = 0, last = len30 - 1;
+            for (int i = 0; i < last; ++i)
+            {
+                c += (D[i] ^ cond) - cond;
+                D[i] = c & M30; c >>= 30;
+            }
+            c += (D[last] ^ cond) - cond;
+            D[last] = c; c >>= 30;
+            return c;
+        }
+
+        private static int CSub30(int len30, int cond, int[] D, int[] M)
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+            Debug.Assert(M.Length >= len30);
+
+            int c = 0, last = len30 - 1;
+            for (int i = 0; i < last; ++i)
+            {
+                c += D[i] - (M[i] & cond);
+                D[i] = c & M30; c >>= 30;
+            }
+            c += D[last] - (M[last] & cond);
+            D[last] = c; c >>= 30;
+            return c;
         }
 
         private static void Decode30(int bits, int[] x, int xOff, uint[] z, int zOff)
@@ -424,30 +486,63 @@ namespace Org.BouncyCastle.Math.Raw
             return true;
         }
 
-        private static void Negate30(int len, int[] D)
-        {
-            Debug.Assert(len > 0);
-            Debug.Assert(D.Length >= len);
+        //private static void Negate30(int len, int[] D)
+        //{
+        //    Debug.Assert(len > 0);
+        //    Debug.Assert(D.Length >= len);
 
-            int last = len - 1;
-            long cd = 0L;
+        //    int last = len - 1;
+        //    long cd = 0L;
 
+        //    for (int i = 0; i < last; ++i)
+        //    {
+        //        cd -= D[i];
+        //        D[i] = (int)cd & M30; cd >>= 30;
+        //    }
+
+        //    cd -= D[last];
+        //    D[last] = (int)cd;
+        //}
+
+        private static int Negate30(int len30, int[] D)
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+
+            int c = 0, last = len30 - 1;
             for (int i = 0; i < last; ++i)
             {
-                cd -= D[i];
-                D[i] = (int)cd & M30; cd >>= 30;
+                c -= D[i];
+                D[i] = c & M30; c >>= 30;
             }
+            c -= D[last];
+            D[last] = c; c >>= 30;
+            return c;
+        }
 
-            cd -= D[last];
-            D[last] = (int)cd;
+        private static int Sub30(int len30, int[] D, int[] M)
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+            Debug.Assert(M.Length >= len30);
+
+            int c = 0, last = len30 - 1;
+            for (int i = 0; i < last; ++i)
+            {
+                c += D[i] - M[i];
+                D[i] = c & M30; c >>= 30;
+            }
+            c += D[last] - M[last];
+            D[last] = c; c >>= 30;
+            return c;
         }
 
-        private static void UpdateDE30(int len, int[] D, int[] E, int[] t, int m0Inv30x4, int[] M)
+        private static void UpdateDE30(int len30, int[] D, int[] E, int[] t, int m0Inv30x4, int[] M)
         {
-            Debug.Assert(len > 0);
-            Debug.Assert(D.Length >= len);
-            Debug.Assert(E.Length >= len);
-            Debug.Assert(M.Length >= len);
+            Debug.Assert(len30 > 0);
+            Debug.Assert(D.Length >= len30);
+            Debug.Assert(E.Length >= len30);
+            Debug.Assert(M.Length >= len30);
             Debug.Assert(m0Inv30x4 * M[0] == -1 << 2);
 
             int u = t[0], v = t[1], q = t[2], r = t[3];
@@ -472,7 +567,7 @@ namespace Org.BouncyCastle.Math.Raw
             cd >>= 30;
             ce >>= 30;
 
-            for (i = 1; i < len; ++i)
+            for (i = 1; i < len30; ++i)
             {
                 di = D[i];
                 ei = E[i];
@@ -487,15 +582,15 @@ namespace Org.BouncyCastle.Math.Raw
                 E[i - 1] = (int)ce & M30; ce >>= 30;
             }
 
-            D[len - 1] = (int)cd;
-            E[len - 1] = (int)ce;
+            D[len30 - 1] = (int)cd;
+            E[len30 - 1] = (int)ce;
         }
 
-        private static void UpdateFG30(int len, int[] F, int[] G, int[] t)
+        private static void UpdateFG30(int len30, int[] F, int[] G, int[] t)
         {
-            Debug.Assert(len > 0);
-            Debug.Assert(F.Length >= len);
-            Debug.Assert(G.Length >= len);
+            Debug.Assert(len30 > 0);
+            Debug.Assert(F.Length >= len30);
+            Debug.Assert(G.Length >= len30);
 
             int u = t[0], v = t[1], q = t[2], r = t[3];
             int fi, gi, i;
@@ -513,7 +608,7 @@ namespace Org.BouncyCastle.Math.Raw
             cf >>= 30;
             cg >>= 30;
 
-            for (i = 1; i < len; ++i)
+            for (i = 1; i < len30; ++i)
             {
                 fi = F[i];
                 gi = G[i];
@@ -525,8 +620,8 @@ namespace Org.BouncyCastle.Math.Raw
                 G[i - 1] = (int)cg & M30; cg >>= 30;
             }
 
-            F[len - 1] = (int)cf;
-            G[len - 1] = (int)cg;
+            F[len30 - 1] = (int)cf;
+            G[len30 - 1] = (int)cg;
         }
     }
 }