Refactoring in Pqc.Crypto.Cmce

2 files changed, 171 insertions, 118 deletions

diff --git a/crypto/src/pqc/crypto/cmce/CmceEngine.cs b/crypto/src/pqc/crypto/cmce/CmceEngine.cs
index 98ce3a7fa..fb7b9035c 100644
--- a/crypto/src/pqc/crypto/cmce/CmceEngine.cs
+++ b/crypto/src/pqc/crypto/cmce/CmceEngine.cs
@@ -27,9 +27,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
         int PublicKeySize { get; }
     }
 
-    internal class CmceEngine<TGFImpl>
+    internal class CmceEngine<GFImpl>
         : ICmceEngine
-        where TGFImpl : struct, GF
+        where GFImpl : struct, GF
     {
         private int SYS_N;       // = 3488;
         private int SYS_T;       // = 64;
@@ -50,7 +50,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
         private int[] poly; // only needed for key pair gen
         private int defaultKeySize;
 
-        private readonly TGFImpl gf;
+        private readonly GFImpl gf;
         private readonly Benes benes;
 
         private bool usePadding;
@@ -90,7 +90,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
             SYND_BYTES = (PK_NROWS + 7) / 8;
             GFMASK = (1 << GFBITS) - 1;
 
-            gf = default(TGFImpl);
+            gf = default(GFImpl);
 
             if (GFBITS == 12)
             {
@@ -787,7 +787,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
                 uint dExt = 0U;
                 for (int i = 0; i <= Min(N, SYS_T); i++)
                 {
-                    dExt = gf.GFAddExt(dExt, gf.GFMulExt(C[i], s[N - i]));
+                    dExt ^= gf.GFMulExt(C[i], s[N - i]);
                 }
 
                 d = gf.GFReduce(dExt);
@@ -861,12 +861,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
                 ushort e_inv = gf.GFInv(gf.GFSq(e));
                 ushort c_div_e = gf.GFMul(e_inv, c);
 
-                output[0] = gf.GFAdd(output[0], c_div_e);
+                output[0] ^= c_div_e;
 
                 for (int j = 1; j < 2 * SYS_T; j++)
                 {
                     c_div_e = gf.GFMul(c_div_e, L_i);
-                    output[j] = gf.GFAdd(output[j], c_div_e);
+                    output[j] ^= c_div_e;
                 }
             }
         }
@@ -1652,8 +1652,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
 
             for (int i = SYS_T - 1; i >= 0; i--)
             {
-                r = gf.GFMul(r, a);
-                r = gf.GFAdd(r, f[i]);
+                r  = gf.GFMul(r, a);
+                r ^= f[i];
             }
 
             return r;
@@ -1669,14 +1669,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
 
         private int GenerateIrrPoly(ushort[] field)
         {
-
             // Irreducible 2.4.1 - 2. Define β = β0 + β1y + ···+ βt−1yt−1 ∈Fq[y]/F(y).
             // generating poly
             ushort[][] m = new ushort[SYS_T + 1][];
-            for (int i = 0; i < SYS_T + 1; i++)
-            {
-                m[i] = new ushort[SYS_T];
-            }
 
             // filling matrix
             {
@@ -1687,19 +1682,23 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
                 //    m[0][i] = 0;
                 //}
 
+                m[1] = new ushort[SYS_T];
                 Array.Copy(field, 0, m[1], 0, SYS_T);
 
                 uint[] temp = new uint[SYS_T * 2 - 1];
                 int j = 2;
                 while (j < SYS_T)
                 {
-                    GFSqr(m[j], m[j >> 1], temp);
-                    GFMul(m[j + 1], m[j], field, temp);
+                    m[j] = new ushort[SYS_T];
+                    gf.GFSqrPoly(SYS_T, poly, m[j], m[j >> 1], temp);
+                    m[j + 1] = new ushort[SYS_T];
+                    gf.GFMulPoly(SYS_T, poly, m[j + 1], m[j], field, temp);
                     j += 2;
                 }
                 if (j == SYS_T)
                 {
-                    GFSqr(m[j], m[j >> 1], temp);
+                    m[j] = new ushort[SYS_T];
+                    gf.GFSqrPoly(SYS_T, poly, m[j], m[j >> 1], temp);
                 }
             }
 
@@ -1714,7 +1713,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
                     ushort mask = gf.GFIsZero(m[j][j]);
                     for (int c = j; c < SYS_T + 1; c++)
                     {
-                        m[c][j] = gf.GFAdd(m[c][j], (ushort)(m[c][k] & mask));
+                        m[c][j] ^= (ushort)(m[c][k] & mask);
                     }
                 }
 
@@ -1749,88 +1748,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
             return 0;
         }
 
