Refactoring in Frodo (performance)

3 files changed, 74 insertions, 32 deletions

diff --git a/crypto/src/crypto/util/Pack.cs b/crypto/src/crypto/util/Pack.cs
index 7b9ce496f..a767232b7 100644
--- a/crypto/src/crypto/util/Pack.cs
+++ b/crypto/src/crypto/util/Pack.cs
@@ -551,6 +551,14 @@ namespace Org.BouncyCastle.Crypto.Utilities
         }
 
         [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        internal static ushort LE_To_UInt16(ReadOnlySpan<byte> bs)
+        {
+            uint n =    bs[0]
+                | (uint)bs[1] << 8;
+            return (ushort)n;
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
         internal static uint LE_To_UInt32(ReadOnlySpan<byte> bs)
         {
             return      bs[0]
@@ -595,6 +603,13 @@ namespace Org.BouncyCastle.Crypto.Utilities
         }
 
         [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        internal static void UInt16_To_LE(ushort n, Span<byte> bs)
+        {
+            bs[0] = (byte)n;
+            bs[1] = (byte)(n >> 8);
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
         internal static void UInt32_To_BE(uint n, Span<byte> bs)
         {
             bs[0] = (byte)(n >> 24);
diff --git a/crypto/src/pqc/crypto/frodo/FrodoEngine.cs b/crypto/src/pqc/crypto/frodo/FrodoEngine.cs
index 7fefb4767..6aa3c8d89 100644
--- a/crypto/src/pqc/crypto/frodo/FrodoEngine.cs
+++ b/crypto/src/pqc/crypto/frodo/FrodoEngine.cs
@@ -127,24 +127,20 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             return res;
         }
 
-        private short[] MatrixMul(short[] X, int Xrow, int Xcol, short[] Y, int Yrow, int Ycol)
+        private short[] MatrixMul(short[] X, int Xrow, int Xcol, short[] Y, int Ycol)
         {
+            int qMask = q - 1;
             short[] res = new short[Xrow * Ycol];
             for (int i = 0; i < Xrow; i++)
             {
                 for (int j = 0; j < Ycol; j++)
                 {
+                    int accum = 0;
                     for (int k = 0; k < Xcol; k++)
                     {
-                        short a_test =  (short) (res[i * Ycol + j] & 0xffff);
-                        short b_test =  (short) (X[i * Xcol + k] & 0xffff);
-                        short c_test =  (short) (Y[k * Ycol + j] & 0xffff);
-                        short bc_test = (short) (((X[i * Xcol + k] & 0xffff) * (Y[k * Ycol + j] & 0xffff)) & 0xffff);
-                        short abc_test = (short) (((res[i * Ycol + j] & 0xffff) + ((X[i * Xcol + k] & 0xffff) * (Y[k * Ycol + j] & 0xffff)) & 0xffff));
-                        res[i * Ycol + j] = (short) ((res[i * Ycol + j] & 0xffff) +
-                            ((X[i * Xcol + k] & 0xffff) * (Y[k * Ycol + j] & 0xffff)) & 0xffff);
+                        accum += X[i * Xcol + k] * Y[k * Ycol + j];
                     }
-                    res[i * Ycol + j] = (short) (((res[i * Ycol + j] & 0xffff) % q) & 0xffff);
+                    res[i * Ycol + j] = (short)(accum & qMask);
                 }
             }
 
@@ -153,11 +149,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
 
         private short[] MatrixAdd(short[] X, short[] Y, int n1, int m1)
         {
+            int qMask = q - 1;
             short[] res = new short[n1 * m1];
             for (int i = 0; i < n1; i++)
-            for (int j = 0; j < m1; j++)
-                res[i * m1 + j] = (short) (((X[i * m1 + j] & 0xffff) + (Y[i * m1 + j] & 0xffff)) % q);
-
+            {
+                for (int j = 0; j < m1; j++)
+                {
+                    res[i * m1 + j] = (short)((X[i * m1 + j] + Y[i * m1 + j]) & qMask);
+                }
+            }
             return res;
         }
 
@@ -247,7 +247,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             short[] E = SampleMatrix(r, n * nbar, n, nbar);
 
             // 7. B = A * S + E
-            short[] B = MatrixAdd(MatrixMul(A, n, n, S, n, nbar), E, n, nbar);
+            short[] B = MatrixAdd(MatrixMul(A, n, n, S, nbar), E, n, nbar);
 
             // 8. b = Pack(B)
             byte[] b = FrodoPack(B);
@@ -408,7 +408,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             short[] A = gen.GenMatrix(seedA);
 
             // 8. B' = S' A + E'
-            short[] Bprime = MatrixAdd(MatrixMul(Sprime, mbar, n, A, n, n), Eprime, mbar, n);
+            short[] Bprime = MatrixAdd(MatrixMul(Sprime, mbar, n, A, n), Eprime, mbar, n);
 
             // 9. c1 = Frodo.Pack(B')
             byte[] c1 = FrodoPack(Bprime);
@@ -421,7 +421,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
 
 
             // 12. V = S' B + E''
-            short[] V = MatrixAdd(MatrixMul(Sprime, mbar, n, B, n, nbar), Eprimeprime, mbar, nbar);
+            short[] V = MatrixAdd(MatrixMul(Sprime, mbar, n, B, nbar), Eprimeprime, mbar, nbar);
 
             // 13. C = V + Frodo.Encode(mu)
             short[] EncodedMU = Encode(mu);
@@ -441,11 +441,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
 
         private short[] MatrixSub(short[] X, short[] Y, int n1, int n2)
         {
+            int qMask = q - 1;
             short[] res = new short[n1 * n2];
             for (int i = 0; i < n1; i++)
-            for (int j = 0; j < n2; j++)
-                res[i * n2 + j] = (short) ((((X[i * n2 + j]) - (Y[i * n2 + j])) & 0xffff) % q);
-
+            {
+                for (int j = 0; j < n2; j++)
+                {
+                    res[i * n2 + j] = (short)((X[i * n2 + j] - Y[i * n2 + j]) & qMask);
+                }
+            }
             return res;
         }
 
@@ -556,7 +560,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             short[] C = FrodoUnpack(c2, mbar, nbar);
 
             // 3. M = C - B' S
-            short[] BprimeS = MatrixMul(Bprime, mbar, n, S, n, nbar);
+            short[] BprimeS = MatrixMul(Bprime, mbar, n, S, nbar);
             short[] M = MatrixSub(C, BprimeS, mbar, nbar);
 
             // 4. mu' = Frodo.Decode(M)
@@ -594,7 +598,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             short[] A = gen.GenMatrix(seedA);
 
             // 11. B'' = S' A + E'
-            short[] Bprimeprime = MatrixAdd(MatrixMul(Sprime, mbar, n, A, n, n), Eprime, mbar, n);
+            short[] Bprimeprime = MatrixAdd(MatrixMul(Sprime, mbar, n, A, n), Eprime, mbar, n);
 
             // 12. E'' = Frodo.SampleMatrix(r[2*mbar*n .. 2*mbar*n + mbar*nbar-1], mbar, n)
             short[] Eprimeprime = SampleMatrix(r, 2 * mbar * n, mbar, nbar);
@@ -603,7 +607,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
             short[] B = FrodoUnpack(b, n, nbar);
 
             // 14. V = S' B + E''
-            short[] V = MatrixAdd(MatrixMul(Sprime, mbar, n, B, n, nbar), Eprimeprime, mbar, nbar);
+            short[] V = MatrixAdd(MatrixMul(Sprime, mbar, n, B, nbar), Eprimeprime, mbar, nbar);
 
             // 15. C' = V + Frodo.Encode(muprime)
             short[] Cprime = MatrixAdd(V, Encode(muprime), mbar, nbar);
diff --git a/crypto/src/pqc/crypto/frodo/FrodoMatrixGenerator.cs b/crypto/src/pqc/crypto/frodo/FrodoMatrixGenerator.cs
index 95a7de18d..ae1c2320e 100644
--- a/crypto/src/pqc/crypto/frodo/FrodoMatrixGenerator.cs
+++ b/crypto/src/pqc/crypto/frodo/FrodoMatrixGenerator.cs
@@ -35,6 +35,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
                 byte[] tmp = new byte[(16 * n) / 8];
                 byte[] b = new byte[2 + seedA.Length];
                 Array.Copy(seedA, 0, b, 2, seedA.Length);
+                uint qMask32 = ((uint)(q - 1) << 16) | (ushort)(q - 1);
 
                 IXof digest = new ShakeDigest(128);
 
@@ -46,9 +47,21 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
                     // 2. c_{i,0} || c_{i,1} || ... || c_{i,n-1} = SHAKE128(b, 16n) (length in bits) where each c_{i,j} is parsed as a 16-bit integer in little-endian byte order format
                     digest.BlockUpdate(b, 0, b.Length);
                     digest.OutputFinal(tmp, 0, tmp.Length);
-                    for (j = 0; j < n; j++)
+                    for (j = 0; j < n; j += 8)
                     {
-                        A[i * n + j] = (short) (Pack.LE_To_UInt16(tmp, 2 * j) & (q - 1));
+                        uint k01 = Pack.LE_To_UInt32(tmp, (2 * j) +  0) & qMask32;
+                        uint k23 = Pack.LE_To_UInt32(tmp, (2 * j) +  4) & qMask32;
+                        uint k45 = Pack.LE_To_UInt32(tmp, (2 * j) +  8) & qMask32;
+                        uint k67 = Pack.LE_To_UInt32(tmp, (2 * j) + 12) & qMask32;
+                        // 6. A[i][j+k] = c[k] where c is treated as a sequence of 8 16-bit integers each in little-endian byte order
+                        A[i * n + j + 0] = (short)k01;
+                        A[i * n + j + 1] = (short)(k01 >> 16);
+                        A[i * n + j + 2] = (short)k23;
+                        A[i * n + j + 3] = (short)(k23 >> 16);
+                        A[i * n + j + 4] = (short)k45;
+                        A[i * n + j + 5] = (short)(k45 >> 16);
+                        A[i * n + j + 6] = (short)k67;
+                        A[i * n + j + 7] = (short)(k67 >> 16);
                     }
                 }
                 return A;
@@ -65,11 +78,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
 
             internal override short[] GenMatrix(byte[] seedA)
             {
-                //        """Generate matrix A using AES-128 (FrodoKEM specification, Algorithm 7)"""
-                //        A = [[None for j in range(self.n)] for i in range(self.n)]
+                // """Generate matrix A using AES-128 (FrodoKEM specification, Algorithm 7)"""
+                // A = [[None for j in range(self.n)] for i in range(self.n)]
                 short[] A = new short[n * n];
                 byte[] b = new byte[16];
                 byte[] c = new byte[16];
+                uint qMask32 = ((uint)(q - 1) << 16) | (ushort)(q - 1);
 
                 IBlockCipher cipher = AesUtilities.CreateEngine();
                 cipher.Init(true, new KeyParameter(seedA));
@@ -77,24 +91,33 @@ namespace Org.BouncyCastle.Pqc.Crypto.Frodo
                 // 1. for i = 0; i < n; i += 1
                 for (int i = 0; i < n; i++)
                 {
+                    Pack.UInt16_To_LE((ushort)i, b, 0);
+
                     // 2. for j = 0; j < n; j += 8
                     for (int j = 0; j < n; j += 8)
                     {
                         // 3. b = i || j || 0 || ... || 0 in {0,1}^128, where i and j are encoded as 16-bit integers in little-endian byte order
-                        Pack.UInt16_To_LE((ushort)i, b, 0);
                         Pack.UInt16_To_LE((ushort)j, b, 2);
                         // 4. c = AES128(seedA, b)
                         cipher.ProcessBlock(b, 0, c, 0);
                         // 5. for k = 0; k < 8; k += 1
-                        for (int k = 0; k < 8; k++)
-                        {
-                            // 6. A[i][j+k] = c[k] where c is treated as a sequence of 8 16-bit integers each in little-endian byte order
-                            A[i * n + j + k] = (short)(Pack.LE_To_UInt16(c, 2 * k) & (q - 1));
-                        }
+                        uint k01 = Pack.LE_To_UInt32(c,  0) & qMask32;
+                        uint k23 = Pack.LE_To_UInt32(c,  4) & qMask32;
+                        uint k45 = Pack.LE_To_UInt32(c,  8) & qMask32;
+                        uint k67 = Pack.LE_To_UInt32(c, 12) & qMask32;
+                        // 6. A[i][j+k] = c[k] where c is treated as a sequence of 8 16-bit integers each in little-endian byte order
+                        A[i * n + j + 0] = (short)k01;
+                        A[i * n + j + 1] = (short)(k01 >> 16);
+                        A[i * n + j + 2] = (short)k23;
+                        A[i * n + j + 3] = (short)(k23 >> 16);
+                        A[i * n + j + 4] = (short)k45;
+                        A[i * n + j + 5] = (short)(k45 >> 16);
+                        A[i * n + j + 6] = (short)k67;
+                        A[i * n + j + 7] = (short)(k67 >> 16);
                     }
                 }
                 return A;
             }
         }
     }
-}
\ No newline at end of file
+}