From b72cba6a65e5a4de6edc8865bdb25acc00c48e8c Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 16 Nov 2022 22:33:55 +0700 Subject: Refactoring in Pqc.Crypto.Cmce --- crypto/src/pqc/crypto/cmce/CmceEngine.cs | 117 +++------------------ crypto/src/pqc/crypto/cmce/GF.cs | 172 +++++++++++++++++++++++++++---- 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 + internal class CmceEngine : 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); -- cgit 1.4.1