-        private void GFMul(ushort[] output, ushort[] left, ushort[] right, uint[] temp)
-        {
-            temp[0] = gf.GFMulExt(left[0], right[0]);
-
-            for (int i = 1; i < SYS_T; i++)
-            {
-                temp[i + i - 1] = 0U;
-
-                ushort left_i = left[i];
-                ushort right_i = right[i];
-
-                for (int j = 0; j < i; j++)
-                {
-                    uint t = temp[i + j];
-                    t = gf.GFAddExt(t, gf.GFMulExt(left_i, right[j]));
-                    t = gf.GFAddExt(t, gf.GFMulExt(left[j], right_i));
-                    temp[i + j] = t;
-                }
-
-                temp[i + i] = gf.GFMulExt(left_i, right_i);
-            }
-
-            for (int i = (SYS_T - 1) * 2; i >= SYS_T; i--)
-            {
-                uint temp_i = temp[i];
-
-                foreach (int polyIndex in poly)
-                {
-                    uint t = temp[i - SYS_T + polyIndex];
-                    if (polyIndex == 0 && GFBITS == 12)
-                    {
-                        t = gf.GFAddExt(t, gf.GFMulExt(gf.GFReduce(temp_i), 2));
-                    }
-                    else
-                    {
-                        t = gf.GFAddExt(t, temp_i);
-                    }
-                    temp[i - SYS_T + polyIndex] = t;
-                }
-            }
-
-            for (int i = 0; i < SYS_T; ++i)
-            {
-                output[i] = gf.GFReduce(temp[i]);
-            }
-        }
-
-        private void GFSqr(ushort[] output, ushort[] input, uint[] temp)
-        {
-            temp[0] = gf.GFSqExt(input[0]);
-
-            for (int i = 1; i < SYS_T; i++)
-            {
-                temp[i + i - 1] = 0;
-                temp[i + i] = gf.GFSqExt(input[i]);
-            }
-
-            for (int i = (SYS_T - 1) * 2; i >= SYS_T; i--)
-            {
-                uint temp_i = temp[i];
-
-                foreach (int polyIndex in poly)
-                {
-                    uint t = temp[i - SYS_T + polyIndex];
-                    if (polyIndex == 0 && GFBITS == 12)
-                    {
-                        t = gf.GFAddExt(t, gf.GFMulExt(gf.GFReduce(temp_i), 2));
-                    }
-                    else
-                    {
-                        t = gf.GFAddExt(t, temp_i);
-                    }
-                    temp[i - SYS_T + polyIndex] = t;
-                }
-            }
-
-            for (int i = 0; i < SYS_T; ++i)
-            {
-                output[i] = gf.GFReduce(temp[i]);
-            }
-        }
-
         /* check if the padding bits of pk are all zero */
         int CheckPKPadding(byte[] pk)
         {
diff --git a/crypto/src/pqc/crypto/cmce/GF.cs b/crypto/src/pqc/crypto/cmce/GF.cs
index 2892278e0..8c5123107 100644
--- a/crypto/src/pqc/crypto/cmce/GF.cs
+++ b/crypto/src/pqc/crypto/cmce/GF.cs
@@ -1,4 +1,3 @@
-using System;
 using System.Diagnostics;
 
 using Org.BouncyCastle.Math.Raw;
@@ -7,8 +6,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
 {
     internal interface GF
     {
-        ushort GFAdd(ushort left, ushort right);
-        uint GFAddExt(uint left, uint right);
+        void GFMulPoly(int length, int[] poly, ushort[] output, ushort[] left, ushort[] right, uint[] temp);
+        void GFSqrPoly(int length, int[] poly, ushort[] output, ushort[] input, uint[] temp);
+
         ushort GFFrac(ushort den, ushort num);
         ushort GFInv(ushort input);
         ushort GFIsZero(ushort a);
@@ -22,14 +22,71 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
     internal struct GF12
         : GF
     {
-        public ushort GFAdd(ushort left, ushort right)
+        public void GFMulPoly(int length, int[] poly, ushort[] output, ushort[] left, ushort[] right, uint[] temp)
         {
-            return (ushort)(left ^ right);
+            temp[0] = GFMulExt(left[0], right[0]);
+
+            for (int i = 1; i < length; i++)
+            {
+                temp[i + i - 1] = 0U;
+
+                ushort left_i = left[i];
+                ushort right_i = right[i];
+
+                for (int j = 0; j < i; j++)
+                {
+                    temp[i + j] ^= GFMulExtPar(left_i, right[j], left[j], right_i);
+                }
+
+                temp[i + i] = GFMulExt(left_i, right_i);
+            }
+
+            for (int i = (length - 1) * 2; i >= length; i--)
+            {
+                uint temp_i = temp[i];
+
+                for (int j = 0; j < poly.Length - 1; j++)
+                {
+                    temp[i - length + poly[j]] ^= temp_i;
+                }
+                {
+                    temp[i - length] ^= GFMulExt(GFReduce(temp_i), 2);
+                }
+            }
+
+            for (int i = 0; i < length; ++i)
+            {
+                output[i] = GFReduce(temp[i]);
+            }
         }
 
-        public uint GFAddExt(uint left, uint right)
+        public void GFSqrPoly(int length, int[] poly, ushort[] output, ushort[] input, uint[] temp)
         {
-            return left ^ right;
+            temp[0] = GFSqExt(input[0]);
+
+            for (int i = 1; i < length; i++)
+            {
+                temp[i + i - 1] = 0;
+                temp[i + i] = GFSqExt(input[i]);
+            }
+
+            for (int i = (length - 1) * 2; i >= length; i--)
+            {
+                uint temp_i = temp[i];
+
+                for (int j = 0; j < poly.Length - 1; j++)
+                {
+                    temp[i - length + poly[j]] ^= temp_i;
+                }
+                {
+                    temp[i - length] ^= GFMulExt(GFReduce(temp_i), 2);
+                }
+            }
+
+            for (int i = 0; i < length; ++i)
+            {
+                output[i] = GFReduce(temp[i]);
+            }
         }
 
         public ushort GFFrac(ushort den, ushort num)
@@ -88,8 +145,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
 
         public uint GFMulExt(ushort left, ushort right)
         {
-            int x = left;
-            int y = right;
+            int x = left, y = right;
 
             int z = x * (y & 1);
             for (int i = 1; i < 12; i++)
@@ -100,6 +156,22 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
             return (uint)z;
         }
 
+        private uint GFMulExtPar(ushort left0, ushort right0, ushort left1, ushort right1)
+        {
+            int x0 = left0, y0 = right0, x1 = left1, y1 = right1;
+
+            int z0 = x0 * (y0 & 1);
+            int z1 = x1 * (y1 & 1);
+
+            for (int i = 1; i < 12; i++)
+            {
+                z0 ^= x0 * (y0 & (1 << i));
+                z1 ^= x1 * (y1 & (1 << i));
+            }
+
+            return (uint)(z0 ^ z1);
+        }
+
         public ushort GFReduce(uint x)
         {
             Debug.Assert((x >> 24) == 0);
@@ -128,16 +200,65 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
     internal struct GF13
         : GF
     {
-        private const int GFMASK = (1 << 13) - 1;
-
-        public ushort GFAdd(ushort left, ushort right)
+        public void GFMulPoly(int length, int[] poly, ushort[] output, ushort[] left, ushort[] right, uint[] temp)
         {
-            return (ushort)(left ^ right);
+            temp[0] = GFMulExt(left[0], right[0]);
+
+            for (int i = 1; i < length; i++)
+            {
+                temp[i + i - 1] = 0U;
+
+                ushort left_i = left[i];
+                ushort right_i = right[i];
+
+                for (int j = 0; j < i; j++)
+                {
+                    temp[i + j] ^= GFMulExtPar(left_i, right[j], left[j], right_i);
+                }
+
+                temp[i + i] = GFMulExt(left_i, right_i);
+            }
+
+            for (int i = (length - 1) * 2; i >= length; i--)
+            {
+                uint temp_i = temp[i];
+
+                for (int j = 0; j < poly.Length; j++)
+                {
+                    temp[i - length + poly[j]] ^= temp_i;
+                }
+            }
+
+            for (int i = 0; i < length; ++i)
+            {
+                output[i] = GFReduce(temp[i]);
+            }
         }
 
-        public uint GFAddExt(uint left, uint right)
+        public void GFSqrPoly(int length, int[] poly, ushort[] output, ushort[] input, uint[] temp)
         {
-            return left ^ right;
+            temp[0] = GFSqExt(input[0]);
+
+            for (int i = 1; i < length; i++)
+            {
+                temp[i + i - 1] = 0;
+                temp[i + i] = GFSqExt(input[i]);
+            }
+
+            for (int i = (length - 1) * 2; i >= length; i--)
+            {
+                uint temp_i = temp[i];
+
+                for (int j = 0; j < poly.Length; j++)
+                {
+                    temp[i - length + poly[j]] ^= temp_i;
+                }
+            }
+
+            for (int i = 0; i < length; ++i)
+            {
+                output[i] = GFReduce(temp[i]);
+            }
         }
 
         /* input: field element den, num */
@@ -180,10 +301,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
             return GFReduce((uint)z);
         }
 
-        public uint GFMulExt(ushort in0, ushort in1)
+        public uint GFMulExt(ushort left, ushort right)
         {
-            int x = in0;
-            int y = in1;
+            int x = left, y = right;
 
             int z = x * (y & 1);
             for (int i = 1; i < 13; i++)
@@ -194,6 +314,22 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce
             return (uint)z;
         }
 
+        private uint GFMulExtPar(ushort left0, ushort right0, ushort left1, ushort right1)
+        {
+            int x0 = left0, y0 = right0, x1 = left1, y1 = right1;
+
+            int z0 = x0 * (y0 & 1);
+            int z1 = x1 * (y1 & 1);
+
+            for (int i = 1; i < 13; i++)
+            {
+                z0 ^= x0 * (y0 & (1 << i));
+                z1 ^= x1 * (y1 & (1 << i));
+            }
+
+            return (uint)(z0 ^ z1);
+        }
+
         public ushort GFReduce(uint x)
         {
             Debug.Assert((x >> 26) == 0);