diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index b57977983..420c3cc5a 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -1,18 +1,69 @@
using System;
using Org.BouncyCastle.Crypto;
+using Org.BouncyCastle.Security;
using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Math
{
- public static class Primes
+ /**
+ * Utility methods for generating primes and testing for primality.
+ */
+ public abstract class Primes
{
private static readonly BigInteger One = BigInteger.One;
private static readonly BigInteger Two = BigInteger.Two;
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;
- }
}
}
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index 9fe9e32fd..40b46ce72 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -677,28 +677,110 @@ namespace Org.BouncyCastle.Math.EC
switch (this.CoordinateSystem)
{
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- if (X.IsZero)
+ case COORD_LAMBDA_AFFINE:
+ case COORD_LAMBDA_PROJECTIVE:
{
- if (!Y.Square().Equals(B))
- throw new ArgumentException();
+ if (X.IsZero)
+ {
+ if (!Y.Square().Equals(B))
+ throw new ArgumentException();
+ }
+ else
+ {
+ // Y becomes Lambda (X + Y/X) here
+ Y = Y.Divide(X).Add(X);
+ }
+ break;
}
- else
+ default:
{
- // Y becomes Lambda (X + Y/X) here
- Y = Y.Divide(X).Add(X);
+ break;
}
- break;
}
- default:
+
+ return CreateRawPoint(X, Y, withCompression);
+ }
+
+ protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
+ {
+ ECFieldElement xp = FromBigInteger(X1), yp = null;
+ if (xp.IsZero)
{
- break;
+ yp = B.Sqrt();
}
+ else
+ {
+ ECFieldElement beta = xp.Square().Invert().Multiply(B).Add(A).Add(xp);
+ ECFieldElement z = SolveQuadradicEquation(beta);
+
+ if (z != null)
+ {
+ if (z.TestBitZero() != (yTilde == 1))
+ {
+ z = z.AddOne();
+ }
+
+ switch (this.CoordinateSystem)
+ {
+ case COORD_LAMBDA_AFFINE:
+ case COORD_LAMBDA_PROJECTIVE:
+ {
+ yp = z.Add(xp);
+ break;
+ }
+ default:
+ {
+ yp = z.Multiply(xp);
+ break;
+ }
+ }
+ }
}
- return CreateRawPoint(X, Y, withCompression);
+ if (yp == null)
+ throw new ArgumentException("Invalid point compression");
+
+ return CreateRawPoint(xp, yp, true);
+ }
+
+ /**
+ * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
+ * D.1.6) The other solution is <code>z + 1</code>.
+ *
+ * @param beta
+ * The value to solve the qradratic equation for.
+ * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
+ * <code>null</code> if no solution exists.
+ */
+ private ECFieldElement SolveQuadradicEquation(ECFieldElement beta)
+ {
+ if (beta.IsZero)
+ return beta;
+
+ ECFieldElement gamma, z, zeroElement = FromBigInteger(BigInteger.Zero);
+
+ int m = FieldSize;
+ Random rand = new Random();
+ do
+ {
+ ECFieldElement t = FromBigInteger(new BigInteger(m, rand));
+ z = zeroElement;
+ ECFieldElement w = beta;
+ for (int i = 1; i < m; i++)
+ {
+ ECFieldElement w2 = w.Square();
+ z = z.Square().Add(w2.Multiply(t));
+ w = w2.Add(beta);
+ }
+ if (!w.IsZero)
+ {
+ return null;
+ }
+ gamma = z.Square().Add(z);
+ }
+ while (gamma.IsZero);
+
+ return z;
}
/**
@@ -994,92 +1076,6 @@ namespace Org.BouncyCastle.Math.EC
get { return m_infinity; }
}
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement xp = FromBigInteger(X1), yp = null;
- if (xp.IsZero)
- {
- yp = m_b.Sqrt();
- }
- else
- {
- ECFieldElement beta = xp.Square().Invert().Multiply(B).Add(A).Add(xp);
- ECFieldElement z = SolveQuadradicEquation(beta);
-
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- yp = z.Add(xp);
- break;
- }
- default:
- {
- yp = z.Multiply(xp);
- break;
- }
- }
- }
- }
-
- if (yp == null)
- throw new ArgumentException("Invalid point compression");
-
- return CreateRawPoint(xp, yp, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the qradratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadradicEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(m, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < m; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- {
- return null;
- }
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public int M
{
get { return m; }
diff --git a/crypto/src/math/ec/custom/sec/SecT113Field.cs b/crypto/src/math/ec/custom/sec/SecT113Field.cs
index dbb645e6f..640c6e787 100644
--- a/crypto/src/math/ec/custom/sec/SecT113Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113Field.cs
@@ -37,6 +37,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat128.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion
+
+ ulong[] t0 = Nat128.Create64();
+ ulong[] t1 = Nat128.Create64();
+
+ Square(x, t0);
+ Multiply(t0, x, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 3, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 7, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 14, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 28, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 56, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat128.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
index e3a923f62..f217e28cb 100644
--- a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT113FieldElement(
- AbstractF2mCurve.Inverse(113, new int[]{ 9 }, ToBigInteger()));
+ ulong[] z = Nat128.Create64();
+ SecT113Field.Invert(x, z);
+ return new SecT113FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs
index 04e69e2a8..2705c94aa 100644
--- a/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs
@@ -65,101 +65,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return new SecT113R1Point(this, x, y, zs, withCompression);
}
- public override bool IsKoblitz
+ public override bool IsKoblitz
{
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(113, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 113; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 113; }
diff --git a/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs
index a02db6b25..abfd26d5b 100644
--- a/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs
@@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(113, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 113; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 113; }
diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs
index 6a1d2a960..47f97078c 100644
--- a/crypto/src/math/ec/custom/sec/SecT131Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs
@@ -40,6 +40,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat192.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion
+
+ ulong[] t0 = Nat192.Create64();
+ ulong[] t1 = Nat192.Create64();
+
+ Square(x, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 2, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 4, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 8, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 16, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 32, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 65, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat192.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
index 65aaf01ba..0ea00ea07 100644
--- a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT131FieldElement(
- AbstractF2mCurve.Inverse(131, new int[] { 2, 3, 8 }, ToBigInteger()));
+ ulong[] z = Nat192.Create64();
+ SecT131Field.Invert(x, z);
+ return new SecT131FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs
index 789e3c0c3..b73964c39 100644
--- a/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs
@@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(131, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 131; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 131; }
diff --git a/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs
index 2004f84ca..724921c94 100644
--- a/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs
@@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(131, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 131; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 131; }
diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs
index 165d5b841..f921a5bc7 100644
--- a/crypto/src/math/ec/custom/sec/SecT163Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs
@@ -41,6 +41,47 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat192.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion with bases { 2, 3 }
+
+ ulong[] t0 = Nat192.Create64();
+ ulong[] t1 = Nat192.Create64();
+
+ Square(x, t0);
+
+ // 3 | 162
+ SquareN(t0, 1, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 1, t1);
+ Multiply(t0, t1, t0);
+
+ // 3 | 54
+ SquareN(t0, 3, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 3, t1);
+ Multiply(t0, t1, t0);
+
+ // 3 | 18
+ SquareN(t0, 9, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 9, t1);
+ Multiply(t0, t1, t0);
+
+ // 3 | 6
+ SquareN(t0, 27, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 27, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 2
+ SquareN(t0, 81, t1);
+ Multiply(t0, t1, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat192.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
index 3ab383a1d..c7a0b5639 100644
--- a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT163FieldElement(
- AbstractF2mCurve.Inverse(163, new int[] { 3, 6, 7 }, ToBigInteger()));
+ ulong[] z = Nat192.Create64();
+ SecT163Field.Invert(x, z);
+ return new SecT163FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs
index 1cfd09e1c..68ff646ca 100644
--- a/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs
@@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(163, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 163; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 163; }
diff --git a/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs
index fc18e1094..8ae58ccef 100644
--- a/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs
@@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(163, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 163; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 163; }
diff --git a/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs
index 9efe11c3e..5a4fa5ad1 100644
--- a/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs
@@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(163, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 163; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 163; }
diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs
index 85db061c3..5154f1e0a 100644
--- a/crypto/src/math/ec/custom/sec/SecT193Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs
@@ -44,6 +44,49 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat256.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion with bases { 2, 3 }
+
+ ulong[] t0 = Nat256.Create64();
+ ulong[] t1 = Nat256.Create64();
+
+ Square(x, t0);
+
+ // 3 | 192
+ SquareN(t0, 1, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 1, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 64
+ SquareN(t0, 3, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 32
+ SquareN(t0, 6, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 16
+ SquareN(t0, 12, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 8
+ SquareN(t0, 24, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 4
+ SquareN(t0, 48, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 2
+ SquareN(t0, 96, t1);
+ Multiply(t0, t1, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
index 995d2ebdd..eba4d10e6 100644
--- a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT193FieldElement(
- AbstractF2mCurve.Inverse(193, new int[] { 15 }, ToBigInteger()));
+ ulong[] z = Nat256.Create64();
+ SecT193Field.Invert(x, z);
+ return new SecT193FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs
index 802954b01..a2cb5a8ac 100644
--- a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs
@@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(193, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 193; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 193; }
diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs
index b5345730c..1c84a3eac 100644
--- a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs
@@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(193, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 193; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 193; }
diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs
index b36ffba2e..a2f73fd5d 100644
--- a/crypto/src/math/ec/custom/sec/SecT233Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs
@@ -45,6 +45,39 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat256.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion
+
+ ulong[] t0 = Nat256.Create64();
+ ulong[] t1 = Nat256.Create64();
+
+ Square(x, t0);
+ Multiply(t0, x, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 3, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 7, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 14, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 29, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 58, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 116, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
index 60b204604..a9041efde 100644
--- a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT233FieldElement(
- AbstractF2mCurve.Inverse(233, new int[] { 74 }, ToBigInteger()));
+ ulong[] z = Nat256.Create64();
+ SecT233Field.Invert(x, z);
+ return new SecT233FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs
index 8768eaa81..72935913d 100644
--- a/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs
@@ -76,98 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(233, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 233; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 233; }
diff --git a/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs
index 92795b8a7..db6e6e1d4 100644
--- a/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs
@@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(233, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 233; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 233; }
diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs
index 6dab907dd..6b8ad696f 100644
--- a/crypto/src/math/ec/custom/sec/SecT239Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs
@@ -45,6 +45,43 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat256.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion
+
+ ulong[] t0 = Nat256.Create64();
+ ulong[] t1 = Nat256.Create64();
+
+ Square(x, t0);
+ Multiply(t0, x, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 3, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 7, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 14, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 29, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 59, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 119, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
index e7bfffd1f..de074c55f 100644
--- a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT239FieldElement(
- AbstractF2mCurve.Inverse(239, new int[] { 158 }, ToBigInteger()));
+ ulong[] z = Nat256.Create64();
+ SecT239Field.Invert(x, z);
+ return new SecT239FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs
index 2c73d941f..a499d48b4 100644
--- a/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs
@@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(239, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 239; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 239; }
diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs
index 435787467..903ea02ff 100644
--- a/crypto/src/math/ec/custom/sec/SecT283Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs
@@ -48,6 +48,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat320.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion
+
+ ulong[] t0 = Nat320.Create64();
+ ulong[] t1 = Nat320.Create64();
+
+ Square(x, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 2, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 4, t0);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 8, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, t1);
+ Multiply(t1, x, t1);
+ SquareN(t1, 17, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 35, t1);
+ Multiply(t1, t0, t1);
+ SquareN(t1, 70, t0);
+ Multiply(t0, t1, t0);
+ Square(t0, t0);
+ Multiply(t0, x, t0);
+ SquareN(t0, 141, t1);
+ Multiply(t1, t0, t1);
+ Square(t1, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat320.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
index 9181b8685..e02108f73 100644
--- a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT283FieldElement(
- AbstractF2mCurve.Inverse(283, new int[] { 5, 7, 12 }, ToBigInteger()));
+ ulong[] z = Nat320.Create64();
+ SecT283Field.Invert(x, z);
+ return new SecT283FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs
index 42414401f..4053287ec 100644
--- a/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs
@@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(283, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 283; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 283; }
diff --git a/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs
index d8c462eeb..e659675ce 100644
--- a/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs
@@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(283, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 283; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 283; }
diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs
index ce6f43f2e..84eada96e 100644
--- a/crypto/src/math/ec/custom/sec/SecT409Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs
@@ -47,6 +47,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat448.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion with bases { 2, 3 }
+
+ ulong[] t0 = Nat448.Create64();
+ ulong[] t1 = Nat448.Create64();
+ ulong[] t2 = Nat448.Create64();
+
+ Square(x, t0);
+
+ // 3 | 408
+ SquareN(t0, 1, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 1, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 136
+ SquareN(t0, 3, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 68
+ SquareN(t0, 6, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 34
+ SquareN(t0, 12, t1);
+ Multiply(t0, t1, t2);
+
+ // ! {2,3} | 17
+ SquareN(t2, 24, t0);
+ SquareN(t0, 24, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 8
+ SquareN(t0, 48, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 4
+ SquareN(t0, 96, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 2
+ SquareN(t0, 192, t1);
+ Multiply(t0, t1, t0);
+
+ Multiply(t0, t2, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat448.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
index b60ceafee..581ea73df 100644
--- a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT409FieldElement(
- AbstractF2mCurve.Inverse(409, new int[] { 87 }, ToBigInteger()));
+ ulong[] z = Nat448.Create64();
+ SecT409Field.Invert(x, z);
+ return new SecT409FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs
index edfe1a293..4f573553e 100644
--- a/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs
@@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(409, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 409; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 409; }
diff --git a/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs
index e679094ad..9212fb5d2 100644
--- a/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs
@@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(409, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 409; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 409; }
diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs
index 921c841a9..fc84e336b 100644
--- a/crypto/src/math/ec/custom/sec/SecT571Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs
@@ -59,6 +59,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
return z;
}
+ public static void Invert(ulong[] x, ulong[] z)
+ {
+ if (Nat576.IsZero64(x))
+ throw new InvalidOperationException();
+
+ // Itoh-Tsujii inversion with bases { 2, 3, 5 }
+
+ ulong[] t0 = Nat576.Create64();
+ ulong[] t1 = Nat576.Create64();
+ ulong[] t2 = Nat576.Create64();
+
+ Square(x, t2);
+
+ // 5 | 570
+ Square(t2, t0);
+ Square(t0, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t0, 2, t1);
+ Multiply(t0, t1, t0);
+ Multiply(t0, t2, t0);
+
+ // 3 | 114
+ SquareN(t0, 5, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 5, t1);
+ Multiply(t0, t1, t0);
+
+ // 2 | 38
+ SquareN(t0, 15, t1);
+ Multiply(t0, t1, t2);
+
+ // ! {2,3,5} | 19
+ SquareN(t2, 30, t0);
+ SquareN(t0, 30, t1);
+ Multiply(t0, t1, t0);
+
+ // 3 | 9
+ SquareN(t0, 60, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 60, t1);
+ Multiply(t0, t1, t0);
+
+ // 3 | 3
+ SquareN(t0, 180, t1);
+ Multiply(t0, t1, t0);
+ SquareN(t1, 180, t1);
+ Multiply(t0, t1, t0);
+
+ Multiply(t0, t2, z);
+ }
+
public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
{
ulong[] tt = Nat576.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
index a26e1e336..5d5458412 100644
--- a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
public override ECFieldElement Invert()
{
- return new SecT571FieldElement(
- AbstractF2mCurve.Inverse(571, new int[] { 2, 5, 10 }, ToBigInteger()));
+ ulong[] z = Nat576.Create64();
+ SecT571Field.Invert(x, z);
+ return new SecT571FieldElement(z);
}
public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs
index fb136c967..f5806f09c 100644
--- a/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs
@@ -76,98 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return true; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- y = B.Sqrt();
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- {
- return beta;
- }
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(571, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 571; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 571; }
diff --git a/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs
index 05d58863e..082afa5bd 100644
--- a/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs
@@ -74,97 +74,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
get { return false; }
}
- /**
- * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
- *
- * @param yTilde
- * ~yp, an indication bit for the decompression of yp.
- * @param X1
- * The field element xp.
- * @return the decompressed point.
- */
- protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
- {
- ECFieldElement x = FromBigInteger(X1), y = null;
- if (x.IsZero)
- {
- // y = B.Sqrt();
- y = SecT571R1_B_SQRT;
- }
- else
- {
- ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x);
- ECFieldElement z = SolveQuadraticEquation(beta);
- if (z != null)
- {
- if (z.TestBitZero() != (yTilde == 1))
- {
- z = z.AddOne();
- }
-
- switch (this.CoordinateSystem)
- {
- case COORD_LAMBDA_AFFINE:
- case COORD_LAMBDA_PROJECTIVE:
- {
- y = z.Add(x);
- break;
- }
- default:
- {
- y = z.Multiply(x);
- break;
- }
- }
- }
- }
-
- if (y == null)
- throw new ArgumentException("Invalid point compression");
-
- return this.CreateRawPoint(x, y, true);
- }
-
- /**
- * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
- * D.1.6) The other solution is <code>z + 1</code>.
- *
- * @param beta
- * The value to solve the quadratic equation for.
- * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
- * <code>null</code> if no solution exists.
- */
- private ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
- {
- if (beta.IsZero)
- return beta;
-
- ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero);
-
- ECFieldElement z = null;
- ECFieldElement gamma = null;
-
- Random rand = new Random();
- do
- {
- ECFieldElement t = FromBigInteger(new BigInteger(571, rand));
- z = zeroElement;
- ECFieldElement w = beta;
- for (int i = 1; i < 571; i++)
- {
- ECFieldElement w2 = w.Square();
- z = z.Square().Add(w2.Multiply(t));
- w = w2.Add(beta);
- }
- if (!w.IsZero)
- return null;
- gamma = z.Square().Add(z);
- }
- while (gamma.IsZero);
-
- return z;
- }
-
public virtual int M
{
get { return 571; }
diff --git a/crypto/src/math/raw/Interleave.cs b/crypto/src/math/raw/Interleave.cs
index 9755c9d6f..a45ee1e08 100644
--- a/crypto/src/math/raw/Interleave.cs
+++ b/crypto/src/math/raw/Interleave.cs
@@ -4,67 +4,92 @@ namespace Org.BouncyCastle.Math.Raw
{
internal abstract class Interleave
{
+ private const ulong M32 = 0x55555555UL;
+ private const ulong M64 = 0x5555555555555555UL;
+
/*
* This expands 8 bit indices into 16 bit contents (high bit 14), by inserting 0s between bits.
* In a binary field, this operation is the same as squaring an 8 bit number.
*/
- private static readonly ushort[] INTERLEAVE2_TABLE = new ushort[]
- {
- 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
- 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
- 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
- 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
- 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
- 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
- 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
- 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
- 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
- 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
- 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
- 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
- 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
- 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
- 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
- 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
- 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
- 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
- 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
- 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
- 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
- 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
- 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
- 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
- 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
- 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
- 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
- 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
- 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
- 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
- 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
- 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
- };
+ //private static readonly ushort[] INTERLEAVE2_TABLE = new ushort[]
+ //{
+ // 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
+ // 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
+ // 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
+ // 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
+ // 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
+ // 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
+ // 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
+ // 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
+ // 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
+ // 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
+ // 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
+ // 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
+ // 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
+ // 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
+ // 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
+ // 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
+ // 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
+ // 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
+ // 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
+ // 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
+ // 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
+ // 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
+ // 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
+ // 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
+ // 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
+ // 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
+ // 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
+ // 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
+ // 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
+ // 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
+ // 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
+ // 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
+ //};
internal static uint Expand8to16(uint x)
{
- return INTERLEAVE2_TABLE[x & 0xFF];
+ x &= 0xFFU;
+ x = (x | (x << 4)) & 0x0F0FU;
+ x = (x | (x << 2)) & 0x3333U;
+ x = (x | (x << 1)) & 0x5555U;
+ return x;
}
internal static uint Expand16to32(uint x)
{
- return (uint)(INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >> 8) & 0xFF] << 16);
+ x &= 0xFFFFU;
+ x = (x | (x << 8)) & 0x00FF00FFU;
+ x = (x | (x << 4)) & 0x0F0F0F0FU;
+ x = (x | (x << 2)) & 0x33333333U;
+ x = (x | (x << 1)) & 0x55555555U;
+ return x;
}
internal static ulong Expand32to64(uint x)
{
- uint r00 = (uint)(INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >> 8) & 0xFF] << 16);
- uint r32 = (uint)(INTERLEAVE2_TABLE[(x >> 16) & 0xFF] | INTERLEAVE2_TABLE[x >> 24] << 16);
- return (ulong)r32 << 32 | (ulong)r00;
+ // "shuffle" low half to even bits and high half to odd bits
+ uint t;
+ t = (x ^ (x >> 8)) & 0x0000FF00U; x ^= (t ^ (t << 8));
+ t = (x ^ (x >> 4)) & 0x00F000F0U; x ^= (t ^ (t << 4));
+ t = (x ^ (x >> 2)) & 0x0C0C0C0CU; x ^= (t ^ (t << 2));
+ t = (x ^ (x >> 1)) & 0x22222222U; x ^= (t ^ (t << 1));
+
+ return ((x >> 1) & M32) << 32 | (x & M32);
}
internal static void Expand64To128(ulong x, ulong[] z, int zOff)
{
- z[zOff ] = Expand32to64((uint)x);
- z[zOff + 1] = Expand32to64((uint)(x >> 32));
+ // "shuffle" low half to even bits and high half to odd bits
+ ulong t;
+ t = (x ^ (x >> 16)) & 0x00000000FFFF0000UL; x ^= (t ^ (t << 16));
+ t = (x ^ (x >> 8)) & 0x0000FF000000FF00UL; x ^= (t ^ (t << 8));
+ t = (x ^ (x >> 4)) & 0x00F000F000F000F0UL; x ^= (t ^ (t << 4));
+ t = (x ^ (x >> 2)) & 0x0C0C0C0C0C0C0C0CUL; x ^= (t ^ (t << 2));
+ t = (x ^ (x >> 1)) & 0x2222222222222222UL; x ^= (t ^ (t << 1));
+
+ z[zOff ] = (x ) & M64;
+ z[zOff + 1] = (x >> 1) & M64;
}
}
}
|
