From 885993b1f48e46fc35c3f08ad8c3a369bbb018f3 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Fri, 11 Nov 2022 22:06:04 +0700 Subject: Picnic perf. opts. --- crypto/src/pqc/crypto/picnic/PicnicEngine.cs | 33 ++++++---- crypto/src/pqc/crypto/picnic/PicnicUtilities.cs | 87 ++++++++++--------------- crypto/src/pqc/crypto/picnic/Tape.cs | 38 +++++++++-- 3 files changed, 86 insertions(+), 72 deletions(-) diff --git a/crypto/src/pqc/crypto/picnic/PicnicEngine.cs b/crypto/src/pqc/crypto/picnic/PicnicEngine.cs index e813d8977..1fb04f3a2 100644 --- a/crypto/src/pqc/crypto/picnic/PicnicEngine.cs +++ b/crypto/src/pqc/crypto/picnic/PicnicEngine.cs @@ -3,6 +3,7 @@ using System; using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Crypto.Digests; using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Math.Raw; using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; @@ -2175,8 +2176,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic { for (int i = 0; i < numMPCParties; i++) { - uint w_i = PicnicUtilities.GetBit(Pack.UInt32_To_LE(w), i); - PicnicUtilities.SetBit(msg.msgs[i], msg.pos, (byte) (w_i & 0xff)); + uint w_i = PicnicUtilities.GetBit(w, i); + PicnicUtilities.SetBit(msg.msgs[i], msg.pos, (byte)w_i); } msg.pos++; @@ -2187,13 +2188,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic uint and_helper = tape.TapesToWord(); // The special mask value setup during preprocessing for each AND gate uint s_shares = (Extend(a) & mask_b) ^ (Extend(b) & mask_a) ^ and_helper; - byte[] temp = Pack.UInt32_To_LE(s_shares); - if (msg.unopened >= 0) { - uint unopenedPartyBit = PicnicUtilities.GetBit(msg.msgs[msg.unopened], msg.pos); - PicnicUtilities.SetBit(temp, msg.unopened, (byte) (unopenedPartyBit & 0xff)); - s_shares = Pack.LE_To_UInt32(temp, 0); + uint unopenedPartyBit = PicnicUtilities.GetBit(msg.msgs[msg.unopened], msg.pos); + s_shares = PicnicUtilities.SetBit(s_shares, msg.unopened, unopenedPartyBit); } // Broadcast each share of s @@ -2489,6 +2487,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic uint[] temp = new uint[LOWMC_MAX_WORDS]; temp[stateSizeWords - 1] = 0; int wholeWords = stateSizeBits / WORD_SIZE_BITS; + int unusedStateBits = stateSizeWords * WORD_SIZE_BITS - stateSizeBits; + + // The final word mask, with bits reversed within each byte + uint partialWordMask = uint.MaxValue >> unusedStateBits; + partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x55555555U, 1); + partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x33333333U, 2); + partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x0F0F0F0FU, 4); for (int i = 0; i < stateSizeBits; i++) { @@ -2496,15 +2501,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic for (int j = 0; j < wholeWords; j++) { int index = i * stateSizeWords + j; - prod ^= state[j + stateOffset] & matrix[matrixOffset + index]; + prod ^= state[j + stateOffset] & + matrix[matrixOffset + index]; } - - for (int j = wholeWords * WORD_SIZE_BITS; j < stateSizeBits; j++) + if (unusedStateBits > 0) { - int index = i * stateSizeWords * WORD_SIZE_BITS + j; - uint bit = PicnicUtilities.GetBitFromWordArray(state, stateOffset * 32 + j) - & PicnicUtilities.GetBitFromWordArray(matrix, matrixOffset * 32 + index); - prod ^= bit; + int index = i * stateSizeWords + wholeWords; + prod ^= state[stateOffset + wholeWords] & + matrix[matrixOffset + index] & + partialWordMask; } PicnicUtilities.SetBit(temp, i, PicnicUtilities.Parity32(prod)); diff --git a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs index c3be46840..a2f1ca080 100644 --- a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs +++ b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs @@ -1,3 +1,9 @@ +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics.X86; +#endif + +using Org.BouncyCastle.Utilities; + namespace Org.BouncyCastle.Pqc.Crypto.Picnic { internal static class PicnicUtilities @@ -16,47 +22,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic internal static uint ceil_log2(uint x) { - if (x == 0) - { - return 0; - } - - return 32 - nlz(x - 1); - } - - private static uint nlz(uint x) - { - uint n; - - if (x == 0) return (32); - n = 1; - if ((x >> 16) == 0) - { - n = n + 16; - x = x << 16; - } - - if ((x >> 24) == 0) - { - n = n + 8; - x = x << 8; - } - - if ((x >> 28) == 0) - { - n = n + 4; - x = x << 4; - } - - if ((x >> 30) == 0) - { - n = n + 2; - x = x << 2; - } - - n = (n - (x >> 31)); - - return n; + return x == 0 ? 0 : 32 - (uint)Integers.NumberOfLeadingZeros((int)(x - 1)); } internal static int Parity(byte[] data, int len) @@ -68,20 +34,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic x ^= data[i]; } - /* Compute parity of x using code from Section 5-2 of - * H.S. Warren, *Hacker's Delight*, Pearson Education, 2003. - * http://www.hackersdelight.org/hdcodetxt/parity.c.txt - */ - int y = x ^ (x >> 1); - y ^= (y >> 2); - y ^= (y >> 4); - y ^= (y >> 8); - y ^= (y >> 16); - return y & 1; + return (int)Parity16(x); } internal static uint Parity16(uint x) { +#if NETCOREAPP3_0_OR_GREATER + if (Popcnt.IsSupported) + { + return Popcnt.PopCount(x & 0xFFFF) & 1U; + } +#endif + uint y = x ^ (x >> 1); y ^= (y >> 2); @@ -92,6 +56,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic internal static uint Parity32(uint x) { +#if NETCOREAPP3_0_OR_GREATER + if (Popcnt.IsSupported) + { + return Popcnt.PopCount(x) & 1U; + } +#endif + /* Compute parity of x using code from Section 5-2 of * H.S. Warren, *Hacker's Delight*, Pearson Education, 2003. * http://www.hackersdelight.org/hdcodetxt/parity.c.txt @@ -124,6 +95,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic return (byte)((array[arrayPos] >> bitPos) & 1); } + internal static uint GetBit(uint word, int bitNumber) + { + int bitPos = bitNumber ^ 7; + return (word >> bitPos) & 1U; + } + /* Get one bit from a byte array */ internal static uint GetBit(uint[] array, int bitNumber) { @@ -140,6 +117,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic array[arrayPos] = (byte)t; } + internal static uint SetBit(uint word, int bitNumber, uint bit) + { + int bitPos = bitNumber ^ 7; + word &= ~(1U << bitPos); + word |= bit << bitPos; + return word; + } + /* Set a specific bit in a int array to a given value */ internal static void SetBit(uint[] array, int bitNumber, uint val) { diff --git a/crypto/src/pqc/crypto/picnic/Tape.cs b/crypto/src/pqc/crypto/picnic/Tape.cs index 9f72bc4dd..700207dea 100644 --- a/crypto/src/pqc/crypto/picnic/Tape.cs +++ b/crypto/src/pqc/crypto/picnic/Tape.cs @@ -114,15 +114,39 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic internal uint TapesToWord() { - byte[] shares = new byte[4]; + //byte[] shares = new byte[4]; + //for (int i = 0; i < 16; i++) + //{ + // byte bit = PicnicUtilities.GetBit(this.tapes[i], this.pos); + // PicnicUtilities.SetBit(shares, i, bit); + //} + //this.pos++; + //return Pack.LE_To_UInt32(shares, 0); + + uint shares = 0U; + int arrayPos = pos >> 3, bitPos = (pos & 7) ^ 7; + uint bitMask = 1U << bitPos; + + shares |= (tapes[ 0][arrayPos] & bitMask) << 7; + shares |= (tapes[ 1][arrayPos] & bitMask) << 6; + shares |= (tapes[ 2][arrayPos] & bitMask) << 5; + shares |= (tapes[ 3][arrayPos] & bitMask) << 4; + shares |= (tapes[ 4][arrayPos] & bitMask) << 3; + shares |= (tapes[ 5][arrayPos] & bitMask) << 2; + shares |= (tapes[ 6][arrayPos] & bitMask) << 1; + shares |= (tapes[ 7][arrayPos] & bitMask) << 0; + + shares |= (tapes[ 8][arrayPos] & bitMask) << 15; + shares |= (tapes[ 9][arrayPos] & bitMask) << 14; + shares |= (tapes[10][arrayPos] & bitMask) << 13; + shares |= (tapes[11][arrayPos] & bitMask) << 12; + shares |= (tapes[12][arrayPos] & bitMask) << 11; + shares |= (tapes[13][arrayPos] & bitMask) << 10; + shares |= (tapes[14][arrayPos] & bitMask) << 9; + shares |= (tapes[15][arrayPos] & bitMask) << 8; - for (int i = 0; i < 16; i++) - { - byte bit = PicnicUtilities.GetBit(this.tapes[i], this.pos); - PicnicUtilities.SetBit(shares, i, bit); - } this.pos++; - return Pack.LE_To_UInt32(shares, 0); + return shares >> bitPos; } } } -- cgit 1.4.1