content: package local.org.bouncycastle.math.ec;
  
  import java.math.BigInteger;
  import java.util.Random;
  
  /**
   * base class for an elliptic curve
   */
  public abstract class ECCurve
  {
      ECFieldElement a, b;
  
      public abstract int getFieldSize();
  
      public abstract ECFieldElement fromBigInteger(BigInteger x);
  
      public abstract ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression);
  
      public abstract ECPoint getInfinity();
  
      public ECFieldElement getA()
      {
          return a;
      }
  
      public ECFieldElement getB()
      {
          return b;
      }
  
      protected abstract ECPoint decompressPoint(int yTilde, BigInteger X1);
  
      /**
       * Decode a point on this curve from its ASN.1 encoding. The different
       * encodings are taken account of, including point compression for
       * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17).
       * @return The decoded point.
       */
      public ECPoint decodePoint(byte[] encoded)
      {
          ECPoint p = null;
          int expectedLength = (getFieldSize() + 7) / 8;
  
          switch (encoded[0])
          {
          case 0x00: // infinity
          {
              if (encoded.length != 1)
              {
                  throw new IllegalArgumentException("Incorrect length for infinity encoding");
              }
  
              p = getInfinity();
              break;
          }
          case 0x02: // compressed
          case 0x03: // compressed
          {
              if (encoded.length != (expectedLength + 1))
              {
                  throw new IllegalArgumentException("Incorrect length for compressed encoding");
              }
  
              int yTilde = encoded[0] & 1;
              BigInteger X1 = fromArray(encoded, 1, expectedLength);
  
              p = decompressPoint(yTilde, X1);
              break;
          }
          case 0x04: // uncompressed
          case 0x06: // hybrid
          case 0x07: // hybrid
          {
              if (encoded.length != (2 * expectedLength + 1))
              {
                  throw new IllegalArgumentException("Incorrect length for uncompressed/hybrid encoding");
              }
  
              BigInteger X1 = fromArray(encoded, 1, expectedLength);
              BigInteger Y1 = fromArray(encoded, 1 + expectedLength, expectedLength);
  
              p = createPoint(X1, Y1, false);
              break;
          }
          default:
              throw new IllegalArgumentException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16));
          }
  
          return p;
      }
  
      private static BigInteger fromArray(byte[] buf, int off, int length)
      {
          byte[] mag = new byte[length];
          System.arraycopy(buf, off, mag, 0, length);
          return new BigInteger(1, mag);
      }
  
      /**
       * Elliptic curve over Fp
       */
      public static class Fp extends ECCurve
      {
          BigInteger q;
          ECPoint.Fp infinity;
  
          public Fp(BigInteger q, BigInteger a, BigInteger b)
          {
              this.q = q;
              this.a = fromBigInteger(a);
              this.b = fromBigInteger(b);
              this.infinity = new ECPoint.Fp(this, null, null);
          }
  
          public BigInteger getQ()
          {
              return q;
          }
  
          public int getFieldSize()
          {
              return q.bitLength();
          }
  
          public ECFieldElement fromBigInteger(BigInteger x)
          {
              return new ECFieldElement.Fp(this.q, x);
          }
  
          public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression)
          {
              return new ECPoint.Fp(this, fromBigInteger(x), fromBigInteger(y), withCompression);
          }
  
          protected ECPoint decompressPoint(int yTilde, BigInteger X1)
          {
              ECFieldElement x = fromBigInteger(X1);
              ECFieldElement alpha = x.multiply(x.square().add(a)).add(b);
              ECFieldElement beta = alpha.sqrt();
  
              //
              // if we can't find a sqrt we haven't got a point on the
              // curve - run!
              //
              if (beta == null)
              {
                  throw new RuntimeException("Invalid point compression");
              }
  
              BigInteger betaValue = beta.toBigInteger();
              int bit0 = betaValue.testBit(0) ? 1 : 0;
  
              if (bit0 != yTilde)
              {
                  // Use the other root
                  beta = fromBigInteger(q.subtract(betaValue));
              }
  
              return new ECPoint.Fp(this, x, beta, true);
          }
  
          public ECPoint getInfinity()
          {
              return infinity;
          }
  
          public boolean equals(
              Object anObject) 
          {
              if (anObject == this) 
              {
                  return true;
              }
  
              if (!(anObject instanceof ECCurve.Fp)) 
              {
                  return false;
              }
  
              ECCurve.Fp other = (ECCurve.Fp) anObject;
  
              return this.q.equals(other.q) 
                      && a.equals(other.a) && b.equals(other.b);
          }
  
          public int hashCode() 
          {
              return a.hashCode() ^ b.hashCode() ^ q.hashCode();
          }
      }
  
      /**
       * Elliptic curves over F2m. The Weierstrass equation is given by
       * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>.
       */
      public static class F2m extends ECCurve
      {
          /**
           * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
           */
          private int m;  // can't be final - JDK 1.1
  
          /**
           * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
           * x<sup>k</sup> + 1</code> represents the reduction polynomial
           * <code>f(z)</code>.<br>
           * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.<br>
           */
          private int k1;  // can't be final - JDK 1.1
  
          /**
           * TPB: Always set to <code>0</code><br>
           * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.<br>
           */
          private int k2;  // can't be final - JDK 1.1
  
          /**
           * TPB: Always set to <code>0</code><br>
           * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.<br>
           */
          private int k3;  // can't be final - JDK 1.1
  
          /**
           * The order of the base point of the curve.
           */
          private BigInteger n;  // can't be final - JDK 1.1
  
          /**
           * The cofactor of the curve.
           */
          private BigInteger h;  // can't be final - JDK 1.1
          
           /**
           * The point at infinity on this curve.
           */
          private ECPoint.F2m infinity;  // can't be final - JDK 1.1
  
          /**
           * The parameter <code>&mu;</code> of the elliptic curve if this is
           * a Koblitz curve.
           */
          private byte mu = 0;
  
          /**
           * The auxiliary values <code>s<sub>0</sub></code> and
           * <code>s<sub>1</sub></code> used for partial modular reduction for
           * Koblitz curves.
           */
          private BigInteger[] si = null;
  
          /**
           * Constructor for Trinomial Polynomial Basis (TPB).
           * @param m  The exponent <code>m</code> of
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
           * x<sup>k</sup> + 1</code> represents the reduction
           * polynomial <code>f(z)</code>.
           * @param a The coefficient <code>a</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param b The coefficient <code>b</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           */
          public F2m(
              int m,
              int k,
              BigInteger a,
              BigInteger b)
          {
              this(m, k, 0, 0, a, b, null, null);
          }
  
          /**
           * Constructor for Trinomial Polynomial Basis (TPB).
           * @param m  The exponent <code>m</code> of
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
           * x<sup>k</sup> + 1</code> represents the reduction
           * polynomial <code>f(z)</code>.
           * @param a The coefficient <code>a</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param b The coefficient <code>b</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param n The order of the main subgroup of the elliptic curve.
           * @param h The cofactor of the elliptic curve, i.e.
           * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
           */
          public F2m(
              int m, 
              int k, 
              BigInteger a, 
              BigInteger b,
              BigInteger n,
              BigInteger h)
          {
              this(m, k, 0, 0, a, b, n, h);
          }
  
          /**
           * Constructor for Pentanomial Polynomial Basis (PPB).
           * @param m  The exponent <code>m</code> of
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param a The coefficient <code>a</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param b The coefficient <code>b</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           */
          public F2m(
              int m,
              int k1,
              int k2,
              int k3,
              BigInteger a,
              BigInteger b)
          {
              this(m, k1, k2, k3, a, b, null, null);
          }
  
          /**
           * Constructor for Pentanomial Polynomial Basis (PPB).
           * @param m  The exponent <code>m</code> of
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
           * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
           * represents the reduction polynomial <code>f(z)</code>.
           * @param a The coefficient <code>a</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param b The coefficient <code>b</code> in the Weierstrass equation
           * for non-supersingular elliptic curves over
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param n The order of the main subgroup of the elliptic curve.
           * @param h The cofactor of the elliptic curve, i.e.
           * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
           */
          public F2m(
              int m, 
              int k1, 
              int k2, 
              int k3,
              BigInteger a, 
              BigInteger b,
              BigInteger n,
              BigInteger h)
          {
              this.m = m;
              this.k1 = k1;
              this.k2 = k2;
              this.k3 = k3;
              this.n = n;
              this.h = h;
  
              if (k1 == 0)
              {
                  throw new IllegalArgumentException("k1 must be > 0");
              }
  
              if (k2 == 0)
              {
                  if (k3 != 0)
                  {
                      throw new IllegalArgumentException("k3 must be 0 if k2 == 0");
                  }
              }
              else
              {
                  if (k2 <= k1)
                  {
                      throw new IllegalArgumentException("k2 must be > k1");
                  }
  
                  if (k3 <= k2)
                  {
                      throw new IllegalArgumentException("k3 must be > k2");
                  }
              }
  
              this.a = fromBigInteger(a);
              this.b = fromBigInteger(b);
              this.infinity = new ECPoint.F2m(this, null, null);
          }
  
          public int getFieldSize()
          {
              return m;
          }
  
          public ECFieldElement fromBigInteger(BigInteger x)
          {
              return new ECFieldElement.F2m(this.m, this.k1, this.k2, this.k3, x);
          }
  
          public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression)
          {
              return new ECPoint.F2m(this, fromBigInteger(x), fromBigInteger(y), withCompression);
          }
  
          public ECPoint getInfinity()
          {
              return infinity;
          }
  
          /**
           * Returns true if this is a Koblitz curve (ABC curve).
           * @return true if this is a Koblitz curve (ABC curve), false otherwise
           */
          public boolean isKoblitz()
          {
              return ((n != null) && (h != null) &&
                      ((a.toBigInteger().equals(ECConstants.ZERO)) ||
                      (a.toBigInteger().equals(ECConstants.ONE))) &&
                      (b.toBigInteger().equals(ECConstants.ONE)));
          }
  
          /**
           * Returns the parameter <code>&mu;</code> of the elliptic curve.
           * @return <code>&mu;</code> of the elliptic curve.
           * @throws IllegalArgumentException if the given ECCurve is not a
           * Koblitz curve.
           */
          synchronized byte getMu()
          {
              if (mu == 0)
              {
                  mu = Tnaf.getMu(this);
              }
              return mu;
          }
  
          /**
           * @return the auxiliary values <code>s<sub>0</sub></code> and
           * <code>s<sub>1</sub></code> used for partial modular reduction for
           * Koblitz curves.
           */
          synchronized BigInteger[] getSi()
          {
              if (si == null)
              {
                  si = Tnaf.getSi(this);
              }
              return si;
          }
  
          /**
           * 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 ECPoint decompressPoint(int yTilde, BigInteger X1)
          {
              ECFieldElement xp = fromBigInteger(X1);
              ECFieldElement yp = null;
              if (xp.toBigInteger().equals(ECConstants.ZERO))
              {
                  yp = (ECFieldElement.F2m)b;
                  for (int i = 0; i < m - 1; i++)
                  {
                      yp = yp.square();
                  }
              }
              else
              {
                  ECFieldElement beta = xp.add(a).add(b.multiply(xp.square().invert()));
                  ECFieldElement z = solveQuadradicEquation(beta);
                  if (z == null)
                  {
                      throw new IllegalArgumentException("Invalid point compression");
                  }
                  int zBit = z.toBigInteger().testBit(0) ? 1 : 0;
                  if (zBit != yTilde)
                  {
                      z = z.add(fromBigInteger(ECConstants.ONE));
                  }
                  yp = xp.multiply(z);
              }
  
              return new ECPoint.F2m(this, 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)
          {
              ECFieldElement zeroElement = new ECFieldElement.F2m(
                      this.m, this.k1, this.k2, this.k3, ECConstants.ZERO);
  
              if (beta.toBigInteger().equals(ECConstants.ZERO))
              {
                  return zeroElement;
              }
  
              ECFieldElement z = null;
              ECFieldElement gamma = zeroElement;
  
              Random rand = new Random();
              do
              {
                  ECFieldElement t = new ECFieldElement.F2m(this.m, this.k1,
                          this.k2, this.k3, new BigInteger(m, rand));
                  z = zeroElement;
                  ECFieldElement w = beta;
                  for (int i = 1; i <= m - 1; i++)
                  {
                      ECFieldElement w2 = w.square();
                      z = z.square().add(w2.multiply(t));
                      w = w2.add(beta);
                  }
                  if (!w.toBigInteger().equals(ECConstants.ZERO))
                  {
                      return null;
                  }
                  gamma = z.square().add(z);
              }
              while (gamma.toBigInteger().equals(ECConstants.ZERO));
  
              return z;
          }
          
          public boolean equals(
              Object anObject)
          {
              if (anObject == this) 
              {
                  return true;
              }
  
              if (!(anObject instanceof ECCurve.F2m)) 
              {
                  return false;
              }
  
              ECCurve.F2m other = (ECCurve.F2m)anObject;
              
              return (this.m == other.m) && (this.k1 == other.k1)
                  && (this.k2 == other.k2) && (this.k3 == other.k3)
                  && a.equals(other.a) && b.equals(other.b);
          }
  
          public int hashCode()
          {
              return this.a.hashCode() ^ this.b.hashCode() ^ m ^ k1 ^ k2 ^ k3;
          }
  
          public int getM()
          {
              return m;
          }
  
          /**
           * Return true if curve uses a Trinomial basis.
           * 
           * @return true if curve Trinomial, false otherwise.
           */
          public boolean isTrinomial()
          {
              return k2 == 0 && k3 == 0;
          }
          
          public int getK1()
          {
              return k1;
          }
  
          public int getK2()
          {
              return k2;
          }
  
          public int getK3()
          {
              return k3;
          }
  
          public BigInteger getN()
          {
              return n;
          }
  
          public BigInteger getH()
          {
              return h;
          }
      }
  }
  