diff options
Diffstat (limited to 'crypto/src/pqc')
21 files changed, 2416 insertions, 16 deletions
diff --git a/crypto/src/pqc/crypto/hqc/FastFourierTransform.cs b/crypto/src/pqc/crypto/hqc/FastFourierTransform.cs new file mode 100644 index 000000000..f6e033897 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/FastFourierTransform.cs @@ -0,0 +1,284 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Security.Cryptography; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class FastFourierTransform + { + internal static void FFT(int[] output, int[] elements, int noCoefs, int fft) + { + int m = HqcParameters.PARAM_M; + int mSize = 1 << (HqcParameters.PARAM_M - 1); + + int fftSize = 1 << fft; + + int[] f0 = new int[fftSize]; + int[] f1 = new int[fftSize]; + int[] deltas = new int[m - 1]; + int[] u = new int[mSize]; + int[] v = new int[mSize]; + + // Step 1: Compute betas + int[] betas = new int[m - 1]; + int[] betaSum = new int[mSize]; + + ComputeFFTBetas(betas, m); + ComputeSubsetSum(betaSum, betas, m - 1); + + // Step 2: Compute radix + ComputeRadix(f0, f1, elements, fft, fft); + + // Step 3: Compute deltas + for (int i = 0; i < m - 1; i++) + { + deltas[i] = GFCalculator.mult(betas[i], betas[i]) ^ betas[i]; + } + + // Step 5: + ComputeFFTRec(u, f0, (noCoefs + 1) / 2, m - 1, fft - 1, deltas, fft, m); + ComputeFFTRec(v, f1, noCoefs / 2, m - 1, fft - 1, deltas, fft, m); + + // Step 6.7 + int k = 1; + k = 1 << (m - 1); + + Array.Copy(v, 0, output, k, k); + + output[0] = u[0]; + output[k] ^= u[0]; + + for (int i = 1; i < k; i++) + { + output[i] = u[i] ^ GFCalculator.mult(betaSum[i], v[i]); + output[k + i] ^= output[i]; + } + } + + internal static void ComputeFFTBetas(int[] betas, int m) + { + for (int i = 0; i < m - 1; i++) + { + betas[i] = 1 << (m - 1 - i); + } + } + + internal static void ComputeSubsetSum(int[] subsetSum, int[] set, int size) + { + subsetSum[0] = 0; + + for (int i = 0; i < size; i++) + { + for (int j = 0; j < (1 << i); j++) + { + subsetSum[(1 << i) + j] = set[i] ^ subsetSum[j]; + } + } + } + + internal static void ComputeRadix(int[] f0, int[] f1, int[] f, int mf, int fft) + { + switch (mf) + { + case 4: + f0[4] = f[8] ^ f[12]; + f0[6] = f[12] ^ f[14]; + f0[7] = f[14] ^ f[15]; + f1[5] = f[11] ^ f[13]; + f1[6] = f[13] ^ f[14]; + f1[7] = f[15]; + f0[5] = f[10] ^ f[12] ^ f1[5]; + f1[4] = f[9] ^ f[13] ^ f0[5]; + + f0[0] = f[0]; + f1[3] = f[7] ^ f[11] ^ f[15]; + f0[3] = f[6] ^ f[10] ^ f[14] ^ f1[3]; + f0[2] = f[4] ^ f0[4] ^ f0[3] ^ f1[3]; + f1[1] = f[3] ^ f[5] ^ f[9] ^ f[13] ^ f1[3]; + f1[2] = f[3] ^ f1[1] ^ f0[3]; + f0[1] = f[2] ^ f0[2] ^ f1[1]; + f1[0] = f[1] ^ f0[1]; + return; + + case 3: + f0[0] = f[0]; + f0[2] = f[4] ^ f[6]; + f0[3] = f[6] ^ f[7]; + f1[1] = f[3] ^ f[5] ^ f[7]; + f1[2] = f[5] ^ f[6]; + f1[3] = f[7]; + f0[1] = f[2] ^ f0[2] ^ f1[1]; + f1[0] = f[1] ^ f0[1]; + return; + + case 2: + f0[0] = f[0]; + f0[1] = f[2] ^ f[3]; + f1[0] = f[1] ^ f0[1]; + f1[1] = f[3]; + return; + + case 1: + f0[0] = f[0]; + f1[0] = f[1]; + return; + + default: + ComputeRadixBig(f0, f1, f, mf, fft); + break; + } + } + + internal static void ComputeRadixBig(int[] f0, int[] f1, int[] f, int mf, int fft) + { + int n = 1; + n <<= (mf - 2); + int fftSize = 1 << (fft - 2); + + int[] Q = new int[2 * fftSize]; + int[] R = new int[2 * fftSize]; + + int[] Q0 = new int[fftSize]; + int[] Q1 = new int[fftSize]; + int[] R0 = new int[fftSize]; + int[] R1 = new int[fftSize]; + + + Utils.CopyBytes(f, 3 * n, Q, 0, 2 * n); + Utils.CopyBytes(f, 3 * n, Q, n, 2 * n); + Utils.CopyBytes(f, 0, R, 0, 4 * n); + + for (int i = 0; i < n; ++i) + { + Q[i] ^= f[2 * n + i]; + R[n + i] ^= Q[i]; + } + + ComputeRadix(Q0, Q1, Q, mf - 1, fft); + ComputeRadix(R0, R1, R, mf - 1, fft); + + Utils.CopyBytes(R0, 0, f0, 0, 2 * n); + Utils.CopyBytes(Q0, 0, f0, n, 2 * n); + Utils.CopyBytes(R1, 0, f1, 0, 2 * n); + Utils.CopyBytes(Q1, 0, f1, n, 2 * n); + } + + internal static void ComputeFFTRec(int[] output, int[] func, int noCoeffs, int noOfBetas, int noCoeffsPlus, int[] betaSet, int fft, int m) + { + int fftSize = 1 << (fft - 2); + int mSize = 1 << (m - 2); + + int[] fx0 = new int[fftSize]; + int[] fx1 = new int[fftSize]; + int[] gammaSet = new int[m - 2]; + int[] deltaSet = new int[m - 2]; + int k = 1; + int[] gammaSumSet = new int[mSize]; + int[] uSet = new int[mSize]; + int[] vSet = new int[mSize]; + int[] tempSet = new int[m - fft + 1]; + + int x = 0; + if (noCoeffsPlus == 1) + { + for (int i = 0; i < noOfBetas; i++) + { + tempSet[i] = GFCalculator.mult(betaSet[i], func[1]); + } + + output[0] = func[0]; + x = 1; + for (int j = 0; j < noOfBetas; j++) + { + for (int t = 0; t < x; t++) + { + output[x + t] = output[t] ^ tempSet[j]; + } + x <<= 1; + } + return; + } + + if (betaSet[noOfBetas - 1] != 1) + { + int betaMPow = 1; + x = 1; + x <<= noCoeffsPlus; + for (int i = 1; i < x; i++) + { + betaMPow = GFCalculator.mult(betaMPow, betaSet[noOfBetas - 1]); + func[i] = GFCalculator.mult(betaMPow, func[i]); + } + } + + ComputeRadix(fx0, fx1, func, noCoeffsPlus, fft); + + for (int i = 0; i < noOfBetas - 1; i++) + { + gammaSet[i] = GFCalculator.mult(betaSet[i], GFCalculator.inverse(betaSet[noOfBetas - 1])); + deltaSet[i] = GFCalculator.mult(gammaSet[i], gammaSet[i]) ^ gammaSet[i]; + } + + ComputeSubsetSum(gammaSumSet, gammaSet, noOfBetas - 1); + + ComputeFFTRec(uSet, fx0, (noCoeffs + 1) / 2, noOfBetas - 1, noCoeffsPlus - 1, deltaSet, fft, m); + + k = 1; + k <<= ((noOfBetas - 1) & 0xf); + if (noCoeffs <= 3) + { + output[0] = uSet[0]; + output[k] = uSet[0] ^ fx1[0]; + for (int i = 1; i < k; i++) + { + output[i] = uSet[i] ^ GFCalculator.mult(gammaSumSet[i], fx1[0]); + output[k + i] = output[i] ^ fx1[0]; + } + } + else + { + ComputeFFTRec(vSet, fx1, noCoeffs / 2, noOfBetas - 1, noCoeffsPlus - 1, deltaSet, fft, m); + + Array.Copy(vSet, 0, output, k, k); + + output[0] = uSet[0]; + output[k] ^= uSet[0]; + for (int i = 1; i < k; i++) + { + output[i] = uSet[i] ^ GFCalculator.mult(gammaSumSet[i], vSet[i]); + output[k + i] ^= output[i]; + } + + + } + } + + internal static void FastFourierTransformGetError(byte[] errorSet, int[] input, int mSize, int[] logArrays) + { + int m = HqcParameters.PARAM_M; + int gfMulOrder = HqcParameters.GF_MUL_ORDER; + + int[] gammaSet = new int[m - 1]; + int[] gammaSumSet = new int[mSize]; + int k = mSize; + + ComputeFFTBetas(gammaSet, m); + ComputeSubsetSum(gammaSumSet, gammaSet, m - 1); + + errorSet[0] ^= (byte) (1 ^ Utils.ToUnsigned16Bits(-input[0] >> 15)); + errorSet[0] ^= (byte) (1 ^ Utils.ToUnsigned16Bits(-input[k] >> 15)); + + for (int i = 1; i < k; i++) + { + int tmp = gfMulOrder - logArrays[gammaSumSet[i]]; + errorSet[tmp] ^= (byte) (1 ^ System.Math.Abs(-input[i] >> 15)); + + tmp = gfMulOrder - logArrays[gammaSumSet[i] ^ 1]; + errorSet[tmp] ^= (byte) (1 ^ System.Math.Abs(-input[k + i] >> 15)); + } + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/GF2PolynomialCalculator.cs b/crypto/src/pqc/crypto/hqc/GF2PolynomialCalculator.cs new file mode 100644 index 000000000..0114791e6 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/GF2PolynomialCalculator.cs @@ -0,0 +1,168 @@ +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class GF2PolynomialCalculator + { + static volatile int TABLE = 16; + static volatile int WORD = 64; + static void Mod(ulong[] res, ulong[] a, int n, int nByte64) + { + ulong r; + ulong carry; + for (int i = 0; i < nByte64; i++) + { + r = a[i + nByte64 - 1] >> (n & 0x3F); + carry = a[i + nByte64] << (64 - (n & 0x3F)); + res[i] = a[i] ^ r ^ carry; + } + res[nByte64 - 1] &= (ulong) Utils.BitMask(n, 64); + } + + static void Swap(int[] table, int fisrtIndex, int secIndex) + { + int tmp = table[fisrtIndex]; + table[fisrtIndex] = table[secIndex]; + table[secIndex] = tmp; + } + + static void FastConvolutionMult(ulong[] res, int[] a, long[] b, int weight, int nByte64, int we, HqcKeccakRandomGenerator random) + { + ulong carry; + int dec, s; + ulong[] table = new ulong[TABLE * (nByte64 + 1)]; + int[] permutedTable = new int[TABLE]; + int[] permutationTable = new int[TABLE]; + int[] permutedSparseVect = new int[we]; + int[] permutationSparseVect = new int[we]; + + for (int i = 0; i < 16; i++) + { + permutedTable[i] = i; + } + + byte[] permutationTableByte = new byte[TABLE*2]; + random.ExpandSeed(permutationTableByte, TABLE << 1); + + Utils.FromByteArrayToByte16Array(permutationTable, permutationTableByte); + + for (int i = 0; i < TABLE - 1; i++) + { + Swap(permutedTable, i, i + permutationTable[i] % (TABLE - i)); + } + + //int count = (permutedTable[0] * (nByte64 + 1)); + int idx = permutedTable[0] * (nByte64 + 1); + ulong[] pt = new ulong[nByte64+1]; + + for (int i = 0; i < nByte64; i++) + { + pt[i] = (ulong) b[i]; + } + + pt[nByte64] = 0x0UL; + + Array.Copy(pt, 0, table, idx, pt.Length); + + for (int i = 1; i < TABLE; i++) + { + carry = 0x0UL; + idx = permutedTable[i] * (nByte64 + 1); + ulong[] pt2 = new ulong[nByte64+1]; + + for (int j = 0; j < nByte64; j++) + { + pt2[j] = ((ulong) b[j] << i) ^ carry; + carry = ((ulong) b[j] >> ((WORD - i))); + } + + pt2[nByte64] = carry; + Array.Copy(pt2, 0, table, idx, pt2.Length); + } + + for (int i = 0; i < weight; i++) + { + permutedSparseVect[i] = i; + } + + byte[] permutationSparseVectBytes = new byte[we * 2]; + random.ExpandSeed(permutationSparseVectBytes, weight << 1); + + Utils.FromByteArrayToByte16Array(permutationSparseVect, permutationSparseVectBytes); + + for (int i = 0; i < (weight - 1); i++) + { + Swap(permutedSparseVect, i, i + permutationSparseVect[i] % (weight - i)); + } + + int[] resByte16 = new int[res.Length * 4]; + + for (int i = 0; i < weight; i++) + { + carry = 0x0UL; + dec = a[permutedSparseVect[i]] & 0xf; + s = a[permutedSparseVect[i]] >> 4; + + idx = (permutedTable[dec] * (nByte64 + 1)); + ulong[] pt3 = new ulong[nByte64+1]; + for (int j = 0; j< pt3.Length; j++) + { + pt3[j] = table[j + idx]; + } + int count = s; + for (int j = 0; j < nByte64 + 1; j++) + { + ulong tmp = (ulong) (((ulong) resByte16[count]) | (((ulong) resByte16[count + 1]) << 16) | ((ulong) (resByte16[count + 2]) << 32) | (((ulong)(resByte16[count + 3])) << 48)); + tmp ^= pt3[j]; + AddULongToByte16Array(resByte16, tmp, count); + count += 4; + } + } + Utils.FromByte16ArrayToLongArray(res, resByte16); + } + + internal static void ModMult(ulong[] res, int[] a, long[] b, int weight,int n, int nByte64, int we, HqcKeccakRandomGenerator random) + { + ulong[] tmp = new ulong[(nByte64 << 1) + 1]; + FastConvolutionMult(tmp, a, b, weight, nByte64, we, random); + Mod(res, tmp, n, nByte64); + } + + private static void AddULongToByte16Array(int[] array, ulong t, int startIndex) + { + ulong[] tmp = new ulong[] { t }; + int[] tmpArray = new int[4]; + Utils.FromULongArrayToByte16Array(tmpArray, tmp); + Array.Copy(tmpArray, 0, array, startIndex, tmpArray.Length); + } + + internal static void AddBytes(byte[] res, byte[] a, byte[] b) + { + for (int i = 0; i < a.Length; i++) + { + res[i] =(byte) (a[i] ^ b[i]); + } + } + + internal static void AddLongs(ulong[] res, ulong[] a, long[] b) + { + for (int i = 0; i < a.Length; i++) + { + res[i] = a[i] ^ (ulong) b[i]; + } + } + + internal static void AddULongs(ulong[] res, ulong[] a, ulong[] b) + { + for (int i = 0; i < a.Length; i++) + { + res[i] = a[i] ^ b[i]; + } + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/GFCalculator.cs b/crypto/src/pqc/crypto/hqc/GFCalculator.cs new file mode 100644 index 000000000..22a7b5b2a --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/GFCalculator.cs @@ -0,0 +1,36 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Security.Cryptography; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class GFCalculator + { + static int[] exp = new int[] { 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4 }; + static int[] log = new int[] { 0, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114, 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 175 }; + + internal static int mult(int a, int b) + { + int mask; + mask = Utils.ToUnsigned16Bits(-a >> 31); // a != 0 + mask &= Utils.ToUnsigned16Bits(-b >> 31); // b != 0 + return Utils.ToUnsigned16Bits(mask & exp[mod(log[a] + log[b])]); + } + + internal static int mod(int a) + { + int tmp = Utils.ToUnsigned16Bits(a - HqcParameters.GF_MUL_ORDER); + int mask = Utils.ToUnsigned8bits(-(tmp >> 15)); + return Utils.ToUnsigned16Bits(tmp + (mask & HqcParameters.GF_MUL_ORDER)); + } + + internal static int inverse(int a) + { + int mask = Utils.ToUnsigned16Bits(-a >> 31); + return mask & exp[HqcParameters.GF_MUL_ORDER - log[a]]; + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcEngine.cs b/crypto/src/pqc/crypto/hqc/HqcEngine.cs new file mode 100644 index 000000000..7bc157796 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcEngine.cs @@ -0,0 +1,440 @@ + +using Org.BouncyCastle.Utilities; +using System; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class HqcEngine + { + private int n; + private int n1; + private int n2; + private int k; + private int delta; + private int w; + private int wr; + private int we; + private int g; + private int rejectionThreshold; + private int fft; + private int mulParam; + + private int SEED_SIZE = 40; + private byte G_FCT_DOMAIN = 3; + private byte H_FCT_DOMAIN = 4; + private byte K_FCT_DOMAIN = 5; + + private int N_BYTE; + private int n1n2; + private int N_BYTE_64; + private int K_BYTE; + private int K_BYTE_64; + private int N1_BYTE_64; + private int N1N2_BYTE_64; + private int N1N2_BYTE; + private int N1_BYTE; + + private int[] generatorPoly; + private int SHA512_BYTES = 512 / 8; + + public HqcEngine(int n, int n1, int n2, int k, int g, int delta, int w, int wr, int we, int rejectionThreshold, int fft, int[] generatorPoly) + { + this.n = n; + this.k = k; + this.delta = delta; + this.w = w; + this.wr = wr; + this.we = we; + this.n1 = n1; + this.n2 = n2; + this.n1n2 = n1 * n2; + this.generatorPoly = generatorPoly; + this.g = g; + this.rejectionThreshold = rejectionThreshold; + this.fft = fft; + + this.mulParam = (n2 + 127) / 128; + this.N_BYTE = Utils.GetByteSizeFromBitSize(n); + this.K_BYTE = k; + this.N_BYTE_64 = Utils.GetByte64SizeFromBitSize(n); + this.K_BYTE_64 = Utils.GetByteSizeFromBitSize(k); + this.N1_BYTE_64 = Utils.GetByteSizeFromBitSize(n1); + this.N1N2_BYTE_64 = Utils.GetByte64SizeFromBitSize(n1 * n2); + this.N1N2_BYTE = Utils.GetByteSizeFromBitSize(n1 * n2); + this.N1_BYTE = Utils.GetByteSizeFromBitSize(n1); + } + + /** + * Generate key pairs + * - Secret key : (x,y) + * - Public key: (h,s) + * @param pk output pk = (publicSeed||s) + * + **/ + public void GenKeyPair(byte[] pk, byte[] sk, byte[] seed) + { + // Randomly generate seeds for secret keys and public keys + byte[] secretKeySeed = new byte[SEED_SIZE]; + + HqcKeccakRandomGenerator randomGenerator = new HqcKeccakRandomGenerator(256); + randomGenerator.RandomGeneratorInit(seed, null, seed.Length, 0); + randomGenerator.Squeeze(secretKeySeed, 40); + + // 1. Randomly generate secret keys x, y + HqcKeccakRandomGenerator secretKeySeedExpander = new HqcKeccakRandomGenerator(256); + secretKeySeedExpander.SeedExpanderInit(secretKeySeed, secretKeySeed.Length); + + long[] xLongBytes = new long[N_BYTE_64]; + int[] yPos = new int[this.w]; + + GenerateSecretKey(xLongBytes, secretKeySeedExpander, w); + GenerateSecretKeyByCoordinates(yPos, secretKeySeedExpander, w); + + // 2. Randomly generate h + byte[] publicKeySeed = new byte[SEED_SIZE]; + randomGenerator.Squeeze(publicKeySeed, 40); + + HqcKeccakRandomGenerator randomPublic = new HqcKeccakRandomGenerator(256); + randomPublic.SeedExpanderInit(publicKeySeed, publicKeySeed.Length); + + long[] hLongBytes = new long[N_BYTE_64]; + GeneratePublicKeyH(hLongBytes, randomPublic); + + // 3. Compute s + ulong[] s = new ulong[N_BYTE_64]; + GF2PolynomialCalculator.ModMult(s, yPos, hLongBytes, w, n, N_BYTE_64, we, secretKeySeedExpander); + GF2PolynomialCalculator.AddLongs(s, s, xLongBytes); + byte[] sBytes = new byte[N_BYTE]; + Utils.FromULongArrayToByteArray(sBytes, s); + + byte[] tmpPk = Arrays.Concatenate(publicKeySeed, sBytes); + byte[] tmpSk = Arrays.Concatenate(secretKeySeed, tmpPk); + + Array.Copy(tmpPk, 0, pk, 0, tmpPk.Length); + Array.Copy(tmpSk, 0, sk, 0, tmpSk.Length); + } + + /** + * HQC Encapsulation + * - Input: pk, seed + * - Output: c = (u,v,d), K + * + * @param u u + * @param v v + * @param d d + * @param K session key + * @param pk public key + * @param seed seed + **/ + public void Encaps(byte[] u, byte[] v, byte[] K, byte[] d, byte[] pk, byte[] seed) + { + // 1. Randomly generate m + byte[] m = new byte[K_BYTE]; + + // TODO: no way to gen m without seed and gen skseed, pkseed. In reference implementation they use the same + byte[] secretKeySeed = new byte[SEED_SIZE]; + HqcKeccakRandomGenerator randomGenerator = new HqcKeccakRandomGenerator(256); + randomGenerator.RandomGeneratorInit(seed, null, seed.Length, 0); + randomGenerator.Squeeze(secretKeySeed, 40); + + byte[] publicKeySeed = new byte[SEED_SIZE]; + randomGenerator.Squeeze(publicKeySeed, 40); + + // gen m + randomGenerator.Squeeze(m, K_BYTE); + + // 2. Generate theta + byte[] theta = new byte[SHA512_BYTES]; + HqcKeccakRandomGenerator shakeDigest = new HqcKeccakRandomGenerator(256); + shakeDigest.SHAKE256_512_ds(theta, m, m.Length, new byte[] { G_FCT_DOMAIN }); + + // 3. Generate ciphertext c = (u,v) + // Extract public keys + long[] h = new long[N_BYTE_64]; + byte[] s = new byte[N_BYTE]; + ExtractPublicKeys(h, s, pk); + + long[] vTmp = new long[N1N2_BYTE_64]; + Encrypt(u, vTmp, h, s, m, theta); + Utils.FromLongArrayToByteArray(v, vTmp); + + // 4. Compute d + shakeDigest.SHAKE256_512_ds(d, m, m.Length, new byte[] { H_FCT_DOMAIN }); + + // 5. Compute session key K + byte[] hashInputK = new byte[K_BYTE + N_BYTE + N1N2_BYTE]; + hashInputK = Arrays.Concatenate(m, u); + hashInputK = Arrays.Concatenate(hashInputK, v); + shakeDigest.SHAKE256_512_ds(K, hashInputK, hashInputK.Length, new byte[] { K_FCT_DOMAIN }); + } + + /** + * HQC Decapsulation + * - Input: ct, sk + * - Output: ss + * + * @param ss session key + * @param ct ciphertext + * @param sk secret key + **/ + public void Decaps(byte[] ss, byte[] ct, byte[] sk) + { + //Extract Y and Public Keys from sk + int[] yPos = new int[this.w]; + byte[] pk = new byte[40 + N_BYTE]; + ExtractKeysFromSecretKeys(yPos, pk, sk); + + // Extract u, v, d from ciphertext + byte[] u = new byte[N_BYTE]; + byte[] v = new byte[N1N2_BYTE]; + byte[] d = new byte[SHA512_BYTES]; + HqcEngine.ExtractCiphertexts(u, v, d, ct); + + // 1. Decrypt -> m' + byte[] mPrimeBytes = new byte[k]; + Decrypt(mPrimeBytes, mPrimeBytes, u, v, yPos); + + // 2. Compute theta' + byte[] theta = new byte[SHA512_BYTES]; + HqcKeccakRandomGenerator shakeDigest = new HqcKeccakRandomGenerator(256); + shakeDigest.SHAKE256_512_ds(theta, mPrimeBytes, mPrimeBytes.Length, new byte[] { G_FCT_DOMAIN }); + + // 3. Compute c' = Enc(pk, m', theta') + // Extract public keys + long[] h = new long[N_BYTE_64]; + byte[] s = new byte[N_BYTE]; + ExtractPublicKeys(h, s, pk); + + byte[] u2Bytes = new byte[N_BYTE]; + byte[] v2Bytes = new byte[N1N2_BYTE]; + long[] vTmp = new long[N1N2_BYTE_64]; + Encrypt(u2Bytes, vTmp, h, s, mPrimeBytes, theta); + Utils.FromLongArrayToByteArray(v2Bytes, vTmp); + + // 4. Compute d' = H(m') + byte[] dPrime = new byte[SHA512_BYTES]; + shakeDigest.SHAKE256_512_ds(dPrime, mPrimeBytes, mPrimeBytes.Length, new byte[] { H_FCT_DOMAIN }); + + // 5. Compute session key KPrime + byte[] hashInputK = new byte[K_BYTE + N_BYTE + N1N2_BYTE]; + hashInputK = Arrays.Concatenate(mPrimeBytes, u); + hashInputK = Arrays.Concatenate(hashInputK, v); + shakeDigest.SHAKE256_512_ds(ss, hashInputK, hashInputK.Length, new byte[] { K_FCT_DOMAIN }); + + int result = 1; + // Compare u, v, d + if (!Arrays.AreEqual(u, u2Bytes)) + { + result = 0; + } + + if (!Arrays.AreEqual(v, v2Bytes)) + { + result = 0; + } + + if (!Arrays.AreEqual(d, dPrime)) + { + result = 0; + } + + if (result == 0) + { //abort + for (int i = 0; i < GetSessionKeySize(); i++) + { + ss[i] = 0; + } + } + } + + internal int GetSessionKeySize() + { + return SHA512_BYTES; + } + + /** + * HQC Encryption + * - Input: (h,s, m) + * - Output: (u,v) = c + * + * @param h public key + * @param s public key + * @param m message + * @param u ciphertext + * @param v ciphertext + **/ + private void Encrypt(byte[] u, long[] v, long[] h, byte[] s, byte[] m, byte[] theta) + { + // Randomly generate e, r1, r2 + HqcKeccakRandomGenerator randomGenerator = new HqcKeccakRandomGenerator(256); + randomGenerator.SeedExpanderInit(theta, SEED_SIZE); + long[] e = new long[N_BYTE_64]; + long[] r1 = new long[N_BYTE_64]; + int[] r2 = new int[wr]; + GenerateSecretKey(r1, randomGenerator, wr); + GenerateSecretKeyByCoordinates(r2, randomGenerator, wr); + GenerateSecretKey(e, randomGenerator, we); + + // Calculate u + ulong[] uLong = new ulong[N_BYTE_64]; + GF2PolynomialCalculator.ModMult(uLong, r2, h, wr, n, N_BYTE_64, we, randomGenerator); + GF2PolynomialCalculator.AddLongs(uLong, uLong, r1); + Utils.FromULongArrayToByteArray(u,uLong); + + // Calculate v + // encode m + byte[] res = new byte[n1]; + long[] vLong = new long[N1N2_BYTE_64]; + long[] tmpVLong = new long[N_BYTE_64]; + ReedSolomon.Encode(res, m, K_BYTE * 8, n1, k, g, generatorPoly); + ReedMuller.Encode(vLong, res, n1, mulParam); + Array.Copy(vLong, 0, tmpVLong, 0, vLong.Length); + + + //Compute v + long[] sLong = new long[N_BYTE_64]; + Utils.FromByteArrayToLongArray(sLong, s); + + ulong[] tmpLong = new ulong[N_BYTE_64]; + GF2PolynomialCalculator.ModMult(tmpLong, r2, sLong, wr, n, N_BYTE_64, we, randomGenerator); + GF2PolynomialCalculator.AddLongs(tmpLong, tmpLong, tmpVLong); + GF2PolynomialCalculator.AddLongs(tmpLong, tmpLong, e); + + Utils.ResizeArray(v, n1n2, Utils.FromULongArrayToLongArray(tmpLong), n, N1N2_BYTE_64, N1N2_BYTE_64); + } + + private void Decrypt(byte[] output, byte[] m, byte[] u, byte[] v, int[] y) + { + byte[] tmpSeed = new byte[SEED_SIZE]; + HqcKeccakRandomGenerator randomGenerator = new HqcKeccakRandomGenerator(256); + randomGenerator.SeedExpanderInit(tmpSeed, SEED_SIZE); + + long[] uLongs = new long[N_BYTE_64]; + Utils.FromByteArrayToLongArray(uLongs, u); + + long[] vLongs = new long[N1N2_BYTE_64]; + Utils.FromByteArrayToLongArray(vLongs, v); + + long[] tmpV = new long[N_BYTE_64]; + Array.Copy(vLongs, 0, tmpV, 0, vLongs.Length); + + ulong[] tmpLong = new ulong[N_BYTE_64]; + GF2PolynomialCalculator.ModMult(tmpLong, y, uLongs, w, n, N_BYTE_64, we, randomGenerator); + GF2PolynomialCalculator.AddLongs(tmpLong, tmpLong, tmpV); + + // Decode res + byte[] tmp = new byte[n1]; + ReedMuller.decode(tmp, Utils.FromULongArrayToLongArray(tmpLong), n1, mulParam); + ReedSolomon.decode(m, tmp, n1, fft, delta, k, g); + + Array.Copy(m, 0, output, 0, output.Length); + } + + private void GenerateSecretKey(long[] output, HqcKeccakRandomGenerator random, int w) + { + int[] tmp = new int[w]; + + GenerateSecretKeyByCoordinates(tmp, random, w); + + for (int i = 0; i < w; ++i) + { + int index = tmp[i] / 64; + int pos = tmp[i] % 64; + long t = ((1L) << pos); + output[index] |= t; + } + } + + private void GenerateSecretKeyByCoordinates(int[] output, HqcKeccakRandomGenerator random, int w) + { + int randomByteSize = 3 * w; + byte[] randomBytes = new byte[3 * this.wr]; + int inc; + + int i = 0; + int j = randomByteSize; + while (i < w) + { + do + { + if (j == randomByteSize) + { + random.ExpandSeed(randomBytes, randomByteSize); + + j = 0; + } + + output[i] = (randomBytes[j++] & 0xff) << 16; + output[i] |= (randomBytes[j++] & 0xff) << 8; + output[i] |= (randomBytes[j++] & 0xff); + + } + while (output[i] >= this.rejectionThreshold); + + output[i] = output[i] % this.n; + inc = 1; + for (int k = 0; k < i; k++) + { + if (output[k] == output[i]) + { + inc = 0; + } + } + i += inc; + } + } + + void GeneratePublicKeyH(long[] output, HqcKeccakRandomGenerator random) + { + byte[] randBytes = new byte[N_BYTE]; + random.ExpandSeed(randBytes, N_BYTE); + long[] tmp = new long[N_BYTE_64]; + Utils.FromByteArrayToLongArray(tmp, randBytes); + tmp[N_BYTE_64 - 1] &= Utils.BitMask(n, 64); + Array.Copy(tmp, 0, output, 0, output.Length); + } + + + + private void ExtractPublicKeys(long[] h, byte[] s, byte[] pk) + { + byte[] publicKeySeed = new byte[SEED_SIZE]; + Array.Copy(pk, 0, publicKeySeed, 0, publicKeySeed.Length); + + HqcKeccakRandomGenerator randomPublic = new HqcKeccakRandomGenerator(256); + randomPublic.SeedExpanderInit(publicKeySeed, publicKeySeed.Length); + + long[] hLongBytes = new long[N_BYTE_64]; + GeneratePublicKeyH(hLongBytes, randomPublic); + + Array.Copy(hLongBytes, 0, h, 0, h.Length); + Array.Copy(pk, 40, s, 0, s.Length); + } + + private void ExtractKeysFromSecretKeys(int[] y, byte[] pk, byte[] sk) + { + byte[] secretKeySeed = new byte[SEED_SIZE]; + Array.Copy(sk, 0, secretKeySeed, 0, secretKeySeed.Length); + + // Randomly generate secret keys x, y + HqcKeccakRandomGenerator secretKeySeedExpander = new HqcKeccakRandomGenerator(256); + secretKeySeedExpander.SeedExpanderInit(secretKeySeed, secretKeySeed.Length); + + long[] xLongBytes = new long[N_BYTE_64]; + int[] yPos = new int[this.w]; + + GenerateSecretKey(xLongBytes, secretKeySeedExpander, w); + GenerateSecretKeyByCoordinates(yPos, secretKeySeedExpander, w); + + Array.Copy(yPos, 0, y, 0, yPos.Length); + Array.Copy(sk, SEED_SIZE, pk, 0, pk.Length); + } + + private static void ExtractCiphertexts(byte[] u, byte[] v, byte[] d, byte[] ct) + { + Array.Copy(ct, 0, u, 0, u.Length); + Array.Copy(ct, u.Length, v, 0, v.Length); + Array.Copy(ct, u.Length + v.Length, d, 0, d.Length); + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcKeccakRandomGenerator.cs b/crypto/src/pqc/crypto/hqc/HqcKeccakRandomGenerator.cs new file mode 100644 index 000000000..83e7bf1af --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKeccakRandomGenerator.cs @@ -0,0 +1,343 @@ +using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class HqcKeccakRandomGenerator + { + private static ulong[] KeccakRoundConstants = new ulong[]{0x0000000000000001L, 0x0000000000008082L, + 0x800000000000808aL, 0x8000000080008000L, 0x000000000000808bL, 0x0000000080000001L, 0x8000000080008081L, + 0x8000000000008009L, 0x000000000000008aL, 0x0000000000000088L, 0x0000000080008009L, 0x000000008000000aL, + 0x000000008000808bL, 0x800000000000008bL, 0x8000000000008089L, 0x8000000000008003L, 0x8000000000008002L, + 0x8000000000000080L, 0x000000000000800aL, 0x800000008000000aL, 0x8000000080008081L, 0x8000000000008080L, + 0x0000000080000001L, 0x8000000080008008L}; + + protected long[] state = new long[26]; + protected byte[] dataQueue = new byte[192]; + protected int rate; + protected int bitsInQueue; + protected int fixedOutputLength; + protected bool squeezing; + + public HqcKeccakRandomGenerator() + { + Init(288); + } + + public HqcKeccakRandomGenerator(int bitLength) + { + Init(bitLength); + } + + private void Init(int bitLength) + { + switch (bitLength) + { + case 128: + case 224: + case 256: + case 288: + case 384: + case 512: + InitSponge(1600 - (bitLength << 1)); + break; + default: + throw new ArgumentException("bitLength must be one of 128, 224, 256, 288, 384, or 512."); + } + } + + private void InitSponge(int rate) + { + if ((rate <= 0) || (rate >= 1600) || ((rate % 64) != 0)) + { + throw new InvalidOperationException("invalid rate value"); + } + + this.rate = rate; + for (int i = 0; i < state.Length; ++i) + { + state[i] = 0L; + } + Arrays.Fill(this.dataQueue, (byte)0); + this.bitsInQueue = 0; + this.squeezing = false; + this.fixedOutputLength = (1600 - rate) / 2; + } + private void KeccakPermutation(long[] s) + { + long[] A = state; + + long a00 = A[0], a01 = A[1], a02 = A[2], a03 = A[3], a04 = A[4]; + long a05 = A[5], a06 = A[6], a07 = A[7], a08 = A[8], a09 = A[9]; + long a10 = A[10], a11 = A[11], a12 = A[12], a13 = A[13], a14 = A[14]; + long a15 = A[15], a16 = A[16], a17 = A[17], a18 = A[18], a19 = A[19]; + long a20 = A[20], a21 = A[21], a22 = A[22], a23 = A[23], a24 = A[24]; + + for (int i = 0; i < 24; i++) + { + // theta + long c0 = a00 ^ a05 ^ a10 ^ a15 ^ a20; + long c1 = a01 ^ a06 ^ a11 ^ a16 ^ a21; + long c2 = a02 ^ a07 ^ a12 ^ a17 ^ a22; + long c3 = a03 ^ a08 ^ a13 ^ a18 ^ a23; + long c4 = a04 ^ a09 ^ a14 ^ a19 ^ a24; + + long d1 = (c1 << 1 | Utils.UnsignedRightBitShiftLong(c1, -1)) ^ c4; + long d2 = (c2 << 1 | Utils.UnsignedRightBitShiftLong(c2, -1)) ^ c0; + long d3 = (c3 << 1 | Utils.UnsignedRightBitShiftLong(c3, -1)) ^ c1; + long d4 = (c4 << 1 | Utils.UnsignedRightBitShiftLong(c4, -1)) ^ c2; + long d0 = (c0 << 1 | Utils.UnsignedRightBitShiftLong(c0, -1)) ^ c3; + + a00 ^= d1; + a05 ^= d1; + a10 ^= d1; + a15 ^= d1; + a20 ^= d1; + a01 ^= d2; + a06 ^= d2; + a11 ^= d2; + a16 ^= d2; + a21 ^= d2; + a02 ^= d3; + a07 ^= d3; + a12 ^= d3; + a17 ^= d3; + a22 ^= d3; + a03 ^= d4; + a08 ^= d4; + a13 ^= d4; + a18 ^= d4; + a23 ^= d4; + a04 ^= d0; + a09 ^= d0; + a14 ^= d0; + a19 ^= d0; + a24 ^= d0; + + // rho/pi + c1 = a01 << 1 | Utils.UnsignedRightBitShiftLong(a01, 63); + a01 = a06 << 44 | Utils.UnsignedRightBitShiftLong(a06, 20); + a06 = a09 << 20 | Utils.UnsignedRightBitShiftLong(a09, 44); + a09 = a22 << 61 | Utils.UnsignedRightBitShiftLong(a22, 3); + a22 = a14 << 39 | Utils.UnsignedRightBitShiftLong(a14, 25); + a14 = a20 << 18 | Utils.UnsignedRightBitShiftLong(a20, 46); + a20 = a02 << 62 | Utils.UnsignedRightBitShiftLong(a02, 2); + a02 = a12 << 43 | Utils.UnsignedRightBitShiftLong(a12, 21); + a12 = a13 << 25 | Utils.UnsignedRightBitShiftLong(a13, 39); + a13 = a19 << 8 | Utils.UnsignedRightBitShiftLong(a19, 56); + a19 = a23 << 56 | Utils.UnsignedRightBitShiftLong(a23, 8); + a23 = a15 << 41 | Utils.UnsignedRightBitShiftLong(a15, 23); + a15 = a04 << 27 | Utils.UnsignedRightBitShiftLong(a04, 37); + a04 = a24 << 14 | Utils.UnsignedRightBitShiftLong(a24, 50); + a24 = a21 << 2 | Utils.UnsignedRightBitShiftLong(a21, 62); + a21 = a08 << 55 | Utils.UnsignedRightBitShiftLong(a08, 9); + a08 = a16 << 45 | Utils.UnsignedRightBitShiftLong(a16, 19); + a16 = a05 << 36 | Utils.UnsignedRightBitShiftLong(a05, 28); + a05 = a03 << 28 | Utils.UnsignedRightBitShiftLong(a03, 36); + a03 = a18 << 21 | Utils.UnsignedRightBitShiftLong(a18, 43); + a18 = a17 << 15 | Utils.UnsignedRightBitShiftLong(a17, 49); + a17 = a11 << 10 | Utils.UnsignedRightBitShiftLong(a11, 54); + a11 = a07 << 6 | Utils.UnsignedRightBitShiftLong(a07, 58); + a07 = a10 << 3 | Utils.UnsignedRightBitShiftLong(a10, 61); + a10 = c1; + + // chi + c0 = a00 ^ (~a01 & a02); + c1 = a01 ^ (~a02 & a03); + a02 ^= ~a03 & a04; + a03 ^= ~a04 & a00; + a04 ^= ~a00 & a01; + a00 = c0; + a01 = c1; + + c0 = a05 ^ (~a06 & a07); + c1 = a06 ^ (~a07 & a08); + a07 ^= ~a08 & a09; + a08 ^= ~a09 & a05; + a09 ^= ~a05 & a06; + a05 = c0; + a06 = c1; + + c0 = a10 ^ (~a11 & a12); + c1 = a11 ^ (~a12 & a13); + a12 ^= ~a13 & a14; + a13 ^= ~a14 & a10; + a14 ^= ~a10 & a11; + a10 = c0; + a11 = c1; + + c0 = a15 ^ (~a16 & a17); + c1 = a16 ^ (~a17 & a18); + a17 ^= ~a18 & a19; + a18 ^= ~a19 & a15; + a19 ^= ~a15 & a16; + a15 = c0; + a16 = c1; + + c0 = a20 ^ (~a21 & a22); + c1 = a21 ^ (~a22 & a23); + a22 ^= ~a23 & a24; + a23 ^= ~a24 & a20; + a24 ^= ~a20 & a21; + a20 = c0; + a21 = c1; + + // iota + a00 ^= (long) KeccakRoundConstants[i]; + } + + A[0] = a00; + A[1] = a01; + A[2] = a02; + A[3] = a03; + A[4] = a04; + A[5] = a05; + A[6] = a06; + A[7] = a07; + A[8] = a08; + A[9] = a09; + A[10] = a10; + A[11] = a11; + A[12] = a12; + A[13] = a13; + A[14] = a14; + A[15] = a15; + A[16] = a16; + A[17] = a17; + A[18] = a18; + A[19] = a19; + A[20] = a20; + A[21] = a21; + A[22] = a22; + A[23] = a23; + A[24] = a24; + } + + private void KeccakIncAbsorb(byte[] input, int inputLen) + { + if (input == null) + { + return; + } + + int count = 0; + int rateBytes = rate >> 3; + while (inputLen + state[25] >= rateBytes) + { + for (int i = 0; i < rateBytes - state[25]; i++) + { + int tmp = (int)(state[25] + i) >> 3; + state[tmp] ^= (long) (((ulong) (input[i + count] & 0xff)) << (int) (8 * ((state[25] + i) & 0x07))); + } + inputLen -= (int) (rateBytes - state[25]); + count += (int) (rateBytes - state[25]); + state[25] = 0; + KeccakPermutation(state); + } + + for (int i = 0; i < inputLen; i++) + { + int tmp = (int)(state[25] + i) >> 3; + state[tmp] ^= (long) (((ulong) (input[i + count] & 0xff)) << (int) (8 * ((state[25] + i) & 0x07))); + } + + state[25] += inputLen; + } + + private void KeccakIncFinalize(int p) + { + int rateBytes = rate >> 3; + + state[(int)state[25] >> 3] ^= (long) (((ulong) (p)) << (int) (8 * ((state[25]) & 0x07))); + state[(rateBytes - 1) >> 3] ^=((long) (128)) << (8 * ((rateBytes - 1) & 0x07)); + + + state[25] = 0; + } + + private void KeccakIncSqueeze(byte[] output, int outLen) + { + int rateBytes = rate >> 3; + int i; + for (i = 0; i < outLen && i < state[25]; i++) + { + output[i] = (byte)(state[(int)((rateBytes - state[25] + i) >> 3)] >> (int) (8 * ((rateBytes - state[25] + i) & 0x07))); + } + + int count = i; + outLen -= i; + state[25] -= i; + + while (outLen > 0) + { + KeccakPermutation(state); + + for (i = 0; i < outLen && i < rateBytes; i++) + { + byte t = (byte)(state[i >> 3] >> (8 * (i & 0x07))); + output[count + i] = (byte)(state[i >> 3] >> (8 * (i & 0x07))); + } + count = count + i; + outLen -= i; + state[25] = rateBytes - i; + } + } + + public void Squeeze(byte[] output, int outLen) + { + KeccakIncSqueeze(output, outLen); + } + + public void RandomGeneratorInit(byte[] entropyInput, byte[] personalizationString, int entropyLen, int perLen) + { + byte[] domain = new byte[] { 1 }; + KeccakIncAbsorb(entropyInput, entropyLen); + KeccakIncAbsorb(personalizationString, perLen); + KeccakIncAbsorb(domain, domain.Length); + KeccakIncFinalize(0x1F); + } + + public void SeedExpanderInit(byte[] seed, int seedLen) + { + byte[] domain = new byte[] { 2 }; + KeccakIncAbsorb(seed, seedLen); + KeccakIncAbsorb(domain, 1); + KeccakIncFinalize(0x1F); + } + + public void ExpandSeed(byte[] output, int outLen) + { + int bSize = 8; + int r = outLen % bSize; + byte[] tmp = new byte[bSize]; + KeccakIncSqueeze(output, outLen - r); + + if (r != 0) + { + KeccakIncSqueeze(tmp, bSize); + int count = outLen - r; + for (int i = 0; i < r; i++) + { + output[count + i] = tmp[i]; + } + } + } + + public void SHAKE256_512_ds(byte[] output, byte[] input, int inLen, byte[] domain) + { + for (int i = 0; i < state.Length; i++) + { + state[i] = 0; + } + KeccakIncAbsorb(input, inLen); + KeccakIncAbsorb(domain, domain.Length); + KeccakIncFinalize(0x1F); + KeccakIncSqueeze(output, 512 / 8); + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcKemExtractor.cs b/crypto/src/pqc/crypto/hqc/HqcKemExtractor.cs new file mode 100644 index 000000000..9dfbd2018 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKemExtractor.cs @@ -0,0 +1,36 @@ +using Org.BouncyCastle.Crypto; +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcKemExtractor : IEncapsulatedSecretExtractor + { + private HqcEngine engine; + + private HqcKeyParameters key; + + public HqcKemExtractor(HqcPrivateKeyParameters privParams) + { + this.key = privParams; + InitCipher(key.Parameters); + } + + private void InitCipher(HqcParameters param) + { + engine = param.Engine; + } + + + public byte[] ExtractSecret(byte[] encapsulation) + { + byte[] session_key = new byte[engine.GetSessionKeySize()]; + HqcPrivateKeyParameters secretKey = (HqcPrivateKeyParameters)key; + byte[] sk = secretKey.PrivateKey; + + engine.Decaps(session_key, encapsulation, sk); + + return session_key; + } + + public int EncapsulationLength => key.Parameters.NBytes + key.Parameters.N1n2Bytes + 64; + + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcKemGenerator.cs b/crypto/src/pqc/crypto/hqc/HqcKemGenerator.cs new file mode 100644 index 000000000..30c81ad27 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKemGenerator.cs @@ -0,0 +1,88 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; +using System; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcKemGenerator : IEncapsulatedSecretGenerator + { + private SecureRandom sr; + public HqcKemGenerator(SecureRandom random) + { + this.sr = random; + } + + public ISecretWithEncapsulation GenerateEncapsulated(AsymmetricKeyParameter recipientKey) + { + HqcPublicKeyParameters key = (HqcPublicKeyParameters)recipientKey; + HqcEngine engine = key.Parameters.Engine; + + byte[] K = new byte[key.Parameters.Sha512Bytes]; + byte[] u = new byte[key.Parameters.NBytes]; + byte[] v = new byte[key.Parameters.N1n2Bytes]; + byte[] d = new byte[key.Parameters.Sha512Bytes]; + byte[] pk = key.PublicKey; + byte[] seed = new byte[48]; + + sr.NextBytes(seed); + + engine.Encaps(u, v, K, d, pk, seed); + + byte[] cipherText = Arrays.Concatenate(u, v); + cipherText = Arrays.Concatenate(cipherText, d); + + return new HqcKemGenerator.SecretWithEncapsulationImpl(K, 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/hqc/HqcKeyGenerationParameters.cs b/crypto/src/pqc/crypto/hqc/HqcKeyGenerationParameters.cs new file mode 100644 index 000000000..e548e1999 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKeyGenerationParameters.cs @@ -0,0 +1,19 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcKeyGenerationParameters : KeyGenerationParameters + { + private HqcParameters param; + + public HqcKeyGenerationParameters( + SecureRandom random, + HqcParameters param) : base(random, 256) + { + this.param = param; + } + + public HqcParameters Parameters => param; + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcKeyPairGenerator.cs b/crypto/src/pqc/crypto/hqc/HqcKeyPairGenerator.cs new file mode 100644 index 000000000..243b0d850 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKeyPairGenerator.cs @@ -0,0 +1,69 @@ +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc + +{ + public class HqcKeyPairGenerator : IAsymmetricCipherKeyPairGenerator + { + private int n; + + private int k; + + private int delta; + + private int w; + + private int wr; + + private int we; + private int N_BYTE; + private HqcKeyGenerationParameters hqcKeyGenerationParameters; + + private SecureRandom random; + + public AsymmetricCipherKeyPair GenerateKeyPair() + { + byte[] seed = new byte[48]; + random.NextBytes(seed); + return GenKeyPair(seed); + } + + public AsymmetricCipherKeyPair GenerateKeyPairWithSeed(byte[] seed) + { + return GenKeyPair(seed); + } + + public void Init(KeyGenerationParameters parameters) + { + this.hqcKeyGenerationParameters = (HqcKeyGenerationParameters)parameters; + this.random = parameters.Random; + + // get parameters + this.n = this.hqcKeyGenerationParameters.Parameters.N; + this.k = this.hqcKeyGenerationParameters.Parameters.K; + this.delta = this.hqcKeyGenerationParameters.Parameters.Delta; + this.w = this.hqcKeyGenerationParameters.Parameters.W; + this.wr = this.hqcKeyGenerationParameters.Parameters.Wr; + this.we = this.hqcKeyGenerationParameters.Parameters.We; + this.N_BYTE = (n + 7) / 8; + } + private AsymmetricCipherKeyPair GenKeyPair(byte[] seed) + { + HqcEngine engine = hqcKeyGenerationParameters.Parameters.Engine; + byte[] pk = new byte[40 + N_BYTE]; + byte[] sk = new byte[40 + 40 + N_BYTE]; + + engine.GenKeyPair(pk, sk, seed); + + // form keys + HqcPublicKeyParameters publicKey = new HqcPublicKeyParameters(hqcKeyGenerationParameters.Parameters, pk); + HqcPrivateKeyParameters privateKey = new HqcPrivateKeyParameters(hqcKeyGenerationParameters.Parameters, sk); + + return new AsymmetricCipherKeyPair(publicKey, privateKey); + } + + + + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcKeyParameters.cs b/crypto/src/pqc/crypto/hqc/HqcKeyParameters.cs new file mode 100644 index 000000000..54e42455e --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcKeyParameters.cs @@ -0,0 +1,25 @@ +using Org.BouncyCastle.Crypto; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Security.Cryptography; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcKeyParameters : AsymmetricKeyParameter + { + private HqcParameters param; + + public HqcKeyParameters( + bool isPrivate, + HqcParameters param) : base(isPrivate) + { + this.param = param; + } + + public HqcParameters Parameters => param; + + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcParameters.cs b/crypto/src/pqc/crypto/hqc/HqcParameters.cs new file mode 100644 index 000000000..641e557f0 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcParameters.cs @@ -0,0 +1,71 @@ +using Org.BouncyCastle.Crypto; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc + +{ + public class HqcParameters : ICipherParameters + { + // 128 bits security + public static HqcParameters hqc128 = new HqcParameters("hqc128", 17669, 46, 384, 16, 31, 15, 66, 75, 75, 16767881, 4, new int[] { 89, 69, 153, 116, 176, 117, 111, 75, 73, 233, 242, 233, 65, 210, 21, 139, 103, 173, 67, 118, 105, 210, 174, 110, 74, 69, 228, 82, 255, 181, 1 }, 128); + + // 192 bits security + public static HqcParameters hqc192 = new HqcParameters("hqc192", 35851, 56, 640, 24, 33, 16, 100, 114, 114, 16742417, 5, new int[] { 45, 216, 239, 24, 253, 104, 27, 40, 107, 50, 163, 210, 227, 134, 224, 158, 119, 13, 158, 1, 238, 164, 82, 43, 15, 232, 246, 142, 50, 189, 29, 232, 1 }, 192); + + // 256 bits security + public static HqcParameters hqc256 = new HqcParameters("hqc256", 57637, 90, 640, 32, 59, 29, 131, 149, 149, 16772367, 5, new int[] { 49, 167, 49, 39, 200, 121, 124, 91, 240, 63, 148, 71, 150, 123, 87, 101, 32, 215, 159, 71, 201, 115, 97, 210, 186, 183, 141, 217, 123, 12, 31, 243, 180, 219, 152, 239, 99, 141, 4, 246, 191, 144, 8, 232, 47, 27, 141, 178, 130, 64, 124, 47, 39, 188, 216, 48, 199, 187, 1 }, 256); + + private string name; + private int n; + private int n1; + private int n2; + private int k; + private int g; + private int delta; + private int w; + private int wr; + private int we; + private int utilRejectionThreshold; + private int fft; + + private int[] generatorPoly; + private int defaultKeySize; + + volatile internal static int PARAM_M = 8; + volatile internal static int GF_MUL_ORDER = 255; + + private HqcEngine hqcEngine; + + private HqcParameters(string name, int n, int n1, int n2, int k, int g, int delta, int w, int wr, int we, int utilRejectionThreshold, int fft, int[] generatorPoly, int defaultKeySize) + { + this.name = name; + this.n = n; + this.n1 = n1; + this.n2 = n2; + this.k = k; + this.delta = delta; + this.w = w; + this.wr = wr; + this.we = we; + this.generatorPoly = generatorPoly; + this.g = g; + this.utilRejectionThreshold = utilRejectionThreshold; + this.fft = fft; + this.defaultKeySize = defaultKeySize; + hqcEngine = new HqcEngine(n, n1, n2, k, g, delta, w, wr, we, utilRejectionThreshold, fft, generatorPoly); + } + + public int N => n; + public int K => k; + public int Delta => delta; + public int W => w; + public int Wr => wr; + public int We => we; + public int N1 => n1; + public int N2 => n2; + public int Sha512Bytes => 512 / 8; + public int NBytes => (n + 7) / 8; + public int N1n2Bytes => (n1 * n2 + 7) / 8; + public int DefaultKeySize => defaultKeySize; + internal HqcEngine Engine => hqcEngine; + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcPrivateKeyParameters.cs b/crypto/src/pqc/crypto/hqc/HqcPrivateKeyParameters.cs new file mode 100644 index 000000000..703f778bd --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcPrivateKeyParameters.cs @@ -0,0 +1,21 @@ + +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcPrivateKeyParameters : HqcKeyParameters + { + private byte[] sk; + + public HqcPrivateKeyParameters(HqcParameters param, byte[] sk) : base(true, param) + { + this.sk = Arrays.Clone(sk); + } + + public byte[] PrivateKey => Arrays.Clone(sk); + public byte[] GetEncoded() + { + return PrivateKey; + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/HqcPublicKeyParameters.cs b/crypto/src/pqc/crypto/hqc/HqcPublicKeyParameters.cs new file mode 100644 index 000000000..678e65975 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/HqcPublicKeyParameters.cs @@ -0,0 +1,26 @@ +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + public class HqcPublicKeyParameters : HqcKeyParameters + { + private byte[] pk; + + public HqcPublicKeyParameters(HqcParameters param, byte[] pk) : base(false, param) + { + this.pk = Arrays.Clone(pk); + } + + public byte[] PublicKey => Arrays.Clone(pk); + + public byte[] GetEncoded() + { + return PublicKey; + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/ReedMuller.cs b/crypto/src/pqc/crypto/hqc/ReedMuller.cs new file mode 100644 index 000000000..ac23cf75f --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/ReedMuller.cs @@ -0,0 +1,202 @@ +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class ReedMuller + { + internal class Codeword + { + internal int[] type32; + internal int[] type8; + + public Codeword() + { + this.type32 = new int[4]; + this.type8 = new int[16]; + } + } + + static void EncodeSub(Codeword codeword, int m) + { + + int word1; + word1 = Bit0Mask(m >> 7); + + word1 ^= (int) (Bit0Mask(m >> 0) & 0xaaaaaaaa); + word1 ^= (int) (Bit0Mask(m >> 1) & 0xcccccccc); + word1 ^= (int) (Bit0Mask(m >> 2) & 0xf0f0f0f0); + word1 ^= (int) (Bit0Mask(m >> 3) & 0xff00ff00); + word1 ^= (int) (Bit0Mask(m >> 4) & 0xffff0000); + + codeword.type32[0] = word1; + + word1 ^= Bit0Mask(m >> 5); + codeword.type32[1] = word1; + + word1 ^= Bit0Mask(m >> 6); + codeword.type32[3] = word1; + + word1 ^= Bit0Mask(m >> 5); + codeword.type32[2] = word1; + } + + private static void HadamardTransform(int[] srcCode, int[] desCode) + { + int[] srcCodeCopy = Arrays.Clone(srcCode); + int[] desCodeCopy = Arrays.Clone(desCode); + + for (int i = 0; i < 7; i++) + { + for (int j = 0; j < 64; j++) + { + desCodeCopy[j] = srcCodeCopy[2 * j] + srcCodeCopy[2 * j + 1]; + desCodeCopy[j + 64] = srcCodeCopy[2 * j] - srcCodeCopy[2 * j + 1]; + } + + //swap srcCode and desCode + int[] tmp = Arrays.Clone(srcCodeCopy); + srcCodeCopy = Arrays.Clone(desCodeCopy); + desCodeCopy = Arrays.Clone(tmp); + } + + // swap + Array.Copy(desCodeCopy, 0, srcCode, 0, srcCode.Length); + Array.Copy(srcCodeCopy, 0, desCode, 0, desCode.Length); + } + + + private static void ExpandThenSum(int[] desCode, Codeword[] srcCode, int off, int mulParam) + { + for (int i = 0; i < 4; i++) + { + for (int j = 0; j < 32; j++) + { + long ii = srcCode[0 + off].type32[i] >> j & 1; + desCode[i * 32 + j] = srcCode[0 + off].type32[i] >> j & 1; + } + } + + for (int i = 1; i < mulParam; i++) + { + for (int j = 0; j < 4; j++) + { + for (int k = 0; k < 32; k++) + { + desCode[j * 32 + k] += srcCode[i + off].type32[j] >> k & 1; + + } + } + } + + } + + private static int FindPeaks(int[] input) + { + int peakAbsVal = 0; + int peakVal = 0; + int peakPos = 0; + + for (int i = 0; i < 128; i++) + { + int t = input[i]; + int posMask = t > 0 ? -1 : 0; + int abs = (posMask & t) | (~posMask & -t); + + peakVal = abs > peakAbsVal ? t : peakVal; + peakPos = abs > peakAbsVal ? i : peakPos; + peakAbsVal = abs > peakAbsVal ? abs : peakAbsVal; + } + int tmp = peakVal > 0 ? 1 : 0; + peakPos |= 128 * tmp; + return peakPos; + } + + + private static int Bit0Mask(int b) + { + return (int) ((-(b & 1)) & 0xffffffff); + } + + public static void Encode(long[] codeword, byte[] m, int n1, int mulParam) + { + byte[] mBytes = Arrays.Clone(m); + + Codeword[] codewordCopy = new Codeword[n1 * mulParam]; + for (int i = 0; i < codewordCopy.Length; i++) + { + codewordCopy[i] = new Codeword(); + } + + for (int i = 0; i < n1; i++) + { + int pos = i * mulParam; + EncodeSub(codewordCopy[pos], mBytes[i]); + + for (int j = 1; j < mulParam; j++) + { + codewordCopy[pos + j] = codewordCopy[pos]; + } + } + + + int[] cwd64 = new int[codewordCopy.Length * 4]; + int off = 0; + for (int i = 0; i < codewordCopy.Length; i++) + { + Array.Copy(codewordCopy[i].type32, 0, cwd64, off, codewordCopy[i].type32.Length); + off += 4; + } + + Utils.FromByte32ArrayToLongArray(codeword, cwd64); + } + + + public static void decode(byte[] m, long[] codeword, int n1, int mulParam) + { + byte[] mBytes = Arrays.Clone(m); + + Codeword[] codewordCopy = new Codeword[codeword.Length / 2]; // because each codewordCopy has a 32 bit array size 4 + int[] byteCodeWords = new int[codeword.Length * 2]; + Utils.FromLongArrayToByte32Array(byteCodeWords, codeword); + + for (int i = 0; i < codewordCopy.Length; i++) + { + codewordCopy[i] = new Codeword(); + for (int j = 0; j < 4; j++) + { + codewordCopy[i].type32[j] = byteCodeWords[i * 4 + j]; + } + } + + int[] expandedCodeword = new int[128]; + + + for (int i = 0; i < n1; i++) + { + ExpandThenSum(expandedCodeword, codewordCopy, i * mulParam, mulParam); + + + int[] tmp = new int[128]; + HadamardTransform(expandedCodeword, tmp); + + tmp[0] -= 64 * mulParam; + mBytes[i] = (byte)FindPeaks(tmp); + } + + int[] cwd64 = new int[codewordCopy.Length * 4]; + int off = 0; + for (int i = 0; i < codewordCopy.Length; i++) + { + Array.Copy(codewordCopy[i].type32, 0, cwd64, off, codewordCopy[i].type32.Length); + off += 4; + } + Utils.FromByte32ArrayToLongArray(codeword, cwd64); + Array.Copy(mBytes, 0, m, 0, m.Length); + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/ReedSolomon.cs b/crypto/src/pqc/crypto/hqc/ReedSolomon.cs new file mode 100644 index 000000000..043b5221b --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/ReedSolomon.cs @@ -0,0 +1,268 @@ +using Org.BouncyCastle.Pqc.Crypto.Hqc; +using Org.BouncyCastle.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class ReedSolomon + { + static int[,] alpha128 = new int[30,45] { { 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193 }, { 4, 16, 64, 29, 116, 205, 19, 76, 45, 180, 234, 143, 6, 24, 96, 157, 78, 37, 148, 106, 181, 238, 159, 70, 5, 20, 80, 93, 105, 185, 222, 95, 97, 153, 94, 101, 137, 30, 120, 253, 211, 107, 177, 254, 223 }, { 8, 64, 58, 205, 38, 45, 117, 143, 12, 96, 39, 37, 53, 181, 193, 70, 10, 80, 186, 185, 161, 97, 47, 101, 15, 120, 231, 107, 127, 223, 182, 217, 134, 68, 26, 208, 206, 62, 237, 59, 197, 102, 23, 184, 169 }, { 16, 29, 205, 76, 180, 143, 24, 157, 37, 106, 238, 70, 20, 93, 185, 95, 153, 101, 30, 253, 107, 254, 91, 217, 17, 13, 208, 129, 248, 59, 151, 133, 184, 79, 132, 168, 82, 73, 228, 230, 198, 252, 123, 227, 150 }, { 32, 116, 38, 180, 3, 96, 156, 106, 193, 5, 160, 185, 190, 94, 15, 253, 214, 223, 226, 17, 26, 103, 124, 59, 51, 46, 169, 132, 77, 85, 114, 230, 145, 215, 255, 150, 55, 174, 100, 28, 167, 89, 239, 172, 36 }, { 64, 205, 45, 143, 96, 37, 181, 70, 80, 185, 97, 101, 120, 107, 223, 217, 68, 208, 62, 59, 102, 184, 33, 168, 85, 228, 191, 252, 241, 150, 110, 130, 7, 221, 89, 195, 138, 61, 251, 44, 207, 173, 8, 58, 38 }, { 128, 19, 117, 24, 156, 181, 140, 93, 161, 94, 60, 107, 163, 67, 26, 129, 147, 102, 109, 132, 41, 57, 209, 252, 255, 98, 87, 200, 224, 89, 155, 18, 245, 11, 233, 173, 16, 232, 45, 3, 157, 53, 159, 40, 185 }, { 29, 76, 143, 157, 106, 70, 93, 95, 101, 253, 254, 217, 13, 129, 59, 133, 79, 168, 73, 230, 252, 227, 149, 130, 28, 81, 195, 18, 247, 44, 27, 2, 58, 152, 3, 39, 212, 140, 186, 190, 202, 231, 225, 175, 26 }, { 58, 45, 12, 37, 193, 80, 161, 101, 231, 223, 134, 208, 237, 102, 169, 168, 146, 191, 179, 150, 87, 7, 166, 195, 36, 251, 125, 173, 64, 38, 143, 39, 181, 10, 185, 47, 120, 127, 217, 26, 62, 197, 184, 21, 85 }, { 116, 180, 96, 106, 5, 185, 94, 253, 223, 17, 103, 59, 46, 132, 85, 230, 215, 150, 174, 28, 89, 172, 244, 44, 108, 32, 38, 3, 156, 193, 160, 190, 15, 214, 226, 26, 124, 51, 169, 77, 114, 145, 255, 55, 100 }, { 232, 234, 39, 238, 160, 97, 60, 254, 134, 103, 118, 184, 84, 57, 145, 227, 220, 7, 162, 172, 245, 176, 71, 58, 180, 192, 181, 40, 95, 15, 177, 175, 208, 147, 46, 21, 73, 99, 241, 55, 200, 166, 43, 122, 44 }, { 205, 143, 37, 70, 185, 101, 107, 217, 208, 59, 184, 168, 228, 252, 150, 130, 221, 195, 61, 44, 173, 58, 117, 39, 193, 186, 47, 231, 182, 26, 237, 23, 21, 146, 145, 219, 87, 56, 242, 36, 139, 54, 64, 45, 96 }, { 135, 6, 53, 20, 190, 120, 163, 13, 237, 46, 84, 228, 229, 98, 100, 81, 69, 251, 131, 32, 45, 192, 238, 186, 94, 187, 217, 189, 236, 169, 82, 209, 241, 220, 28, 242, 72, 22, 173, 116, 201, 37, 140, 222, 15 }, { 19, 24, 181, 93, 94, 107, 67, 129, 102, 132, 57, 252, 98, 200, 89, 18, 11, 173, 232, 3, 53, 40, 194, 231, 226, 189, 197, 158, 170, 145, 75, 25, 166, 69, 235, 54, 29, 234, 37, 5, 95, 120, 91, 52, 59 }, { 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145 }, { 76, 157, 70, 95, 253, 217, 129, 133, 168, 230, 227, 130, 81, 18, 44, 2, 152, 39, 140, 190, 231, 175, 31, 23, 77, 209, 219, 25, 162, 36, 88, 4, 45, 78, 5, 97, 211, 67, 62, 46, 154, 191, 171, 50, 89 }, { 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1 }, { 45, 37, 80, 101, 223, 208, 102, 168, 191, 150, 7, 195, 251, 173, 38, 39, 10, 47, 127, 26, 197, 21, 115, 219, 100, 242, 245, 54, 205, 96, 70, 97, 107, 68, 59, 33, 228, 241, 130, 89, 61, 207, 58, 12, 193 }, { 90, 148, 186, 30, 226, 62, 109, 73, 179, 174, 162, 61, 131, 232, 96, 140, 153, 127, 52, 51, 168, 99, 98, 56, 172, 22, 8, 234, 212, 185, 240, 67, 237, 79, 114, 241, 25, 121, 245, 108, 19, 39, 20, 188, 223 }, { 180, 106, 185, 253, 17, 59, 132, 230, 150, 28, 172, 44, 32, 3, 193, 190, 214, 26, 51, 77, 145, 55, 167, 36, 233, 116, 96, 5, 94, 223, 103, 46, 85, 215, 174, 89, 244, 108, 38, 156, 160, 15, 226, 124, 169 }, { 117, 181, 161, 107, 26, 102, 41, 252, 87, 89, 245, 173, 45, 53, 185, 231, 68, 197, 168, 145, 110, 166, 61, 54, 38, 37, 186, 120, 134, 59, 21, 191, 196, 221, 36, 207, 205, 39, 80, 15, 217, 237, 33, 115, 150 }, { 234, 238, 97, 254, 103, 184, 57, 227, 7, 172, 176, 58, 192, 40, 15, 175, 147, 21, 99, 55, 166, 122, 216, 45, 106, 222, 107, 52, 133, 85, 123, 50, 195, 11, 32, 12, 140, 188, 182, 124, 158, 115, 49, 224, 36 }, { 201, 159, 47, 91, 124, 33, 209, 149, 166, 244, 71, 117, 238, 194, 223, 31, 79, 115, 98, 167, 61, 216, 90, 181, 190, 254, 206, 218, 213, 150, 224, 72, 54, 152, 106, 161, 177, 189, 184, 114, 171, 56, 18, 131, 38 }, { 143, 70, 101, 217, 59, 168, 252, 130, 195, 44, 58, 39, 186, 231, 26, 23, 146, 219, 56, 36, 54, 45, 181, 97, 223, 62, 33, 191, 110, 89, 251, 8, 12, 10, 15, 134, 197, 41, 179, 100, 86, 125, 205, 37, 185 }, { 3, 5, 15, 17, 51, 85, 255, 28, 36, 108, 180, 193, 94, 226, 59, 77, 215, 100, 172, 233, 38, 106, 190, 223, 124, 132, 145, 174, 239, 44, 116, 156, 185, 214, 103, 169, 230, 55, 89, 235, 32, 96, 160, 253, 26 }, { 6, 20, 120, 13, 46, 228, 98, 81, 251, 32, 192, 186, 187, 189, 169, 209, 220, 242, 22, 116, 37, 222, 254, 62, 132, 63, 130, 43, 250, 38, 212, 194, 182, 147, 77, 179, 141, 9, 54, 180, 159, 101, 67, 151, 85 }, { 12, 80, 231, 208, 169, 191, 87, 195, 125, 38, 181, 47, 217, 197, 85, 219, 221, 245, 8, 96, 186, 107, 206, 33, 145, 130, 86, 207, 45, 193, 101, 134, 102, 146, 150, 166, 251, 64, 39, 185, 127, 62, 21, 252, 100 }, { 24, 93, 107, 129, 132, 252, 200, 18, 173, 3, 40, 231, 189, 158, 145, 25, 69, 54, 234, 5, 120, 52, 218, 191, 174, 43, 207, 90, 35, 15, 136, 92, 115, 220, 239, 125, 76, 238, 101, 17, 133, 228, 149, 121, 44 }, { 48, 105, 127, 248, 77, 241, 224, 247, 64, 156, 95, 182, 236, 170, 150, 162, 11, 205, 212, 94, 134, 133, 213, 110, 239, 250, 45, 35, 30, 26, 218, 99, 130, 69, 108, 143, 40, 211, 206, 132, 229, 7, 144, 2, 96 }, { 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15 } }; + static int[,] alpha192 = new int[32,55] { { 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160 }, { 4, 16, 64, 29, 116, 205, 19, 76, 45, 180, 234, 143, 6, 24, 96, 157, 78, 37, 148, 106, 181, 238, 159, 70, 5, 20, 80, 93, 105, 185, 222, 95, 97, 153, 94, 101, 137, 30, 120, 253, 211, 107, 177, 254, 223, 91, 113, 217, 67, 17, 68, 13, 52, 208, 103 }, { 8, 64, 58, 205, 38, 45, 117, 143, 12, 96, 39, 37, 53, 181, 193, 70, 10, 80, 186, 185, 161, 97, 47, 101, 15, 120, 231, 107, 127, 223, 182, 217, 134, 68, 26, 208, 206, 62, 237, 59, 197, 102, 23, 184, 169, 33, 21, 168, 41, 85, 146, 228, 115, 191, 145 }, { 16, 29, 205, 76, 180, 143, 24, 157, 37, 106, 238, 70, 20, 93, 185, 95, 153, 101, 30, 253, 107, 254, 91, 217, 17, 13, 208, 129, 248, 59, 151, 133, 184, 79, 132, 168, 82, 73, 228, 230, 198, 252, 123, 227, 150, 149, 165, 130, 200, 28, 221, 81, 121, 195, 172 }, { 32, 116, 38, 180, 3, 96, 156, 106, 193, 5, 160, 185, 190, 94, 15, 253, 214, 223, 226, 17, 26, 103, 124, 59, 51, 46, 169, 132, 77, 85, 114, 230, 145, 215, 255, 150, 55, 174, 100, 28, 167, 89, 239, 172, 36, 244, 235, 44, 233, 108, 1, 32, 116, 38, 180 }, { 64, 205, 45, 143, 96, 37, 181, 70, 80, 185, 97, 101, 120, 107, 223, 217, 68, 208, 62, 59, 102, 184, 33, 168, 85, 228, 191, 252, 241, 150, 110, 130, 7, 221, 89, 195, 138, 61, 251, 44, 207, 173, 8, 58, 38, 117, 12, 39, 53, 193, 10, 186, 161, 47, 15 }, { 128, 19, 117, 24, 156, 181, 140, 93, 161, 94, 60, 107, 163, 67, 26, 129, 147, 102, 109, 132, 41, 57, 209, 252, 255, 98, 87, 200, 224, 89, 155, 18, 245, 11, 233, 173, 16, 232, 45, 3, 157, 53, 159, 40, 185, 194, 137, 231, 254, 226, 68, 189, 248, 197, 46 }, { 29, 76, 143, 157, 106, 70, 93, 95, 101, 253, 254, 217, 13, 129, 59, 133, 79, 168, 73, 230, 252, 227, 149, 130, 28, 81, 195, 18, 247, 44, 27, 2, 58, 152, 3, 39, 212, 140, 186, 190, 202, 231, 225, 175, 26, 31, 118, 23, 158, 77, 146, 209, 229, 219, 55 }, { 58, 45, 12, 37, 193, 80, 161, 101, 231, 223, 134, 208, 237, 102, 169, 168, 146, 191, 179, 150, 87, 7, 166, 195, 36, 251, 125, 173, 64, 38, 143, 39, 181, 10, 185, 47, 120, 127, 217, 26, 62, 197, 184, 21, 85, 115, 252, 219, 110, 100, 221, 242, 138, 245, 44 }, { 116, 180, 96, 106, 5, 185, 94, 253, 223, 17, 103, 59, 46, 132, 85, 230, 215, 150, 174, 28, 89, 172, 244, 44, 108, 32, 38, 3, 156, 193, 160, 190, 15, 214, 226, 26, 124, 51, 169, 77, 114, 145, 255, 55, 100, 167, 239, 36, 235, 233, 1, 116, 180, 96, 106 }, { 232, 234, 39, 238, 160, 97, 60, 254, 134, 103, 118, 184, 84, 57, 145, 227, 220, 7, 162, 172, 245, 176, 71, 58, 180, 192, 181, 40, 95, 15, 177, 175, 208, 147, 46, 21, 73, 99, 241, 55, 200, 166, 43, 122, 44, 216, 128, 45, 48, 106, 10, 222, 202, 107, 226 }, { 205, 143, 37, 70, 185, 101, 107, 217, 208, 59, 184, 168, 228, 252, 150, 130, 221, 195, 61, 44, 173, 58, 117, 39, 193, 186, 47, 231, 182, 26, 237, 23, 21, 146, 145, 219, 87, 56, 242, 36, 139, 54, 64, 45, 96, 181, 80, 97, 120, 223, 68, 62, 102, 33, 85 }, { 135, 6, 53, 20, 190, 120, 163, 13, 237, 46, 84, 228, 229, 98, 100, 81, 69, 251, 131, 32, 45, 192, 238, 186, 94, 187, 217, 189, 236, 169, 82, 209, 241, 220, 28, 242, 72, 22, 173, 116, 201, 37, 140, 222, 15, 254, 34, 62, 204, 132, 146, 63, 75, 130, 167 }, { 19, 24, 181, 93, 94, 107, 67, 129, 102, 132, 57, 252, 98, 200, 89, 18, 11, 173, 232, 3, 53, 40, 194, 231, 226, 189, 197, 158, 170, 145, 75, 25, 166, 69, 235, 54, 29, 234, 37, 5, 95, 120, 91, 52, 59, 218, 82, 191, 227, 174, 221, 43, 247, 207, 32 }, { 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185 }, { 76, 157, 70, 95, 253, 217, 129, 133, 168, 230, 227, 130, 81, 18, 44, 2, 152, 39, 140, 190, 231, 175, 31, 23, 77, 209, 219, 25, 162, 36, 88, 4, 45, 78, 5, 97, 211, 67, 62, 46, 154, 191, 171, 50, 89, 72, 176, 8, 90, 156, 10, 194, 187, 134, 124 }, { 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215 }, { 45, 37, 80, 101, 223, 208, 102, 168, 191, 150, 7, 195, 251, 173, 38, 39, 10, 47, 127, 26, 197, 21, 115, 219, 100, 242, 245, 54, 205, 96, 70, 97, 107, 68, 59, 33, 228, 241, 130, 89, 61, 207, 58, 12, 193, 161, 231, 134, 237, 169, 146, 179, 87, 166, 36 }, { 90, 148, 186, 30, 226, 62, 109, 73, 179, 174, 162, 61, 131, 232, 96, 140, 153, 127, 52, 51, 168, 99, 98, 56, 172, 22, 8, 234, 212, 185, 240, 67, 237, 79, 114, 241, 25, 121, 245, 108, 19, 39, 20, 188, 223, 189, 133, 41, 63, 55, 221, 9, 176, 64, 3 }, { 180, 106, 185, 253, 17, 59, 132, 230, 150, 28, 172, 44, 32, 3, 193, 190, 214, 26, 51, 77, 145, 55, 167, 36, 233, 116, 96, 5, 94, 223, 103, 46, 85, 215, 174, 89, 244, 108, 38, 156, 160, 15, 226, 124, 169, 114, 255, 100, 239, 235, 1, 180, 106, 185, 253 }, { 117, 181, 161, 107, 26, 102, 41, 252, 87, 89, 245, 173, 45, 53, 185, 231, 68, 197, 168, 145, 110, 166, 61, 54, 38, 37, 186, 120, 134, 59, 21, 191, 196, 221, 36, 207, 205, 39, 80, 15, 217, 237, 33, 115, 150, 56, 138, 125, 58, 96, 10, 101, 182, 62, 169 }, { 234, 238, 97, 254, 103, 184, 57, 227, 7, 172, 176, 58, 192, 40, 15, 175, 147, 21, 99, 55, 166, 122, 216, 45, 106, 222, 107, 52, 133, 85, 123, 50, 195, 11, 32, 12, 140, 188, 182, 124, 158, 115, 49, 224, 36, 131, 19, 37, 105, 253, 68, 151, 154, 252, 174 }, { 201, 159, 47, 91, 124, 33, 209, 149, 166, 244, 71, 117, 238, 194, 223, 31, 79, 115, 98, 167, 61, 216, 90, 181, 190, 254, 206, 218, 213, 150, 224, 72, 54, 152, 106, 161, 177, 189, 184, 114, 171, 56, 18, 131, 38, 148, 111, 107, 104, 46, 146, 227, 14, 138, 233 }, { 143, 70, 101, 217, 59, 168, 252, 130, 195, 44, 58, 39, 186, 231, 26, 23, 146, 219, 56, 36, 54, 45, 181, 97, 223, 62, 33, 191, 110, 89, 251, 8, 12, 10, 15, 134, 197, 41, 179, 100, 86, 125, 205, 37, 185, 107, 208, 184, 228, 150, 221, 61, 173, 117, 193 }, { 3, 5, 15, 17, 51, 85, 255, 28, 36, 108, 180, 193, 94, 226, 59, 77, 215, 100, 172, 233, 38, 106, 190, 223, 124, 132, 145, 174, 239, 44, 116, 156, 185, 214, 103, 169, 230, 55, 89, 235, 32, 96, 160, 253, 26, 46, 114, 150, 167, 244, 1, 3, 5, 15, 17 }, { 6, 20, 120, 13, 46, 228, 98, 81, 251, 32, 192, 186, 187, 189, 169, 209, 220, 242, 22, 116, 37, 222, 254, 62, 132, 63, 130, 43, 250, 38, 212, 194, 182, 147, 77, 179, 141, 9, 54, 180, 159, 101, 67, 151, 85, 227, 112, 61, 142, 3, 10, 60, 136, 23, 114 }, { 12, 80, 231, 208, 169, 191, 87, 195, 125, 38, 181, 47, 217, 197, 85, 219, 221, 245, 8, 96, 186, 107, 206, 33, 145, 130, 86, 207, 45, 193, 101, 134, 102, 146, 150, 166, 251, 64, 39, 185, 127, 62, 21, 252, 100, 138, 54, 117, 70, 15, 68, 23, 228, 196, 89 }, { 24, 93, 107, 129, 132, 252, 200, 18, 173, 3, 40, 231, 189, 158, 145, 25, 69, 54, 234, 5, 120, 52, 218, 191, 174, 43, 207, 90, 35, 15, 136, 92, 115, 220, 239, 125, 76, 238, 101, 17, 133, 228, 149, 121, 44, 135, 212, 47, 175, 51, 146, 49, 162, 139, 116 }, { 48, 105, 127, 248, 77, 241, 224, 247, 64, 156, 95, 182, 236, 170, 150, 162, 11, 205, 212, 94, 134, 133, 213, 110, 239, 250, 45, 35, 30, 26, 218, 99, 130, 69, 108, 143, 40, 211, 206, 132, 229, 7, 144, 2, 96, 210, 254, 237, 154, 255, 221, 243, 128, 37, 190 }, { 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59 }, { 192, 222, 182, 151, 114, 110, 155, 27, 143, 160, 177, 237, 82, 75, 89, 88, 152, 70, 240, 103, 21, 123, 224, 251, 116, 212, 101, 136, 218, 145, 200, 144, 8, 78, 190, 217, 204, 183, 87, 172, 216, 12, 105, 225, 59, 170, 98, 242, 250, 180, 10, 211, 31, 168, 255 }, { 157, 95, 217, 133, 230, 130, 18, 2, 39, 190, 175, 23, 209, 25, 36, 4, 78, 97, 67, 46, 191, 50, 72, 8, 156, 194, 134, 92, 99, 100, 144, 16, 37, 153, 17, 184, 198, 200, 61, 32, 74, 47, 34, 109, 145, 141, 122, 64, 148, 94, 68, 218, 63, 7, 244 } }; + static int[,] alpha256 = new int[58,89] { { 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225 }, { 4, 16, 64, 29, 116, 205, 19, 76, 45, 180, 234, 143, 6, 24, 96, 157, 78, 37, 148, 106, 181, 238, 159, 70, 5, 20, 80, 93, 105, 185, 222, 95, 97, 153, 94, 101, 137, 30, 120, 253, 211, 107, 177, 254, 223, 91, 113, 217, 67, 17, 68, 13, 52, 208, 103, 129, 62, 248, 199, 59, 236, 151, 102, 133, 46, 184, 218, 79, 33, 132, 42, 168, 154, 82, 85, 73, 57, 228, 183, 230, 191, 198, 63, 252, 215, 123, 241, 227, 171 }, { 8, 64, 58, 205, 38, 45, 117, 143, 12, 96, 39, 37, 53, 181, 193, 70, 10, 80, 186, 185, 161, 97, 47, 101, 15, 120, 231, 107, 127, 223, 182, 217, 134, 68, 26, 208, 206, 62, 237, 59, 197, 102, 23, 184, 169, 33, 21, 168, 41, 85, 146, 228, 115, 191, 145, 252, 179, 241, 219, 150, 196, 110, 87, 130, 100, 7, 56, 221, 166, 89, 242, 195, 86, 138, 36, 61, 245, 251, 139, 44, 125, 207, 54, 173, 1, 8, 64, 58, 205 }, { 16, 29, 205, 76, 180, 143, 24, 157, 37, 106, 238, 70, 20, 93, 185, 95, 153, 101, 30, 253, 107, 254, 91, 217, 17, 13, 208, 129, 248, 59, 151, 133, 184, 79, 132, 168, 82, 73, 228, 230, 198, 252, 123, 227, 150, 149, 165, 130, 200, 28, 221, 81, 121, 195, 172, 18, 61, 247, 203, 44, 250, 27, 173, 2, 32, 58, 135, 152, 117, 3, 48, 39, 74, 212, 193, 140, 40, 186, 111, 190, 47, 202, 60, 231, 214, 225, 182, 175, 34 }, { 32, 116, 38, 180, 3, 96, 156, 106, 193, 5, 160, 185, 190, 94, 15, 253, 214, 223, 226, 17, 26, 103, 124, 59, 51, 46, 169, 132, 77, 85, 114, 230, 145, 215, 255, 150, 55, 174, 100, 28, 167, 89, 239, 172, 36, 244, 235, 44, 233, 108, 1, 32, 116, 38, 180, 3, 96, 156, 106, 193, 5, 160, 185, 190, 94, 15, 253, 214, 223, 226, 17, 26, 103, 124, 59, 51, 46, 169, 132, 77, 85, 114, 230, 145, 215, 255, 150, 55, 174 }, { 64, 205, 45, 143, 96, 37, 181, 70, 80, 185, 97, 101, 120, 107, 223, 217, 68, 208, 62, 59, 102, 184, 33, 168, 85, 228, 191, 252, 241, 150, 110, 130, 7, 221, 89, 195, 138, 61, 251, 44, 207, 173, 8, 58, 38, 117, 12, 39, 53, 193, 10, 186, 161, 47, 15, 231, 127, 182, 134, 26, 206, 237, 197, 23, 169, 21, 41, 146, 115, 145, 179, 219, 196, 87, 100, 56, 166, 242, 86, 36, 245, 139, 125, 54, 1, 64, 205, 45, 143 }, { 128, 19, 117, 24, 156, 181, 140, 93, 161, 94, 60, 107, 163, 67, 26, 129, 147, 102, 109, 132, 41, 57, 209, 252, 255, 98, 87, 200, 224, 89, 155, 18, 245, 11, 233, 173, 16, 232, 45, 3, 157, 53, 159, 40, 185, 194, 137, 231, 254, 226, 68, 189, 248, 197, 46, 158, 168, 170, 183, 145, 123, 75, 110, 25, 28, 166, 249, 69, 61, 235, 176, 54, 2, 29, 38, 234, 48, 37, 119, 5, 186, 95, 188, 120, 214, 91, 134, 52, 31 }, { 29, 76, 143, 157, 106, 70, 93, 95, 101, 253, 254, 217, 13, 129, 59, 133, 79, 168, 73, 230, 252, 227, 149, 130, 28, 81, 195, 18, 247, 44, 27, 2, 58, 152, 3, 39, 212, 140, 186, 190, 202, 231, 225, 175, 26, 31, 118, 23, 158, 77, 146, 209, 229, 219, 55, 25, 56, 162, 155, 36, 243, 88, 54, 4, 116, 45, 6, 78, 181, 5, 105, 97, 137, 211, 223, 67, 52, 62, 236, 46, 33, 154, 57, 191, 215, 171, 110, 50, 112 }, { 58, 45, 12, 37, 193, 80, 161, 101, 231, 223, 134, 208, 237, 102, 169, 168, 146, 191, 179, 150, 87, 7, 166, 195, 36, 251, 125, 173, 64, 38, 143, 39, 181, 10, 185, 47, 120, 127, 217, 26, 62, 197, 184, 21, 85, 115, 252, 219, 110, 100, 221, 242, 138, 245, 44, 54, 8, 205, 117, 96, 53, 70, 186, 97, 15, 107, 182, 68, 206, 59, 23, 33, 41, 228, 145, 241, 196, 130, 56, 89, 86, 61, 139, 207, 1, 58, 45, 12, 37 }, { 116, 180, 96, 106, 5, 185, 94, 253, 223, 17, 103, 59, 46, 132, 85, 230, 215, 150, 174, 28, 89, 172, 244, 44, 108, 32, 38, 3, 156, 193, 160, 190, 15, 214, 226, 26, 124, 51, 169, 77, 114, 145, 255, 55, 100, 167, 239, 36, 235, 233, 1, 116, 180, 96, 106, 5, 185, 94, 253, 223, 17, 103, 59, 46, 132, 85, 230, 215, 150, 174, 28, 89, 172, 244, 44, 108, 32, 38, 3, 156, 193, 160, 190, 15, 214, 226, 26, 124, 51 }, { 232, 234, 39, 238, 160, 97, 60, 254, 134, 103, 118, 184, 84, 57, 145, 227, 220, 7, 162, 172, 245, 176, 71, 58, 180, 192, 181, 40, 95, 15, 177, 175, 208, 147, 46, 21, 73, 99, 241, 55, 200, 166, 43, 122, 44, 216, 128, 45, 48, 106, 10, 222, 202, 107, 226, 52, 237, 133, 66, 85, 209, 123, 196, 50, 167, 195, 144, 11, 54, 32, 76, 12, 148, 140, 185, 188, 211, 182, 13, 124, 102, 158, 82, 115, 215, 49, 130, 224, 249 }, { 205, 143, 37, 70, 185, 101, 107, 217, 208, 59, 184, 168, 228, 252, 150, 130, 221, 195, 61, 44, 173, 58, 117, 39, 193, 186, 47, 231, 182, 26, 237, 23, 21, 146, 145, 219, 87, 56, 242, 36, 139, 54, 64, 45, 96, 181, 80, 97, 120, 223, 68, 62, 102, 33, 85, 191, 241, 110, 7, 89, 138, 251, 207, 8, 38, 12, 53, 10, 161, 15, 127, 134, 206, 197, 169, 41, 115, 179, 196, 100, 166, 86, 245, 125, 1, 205, 143, 37, 70 }, { 135, 6, 53, 20, 190, 120, 163, 13, 237, 46, 84, 228, 229, 98, 100, 81, 69, 251, 131, 32, 45, 192, 238, 186, 94, 187, 217, 189, 236, 169, 82, 209, 241, 220, 28, 242, 72, 22, 173, 116, 201, 37, 140, 222, 15, 254, 34, 62, 204, 132, 146, 63, 75, 130, 167, 43, 245, 250, 4, 38, 24, 212, 80, 194, 253, 182, 52, 147, 184, 77, 183, 179, 149, 141, 89, 9, 203, 54, 128, 180, 39, 159, 210, 101, 214, 67, 206, 151, 158 }, { 19, 24, 181, 93, 94, 107, 67, 129, 102, 132, 57, 252, 98, 200, 89, 18, 11, 173, 232, 3, 53, 40, 194, 231, 226, 189, 197, 158, 170, 145, 75, 25, 166, 69, 235, 54, 29, 234, 37, 5, 95, 120, 91, 52, 59, 218, 82, 191, 227, 174, 221, 43, 247, 207, 32, 90, 39, 35, 111, 15, 225, 136, 237, 92, 77, 115, 246, 220, 56, 239, 122, 125, 4, 76, 96, 238, 105, 101, 177, 17, 62, 133, 42, 228, 215, 149, 7, 121, 72 }, { 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185, 15, 223, 26, 59, 169, 85, 145, 150, 100, 89, 36, 44, 1, 38, 96, 193, 185 }, { 76, 157, 70, 95, 253, 217, 129, 133, 168, 230, 227, 130, 81, 18, 44, 2, 152, 39, 140, 190, 231, 175, 31, 23, 77, 209, 219, 25, 162, 36, 88, 4, 45, 78, 5, 97, 211, 67, 62, 46, 154, 191, 171, 50, 89, 72, 176, 8, 90, 156, 10, 194, 187, 134, 124, 92, 41, 99, 75, 100, 178, 144, 125, 16, 180, 37, 20, 153, 107, 17, 248, 184, 82, 198, 150, 200, 121, 61, 250, 32, 117, 74, 40, 47, 214, 34, 237, 109, 164 }, { 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11, 1, 152, 78, 10, 153, 214, 68, 147, 79, 146, 215, 220, 221, 69, 11 }, { 45, 37, 80, 101, 223, 208, 102, 168, 191, 150, 7, 195, 251, 173, 38, 39, 10, 47, 127, 26, 197, 21, 115, 219, 100, 242, 245, 54, 205, 96, 70, 97, 107, 68, 59, 33, 228, 241, 130, 89, 61, 207, 58, 12, 193, 161, 231, 134, 237, 169, 146, 179, 87, 166, 36, 125, 64, 143, 181, 185, 120, 217, 62, 184, 85, 252, 110, 221, 138, 44, 8, 117, 53, 186, 15, 182, 206, 23, 41, 145, 196, 56, 86, 139, 1, 45, 37, 80, 101 }, { 90, 148, 186, 30, 226, 62, 109, 73, 179, 174, 162, 61, 131, 232, 96, 140, 153, 127, 52, 51, 168, 99, 98, 56, 172, 22, 8, 234, 212, 185, 240, 67, 237, 79, 114, 241, 25, 121, 245, 108, 19, 39, 20, 188, 223, 189, 133, 41, 63, 55, 221, 9, 176, 64, 3, 238, 161, 211, 34, 59, 66, 183, 219, 200, 239, 251, 71, 152, 37, 160, 137, 182, 129, 92, 85, 229, 165, 166, 72, 233, 58, 24, 35, 97, 214, 13, 197, 42, 209 }, { 180, 106, 185, 253, 17, 59, 132, 230, 150, 28, 172, 44, 32, 3, 193, 190, 214, 26, 51, 77, 145, 55, 167, 36, 233, 116, 96, 5, 94, 223, 103, 46, 85, 215, 174, 89, 244, 108, 38, 156, 160, 15, 226, 124, 169, 114, 255, 100, 239, 235, 1, 180, 106, 185, 253, 17, 59, 132, 230, 150, 28, 172, 44, 32, 3, 193, 190, 214, 26, 51, 77, 145, 55, 167, 36, 233, 116, 96, 5, 94, 223, 103, 46, 85, 215, 174, 89, 244, 108 }, { 117, 181, 161, 107, 26, 102, 41, 252, 87, 89, 245, 173, 45, 53, 185, 231, 68, 197, 168, 145, 110, 166, 61, 54, 38, 37, 186, 120, 134, 59, 21, 191, 196, 221, 36, 207, 205, 39, 80, 15, 217, 237, 33, 115, 150, 56, 138, 125, 58, 96, 10, 101, 182, 62, 169, 228, 219, 7, 86, 44, 64, 12, 70, 47, 223, 206, 184, 146, 241, 100, 195, 139, 8, 143, 193, 97, 127, 208, 23, 85, 179, 130, 242, 251, 1, 117, 181, 161, 107 }, { 234, 238, 97, 254, 103, 184, 57, 227, 7, 172, 176, 58, 192, 40, 15, 175, 147, 21, 99, 55, 166, 122, 216, 45, 106, 222, 107, 52, 133, 85, 123, 50, 195, 11, 32, 12, 140, 188, 182, 124, 158, 115, 49, 224, 36, 131, 19, 37, 105, 253, 68, 151, 154, 252, 174, 121, 251, 2, 201, 193, 194, 225, 206, 109, 114, 219, 14, 69, 125, 116, 157, 80, 30, 67, 59, 42, 198, 110, 81, 244, 173, 90, 212, 161, 214, 104, 23, 170, 246 }, { 201, 159, 47, 91, 124, 33, 209, 149, 166, 244, 71, 117, 238, 194, 223, 31, 79, 115, 98, 167, 61, 216, 90, 181, 190, 254, 206, 218, 213, 150, 224, 72, 54, 152, 106, 161, 177, 189, 184, 114, 171, 56, 18, 131, 38, 148, 111, 107, 104, 46, 146, 227, 14, 138, 233, 135, 37, 210, 211, 26, 133, 170, 241, 141, 172, 125, 232, 78, 186, 253, 136, 102, 164, 123, 100, 43, 88, 58, 157, 160, 120, 34, 151, 41, 215, 25, 195, 22, 128 }, { 143, 70, 101, 217, 59, 168, 252, 130, 195, 44, 58, 39, 186, 231, 26, 23, 146, 219, 56, 36, 54, 45, 181, 97, 223, 62, 33, 191, 110, 89, 251, 8, 12, 10, 15, 134, 197, 41, 179, 100, 86, 125, 205, 37, 185, 107, 208, 184, 228, 150, 221, 61, 173, 117, 193, 47, 182, 237, 21, 145, 87, 242, 139, 64, 96, 80, 120, 68, 102, 85, 241, 7, 138, 207, 38, 53, 161, 127, 206, 169, 115, 196, 166, 245, 1, 143, 70, 101, 217 }, { 3, 5, 15, 17, 51, 85, 255, 28, 36, 108, 180, 193, 94, 226, 59, 77, 215, 100, 172, 233, 38, 106, 190, 223, 124, 132, 145, 174, 239, 44, 116, 156, 185, 214, 103, 169, 230, 55, 89, 235, 32, 96, 160, 253, 26, 46, 114, 150, 167, 244, 1, 3, 5, 15, 17, 51, 85, 255, 28, 36, 108, 180, 193, 94, 226, 59, 77, 215, 100, 172, 233, 38, 106, 190, 223, 124, 132, 145, 174, 239, 44, 116, 156, 185, 214, 103, 169, 230, 55 }, { 6, 20, 120, 13, 46, 228, 98, 81, 251, 32, 192, 186, 187, 189, 169, 209, 220, 242, 22, 116, 37, 222, 254, 62, 132, 63, 130, 43, 250, 38, 212, 194, 182, 147, 77, 179, 141, 9, 54, 180, 159, 101, 67, 151, 85, 227, 112, 61, 142, 3, 10, 60, 136, 23, 114, 49, 166, 243, 16, 96, 93, 211, 208, 218, 230, 110, 121, 11, 58, 156, 111, 127, 31, 66, 145, 65, 155, 125, 19, 106, 97, 91, 199, 168, 215, 200, 138, 27, 90 }, { 12, 80, 231, 208, 169, 191, 87, 195, 125, 38, 181, 47, 217, 197, 85, 219, 221, 245, 8, 96, 186, 107, 206, 33, 145, 130, 86, 207, 45, 193, 101, 134, 102, 146, 150, 166, 251, 64, 39, 185, 127, 62, 21, 252, 100, 138, 54, 117, 70, 15, 68, 23, 228, 196, 89, 139, 58, 37, 161, 223, 237, 168, 179, 7, 36, 173, 143, 10, 120, 26, 184, 115, 110, 242, 44, 205, 53, 97, 182, 59, 41, 241, 56, 61, 1, 12, 80, 231, 208 }, { 24, 93, 107, 129, 132, 252, 200, 18, 173, 3, 40, 231, 189, 158, 145, 25, 69, 54, 234, 5, 120, 52, 218, 191, 174, 43, 207, 90, 35, 15, 136, 92, 115, 220, 239, 125, 76, 238, 101, 17, 133, 228, 149, 121, 44, 135, 212, 47, 175, 51, 146, 49, 162, 139, 116, 148, 97, 113, 236, 85, 171, 83, 251, 128, 156, 161, 163, 147, 41, 255, 224, 245, 16, 157, 185, 254, 248, 168, 123, 28, 61, 2, 48, 186, 214, 31, 21, 229, 141 }, { 48, 105, 127, 248, 77, 241, 224, 247, 64, 156, 95, 182, 236, 170, 150, 162, 11, 205, 212, 94, 134, 133, 213, 110, 239, 250, 45, 35, 30, 26, 218, 99, 130, 69, 108, 143, 40, 211, 206, 132, 229, 7, 144, 2, 96, 210, 254, 237, 154, 255, 221, 243, 128, 37, 190, 113, 197, 73, 49, 89, 22, 135, 181, 188, 17, 23, 183, 220, 195, 233, 90, 70, 60, 52, 169, 198, 25, 138, 216, 3, 80, 187, 129, 21, 215, 14, 61, 4, 192 }, { 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59, 85, 150, 89, 44, 38, 193, 15, 26, 169, 145, 100, 36, 1, 96, 185, 223, 59 }, { 192, 222, 182, 151, 114, 110, 155, 27, 143, 160, 177, 237, 82, 75, 89, 88, 152, 70, 240, 103, 21, 123, 224, 251, 116, 212, 101, 136, 218, 145, 200, 144, 8, 78, 190, 217, 204, 183, 87, 172, 216, 12, 105, 225, 59, 170, 98, 242, 250, 180, 10, 211, 31, 168, 255, 83, 139, 135, 238, 15, 52, 158, 252, 14, 244, 64, 74, 153, 134, 46, 209, 130, 9, 142, 96, 111, 91, 197, 57, 55, 195, 131, 201, 80, 214, 248, 41, 171, 162 }, { 157, 95, 217, 133, 230, 130, 18, 2, 39, 190, 175, 23, 209, 25, 36, 4, 78, 97, 67, 46, 191, 50, 72, 8, 156, 194, 134, 92, 99, 100, 144, 16, 37, 153, 17, 184, 198, 200, 61, 32, 74, 47, 34, 109, 145, 141, 122, 64, 148, 94, 68, 218, 63, 7, 244, 128, 53, 188, 136, 169, 126, 14, 245, 29, 106, 101, 13, 79, 252, 28, 247, 58, 212, 202, 26, 158, 229, 56, 243, 116, 181, 137, 52, 33, 215, 112, 251, 232, 119 }, { 39, 97, 134, 184, 145, 7, 245, 58, 181, 15, 208, 21, 241, 166, 44, 45, 10, 107, 237, 85, 196, 195, 54, 12, 185, 182, 102, 115, 130, 36, 8, 37, 47, 68, 169, 252, 56, 251, 205, 193, 120, 206, 168, 219, 89, 125, 117, 80, 127, 59, 146, 110, 86, 173, 96, 161, 217, 23, 191, 100, 61, 64, 53, 101, 26, 33, 179, 221, 139, 38, 70, 231, 62, 41, 150, 242, 207, 143, 186, 223, 197, 228, 87, 138, 1, 39, 97, 134, 184 }, { 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69, 1, 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69, 1, 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69, 1, 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69, 1, 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69, 1, 78, 153, 68, 79, 215, 221, 11, 152, 10, 214, 147, 146, 220, 69 }, { 156, 94, 26, 132, 255, 89, 233, 3, 185, 226, 46, 145, 28, 235, 38, 5, 214, 59, 114, 174, 36, 32, 106, 15, 103, 77, 150, 239, 108, 96, 190, 17, 169, 215, 167, 44, 180, 160, 223, 51, 230, 100, 244, 116, 193, 253, 124, 85, 55, 172, 1, 156, 94, 26, 132, 255, 89, 233, 3, 185, 226, 46, 145, 28, 235, 38, 5, 214, 59, 114, 174, 36, 32, 106, 15, 103, 77, 150, 239, 108, 96, 190, 17, 169, 215, 167, 44, 180, 160 }, { 37, 101, 208, 168, 150, 195, 173, 39, 47, 26, 21, 219, 242, 54, 96, 97, 68, 33, 241, 89, 207, 12, 161, 134, 169, 179, 166, 125, 143, 185, 217, 184, 252, 221, 44, 117, 186, 182, 23, 145, 56, 139, 45, 80, 223, 102, 191, 7, 251, 38, 10, 127, 197, 115, 100, 245, 205, 70, 107, 59, 228, 130, 61, 58, 193, 231, 237, 146, 87, 36, 64, 181, 120, 62, 85, 110, 138, 8, 53, 15, 206, 41, 196, 86, 1, 37, 101, 208, 168 }, { 74, 137, 206, 82, 55, 138, 16, 212, 120, 124, 73, 87, 72, 29, 193, 211, 147, 228, 25, 244, 205, 140, 177, 197, 230, 141, 251, 76, 40, 223, 204, 198, 56, 11, 180, 186, 113, 92, 252, 167, 176, 143, 111, 67, 169, 123, 162, 207, 24, 190, 68, 66, 227, 242, 108, 157, 47, 52, 84, 150, 155, 142, 37, 202, 103, 41, 149, 69, 8, 106, 60, 62, 170, 165, 36, 128, 238, 231, 199, 114, 130, 122, 232, 70, 214, 236, 115, 200, 243 }, { 148, 30, 62, 73, 174, 61, 232, 140, 127, 51, 99, 56, 22, 234, 185, 67, 79, 241, 121, 108, 39, 188, 189, 41, 55, 9, 64, 238, 211, 59, 183, 200, 251, 152, 160, 182, 92, 229, 166, 233, 24, 97, 13, 42, 150, 43, 2, 53, 60, 124, 146, 65, 122, 205, 5, 254, 102, 198, 112, 44, 201, 111, 134, 158, 255, 242, 216, 78, 101, 103, 82, 110, 18, 128, 193, 187, 118, 115, 141, 235, 45, 93, 113, 184, 215, 81, 207, 48, 194 }, { 53, 120, 237, 228, 100, 251, 45, 186, 217, 169, 241, 242, 173, 37, 15, 62, 146, 130, 245, 38, 80, 182, 184, 179, 89, 54, 39, 101, 206, 85, 87, 61, 205, 10, 223, 23, 252, 166, 207, 96, 47, 208, 41, 110, 36, 58, 70, 127, 102, 145, 221, 125, 12, 97, 26, 168, 196, 138, 64, 193, 107, 197, 191, 56, 44, 143, 161, 68, 21, 150, 86, 8, 181, 231, 59, 115, 7, 139, 117, 185, 134, 33, 219, 195, 1, 53, 120, 237, 228 }, { 106, 253, 59, 230, 28, 44, 3, 190, 26, 77, 55, 36, 116, 5, 223, 46, 215, 89, 108, 156, 15, 124, 114, 100, 235, 180, 185, 17, 132, 150, 172, 32, 193, 214, 51, 145, 167, 233, 96, 94, 103, 85, 174, 244, 38, 160, 226, 169, 255, 239, 1, 106, 253, 59, 230, 28, 44, 3, 190, 26, 77, 55, 36, 116, 5, 223, 46, 215, 89, 108, 156, 15, 124, 114, 100, 235, 180, 185, 17, 132, 150, 172, 32, 193, 214, 51, 145, 167, 233 }, { 212, 211, 197, 198, 167, 207, 157, 202, 62, 114, 200, 139, 201, 95, 26, 154, 220, 61, 19, 160, 217, 158, 171, 86, 32, 159, 127, 133, 229, 89, 216, 74, 120, 147, 230, 56, 176, 24, 47, 103, 170, 130, 243, 90, 185, 34, 42, 196, 18, 116, 10, 91, 109, 241, 239, 2, 181, 187, 151, 145, 83, 131, 39, 137, 124, 228, 141, 11, 143, 190, 52, 41, 165, 122, 38, 93, 175, 33, 75, 172, 64, 35, 254, 23, 215, 178, 173, 148, 240 }, { 181, 107, 102, 252, 89, 173, 53, 231, 197, 145, 166, 54, 37, 120, 59, 191, 221, 207, 39, 15, 237, 115, 56, 125, 96, 101, 62, 228, 7, 44, 12, 47, 206, 146, 100, 139, 143, 97, 208, 85, 130, 251, 117, 161, 26, 41, 87, 245, 45, 185, 68, 168, 110, 61, 38, 186, 134, 21, 196, 36, 205, 80, 217, 33, 150, 138, 58, 10, 182, 169, 219, 86, 64, 70, 223, 184, 241, 195, 8, 193, 127, 23, 179, 242, 1, 181, 107, 102, 252 }, { 119, 177, 23, 123, 239, 8, 159, 225, 184, 255, 43, 64, 140, 91, 169, 171, 69, 58, 20, 226, 33, 49, 18, 205, 160, 67, 21, 149, 144, 38, 105, 34, 168, 220, 244, 45, 111, 13, 41, 174, 243, 117, 95, 104, 85, 25, 203, 143, 194, 103, 146, 200, 22, 12, 94, 31, 228, 14, 176, 96, 202, 248, 115, 112, 233, 39, 30, 147, 191, 167, 27, 37, 240, 236, 145, 81, 216, 53, 211, 51, 252, 178, 142, 181, 214, 133, 179, 249, 4 }, { 238, 254, 184, 227, 172, 58, 40, 175, 21, 55, 122, 45, 222, 52, 85, 50, 11, 12, 188, 124, 115, 224, 131, 37, 253, 151, 252, 121, 2, 193, 225, 109, 219, 69, 116, 80, 67, 42, 110, 244, 90, 161, 104, 170, 100, 22, 24, 101, 248, 230, 221, 27, 74, 231, 51, 229, 242, 4, 159, 223, 218, 171, 138, 232, 160, 134, 84, 220, 245, 180, 95, 208, 73, 200, 44, 48, 202, 237, 209, 167, 54, 148, 211, 102, 215, 249, 8, 35, 163 }, { 193, 223, 169, 150, 36, 38, 185, 26, 85, 100, 44, 96, 15, 59, 145, 89, 1, 193, 223, 169, 150, 36, 38, 185, 26, 85, 100, 44, 96, 15, 59, 145, 89, 1, 193, 223, 169, 150, 36, 38, 185, 26, 85, 100, 44, 96, 15, 59, 145, 89, 1, 193, 223, 169, 150, 36, 38, 185, 26, 85, 100, 44, 96, 15, 59, 145, 89, 1, 193, 223, 169, 150, 36, 38, 185, 26, 85, 100, 44, 96, 15, 59, 145, 89, 1, 193, 223, 169, 150 }, { 159, 91, 33, 149, 244, 117, 194, 31, 115, 167, 216, 181, 254, 218, 150, 72, 152, 161, 189, 114, 56, 131, 148, 107, 46, 227, 138, 135, 210, 26, 170, 141, 125, 78, 253, 102, 123, 43, 58, 160, 34, 41, 25, 22, 96, 30, 236, 252, 249, 32, 10, 175, 84, 87, 235, 6, 101, 199, 198, 89, 2, 35, 182, 66, 55, 245, 234, 153, 62, 230, 83, 173, 119, 225, 169, 49, 144, 45, 95, 103, 228, 112, 27, 53, 214, 92, 219, 9, 19 }, { 35, 113, 21, 165, 235, 12, 137, 118, 252, 239, 128, 80, 34, 82, 100, 176, 78, 231, 133, 255, 138, 19, 111, 208, 114, 112, 54, 212, 254, 169, 98, 122, 117, 153, 124, 191, 162, 2, 70, 226, 42, 87, 203, 24, 15, 236, 229, 195, 29, 160, 68, 164, 200, 125, 156, 211, 23, 227, 9, 38, 222, 189, 228, 224, 108, 181, 225, 79, 196, 244, 234, 47, 248, 99, 89, 4, 140, 217, 84, 174, 139, 48, 30, 197, 215, 155, 58, 93, 136 }, { 70, 217, 168, 130, 44, 39, 231, 23, 219, 36, 45, 97, 62, 191, 89, 8, 10, 134, 41, 100, 125, 37, 107, 184, 150, 61, 117, 47, 237, 145, 242, 64, 80, 68, 85, 7, 207, 53, 127, 169, 196, 245, 143, 101, 59, 252, 195, 58, 186, 26, 146, 56, 54, 181, 223, 33, 110, 251, 12, 15, 197, 179, 86, 205, 185, 208, 228, 221, 173, 193, 182, 21, 87, 139, 96, 120, 102, 241, 138, 38, 161, 206, 115, 166, 1, 70, 217, 168, 130 }, { 140, 67, 41, 200, 233, 53, 254, 158, 110, 235, 48, 120, 204, 227, 36, 90, 153, 237, 63, 239, 58, 105, 104, 228, 167, 142, 70, 175, 154, 100, 250, 148, 127, 79, 55, 251, 24, 60, 102, 255, 18, 45, 194, 248, 145, 249, 29, 186, 52, 114, 221, 71, 35, 217, 77, 50, 125, 74, 177, 169, 149, 243, 12, 30, 51, 241, 9, 152, 97, 124, 198, 242, 128, 93, 26, 57, 224, 173, 159, 226, 168, 25, 176, 37, 214, 218, 196, 247, 6 }, { 5, 17, 85, 28, 108, 193, 226, 77, 100, 233, 106, 223, 132, 174, 44, 156, 214, 169, 55, 235, 96, 253, 46, 150, 244, 3, 15, 51, 255, 36, 180, 94, 59, 215, 172, 38, 190, 124, 145, 239, 116, 185, 103, 230, 89, 32, 160, 26, 114, 167, 1, 5, 17, 85, 28, 108, 193, 226, 77, 100, 233, 106, 223, 132, 174, 44, 156, 214, 169, 55, 235, 96, 253, 46, 150, 244, 3, 15, 51, 255, 36, 180, 94, 59, 215, 172, 38, 190, 124 }, { 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221, 1, 10, 68, 146, 221 }, { 20, 13, 228, 81, 32, 186, 189, 209, 242, 116, 222, 62, 63, 43, 38, 194, 147, 179, 9, 180, 101, 151, 227, 61, 3, 60, 23, 49, 243, 96, 211, 218, 110, 11, 156, 127, 66, 65, 125, 106, 91, 168, 200, 27, 193, 175, 164, 56, 71, 5, 68, 57, 83, 8, 160, 104, 115, 178, 29, 185, 129, 198, 195, 135, 190, 237, 229, 69, 45, 94, 236, 241, 72, 201, 15, 204, 75, 245, 24, 253, 184, 149, 203, 39, 214, 158, 87, 88, 148 }, { 40, 52, 115, 121, 116, 161, 248, 229, 138, 180, 202, 102, 75, 247, 96, 187, 79, 87, 176, 106, 182, 154, 14, 173, 5, 136, 228, 162, 128, 185, 31, 63, 86, 152, 94, 197, 227, 122, 12, 253, 109, 110, 22, 74, 223, 84, 200, 54, 35, 17, 146, 83, 16, 186, 103, 99, 195, 19, 194, 59, 246, 72, 143, 60, 46, 196, 203, 78, 127, 132, 25, 207, 238, 175, 85, 224, 2, 80, 104, 230, 242, 232, 95, 237, 215, 9, 117, 137, 204 }, { 80, 208, 191, 195, 38, 47, 197, 219, 245, 96, 107, 33, 130, 207, 193, 134, 146, 166, 64, 185, 62, 252, 138, 117, 15, 23, 196, 139, 37, 223, 168, 7, 173, 10, 26, 115, 242, 205, 97, 59, 241, 61, 12, 231, 169, 87, 125, 181, 217, 85, 221, 8, 186, 206, 145, 86, 45, 101, 102, 150, 251, 39, 127, 21, 100, 54, 70, 68, 228, 89, 58, 161, 237, 179, 36, 143, 120, 184, 110, 44, 53, 182, 41, 56, 1, 80, 208, 191, 195 }, { 160, 103, 145, 172, 180, 15, 46, 55, 44, 106, 226, 85, 167, 32, 185, 124, 215, 36, 3, 253, 169, 174, 233, 193, 17, 114, 89, 116, 190, 59, 255, 244, 96, 214, 132, 100, 108, 5, 26, 230, 239, 38, 94, 51, 150, 235, 156, 223, 77, 28, 1, 160, 103, 145, 172, 180, 15, 46, 55, 44, 106, 226, 85, 167, 32, 185, 124, 215, 36, 3, 253, 169, 174, 233, 193, 17, 114, 89, 116, 190, 59, 255, 244, 96, 214, 132, 100, 108, 5 }, { 93, 129, 252, 18, 3, 231, 158, 25, 54, 5, 52, 191, 43, 90, 15, 92, 220, 125, 238, 17, 228, 121, 135, 47, 51, 49, 139, 148, 113, 85, 83, 128, 161, 147, 255, 245, 157, 254, 168, 28, 2, 186, 31, 229, 36, 6, 211, 33, 50, 108, 10, 104, 99, 86, 180, 30, 184, 165, 250, 193, 34, 213, 242, 19, 94, 102, 98, 11, 53, 226, 170, 166, 29, 95, 59, 227, 247, 39, 225, 77, 56, 4, 105, 62, 215, 72, 12, 187, 66 }, { 186, 62, 179, 61, 96, 127, 168, 56, 8, 185, 237, 241, 245, 39, 223, 41, 221, 64, 161, 59, 219, 251, 37, 182, 85, 166, 58, 97, 197, 150, 139, 53, 217, 146, 89, 205, 47, 102, 196, 44, 181, 134, 228, 242, 38, 101, 23, 110, 125, 193, 68, 115, 195, 45, 15, 184, 87, 207, 70, 26, 191, 86, 117, 120, 169, 130, 54, 10, 208, 145, 138, 143, 231, 33, 100, 173, 80, 206, 252, 36, 12, 107, 21, 7, 1, 186, 62, 179, 61 }, { 105, 248, 241, 247, 156, 182, 170, 162, 205, 94, 133, 110, 250, 35, 26, 99, 69, 143, 211, 132, 7, 2, 210, 237, 255, 243, 37, 113, 73, 89, 135, 188, 23, 220, 233, 70, 52, 198, 138, 3, 187, 21, 14, 4, 185, 199, 227, 251, 74, 226, 146, 178, 19, 101, 46, 165, 207, 140, 104, 145, 9, 6, 107, 42, 28, 8, 111, 147, 219, 235, 148, 217, 57, 121, 38, 202, 92, 87, 131, 5, 208, 63, 18, 12, 214, 84, 56, 16, 222 } }; + static int[] logArrays = { 256, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114, 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 175 }; + static int[] expArrays = { 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4 }; + + // Encode + internal static void Encode(byte[] codeWord, byte[] message, int mBitSize, int n1, int paramK, int paramG, int[] rsPoly) + { + int gateValue = 0; + byte[] encodedBytes = new byte[n1]; + int[] tmp = new int[paramG]; + + byte[] msgByte = Arrays.Clone(message); + + for (int i = 0; i < paramK; i++) + { + gateValue = Utils.ToUnsigned8bits(msgByte[paramK - 1 - i] ^ encodedBytes[n1 - paramK - 1]); + + for (int j = 0; j < paramG; j++) + { + tmp[j] = GFCalculator.mult(gateValue, rsPoly[j]); + int n = 1; + } + + for (int j = n1 - paramK - 1; j > 0; j--) + { + encodedBytes[j] = (byte)(encodedBytes[j - 1] ^ tmp[j]); + } + encodedBytes[0] = (byte)(tmp[0]); + } + + Array.Copy(msgByte, 0, encodedBytes, n1 - paramK, paramK); + Array.Copy(encodedBytes, 0, codeWord, 0, codeWord.Length); + } + + // Decode + internal static void decode(byte[] message, byte[] codeWord, int n1, int fft, int delta, int paramK, int paramG) + { + int fftSize = 1 << fft; + int mSize = 1 << (HqcParameters.PARAM_M - 1); + + byte[] codeWordByte = Arrays.Clone(codeWord); + + int[] syndromes = new int[2 * delta]; + // Step 1: Compute syndromes + ComputeSyndromes(syndromes, codeWordByte, delta, n1); + + // Step 2: Compute the error locator polynomial sigma + int[] sigma = new int[fftSize]; + int degSigma = ComputeELP(sigma, syndromes, delta); + + // Step 3: Compute roots using FFT + int[] fftRes = new int[1 << HqcParameters.PARAM_M]; + byte[] errorSet = new byte[1 << HqcParameters.PARAM_M]; + FastFourierTransform.FFT(fftRes, sigma, delta + 1, fft); + FastFourierTransform.FastFourierTransformGetError(errorSet, fftRes, mSize, logArrays); + + // Step 4: Compute z(x) + int[] zx = new int[n1]; + ComputeZx(zx, sigma, degSigma, syndromes, delta); + + // Step 5: Compute errors + int[] errors = new int[n1]; + ComputeErrors(errors, zx, errorSet, delta, n1); + + // Step 6: Correct errors + for (int i = 0; i < n1; i++) + { + codeWordByte[i] ^= (byte) errors[i]; + } + byte[] mTmp = new byte[paramK]; + Array.Copy(codeWordByte, paramG - 1, mTmp, 0, paramK); + Array.Copy(mTmp, 0, message, 0, message.Length); + } + + private static void ComputeSyndromes(int[] syndromes, byte[] codeWord, int delta, int n1) + { + if (n1 == 46) + { + for (int i = 0; i < 2 * delta; i++) + { + for (int j = 1; j < n1; j++) + { + syndromes[i] ^= GFCalculator.mult(Utils.ToUnsigned8bits(codeWord[j]), alpha128[i, j - 1]); + } + syndromes[i] ^= Utils.ToUnsigned8bits(codeWord[0]); + } + } + else if (n1 == 56) + { + for (int i = 0; i < 2 * delta; i++) + { + for (int j = 1; j < n1; j++) + { + syndromes[i] ^= GFCalculator.mult(Utils.ToUnsigned8bits(codeWord[j]), alpha192[i, j - 1]); + } + syndromes[i] ^= Utils.ToUnsigned8bits(codeWord[0]); + } + } + else if (n1 == 90) + { + for (int i = 0; i < 2 * delta; i++) + { + for (int j = 1; j < n1; j++) + { + syndromes[i] ^= GFCalculator.mult(Utils.ToUnsigned8bits(codeWord[j]), alpha256[i, j - 1]); + } + syndromes[i] ^= Utils.ToUnsigned8bits(codeWord[0]); + } + } + } + + private static int ComputeELP(int[] sigma, int[] syndromes, int delta) + { + sigma[0] = 1; + int degSigma = 0; + int degSigmaP = 0; + int[] sigmaDup = new int[delta + 1]; + int[] sigmaP = new int[delta + 1]; + int degSigmaDup = 0; + int pp = Utils.ToUnsigned16Bits(-1); + int dp = 1; + int d = syndromes[0]; + + sigmaP[1] = 1; + + for (int i = 0; i < 2 * delta; i++) + { + Array.Copy(sigma, 0, sigmaDup, 0, delta + 1); + degSigmaDup = degSigma; + int dd = GFCalculator.mult(d, GFCalculator.inverse(dp)); + + for (int j = 1; j <= i + 1 && j <= delta; j++) + { + sigma[j] ^= GFCalculator.mult(dd, sigmaP[j]); + } + + int degX = Utils.ToUnsigned16Bits(i - pp); + int degXSigmaP = Utils.ToUnsigned16Bits(degX + degSigmaP); + + int firstMask = d != 0 ? 0xffff : 0; + int secondMask = degXSigmaP > degSigma ? 0xffff : 0; + + int mask = firstMask & secondMask; + degSigma ^= mask & (degXSigmaP ^ degSigma); + + if (i == (2 * delta - 1)) + { + break; + } + + pp ^= mask & (i ^ pp); + dp ^= mask & (d ^ dp); + + for (int k = delta; k > 0; k--) + { + sigmaP[k] = (mask & sigmaDup[k - 1]) ^ (~mask & sigmaP[k - 1]); + } + + degSigmaP ^= mask & (degSigmaDup ^ degSigmaP); + d = syndromes[i + 1]; + + for (int k = 1; k <= i + 1 && k <= delta; k++) + { + d ^= GFCalculator.mult(sigma[k], syndromes[i + 1 - k]); + } + } + return degSigma; + } + + private static void ComputeZx(int[] output, int[] sigma, int deg, int[] syndromes, int delta) + { + output[0] = 1; + + for (int i = 1; i < delta + 1; i++) + { + int mask = i - deg < 1 ? 0xffff : 0; + output[i] = mask & sigma[i]; + } + + output[1] ^= syndromes[0]; + + for (int i = 2; i <= delta; i++) + { + int mask = i - deg < 1 ? 0xffff : 0; + output[i] = mask & sigma[i - 1]; + + for (int j = 1; j < i; j++) + { + output[i] ^= (mask) & GFCalculator.mult(sigma[j], syndromes[i - j - 1]); + } + } + } + + private static void ComputeErrors(int[] res, int[] zx, byte[] errorCompactSet, int delta, int n1) + { + int[] betaSet = new int[delta]; + int[] eSet = new int[delta]; + + int deltaCount = 0; + int deltaVal = 0; + int mask1 = 0; + for (int i = 0; i < n1; i++) + { + int mark = 0; + int mask = errorCompactSet[i] != 0 ? 0xffff : 0; + for (int j = 0; j < delta; j++) + { + int iMask = j == deltaCount ? 0xffff : 0; + betaSet[j] += iMask & mask & expArrays[i]; + mark += iMask & mask & 1; + } + deltaCount += mark; + } + deltaVal = deltaCount; + + for (int i = 0; i < delta; i++) + { + int temp1 = 1; + int temp2 = 1; + int inv = GFCalculator.inverse(betaSet[i]); + int invPow = 1; + + for (int j = 1; j <= delta; j++) + { + invPow = GFCalculator.mult(invPow, inv); + temp1 ^= GFCalculator.mult(invPow, zx[j]); + } + + for (int j = 1; j < delta; j++) + { + temp2 = GFCalculator.mult(temp2, (1 ^ GFCalculator.mult(inv, betaSet[(i + j) % delta]))); + } + + mask1 = i < deltaVal ? 0xffff : 0; + eSet[i] = mask1 & GFCalculator.mult(temp1, GFCalculator.inverse(temp2)); + } + + deltaCount = 0; + for (int i = 0; i < n1; i++) + { + int mark = 0; + int mask = errorCompactSet[i] != 0 ? 0xffff : 0; + + for (int j = 0; j < delta; j++) + { + int iMask = j == deltaCount ? 0xffff : 0; + res[i] += iMask & mask & eSet[j]; + mark += iMask & mask & 1; + } + deltaCount += mark; + } + } + } +} diff --git a/crypto/src/pqc/crypto/hqc/Utils.cs b/crypto/src/pqc/crypto/hqc/Utils.cs new file mode 100644 index 000000000..a03633e64 --- /dev/null +++ b/crypto/src/pqc/crypto/hqc/Utils.cs @@ -0,0 +1,243 @@ +using Org.BouncyCastle.Crypto.Utilities; +using System; +using System.Collections.Generic; +using System.Linq; +using System.Runtime.CompilerServices; +using System.Text; +using System.Threading.Tasks; + +namespace Org.BouncyCastle.Pqc.Crypto.Hqc +{ + internal class Utils + { + internal static void ResizeArray(long[] output, int sizeOutBits, long[] input, int sizeInBits, int n1n2ByteSize, int n1n2Byte64Size) + { + + long mask = 0x7FFFFFFFFFFFFFFFl; + int val = 0; + if (sizeOutBits < sizeInBits) + { + if (sizeOutBits % 64 != 0) + { + val = 64 - (sizeOutBits % 64); + } + + Array.Copy(input, 0, output, 0, n1n2ByteSize); + + for (int i = 0; i < val; ++i) + { + output[n1n2Byte64Size - 1] &= (mask >> i); + } + } + else + { + Array.Copy(input, 0, output, 0, (sizeInBits + 7) / 8); + } + } + + internal static long[] FromULongArrayToLongArray(ulong[] input) + { + long[] output = new long[input.Length]; + for (int i =0; i< output.Length; i++) + { + output[i] = (long) input[i]; + } + return output; + } + + 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) UnsignedRightBitShiftLong((input[i] & (1 << j)), j); + } + } + if (output.Length % 8 != 0) + { + int off = max * 8; + int count = 0; + while (off < output.Length) + { + output[off++] = (byte) UnsignedRightBitShiftLong((input[max] & (1 << count)), count); + count++; + } + } + } + + internal static void FromLongArrayToBitArray(byte[] output, long[] input) + { + int max = (output.Length / 64); + for (int i = 0; i < max; i++) + { + for (int j = 0; j != 64; j++) + { + output[i * 64 + j] = (byte)UnsignedRightBitShiftLong((input[i] & (1L << j)), j); + } + } + if (output.Length % 64 != 0) + { + int off = max * 64; + int count = 0; + while (off < output.Length) + { + output[off++] = (byte) UnsignedRightBitShiftLong((input[max] & (1L << count)), count); + count++; + } + } + } + + internal static void FromLongArrayToByteArray(byte[] output, long[] input) + { + int max = output.Length / 8; + for (int i = 0; i != max; i++) + { + Pack.UInt64_To_LE((ulong) input[i], output, i * 8); + } + + if (output.Length % 8 != 0) + { + int off = max * 8; + int count = 0; + while (off < output.Length) + { + output[off++] = (byte) UnsignedRightBitShiftLong(input[max], (count++ * 8)); + } + } + } + + internal static void FromULongArrayToByteArray(byte[] output, ulong[] input) + { + int max = output.Length / 8; + for (int i = 0; i != max; i++) + { + Pack.UInt64_To_LE(input[i], output, i * 8); + } + + if (output.Length % 8 != 0) + { + int off = max * 8; + int count = 0; + while (off < output.Length) + { + output[off++] = (byte)(input[max] >> (count++ * 8)); + } + } + } + + internal static long BitMask(long a, long b) + { + int tmp = (int) (a % b); + return ((1L << tmp) - 1); + } + + internal static void FromByteArrayToLongArray(long[] output, byte[] input) + { + byte[] tmp = input; + if (input.Length % 8 != 0) + { + tmp = new byte[((input.Length + 7) / 8) * 8]; + Array.Copy(input, 0, tmp, 0, input.Length); + } + + int off = 0; + for (int i = 0; i < output.Length; i++) + { + output[i] = (long) Pack.LE_To_UInt64(tmp, off); + off += 8; + } + } + + internal static void FromByteArrayToByte16Array(int[] output, byte[] input) + { + byte[] tmp = input; + if (input.Length % 2 != 0) + { + tmp = new byte[((input.Length + 1) / 2) * 2]; + Array.Copy(input, 0, tmp, 0, input.Length); + } + + int off = 0; + for (int i = 0; i < output.Length; i++) + { + output[i] = (int)Pack.LE_To_UInt16(tmp, off); + off += 2; + } + } + + internal static void FromByte32ArrayToLongArray(long[] output, int[] input) + { + for (int i = 0; i != input.Length; i += 2) + { + output[i / 2] = input[i] & 0xffffffffL; + output[i / 2] |= (long)input[i + 1] << 32; + } + } + + internal static void FromByte16ArrayToLongArray(ulong[] output, int[] input) + { + for (int i = 0; i != input.Length; i += 4) + { + output[i / 4] = (ulong) input[i] & 0xffffL; + output[i / 4] |= (ulong) input[i + 1] << 16; + output[i / 4] |= (ulong) input[i + 2] << 32; + output[i / 4] |= (ulong) input[i + 3] << 48; + } + } + + internal static void FromULongArrayToByte16Array(int[] output, ulong[] input) + { + for (int i = 0; i != input.Length; i++) + { + output[4 * i] = (UInt16)input[i]; + output[4 * i + 1] = (UInt16)(input[i] >> 16); + output[4 * i + 2] = (UInt16)(input[i] >> 32); + output[4 * i + 3] = (UInt16)(input[i] >> 48); + } + } + + internal static void FromLongArrayToByte32Array(int[] output, long[] input) + { + for (int i = 0; i != input.Length; i++) + { + output[2 * i] = (int)input[i]; + output[2 * i + 1] = (int)(input[i] >> 32); + } + } + + internal static void CopyBytes(int[] src, int offsetSrc, int[] dst, int offsetDst, int lengthBytes) + { + Array.Copy(src, offsetSrc, dst, offsetDst, lengthBytes / 2); + } + + internal static int GetByteSizeFromBitSize(int size) + { + return (size + 7) / 8; + } + + internal static int GetByte64SizeFromBitSize(int size) + { + return (size + 63) / 64; + } + + internal static int ToUnsigned8bits(int a) + { + return a & 0xff; + } + + internal static int ToUnsigned16Bits(int a) + { + return a & 0xffff; + } + + internal static long UnsignedRightBitShiftLong(long a, int b) + { + ulong tmp = (ulong)a; + tmp >>= b; + return (long)tmp; + } + + } +} diff --git a/crypto/src/pqc/crypto/utils/PqcUtilities.cs b/crypto/src/pqc/crypto/utils/PqcUtilities.cs index d0873d702..eece55e99 100644 --- a/crypto/src/pqc/crypto/utils/PqcUtilities.cs +++ b/crypto/src/pqc/crypto/utils/PqcUtilities.cs @@ -8,6 +8,7 @@ using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; using Org.BouncyCastle.Pqc.Crypto.Falcon; +using Org.BouncyCastle.Pqc.Crypto.Hqc; using Org.BouncyCastle.Pqc.Crypto.Picnic; using Org.BouncyCastle.Pqc.Crypto.Saber; using Org.BouncyCastle.Pqc.Crypto.Sike; @@ -41,6 +42,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities private readonly static Dictionary<BikeParameters, DerObjectIdentifier> bikeOids = new Dictionary<BikeParameters, DerObjectIdentifier>(); private readonly static Dictionary<DerObjectIdentifier, BikeParameters> bikeParams = new Dictionary<DerObjectIdentifier, BikeParameters>(); + private readonly static Dictionary<HqcParameters, DerObjectIdentifier> hqcOids = new Dictionary<HqcParameters, DerObjectIdentifier>(); + private readonly static Dictionary<DerObjectIdentifier, HqcParameters> hqcParams = new Dictionary<DerObjectIdentifier, HqcParameters>(); + static PqcUtilities() { // CMCE @@ -166,13 +170,21 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities dilithiumParams[BCObjectIdentifiers.dilithium3_aes] = DilithiumParameters.Dilithium3Aes; dilithiumParams[BCObjectIdentifiers.dilithium5_aes] = DilithiumParameters.Dilithium5Aes; + bikeParams[BCObjectIdentifiers.bike128] = BikeParameters.bike128; + bikeParams[BCObjectIdentifiers.bike192] = BikeParameters.bike192; + bikeParams[BCObjectIdentifiers.bike256] = BikeParameters.bike256; + 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; + hqcParams[BCObjectIdentifiers.hqc128] = HqcParameters.hqc128; + hqcParams[BCObjectIdentifiers.hqc192] = HqcParameters.hqc192; + hqcParams[BCObjectIdentifiers.hqc256] = HqcParameters.hqc256; + + hqcOids[HqcParameters.hqc128] = BCObjectIdentifiers.hqc128; + hqcOids[HqcParameters.hqc192] = BCObjectIdentifiers.hqc192; + hqcOids[HqcParameters.hqc256] = BCObjectIdentifiers.hqc256; } public static DerObjectIdentifier McElieceOidLookup(CmceParameters parameters) @@ -263,5 +275,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities { return bikeParams[oid]; } + + internal static DerObjectIdentifier HqcOidLookup(HqcParameters parameters) + { + return hqcOids[parameters]; + } + + internal static HqcParameters HqcParamsLookup(DerObjectIdentifier oid) + { + return hqcParams[oid]; + } } } diff --git a/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs b/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs index 937242903..1bcd10934 100644 --- a/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs +++ b/crypto/src/pqc/crypto/utils/PrivateKeyFactory.cs @@ -14,6 +14,7 @@ using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; using Org.BouncyCastle.Pqc.Crypto.Falcon; +using Org.BouncyCastle.Pqc.Crypto.Hqc; using Org.BouncyCastle.Pqc.Crypto.Lms; using Org.BouncyCastle.Pqc.Crypto.Picnic; using Org.BouncyCastle.Pqc.Crypto.Saber; @@ -118,9 +119,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities 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.On(BCObjectIdentifiers.pqc_kem_hqc)) + { + byte[] keyEnc = Asn1OctetString.GetInstance(keyInfo.ParsePrivateKey()).GetOctets(); + HqcParameters hqcParams = PqcUtilities.HqcParamsLookup(keyInfo.PrivateKeyAlgorithm.Algorithm); + + return new HqcPrivateKeyParameters(hqcParams, keyEnc); + } 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 61b02f009..3525b79d3 100644 --- a/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs +++ b/crypto/src/pqc/crypto/utils/PrivateKeyInfoFactory.cs @@ -16,6 +16,7 @@ using Org.BouncyCastle.Pqc.Crypto.Sike; using Org.BouncyCastle.Pqc.Crypto.Bike; using Org.BouncyCastle.Pqc.Crypto.SphincsPlus; using Org.BouncyCastle.Utilities; +using Org.BouncyCastle.Pqc.Crypto.Hqc; namespace Org.BouncyCastle.Pqc.Crypto.Utilities { @@ -170,13 +171,19 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return new PrivateKeyInfo(algorithmIdentifier, new DerSequence(v), attributes, new DerSequence(vPub).GetEncoded()); } - if (privateKey is BikePrivateKeyParameters) + if (privateKey is BikePrivateKeyParameters bikePrivateKeyParameters) { - BikePrivateKeyParameters parameters = (BikePrivateKeyParameters)privateKey; + byte[] encoding = bikePrivateKeyParameters.GetEncoded(); - byte[] encoding = parameters.GetEncoded(); - - AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier(PqcUtilities.BikeOidLookup(parameters.Parameters)); + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier( + PqcUtilities.BikeOidLookup(bikePrivateKeyParameters.Parameters)); + return new PrivateKeyInfo(algorithmIdentifier, new DerOctetString(encoding), attributes); + } + else if (privateKey is HqcPrivateKeyParameters hqcPrivateKeyParameters) + { + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier( + PqcUtilities.HqcOidLookup(hqcPrivateKeyParameters.Parameters)); + byte[] encoding = hqcPrivateKeyParameters.PrivateKey; return new PrivateKeyInfo(algorithmIdentifier, new DerOctetString(encoding), attributes); } diff --git a/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs b/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs index 3f352bf04..1d753c637 100644 --- a/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs +++ b/crypto/src/pqc/crypto/utils/PublicKeyFactory.cs @@ -14,6 +14,7 @@ using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; using Org.BouncyCastle.Pqc.Crypto.Falcon; +using Org.BouncyCastle.Pqc.Crypto.Hqc; using Org.BouncyCastle.Pqc.Crypto.Picnic; using Org.BouncyCastle.Pqc.Crypto.Saber; using Org.BouncyCastle.Pqc.Crypto.Sike; @@ -98,8 +99,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities converters[BCObjectIdentifiers.bike128] = new BikeConverter(); converters[BCObjectIdentifiers.bike192] = new BikeConverter(); converters[BCObjectIdentifiers.bike256] = new BikeConverter(); + + converters[BCObjectIdentifiers.hqc128] = new HqcConverter(); + converters[BCObjectIdentifiers.hqc192] = new HqcConverter(); + converters[BCObjectIdentifiers.hqc256] = new HqcConverter(); } - + /// <summary> Create a public key from a SubjectPublicKeyInfo encoding</summary> /// <param name="keyInfoData"> the SubjectPublicKeyInfo encoding</param> /// <returns> the appropriate key parameter</returns> @@ -297,12 +302,24 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities { internal override AsymmetricKeyParameter GetPublicKeyParameters(SubjectPublicKeyInfo keyInfo, object defaultParams) { - byte[] keyEnc = DerOctetString.GetInstance(keyInfo.ParsePublicKey()).GetOctets(); + byte[] keyEnc = Asn1OctetString.GetInstance(keyInfo.ParsePublicKey()).GetOctets(); BikeParameters bikeParams = PqcUtilities.BikeParamsLookup(keyInfo.AlgorithmID.Algorithm); return new BikePublicKeyParameters(bikeParams, keyEnc); } } + + private class HqcConverter : SubjectPublicKeyInfoConverter + { + internal override AsymmetricKeyParameter GetPublicKeyParameters(SubjectPublicKeyInfo keyInfo, object defaultParams) + { + byte[] keyEnc = Asn1OctetString.GetInstance(keyInfo.ParsePublicKey()).GetOctets(); + + HqcParameters hqcParams = PqcUtilities.HqcParamsLookup(keyInfo.AlgorithmID.Algorithm); + + return new HqcPublicKeyParameters(hqcParams, 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 a919a71e5..7ef63871f 100644 --- a/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs +++ b/crypto/src/pqc/crypto/utils/SubjectPublicKeyInfoFactory.cs @@ -10,6 +10,7 @@ using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium; using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber; using Org.BouncyCastle.Pqc.Crypto.Falcon; +using Org.BouncyCastle.Pqc.Crypto.Hqc; using Org.BouncyCastle.Pqc.Crypto.Picnic; using Org.BouncyCastle.Pqc.Crypto.Saber; using Org.BouncyCastle.Pqc.Crypto.Sike; @@ -119,13 +120,20 @@ namespace Org.BouncyCastle.Pqc.Crypto.Utilities return new SubjectPublicKeyInfo(algorithmIdentifier, new DerOctetString(Arrays.Concatenate(parameters.Rho, parameters.T1))); } - if (publicKey is BikePublicKeyParameters) + if (publicKey is BikePublicKeyParameters bikePublicKeyParameters) { - BikePublicKeyParameters parameters = (BikePublicKeyParameters)publicKey; + byte[] encoding = bikePublicKeyParameters.GetEncoded(); + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier( + PqcUtilities.BikeOidLookup(bikePublicKeyParameters.Parameters)); - - byte[] encoding = parameters.GetEncoded(); - AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier(PqcUtilities.BikeOidLookup(parameters.Parameters)); + return new SubjectPublicKeyInfo(algorithmIdentifier, new DerOctetString(encoding)); + } + if (publicKey is HqcPublicKeyParameters hqcPublicKeyParameters) + { + byte[] encoding = hqcPublicKeyParameters.GetEncoded(); + + AlgorithmIdentifier algorithmIdentifier = new AlgorithmIdentifier( + PqcUtilities.HqcOidLookup(hqcPublicKeyParameters.Parameters)); return new SubjectPublicKeyInfo(algorithmIdentifier, new DerOctetString(encoding)); } |