using System;
using System.Collections;
using Org.BouncyCastle.Math.EC.Abc;
using Org.BouncyCastle.Math.Field;
using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Math.EC
{
/// Base class for an elliptic curve.
public abstract class ECCurve
{
protected IFiniteField m_field;
protected ECFieldElement m_a, m_b;
protected ECCurve(IFiniteField field)
{
this.m_field = field;
}
public abstract int FieldSize { get; }
public abstract ECFieldElement FromBigInteger(BigInteger x);
public abstract ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression);
public abstract ECPoint Infinity { get; }
public virtual IFiniteField Field
{
get { return m_field; }
}
public virtual ECFieldElement A
{
get { return m_a; }
}
public virtual ECFieldElement B
{
get { return m_b; }
}
public virtual bool Equals(ECCurve other)
{
if (this == other)
return true;
if (null == other)
return false;
return Field.Equals(other.Field)
&& A.Equals(other.A)
&& B.Equals(other.B);
}
public override bool Equals(object obj)
{
return Equals(obj as ECCurve);
}
public override int GetHashCode()
{
return Field.GetHashCode()
^ Integers.RotateLeft(A.GetHashCode(), 8)
^ Integers.RotateLeft(B.GetHashCode(), 16);
}
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
* Fp (X9.62 s 4.2.1 pg 17).
* @return The decoded point.
*/
public virtual ECPoint DecodePoint(byte[] encoded)
{
ECPoint p = null;
int expectedLength = (FieldSize + 7) / 8;
switch (encoded[0])
{
case 0x00: // infinity
{
if (encoded.Length != 1)
throw new ArgumentException("Incorrect length for infinity encoding", "encoded");
p = Infinity;
break;
}
case 0x02: // compressed
case 0x03: // compressed
{
if (encoded.Length != (expectedLength + 1))
throw new ArgumentException("Incorrect length for compressed encoding", "encoded");
int yTilde = encoded[0] & 1;
BigInteger X1 = new BigInteger(1, 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 ArgumentException("Incorrect length for uncompressed/hybrid encoding", "encoded");
BigInteger X1 = new BigInteger(1, encoded, 1, expectedLength);
BigInteger Y1 = new BigInteger(1, encoded, 1 + expectedLength, expectedLength);
p = CreatePoint(X1, Y1, false);
break;
}
default:
throw new FormatException("Invalid point encoding " + encoded[0]);
}
return p;
}
}
/**
* Elliptic curve over Fp
*/
public class FpCurve
: ECCurve
{
private readonly BigInteger q, r;
private readonly FpPoint infinity;
public FpCurve(BigInteger q, BigInteger a, BigInteger b)
: base(FiniteFields.GetPrimeField(q))
{
this.q = q;
this.r = FpFieldElement.CalculateResidue(q);
this.m_a = FromBigInteger(a);
this.m_b = FromBigInteger(b);
this.infinity = new FpPoint(this, null, null);
}
public BigInteger Q
{
get { return q; }
}
public override ECPoint Infinity
{
get { return infinity; }
}
public override int FieldSize
{
get { return q.BitLength; }
}
public override ECFieldElement FromBigInteger(BigInteger x)
{
return new FpFieldElement(this.q, this.r, x);
}
public override ECPoint CreatePoint(
BigInteger X1,
BigInteger Y1,
bool withCompression)
{
// TODO Validation of X1, Y1?
return new FpPoint(
this,
FromBigInteger(X1),
FromBigInteger(Y1),
withCompression);
}
protected override ECPoint DecompressPoint(
int yTilde,
BigInteger X1)
{
ECFieldElement x = FromBigInteger(X1);
ECFieldElement alpha = x.Multiply(x.Square().Add(m_a)).Add(m_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 ArithmeticException("Invalid point compression");
BigInteger betaValue = beta.ToBigInteger();
int bit0 = betaValue.TestBit(0) ? 1 : 0;
if (bit0 != yTilde)
{
// Use the other root
beta = beta.Negate();
}
return new FpPoint(this, x, beta, true);
}
}
/**
* Elliptic curves over F2m. The Weierstrass equation is given by
* y2 + xy = x3 + ax2 + b.
*/
public class F2mCurve : ECCurve
{
private static IFiniteField BuildField(int m, int k1, int k2, int k3)
{
if (k1 == 0)
{
throw new ArgumentException("k1 must be > 0");
}
if (k2 == 0)
{
if (k3 != 0)
{
throw new ArgumentException("k3 must be 0 if k2 == 0");
}
return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, m });
}
if (k2 <= k1)
{
throw new ArgumentException("k2 must be > k1");
}
if (k3 <= k2)
{
throw new ArgumentException("k3 must be > k2");
}
return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, k2, k3, m });
}
/**
* The exponent m of F2m.
*/
private readonly int m;
/**
* TPB: The integer k where xm +
* xk + 1 represents the reduction polynomial
* f(z).
* PPB: The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private readonly int k1;
/**
* TPB: Always set to 0
* PPB: The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private readonly int k2;
/**
* TPB: Always set to 0
* PPB: The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private readonly int k3;
/**
* The order of the base point of the curve.
*/
private readonly BigInteger n;
/**
* The cofactor of the curve.
*/
private readonly BigInteger h;
/**
* The point at infinity on this curve.
*/
private readonly F2mPoint infinity;
/**
* The parameter μ of the elliptic curve if this is
* a Koblitz curve.
*/
private sbyte mu = 0;
/**
* The auxiliary values s0 and
* s1 used for partial modular reduction for
* Koblitz curves.
*/
private BigInteger[] si = null;
/**
* Constructor for Trinomial Polynomial Basis (TPB).
* @param m The exponent m of
* F2m.
* @param k The integer k where xm +
* xk + 1 represents the reduction
* polynomial f(z).
* @param a The coefficient a in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param b The coefficient b in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
*/
public F2mCurve(
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 m of
* F2m.
* @param k The integer k where xm +
* xk + 1 represents the reduction
* polynomial f(z).
* @param a The coefficient a in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param b The coefficient b in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param n The order of the main subgroup of the elliptic curve.
* @param h The cofactor of the elliptic curve, i.e.
* #Ea(F2m) = h * n.
*/
public F2mCurve(
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 m of
* F2m.
* @param k1 The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k2 The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k3 The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param a The coefficient a in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param b The coefficient b in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
*/
public F2mCurve(
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 m of
* F2m.
* @param k1 The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k2 The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k3 The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param a The coefficient a in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param b The coefficient b in the Weierstrass equation
* for non-supersingular elliptic curves over
* F2m.
* @param n The order of the main subgroup of the elliptic curve.
* @param h The cofactor of the elliptic curve, i.e.
* #Ea(F2m) = h * n.
*/
public F2mCurve(
int m,
int k1,
int k2,
int k3,
BigInteger a,
BigInteger b,
BigInteger n,
BigInteger h)
: base(BuildField(m, k1, k2, k3))
{
this.m = m;
this.k1 = k1;
this.k2 = k2;
this.k3 = k3;
this.n = n;
this.h = h;
this.infinity = new F2mPoint(this, null, null);
if (k1 == 0)
throw new ArgumentException("k1 must be > 0");
if (k2 == 0)
{
if (k3 != 0)
throw new ArgumentException("k3 must be 0 if k2 == 0");
}
else
{
if (k2 <= k1)
throw new ArgumentException("k2 must be > k1");
if (k3 <= k2)
throw new ArgumentException("k3 must be > k2");
}
this.m_a = FromBigInteger(a);
this.m_b = FromBigInteger(b);
}
public override ECPoint Infinity
{
get { return infinity; }
}
public override int FieldSize
{
get { return m; }
}
public override ECFieldElement FromBigInteger(BigInteger x)
{
return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x);
}
/**
* Returns true if this is a Koblitz curve (ABC curve).
* @return true if this is a Koblitz curve (ABC curve), false otherwise
*/
public bool IsKoblitz
{
get
{
return n != null && h != null && m_a.BitLength <= 1 && m_b.IsOne;
}
}
/**
* Returns the parameter μ of the elliptic curve.
* @return μ of the elliptic curve.
* @throws ArgumentException if the given ECCurve is not a
* Koblitz curve.
*/
internal sbyte GetMu()
{
if (mu == 0)
{
lock (this)
{
if (mu == 0)
{
mu = Tnaf.GetMu(this);
}
}
}
return mu;
}
/**
* @return the auxiliary values s0 and
* s1 used for partial modular reduction for
* Koblitz curves.
*/
internal BigInteger[] GetSi()
{
if (si == null)
{
lock (this)
{
if (si == null)
{
si = Tnaf.GetSi(this);
}
}
}
return si;
}
public override ECPoint CreatePoint(
BigInteger X1,
BigInteger Y1,
bool withCompression)
{
// TODO Validation of X1, Y1?
return new F2mPoint(
this,
FromBigInteger(X1),
FromBigInteger(Y1),
withCompression);
}
protected override ECPoint DecompressPoint(
int yTilde,
BigInteger X1)
{
ECFieldElement xp = FromBigInteger(X1);
ECFieldElement yp = null;
if (xp.ToBigInteger().SignValue == 0)
{
yp = (F2mFieldElement)m_b;
for (int i = 0; i < m - 1; i++)
{
yp = yp.Square();
}
}
else
{
ECFieldElement beta = xp.Add(m_a).Add(m_b.Multiply(xp.Square().Invert()));
ECFieldElement z = solveQuadradicEquation(beta);
if (z == null)
throw new ArithmeticException("Invalid point compression");
int zBit = z.ToBigInteger().TestBit(0) ? 1 : 0;
if (zBit != yTilde)
{
z = z.Add(FromBigInteger(BigInteger.One));
}
yp = xp.Multiply(z);
}
return new F2mPoint(this, xp, yp, true);
}
/**
* Solves a quadratic equation z2 + z = beta(X9.62
* D.1.6) The other solution is z + 1.
*
* @param beta
* The value to solve the qradratic equation for.
* @return the solution for z2 + z = beta or
* null if no solution exists.
*/
private ECFieldElement solveQuadradicEquation(ECFieldElement beta)
{
if (beta.ToBigInteger().SignValue == 0)
{
return FromBigInteger(BigInteger.Zero);
}
ECFieldElement z = null;
ECFieldElement gamma = FromBigInteger(BigInteger.Zero);
while (gamma.ToBigInteger().SignValue == 0)
{
ECFieldElement t = FromBigInteger(new BigInteger(m, new Random()));
z = FromBigInteger(BigInteger.Zero);
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().SignValue != 0)
{
return null;
}
gamma = z.Square().Add(z);
}
return z;
}
public int M
{
get { return m; }
}
/**
* Return true if curve uses a Trinomial basis.
*
* @return true if curve Trinomial, false otherwise.
*/
public bool IsTrinomial()
{
return k2 == 0 && k3 == 0;
}
public int K1
{
get { return k1; }
}
public int K2
{
get { return k2; }
}
public int K3
{
get { return k3; }
}
public BigInteger N
{
get { return n; }
}
public BigInteger H
{
get { return h; }
}
}
}