diff options
| author | David Hook <david.hook@keyfactor.com> | 2022-10-12 20:43:23 +1100 |
|---|---|---|
| committer | David Hook <david.hook@keyfactor.com> | 2022-10-12 20:43:23 +1100 |
| commit | 9bc545cf0fcfd4dc03b8c47031ba1bac54279d23 (patch) | |
| tree | c3dcee4169df32ba2d85b6a9f9a46298d9faacfc /crypto/src | |
| parent | added BIKE cred (diff) | |
| download | BouncyCastle.NET-ed25519-9bc545cf0fcfd4dc03b8c47031ba1bac54279d23.tar.xz | |
general cleanups - naming, imports
Diffstat (limited to 'crypto/src')
36 files changed, 4114 insertions, 82 deletions
diff --git a/crypto/src/BouncyCastle.Crypto.csproj b/crypto/src/BouncyCastle.Crypto.csproj index 493288c26..9786cd985 100644 --- a/crypto/src/BouncyCastle.Crypto.csproj +++ b/crypto/src/BouncyCastle.Crypto.csproj @@ -1,7 +1,7 @@ <Project Sdk="Microsoft.NET.Sdk"> <PropertyGroup> - <TargetFrameworks>net6.0;netstandard2.0;net40</TargetFrameworks> + <TargetFrameworks>net6.0;netstandard2.0;net462</TargetFrameworks> <RootNamespace>Org.BouncyCastle</RootNamespace> <AssemblyOriginatorKeyFile>..\..\BouncyCastle.snk</AssemblyOriginatorKeyFile> <SignAssembly>true</SignAssembly> diff --git a/crypto/src/asn1/bc/BCObjectIdentifiers.cs b/crypto/src/asn1/bc/BCObjectIdentifiers.cs index 0a2db9fd6..424d9b6f3 100644 --- a/crypto/src/asn1/bc/BCObjectIdentifiers.cs +++ b/crypto/src/asn1/bc/BCObjectIdentifiers.cs @@ -207,8 +207,8 @@ namespace Org.BouncyCastle.Asn1.BC public static readonly DerObjectIdentifier sikep751_compressed = pqc_kem_sike.Branch("8"); /** - * Kyber - */ + * Kyber + */ public static readonly DerObjectIdentifier pqc_kem_kyber = bc_kem.Branch("6"); public static readonly DerObjectIdentifier kyber512 = new DerObjectIdentifier("1.3.6.1.4.1.2.267.8.2.2"); // pqc_kem_kyber.Branch("1"); @@ -217,5 +217,14 @@ namespace Org.BouncyCastle.Asn1.BC public static readonly DerObjectIdentifier kyber512_aes = new DerObjectIdentifier("1.3.6.1.4.1.2.267.10.2.2"); // pqc_kem_kyber.Branch("4"); public static readonly DerObjectIdentifier kyber768_aes = new DerObjectIdentifier("1.3.6.1.4.1.2.267.10.3.3"); // pqc_kem_kyber.Branch("5"); public static readonly DerObjectIdentifier kyber1024_aes = new DerObjectIdentifier("1.3.6.1.4.1.2.267.10.4.4"); // pqc_kem_kyber.Branch("6"); - } + + /** + * BIKE + */ + public static readonly DerObjectIdentifier pqc_kem_bike = bc_kem.Branch("8"); + + public static readonly DerObjectIdentifier bike128 = pqc_kem_bike.Branch("1"); + public static readonly DerObjectIdentifier bike192 = pqc_kem_bike.Branch("2"); + public static readonly DerObjectIdentifier bike256 = pqc_kem_bike.Branch("3"); + } } diff --git a/crypto/src/pqc/crypto/bike/BikeEngine.cs b/crypto/src/pqc/crypto/bike/BikeEngine.cs new file mode 100644 index 000000000..7df2703c9 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeEngine.cs @@ -0,0 +1,546 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Crypto.Digests; +using Org.BouncyCastle.Pqc.Math.LinearAlgebra; +using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeEngine + { + // degree of R + private int r; + + // the row weight + private int w; + + // Hamming weight of h0, h1 + private int hw; + + // the error weight + private int t; + + //the shared secret size + private int l; + + // number of iterations in BGF decoder + private int nbIter; + + // tau + private int tau; + + private GF2mField field; + private PolynomialGF2mSmallM reductionPoly; + private int L_BYTE; + private int R_BYTE; + + public BikeEngine(int r, int w, int t, int l, int nbIter, int tau) + { + this.r = r; + this.w = w; + this.t = t; + this.l = l; + this.nbIter = nbIter; + this.tau = tau; + this.hw = this.w / 2; + this.L_BYTE = l / 8; + this.R_BYTE = (r + 7) / 8; + + // finite field GF(2) + GF2mField field = new GF2mField(1); + this.field = field; + + // generate reductionPoly (X^r + 1) + PolynomialGF2mSmallM poly = new PolynomialGF2mSmallM(field, r); + this.reductionPoly = poly.AddMonomial(0); + } + + public int GetSessionKeySize() + { + return L_BYTE; + } + + private byte[] FunctionH(byte[] seed) + { + IXof digest = new ShakeDigest(256); + digest.BlockUpdate(seed, 0, seed.Length); + byte[] wlist = BikeRandomGenerator.GenerateRandomByteArray(r * 2, 2 * R_BYTE, t, digest); + return wlist; + } + + private byte[] FunctionL(byte[] e0, byte[] e1) + { + byte[] hashRes = new byte[48]; + byte[] res = new byte[L_BYTE]; + + + Sha3Digest digest = new Sha3Digest(384); + digest.BlockUpdate(e0, 0, e0.Length); + digest.BlockUpdate(e1, 0, e1.Length); + digest.DoFinal(hashRes, 0); + + Array.Copy(hashRes, 0, res, 0, L_BYTE); + return res; + } + + private byte[] FunctionK(byte[] m, byte[] c0, byte[] c1) + { + byte[] hashRes = new byte[48]; + byte[] res = new byte[L_BYTE]; + + Sha3Digest digest = new Sha3Digest(384); + digest.BlockUpdate(m, 0, m.Length); + digest.BlockUpdate(c0, 0, c0.Length); + digest.BlockUpdate(c1, 0, c1.Length); + digest.DoFinal(hashRes, 0); + + Array.Copy(hashRes, 0, res, 0, L_BYTE); + return res; + } + + /** + Generate key pairs + - Secret key : (h0, h1, sigma) + - Public key: h + * @param h0 h0 + * @param h1 h1 + * @param sigma sigma + * @param h h + * @param random Secure Random + **/ + public void GenKeyPair(byte[] h0, byte[] h1, byte[] sigma, byte[] h, SecureRandom random) + { + // Randomly generate seeds + byte[] seeds = new byte[64]; + random.NextBytes(seeds); + + byte[] seed1 = new byte[L_BYTE]; + byte[] seed2 = new byte[L_BYTE]; + Array.Copy(seeds, 0, seed1, 0, seed1.Length); + Array.Copy(seeds, seed1.Length, seed2, 0, seed2.Length); + + IXof digest = new ShakeDigest(256); + digest.BlockUpdate(seed1, 0, seed1.Length); + + // 1. Randomly generate h0, h1 + byte[] h0Tmp = BikeRandomGenerator.GenerateRandomByteArray(r, R_BYTE, hw, digest); + byte[] h1Tmp = BikeRandomGenerator.GenerateRandomByteArray(r, R_BYTE, hw, digest); + + Array.Copy(h0Tmp, 0, h0, 0, h0.Length); + Array.Copy(h1Tmp, 0, h1, 0, h1.Length); + + byte[] h1Bits = new byte[r]; + byte[] h0Bits = new byte[r]; + + Utils.FromByteArrayToBitArray(h0Bits, h0Tmp); + Utils.FromByteArrayToBitArray(h1Bits, h1Tmp); + + // remove last 0 bits (most significant bits with 0 mean non-sense) + byte[] h0Cut = Utils.RemoveLast0Bits(h0Bits); + byte[] h1Cut = Utils.RemoveLast0Bits(h1Bits); + + // 2. Compute h + PolynomialGF2mSmallM h0Poly = new PolynomialGF2mSmallM(this.field, h0Cut); + PolynomialGF2mSmallM h1Poly = new PolynomialGF2mSmallM(this.field, h1Cut); + + PolynomialGF2mSmallM h0Inv = h0Poly.ModInverseBigDeg(reductionPoly); + PolynomialGF2mSmallM hPoly = h1Poly.ModKaratsubaMultiplyBigDeg(h0Inv, reductionPoly); + + // Get coefficients of hPoly + byte[] hTmp = hPoly.GetEncoded(); + byte[] hByte = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(hByte, hTmp); + Array.Copy(hByte, 0, h, 0, h.Length); + + //3. Parse seed2 as sigma + Array.Copy(seed2, 0, sigma, 0, sigma.Length); + } + + /** + KEM Encapsulation + - Input: h + - Output: (c0,c1,k) + * @param c0 ciphertext + * @param c1 ciphertext + * @param k session key + * @param h public key + * @param random Secure Random + **/ + public void Encaps(byte[] c0, byte[] c1, byte[] k, byte[] h, SecureRandom random) + { + byte[] seeds = new byte[64]; + random.NextBytes(seeds); + + // 1. Randomly generate m by using seed1 + byte[] m = new byte[L_BYTE]; + Array.Copy(seeds, 0, m, 0, m.Length); + + // 2. Calculate e0, e1 + byte[] eBytes = FunctionH(m); + + byte[] eBits = new byte[2 * r]; + Utils.FromByteArrayToBitArray(eBits, eBytes); + + byte[] e0Bits = Arrays.CopyOfRange(eBits, 0, r); + byte[] e1Bits = Arrays.CopyOfRange(eBits, r, eBits.Length); + + // remove last 0 bits (most significant bits with 0 mean no sense) + byte[] e0Cut = Utils.RemoveLast0Bits(e0Bits); + byte[] e1Cut = Utils.RemoveLast0Bits(e1Bits); + + PolynomialGF2mSmallM e0 = new PolynomialGF2mSmallM(field, e0Cut); + PolynomialGF2mSmallM e1 = new PolynomialGF2mSmallM(field, e1Cut); + + // 3. Calculate c + // calculate c0 + byte[] h0Bits = new byte[r]; + Utils.FromByteArrayToBitArray(h0Bits, h); + PolynomialGF2mSmallM hPoly = new PolynomialGF2mSmallM(field, Utils.RemoveLast0Bits(h0Bits)); + PolynomialGF2mSmallM c0Poly = e0.add(e1.ModKaratsubaMultiplyBigDeg(hPoly, reductionPoly)); + + byte[] c0Bits = c0Poly.GetEncoded(); + byte[] c0Bytes = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(c0Bytes, c0Bits); + Array.Copy(c0Bytes, 0, c0, 0, c0.Length); + + //calculate c1 + byte[] e0Bytes = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(e0Bytes, e0Bits); + byte[] e1Bytes = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(e1Bytes, e1Bits); + + byte[] tmp = FunctionL(e0Bytes, e1Bytes); + byte[] c1Tmp = Utils.XorBytes(m, tmp, L_BYTE); + Array.Copy(c1Tmp, 0, c1, 0, c1.Length); + + // 4. Calculate K + byte[] kTmp = FunctionK(m, c0, c1); + Array.Copy(kTmp, 0, k, 0, kTmp.Length); + } + + /** + KEM Decapsulation + - Input: (h0, h1, sigma), (c0, c1) + - Output: k + * @param h0 private key + * @param h1 private key + * @param sigma private key + * @param c0 ciphertext + * @param c1 ciphertext + * @param k session key + **/ + public void Decaps(byte[] k, byte[] h0, byte[] h1, byte[] sigma, byte[] c0, byte[] c1) + { + //convert to bits + byte[] c0Bits = new byte[this.r]; + byte[] h0Bits = new byte[this.r]; + byte[] sigmaBits = new byte[this.l]; + + Utils.FromByteArrayToBitArray(c0Bits, c0); + Utils.FromByteArrayToBitArray(h0Bits, h0); + Utils.FromByteArrayToBitArray(sigmaBits, sigma); + + byte[] c0Cut = Utils.RemoveLast0Bits(c0Bits); + byte[] h0Cut = Utils.RemoveLast0Bits(h0Bits); + + // Get compact version of h0, h1 + int[] h0Compact = new int[hw]; + int[] h1Compact = new int[hw]; + ConvertToCompact(h0Compact, h0); + ConvertToCompact(h1Compact, h1); + + // Compute syndrome + byte[] syndrome = ComputeSyndrome(c0Cut, h0Cut); + + // 1. Compute e' + byte[] ePrimeBits = BGFDecoder(syndrome, h0Compact, h1Compact); + byte[] ePrimeBytes = new byte[2 * R_BYTE]; + Utils.FromBitArrayToByteArray(ePrimeBytes, ePrimeBits); + + byte[] e0Bits = Arrays.CopyOfRange(ePrimeBits, 0, r); + byte[] e1Bits = Arrays.CopyOfRange(ePrimeBits, r, ePrimeBits.Length); + + byte[] e0Bytes = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(e0Bytes, e0Bits); + byte[] e1Bytes = new byte[R_BYTE]; + Utils.FromBitArrayToByteArray(e1Bytes, e1Bits); + + // 2. Compute m' + byte[] mPrime = Utils.XorBytes(c1, FunctionL(e0Bytes, e1Bytes), L_BYTE); + + // 3. Compute K + byte[] tmpK = new byte[l]; + byte[] wlist = FunctionH(mPrime); + if (Arrays.AreEqual(ePrimeBytes, wlist)) + { + tmpK = FunctionK(mPrime, c0, c1); + } + else + { + tmpK = FunctionK(sigma, c0, c1); + } + Array.Copy(tmpK, 0, k, 0, tmpK.Length); + } + + private byte[] ComputeSyndrome(byte[] h0, byte[] c0) + { + PolynomialGF2mSmallM coPoly = new PolynomialGF2mSmallM(field, c0); + PolynomialGF2mSmallM h0Poly = new PolynomialGF2mSmallM(field, h0); + + PolynomialGF2mSmallM s = coPoly.ModKaratsubaMultiplyBigDeg(h0Poly, reductionPoly); + byte[] transposedS = Transpose(s.GetEncoded()); + return transposedS; + } + + private byte[] BGFDecoder(byte[] s, int[] h0Compact, int[] h1Compact) + { + byte[] e = new byte[2 * r]; + + // Get compact column version + int[] h0CompactCol = GetColumnFromCompactVersion(h0Compact); + int[] h1CompactCol = GetColumnFromCompactVersion(h1Compact); + + for (int i = 1; i <= nbIter; i++) + { + byte[] black = new byte[2 * r]; + byte[] gray = new byte[2 * r]; + + int T = Threshold(Utils.GetHammingWeight(s), i, r); + + BFIter(s, e, T, h0Compact, h1Compact, h0CompactCol, h1CompactCol, black, gray); + + if (i == 1) + { + BFMaskedIter(s, e, black, (hw + 1) / 2 + 1, h0Compact, h1Compact, h0CompactCol, h1CompactCol); + BFMaskedIter(s, e, gray, (hw + 1) / 2 + 1, h0Compact, h1Compact, h0CompactCol, h1CompactCol); + } + } + if (Utils.GetHammingWeight(s) == 0) + { + return e; + } + else return null; + } + + private byte[] Transpose(byte[] input) + { + byte[] tmp = Utils.Append0s(input, r); // append zeros to s + byte[] output = new byte[r]; + output[0] = tmp[0]; + for (int i = 1; i < r; i++) + { + output[i] = tmp[r - i]; + } + return output; + } + private void BFIter(byte[] s, byte[] e, int T, int[] h0Compact, int[] h1Compact, int[] h0CompactCol, int[] h1CompactCol, byte[] black, byte[] gray) + { + int[] updatedIndices = new int[2 * r]; + + // calculate for h0compact + for (int j = 0; j < r; j++) + { + if (Ctr(h0CompactCol, s, j) >= T) + { + UpdateNewErrorIndex(e, j); + updatedIndices[j] = 1; + black[j] = 1; + } + else if (Ctr(h0CompactCol, s, j) >= T - tau) + { + gray[j] = 1; + } + } + + // calculate for h1Compact + for (int j = 0; j < r; j++) + { + if (Ctr(h1CompactCol, s, j) >= T) + { + UpdateNewErrorIndex(e, r + j); + updatedIndices[r + j] = 1; + black[r + j] = 1; + } + else if (Ctr(h1CompactCol, s, j) >= T - tau) + { + gray[r + j] = 1; + } + } + + // recompute syndrome + for (int i = 0; i < 2 * r; i++) + { + if (updatedIndices[i] == 1) + { + RecomputeSyndrome(s, i, h0Compact, h1Compact); + } + } + } + + private void BFMaskedIter(byte[] s, byte[] e, byte[] mask, int T, int[] h0Compact, int[] h1Compact, int[] h0CompactCol, int[] h1CompactCol) + { + int[] updatedIndices = new int[2 * r]; + + for (int j = 0; j < r; j++) + { + if (Ctr(h0CompactCol, s, j) >= T && mask[j] == 1) + { + UpdateNewErrorIndex(e, j); + updatedIndices[j] = 1; + } + } + + for (int j = 0; j < r; j++) + { + if (Ctr(h1CompactCol, s, j) >= T && mask[r + j] == 1) + { + UpdateNewErrorIndex(e, r + j); + updatedIndices[r + j] = 1; + } + } + + // recompute syndrome + for (int i = 0; i < 2 * r; i++) + { + if (updatedIndices[i] == 1) + { + RecomputeSyndrome(s, i, h0Compact, h1Compact); + } + } + } + + private int Threshold(int hammingWeight, int i, int r) + { + double d = 0; + int floorD = 0; + int res = 0; + switch (r) + { + case 12323: + d = 0.0069722 * hammingWeight + 13.530; + floorD = (int) System.Math.Floor(d); + res = floorD > 36 ? floorD : 36; + break; + case 24659: + d = 0.005265 * hammingWeight + 15.2588; + floorD = (int) System.Math.Floor(d); + res = floorD > 52 ? floorD : 52; + break; + case 40973: + d = 0.00402312 * hammingWeight + 17.8785; + floorD = (int) System.Math.Floor(d); + res = floorD > 69 ? floorD : 69; + break; + } + return res; + } + + private int Ctr(int[] hCompactCol, byte[] s, int j) + { + int count = 0; + for (int i = 0; i < hw; i++) + { + if (s[(hCompactCol[i] + j) % r] == 1) + { + count += 1; + } + } + return count; + } + + // Convert a polynomial in GF2 to an array of positions of which the coefficients of the polynomial are equals to 1 + private void ConvertToCompact(int[] compactVersion, byte[] h) + { + // maximum size of this array is the Hamming weight of the polynomial + int count = 0; + for (int i = 0; i < R_BYTE; i++) + { + for (int j = 0; j < 8; j++) + { + if ((i * 8 + j) == this.r) + { + break; + } + + if (((h[i] >> j) & 1) == 1) + { + compactVersion[count++] = i * 8 + j; + } + } + } + } + + private int[] GetColumnFromCompactVersion(int[] hCompact) + { + int[] hCompactColumn = new int[hw]; + if (hCompact[0] == 0) + { + hCompactColumn[0] = 0; + for (int i = 1; i < hw; i++) + { + hCompactColumn[i] = r - hCompact[hw - i]; + } + } + else + { + for (int i = 0; i < hw; i++) + { + hCompactColumn[i] = r - hCompact[hw - 1 - i]; + } + } + return hCompactColumn; + } + + private void RecomputeSyndrome(byte[] syndrome, int index, int[] h0Compact, int[] h1Compact) + { + if (index < r) + { + for (int i = 0; i < hw; i++) + { + if (h0Compact[i] <= index) + { + syndrome[index - h0Compact[i]] ^= 1; + } + else + { + syndrome[r + index - h0Compact[i]] ^= 1; + } + } + } + else + { + for (int i = 0; i < hw; i++) + { + if (h1Compact[i] <= (index - r)) + { + syndrome[(index - r) - h1Compact[i]] ^= 1; + } + else + { + syndrome[r - h1Compact[i] + (index - r)] ^= 1; + } + } + } + } + + private void UpdateNewErrorIndex(byte[] e, int index) + { + int newIndex = index; + if (index != 0 && index != r) + { + if (index > r) + { + newIndex = 2 * r - index + r; + } + else + { + newIndex = r - index; + } + } + e[newIndex] ^= 1; + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeKemExtractor.cs b/crypto/src/pqc/crypto/bike/BikeKemExtractor.cs new file mode 100644 index 000000000..bcc0c124c --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeKemExtractor.cs @@ -0,0 +1,48 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeKemExtractor : IEncapsulatedSecretExtractor + { + private BikeEngine engine; + + private BikeKeyParameters key; + private int defaultKeySize; + + public BikeKemExtractor(BikePrivateKeyParameters privParams) + { + this.key = privParams; + initCipher(key.Parameters); + } + + private void initCipher(BikeParameters param) + { + engine = param.BIKEEngine; + defaultKeySize = param.DefaultKeySize; + } + + public byte[] ExtractSecret(byte[] encapsulation) + { + byte[] session_key = new byte[engine.GetSessionKeySize()]; + BikePrivateKeyParameters secretKey = (BikePrivateKeyParameters)key; + + // Extract c0, c1 from encapsulation c + byte[] c0 = Arrays.CopyOfRange(encapsulation, 0, secretKey.Parameters.RByte); + byte[] c1 = Arrays.CopyOfRange(encapsulation, secretKey.Parameters.RByte, encapsulation.Length); + + byte[] h0 = secretKey.GetH0(); + byte[] h1 = secretKey.GetH1(); + byte[] sigma = secretKey.GetSigma(); + + engine.Decaps(session_key, h0, h1, sigma, c0, c1); + return Arrays.CopyOfRange(session_key, 0, defaultKeySize / 8); + } + + public int EncapsulationLength => key.Parameters.RByte + key.Parameters.LByte; + + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs b/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs new file mode 100644 index 000000000..461cdae97 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs @@ -0,0 +1,85 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeKemGenerator : IEncapsulatedSecretGenerator + { + private SecureRandom sr; + public BikeKemGenerator(SecureRandom random) + { + this.sr = random; + } + + public ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey) + { + BikePublicKeyParameters key = (BikePublicKeyParameters)recipientKey; + BikeEngine engine = key.Parameters.BIKEEngine; + + byte[] K = new byte[key.Parameters.LByte]; + byte[] c0 = new byte[key.Parameters.RByte]; + byte[] c1 = new byte[key.Parameters.LByte]; + byte[] h = key.PublicKey; + + engine.Encaps(c0, c1, K, h, sr); + + byte[] cipherText = Arrays.Concatenate(c0, c1); + + return new SecretWithEncapsulationImpl(Arrays.CopyOfRange(K, 0, key.Parameters.DefaultKeySize / 8), cipherText); + } + + private class SecretWithEncapsulationImpl : ISecretWithEncapsulation + { + private volatile bool hasBeenDestroyed = false; + + private byte[] sessionKey; + private byte[] cipher_text; + + public SecretWithEncapsulationImpl(byte[] sessionKey, byte[] cipher_text) + { + this.sessionKey = sessionKey; + this.cipher_text = cipher_text; + } + + public byte[] GetSecret() + { + CheckDestroyed(); + return Arrays.Clone(sessionKey); + } + + public byte[] GetEncapsulation() + { + CheckDestroyed(); + + return Arrays.Clone(cipher_text); + } + + public void Dispose() + { + if (!hasBeenDestroyed) + { + hasBeenDestroyed = true; + Arrays.Clear(sessionKey); + Arrays.Clear(cipher_text); + } + } + + public bool IsDestroyed() + { + return hasBeenDestroyed; + } + + void CheckDestroyed() + { + if (IsDestroyed()) + { + throw new Exception("data has been destroyed"); + } + } + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeKeyGenerationParameters.cs b/crypto/src/pqc/crypto/bike/BikeKeyGenerationParameters.cs new file mode 100644 index 000000000..226d939fc --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeKeyGenerationParameters.cs @@ -0,0 +1,22 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeKeyGenerationParameters : KeyGenerationParameters + { + private BikeParameters param; + + public BikeKeyGenerationParameters( + SecureRandom random, + BikeParameters param) : base(random, 256) + { + this.param = param; + } + + public BikeParameters Parameters => param; + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeKeyPairGenerator.cs b/crypto/src/pqc/crypto/bike/BikeKeyPairGenerator.cs new file mode 100644 index 000000000..f1b786336 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeKeyPairGenerator.cs @@ -0,0 +1,76 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeKeyPairGenerator : IAsymmetricCipherKeyPairGenerator + { + private SecureRandom random; + + // block length + private int r; + + // the row weight + private int w; + + // Hamming weight of h0, h1 + private int hw; + + // the error weight + private int t; + + //the shared secret size + private int l; + + // number of iterations in BGF decoder + private int nbIter; + + // tau + private int tau; + private int L_BYTE; + private int R_BYTE; + + private BikeKeyGenerationParameters bikeKeyGenerationParameters; + public void Init(KeyGenerationParameters param) + { + this.bikeKeyGenerationParameters = (BikeKeyGenerationParameters)param; + this.random = param.Random; + + // get parameters + this.r = this.bikeKeyGenerationParameters.Parameters.R; + this.w = this.bikeKeyGenerationParameters.Parameters.W; + this.l = this.bikeKeyGenerationParameters.Parameters.L; + this.t = this.bikeKeyGenerationParameters.Parameters.T; + this.nbIter = this.bikeKeyGenerationParameters.Parameters.NbIter; + this.tau = this.bikeKeyGenerationParameters.Parameters.Tau; + this.hw = w / 2; + this.L_BYTE = l / 8; + this.R_BYTE = (r + 7) / 8; + } + + private AsymmetricCipherKeyPair GenKeyPair() + { + BikeEngine engine = bikeKeyGenerationParameters.Parameters.BIKEEngine; + byte[] h0 = new byte[R_BYTE]; + byte[] h1 = new byte[R_BYTE]; + byte[] h = new byte[R_BYTE]; + byte[] sigma = new byte[L_BYTE]; + + engine.GenKeyPair(h0, h1, sigma, h, random); + + // form keys + BikePublicKeyParameters publicKey = new BikePublicKeyParameters(bikeKeyGenerationParameters.Parameters, h); + BikePrivateKeyParameters privateKey = new BikePrivateKeyParameters(bikeKeyGenerationParameters.Parameters, h0, h1, sigma); + + return new AsymmetricCipherKeyPair(publicKey, privateKey); + } + + public AsymmetricCipherKeyPair GenerateKeyPair() + { + return GenKeyPair(); + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeKeyParameters.cs b/crypto/src/pqc/crypto/bike/BikeKeyParameters.cs new file mode 100644 index 000000000..0ee8279a9 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeKeyParameters.cs @@ -0,0 +1,21 @@ +using Org.BouncyCastle.Crypto; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeKeyParameters : AsymmetricKeyParameter + { + private BikeParameters param; + + public BikeKeyParameters( + bool isPrivate, + BikeParameters param) : base(isPrivate) + { + this.param = param; + } + + public BikeParameters Parameters => param; + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeParameters.cs b/crypto/src/pqc/crypto/bike/BikeParameters.cs new file mode 100644 index 000000000..e5695c48f --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeParameters.cs @@ -0,0 +1,67 @@ +using Org.BouncyCastle.Crypto; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikeParameters : ICipherParameters + { + // 128 bits security + public static BikeParameters bike128 = new BikeParameters("bike128", 12323, 142, 134, 256, 5, 3, 128); + + // 192 bits security + public static BikeParameters bike192 = new BikeParameters("bike192",24659, 206, 199, 256, 5, 3, 192); + + // 256 bits security + public static BikeParameters bike256 = new BikeParameters("bike256",40973, 274, 264, 256, 5, 3, 256); + + private String name; + private int r; + private int w; + private int t; + private int l; + private int nbIter; + private int tau; + private int defaultKeySize; + + private BikeEngine bikeEngine; + internal BikeParameters(String name, int r, int w, int t, int l, int nbIter, int tau, int defaultKeySize) + { + this.name = name; + this.r = r; + this.w = w; + this.t = t; + this.l = l; + this.nbIter = nbIter; + this.tau = tau; + this.defaultKeySize = defaultKeySize; + this.bikeEngine = new BikeEngine(r, w, t, l, nbIter, tau); + } + + internal BikeParameters(BikeParameters param) + { + this.name = param.name; + this.r = param.r; + this.w = param.w; + this.t = param.t; + this.l = param.l; + this.nbIter = param.nbIter; + this.tau = param.tau; + this.defaultKeySize = param.defaultKeySize; + this.bikeEngine = new BikeEngine(r, w, t, l, nbIter, tau); + } + + public int R => r; + public int RByte => (r + 7) / 8; + public int LByte => l / 8; + public int W => w; + public int T => t; + public int L => l; + public int NbIter => nbIter; + public int Tau => tau; + public String Name => name; + public int DefaultKeySize => defaultKeySize; + internal BikeEngine BIKEEngine => bikeEngine; + } +} diff --git a/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs b/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs new file mode 100644 index 000000000..d8c6e4613 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs @@ -0,0 +1,55 @@ +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikePrivateKeyParameters : BikeKeyParameters + { + // h0 + private byte[] h0; + + // h1 + private byte[] h1; + + // sigma + private byte[] sigma; + + /** + * Constructor. + * + * @param h0 h0 + * @param h1 h1 + * @param sigma random bytes sigma + */ + public BikePrivateKeyParameters(BikeParameters bikeParameters, byte[] h0, byte[] h1, byte[] sigma) : base(true, bikeParameters) + { + this.h0 = Arrays.Clone(h0); + this.h1 = Arrays.Clone(h1); + this.sigma = Arrays.Clone(sigma); + } + + public byte[] GetH0() + { + return h0; + } + + public byte[] GetH1() + { + return h1; + } + + public byte[] GetSigma() + { + return sigma; + } + + public byte[] PrivateKey => Arrays.Concatenate(Arrays.Concatenate(h0, h1), sigma); + + public byte[] GetEncoded() + { + return PrivateKey; + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikePublicKeyParameters.cs b/crypto/src/pqc/crypto/bike/BikePublicKeyParameters.cs new file mode 100644 index 000000000..16370c3cf --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikePublicKeyParameters.cs @@ -0,0 +1,28 @@ +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + public class BikePublicKeyParameters : BikeKeyParameters + { + byte[] publicKey; + + /** + * Constructor. + * + * @param publicKey byte + */ + public BikePublicKeyParameters(BikeParameters param, byte[] publicKey) : base(false, param) + { + this.publicKey = Arrays.Clone(publicKey); + } + + public byte[] PublicKey => Arrays.Clone(publicKey); + public byte[] GetEncoded() + { + return PublicKey; + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs b/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs new file mode 100644 index 000000000..4eea5774a --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs @@ -0,0 +1,91 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Crypto.Utilities; +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + class BikeRandomGenerator + { + private static int BitScanReverse(int t) + { + int res = 0; + while (t != 0) + { + t >>= 1; + res++; + } + + return res; + } + + private static int GetRandomInMod(int mod, IXof digest) + { + int mask = MaskNumber(BitScanReverse(mod)); + int res = -1; + while (true) + { + res = GetRandomNumber(digest); + res &= mask; + + if (res < mod) + { + break; + } + } + return res; + } + + private static void GenerateRandomArray(byte[] res, int mod, int weight, IXof digest) + { + int index = 0; + while (index < weight) + { + int tmp = GetRandomInMod(mod, digest); + + if (CheckBit(res, tmp) == 0) + { // check for new index + SetBit(res, tmp); + index++; + } + } + } + + private static int CheckBit(byte[] a, int position) + { + int index = position / 8; + int pos = position % 8; + return ((a[index] >> (pos)) & 0x01); + } + + + + private static void SetBit(byte[] a, int position) + { + int index = position / 8; + int pos = position % 8; + a[index] |= (byte) (1 << (pos)); + } + + public static byte[] GenerateRandomByteArray(int mod, int size, int weight, IXof digest) + { + byte[] res = new byte[size]; + GenerateRandomArray(res, mod, weight, digest); + return res; + } + + private static int MaskNumber(int n) + { + return ((1 << n) - 1); + } + + private static int GetRandomNumber(IXof digest) + { + byte[] output = new byte[4]; + digest.Output(output, 0, output.Length); + int tmp = Pack.LE_To_UInt16(output, 0); + return tmp; + } + } +} diff --git a/crypto/src/pqc/crypto/bike/Utils.cs b/crypto/src/pqc/crypto/bike/Utils.cs new file mode 100644 index 000000000..8a1a05e37 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/Utils.cs @@ -0,0 +1,119 @@ +using System; +using System.Collections.Generic; +using System.Text; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + class Utils + { + internal static byte[] XorBytes(byte[] a, byte[] b, int size) + { + byte[] output = new byte[size]; + + for (int i = 0; i < size; i++) + { + output[i] = (byte)(a[i] ^ b[i]); + } + return output; + } + + internal static int GetHammingWeight(byte[] bytes) + { + int hammingWeight = 0; + for (int i = 0; i < bytes.Length; i++) + { + hammingWeight += bytes[i]; + } + return hammingWeight; + } + + internal static void FromByteArrayToBitArray(byte[] output, byte[] input) + { + int max = (output.Length / 8); + for (int i = 0; i < max; i++) + { + for (int j = 0; j != 8; j++) + { + output[i * 8 + j] = (byte)UnsignedRightBitShiftInt(input[i] & (1 << j), j); + } + } + if (output.Length % 8 != 0) + { + int off = max * 8; + int count = 0; + while (off < output.Length) + { + output[off++] = (byte)(UnsignedRightBitShiftInt(input[max] & (1 << count), count)); + count++; + } + } + } + + internal static void FromBitArrayToByteArray(byte[] output, byte[] input) + { + int count = 0; + int pos = 0; + long len = input.Length; + while (count < len) + { + if (count + 8 >= input.Length) + {// last set of bits cannot have enough 8 bits + int b = input[count]; + for (int j = input.Length - count - 1; j >= 1; j--) + { //bin in reversed order + b |= input[count + j] << j; + } + output[pos] = (byte)b; + } + else + { + int b = input[count]; + for (int j = 7; j >= 1; j--) + { //bin in reversed order + b |= input[count + j] << j; + } + output[pos] = (byte)b; + } + + count += 8; + pos++; + } + } + + internal static byte[] RemoveLast0Bits(byte[] output) + { + int lastIndexOf1 = 0; + for (int i = output.Length - 1; i >= 0; i--) + { + if (output[i] == 1) + { + lastIndexOf1 = i; + break; + } + } + byte[] res = new byte[lastIndexOf1 + 1]; + Array.Copy(output, 0, res, 0, res.Length); + return res; + } + + internal static byte[] Append0s(byte[] input, int length) + { + byte[] output = new byte[length]; + Array.Copy(input, 0, output, 0, input.Length); + return output; + } + internal static int UnsignedRightBitShiftInt(int a, int b) + { + uint tmp = (uint)a; + tmp >>= b; + return (int)tmp; + } + + internal static long UnsignedRightBitShiftLong(long a, int b) + { + ulong tmp = (ulong)a; + tmp >>= b; + return (long)tmp; + } + } +} diff --git a/crypto/src/pqc/crypto/saber/SABERKEMExtractor.cs b/crypto/src/pqc/crypto/saber/SABERKEMExtractor.cs index 83d6f9d65..7199b9dab 100644 --- a/crypto/src/pqc/crypto/saber/SABERKEMExtractor.cs +++ b/crypto/src/pqc/crypto/saber/SABERKEMExtractor.cs @@ -3,20 +3,20 @@ using Org.BouncyCastle.Crypto; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERKEMExtractor + public class SaberKemExtractor : IEncapsulatedSecretExtractor { private SABEREngine engine; - private SABERKeyParameters key; + private SaberKeyParameters key; - public SABERKEMExtractor(SABERKeyParameters privParams) + public SaberKemExtractor(SaberKeyParameters privParams) { this.key = privParams; InitCipher(key.GetParameters()); } - private void InitCipher(SABERParameters param) + private void InitCipher(SaberParameters param) { engine = param.GetEngine(); } @@ -24,7 +24,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Saber public byte[] ExtractSecret(byte[] encapsulation) { byte[] session_key = new byte[engine.GetSessionKeySize()]; - engine.crypto_kem_dec(session_key, encapsulation, ((SABERPrivateKeyParameters) key).GetPrivateKey()); + engine.crypto_kem_dec(session_key, encapsulation, ((SaberPrivateKeyParameters) key).GetPrivateKey()); return session_key; } diff --git a/crypto/src/pqc/crypto/saber/SABERKEMGenerator.cs b/crypto/src/pqc/crypto/saber/SABERKEMGenerator.cs index 4baf1d0c6..0919b4dea 100644 --- a/crypto/src/pqc/crypto/saber/SABERKEMGenerator.cs +++ b/crypto/src/pqc/crypto/saber/SABERKEMGenerator.cs @@ -7,20 +7,20 @@ using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERKEMGenerator + public class SaberKemGenerator : IEncapsulatedSecretGenerator { // the source of randomness private SecureRandom sr; - public SABERKEMGenerator(SecureRandom random) + public SaberKemGenerator(SecureRandom random) { this.sr = random; } public ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey) { - SABERPublicKeyParameters key = (SABERPublicKeyParameters) recipientKey; + SaberPublicKeyParameters key = (SaberPublicKeyParameters) recipientKey; SABEREngine engine = key.GetParameters().GetEngine(); byte[] cipher_text = new byte[engine.GetCipherTextSize()]; byte[] sessionKey = new byte[engine.GetSessionKeySize()]; diff --git a/crypto/src/pqc/crypto/saber/SABERKeyGenerationParameters.cs b/crypto/src/pqc/crypto/saber/SABERKeyGenerationParameters.cs index 48851076d..038c191ef 100644 --- a/crypto/src/pqc/crypto/saber/SABERKeyGenerationParameters.cs +++ b/crypto/src/pqc/crypto/saber/SABERKeyGenerationParameters.cs @@ -4,22 +4,19 @@ using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERKeyGenerationParameters + public class SaberKeyGenerationParameters : KeyGenerationParameters { - private SABERParameters parameters; + private SaberParameters parameters; - public SABERKeyGenerationParameters( + public SaberKeyGenerationParameters( SecureRandom random, - SABERParameters saberParameters) + SaberParameters saberParameters) : base(random, 256) { this.parameters = saberParameters; } - public SABERParameters GetParameters() - { - return parameters; - } + public SaberParameters Parameters => parameters; } } \ No newline at end of file diff --git a/crypto/src/pqc/crypto/saber/SABERKeyPairGenerator.cs b/crypto/src/pqc/crypto/saber/SABERKeyPairGenerator.cs index 79b59ee1d..73209b18b 100644 --- a/crypto/src/pqc/crypto/saber/SABERKeyPairGenerator.cs +++ b/crypto/src/pqc/crypto/saber/SABERKeyPairGenerator.cs @@ -4,10 +4,10 @@ using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERKeyPairGenerator + public class SaberKeyPairGenerator : IAsymmetricCipherKeyPairGenerator { - private SABERKeyGenerationParameters saberParams; + private SaberKeyGenerationParameters saberParams; private int l; @@ -16,21 +16,21 @@ namespace Org.BouncyCastle.Pqc.Crypto.Saber private void Initialize( KeyGenerationParameters param) { - this.saberParams = (SABERKeyGenerationParameters) param; + this.saberParams = (SaberKeyGenerationParameters) param; this.random = param.Random; - this.l = this.saberParams.GetParameters().L; + this.l = this.saberParams.Parameters.L; } private AsymmetricCipherKeyPair GenKeyPair() { - SABEREngine engine = saberParams.GetParameters().GetEngine(); + SABEREngine engine = saberParams.Parameters.GetEngine(); byte[] sk = new byte[engine.GetPrivateKeySize()]; byte[] pk = new byte[engine.GetPublicKeySize()]; engine.crypto_kem_keypair(pk, sk, random); - SABERPublicKeyParameters pubKey = new SABERPublicKeyParameters(saberParams.GetParameters(), pk); - SABERPrivateKeyParameters privKey = new SABERPrivateKeyParameters(saberParams.GetParameters(), sk); + SaberPublicKeyParameters pubKey = new SaberPublicKeyParameters(saberParams.Parameters, pk); + SaberPrivateKeyParameters privKey = new SaberPrivateKeyParameters(saberParams.Parameters, sk); return new AsymmetricCipherKeyPair(pubKey, privKey); } diff --git a/crypto/src/pqc/crypto/saber/SABERKeyParameters.cs b/crypto/src/pqc/crypto/saber/SABERKeyParameters.cs index f44e21e00..e5a9e767e 100644 --- a/crypto/src/pqc/crypto/saber/SABERKeyParameters.cs +++ b/crypto/src/pqc/crypto/saber/SABERKeyParameters.cs @@ -3,20 +3,20 @@ using Org.BouncyCastle.Crypto; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERKeyParameters + public class SaberKeyParameters : AsymmetricKeyParameter { - private SABERParameters parameters; + private SaberParameters parameters; - public SABERKeyParameters( + public SaberKeyParameters( bool isPrivate, - SABERParameters parameters) + SaberParameters parameters) : base(isPrivate) { this.parameters = parameters; } - public SABERParameters GetParameters() + public SaberParameters GetParameters() { return parameters; } diff --git a/crypto/src/pqc/crypto/saber/SABERParameters.cs b/crypto/src/pqc/crypto/saber/SABERParameters.cs index f558e29bd..357430d50 100644 --- a/crypto/src/pqc/crypto/saber/SABERParameters.cs +++ b/crypto/src/pqc/crypto/saber/SABERParameters.cs @@ -4,27 +4,27 @@ using Org.BouncyCastle.Crypto; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public sealed class SABERParameters + public sealed class SaberParameters : ICipherParameters { - public static SABERParameters lightsaberkem128r3 = new SABERParameters("lightsaberkem128r3", 2, 128); - public static SABERParameters saberkem128r3 = new SABERParameters("saberkem128r3", 3, 128); - public static SABERParameters firesaberkem128r3 = new SABERParameters("firesaberkem128r3", 4, 128); + public static SaberParameters lightsaberkem128r3 = new SaberParameters("lightsaberkem128r3", 2, 128); + public static SaberParameters saberkem128r3 = new SaberParameters("saberkem128r3", 3, 128); + public static SaberParameters firesaberkem128r3 = new SaberParameters("firesaberkem128r3", 4, 128); - public static SABERParameters lightsaberkem192r3 = new SABERParameters("lightsaberkem192r3", 2, 192); - public static SABERParameters saberkem192r3 = new SABERParameters("saberkem192r3", 3, 192); - public static SABERParameters firesaberkem192r3 = new SABERParameters("firesaberkem192r3", 4, 192); + public static SaberParameters lightsaberkem192r3 = new SaberParameters("lightsaberkem192r3", 2, 192); + public static SaberParameters saberkem192r3 = new SaberParameters("saberkem192r3", 3, 192); + public static SaberParameters firesaberkem192r3 = new SaberParameters("firesaberkem192r3", 4, 192); - public static SABERParameters lightsaberkem256r3 = new SABERParameters("lightsaberkem256r3", 2, 256); - public static SABERParameters saberkem256r3 = new SABERParameters("saberkem256r3", 3, 256); - public static SABERParameters firesaberkem256r3 = new SABERParameters("firesaberkem256r3", 4, 256); + public static SaberParameters lightsaberkem256r3 = new SaberParameters("lightsaberkem256r3", 2, 256); + public static SaberParameters saberkem256r3 = new SaberParameters("saberkem256r3", 3, 256); + public static SaberParameters firesaberkem256r3 = new SaberParameters("firesaberkem256r3", 4, 256); private string name; private int l; private int defaultKeySize; private SABEREngine engine; - public SABERParameters(string name, int l, int defaultKeySize) + public SaberParameters(string name, int l, int defaultKeySize) { this.name = name; this.l = l; diff --git a/crypto/src/pqc/crypto/saber/SABERPrivateKeyParameters.cs b/crypto/src/pqc/crypto/saber/SABERPrivateKeyParameters.cs index 9dc9d1393..ec4add8b5 100644 --- a/crypto/src/pqc/crypto/saber/SABERPrivateKeyParameters.cs +++ b/crypto/src/pqc/crypto/saber/SABERPrivateKeyParameters.cs @@ -2,8 +2,8 @@ using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERPrivateKeyParameters - : SABERKeyParameters + public class SaberPrivateKeyParameters + : SaberKeyParameters { private byte[] privateKey; @@ -12,7 +12,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Saber return Arrays.Clone(privateKey); } - public SABERPrivateKeyParameters(SABERParameters parameters, byte[] privateKey) + public SaberPrivateKeyParameters(SaberParameters parameters, byte[] privateKey) : base(true, parameters) { this.privateKey = Arrays.Clone(privateKey); diff --git a/crypto/src/pqc/crypto/saber/SABERPublicKeyParameters.cs b/crypto/src/pqc/crypto/saber/SABERPublicKeyParameters.cs index d8dc16cb4..dcac1ec3c 100644 --- a/crypto/src/pqc/crypto/saber/SABERPublicKeyParameters.cs +++ b/crypto/src/pqc/crypto/saber/SABERPublicKeyParameters.cs @@ -2,8 +2,8 @@ using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Pqc.Crypto.Saber { - public class SABERPublicKeyParameters - : SABERKeyParameters + public class SaberPublicKeyParameters + : SaberKeyParameters { public byte[] publicKey; @@ -14,7 +14,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Saber return PublicKey; } - public SABERPublicKeyParameters(SABERParameters parameters, byte[] publicKey) + public SaberPublicKeyParameters(SaberParameters parameters, byte[] publicKey) : base(false, parameters) { this.publicKey = Arrays.Clone(publicKey); diff --git a/crypto/src/pqc/crypto/utils/PqcUtilities.cs b/crypto/src/pqc/crypto/utils/PqcUtilities.cs index 26ced321a..d0873d702 100644 --- a/crypto/src/pqc/crypto/utils/PqcUtilities.cs +++ b/crypto/src/pqc/crypto/utils/PqcUtilities.cs @@ -3,6 +3,7 @@ using System.Collections.Generic; using Org.BouncyCastle.Asn1; using Org.BouncyCastle.Asn1.BC; +using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; @@ -19,8 +20,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities private readonly static Dictionary<CmceParameters, DerObjectIdentifier> mcElieceOids = new Dictionary<CmceParameters, DerObjectIdentifier>(); private readonly static Dictionary<DerObjectIdentifier, CmceParameters> mcElieceParams = new Dictionary<DerObjectIdentifier, CmceParameters>(); - private readonly static Dictionary<SABERParameters, DerObjectIdentifier> saberOids = new Dictionary<SABERParameters, DerObjectIdentifier>(); - private readonly static Dictionary<DerObjectIdentifier, SABERParameters> saberParams = new Dictionary<DerObjectIdentifier, SABERParameters>(); + private readonly static Dictionary<SaberParameters, DerObjectIdentifier> saberOids = new Dictionary<SaberParameters, DerObjectIdentifier>(); + private readonly static Dictionary<DerObjectIdentifier, SaberParameters> saberParams = new Dictionary<DerObjectIdentifier, SaberParameters>(); private readonly static Dictionary<PicnicParameters, DerObjectIdentifier> picnicOids = new Dictionary<PicnicParameters, DerObjectIdentifier>(); private readonly static Dictionary<DerObjectIdentifier, PicnicParameters> picnicParams = new Dictionary<DerObjectIdentifier, PicnicParameters>(); @@ -37,7 +38,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities private readonly static Dictionary<FalconParameters, DerObjectIdentifier> falconOids = new Dictionary<FalconParameters, DerObjectIdentifier>(); private readonly static Dictionary<DerObjectIdentifier, FalconParameters> falconParams = new Dictionary<DerObjectIdentifier, FalconParameters>(); - + private readonly static Dictionary<BikeParameters, DerObjectIdentifier> bikeOids = new Dictionary<BikeParameters, DerObjectIdentifier>(); + private readonly static Dictionary<DerObjectIdentifier, BikeParameters> bikeParams = new Dictionary<DerObjectIdentifier, BikeParameters>(); + static PqcUtilities() { // CMCE @@ -63,25 +66,25 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities mcElieceParams[BCObjectIdentifiers.mceliece8192128_r3] = CmceParameters.mceliece8192128r3; mcElieceParams[BCObjectIdentifiers.mceliece8192128f_r3] = CmceParameters.mceliece8192128fr3; - saberOids[SABERParameters.lightsaberkem128r3] = BCObjectIdentifiers.lightsaberkem128r3; - saberOids[SABERParameters.saberkem128r3] = BCObjectIdentifiers.saberkem128r3; - saberOids[SABERParameters.firesaberkem128r3] = BCObjectIdentifiers.firesaberkem128r3; - saberOids[SABERParameters.lightsaberkem192r3] = BCObjectIdentifiers.lightsaberkem192r3; - saberOids[SABERParameters.saberkem192r3] = BCObjectIdentifiers.saberkem192r3; - saberOids[SABERParameters.firesaberkem192r3] = BCObjectIdentifiers.firesaberkem192r3; - saberOids[SABERParameters.lightsaberkem256r3] = BCObjectIdentifiers.lightsaberkem256r3; - saberOids[SABERParameters.saberkem256r3] = BCObjectIdentifiers.saberkem256r3; - saberOids[SABERParameters.firesaberkem256r3] = BCObjectIdentifiers.firesaberkem256r3; + saberOids[SaberParameters.lightsaberkem128r3] = BCObjectIdentifiers.lightsaberkem128r3; + saberOids[SaberParameters.saberkem128r3] = BCObjectIdentifiers.saberkem128r3; + saberOids[SaberParameters.firesaberkem128r3] = BCObjectIdentifiers.firesaberkem128r3; + saberOids[SaberParameters.lightsaberkem192r3] = BCObjectIdentifiers.lightsaberkem192r3; + saberOids[SaberParameters.saberkem192r3] = BCObjectIdentifiers.saberkem192r3; + saberOids[SaberParameters.firesaberkem192r3] = BCObjectIdentifiers.firesaberkem192r3; + saberOids[SaberParameters.lightsaberkem256r3] = BCObjectIdentifiers.lightsaberkem256r3; + saberOids[SaberParameters.saberkem256r3] = BCObjectIdentifiers.saberkem256r3; + saberOids[SaberParameters.firesaberkem256r3] = BCObjectIdentifiers.firesaberkem256r3; - saberParams[BCObjectIdentifiers.lightsaberkem128r3] = SABERParameters.lightsaberkem128r3; - saberParams[BCObjectIdentifiers.saberkem128r3] = SABERParameters.saberkem128r3; - saberParams[BCObjectIdentifiers.firesaberkem128r3] = SABERParameters.firesaberkem128r3; - saberParams[BCObjectIdentifiers.lightsaberkem192r3] = SABERParameters.lightsaberkem192r3; - saberParams[BCObjectIdentifiers.saberkem192r3] = SABERParameters.saberkem192r3; - saberParams[BCObjectIdentifiers.firesaberkem192r3] = SABERParameters.firesaberkem192r3; - saberParams[BCObjectIdentifiers.lightsaberkem256r3] = SABERParameters.lightsaberkem256r3; - saberParams[BCObjectIdentifiers.saberkem256r3] = SABERParameters.saberkem256r3; - saberParams[BCObjectIdentifiers.firesaberkem256r3] = SABERParameters.firesaberkem256r3; + saberParams[BCObjectIdentifiers.lightsaberkem128r3] = SaberParameters.lightsaberkem128r3; + saberParams[BCObjectIdentifiers.saberkem128r3] = SaberParameters.saberkem128r3; + saberParams[BCObjectIdentifiers.firesaberkem128r3] = SaberParameters.firesaberkem128r3; + saberParams[BCObjectIdentifiers.lightsaberkem192r3] = SaberParameters.lightsaberkem192r3; + saberParams[BCObjectIdentifiers.saberkem192r3] = SaberParameters.saberkem192r3; + saberParams[BCObjectIdentifiers.firesaberkem192r3] = SaberParameters.firesaberkem192r3; + saberParams[BCObjectIdentifiers.lightsaberkem256r3] = SaberParameters.lightsaberkem256r3; + saberParams[BCObjectIdentifiers.saberkem256r3] = SaberParameters.saberkem256r3; + saberParams[BCObjectIdentifiers.firesaberkem256r3] = SaberParameters.firesaberkem256r3; picnicOids[PicnicParameters.picnicl1fs] = BCObjectIdentifiers.picnicl1fs; @@ -162,6 +165,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities dilithiumParams[BCObjectIdentifiers.dilithium2_aes] = DilithiumParameters.Dilithium2Aes; dilithiumParams[BCObjectIdentifiers.dilithium3_aes] = DilithiumParameters.Dilithium3Aes; dilithiumParams[BCObjectIdentifiers.dilithium5_aes] = DilithiumParameters.Dilithium5Aes; + + bikeOids[BikeParameters.bike128] = BCObjectIdentifiers.bike128; + bikeOids[BikeParameters.bike192] = BCObjectIdentifiers.bike192; + bikeOids[BikeParameters.bike256] = BCObjectIdentifiers.bike256; + + bikeParams[BCObjectIdentifiers.bike128] = BikeParameters.bike128; + bikeParams[BCObjectIdentifiers.bike192] = BikeParameters.bike192; + bikeParams[BCObjectIdentifiers.bike256] = BikeParameters.bike256; } public static DerObjectIdentifier McElieceOidLookup(CmceParameters parameters) @@ -174,11 +185,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return mcElieceParams[oid]; } - internal static DerObjectIdentifier SaberOidLookup(SABERParameters parameters) + internal static DerObjectIdentifier SaberOidLookup(SaberParameters parameters) { return saberOids[parameters]; } - internal static SABERParameters SaberParamsLookup(DerObjectIdentifier oid) + internal static SaberParameters SaberParamsLookup(DerObjectIdentifier oid) { return saberParams[oid]; } @@ -243,5 +254,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return sikeParams[oid]; } + internal static DerObjectIdentifier BikeOidLookup(BikeParameters parameters) + { + return bikeOids[parameters]; + } + + internal static BikeParameters BikeParamsLookup(DerObjectIdentifier oid) + { + return bikeParams[oid]; + } } } diff --git a/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs b/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs index 63ae37e48..937242903 100644 --- a/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs +++ b/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs @@ -9,6 +9,7 @@ using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math; using Org.BouncyCastle.Pqc.Asn1; +using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; @@ -90,9 +91,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities if (algOID.On(BCObjectIdentifiers.pqc_kem_saber)) { byte[] keyEnc = Asn1OctetString.GetInstance(keyInfo.ParsePrivateKey()).GetOctets(); - SABERParameters spParams = PqcUtilities.SaberParamsLookup(keyInfo.PrivateKeyAlgorithm.Algorithm); + SaberParameters spParams = PqcUtilities.SaberParamsLookup(keyInfo.PrivateKeyAlgorithm.Algorithm); - return new SABERPrivateKeyParameters(spParams, keyEnc); + return new SaberPrivateKeyParameters(spParams, keyEnc); } if (algOID.On(BCObjectIdentifiers.picnic)) { @@ -108,6 +109,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return new SIKEPrivateKeyParameters(sikeParams, keyEnc); } + if (algOID.On(BCObjectIdentifiers.pqc_kem_bike)) + { + byte[] keyEnc = Asn1OctetString.GetInstance(keyInfo.ParsePrivateKey()).GetOctets(); + BikeParameters bikeParams = PqcUtilities.BikeParamsLookup(keyInfo.PrivateKeyAlgorithm.Algorithm); + + byte[] h0 = Arrays.CopyOfRange(keyEnc, 0, bikeParams.RByte); + byte[] h1 = Arrays.CopyOfRange(keyEnc, bikeParams.RByte, 2 * bikeParams.RByte); + byte[] sigma = Arrays.CopyOfRange(keyEnc, 2 * bikeParams.RByte, keyEnc.Length); + + + return new BikePrivateKeyParameters(bikeParams, h0, h1, sigma); + } if (algOID.Equals(BCObjectIdentifiers.kyber512) || algOID.Equals(BCObjectIdentifiers.kyber512_aes) || algOID.Equals(BCObjectIdentifiers.kyber768) diff --git a/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs b/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs index 010d9f0e3..61b02f009 100644 --- a/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs +++ b/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs @@ -13,6 +13,7 @@ using Org.BouncyCastle.Pqc.Crypto.Lms; using Org.BouncyCastle.Pqc.Crypto.Picnic; using Org.BouncyCastle.Pqc.Crypto.Saber; using Org.BouncyCastle.Pqc.Crypto.Sike; +using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.SphincsPlus; using Org.BouncyCastle.Utilities; @@ -85,9 +86,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities parameters.Alpha, parameters.S, CmcePub); return new PrivateKeyInfo(algorithmIdentifier, CmcePriv, attributes); } - if (privateKey is SABERPrivateKeyParameters) + if (privateKey is SaberPrivateKeyParameters) { - SABERPrivateKeyParameters parameters = (SABERPrivateKeyParameters)privateKey; + SaberPrivateKeyParameters parameters = (SaberPrivateKeyParameters)privateKey; byte[] encoding = parameters.GetEncoded(); @@ -169,6 +170,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return new PrivateKeyInfo(algorithmIdentifier, new DerSequence(v), attributes, new DerSequence(vPub).GetEncoded()); } + if (privateKey is BikePrivateKeyParameters) + { + BikePrivateKeyParameters parameters = (BikePrivateKeyParameters)privateKey; + + byte[] encoding = parameters.GetEncoded(); + + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier(PqcUtilities.BikeOidLookup(parameters.Parameters)); + return new PrivateKeyInfo(algorithmIdentifier, new DerOctetString(encoding), attributes); + } throw new ArgumentException("Class provided is not convertible: " + Platform.GetTypeName(privateKey)); } diff --git a/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs b/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs index a5aaca92c..3f352bf04 100644 --- a/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs +++ b/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs @@ -9,6 +9,7 @@ using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math; using Org.BouncyCastle.Pqc.Asn1; +using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; @@ -93,6 +94,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities converters[BCObjectIdentifiers.kyber768_aes] = new KyberConverter(); converters[BCObjectIdentifiers.kyber1024] = new KyberConverter(); converters[BCObjectIdentifiers.kyber1024_aes] = new KyberConverter(); + + converters[BCObjectIdentifiers.bike128] = new BikeConverter(); + converters[BCObjectIdentifiers.bike192] = new BikeConverter(); + converters[BCObjectIdentifiers.bike256] = new BikeConverter(); } /// <summary> Create a public key from a SubjectPublicKeyInfo encoding</summary> @@ -180,9 +185,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities byte[] keyEnc = DerOctetString.GetInstance( DerSequence.GetInstance(keyInfo.ParsePublicKey())[0]).GetOctets(); - SABERParameters saberParams = PqcUtilities.SaberParamsLookup(keyInfo.AlgorithmID.Algorithm); + SaberParameters saberParams = PqcUtilities.SaberParamsLookup(keyInfo.AlgorithmID.Algorithm); - return new SABERPublicKeyParameters(saberParams, keyEnc); + return new SaberPublicKeyParameters(saberParams, keyEnc); } } @@ -287,5 +292,17 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities } } } + + private class BikeConverter: SubjectPublicKeyInfoConverter + { + internal override AsymmetricKeyParameter GetPublicKeyParameters(SubjectPublicKeyInfo keyInfo, object defaultParams) + { + byte[] keyEnc = DerOctetString.GetInstance(keyInfo.ParsePublicKey()).GetOctets(); + + BikeParameters bikeParams = PqcUtilities.BikeParamsLookup(keyInfo.AlgorithmID.Algorithm); + + return new BikePublicKeyParameters(bikeParams, keyEnc); + } + } } } \ No newline at end of file diff --git a/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs b/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs index 8aa09af06..75a89c3f0 100644 --- a/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs +++ b/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs @@ -5,6 +5,7 @@ using Org.BouncyCastle.Asn1.X509; using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Math; using Org.BouncyCastle.Pqc.Asn1; +using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; @@ -62,9 +63,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities // https://datatracker.ietf.org/doc/draft-uni-qsckeys/ return new SubjectPublicKeyInfo(algorithmIdentifier, new CmcePublicKey(encoding)); } - if (publicKey is SABERPublicKeyParameters) + if (publicKey is SaberPublicKeyParameters) { - SABERPublicKeyParameters parameters = (SABERPublicKeyParameters)publicKey; + SaberPublicKeyParameters parameters = (SaberPublicKeyParameters)publicKey; byte[] encoding = parameters.GetEncoded(); @@ -120,9 +121,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities v.Add(new DerOctetString(parameters.T1)); return new SubjectPublicKeyInfo(algorithmIdentifier, new DerSequence(v)); } - - throw new ArgumentException("Class provided no convertible: " + Platform.GetTypeName(publicKey)); + if (publicKey is BikePublicKeyParameters) + { + BikePublicKeyParameters parameters = (BikePublicKeyParameters)publicKey; + + + byte[] encoding = parameters.GetEncoded(); + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier(PqcUtilities.BikeOidLookup(parameters.Parameters)); + return new SubjectPublicKeyInfo(algorithmIdentifier, new DerOctetString(encoding)); + } + + throw new ArgumentException("Class provided no convertible: " + Platform.GetTypeName(publicKey)); } private static void ExtractBytes( diff --git a/crypto/src/pqc/math/linearalgebra/GF2mField.cs b/crypto/src/pqc/math/linearalgebra/GF2mField.cs new file mode 100644 index 000000000..e8182bf6f --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/GF2mField.cs @@ -0,0 +1,370 @@ +using Org.BouncyCastle.Security; +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + public class GF2mField + { + + /* + * degree - degree of the field polynomial - the field polynomial ring - + * polynomial ring over the finite field GF(2) + */ + + private int degree = 0; + + private int polynomial; + + /** + * create a finite field GF(2^m) + * + * @param degree the degree of the field + */ + public GF2mField(int degree) + { + if (degree >= 32) + { + throw new ArgumentException( + " Error: the degree of field is too large "); + } + if (degree < 1) + { + throw new ArgumentException( + " Error: the degree of field is non-positive "); + } + this.degree = degree; + polynomial = PolynomialRingGF2.GetIrreduciblePolynomial(degree); + } + + /** + * create a finite field GF(2^m) with the fixed field polynomial + * + * @param degree the degree of the field + * @param poly the field polynomial + */ + public GF2mField(int degree, int poly) + { + if (degree != PolynomialRingGF2.Degree(poly)) + { + throw new ArgumentException( + " Error: the degree is not correct"); + } + if (!PolynomialRingGF2.IsIrreducible(poly)) + { + throw new ArgumentException( + " Error: given polynomial is reducible"); + } + this.degree = degree; + polynomial = poly; + + } + + public GF2mField(byte[] enc) + { + if (enc.Length != 4) + { + throw new ArgumentException( + "byte array is not an encoded finite field"); + } + polynomial = LittleEndianConversions.OS2IP(enc); + if (!PolynomialRingGF2.IsIrreducible(polynomial)) + { + throw new ArgumentException( + "byte array is not an encoded finite field"); + } + + degree = PolynomialRingGF2.Degree(polynomial); + } + + public GF2mField(GF2mField field) + { + degree = field.degree; + polynomial = field.polynomial; + } + + /** + * return degree of the field + * + * @return degree of the field + */ + public int GetDegree() + { + return degree; + } + + /** + * return the field polynomial + * + * @return the field polynomial + */ + public int GetPolynomial() + { + return polynomial; + } + + /** + * return the encoded form of this field + * + * @return the field in byte array form + */ + public byte[] GetEncoded() + { + return LittleEndianConversions.I2OSP(polynomial); + } + + /** + * Return sum of two elements + * + * @param a + * @param b + * @return a+b + */ + public int add(int a, int b) + { + return a ^ b; + } + + /** + * Return product of two elements + * + * @param a + * @param b + * @return a*b + */ + public int Mult(int a, int b) + { + return PolynomialRingGF2.modMultiply(a, b, polynomial); + } + + /** + * compute exponentiation a^k + * + * @param a a field element a + * @param k k degree + * @return a^k + */ + public int Exp(int a, int k) + { + if (k == 0) + { + return 1; + } + if (a == 0) + { + return 0; + } + if (a == 1) + { + return 1; + } + int result = 1; + if (k < 0) + { + a = Inverse(a); + k = -k; + } + while (k != 0) + { + if ((k & 1) == 1) + { + result = Mult(result, a); + } + a = Mult(a, a); + //k >>>= 1; + uint kTmp = (uint)k; + kTmp >>= 1; + k = (int) kTmp; + } + return result; + } + + /** + * compute the multiplicative inverse of a + * + * @param a a field element a + * @return a<sup>-1</sup> + */ + public int Inverse(int a) + { + int d = (1 << degree) - 2; + + return Exp(a, d); + } + + /** + * compute the square root of an integer + * + * @param a a field element a + * @return a<sup>1/2</sup> + */ + public int SqRoot(int a) + { + for (int i = 1; i < degree; i++) + { + a = Mult(a, a); + } + return a; + } + + /** + * create a random field element using PRNG sr + * + * @param sr SecureRandom + * @return a random element + */ + public int GetRandomElement(SecureRandom sr) + { + int result = RandUtils.NextInt(sr, 1 << degree); + return result; + } + + /** + * create a random non-zero field element + * + * @return a random element + */ + //public int getRandomNonZeroElement() + //{ + // return getRandomNonZeroElement(CryptoServicesRegistrar.getSecureRandom()); + //} + + /** + * create a random non-zero field element using PRNG sr + * + * @param sr SecureRandom + * @return a random non-zero element + */ + public int GetRandomNonZeroElement(SecureRandom sr) + { + int controltime = 1 << 20; + int count = 0; + int result = RandUtils.NextInt(sr, 1 << degree); + while ((result == 0) && (count < controltime)) + { + result = RandUtils.NextInt(sr, 1 << degree); + count++; + } + if (count == controltime) + { + result = 1; + } + return result; + } + + /** + * @return true if e is encoded element of this field and false otherwise + */ + public bool IsElementOfThisField(int e) + { + // e is encoded element of this field iff 0<= e < |2^m| + if (degree == 31) + { + return e >= 0; + } + return e >= 0 && e < (1 << degree); + } + + /* + * help method for visual control + */ + public String ElementToStr(int a) + { + String s = ""; + for (int i = 0; i < degree; i++) + { + if (((byte)a & 0x01) == 0) + { + s = "0" + s; + } + else + { + s = "1" + s; + } + //a >>>= 1; + uint aTmp = (uint)a; + aTmp >>= 1; + a = (int)aTmp; + } + return s; + } + + /** + * checks if given object is equal to this field. + * <p> + * The method returns false whenever the given object is not GF2m. + * + * @param other object + * @return true or false + */ + public bool Equals(Object other) + { + if ((other == null) || !(other is GF2mField)) + { + return false; + } + + GF2mField otherField = (GF2mField)other; + + if ((degree == otherField.degree) + && (polynomial == otherField.polynomial)) + { + return true; + } + + return false; + } + + public int HashCode() + { + return polynomial; + } + + /** + * Returns a human readable form of this field. + * + * @return a human readable form of this field. + */ + public String ToString() + { + String str = "Finite Field GF(2^" + degree + ") = " + "GF(2)[X]/<" + + PolyToString(polynomial) + "> "; + return str; + } + + private static String PolyToString(int p) + { + String str = ""; + if (p == 0) + { + str = "0"; + } + else + { + byte b = (byte)(p & 0x01); + if (b == 1) + { + str = "1"; + } + //p >>>= 1; + uint pTmp = (uint)p; + pTmp >>= 1; + p = (int)pTmp; + int i = 1; + while (p != 0) + { + b = (byte)(p & 0x01); + if (b == 1) + { + str = str + "+x^" + i; + } + //p >>>= 1; + pTmp = (uint) p; + pTmp >>= 1; + p = (int)pTmp; + i++; + } + } + return str; + } + } +} \ No newline at end of file diff --git a/crypto/src/pqc/math/linearalgebra/GF2mVector.cs b/crypto/src/pqc/math/linearalgebra/GF2mVector.cs new file mode 100644 index 000000000..f0e44ebe6 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/GF2mVector.cs @@ -0,0 +1,221 @@ +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + /** + * This class implements vectors over the finite field + * <tt>GF(2<sup>m</sup>)</tt> for small <tt>m</tt> (i.e., + * <tt>1<m<32</tt>). It extends the abstract class {@link Vector}. + */ +public class GF2mVector : Vector +{ + + /** + * the finite field this vector is defined over + */ + private GF2mField field; + + /** + * the element array + */ + private int[] vector; + + /** + * creates the vector over GF(2^m) of given length and with elements from + * array v (beginning at the first bit) + * + * @param field finite field + * @param v array with elements of vector + */ + public GF2mVector(GF2mField field, byte[] v) + { + this.field = new GF2mField(field); + + // decode vector + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + if ((v.Length % count) != 0) + { + throw new ArgumentException( + "Byte array is not an encoded vector over the given finite field."); + } + + length = v.Length / count; + vector = new int[length]; + count = 0; + for (int i = 0; i < vector.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + vector[i] |= (v[count++] & 0xff) << j; + } + if (!field.IsElementOfThisField(vector[i])) + { + throw new ArgumentException( + "Byte array is not an encoded vector over the given finite field."); + } + } + } + + /** + * Create a new vector over <tt>GF(2<sup>m</sup>)</tt> of the given + * length and element array. + * + * @param field the finite field <tt>GF(2<sup>m</sup>)</tt> + * @param vector the element array + */ + public GF2mVector(GF2mField field, int[] vector) + { + this.field = field; + length = vector.Length; + for (int i = vector.Length - 1; i >= 0; i--) + { + if (!field.IsElementOfThisField(vector[i])) + { + throw new ArithmeticException( + "Element array is not specified over the given finite field."); + } + } + this.vector = IntUtils.Clone(vector); + } + + /** + * Copy constructor. + * + * @param other another {@link GF2mVector} + */ + public GF2mVector(GF2mVector other) + { + field = new GF2mField(other.field); + length = other.length; + vector = IntUtils.Clone(other.vector); + } + + /** + * @return the finite field this vector is defined over + */ + public GF2mField GetField() + { + return field; + } + + /** + * @return int[] form of this vector + */ + public int[] GetIntArrayForm() + { + return IntUtils.Clone(vector); + } + + /** + * @return a byte array encoding of this vector + */ + public override byte[] GetEncoded() + { + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + byte[] res = new byte[vector.Length * count]; + count = 0; + for (int i = 0; i < vector.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + res[count++] = (byte)(Utils.UnsignedRightBitShiftInt(vector[i], j)); + } + } + + return res; + } + + /** + * @return whether this is the zero vector (i.e., all elements are zero) + */ + public override bool IsZero() + { + for (int i = vector.Length - 1; i >= 0; i--) + { + if (vector[i] != 0) + { + return false; + } + } + return true; + } + + /** + * Add another vector to this vector. Method is not yet implemented. + * + * @param addend the other vector + * @return <tt>this + addend</tt> + * @throws ArithmeticException if the other vector is not defined over the same field as + * this vector. + * <p> + * TODO: implement this method + */ + public override Vector Add(Vector addend) + { + throw new SystemException("not implemented"); + } + + /** + * Multiply this vector with a permutation. + * + * @param p the permutation + * @return <tt>this*p = p*this</tt> + */ + public override Vector Multiply(Permutation p) + { + int[] pVec = p.GetVector(); + if (length != pVec.Length) + { + throw new ArithmeticException( + "permutation size and vector size mismatch"); + } + + int[] result = new int[length]; + for (int i = 0; i < pVec.Length; i++) + { + result[i] = vector[pVec[i]]; + } + + return new GF2mVector(field, result); + } + + /** + * Compare this vector with another object. + * + * @param other the other object + * @return the result of the comparison + */ + public override bool Equals(Object other) + { + + if (!(other is GF2mVector)) + { + return false; + } + GF2mVector otherVec = (GF2mVector)other; + + if (!field.Equals(otherVec.field)) + { + return false; + } + + return IntUtils.Equals(vector, otherVec.vector); + } + + + } +} diff --git a/crypto/src/pqc/math/linearalgebra/IntUtils.cs b/crypto/src/pqc/math/linearalgebra/IntUtils.cs new file mode 100644 index 000000000..0a7671df6 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/IntUtils.cs @@ -0,0 +1,159 @@ +using Org.BouncyCastle.Utilities; +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + public class IntUtils + { + + /** + * Default constructor (private). + */ + private IntUtils() + { + // empty + } + + /** + * Compare two int arrays. No null checks are performed. + * + * @param left the first int array + * @param right the second int array + * @return the result of the comparison + */ + public static bool Equals(int[] left, int[] right) + { + return Arrays.AreEqual(left, right); + } + + /** + * Return a clone of the given int array. No null checks are performed. + * + * @param array the array to clone + * @return the clone of the given array + */ + public static int[] Clone(int[] array) + { + return Arrays.Clone(array); + } + + /** + * Fill the given int array with the given value. + * + * @param array the array + * @param value the value + */ + public static void Fill(int[] array, int value) + { + Arrays.Fill(array, value); + } + + /** + * Sorts this array of integers according to the Quicksort algorithm. After + * calling this method this array is sorted in ascending order with the + * smallest integer taking position 0 in the array. + * <p> + * This implementation is based on the quicksort algorithm as described in + * <code>Data Structures In Java</code> by Thomas A. Standish, Chapter 10, + * ISBN 0-201-30564-X. + * + * @param source the array of integers that needs to be sorted. + */ + public static void Quicksort(int[] source) + { + Quicksort(source, 0, source.Length - 1); + } + + /** + * Sort a subarray of a source array. The subarray is specified by its start + * and end index. + * + * @param source the int array to be sorted + * @param left the start index of the subarray + * @param right the end index of the subarray + */ + public static void Quicksort(int[] source, int left, int right) + { + if (right > left) + { + int index = Partition(source, left, right, right); + Quicksort(source, left, index - 1); + Quicksort(source, index + 1, right); + } + } + + /** + * Split a subarray of a source array into two partitions. The left + * partition contains elements that have value less than or equal to the + * pivot element, the right partition contains the elements that have larger + * value. + * + * @param source the int array whose subarray will be splitted + * @param left the start position of the subarray + * @param right the end position of the subarray + * @param pivotIndex the index of the pivot element inside the array + * @return the new index of the pivot element inside the array + */ + private static int Partition(int[] source, int left, int right, + int pivotIndex) + { + + int pivot = source[pivotIndex]; + source[pivotIndex] = source[right]; + source[right] = pivot; + + int index = left; + int tmp = 0; + for (int i = left; i < right; i++) + { + if (source[i] <= pivot) + { + tmp = source[index]; + source[index] = source[i]; + source[i] = tmp; + index++; + } + } + + tmp = source[index]; + source[index] = source[right]; + source[right] = tmp; + + return index; + } + + /** + * Generates a subarray of a given int array. + * + * @param input - + * the input int array + * @param start - + * the start index + * @param end - + * the end index + * @return a subarray of <tt>input</tt>, ranging from <tt>start</tt> to + * <tt>end</tt> + */ + public static int[] SubArray( int[] input, int start, + int end) + { + int[] result = new int[end - start]; + Array.Copy(input, start, result, 0, end - start); + return result; + } + + /** + * @param input an int array + * @return a human readable form of the given int array + */ + public static String ToString(int[] input) + { + String result = ""; + for (int i = 0; i < input.Length; i++) + { + result += input[i] + " "; + } + return result; + } + } +} diff --git a/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs b/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs new file mode 100644 index 000000000..5b3215070 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs @@ -0,0 +1,195 @@ + +using Org.BouncyCastle.Crypto.Utilities; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + /** + * This is a utility class containing data type conversions using little-endian + * byte order. + * + */ + class LittleEndianConversions + { + /** + * Default constructor (private). + */ + private LittleEndianConversions() + { + // empty + } + + /** + * Convert an octet string of length 4 to an integer. No length checking is + * performed. + * + * @param input the byte array holding the octet string + * @return an integer representing the octet string <tt>input</tt> + * @throws ArithmeticException if the length of the given octet string is larger than 4. + */ + public static int OS2IP(byte[] input) + { + return (int)Pack.LE_To_UInt32(input); + } + + /** + * Convert an byte array of length 4 beginning at <tt>offset</tt> into an + * integer. + * + * @param input the byte array + * @param inOff the offset into the byte array + * @return the resulting integer + */ + public static int OS2IP(byte[] input, int inOff) + { + return (int)Pack.LE_To_UInt32(input, inOff); + } + + /** + * Convert a byte array of the given length beginning at <tt>offset</tt> + * into an integer. + * + * @param input the byte array + * @param inOff the offset into the byte array + * @param inLen the length of the encoding + * @return the resulting integer + */ + public static int OS2IP(byte[] input, int inOff, int inLen) + { + int result = 0; + for (int i = inLen - 1; i >= 0; i--) + { + result |= (input[inOff + i] & 0xff) << (8 * i); + } + return result; + } + + /** + * Convert a byte array of length 8 beginning at <tt>inOff</tt> into a + * long integer. + * + * @param input the byte array + * @param inOff the offset into the byte array + * @return the resulting long integer + */ + public static long OS2LIP(byte[] input, int inOff) + { + return (long)Pack.LE_To_UInt64(input, inOff); + } + + /** + * Convert an integer to an octet string of length 4. + * + * @param x the integer to convert + * @return the converted integer + */ + public static byte[] I2OSP(int x) + { + return Pack.UInt32_To_LE((uint)x); + } + + /** + * Convert an integer into a byte array beginning at the specified offset. + * + * @param value the integer to convert + * @param output the byte array to hold the result + * @param outOff the integer offset into the byte array + */ + public static void I2OSP(int value, byte[] output, int outOff) + { + Pack.UInt32_To_LE((uint)value, output, outOff); + } + + /** + * Convert an integer to a byte array beginning at the specified offset. No + * length checking is performed (i.e., if the integer cannot be encoded with + * <tt>length</tt> octets, it is truncated). + * + * @param value the integer to convert + * @param output the byte array to hold the result + * @param outOff the integer offset into the byte array + * @param outLen the length of the encoding + */ + public static void I2OSP(int value, byte[] output, int outOff, int outLen) + { + uint valueTmp = (uint)value; + for (int i = outLen - 1; i >= 0; i--) + { + output[outOff + i] = (byte)(valueTmp >> (8 * i)); + } + } + + /** + * Convert an integer to a byte array of length 8. + * + * @param input the integer to convert + * @return the converted integer + */ + public static byte[] I2OSP(long input) + { + return Pack.UInt64_To_LE((ulong)input); + } + + /** + * Convert an integer to a byte array of length 8. + * + * @param input the integer to convert + * @param output byte array holding the output + * @param outOff offset in output array where the result is stored + */ + public static void I2OSP(long input, byte[] output, int outOff) + { + Pack.UInt64_To_LE((ulong)input, output, outOff); + } + + /** + * Convert an int array to a byte array of the specified length. No length + * checking is performed (i.e., if the last integer cannot be encoded with + * <tt>length % 4</tt> octets, it is truncated). + * + * @param input the int array + * @param outLen the length of the converted array + * @return the converted array + */ + public static byte[] ToByteArray(int[] input, int outLen) + { + int intLen = input.Length; + byte[] result = new byte[outLen]; + int index = 0; + for (int i = 0; i <= intLen - 2; i++, index += 4) + { + I2OSP(input[i], result, index); + } + I2OSP(input[intLen - 1], result, index, outLen - index); + return result; + } + + /** + * Convert a byte array to an int array. + * + * @param input the byte array + * @return the converted array + */ + public static int[] ToIntArray(byte[] input) + { + int intLen = (input.Length + 3) / 4; + int lastLen = input.Length & 0x03; + int[] result = new int[intLen]; + + int index = 0; + for (int i = 0; i <= intLen - 2; i++, index += 4) + { + result[i] = OS2IP(input, index); + } + if (lastLen != 0) + { + result[intLen - 1] = OS2IP(input, index, lastLen); + } + else + { + result[intLen - 1] = OS2IP(input, index); + } + + return result; + } + } +} diff --git a/crypto/src/pqc/math/linearalgebra/Permutation.cs b/crypto/src/pqc/math/linearalgebra/Permutation.cs new file mode 100644 index 000000000..0d36958c9 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Permutation.cs @@ -0,0 +1,192 @@ +using Org.BouncyCastle.Security; +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + /** + * This class implements permutations of the set {0,1,...,n-1} for some given n + * > 0, i.e., ordered sequences containing each number <tt>m</tt> (<tt>0 <= + * m < n</tt>) + * once and only once. + */ + public class Permutation + { + + /** + * perm holds the elements of the permutation vector, i.e. <tt>[perm(0), + * perm(1), ..., perm(n-1)]</tt> + */ + private int[] perm; + + /** + * Create the identity permutation of the given size. + * + * @param n the size of the permutation + */ + public Permutation(int n) + { + if (n <= 0) + { + throw new ArgumentException("invalid length"); + } + + perm = new int[n]; + for (int i = n - 1; i >= 0; i--) + { + perm[i] = i; + } + } + + /** + * Create a permutation using the given permutation vector. + * + * @param perm the permutation vector + */ + public Permutation(int[] perm) + { + if (!IsPermutation(perm)) + { + throw new ArgumentException( + "array is not a permutation vector"); + } + + this.perm = IntUtils.Clone(perm); + } + + /** + * Create a random permutation of the given size. + * + * @param n the size of the permutation + * @param sr the source of randomness + */ + public Permutation(int n, SecureRandom sr) + { + if (n <= 0) + { + throw new ArgumentException("invalid length"); + } + + perm = new int[n]; + + int[] help = new int[n]; + for (int i = 0; i < n; i++) + { + help[i] = i; + } + + int k = n; + for (int j = 0; j < n; j++) + { + int i = RandUtils.NextInt(sr, k); + k--; + perm[j] = help[i]; + help[i] = help[k]; + } + } + + + /** + * @return the permutation vector <tt>(perm(0),perm(1),...,perm(n-1))</tt> + */ + public int[] GetVector() + { + return IntUtils.Clone(perm); + } + + /** + * Compute the inverse permutation <tt>P<sup>-1</sup></tt>. + * + * @return <tt>this<sup>-1</sup></tt> + */ + public Permutation ComputeInverse() + { + Permutation result = new Permutation(perm.Length); + for (int i = perm.Length - 1; i >= 0; i--) + { + result.perm[perm[i]] = i; + } + return result; + } + + /** + * Compute the product of this permutation and another permutation. + * + * @param p the other permutation + * @return <tt>this * p</tt> + */ + public Permutation RightMultiply(Permutation p) + { + if (p.perm.Length != perm.Length) + { + throw new ArgumentException("length mismatch"); + } + Permutation result = new Permutation(perm.Length); + for (int i = perm.Length - 1; i >= 0; i--) + { + result.perm[i] = perm[p.perm[i]]; + } + return result; + } + + /** + * checks if given object is equal to this permutation. + * <p> + * The method returns false whenever the given object is not permutation. + * + * @param other - + * permutation + * @return true or false + */ + public bool equals(Object other) + { + + if (!(other is Permutation)) + { + return false; + } + Permutation otherPerm = (Permutation)other; + + return IntUtils.Equals(perm, otherPerm.perm); + } + + /** + * @return a human readable form of the permutation + */ + public String ToString() + { + String result = "[" + perm[0]; + for (int i = 1; i < perm.Length; i++) + { + result += ", " + perm[i]; + } + result += "]"; + return result; + } + + /** + * Check that the given array corresponds to a permutation of the set + * <tt>{0, 1, ..., n-1}</tt>. + * + * @param perm permutation vector + * @return true if perm represents an n-permutation and false otherwise + */ + private bool IsPermutation(int[] perm) + { + int n = perm.Length; + bool[] onlyOnce = new bool[n]; + + for (int i = 0; i < n; i++) + { + if ((perm[i] < 0) || (perm[i] >= n) || onlyOnce[perm[i]]) + { + return false; + } + onlyOnce[perm[i]] = true; + } + + return true; + } + + } + +} diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs new file mode 100644 index 000000000..9dca71bee --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs @@ -0,0 +1,1266 @@ +using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + public class PolynomialGF2mSmallM + { + + /** + * the finite field GF(2^m) + */ + private GF2mField field; + + /** + * the degree of this polynomial + */ + private int degree; + + /** + * For the polynomial representation the map f: R->Z*, + * <tt>poly(X) -> [coef_0, coef_1, ...]</tt> is used, where + * <tt>coef_i</tt> is the <tt>i</tt>th coefficient of the polynomial + * represented as int (see {@link GF2mField}). The polynomials are stored + * as int arrays. + */ + private int[] coefficients; + + /* + * some types of polynomials + */ + + /** + * Constant used for polynomial construction (see constructor + * {@link #PolynomialGF2mSmallM(GF2mField, int, char, SecureRandom)}). + */ + public const char RANDOM_IRREDUCIBLE_POLYNOMIAL = 'I'; + + /** + * Construct the zero polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + */ + public PolynomialGF2mSmallM(GF2mField field) + { + this.field = field; + degree = -1; + coefficients = new int[1]; + } + + /** + * Construct a polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param deg degree of polynomial + * @param typeOfPolynomial type of polynomial + * @param sr PRNG + */ + public PolynomialGF2mSmallM(GF2mField field, int deg, + char typeOfPolynomial, SecureRandom sr) + { + this.field = field; + + switch (typeOfPolynomial) + { + case PolynomialGF2mSmallM.RANDOM_IRREDUCIBLE_POLYNOMIAL: + coefficients = CreateRandomIrreduciblePolynomial(deg, sr); + break; + default: + throw new ArgumentException(" Error: type " + + typeOfPolynomial + + " is not defined for GF2smallmPolynomial"); + } + ComputeDegree(); + } + + /** + * Create an irreducible polynomial with the given degree over the field + * <tt>GF(2^m)</tt>. + * + * @param deg polynomial degree + * @param sr source of randomness + * @return the generated irreducible polynomial + */ + private int[] CreateRandomIrreduciblePolynomial(int deg, SecureRandom sr) + { + int[] resCoeff = new int[deg + 1]; + resCoeff[deg] = 1; + resCoeff[0] = field.GetRandomNonZeroElement(sr); + for (int i = 1; i < deg; i++) + { + resCoeff[i] = field.GetRandomElement(sr); + } + while (!IsIrreducible(resCoeff)) + { + int n = RandUtils.NextInt(sr, deg); + if (n == 0) + { + resCoeff[0] = field.GetRandomNonZeroElement(sr); + } + else + { + resCoeff[n] = field.GetRandomElement(sr); + } + } + return resCoeff; + } + + /** + * Construct a monomial of the given degree over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param degree the degree of the monomial + */ + public PolynomialGF2mSmallM(GF2mField field, int degree) + { + this.field = field; + this.degree = degree; + coefficients = new int[degree + 1]; + coefficients[degree] = 1; + } + + /** + * Construct the polynomial over the given finite field GF(2^m) from the + * given coefficient vector. + * + * @param field finite field GF2m + * @param coeffs the coefficient vector + */ + public PolynomialGF2mSmallM(GF2mField field, int[] coeffs) + { + this.field = field; + coefficients = NormalForm(coeffs); + ComputeDegree(); + } + + /** + * Create a polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param enc byte[] polynomial in byte array form + */ + public PolynomialGF2mSmallM(GF2mField field, byte[] enc) + { + this.field = field; + + // decodes polynomial + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + if ((enc.Length % count) != 0) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + + coefficients = new int[enc.Length / count]; + count = 0; + for (int i = 0; i < coefficients.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + coefficients[i] ^= (enc[count++] & 0x000000ff) << j; + } + if (!this.field.IsElementOfThisField(coefficients[i])) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + } + // if HC = 0 for non-zero polynomial, returns error + if ((coefficients.Length != 1) + && (coefficients[coefficients.Length - 1] == 0)) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + ComputeDegree(); + } + + /** + * Copy constructor. + * + * @param other another {@link PolynomialGF2mSmallM} + */ + public PolynomialGF2mSmallM(PolynomialGF2mSmallM other) + { + // field needs not to be cloned since it is immutable + field = other.field; + degree = other.degree; + coefficients = IntUtils.Clone(other.coefficients); + } + + /** + * Create a polynomial over the finite field GF(2^m) out of the given + * coefficient vector. The finite field is also obtained from the + * {@link GF2mVector}. + * + * @param vect the coefficient vector + */ + public PolynomialGF2mSmallM(GF2mVector vect) + { + new PolynomialGF2mSmallM(vect.GetField(), vect.GetIntArrayForm()); + } + + /* + * ------------------------ + */ + + /** + * Return the degree of this polynomial + * + * @return int degree of this polynomial if this is zero polynomial return + * -1 + */ + public int GetDegree() + { + int d = coefficients.Length - 1; + if (coefficients[d] == 0) + { + return -1; + } + return d; + } + + /** + * @return the head coefficient of this polynomial + */ + public int GetHeadCoefficient() + { + if (degree == -1) + { + return 0; + } + return coefficients[degree]; + } + + /** + * Return the head coefficient of a polynomial. + * + * @param a the polynomial + * @return the head coefficient of <tt>a</tt> + */ + private static int HeadCoefficient(int[] a) + { + int degree = ComputeDegree(a); + if (degree == -1) + { + return 0; + } + return a[degree]; + } + + /** + * Return the coefficient with the given index. + * + * @param index the index + * @return the coefficient with the given index + */ + public int GetCoefficient(int index) + { + if ((index < 0) || (index > degree)) + { + return 0; + } + return coefficients[index]; + } + + /** + * Returns encoded polynomial, i.e., this polynomial in byte array form + * + * @return the encoded polynomial + */ + public byte[] GetEncoded() + { + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + byte[] res = new byte[coefficients.Length * count]; + count = 0; + for (int i = 0; i < coefficients.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + res[count++] = (byte)(Utils.UnsignedRightBitShiftInt(coefficients[i], j)); + } + } + + return res; + } + + /** + * Evaluate this polynomial <tt>p</tt> at a value <tt>e</tt> (in + * <tt>GF(2^m)</tt>) with the Horner scheme. + * + * @param e the element of the finite field GF(2^m) + * @return <tt>this(e)</tt> + */ + public int evaluateAt(int e) + { + int result = coefficients[degree]; + for (int i = degree - 1; i >= 0; i--) + { + result = field.Mult(result, e) ^ coefficients[i]; + } + return result; + } + + /** + * Compute the sum of this polynomial and the given polynomial. + * + * @param addend the addend + * @return <tt>this + a</tt> (newly created) + */ + public PolynomialGF2mSmallM add(PolynomialGF2mSmallM addend) + { + int[] resultCoeff = Add(coefficients, addend.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Add the given polynomial to this polynomial (overwrite this). + * + * @param addend the addend + */ + public void AddToThis(PolynomialGF2mSmallM addend) + { + coefficients = Add(coefficients, addend.coefficients); + ComputeDegree(); + } + + /** + * Compute the sum of two polynomials a and b over the finite field + * <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @return a + b + */ + private int[] Add(int[] a, int[] b) + { + int[] result, addend; + if (a.Length < b.Length) + { + result = new int[b.Length]; + Array.Copy(b, 0, result, 0, b.Length); + addend = a; + } + else + { + result = new int[a.Length]; + Array.Copy(a, 0, result, 0, a.Length); + addend = b; + } + + for (int i = addend.Length - 1; i >= 0; i--) + { + result[i] = field.add(result[i], addend[i]); + } + + return result; + } + + /** + * Compute the sum of this polynomial and the monomial of the given degree. + * + * @param degree the degree of the monomial + * @return <tt>this + X^k</tt> + */ + public PolynomialGF2mSmallM AddMonomial(int degree) + { + int[] monomial = new int[degree + 1]; + monomial[degree] = 1; + int[] resultCoeff = Add(coefficients, monomial); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of this polynomial with an element from GF(2^m). + * + * @param element an element of the finite field GF(2^m) + * @return <tt>this * element</tt> (newly created) + * @throws ArithmeticException if <tt>element</tt> is not an element of the finite + * field this polynomial is defined over. + */ + public PolynomialGF2mSmallM MultWithElement(int element) + { + if (!field.IsElementOfThisField(element)) + { + throw new ArithmeticException( + "Not an element of the finite field this polynomial is defined over."); + } + int[] resultCoeff = MultWithElement(coefficients, element); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Multiply this polynomial with an element from GF(2^m). + * + * @param element an element of the finite field GF(2^m) + * @throws ArithmeticException if <tt>element</tt> is not an element of the finite + * field this polynomial is defined over. + */ + public void MultThisWithElement(int element) + { + if (!field.IsElementOfThisField(element)) + { + throw new ArithmeticException( + "Not an element of the finite field this polynomial is defined over."); + } + coefficients = MultWithElement(coefficients, element); + ComputeDegree(); + } + + /** + * Compute the product of a polynomial a with an element from the finite + * field <tt>GF(2^m)</tt>. + * + * @param a the polynomial + * @param element an element of the finite field GF(2^m) + * @return <tt>a * element</tt> + */ + private int[] MultWithElement(int[] a, int element) + { + int degree = ComputeDegree(a); + if (degree == -1 || element == 0) + { + return new int[1]; + } + + if (element == 1) + { + return IntUtils.Clone(a); + } + + int[] result = new int[degree + 1]; + for (int i = degree; i >= 0; i--) + { + result[i] = field.Mult(a[i], element); + } + + return result; + } + + /** + * Compute the product of this polynomial with a monomial X^k. + * + * @param k the degree of the monomial + * @return <tt>this * X^k</tt> + */ + public PolynomialGF2mSmallM MultWithMonomial(int k) + { + int[] resultCoeff = MultWithMonomial(coefficients, k); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of a polynomial with a monomial X^k. + * + * @param a the polynomial + * @param k the degree of the monomial + * @return <tt>a * X^k</tt> + */ + private static int[] MultWithMonomial(int[] a, int k) + { + int d = ComputeDegree(a); + if (d == -1) + { + return new int[1]; + } + int[] result = new int[d + k + 1]; + Array.Copy(a, 0, result, k, d + 1); + return result; + } + + /** + * Divide this polynomial by the given polynomial. + * + * @param f a polynomial + * @return polynomial pair = {q,r} where this = q*f+r and deg(r) < + * deg(f); + */ + public PolynomialGF2mSmallM[] Div(PolynomialGF2mSmallM f) + { + int[][] resultCoeffs = Div(coefficients, f.coefficients); + return new PolynomialGF2mSmallM[]{ + new PolynomialGF2mSmallM(field, resultCoeffs[0]), + new PolynomialGF2mSmallM(field, resultCoeffs[1])}; + } + + /** + * Compute the result of the division of two polynomials over the field + * <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param f the second polynomial + * @return int[][] {q,r}, where a = q*f+r and deg(r) < deg(f); + */ + private int[][] Div(int[] a, int[] f) + { + int df = ComputeDegree(f); + int da = ComputeDegree(a) + 1; + if (df == -1) + { + throw new ArithmeticException("Division by zero."); + } + int[][] result = new int[2][]; + result[0] = new int[1]; + result[1] = new int[da]; + int hc = HeadCoefficient(f); + hc = field.Inverse(hc); + result[0][0] = 0; + Array.Copy(a, 0, result[1], 0, result[1].Length); + while (df <= ComputeDegree(result[1])) + { + int[] q; + int[] coeff = new int[1]; + coeff[0] = field.Mult(HeadCoefficient(result[1]), hc); + q = MultWithElement(f, coeff[0]); + int n = ComputeDegree(result[1]) - df; + q = MultWithMonomial(q, n); + coeff = MultWithMonomial(coeff, n); + result[0] = Add(coeff, result[0]); + result[1] = Add(q, result[1]); + } + return result; + } + + /** + * Return the greatest common divisor of this and a polynomial <i>f</i> + * + * @param f polynomial + * @return GCD(this, f) + */ + public PolynomialGF2mSmallM Gcd(PolynomialGF2mSmallM f) + { + int[] resultCoeff = Gcd(coefficients, f.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Return the greatest common divisor of two polynomials over the field + * <tt>GF(2^m)</tt>. + * + * @param f the first polynomial + * @param g the second polynomial + * @return <tt>gcd(f, g)</tt> + */ + private int[] Gcd(int[] f, int[] g) + { + int[] a = f; + int[] b = g; + if (ComputeDegree(a) == -1) + { + return b; + } + while (ComputeDegree(b) != -1) + { + int[] c = Mod(a, b); + a = new int[b.Length]; + Array.Copy(b, 0, a, 0, a.Length); + b = new int[c.Length]; + Array.Copy(c, 0, b, 0, b.Length); + } + int coeff = field.Inverse(HeadCoefficient(a)); + return MultWithElement(a, coeff); + } + + /** + * Compute the product of this polynomial and the given factor using a + * Karatzuba like scheme. + * + * @param factor the polynomial + * @return <tt>this * factor</tt> + */ + public PolynomialGF2mSmallM Multiply(PolynomialGF2mSmallM factor) + { + int[] resultCoeff = Multiply(coefficients, factor.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of two polynomials over the field <tt>GF(2^m)</tt> + * using a Karatzuba like multiplication. + * + * @param a the first polynomial + * @param b the second polynomial + * @return a * b + */ + private int[] Multiply(int[] a, int[] b) + { + int[] mult1, mult2; + if (ComputeDegree(a) < ComputeDegree(b)) + { + mult1 = b; + mult2 = a; + } + else + { + mult1 = a; + mult2 = b; + } + + mult1 = NormalForm(mult1); + mult2 = NormalForm(mult2); + + if (mult2.Length == 1) + { + return MultWithElement(mult1, mult2[0]); + } + + int d1 = mult1.Length; + int d2 = mult2.Length; + int[] result = new int[d1 + d2 - 1]; + + if (d2 != d1) + { + int[] res1 = new int[d2]; + int[] res2 = new int[d1 - d2]; + Array.Copy(mult1, 0, res1, 0, res1.Length); + Array.Copy(mult1, d2, res2, 0, res2.Length); + res1 = Multiply(res1, mult2); + res2 = Multiply(res2, mult2); + res2 = MultWithMonomial(res2, d2); + result = Add(res1, res2); + } + else + { + d2 = Utils.UnsignedRightBitShiftInt(d1 + 1, 1); + int d = d1 - d2; + int[] firstPartMult1 = new int[d2]; + int[] firstPartMult2 = new int[d2]; + int[] secondPartMult1 = new int[d]; + int[] secondPartMult2 = new int[d]; + Array.Copy(mult1, 0, firstPartMult1, 0, + firstPartMult1.Length); + Array.Copy(mult1, d2, secondPartMult1, 0, + secondPartMult1.Length); + Array.Copy(mult2, 0, firstPartMult2, 0, + firstPartMult2.Length); + Array.Copy(mult2, d2, secondPartMult2, 0, + secondPartMult2.Length); + int[] helpPoly1 = Add(firstPartMult1, secondPartMult1); + int[] helpPoly2 = Add(firstPartMult2, secondPartMult2); + int[] res1 = Multiply(firstPartMult1, firstPartMult2); + int[] res2 = Multiply(helpPoly1, helpPoly2); + int[] res3 = Multiply(secondPartMult1, secondPartMult2); + res2 = Add(res2, res1); + res2 = Add(res2, res3); + res3 = MultWithMonomial(res3, d2); + result = Add(res2, res3); + result = MultWithMonomial(result, d2); + result = Add(result, res1); + } + + return result; + } + + /* + * ---------------- PART II ---------------- + * + */ + + /** + * Check a polynomial for irreducibility over the field <tt>GF(2^m)</tt>. + * + * @param a the polynomial to check + * @return true if a is irreducible, false otherwise + */ + private bool IsIrreducible(int[] a) + { + if (a[0] == 0) + { + return false; + } + int d = ComputeDegree(a) >> 1; + int[] u = { 0, 1 }; + int[] Y = { 0, 1 }; + int fieldDegree = field.GetDegree(); + for (int i = 0; i < d; i++) + { + for (int j = fieldDegree - 1; j >= 0; j--) + { + u = ModMultiply(u, u, a); + } + u = NormalForm(u); + int[] g = Gcd(Add(u, Y), a); + if (ComputeDegree(g) != 0) + { + return false; + } + } + return true; + } + + /** + * Reduce this polynomial modulo another polynomial. + * + * @param f the reduction polynomial + * @return <tt>this mod f</tt> + */ + public PolynomialGF2mSmallM Mod(PolynomialGF2mSmallM f) + { + int[] resultCoeff = Mod(coefficients, f.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Reduce a polynomial modulo another polynomial. + * + * @param a the polynomial + * @param f the reduction polynomial + * @return <tt>a mod f</tt> + */ + private int[] Mod(int[] a, int[] f) + { + int df = ComputeDegree(f); + if (df == -1) + { + throw new ArithmeticException("Division by zero"); + } + int[] result = new int[a.Length]; + int hc = HeadCoefficient(f); + hc = field.Inverse(hc); + Array.Copy(a, 0, result, 0, result.Length); + while (df <= ComputeDegree(result)) + { + int[] q; + int coeff = field.Mult(HeadCoefficient(result), hc); + q = MultWithMonomial(f, ComputeDegree(result) - df); + q = MultWithElement(q, coeff); + result = Add(q, result); + } + return result; + } + + /** + * Compute the product of this polynomial and another polynomial modulo a + * third polynomial. + * + * @param a another polynomial + * @param b the reduction polynomial + * @return <tt>this * a mod b</tt> + */ + public PolynomialGF2mSmallM ModMultiply(PolynomialGF2mSmallM a, + PolynomialGF2mSmallM b) + { + int[] resultCoeff = ModMultiply(coefficients, a.coefficients, + b.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + + + /** + * Square this polynomial using a squaring matrix. + * + * @param matrix the squaring matrix + * @return <tt>this^2</tt> modulo the reduction polynomial implicitly + * given via the squaring matrix + */ + public PolynomialGF2mSmallM ModSquareMatrix(PolynomialGF2mSmallM[] matrix) + { + + int length = matrix.Length; + + int[] resultCoeff = new int[length]; + int[] thisSquare = new int[length]; + + // square each entry of this polynomial + for (int i = 0; i < coefficients.Length; i++) + { + thisSquare[i] = field.Mult(coefficients[i], coefficients[i]); + } + + // do matrix-vector multiplication + for (int i = 0; i < length; i++) + { + // compute scalar product of i-th row and coefficient vector + for (int j = 0; j < length; j++) + { + if (i >= matrix[j].coefficients.Length) + { + continue; + } + int scalarTerm = field.Mult(matrix[j].coefficients[i], + thisSquare[j]); + resultCoeff[i] = field.add(resultCoeff[i], scalarTerm); + } + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of two polynomials modulo a third polynomial over the + * finite field <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b mod g</tt> + */ + private int[] ModMultiply(int[] a, int[] b, int[] g) + { + return Mod(Multiply(a, b), g); + } + + /** + * Compute the square root of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(1/2) mod a</tt> + */ + public PolynomialGF2mSmallM ModSquareRoot(PolynomialGF2mSmallM a) + { + int[] resultCoeff = IntUtils.Clone(coefficients); + int[] help = ModMultiply(resultCoeff, resultCoeff, a.coefficients); + while (!IsEqual(help, coefficients)) + { + resultCoeff = NormalForm(help); + help = ModMultiply(resultCoeff, resultCoeff, a.coefficients); + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the square root of this polynomial using a square root matrix. + * + * @param matrix the matrix for computing square roots in + * <tt>(GF(2^m))^t</tt> the polynomial ring defining the + * square root matrix + * @return <tt>this^(1/2)</tt> modulo the reduction polynomial implicitly + * given via the square root matrix + */ + public PolynomialGF2mSmallM ModSquareRootMatrix( + PolynomialGF2mSmallM[] matrix) + { + + int length = matrix.Length; + + int[] resultCoeff = new int[length]; + + // do matrix multiplication + for (int i = 0; i < length; i++) + { + // compute scalar product of i-th row and j-th column + for (int j = 0; j < length; j++) + { + if (i >= matrix[j].coefficients.Length) + { + continue; + } + if (j < coefficients.Length) + { + int scalarTerm = field.Mult(matrix[j].coefficients[i], + coefficients[j]); + resultCoeff[i] = field.add(resultCoeff[i], scalarTerm); + } + } + } + + // compute the square root of each entry of the result coefficients + for (int i = 0; i < length; i++) + { + resultCoeff[i] = field.SqRoot(resultCoeff[i]); + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the result of the division of this polynomial by another + * polynomial modulo a third polynomial. + * + * @param divisor the divisor + * @param modulus the reduction polynomial + * @return <tt>this * divisor^(-1) mod modulus</tt> + */ + public PolynomialGF2mSmallM ModDiv(PolynomialGF2mSmallM divisor, + PolynomialGF2mSmallM modulus) + { + int[] resultCoeff = ModDiv(coefficients, divisor.coefficients, + modulus.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the result of the division of two polynomials modulo a third + * polynomial over the field <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b^(-1) mod g</tt> + */ + private int[] ModDiv(int[] a, int[] b, int[] g) + { + int[] r0 = NormalForm(g); + int[] r1 = Mod(b, g); + int[] s0 = { 0 }; + int[] s1 = Mod(a, g); + int[] s2; + int[][] q; + while (ComputeDegree(r1) != -1) + { + q = Div(r0, r1); + r0 = NormalForm(r1); + r1 = NormalForm(q[1]); + s2 = Add(s0, ModMultiply(q[0], s1, g)); + s0 = NormalForm(s1); + s1 = NormalForm(s2); + + } + int hc = HeadCoefficient(r0); + s0 = MultWithElement(s0, field.Inverse(hc)); + return s0; + } + + /** + * Compute the inverse of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(-1) mod a</tt> + */ + public PolynomialGF2mSmallM ModInverse(PolynomialGF2mSmallM a) + { + int[] unit = { 1 }; + int[] resultCoeff = ModDiv(unit, coefficients, a.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute a polynomial pair (a,b) from this polynomial and the given + * polynomial g with the property b*this = a mod g and deg(a)<=deg(g)/2. + * + * @param g the reduction polynomial + * @return PolynomialGF2mSmallM[] {a,b} with b*this = a mod g and deg(a)<= + * deg(g)/2 + */ + public PolynomialGF2mSmallM[] ModPolynomialToFracton(PolynomialGF2mSmallM g) + { + int dg = g.degree >> 1; + int[] a0 = NormalForm(g.coefficients); + int[] a1 = Mod(coefficients, g.coefficients); + int[] b0 = { 0 }; + int[] b1 = { 1 }; + while (ComputeDegree(a1) > dg) + { + int[][] q = Div(a0, a1); + a0 = a1; + a1 = q[1]; + int[] b2 = Add(b0, ModMultiply(q[0], b1, g.coefficients)); + b0 = b1; + b1 = b2; + } + + return new PolynomialGF2mSmallM[]{ + new PolynomialGF2mSmallM(field, a1), + new PolynomialGF2mSmallM(field, b1)}; + } + + /** + * checks if given object is equal to this polynomial. + * <p> + * The method returns false whenever the given object is not polynomial over + * GF(2^m). + * + * @param other object + * @return true or false + */ + public bool equals(Object other) + { + + if (other == null || !(other is PolynomialGF2mSmallM)) + { + return false; + } + + PolynomialGF2mSmallM p = (PolynomialGF2mSmallM)other; + + if ((field.Equals(p.field)) && (degree == p.degree) + && (IsEqual(coefficients, p.coefficients))) + { + return true; + } + + return false; + } + + /** + * Compare two polynomials given as int arrays. + * + * @param a the first polynomial + * @param b the second polynomial + * @return <tt>true</tt> if <tt>a</tt> and <tt>b</tt> represent the + * same polynomials, <tt>false</tt> otherwise + */ + private static bool IsEqual(int[] a, int[] b) + { + int da = ComputeDegree(a); + int db = ComputeDegree(b); + if (da != db) + { + return false; + } + for (int i = 0; i <= da; i++) + { + if (a[i] != b[i]) + { + return false; + } + } + return true; + } + + /** + * @return the hash code of this polynomial + */ + public int HashCode() + { + int hash = field.HashCode(); + for (int j = 0; j < coefficients.Length; j++) + { + hash = hash * 31 + coefficients[j]; + } + return hash; + } + + /** + * Returns a human readable form of the polynomial. + * + * @return a human readable form of the polynomial. + */ + public String toString() + { + String str = " Polynomial over " + field.ToString() + ": \n"; + + for (int i = 0; i < coefficients.Length; i++) + { + str = str + field.ElementToStr(coefficients[i]) + "Y^" + i + "+"; + } + str = str + ";"; + + return str; + } + + /** + * Compute the degree of this polynomial. If this is the zero polynomial, + * the degree is -1. + */ + private void ComputeDegree() + { + for (degree = coefficients.Length - 1; degree >= 0 + && coefficients[degree] == 0; degree--) + { + ; + } + } + + /** + * Compute the degree of a polynomial. + * + * @param a the polynomial + * @return the degree of the polynomial <tt>a</tt>. If <tt>a</tt> is + * the zero polynomial, return -1. + */ + private static int ComputeDegree(int[] a) + { + int degree; + for (degree = a.Length - 1; degree >= 0 && a[degree] == 0; degree--) + { + ; + } + return degree; + } + + /** + * Strip leading zero coefficients from the given polynomial. + * + * @param a the polynomial + * @return the reduced polynomial + */ + private static int[] NormalForm(int[] a) + { + int d = ComputeDegree(a); + + // if a is the zero polynomial + if (d == -1) + { + // return new zero polynomial + return new int[1]; + } + + // if a already is in normal form + if (a.Length == d + 1) + { + // return a clone of a + return IntUtils.Clone(a); + } + + // else, reduce a + int[] result = new int[d + 1]; + Array.Copy(a, 0, result, 0, d + 1); + return result; + } + + /** + * Compute the product of this polynomial and another polynomial modulo a + * third polynomial. + * + * @param a another polynomial + * @param b the reduction polynomial + * @return <tt>this * a mod b</tt> + */ + public PolynomialGF2mSmallM ModKaratsubaMultiplyBigDeg(PolynomialGF2mSmallM a, + PolynomialGF2mSmallM b) + { + int[] resultCoeff = ModKaratsubaMultiplyBigDeg(coefficients, a.coefficients, + b.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the inverse of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(-1) mod a</tt> + */ + public PolynomialGF2mSmallM ModInverseBigDeg(PolynomialGF2mSmallM a) + { + int[] unit = { 1 }; + int[] resultCoeff = ModDivBigDeg(unit, coefficients, a.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + private int[] ModDivBigDeg(int[] a, int[] b, int[] g) + { + int[] r0 = NormalForm(g); + int[] r1 = Mod(b, g); + int[] s0 = { 0 }; + int[] s1 = Mod(a, g); + int[] s2; + int[][] q; + while (ComputeDegree(r1) != -1) + { + q = Div(r0, r1); + r0 = NormalForm(r1); + r1 = NormalForm(q[1]); + s2 = Add(s0, ModKaratsubaMultiplyBigDeg(q[0], s1, g)); + s0 = NormalForm(s1); + s1 = NormalForm(s2); + } + int hc = HeadCoefficient(r0); + s0 = MultWithElement(s0, field.Inverse(hc)); + return s0; + } + + /** + * Compute the product of two polynomials modulo a third polynomial over the + * finite field <tt>GF(2^m)</tt>. + * + * @param aa the first polynomial + * @param bb the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b mod g</tt> + */ + private int[] ModKaratsubaMultiplyBigDeg(int[] aa, int[] bb, int[] g) + { + int[] a, b; + if (aa.Length >= bb.Length) + { + a = Arrays.Clone(aa); + b = Arrays.Clone(bb); + } + else + { + a = Arrays.Clone(bb); + b = Arrays.Clone(aa); + } + + int n = a.Length; + int m = b.Length; + + int[] D = new int[(n + m) / 2]; + int[] S = new int[n + m - 1]; + int[] T = new int[n + m - 1]; + int[] C = new int[n + m - 1]; + + for (int i = 0; i < m; i++) + { + D[i] = a[i] * b[i]; + } + + for (int i = 1; i < n + m - 2; i++) + { + for (int p = 0; p < System.Math.Min(m, i); p++) + { + int q = i - p; + if (p >= q) + { + break; + } + + int ap = a[p]; + int aq = 0; + + if (q < a.Length) + { + aq = a[q]; + } + + int bp = b[p]; + int dp = D[p]; + + if (q < m && p < m) + { + int bq = b[q]; + int dq = D[q]; + + S[i] = S[i] + (ap + aq) * (bp + bq); + T[i] = T[i] + dp + dq; + } + else if (q >= m && q < n) + { + S[i] = S[i] + ((ap + aq) * bp); + T[i] = T[i] + dp; + } + } + } + + for (int i = 0; i < n + m - 1; i++) + { + if (i == 0) + { + C[i] = D[i] % 2; + } + else if (i == n + m - 2) + { + C[i] = (a[a.Length - 1] * b[b.Length - 1]) % 2; + } + else if (i % 2 == 1) + { + C[i] = (S[i] - T[i]) % 2; + } + else + { + C[i] = (S[i] - T[i] + D[i / 2]) % 2; + } + } + int[] res = Mod(C, g); + return res; + } + } +} diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs b/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs new file mode 100644 index 000000000..9bc3fcd31 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs @@ -0,0 +1,286 @@ +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + /** + * This class describes operations with polynomials over finite field GF(2), i e + * polynomial ring R = GF(2)[X]. All operations are defined only for polynomials + * with degree <=32. For the polynomial representation the map f: R->Z, + * poly(X)->poly(2) is used, where integers have the binary representation. For + * example: X^7+X^3+X+1 -> (00...0010001011)=139 Also for polynomials type + * Integer is used. + * + * @see GF2mField + */ + public class PolynomialRingGF2 + { + + /** + * Default constructor (private). + */ + private PolynomialRingGF2() + { + // empty + } + + /** + * Return sum of two polyomials + * + * @param p polynomial + * @param q polynomial + * @return p+q + */ + + public static int Add(int p, int q) + { + return p ^ q; + } + + /** + * Return product of two polynomials + * + * @param p polynomial + * @param q polynomial + * @return p*q + */ + + public static long Multiply(int p, int q) + { + long result = 0; + if (q != 0) + { + long q1 = q & 0x00000000ffffffffL; + + while (p != 0) + { + byte b = (byte)(p & 0x01); + if (b == 1) + { + result ^= q1; + } + p = Utils.UnsignedRightBitShiftInt(p, 1); + q1 <<= 1; + + } + } + return result; + } + + /** + * Compute the product of two polynomials modulo a third polynomial. + * + * @param a the first polynomial + * @param b the second polynomial + * @param r the reduction polynomial + * @return <tt>a * b mod r</tt> + */ + public static int modMultiply(int a, int b, int r) + { + int result = 0; + int p = Remainder(a, r); + int q = Remainder(b, r); + if (q != 0) + { + int d = 1 << Degree(r); + + while (p != 0) + { + byte pMod2 = (byte)(p & 0x01); + if (pMod2 == 1) + { + result ^= q; + } + p = Utils.UnsignedRightBitShiftInt(p, 1); + q <<= 1; + if (q >= d) + { + q ^= r; + } + } + } + return result; + } + + /** + * Return the degree of a polynomial + * + * @param p polynomial p + * @return degree(p) + */ + + public static int Degree(int p) + { + int result = -1; + while (p != 0) + { + result++; + p = Utils.UnsignedRightBitShiftInt(p, 1); + } + return result; + } + + /** + * Return the degree of a polynomial + * + * @param p polynomial p + * @return degree(p) + */ + + public static int Degree(long p) + { + int result = 0; + while (p != 0) + { + result++; + p = Utils.UnsignedRightBitShiftLong(p, 1); + } + return result - 1; + } + + /** + * Return the remainder of a polynomial division of two polynomials. + * + * @param p dividend + * @param q divisor + * @return <tt>p mod q</tt> + */ + public static int Remainder(int p, int q) + { + int result = p; + + if (q == 0) + { + // -DM Console.Error.WriteLine + Console.Error.WriteLine("Error: to be divided by 0"); + return 0; + } + + while (Degree(result) >= Degree(q)) + { + result ^= q << (Degree(result) - Degree(q)); + } + + return result; + } + + /** + * Return the rest of devision two polynomials + * + * @param p polinomial + * @param q polinomial + * @return p mod q + */ + + public static int Rest(long p, int q) + { + long p1 = p; + if (q == 0) + { + // -DM Console.Error.WriteLine + Console.Error.WriteLine("Error: to be divided by 0"); + return 0; + } + long q1 = q & 0x00000000ffffffffL; + + while ((Utils.UnsignedRightBitShiftLong(p1, 32)) != 0) + { + p1 ^= q1 << (Degree(p1) - Degree(q1)); + } + + int result = (int)(p1 & 0xffffffff); + while (Degree(result) >= Degree(q)) + { + result ^= q << (Degree(result) - Degree(q)); + } + + return result; + } + + /** + * Return the greatest common divisor of two polynomials + * + * @param p polinomial + * @param q polinomial + * @return GCD(p, q) + */ + + public static int Gcd(int p, int q) + { + int a, b, c; + a = p; + b = q; + while (b != 0) + { + c = Remainder(a, b); + a = b; + b = c; + + } + return a; + } + + /** + * Checking polynomial for irreducibility + * + * @param p polinomial + * @return true if p is irreducible and false otherwise + */ + + public static bool IsIrreducible(int p) + { + if (p == 0) + { + return false; + } + uint tmpDeg = (uint)Degree(p); + int d = (int) tmpDeg >> 1; + int u = 2; + for (int i = 0; i < d; i++) + { + u = modMultiply(u, u, p); + if (Gcd(u ^ 2, p) != 1) + { + return false; + } + } + return true; + } + + /** + * Creates irreducible polynomial with degree d + * + * @param deg polynomial degree + * @return irreducible polynomial p + */ + public static int GetIrreduciblePolynomial(int deg) + { + if (deg < 0) + { + // -DM Console.Error.WriteLine + Console.Error.WriteLine("The Degree is negative"); + return 0; + } + if (deg > 31) + { + // -DM Console.Error.WriteLine + Console.Error.WriteLine("The Degree is more then 31"); + return 0; + } + if (deg == 0) + { + return 1; + } + int a = 1 << deg; + a++; + int b = 1 << (deg + 1); + for (int i = a; i < b; i += 2) + { + if (IsIrreducible(i)) + { + return i; + } + } + return 0; + } + } +} diff --git a/crypto/src/pqc/math/linearalgebra/RandUtils.cs b/crypto/src/pqc/math/linearalgebra/RandUtils.cs new file mode 100644 index 000000000..f7b7b8588 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/RandUtils.cs @@ -0,0 +1,27 @@ +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + public class RandUtils + { + public static int NextInt(SecureRandom rand, int n) + { + + if ((n & -n) == n) // i.e., n is a power of 2 + { + return (int)((n * (long)(Utils.UnsignedRightBitShiftInt(rand.NextInt(), 1))) >> 31); + } + + int bits, value; + do + { + bits = Utils.UnsignedRightBitShiftInt(rand.NextInt() ,1); + value = bits % n; + } + while (bits - value + (n - 1) < 0); + + return value; + } + } + +} diff --git a/crypto/src/pqc/math/linearalgebra/Utils.cs b/crypto/src/pqc/math/linearalgebra/Utils.cs new file mode 100644 index 000000000..eb2760f82 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Utils.cs @@ -0,0 +1,20 @@ + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + class Utils + { + internal static int UnsignedRightBitShiftInt(int a, int b) + { + uint tmp = (uint) a; + tmp >>= b; + return (int) tmp; + } + + internal static long UnsignedRightBitShiftLong(long a, int b) + { + ulong tmp = (ulong)a; + tmp >>= b; + return (long) tmp; + } + } +} diff --git a/crypto/src/pqc/math/linearalgebra/Vector.cs b/crypto/src/pqc/math/linearalgebra/Vector.cs new file mode 100644 index 000000000..e50c54792 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Vector.cs @@ -0,0 +1,62 @@ +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + /** + * This abstract class defines vectors. It holds the length of vector. + */ + public abstract class Vector + { + + /** + * the length of this vector + */ + protected int length; + + /** + * @return the length of this vector + */ + public int GetLength() + { + return length; + } + + /** + * @return this vector as byte array + */ + public abstract byte[] GetEncoded(); + + /** + * Return whether this is the zero vector (i.e., all elements are zero). + * + * @return <tt>true</tt> if this is the zero vector, <tt>false</tt> + * otherwise + */ + public abstract bool IsZero(); + + /** + * Add another vector to this vector. + * + * @param addend the other vector + * @return <tt>this + addend</tt> + */ + public abstract Vector Add(Vector addend); + + /** + * Multiply this vector with a permutation. + * + * @param p the permutation + * @return <tt>this*p = p*this</tt> + */ + public abstract Vector Multiply(Permutation p); + + /** + * Check if the given object is equal to this vector. + * + * @param other vector + * @return the result of the comparison + */ + public abstract bool Equals(Object other); + + } +} |