diff --git a/crypto/src/crypto/IXof.cs b/crypto/src/crypto/IXof.cs
new file mode 100644
index 000000000..e9e2253a0
--- /dev/null
+++ b/crypto/src/crypto/IXof.cs
@@ -0,0 +1,22 @@
+using System;
+
+namespace Org.BouncyCastle.Crypto
+{
+ /// <remarks>
+ /// With FIPS PUB 202 a new kind of message digest was announced which supported extendable output, or variable digest sizes.
+ /// This interface provides the extra method required to support variable output on a digest implementation.
+ /// </remarks>
+ public interface IXof
+ : IDigest
+ {
+ /**
+ * Output the results of the final calculation for this digest to outLen number of bytes.
+ *
+ * @param out output array to write the output bytes to.
+ * @param outOff offset to start writing the bytes at.
+ * @param outLen the number of output bytes requested.
+ * @return the number of bytes written
+ */
+ int DoFinal(byte[] output, int outOff, int outLen);
+ }
+}
diff --git a/crypto/src/crypto/digests/KeccakDigest.cs b/crypto/src/crypto/digests/KeccakDigest.cs
new file mode 100644
index 000000000..2d6cf393c
--- /dev/null
+++ b/crypto/src/crypto/digests/KeccakDigest.cs
@@ -0,0 +1,534 @@
+using System;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Crypto.Digests
+{
+ /// <summary>
+ /// Implementation of Keccak based on following KeccakNISTInterface.c from http://keccak.noekeon.org/
+ /// </summary>
+ /// <remarks>
+ /// Following the naming conventions used in the C source code to enable easy review of the implementation.
+ /// </remarks>
+ public class KeccakDigest
+ : IDigest, IMemoable
+ {
+ private static readonly ulong[] KeccakRoundConstants = KeccakInitializeRoundConstants();
+
+ private static readonly int[] KeccakRhoOffsets = KeccakInitializeRhoOffsets();
+
+ private static ulong[] KeccakInitializeRoundConstants()
+ {
+ ulong[] keccakRoundConstants = new ulong[24];
+ byte LFSRState = 0x01;
+
+ for (int i = 0; i < 24; i++)
+ {
+ keccakRoundConstants[i] = 0;
+ for (int j = 0; j < 7; j++)
+ {
+ int bitPosition = (1 << j) - 1;
+
+ // LFSR86540
+
+ bool loBit = (LFSRState & 0x01) != 0;
+ if (loBit)
+ {
+ keccakRoundConstants[i] ^= 1UL << bitPosition;
+ }
+
+ bool hiBit = (LFSRState & 0x80) != 0;
+ LFSRState <<= 1;
+ if (hiBit)
+ {
+ LFSRState ^= 0x71;
+ }
+
+ }
+ }
+
+ return keccakRoundConstants;
+ }
+
+ private static int[] KeccakInitializeRhoOffsets()
+ {
+ int[] keccakRhoOffsets = new int[25];
+ int x, y, t, newX, newY;
+
+ int rhoOffset = 0;
+ keccakRhoOffsets[(((0) % 5) + 5 * ((0) % 5))] = rhoOffset;
+ x = 1;
+ y = 0;
+ for (t = 1; t < 25; t++)
+ {
+ //rhoOffset = ((t + 1) * (t + 2) / 2) % 64;
+ rhoOffset = (rhoOffset + t) & 63;
+ keccakRhoOffsets[(((x) % 5) + 5 * ((y) % 5))] = rhoOffset;
+ newX = (0 * x + 1 * y) % 5;
+ newY = (2 * x + 3 * y) % 5;
+ x = newX;
+ y = newY;
+ }
+
+ return keccakRhoOffsets;
+ }
+
+ protected byte[] state = new byte[(1600 / 8)];
+ protected byte[] dataQueue = new byte[(1536 / 8)];
+ protected int rate;
+ protected int bitsInQueue;
+ protected int fixedOutputLength;
+ protected bool squeezing;
+ protected int bitsAvailableForSqueezing;
+ protected byte[] chunk;
+ protected byte[] oneByte;
+
+ private void ClearDataQueueSection(int off, int len)
+ {
+ for (int i = off; i != off + len; i++)
+ {
+ dataQueue[i] = 0;
+ }
+ }
+
+ public KeccakDigest()
+ : this(288)
+ {
+ }
+
+ public KeccakDigest(int bitLength)
+ {
+ Init(bitLength);
+ }
+
+ public KeccakDigest(KeccakDigest source)
+ {
+ CopyIn(source);
+ }
+
+ private void CopyIn(KeccakDigest source)
+ {
+ Array.Copy(source.state, 0, this.state, 0, source.state.Length);
+ Array.Copy(source.dataQueue, 0, this.dataQueue, 0, source.dataQueue.Length);
+ this.rate = source.rate;
+ this.bitsInQueue = source.bitsInQueue;
+ this.fixedOutputLength = source.fixedOutputLength;
+ this.squeezing = source.squeezing;
+ this.bitsAvailableForSqueezing = source.bitsAvailableForSqueezing;
+ this.chunk = Arrays.Clone(source.chunk);
+ this.oneByte = Arrays.Clone(source.oneByte);
+ }
+
+ public virtual string AlgorithmName
+ {
+ get { return "Keccak-" + fixedOutputLength; }
+ }
+
+ public virtual int GetDigestSize()
+ {
+ return fixedOutputLength / 8;
+ }
+
+ public virtual void Update(byte input)
+ {
+ oneByte[0] = input;
+
+ Absorb(oneByte, 0, 8L);
+ }
+
+ public virtual void BlockUpdate(byte[] input, int inOff, int len)
+ {
+ Absorb(input, inOff, len * 8L);
+ }
+
+ public virtual int DoFinal(byte[] output, int outOff)
+ {
+ Squeeze(output, outOff, fixedOutputLength);
+
+ Reset();
+
+ return GetDigestSize();
+ }
+
+ /*
+ * TODO Possible API change to support partial-byte suffixes.
+ */
+ protected virtual int DoFinal(byte[] output, int outOff, byte partialByte, int partialBits)
+ {
+ if (partialBits > 0)
+ {
+ oneByte[0] = partialByte;
+ Absorb(oneByte, 0, partialBits);
+ }
+
+ Squeeze(output, outOff, fixedOutputLength);
+
+ Reset();
+
+ return GetDigestSize();
+ }
+
+ public virtual void Reset()
+ {
+ Init(fixedOutputLength);
+ }
+
+ /**
+ * Return the size of block that the compression function is applied to in bytes.
+ *
+ * @return internal byte length of a block.
+ */
+ public virtual int GetByteLength()
+ {
+ return rate / 8;
+ }
+
+ private void Init(int bitLength)
+ {
+ switch (bitLength)
+ {
+ case 128:
+ InitSponge(1344, 256);
+ break;
+ case 224:
+ InitSponge(1152, 448);
+ break;
+ case 256:
+ InitSponge(1088, 512);
+ break;
+ case 288:
+ InitSponge(1024, 576);
+ break;
+ case 384:
+ InitSponge(832, 768);
+ break;
+ case 512:
+ InitSponge(576, 1024);
+ break;
+ default:
+ throw new ArgumentException("must be one of 128, 224, 256, 288, 384, or 512.", "bitLength");
+ }
+ }
+
+ private void InitSponge(int rate, int capacity)
+ {
+ if (rate + capacity != 1600)
+ {
+ throw new InvalidOperationException("rate + capacity != 1600");
+ }
+ if ((rate <= 0) || (rate >= 1600) || ((rate % 64) != 0))
+ {
+ throw new InvalidOperationException("invalid rate value");
+ }
+
+ this.rate = rate;
+ // this is never read, need to check to see why we want to save it
+ // this.capacity = capacity;
+ this.fixedOutputLength = 0;
+ Arrays.Fill(this.state, (byte)0);
+ Arrays.Fill(this.dataQueue, (byte)0);
+ this.bitsInQueue = 0;
+ this.squeezing = false;
+ this.bitsAvailableForSqueezing = 0;
+ this.fixedOutputLength = capacity / 2;
+ this.chunk = new byte[rate / 8];
+ this.oneByte = new byte[1];
+ }
+
+ private void AbsorbQueue()
+ {
+ KeccakAbsorb(state, dataQueue, rate / 8);
+
+ bitsInQueue = 0;
+ }
+
+ protected virtual void Absorb(byte[] data, int off, long databitlen)
+ {
+ long i, j, wholeBlocks;
+
+ if ((bitsInQueue % 8) != 0)
+ {
+ throw new InvalidOperationException("attempt to absorb with odd length queue.");
+ }
+ if (squeezing)
+ {
+ throw new InvalidOperationException("attempt to absorb while squeezing.");
+ }
+
+ i = 0;
+ while (i < databitlen)
+ {
+ if ((bitsInQueue == 0) && (databitlen >= rate) && (i <= (databitlen - rate)))
+ {
+ wholeBlocks = (databitlen - i) / rate;
+
+ for (j = 0; j < wholeBlocks; j++)
+ {
+ Array.Copy(data, (int)(off + (i / 8) + (j * chunk.Length)), chunk, 0, chunk.Length);
+
+ KeccakAbsorb(state, chunk, chunk.Length);
+ }
+
+ i += wholeBlocks * rate;
+ }
+ else
+ {
+ int partialBlock = (int)(databitlen - i);
+ if (partialBlock + bitsInQueue > rate)
+ {
+ partialBlock = rate - bitsInQueue;
+ }
+ int partialByte = partialBlock % 8;
+ partialBlock -= partialByte;
+ Array.Copy(data, off + (int)(i / 8), dataQueue, bitsInQueue / 8, partialBlock / 8);
+
+ bitsInQueue += partialBlock;
+ i += partialBlock;
+ if (bitsInQueue == rate)
+ {
+ AbsorbQueue();
+ }
+ if (partialByte > 0)
+ {
+ int mask = (1 << partialByte) - 1;
+ dataQueue[bitsInQueue / 8] = (byte)(data[off + ((int)(i / 8))] & mask);
+ bitsInQueue += partialByte;
+ i += partialByte;
+ }
+ }
+ }
+ }
+
+ private void PadAndSwitchToSqueezingPhase()
+ {
+ if (bitsInQueue + 1 == rate)
+ {
+ dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
+ AbsorbQueue();
+ ClearDataQueueSection(0, rate / 8);
+ }
+ else
+ {
+ ClearDataQueueSection((bitsInQueue + 7) / 8, rate / 8 - (bitsInQueue + 7) / 8);
+ dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
+ }
+ dataQueue[(rate - 1) / 8] |= (byte)(1U << ((rate - 1) % 8));
+ AbsorbQueue();
+
+ if (rate == 1024)
+ {
+ KeccakExtract1024bits(state, dataQueue);
+ bitsAvailableForSqueezing = 1024;
+ }
+ else
+ {
+ KeccakExtract(state, dataQueue, rate / 64);
+ bitsAvailableForSqueezing = rate;
+ }
+
+ squeezing = true;
+ }
+
+ protected virtual void Squeeze(byte[] output, int offset, long outputLength)
+ {
+ long i;
+ int partialBlock;
+
+ if (!squeezing)
+ {
+ PadAndSwitchToSqueezingPhase();
+ }
+ if ((outputLength % 8) != 0)
+ {
+ throw new InvalidOperationException("outputLength not a multiple of 8");
+ }
+
+ i = 0;
+ while (i < outputLength)
+ {
+ if (bitsAvailableForSqueezing == 0)
+ {
+ KeccakPermutation(state);
+
+ if (rate == 1024)
+ {
+ KeccakExtract1024bits(state, dataQueue);
+ bitsAvailableForSqueezing = 1024;
+ }
+ else
+ {
+ KeccakExtract(state, dataQueue, rate / 64);
+ bitsAvailableForSqueezing = rate;
+ }
+ }
+ partialBlock = bitsAvailableForSqueezing;
+ if ((long)partialBlock > outputLength - i)
+ {
+ partialBlock = (int)(outputLength - i);
+ }
+
+ Array.Copy(dataQueue, (rate - bitsAvailableForSqueezing) / 8, output, offset + (int)(i / 8), partialBlock / 8);
+ bitsAvailableForSqueezing -= partialBlock;
+ i += partialBlock;
+ }
+ }
+
+ private static void FromBytesToWords(ulong[] stateAsWords, byte[] state)
+ {
+ for (int i = 0; i < (1600 / 64); i++)
+ {
+ stateAsWords[i] = 0;
+ int index = i * (64 / 8);
+ for (int j = 0; j < (64 / 8); j++)
+ {
+ stateAsWords[i] |= ((ulong)state[index + j] & 0xff) << ((8 * j));
+ }
+ }
+ }
+
+ private static void FromWordsToBytes(byte[] state, ulong[] stateAsWords)
+ {
+ for (int i = 0; i < (1600 / 64); i++)
+ {
+ int index = i * (64 / 8);
+ for (int j = 0; j < (64 / 8); j++)
+ {
+ state[index + j] = (byte)(stateAsWords[i] >> (8 * j));
+ }
+ }
+ }
+
+ private void KeccakPermutation(byte[] state)
+ {
+ ulong[] longState = new ulong[state.Length / 8];
+
+ FromBytesToWords(longState, state);
+
+ KeccakPermutationOnWords(longState);
+
+ FromWordsToBytes(state, longState);
+ }
+
+ private void KeccakPermutationAfterXor(byte[] state, byte[] data, int dataLengthInBytes)
+ {
+ for (int i = 0; i < dataLengthInBytes; i++)
+ {
+ state[i] ^= data[i];
+ }
+
+ KeccakPermutation(state);
+ }
+
+ private void KeccakPermutationOnWords(ulong[] state)
+ {
+ int i;
+
+ for (i = 0; i < 24; i++)
+ {
+ Theta(state);
+ Rho(state);
+ Pi(state);
+ Chi(state);
+ Iota(state, i);
+ }
+ }
+
+ ulong[] C = new ulong[5];
+
+ private void Theta(ulong[] A)
+ {
+ for (int x = 0; x < 5; x++)
+ {
+ C[x] = 0;
+ for (int y = 0; y < 5; y++)
+ {
+ C[x] ^= A[x + 5 * y];
+ }
+ }
+ for (int x = 0; x < 5; x++)
+ {
+ ulong dX = ((((C[(x + 1) % 5]) << 1) ^ ((C[(x + 1) % 5]) >> (64 - 1)))) ^ C[(x + 4) % 5];
+ for (int y = 0; y < 5; y++)
+ {
+ A[x + 5 * y] ^= dX;
+ }
+ }
+ }
+
+ private void Rho(ulong[] A)
+ {
+ for (int x = 0; x < 5; x++)
+ {
+ for (int y = 0; y < 5; y++)
+ {
+ int index = x + 5 * y;
+ A[index] = ((KeccakRhoOffsets[index] != 0) ? (((A[index]) << KeccakRhoOffsets[index]) ^ ((A[index]) >> (64 - KeccakRhoOffsets[index]))) : A[index]);
+ }
+ }
+ }
+
+ ulong[] tempA = new ulong[25];
+
+ private void Pi(ulong[] A)
+ {
+ Array.Copy(A, 0, tempA, 0, tempA.Length);
+
+ for (int x = 0; x < 5; x++)
+ {
+ for (int y = 0; y < 5; y++)
+ {
+ A[y + 5 * ((2 * x + 3 * y) % 5)] = tempA[x + 5 * y];
+ }
+ }
+ }
+
+ ulong[] chiC = new ulong[5];
+
+ private void Chi(ulong[] A)
+ {
+ for (int y = 0; y < 5; y++)
+ {
+ for (int x = 0; x < 5; x++)
+ {
+ chiC[x] = A[x + 5 * y] ^ ((~A[(((x + 1) % 5) + 5 * y)]) & A[(((x + 2) % 5) + 5 * y)]);
+ }
+ for (int x = 0; x < 5; x++)
+ {
+ A[x + 5 * y] = chiC[x];
+ }
+ }
+ }
+
+ private static void Iota(ulong[] A, int indexRound)
+ {
+ A[(((0) % 5) + 5 * ((0) % 5))] ^= KeccakRoundConstants[indexRound];
+ }
+
+ private void KeccakAbsorb(byte[] byteState, byte[] data, int dataInBytes)
+ {
+ KeccakPermutationAfterXor(byteState, data, dataInBytes);
+ }
+
+ private void KeccakExtract1024bits(byte[] byteState, byte[] data)
+ {
+ Array.Copy(byteState, 0, data, 0, 128);
+ }
+
+ private void KeccakExtract(byte[] byteState, byte[] data, int laneCount)
+ {
+ Array.Copy(byteState, 0, data, 0, laneCount * 8);
+ }
+
+ public virtual IMemoable Copy()
+ {
+ return new KeccakDigest(this);
+ }
+
+ public virtual void Reset(IMemoable other)
+ {
+ KeccakDigest d = (KeccakDigest)other;
+
+ CopyIn(d);
+ }
+ }
+}
diff --git a/crypto/src/crypto/digests/SHA3Digest.cs b/crypto/src/crypto/digests/SHA3Digest.cs
index 2c6837b3c..890b665cf 100644
--- a/crypto/src/crypto/digests/SHA3Digest.cs
+++ b/crypto/src/crypto/digests/SHA3Digest.cs
@@ -1,4 +1,5 @@
using System;
+using System.Diagnostics;
using Org.BouncyCastle.Utilities;
@@ -11,550 +12,75 @@ namespace Org.BouncyCastle.Crypto.Digests
/// Following the naming conventions used in the C source code to enable easy review of the implementation.
/// </remarks>
public class Sha3Digest
- : IDigest, IMemoable
+ : KeccakDigest
{
- private static readonly ulong[] KeccakRoundConstants = KeccakInitializeRoundConstants();
-
- private static readonly int[] KeccakRhoOffsets = KeccakInitializeRhoOffsets();
-
- private static ulong[] KeccakInitializeRoundConstants()
- {
- ulong[] keccakRoundConstants = new ulong[24];
- byte LFSRState = 0x01;
-
- for (int i = 0; i < 24; i++)
- {
- keccakRoundConstants[i] = 0;
- for (int j = 0; j < 7; j++)
- {
- int bitPosition = (1 << j) - 1;
-
- // LFSR86540
-
- bool loBit = (LFSRState & 0x01) != 0;
- if (loBit)
- {
- keccakRoundConstants[i] ^= 1UL << bitPosition;
- }
-
- bool hiBit = (LFSRState & 0x80) != 0;
- LFSRState <<= 1;
- if (hiBit)
- {
- LFSRState ^= 0x71;
- }
-
- }
- }
-
- return keccakRoundConstants;
- }
-
- private static int[] KeccakInitializeRhoOffsets()
- {
- int[] keccakRhoOffsets = new int[25];
- int x, y, t, newX, newY;
-
- int rhoOffset = 0;
- keccakRhoOffsets[(((0) % 5) + 5 * ((0) % 5))] = rhoOffset;
- x = 1;
- y = 0;
- for (t = 1; t < 25; t++)
- {
- //rhoOffset = ((t + 1) * (t + 2) / 2) % 64;
- rhoOffset = (rhoOffset + t) & 63;
- keccakRhoOffsets[(((x) % 5) + 5 * ((y) % 5))] = rhoOffset;
- newX = (0 * x + 1 * y) % 5;
- newY = (2 * x + 3 * y) % 5;
- x = newX;
- y = newY;
- }
-
- return keccakRhoOffsets;
- }
-
- private byte[] state = new byte[(1600 / 8)];
- private byte[] dataQueue = new byte[(1536 / 8)];
- private int rate;
- private int bitsInQueue;
- private int fixedOutputLength;
- private bool squeezing;
- private int bitsAvailableForSqueezing;
- private byte[] chunk;
- private byte[] oneByte;
-
- private void ClearDataQueueSection(int off, int len)
- {
- for (int i = off; i != off + len; i++)
- {
- dataQueue[i] = 0;
- }
- }
-
- public Sha3Digest()
- {
- Init(0);
- }
-
- public Sha3Digest(int bitLength)
- {
- Init(bitLength);
- }
-
- public Sha3Digest(Sha3Digest source)
- {
- CopyIn(source);
- }
-
- private void CopyIn(Sha3Digest source)
- {
- Array.Copy(source.state, 0, this.state, 0, source.state.Length);
- Array.Copy(source.dataQueue, 0, this.dataQueue, 0, source.dataQueue.Length);
- this.rate = source.rate;
- this.bitsInQueue = source.bitsInQueue;
- this.fixedOutputLength = source.fixedOutputLength;
- this.squeezing = source.squeezing;
- this.bitsAvailableForSqueezing = source.bitsAvailableForSqueezing;
- this.chunk = Arrays.Clone(source.chunk);
- this.oneByte = Arrays.Clone(source.oneByte);
- }
-
- public virtual string AlgorithmName
- {
- get { return "SHA3-" + fixedOutputLength; }
- }
-
- public virtual int GetDigestSize()
- {
- return fixedOutputLength / 8;
- }
-
- public virtual void Update(byte input)
- {
- oneByte[0] = input;
-
- DoUpdate(oneByte, 0, 8L);
- }
-
- public virtual void BlockUpdate(byte[] input, int inOff, int len)
- {
- DoUpdate(input, inOff, len * 8L);
- }
-
- public virtual int DoFinal(byte[] output, int outOff)
- {
- Squeeze(output, outOff, fixedOutputLength);
-
- Reset();
-
- return GetDigestSize();
- }
-
- public virtual void Reset()
- {
- Init(fixedOutputLength);
- }
-
- /**
- * Return the size of block that the compression function is applied to in bytes.
- *
- * @return internal byte length of a block.
- */
- public virtual int GetByteLength()
- {
- return rate / 8;
- }
-
- private void Init(int bitLength)
+ private static int CheckBitLength(int bitLength)
{
switch (bitLength)
{
- case 0:
- case 288:
- InitSponge(1024, 576);
- break;
case 224:
- InitSponge(1152, 448);
- break;
case 256:
- InitSponge(1088, 512);
- break;
case 384:
- InitSponge(832, 768);
- break;
case 512:
- InitSponge(576, 1024);
- break;
+ return bitLength;
default:
- throw new ArgumentException("must be one of 224, 256, 384, or 512.", "bitLength");
- }
- }
-
- private void DoUpdate(byte[] data, int off, long databitlen)
- {
- if ((databitlen % 8) == 0)
- {
- Absorb(data, off, databitlen);
- }
- else
- {
- Absorb(data, off, databitlen - (databitlen % 8));
-
- byte[] lastByte = new byte[1];
-
- lastByte[0] = (byte)(data[off + (int)(databitlen / 8)] >> (int)(8 - (databitlen % 8)));
- Absorb(lastByte, off, databitlen % 8);
- }
- }
-
- private void InitSponge(int rate, int capacity)
- {
- if (rate + capacity != 1600)
- {
- throw new InvalidOperationException("rate + capacity != 1600");
- }
- if ((rate <= 0) || (rate >= 1600) || ((rate % 64) != 0))
- {
- throw new InvalidOperationException("invalid rate value");
- }
-
- this.rate = rate;
- // this is never read, need to check to see why we want to save it
- // this.capacity = capacity;
- this.fixedOutputLength = 0;
- Arrays.Fill(this.state, (byte)0);
- Arrays.Fill(this.dataQueue, (byte)0);
- this.bitsInQueue = 0;
- this.squeezing = false;
- this.bitsAvailableForSqueezing = 0;
- this.fixedOutputLength = capacity / 2;
- this.chunk = new byte[rate / 8];
- this.oneByte = new byte[1];
- }
-
- private void AbsorbQueue()
- {
- KeccakAbsorb(state, dataQueue, rate / 8);
-
- bitsInQueue = 0;
- }
-
- private void Absorb(byte[] data, int off, long databitlen)
- {
- long i, j, wholeBlocks;
-
- if ((bitsInQueue % 8) != 0)
- {
- throw new InvalidOperationException("attempt to absorb with odd length queue.");
- }
- if (squeezing)
- {
- throw new InvalidOperationException("attempt to absorb while squeezing.");
- }
-
- i = 0;
- while (i < databitlen)
- {
- if ((bitsInQueue == 0) && (databitlen >= rate) && (i <= (databitlen - rate)))
- {
- wholeBlocks = (databitlen - i) / rate;
-
- for (j = 0; j < wholeBlocks; j++)
- {
- Array.Copy(data, (int)(off + (i / 8) + (j * chunk.Length)), chunk, 0, chunk.Length);
-
- //displayIntermediateValues.displayBytes(1, "Block to be absorbed", curData, rate / 8);
-
- KeccakAbsorb(state, chunk, chunk.Length);
- }
-
- i += wholeBlocks * rate;
- }
- else
- {
- int partialBlock = (int)(databitlen - i);
- if (partialBlock + bitsInQueue > rate)
- {
- partialBlock = rate - bitsInQueue;
- }
- int partialByte = partialBlock % 8;
- partialBlock -= partialByte;
- Array.Copy(data, off + (int)(i / 8), dataQueue, bitsInQueue / 8, partialBlock / 8);
-
- bitsInQueue += partialBlock;
- i += partialBlock;
- if (bitsInQueue == rate)
- {
- AbsorbQueue();
- }
- if (partialByte > 0)
- {
- int mask = (1 << partialByte) - 1;
- dataQueue[bitsInQueue / 8] = (byte)(data[off + ((int)(i / 8))] & mask);
- bitsInQueue += partialByte;
- i += partialByte;
- }
- }
+ throw new ArgumentException(bitLength + " not supported for SHA-3", "bitLength");
}
}
- private void PadAndSwitchToSqueezingPhase()
- {
- if (bitsInQueue + 1 == rate)
- {
- dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
- AbsorbQueue();
- ClearDataQueueSection(0, rate / 8);
- }
- else
- {
- ClearDataQueueSection((bitsInQueue + 7) / 8, rate / 8 - (bitsInQueue + 7) / 8);
- dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
- }
- dataQueue[(rate - 1) / 8] |= (byte)(1U << ((rate - 1) % 8));
- AbsorbQueue();
-
- //displayIntermediateValues.displayText(1, "--- Switching to squeezing phase ---");
-
- if (rate == 1024)
- {
- KeccakExtract1024bits(state, dataQueue);
- bitsAvailableForSqueezing = 1024;
- }
- else
- {
- KeccakExtract(state, dataQueue, rate / 64);
- bitsAvailableForSqueezing = rate;
- }
-
- //displayIntermediateValues.displayBytes(1, "Block available for squeezing", dataQueue, bitsAvailableForSqueezing / 8);
-
- squeezing = true;
- }
-
- private void Squeeze(byte[] output, int offset, long outputLength)
- {
- long i;
- int partialBlock;
-
- if (!squeezing)
- {
- PadAndSwitchToSqueezingPhase();
- }
- if ((outputLength % 8) != 0)
- {
- throw new InvalidOperationException("outputLength not a multiple of 8");
- }
-
- i = 0;
- while (i < outputLength)
- {
- if (bitsAvailableForSqueezing == 0)
- {
- KeccakPermutation(state);
-
- if (rate == 1024)
- {
- KeccakExtract1024bits(state, dataQueue);
- bitsAvailableForSqueezing = 1024;
- }
- else
-
- {
- KeccakExtract(state, dataQueue, rate / 64);
- bitsAvailableForSqueezing = rate;
- }
-
- //displayIntermediateValues.displayBytes(1, "Block available for squeezing", dataQueue, bitsAvailableForSqueezing / 8);
-
- }
- partialBlock = bitsAvailableForSqueezing;
- if ((long)partialBlock > outputLength - i)
- {
- partialBlock = (int)(outputLength - i);
- }
-
- Array.Copy(dataQueue, (rate - bitsAvailableForSqueezing) / 8, output, offset + (int)(i / 8), partialBlock / 8);
- bitsAvailableForSqueezing -= partialBlock;
- i += partialBlock;
- }
- }
-
- private static void FromBytesToWords(ulong[] stateAsWords, byte[] state)
- {
- for (int i = 0; i < (1600 / 64); i++)
- {
- stateAsWords[i] = 0;
- int index = i * (64 / 8);
- for (int j = 0; j < (64 / 8); j++)
- {
- stateAsWords[i] |= ((ulong)state[index + j] & 0xff) << ((8 * j));
- }
- }
- }
-
- private static void FromWordsToBytes(byte[] state, ulong[] stateAsWords)
+ public Sha3Digest()
+ : this(256)
{
- for (int i = 0; i < (1600 / 64); i++)
- {
- int index = i * (64 / 8);
- for (int j = 0; j < (64 / 8); j++)
- {
- state[index + j] = (byte)(stateAsWords[i] >> (8 * j));
- }
- }
}
- private void KeccakPermutation(byte[] state)
+ public Sha3Digest(int bitLength)
+ : base(CheckBitLength(bitLength))
{
- ulong[] longState = new ulong[state.Length / 8];
-
- FromBytesToWords(longState, state);
-
- //displayIntermediateValues.displayStateAsBytes(1, "Input of permutation", longState);
-
- KeccakPermutationOnWords(longState);
-
- //displayIntermediateValues.displayStateAsBytes(1, "State after permutation", longState);
-
- FromWordsToBytes(state, longState);
}
- private void KeccakPermutationAfterXor(byte[] state, byte[] data, int dataLengthInBytes)
+ public Sha3Digest(Sha3Digest source)
+ : base(source)
{
- for (int i = 0; i < dataLengthInBytes; i++)
- {
- state[i] ^= data[i];
- }
-
- KeccakPermutation(state);
}
- private void KeccakPermutationOnWords(ulong[] state)
+ public override string AlgorithmName
{
- int i;
-
- //displayIntermediateValues.displayStateAs64bitWords(3, "Same, with lanes as 64-bit words", state);
-
- for (i = 0; i < 24; i++)
- {
- //displayIntermediateValues.displayRoundNumber(3, i);
-
- Theta(state);
- //displayIntermediateValues.displayStateAs64bitWords(3, "After theta", state);
-
- Rho(state);
- //displayIntermediateValues.displayStateAs64bitWords(3, "After rho", state);
-
- Pi(state);
- //displayIntermediateValues.displayStateAs64bitWords(3, "After pi", state);
-
- Chi(state);
- //displayIntermediateValues.displayStateAs64bitWords(3, "After chi", state);
-
- Iota(state, i);
- //displayIntermediateValues.displayStateAs64bitWords(3, "After iota", state);
- }
+ get { return "SHA3-" + fixedOutputLength; }
}
- ulong[] C = new ulong[5];
-
- private void Theta(ulong[] A)
+ public override int DoFinal(byte[] output, int outOff)
{
- for (int x = 0; x < 5; x++)
- {
- C[x] = 0;
- for (int y = 0; y < 5; y++)
- {
- C[x] ^= A[x + 5 * y];
- }
- }
- for (int x = 0; x < 5; x++)
- {
- ulong dX = ((((C[(x + 1) % 5]) << 1) ^ ((C[(x + 1) % 5]) >> (64 - 1)))) ^ C[(x + 4) % 5];
- for (int y = 0; y < 5; y++)
- {
- A[x + 5 * y] ^= dX;
- }
- }
- }
+ Absorb(new byte[]{ 0x02 }, 0, 2);
- private void Rho(ulong[] A)
- {
- for (int x = 0; x < 5; x++)
- {
- for (int y = 0; y < 5; y++)
- {
- int index = x + 5 * y;
- A[index] = ((KeccakRhoOffsets[index] != 0) ? (((A[index]) << KeccakRhoOffsets[index]) ^ ((A[index]) >> (64 - KeccakRhoOffsets[index]))) : A[index]);
- }
- }
+ return base.DoFinal(output, outOff);
}
- ulong[] tempA = new ulong[25];
-
- private void Pi(ulong[] A)
+ /*
+ * TODO Possible API change to support partial-byte suffixes.
+ */
+ protected override int DoFinal(byte[] output, int outOff, byte partialByte, int partialBits)
{
- Array.Copy(A, 0, tempA, 0, tempA.Length);
-
- for (int x = 0; x < 5; x++)
- {
- for (int y = 0; y < 5; y++)
- {
- A[y + 5 * ((2 * x + 3 * y) % 5)] = tempA[x + 5 * y];
- }
- }
- }
+ if (partialBits < 0 || partialBits > 7)
+ throw new ArgumentException("must be in the range [0,7]", "partialBits");
- ulong[] chiC = new ulong[5];
+ int finalInput = (partialByte & ((1 << partialBits) - 1)) | (0x02 << partialBits);
+ Debug.Assert(finalInput >= 0);
+ int finalBits = partialBits + 2;
- private void Chi(ulong[] A)
- {
- for (int y = 0; y < 5; y++)
+ if (finalBits >= 8)
{
- for (int x = 0; x < 5; x++)
- {
- chiC[x] = A[x + 5 * y] ^ ((~A[(((x + 1) % 5) + 5 * y)]) & A[(((x + 2) % 5) + 5 * y)]);
- }
- for (int x = 0; x < 5; x++)
- {
- A[x + 5 * y] = chiC[x];
- }
+ oneByte[0] = (byte)finalInput;
+ Absorb(oneByte, 0, 8);
+ finalBits -= 8;
+ finalInput >>= 8;
}
- }
-
- private static void Iota(ulong[] A, int indexRound)
- {
- A[(((0) % 5) + 5 * ((0) % 5))] ^= KeccakRoundConstants[indexRound];
- }
-
- private void KeccakAbsorb(byte[] byteState, byte[] data, int dataInBytes)
- {
- KeccakPermutationAfterXor(byteState, data, dataInBytes);
- }
-
- private void KeccakExtract1024bits(byte[] byteState, byte[] data)
- {
- Array.Copy(byteState, 0, data, 0, 128);
- }
- private void KeccakExtract(byte[] byteState, byte[] data, int laneCount)
- {
- Array.Copy(byteState, 0, data, 0, laneCount * 8);
+ return base.DoFinal(output, outOff, (byte)finalInput, finalBits);
}
- public IMemoable Copy()
+ public override IMemoable Copy()
{
return new Sha3Digest(this);
}
-
- public void Reset(IMemoable other)
- {
- Sha3Digest d = (Sha3Digest)other;
-
- CopyIn(d);
- }
-
-
}
}
diff --git a/crypto/src/crypto/digests/ShakeDigest.cs b/crypto/src/crypto/digests/ShakeDigest.cs
new file mode 100644
index 000000000..fd7d85681
--- /dev/null
+++ b/crypto/src/crypto/digests/ShakeDigest.cs
@@ -0,0 +1,111 @@
+using System;
+using System.Diagnostics;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Crypto.Digests
+{
+ /// <summary>
+ /// Implementation of SHAKE based on following KeccakNISTInterface.c from http://keccak.noekeon.org/
+ /// </summary>
+ /// <remarks>
+ /// Following the naming conventions used in the C source code to enable easy review of the implementation.
+ /// </remarks>
+ public class ShakeDigest
+ : KeccakDigest, IXof
+ {
+ private static int CheckBitLength(int bitLength)
+ {
+ switch (bitLength)
+ {
+ case 128:
+ case 256:
+ return bitLength;
+ default:
+ throw new ArgumentException(bitLength + " not supported for SHAKE", "bitLength");
+ }
+ }
+
+ public ShakeDigest()
+ : this(128)
+ {
+ }
+
+ public ShakeDigest(int bitLength)
+ : base(CheckBitLength(bitLength))
+ {
+ }
+
+ public ShakeDigest(ShakeDigest source)
+ : base(source)
+ {
+ }
+
+ public override string AlgorithmName
+ {
+ get { return "SHAKE" + fixedOutputLength; }
+ }
+
+ public override int DoFinal(byte[] output, int outOff)
+ {
+ return DoFinal(output, outOff, GetDigestSize());
+ }
+
+ public virtual int DoFinal(byte[] output, int outOff, int outLen)
+ {
+ Absorb(new byte[]{ 0x0F }, 0, 4);
+
+ Squeeze(output, outOff, ((long)outLen) * 8);
+
+ Reset();
+
+ return outLen;
+ }
+
+ /*
+ * TODO Possible API change to support partial-byte suffixes.
+ */
+ protected override int DoFinal(byte[] output, int outOff, byte partialByte, int partialBits)
+ {
+ return DoFinal(output, outOff, GetDigestSize(), partialByte, partialBits);
+ }
+
+ /*
+ * TODO Possible API change to support partial-byte suffixes.
+ */
+ protected virtual int DoFinal(byte[] output, int outOff, int outLen, byte partialByte, int partialBits)
+ {
+ if (partialBits < 0 || partialBits > 7)
+ throw new ArgumentException("must be in the range [0,7]", "partialBits");
+
+ int finalInput = (partialByte & ((1 << partialBits) - 1)) | (0x0F << partialBits);
+ Debug.Assert(finalInput >= 0);
+ int finalBits = partialBits + 4;
+
+ if (finalBits >= 8)
+ {
+ oneByte[0] = (byte)finalInput;
+ Absorb(oneByte, 0, 8);
+ finalBits -= 8;
+ finalInput >>= 8;
+ }
+
+ if (finalBits > 0)
+ {
+ oneByte[0] = (byte)finalInput;
+ Absorb(oneByte, 0, finalBits);
+ }
+
+ Squeeze(output, outOff, ((long)outLen) * 8);
+
+ Reset();
+
+ return outLen;
+ }
+
+ public override IMemoable Copy()
+ {
+ return new ShakeDigest(this);
+ }
+ }
+}
diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index b57977983..55d739f34 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -1,10 +1,14 @@
using System;
using Org.BouncyCastle.Crypto;
+using Org.BouncyCastle.Security;
using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Math
{
+ /**
+ * Utility methods for generating primes and testing for primality.
+ */
public static class Primes
{
private static readonly BigInteger One = BigInteger.One;
@@ -12,7 +16,54 @@ namespace Org.BouncyCastle.Math
private static readonly BigInteger Three = BigInteger.Three;
/**
- * Used to return the output from the {@linkplain #generateSTRandomPrime(Digest) Shawe-Taylor Random_Prime Routine}
+ * Used to return the output from the
+ * {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced
+ * Miller-Rabin Probabilistic Primality Test}
+ */
+ public class MROutput
+ {
+ internal static MROutput ProbablyPrime()
+ {
+ return new MROutput(false, null);
+ }
+
+ internal static MROutput ProvablyCompositeWithFactor(BigInteger factor)
+ {
+ return new MROutput(true, factor);
+ }
+
+ internal static MROutput ProvablyCompositeNotPrimePower()
+ {
+ return new MROutput(true, null);
+ }
+
+ private readonly bool mProvablyComposite;
+ private readonly BigInteger mFactor;
+
+ private MROutput(bool provablyComposite, BigInteger factor)
+ {
+ this.mProvablyComposite = provablyComposite;
+ this.mFactor = factor;
+ }
+
+ public BigInteger Factor
+ {
+ get { return mFactor; }
+ }
+
+ public bool IsProvablyComposite
+ {
+ get { return mProvablyComposite; }
+ }
+
+ public bool IsNotPrimePower
+ {
+ get { return mProvablyComposite && mFactor == null; }
+ }
+ }
+
+ /**
+ * Used to return the output from the {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime Routine}
*/
public class STOutput
{
@@ -51,11 +102,11 @@ namespace Org.BouncyCastle.Math
* @param hash
* the {@link Digest} instance to use (as "Hash()"). Cannot be null.
* @param length
- * the length (in bits) of the prime to be generated. Must be >= 2.
+ * the length (in bits) of the prime to be generated. Must be at least 2.
* @param inputSeed
* the seed to be used for the generation of the requested prime. Cannot be null or
* empty.
- * @returns an {@link STOutput} instance containing the requested prime.
+ * @return an {@link STOutput} instance containing the requested prime.
*/
public static STOutput GenerateSTRandomPrime(IDigest hash, int length, byte[] inputSeed)
{
@@ -71,6 +122,269 @@ namespace Org.BouncyCastle.Math
return ImplSTRandomPrime(hash, length, Arrays.Clone(inputSeed));
}
+ /**
+ * FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test
+ *
+ * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. This is an
+ * alternative to {@link #isMRProbablePrime(BigInteger, SecureRandom, int)} that provides more
+ * information about a composite candidate, which may be useful when generating or validating
+ * RSA moduli.
+ *
+ * @param candidate
+ * the {@link BigInteger} instance to test for primality.
+ * @param random
+ * the source of randomness to use to choose bases.
+ * @param iterations
+ * the number of randomly-chosen bases to perform the test for.
+ * @return an {@link MROutput} instance that can be further queried for details.
+ */
+ public static MROutput EnhancedMRProbablePrimeTest(BigInteger candidate, SecureRandom random, int iterations)
+ {
+ CheckCandidate(candidate, "candidate");
+
+ if (random == null)
+ throw new ArgumentNullException("random");
+ if (iterations < 1)
+ throw new ArgumentException("must be > 0", "iterations");
+
+ if (candidate.BitLength == 2)
+ return MROutput.ProbablyPrime();
+
+ if (!candidate.TestBit(0))
+ return MROutput.ProvablyCompositeWithFactor(Two);
+
+ BigInteger w = candidate;
+ BigInteger wSubOne = candidate.Subtract(One);
+ BigInteger wSubTwo = candidate.Subtract(Two);
+
+ int a = wSubOne.GetLowestSetBit();
+ BigInteger m = wSubOne.ShiftRight(a);
+
+ for (int i = 0; i < iterations; ++i)
+ {
+ BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
+ BigInteger g = b.Gcd(w);
+
+ if (g.CompareTo(One) > 0)
+ return MROutput.ProvablyCompositeWithFactor(g);
+
+ BigInteger z = b.ModPow(m, w);
+
+ if (z.Equals(One) || z.Equals(wSubOne))
+ continue;
+
+ bool primeToBase = false;
+
+ BigInteger x = z;
+ for (int j = 1; j < a; ++j)
+ {
+ z = z.ModPow(Two, w);
+
+ if (z.Equals(wSubOne))
+ {
+ primeToBase = true;
+ break;
+ }
+
+ if (z.Equals(One))
+ break;
+
+ x = z;
+ }
+
+ if (!primeToBase)
+ {
+ if (!z.Equals(One))
+ {
+ x = z;
+ z = z.ModPow(Two, w);
+
+ if (!z.Equals(One))
+ {
+ x = z;
+ }
+ }
+
+ g = x.Subtract(One).Gcd(w);
+
+ if (g.CompareTo(One) > 0)
+ return MROutput.ProvablyCompositeWithFactor(g);
+
+ return MROutput.ProvablyCompositeNotPrimePower();
+ }
+ }
+
+ return MROutput.ProbablyPrime();
+ }
+
+ /**
+ * A fast check for small divisors, up to some implementation-specific limit.
+ *
+ * @param candidate
+ * the {@link BigInteger} instance to test for division by small factors.
+ *
+ * @return <code>true</code> if the candidate is found to have any small factors,
+ * <code>false</code> otherwise.
+ */
+ public static bool HasAnySmallFactors(BigInteger candidate)
+ {
+ CheckCandidate(candidate, "candidate");
+
+ return ImplHasAnySmallFactors(candidate);
+ }
+
+ /**
+ * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test
+ *
+ * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases.
+ *
+ * @param candidate
+ * the {@link BigInteger} instance to test for primality.
+ * @param random
+ * the source of randomness to use to choose bases.
+ * @param iterations
+ * the number of randomly-chosen bases to perform the test for.
+ * @return <code>false</code> if any witness to compositeness is found amongst the chosen bases
+ * (so <code>candidate</code> is definitely NOT prime), or else <code>true</code>
+ * (indicating primality with some probability dependent on the number of iterations
+ * that were performed).
+ */
+ public static bool IsMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations)
+ {
+ CheckCandidate(candidate, "candidate");
+
+ if (random == null)
+ throw new ArgumentException("cannot be null", "random");
+ if (iterations < 1)
+ throw new ArgumentException("must be > 0", "iterations");
+
+ if (candidate.BitLength == 2)
+ return true;
+ if (!candidate.TestBit(0))
+ return false;
+
+ BigInteger w = candidate;
+ BigInteger wSubOne = candidate.Subtract(One);
+ BigInteger wSubTwo = candidate.Subtract(Two);
+
+ int a = wSubOne.GetLowestSetBit();
+ BigInteger m = wSubOne.ShiftRight(a);
+
+ for (int i = 0; i < iterations; ++i)
+ {
+ BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
+
+ if (!ImplMRProbablePrimeToBase(w, wSubOne, m, a, b))
+ return false;
+ }
+
+ return true;
+ }
+
+ /**
+ * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test (to a fixed base).
+ *
+ * Run a single iteration of the Miller-Rabin algorithm against the specified base.
+ *
+ * @param candidate
+ * the {@link BigInteger} instance to test for primality.
+ * @param baseValue
+ * the base value to use for this iteration.
+ * @return <code>false</code> if the specified base is a witness to compositeness (so
+ * <code>candidate</code> is definitely NOT prime), or else <code>true</code>.
+ */
+ public static bool IsMRProbablePrimeToBase(BigInteger candidate, BigInteger baseValue)
+ {
+ CheckCandidate(candidate, "candidate");
+ CheckCandidate(baseValue, "baseValue");
+
+ if (baseValue.CompareTo(candidate.Subtract(One)) >= 0)
+ throw new ArgumentException("must be < ('candidate' - 1)", "baseValue");
+
+ if (candidate.BitLength == 2)
+ return true;
+
+ BigInteger w = candidate;
+ BigInteger wSubOne = candidate.Subtract(One);
+
+ int a = wSubOne.GetLowestSetBit();
+ BigInteger m = wSubOne.ShiftRight(a);
+
+ return ImplMRProbablePrimeToBase(w, wSubOne, m, a, baseValue);
+ }
+
+ private static void CheckCandidate(BigInteger n, string name)
+ {
+ if (n == null || n.SignValue < 1 || n.BitLength < 2)
+ throw new ArgumentException("must be non-null and >= 2", name);
+ }
+
+ private static bool ImplHasAnySmallFactors(BigInteger x)
+ {
+ /*
+ * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
+ */
+ int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
+ int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
+ && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
+ {
+ m = 29 * 31 * 37 * 41 * 43;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
+ {
+ m = 47 * 53 * 59 * 61 * 67;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
+ {
+ m = 71 * 73 * 79 * 83;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
+ {
+ m = 89 * 97 * 101 * 103;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
+ {
+ m = 107 * 109 * 113 * 127;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
+ {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ }
+ return true;
+ }
+
+ private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b)
+ {
+ BigInteger z = b.ModPow(m, w);
+
+ if (z.Equals(One) || z.Equals(wSubOne))
+ return true;
+
+ bool result = false;
+
+ for (int j = 1; j < a; ++j)
+ {
+ z = z.ModPow(Two, w);
+
+ if (z.Equals(wSubOne))
+ {
+ result = true;
+ break;
+ }
+
+ if (z.Equals(One))
+ return false;
+ }
+
+ return result;
+ }
+
private static STOutput ImplSTRandomPrime(IDigest d, int length, byte[] primeSeed)
{
int dLen = d.GetDigestSize();
@@ -131,7 +445,7 @@ namespace Org.BouncyCastle.Math
/*
* TODO Since the candidate primes are generated by constant steps ('c0x2'),
- * sieving could be used here in place of the 'mightBePrime' approach.
+ * sieving could be used here in place of the 'HasAnySmallFactors' approach.
*/
for (;;)
{
@@ -149,7 +463,7 @@ namespace Org.BouncyCastle.Math
*
* NOTE: 'primeSeed' is still incremented as if we performed the full check!
*/
- if (MightBePrime(c))
+ if (!ImplHasAnySmallFactors(c))
{
BigInteger a = HashGen(d, primeSeed, iterations + 1);
a = a.Mod(c.Subtract(Three)).Add(Two);
@@ -266,45 +580,5 @@ namespace Org.BouncyCastle.Math
}
}
}
-
- private static bool MightBePrime(BigInteger x)
- {
- /*
- * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
- */
- int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
- int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
- && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
- {
- m = 29 * 31 * 37 * 41 * 43;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
- {
- m = 47 * 53 * 59 * 61 * 67;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
- {
- m = 71 * 73 * 79 * 83;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
- {
- m = 89 * 97 * 101 * 103;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
- {
- m = 107 * 109 * 113 * 127;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
- {
- return true;
- }
- }
- }
- }
- }
- }
- return false;
- }
}
}
|
