From 22ed1cc4b4c62170a9c4bc4f345dc27095cb7044 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Mon, 14 Nov 2022 15:35:39 +0700 Subject: Cmce perf. opts. --- crypto/src/pqc/crypto/cmce/CmceEngine.cs | 233 +++++++++++++++------ crypto/src/pqc/crypto/cmce/CmceKemExtractor.cs | 6 +- crypto/src/pqc/crypto/cmce/CmceKemGenerator.cs | 6 +- crypto/src/pqc/crypto/cmce/CmceKeyPairGenerator.cs | 4 +- crypto/src/pqc/crypto/cmce/CmceParameters.cs | 19 +- .../pqc/crypto/cmce/CmcePrivateKeyParameters.cs | 2 +- crypto/src/pqc/crypto/cmce/GF.cs | 209 +++++++++++------- 7 files changed, 332 insertions(+), 147 deletions(-) diff --git a/crypto/src/pqc/crypto/cmce/CmceEngine.cs b/crypto/src/pqc/crypto/cmce/CmceEngine.cs index 605770c3c..710898af8 100644 --- a/crypto/src/pqc/crypto/cmce/CmceEngine.cs +++ b/crypto/src/pqc/crypto/cmce/CmceEngine.cs @@ -3,6 +3,9 @@ using System; using System.Numerics; using System.Runtime.InteropServices; #endif +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Asn1.Nist; using Org.BouncyCastle.Crypto; @@ -11,7 +14,22 @@ using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Pqc.Crypto.Cmce { - internal class CmceEngine + internal interface ICmceEngine + { + int CipherTextSize { get; } + byte[] DecompressPrivateKey(byte[] sk); + int DefaultSessionKeySize { get; } + byte[] GeneratePublicKeyFromPrivateKey(byte[] sk); + int KemDec(byte[] key, byte[] cipher_text, byte[] sk); + int KemEnc(byte[] cipher_text, byte[] key, byte[] pk, SecureRandom random); + void KemKeypair(byte[] pk, byte[] sk, SecureRandom random); + int PrivateKeySize { get; } + int PublicKeySize { get; } + } + + internal class CmceEngine + : ICmceEngine + where TGFImpl : struct, GF { private int SYS_N; // = 3488; private int SYS_T; // = 64; @@ -32,8 +50,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce private int[] poly; // only needed for key pair gen private int defaultKeySize; - private GF gf; - private Benes benes; + private readonly TGFImpl gf; + private readonly Benes benes; private bool usePadding; private bool countErrorIndices; @@ -43,6 +61,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce public int IrrBytes => IRR_BYTES; public int CondBytes => COND_BYTES; + public int PrivateKeySize => COND_BYTES + IRR_BYTES + SYS_N / 8 + 40; public int PublicKeySize => usePadding ? PK_NROWS * ((SYS_N / 8 - ((PK_NROWS - 1) / 8))) : PK_NROWS * PK_NCOLS / 8; @@ -71,14 +90,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce SYND_BYTES = (PK_NROWS + 7) / 8; GFMASK = (1 << GFBITS) - 1; + gf = default(TGFImpl); + if (GFBITS == 12) { - gf = new GF12(); benes = new Benes12(SYS_N, SYS_T, GFBITS); } else { - gf = new GF13(); benes = new Benes13(SYS_N, SYS_T, GFBITS); } @@ -111,7 +130,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce } // generates the rest of the private key given the first 40 bytes - public byte[] decompress_private_key(byte[] sk) + public byte[] DecompressPrivateKey(byte[] sk) { byte[] reg_sk = new byte[PrivateKeySize]; Array.Copy(sk, 0, reg_sk, 0, sk.Length); @@ -190,7 +209,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return reg_sk; } - public void kem_keypair(byte[] pk, byte[] sk, SecureRandom random) + public void KemKeypair(byte[] pk, byte[] sk, SecureRandom random) { // 1. Generate a uniform random l-bit string δ. (This is called a seed.) byte[] seed_a = new byte[1]; @@ -502,7 +521,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce } // 2.4.5 Encapsulation - public int kem_enc(byte[] cipher_text, byte[] key, byte[] pk, SecureRandom random) + public int KemEnc(byte[] cipher_text, byte[] key, byte[] pk, SecureRandom random) { byte[] error_vector = new byte[SYS_N / 8]; byte mask; @@ -555,7 +574,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce } // 2.3.3 Decapsulation - public int kem_dec(byte[] key, byte[] cipher_text, byte[] sk) + public int KemDec(byte[] key, byte[] cipher_text, byte[] sk) { byte[] error_vector = new byte[SYS_N / 8]; byte[] preimage = new byte[1 + SYS_N/8 + SYND_BYTES]; @@ -767,13 +786,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce for (N = 0; N < 2 * SYS_T; N++) { - d = 0; - + uint dExt = 0U; for (i = 0; i <= Min(N, SYS_T); i++) { - d ^= gf.GFMul(C[i], s[N - i]); + dExt = gf.GFAddExt(dExt, gf.GFMulExt(C[i], s[N - i])); } + d = gf.GFReduce(dExt); + mne = d; mne -= 1; mne >>= 15; @@ -824,34 +844,46 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce /* output: out, the syndrome of length 2t */ private void Synd(ushort[] output, ushort[] f, ushort[] L, byte[] r) { - int i, j; - ushort e, e_inv, c; - - for (j = 0; j < 2 * SYS_T; j++) { - output[j] = 0; - } + ushort c = (ushort)(r[0] & 1); - for (i = 0; i < SYS_N; i++) + ushort L_i = L[0]; + ushort e = Eval(f, L_i); + ushort e_inv = gf.GFInv(gf.GFSq(e)); + ushort c_div_e = (ushort)(e_inv & (0 - c)); + + 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] = c_div_e; + } + } + for (int i = 1; i < SYS_N; i++) { - c = (ushort)((r[i / 8] >> (i % 8)) & 1); + ushort c = (ushort)((r[i / 8] >> (i % 8)) & 1); - e = Eval(f, L[i]); - e_inv = gf.GFInv(gf.GFMul(e, e)); + ushort L_i = L[i]; + ushort e = Eval(f, L_i); + ushort e_inv = gf.GFInv(gf.GFSq(e)); + ushort c_div_e = gf.GFMul(e_inv, c); - for (j = 0; j < 2 * SYS_T; j++) + output[0] = gf.GFAdd(output[0], c_div_e); + + for (int j = 1; j < 2 * SYS_T; j++) { - output[j] = gf.GFAdd(output[j], gf.GFMul(e_inv, c)); - e_inv = gf.GFMul(e_inv, L[i]); + c_div_e = gf.GFMul(c_div_e, L_i); + output[j] = gf.GFAdd(output[j], c_div_e); } } } private int MovColumns(byte[][] mat, ushort[] pi, ulong[] pivots) { - int i, j, k, s, block_idx, row, tail; - ulong[] buf = new ulong[64], - ctz_list = new ulong[32]; + int i, j, k, block_idx, row, tail; + ulong[] buf = new ulong[64]; + int[] ctz_list = new int[32]; ulong t, d, mask, one = 1; byte[] tmp = new byte[9]; // Used for padding @@ -904,9 +936,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return -1; // return if buf is not full rank } - s = Ctz(t); - ctz_list[i] = (ulong)s; - pivots[0] |= one << (int)ctz_list[i]; + int s = Ctz(t); + ctz_list[i] = s; + pivots[0] |= one << s; for (j = i + 1; j < 32; j++) { @@ -917,7 +949,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce for (j = i + 1; j < 32; j++) { mask = (buf[j] >> s) & 1; - mask = (ulong)-(long)mask;//todo replace with ~? + mask = 0UL - mask; buf[j] ^= buf[i] & mask; } } @@ -959,10 +991,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce for (j = 0; j < 32; j++) { d = t >> j; - d ^= t >> (int)ctz_list[j]; + d ^= t >> ctz_list[j]; d &= 1; - t ^= d << (int)ctz_list[j]; + t ^= d << ctz_list[j]; t ^= d << j; } if (usePadding) @@ -989,16 +1021,42 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce /* return number of trailing zeros of the non-zero input in */ private static int Ctz(ulong input) { - int i, b, m = 0, r = 0; +#if NETCOREAPP3_0_OR_GREATER + if (Bmi1.X64.IsSupported) + { + return (int)Bmi1.X64.TrailingZeroCount(input); + } +#endif - for (i = 0; i < 64; i++) + //ulong m = 1UL, r = 0, x = ~input; + //for (int i = 0; i < 64; i++) + //{ + // m &= x >> i; + // r += m; + //} + //return (int)r; + + ulong m1 = 0x0101010101010101UL, r8 = 0, x = ~input; + for (int i = 0; i < 8; ++i) { - b = (int)((input >> i) & 1); - m |= b; - r += (m ^ 1) & (b ^ 1); + m1 &= x >> i; + r8 += m1; } - return r; + ulong m8 = r8 & 0x0808080808080808UL; + m8 |= m8 >> 1; + m8 |= m8 >> 2; + + ulong r = r8; + r8 >>= 8; + r += r8 & m8; + for (int i = 2; i < 8; ++i) + { + m8 &= m8 >> 8; + r8 >>= 8; + r += r8 & m8; + } + return (int)r & 0xFF; } /* Used in mov columns*/ @@ -1629,17 +1687,28 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce } // filling matrix - m[0] = new ushort[SYS_T]; - m[0][0] = 1; - for (int i = 1; i < SYS_T; i++) { - m[0][i] = 0; - } - Array.Copy(field, 0, m[1], 0, SYS_T); + m[0] = new ushort[SYS_T]; + m[0][0] = 1; + for (int i = 1; i < SYS_T; i++) + { + m[0][i] = 0; + } + Array.Copy(field, 0, m[1], 0, SYS_T); - for (int j = 2; j <= SYS_T; j++) - { - GFMul(m[j], m[j - 1], field); + 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); + j += 2; + } + if (j == SYS_T) + { + GFSqr(m[j], m[j >> 1], temp); + } } // Irreducible 2.4.1 - 3. Compute the minimal polynomial g of β over Fq. (By definition g is monic and irre- @@ -1653,8 +1722,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce ushort mask = gf.GFIsZero(m[j][j]); for (int c = j; c < SYS_T + 1; c++) { - ushort temp = (ushort)(m[c][j] ^ m[c][k] & mask); - m[c][j] = temp; + m[c][j] = gf.GFAdd(m[c][j], (ushort)(m[c][k] & mask)); } } @@ -1663,7 +1731,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce { // System.out.println("FAILED GENERATING IRR POLY"); return -1; - } ushort inv = gf.GFInv(m[j][j]); @@ -1693,39 +1760,85 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return 0; } - private void GFMul(ushort[] output, ushort[] left, ushort[] right) + private void GFMul(ushort[] output, ushort[] left, ushort[] right, uint[] temp) { - ushort[] prod = new ushort[SYS_T * 2 - 1]; + temp[0] = gf.GFMulExt(left[0], right[0]); - for (int i = 0; i < SYS_T; i++) + 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++) { - prod[i + j] ^= (ushort)(gf.GFMul(left_i, right[j]) ^ gf.GFMul(left[j], right_i)); + 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; } - prod[i + i] ^= gf.GFMul(left_i, right_i); + 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) { - prod[i - SYS_T] ^= gf.GFMul(prod[i], 2); + t = gf.GFAddExt(t, gf.GFMulExt(gf.GFReduce(temp_i), 2)); } else { - prod[i - SYS_T + polyIndex] ^= prod[i]; + t = gf.GFAddExt(t, temp_i); } + temp[i - SYS_T + polyIndex] = t; } } - Array.Copy(prod, 0, output, 0, SYS_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 */ diff --git a/crypto/src/pqc/crypto/cmce/CmceKemExtractor.cs b/crypto/src/pqc/crypto/cmce/CmceKemExtractor.cs index 51cef8ff0..0e07946b3 100644 --- a/crypto/src/pqc/crypto/cmce/CmceKemExtractor.cs +++ b/crypto/src/pqc/crypto/cmce/CmceKemExtractor.cs @@ -5,7 +5,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce public sealed class CmceKemExtractor : IEncapsulatedSecretExtractor { - private CmceEngine engine; + private ICmceEngine engine; private CmceKeyParameters key; @@ -22,7 +22,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce if (privateParams.privateKey.Length < engine.PrivateKeySize) { key = new CmcePrivateKeyParameters(privateParams.Parameters, - engine.decompress_private_key(privateParams.privateKey)); + engine.DecompressPrivateKey(privateParams.privateKey)); } } @@ -34,7 +34,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce private byte[] ExtractSecret(byte[] encapsulation, int sessionKeySizeInBits) { byte[] session_key = new byte[sessionKeySizeInBits / 8]; - engine.kem_dec(session_key, encapsulation, ((CmcePrivateKeyParameters)key).privateKey); + engine.KemDec(session_key, encapsulation, ((CmcePrivateKeyParameters)key).privateKey); return session_key; } diff --git a/crypto/src/pqc/crypto/cmce/CmceKemGenerator.cs b/crypto/src/pqc/crypto/cmce/CmceKemGenerator.cs index 4ac145e3f..4b11f5df6 100644 --- a/crypto/src/pqc/crypto/cmce/CmceKemGenerator.cs +++ b/crypto/src/pqc/crypto/cmce/CmceKemGenerator.cs @@ -18,7 +18,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce public ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey) { CmcePublicKeyParameters key = (CmcePublicKeyParameters)recipientKey; - CmceEngine engine = key.Parameters.Engine; + ICmceEngine engine = key.Parameters.Engine; return GenerateEncapsulated(recipientKey, engine.DefaultSessionKeySize); } @@ -26,10 +26,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce private ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey, int sessionKeySizeInBits) { CmcePublicKeyParameters key = (CmcePublicKeyParameters)recipientKey; - CmceEngine engine = key.Parameters.Engine; + ICmceEngine engine = key.Parameters.Engine; byte[] cipher_text = new byte[engine.CipherTextSize]; byte[] sessionKey = new byte[sessionKeySizeInBits / 8]; // document as 32 - l/8 - Section 2.5.2 - engine.kem_enc(cipher_text, sessionKey, key.publicKey, sr); + engine.KemEnc(cipher_text, sessionKey, key.publicKey, sr); return new SecretWithEncapsulationImpl(sessionKey, cipher_text); } } diff --git a/crypto/src/pqc/crypto/cmce/CmceKeyPairGenerator.cs b/crypto/src/pqc/crypto/cmce/CmceKeyPairGenerator.cs index f2adc884c..85e2796a8 100644 --- a/crypto/src/pqc/crypto/cmce/CmceKeyPairGenerator.cs +++ b/crypto/src/pqc/crypto/cmce/CmceKeyPairGenerator.cs @@ -19,10 +19,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce private AsymmetricCipherKeyPair GenKeyPair() { - CmceEngine engine = m_cmceParams.Parameters.Engine; + ICmceEngine engine = m_cmceParams.Parameters.Engine; byte[] sk = new byte[engine.PrivateKeySize]; byte[] pk = new byte[engine.PublicKeySize]; - engine.kem_keypair(pk, sk, random); + engine.KemKeypair(pk, sk, random); CmcePublicKeyParameters pubKey = new CmcePublicKeyParameters(m_cmceParams.Parameters, pk); CmcePrivateKeyParameters privKey = new CmcePrivateKeyParameters(m_cmceParams.Parameters, sk); diff --git a/crypto/src/pqc/crypto/cmce/CmceParameters.cs b/crypto/src/pqc/crypto/cmce/CmceParameters.cs index 53932bd77..be8f54177 100644 --- a/crypto/src/pqc/crypto/cmce/CmceParameters.cs +++ b/crypto/src/pqc/crypto/cmce/CmceParameters.cs @@ -1,3 +1,5 @@ +using System; + using Org.BouncyCastle.Crypto; namespace Org.BouncyCastle.Pqc.Crypto.Cmce @@ -48,7 +50,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce //private readonly int[] poly; private readonly bool usePivots; private readonly int defaultKeySize; - private readonly CmceEngine engine; + private readonly ICmceEngine engine; private CmceParameters(string name, int m, int n, int t, int[] p, bool usePivots, int defaultKeySize) { @@ -59,7 +61,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce //this.poly = p; this.usePivots = usePivots; this.defaultKeySize = defaultKeySize; - this.engine = new CmceEngine(m, n, t, p, usePivots, defaultKeySize); + + switch (m) + { + case 12: + this.engine = new CmceEngine(m, n, t, p, usePivots, defaultKeySize); + break; + case 13: + this.engine = new CmceEngine(m, n, t, p, usePivots, defaultKeySize); + break; + default: + throw new ArgumentException(); + } } public string Name => name; @@ -76,6 +89,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce public int DefaultKeySize => defaultKeySize; - internal CmceEngine Engine => engine; + internal ICmceEngine Engine => engine; } } diff --git a/crypto/src/pqc/crypto/cmce/CmcePrivateKeyParameters.cs b/crypto/src/pqc/crypto/cmce/CmcePrivateKeyParameters.cs index a30f44469..9c4316c92 100644 --- a/crypto/src/pqc/crypto/cmce/CmcePrivateKeyParameters.cs +++ b/crypto/src/pqc/crypto/cmce/CmcePrivateKeyParameters.cs @@ -41,7 +41,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce public byte[] ReconstructPublicKey() { - CmceEngine engine = Parameters.Engine; + ICmceEngine engine = Parameters.Engine; byte[] pk = new byte[engine.PublicKeySize]; engine.GeneratePublicKeyFromPrivateKey(privateKey); return pk; diff --git a/crypto/src/pqc/crypto/cmce/GF.cs b/crypto/src/pqc/crypto/cmce/GF.cs index 02c14f971..f58206a20 100644 --- a/crypto/src/pqc/crypto/cmce/GF.cs +++ b/crypto/src/pqc/crypto/cmce/GF.cs @@ -5,49 +5,39 @@ using Org.BouncyCastle.Math.Raw; namespace Org.BouncyCastle.Pqc.Crypto.Cmce { - internal abstract class GF + internal interface GF { - internal GF() - { - } - - internal ushort GFIsZero(ushort a) - { - return (ushort)((a - 1) >> 31); - } - - internal ushort GFAdd(ushort left, ushort right) - { - return (ushort)(left ^ right); - } - - internal abstract ushort GFMul(ushort left, ushort right); - internal abstract ushort GFFrac(ushort den, ushort num); - internal abstract ushort GFInv(ushort input); + ushort GFAdd(ushort left, ushort right); + uint GFAddExt(uint left, uint right); + ushort GFFrac(ushort den, ushort num); + ushort GFInv(ushort input); + ushort GFIsZero(ushort a); + ushort GFMul(ushort left, ushort right); + uint GFMulExt(ushort left, ushort right); + ushort GFReduce(uint input); + ushort GFSq(ushort input); + uint GFSqExt(ushort input); } - internal class GF12 + internal struct GF12 : GF { - internal GF12() + public ushort GFAdd(ushort left, ushort right) { + return (ushort)(left ^ right); } - internal override ushort GFMul(ushort left, ushort right) + public uint GFAddExt(uint left, uint right) { - int x = left; - int y = right; - - int z = x * (y & 1); - for (int i = 1; i < 12; i++) - { - z ^= x * (y & (1 << i)); - } + return left ^ right; + } - return Reduce((uint)z); + public ushort GFFrac(ushort den, ushort num) + { + return GFMul(GFInv(den), num); } - internal override ushort GFInv(ushort input) + public ushort GFInv(ushort input) { ushort tmp_11; ushort tmp_1111; @@ -77,18 +67,40 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return GFSq(output); // 111111111110 } - internal override ushort GFFrac(ushort den, ushort num) + public ushort GFIsZero(ushort a) { - return GFMul(GFInv(den), num); + return (ushort)((a - 1) >> 31); } - private static ushort GFSq(ushort input) + public ushort GFMul(ushort left, ushort right) { - uint z = Interleave.Expand16to32(input); - return Reduce(z); + int x = left; + int y = right; + + int z = x * (y & 1); + for (int i = 1; i < 12; i++) + { + z ^= x * (y & (1 << i)); + } + + return GFReduce((uint)z); + } + + public uint GFMulExt(ushort left, ushort right) + { + int x = left; + int y = right; + + int z = x * (y & 1); + for (int i = 1; i < 12; i++) + { + z ^= x * (y & (1 << i)); + } + + return (uint)z; } - private static ushort Reduce(uint x) + public ushort GFReduce(uint x) { Debug.Assert((x >> 24) == 0); @@ -100,34 +112,37 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return (ushort)(u0 ^ u1 ^ u2 ^ u3 ^ u4); } + + public ushort GFSq(ushort input) + { + uint z = Interleave.Expand16to32(input); + return GFReduce(z); + } + + public uint GFSqExt(ushort input) + { + return Interleave.Expand16to32(input); + } } - internal class GF13 + internal struct GF13 : GF { private const int GFMASK = (1 << 13) - 1; - internal GF13() + public ushort GFAdd(ushort left, ushort right) { + return (ushort)(left ^ right); } - internal override ushort GFMul(ushort in0, ushort in1) + public uint GFAddExt(uint left, uint right) { - int x = in0; - int y = in1; - - int z = x * (y & 1); - for (int i = 1; i < 13; i++) - { - z ^= x * (y & (1 << i)); - } - - return Reduce((uint)z); + return left ^ right; } /* input: field element den, num */ /* return: (num/den) */ - internal override ushort GFFrac(ushort den, ushort num) + public ushort GFFrac(ushort den, ushort num) { ushort tmp_11, tmp_1111, output; @@ -141,24 +156,84 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce return GFSqMul(output, num); // ^1111111111110 = ^-1 } - internal override ushort GFInv(ushort den) + public ushort GFInv(ushort den) { return GFFrac(den, 1); } + public ushort GFIsZero(ushort a) + { + return (ushort)((a - 1) >> 31); + } + + public ushort GFMul(ushort in0, ushort in1) + { + int x = in0; + int y = in1; + + int z = x * (y & 1); + for (int i = 1; i < 13; i++) + { + z ^= x * (y & (1 << i)); + } + + return GFReduce((uint)z); + } + + public uint GFMulExt(ushort in0, ushort in1) + { + int x = in0; + int y = in1; + + int z = x * (y & 1); + for (int i = 1; i < 13; i++) + { + z ^= x * (y & (1 << i)); + } + + return (uint)z; + } + + public ushort GFReduce(uint x) + { + Debug.Assert((x >> 26) == 0); + + uint u0 = x & 0x00001FFFU; + uint u1 = x >> 13; + + uint t2 = (u1 << 4) ^ (u1 << 3) ^ (u1 << 1); + + uint u2 = t2 >> 13; + uint u3 = t2 & 0x00001FFFU; + uint u4 = (u2 << 4) ^ (u2 << 3) ^ (u2 << 1); + + return (ushort)(u0 ^ u1 ^ u2 ^ u3 ^ u4); + } + + public ushort GFSq(ushort input) + { + uint z = Interleave.Expand16to32(input); + return GFReduce(z); + } + + public uint GFSqExt(ushort input) + { + return Interleave.Expand16to32(input); + } + /* input: field element in */ /* return: (in^2)^2 */ - private static ushort GFSq2(ushort input) + private ushort GFSq2(ushort input) { uint z1 = Interleave.Expand16to32(input); - input = Reduce(z1); + input = GFReduce(z1); uint z2 = Interleave.Expand16to32(input); - return Reduce(z2); + return GFReduce(z2); } /* input: field element in, m */ /* return: (in^2)*m */ - private static ushort GFSqMul(ushort input, ushort m) + private ushort GFSqMul(ushort input, ushort m) { long t0 = input; long t1 = m; @@ -178,12 +253,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce t = x & 0x0000001FFC000000L; x ^= (t >> 18) ^ (t >> 20) ^ (t >> 24) ^ (t >> 26); - return Reduce((uint)(x & 0x03FFFFFFU)); + return GFReduce((uint)(x & 0x03FFFFFFU)); } /* input: field element in, m */ /* return: ((in^2)^2)*m */ - private static ushort GFSq2Mul(ushort input, ushort m) + private ushort GFSq2Mul(ushort input, ushort m) { long t0 = input; long t1 = m; @@ -206,23 +281,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Cmce t = x & 0x000007FFFC000000L; x ^= (t >> 18) ^ (t >> 20) ^ (t >> 24) ^ (t >> 26); - return Reduce((uint)x & 0x03FFFFFFU); - } - - private static ushort Reduce(uint x) - { - Debug.Assert((x >> 26) == 0); - - uint u0 = x & 0x00001FFFU; - uint u1 = x >> 13; - - uint t2 = (u1 << 4) ^ (u1 << 3) ^ (u1 << 1); - - uint u2 = t2 >> 13; - uint u3 = t2 & 0x00001FFFU; - uint u4 = (u2 << 4) ^ (u2 << 3) ^ (u2 << 1); - - return (ushort)(u0 ^ u1 ^ u2 ^ u3 ^ u4); + return GFReduce((uint)x & 0x03FFFFFFU); } } } -- cgit 1.4.1