path: root/crypto/src/math/ec/ECPoint.cs

using System;
using System.Collections;
using System.Diagnostics;

using Org.BouncyCastle.Asn1.X9;

using Org.BouncyCastle.Math.EC.Multiplier;

namespace Org.BouncyCastle.Math.EC
{
	/**
	 * base class for points on elliptic curves.
	 */
	public abstract class ECPoint
	{
		internal readonly ECCurve			curve;
		internal readonly ECFieldElement	x, y;
		internal readonly bool				withCompression;
		internal ECMultiplier				multiplier = null;
		internal PreCompInfo				preCompInfo = null;

		protected internal ECPoint(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y,
			bool			withCompression)
		{
			if (curve == null)
				throw new ArgumentNullException("curve");

			this.curve = curve;
			this.x = x;
			this.y = y;
			this.withCompression = withCompression;
		}

		public ECCurve Curve
		{
			get { return curve; }
		}

		public ECFieldElement X
		{
			get { return x; }
		}

		public ECFieldElement Y
		{
			get { return y; }
		}

		public bool IsInfinity
		{
			get { return x == null && y == null; }
		}

		public bool IsCompressed
		{
			get { return withCompression; }
		}

		public override bool Equals(
			object obj)
		{
			if (obj == this)
				return true;

			ECPoint o = obj as ECPoint;

			if (o == null)
				return false;

			if (this.IsInfinity)
				return o.IsInfinity;

			return x.Equals(o.x) && y.Equals(o.y);
		}

		public override int GetHashCode()
		{
			if (this.IsInfinity)
				return 0;

			return x.GetHashCode() ^ y.GetHashCode();
		}

//		/**
//		 * Mainly for testing. Explicitly set the <code>ECMultiplier</code>.
//		 * @param multiplier The <code>ECMultiplier</code> to be used to multiply
//		 * this <code>ECPoint</code>.
//		 */
//		internal void SetECMultiplier(
//			ECMultiplier multiplier)
//		{
//			this.multiplier = multiplier;
//		}

		/**
		 * Sets the <code>PreCompInfo</code>. Used by <code>ECMultiplier</code>s
		 * to save the precomputation for this <code>ECPoint</code> to store the
		 * precomputation result for use by subsequent multiplication.
		 * @param preCompInfo The values precomputed by the
		 * <code>ECMultiplier</code>.
		 */
		internal void SetPreCompInfo(
			PreCompInfo preCompInfo)
		{
			this.preCompInfo = preCompInfo;
		}

		public abstract byte[] GetEncoded();

		public abstract ECPoint Add(ECPoint b);
		public abstract ECPoint Subtract(ECPoint b);
		public abstract ECPoint Negate();
		public abstract ECPoint Twice();
		public abstract ECPoint Multiply(BigInteger b);

		/**
		* Sets the appropriate <code>ECMultiplier</code>, unless already set. 
		*/
		internal virtual void AssertECMultiplier()
		{
			if (this.multiplier == null)
			{
				lock (this)
				{
					if (this.multiplier == null)
					{
						this.multiplier = new FpNafMultiplier();
					}
				}
			}
		}
	}

	public abstract class ECPointBase
		: ECPoint
	{
		protected internal ECPointBase(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y,
			bool			withCompression)
			: base(curve, x, y, withCompression)
		{
		}

		protected internal abstract bool YTilde { get; }

		/**
		 * return the field element encoded with point compression. (S 4.3.6)
		 */
		public override byte[] GetEncoded()
		{
			if (this.IsInfinity)
				return new byte[1];

			// Note: some of the tests rely on calculating byte length from the field element
			// (since the test cases use mismatching fields for curve/elements)
			int byteLength = X9IntegerConverter.GetByteLength(x);
			byte[] X = X9IntegerConverter.IntegerToBytes(this.X.ToBigInteger(), byteLength);
			byte[] PO;

			if (withCompression)
			{
				PO = new byte[1 + X.Length];

				PO[0] = (byte)(YTilde ? 0x03 : 0x02);
			}
			else
			{
				byte[] Y = X9IntegerConverter.IntegerToBytes(this.Y.ToBigInteger(), byteLength);
				PO = new byte[1 + X.Length + Y.Length];

				PO[0] = 0x04;

				Y.CopyTo(PO, 1 + X.Length);
			}

			X.CopyTo(PO, 1);

			return PO;
		}

		/**
		 * Multiplies this <code>ECPoint</code> by the given number.
		 * @param k The multiplicator.
		 * @return <code>k * this</code>.
		 */
		public override ECPoint Multiply(
			BigInteger k)
		{
			if (k.SignValue < 0)
				throw new ArgumentException("The multiplicator cannot be negative", "k");

			if (this.IsInfinity)
				return this;

			if (k.SignValue == 0)
				return this.curve.Infinity;

			AssertECMultiplier();
			return this.multiplier.Multiply(this, k, preCompInfo);
		}
	}

	/**
	 * Elliptic curve points over Fp
	 */
	public class FpPoint
		: ECPointBase
	{
		/**
		 * Create a point which encodes with point compression.
		 *
		 * @param curve the curve to use
		 * @param x affine x co-ordinate
		 * @param y affine y co-ordinate
		 */
		public FpPoint(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y)
			: this(curve, x, y, false)
		{
		}

		/**
		 * Create a point that encodes with or without point compresion.
		 *
		 * @param curve the curve to use
		 * @param x affine x co-ordinate
		 * @param y affine y co-ordinate
		 * @param withCompression if true encode with point compression
		 */
		public FpPoint(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y,
			bool			withCompression)
			: base(curve, x, y, withCompression)
		{
			if ((x != null && y == null) || (x == null && y != null))
				throw new ArgumentException("Exactly one of the field elements is null");
		}

		protected internal override bool YTilde
		{
			get
			{
				return this.Y.ToBigInteger().TestBit(0);
			}
		}

		// B.3 pg 62
		public override ECPoint Add(
			ECPoint b)
		{
			if (this.IsInfinity)
				return b;

			if (b.IsInfinity)
				return this;

			// Check if b = this or b = -this
			if (this.x.Equals(b.x))
			{
				if (this.y.Equals(b.y))
				{
					// this = b, i.e. this must be doubled
					return this.Twice();
				}

				Debug.Assert(this.y.Equals(b.y.Negate()));

				// this = -b, i.e. the result is the point at infinity
				return this.curve.Infinity;
			}

			ECFieldElement gamma = b.y.Subtract(this.y).Divide(b.x.Subtract(this.x));

			ECFieldElement x3 = gamma.Square().Subtract(this.x).Subtract(b.x);
			ECFieldElement y3 = gamma.Multiply(this.x.Subtract(x3)).Subtract(this.y);

			return new FpPoint(curve, x3, y3);
		}

		// B.3 pg 62
		public override ECPoint Twice()
		{
			// Twice identity element (point at infinity) is identity
			if (this.IsInfinity)
				return this;

			// if y1 == 0, then (x1, y1) == (x1, -y1)
			// and hence this = -this and thus 2(x1, y1) == infinity
			if (this.y.ToBigInteger().SignValue == 0)
				return this.curve.Infinity;

			ECFieldElement TWO = this.curve.FromBigInteger(BigInteger.Two);
			ECFieldElement THREE = this.curve.FromBigInteger(BigInteger.Three);
			ECFieldElement gamma = this.x.Square().Multiply(THREE).Add(curve.a).Divide(y.Multiply(TWO));

			ECFieldElement x3 = gamma.Square().Subtract(this.x.Multiply(TWO));
			ECFieldElement y3 = gamma.Multiply(this.x.Subtract(x3)).Subtract(this.y);

			return new FpPoint(curve, x3, y3, this.withCompression);
		}

		// D.3.2 pg 102 (see Note:)
		public override ECPoint Subtract(
			ECPoint b)
		{
			if (b.IsInfinity)
				return this;

			// Add -b
			return Add(b.Negate());
		}

		public override ECPoint Negate()
		{
			return new FpPoint(this.curve, this.x, this.y.Negate(), this.withCompression);
		}

		/**
		 * Sets the default <code>ECMultiplier</code>, unless already set. 
		 */
		internal override void AssertECMultiplier()
		{
			if (this.multiplier == null)
			{
				lock (this)
				{
					if (this.multiplier == null)
					{
						this.multiplier = new WNafMultiplier();
					}
				}
			}
		}
	}

	/**
	 * Elliptic curve points over F2m
	 */
	public class F2mPoint
		: ECPointBase
	{
		/**
		 * @param curve base curve
		 * @param x x point
		 * @param y y point
		 */
		public F2mPoint(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y)
			:  this(curve, x, y, false)
		{
		}

		/**
		 * @param curve base curve
		 * @param x x point
		 * @param y y point
		 * @param withCompression true if encode with point compression.
		 */
		public F2mPoint(
			ECCurve			curve,
			ECFieldElement	x,
			ECFieldElement	y,
			bool			withCompression)
			: base(curve, x, y, withCompression)
		{
			if ((x != null && y == null) || (x == null && y != null))
			{
				throw new ArgumentException("Exactly one of the field elements is null");
			}

			if (x != null)
			{
				// Check if x and y are elements of the same field
				F2mFieldElement.CheckFieldElements(this.x, this.y);

				// Check if x and a are elements of the same field
				F2mFieldElement.CheckFieldElements(this.x, this.curve.A);
			}
		}

		/**
		 * Constructor for point at infinity
		 */
		[Obsolete("Use ECCurve.Infinity property")]
		public F2mPoint(
			ECCurve curve)
			: this(curve, null, null)
		{
		}

		protected internal override bool YTilde
		{
			get
			{
				// X9.62 4.2.2 and 4.3.6:
				// if x = 0 then ypTilde := 0, else ypTilde is the rightmost
				// bit of y * x^(-1)
				return this.X.ToBigInteger().SignValue != 0
					&& this.Y.Multiply(this.X.Invert()).ToBigInteger().TestBit(0);
			}
		}

		/**
		 * Check, if two <code>ECPoint</code>s can be added or subtracted.
		 * @param a The first <code>ECPoint</code> to check.
		 * @param b The second <code>ECPoint</code> to check.
		 * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
		 * cannot be added.
		 */
		private static void CheckPoints(
			ECPoint	a,
			ECPoint	b)
		{
			// Check, if points are on the same curve
			if (!a.curve.Equals(b.curve))
				throw new ArgumentException("Only points on the same curve can be added or subtracted");

//			F2mFieldElement.CheckFieldElements(a.x, b.x);
		}

		/* (non-Javadoc)
		 * @see org.bouncycastle.math.ec.ECPoint#add(org.bouncycastle.math.ec.ECPoint)
		 */
		public override ECPoint Add(ECPoint b)
		{
			CheckPoints(this, b);
			return AddSimple((F2mPoint) b);
		}

		/**
		 * Adds another <code>ECPoints.F2m</code> to <code>this</code> without
		 * checking if both points are on the same curve. Used by multiplication
		 * algorithms, because there all points are a multiple of the same point
		 * and hence the checks can be omitted.
		 * @param b The other <code>ECPoints.F2m</code> to add to
		 * <code>this</code>.
		 * @return <code>this + b</code>
		 */
		internal F2mPoint AddSimple(F2mPoint b)
		{
			if (this.IsInfinity)
				return b;

			if (b.IsInfinity)
				return this;

			F2mFieldElement x2 = (F2mFieldElement) b.X;
			F2mFieldElement y2 = (F2mFieldElement) b.Y;

			// Check if b == this or b == -this
			if (this.x.Equals(x2))
			{
				// this == b, i.e. this must be doubled
				if (this.y.Equals(y2))
					return (F2mPoint) this.Twice();

				// this = -other, i.e. the result is the point at infinity
				return (F2mPoint) this.curve.Infinity;
			}

			ECFieldElement xSum = this.x.Add(x2);

			F2mFieldElement lambda
				= (F2mFieldElement)(this.y.Add(y2)).Divide(xSum);

			F2mFieldElement x3
				= (F2mFieldElement)lambda.Square().Add(lambda).Add(xSum).Add(this.curve.A);

			F2mFieldElement y3
				= (F2mFieldElement)lambda.Multiply(this.x.Add(x3)).Add(x3).Add(this.y);

			return new F2mPoint(curve, x3, y3, withCompression);
		}

		/* (non-Javadoc)
		 * @see org.bouncycastle.math.ec.ECPoint#subtract(org.bouncycastle.math.ec.ECPoint)
		 */
		public override ECPoint Subtract(
			ECPoint b)
		{
			CheckPoints(this, b);
			return SubtractSimple((F2mPoint) b);
		}

		/**
		 * Subtracts another <code>ECPoints.F2m</code> from <code>this</code>
		 * without checking if both points are on the same curve. Used by
		 * multiplication algorithms, because there all points are a multiple
		 * of the same point and hence the checks can be omitted.
		 * @param b The other <code>ECPoints.F2m</code> to subtract from
		 * <code>this</code>.
		 * @return <code>this - b</code>
		 */
		internal F2mPoint SubtractSimple(
			F2mPoint b)
		{
			if (b.IsInfinity)
				return this;

			// Add -b
			return AddSimple((F2mPoint) b.Negate());
		}

		/* (non-Javadoc)
		 * @see Org.BouncyCastle.Math.EC.ECPoint#twice()
		 */
		public override ECPoint Twice()
		{
			// Twice identity element (point at infinity) is identity
			if (this.IsInfinity)
				return this;

			// if x1 == 0, then (x1, y1) == (x1, x1 + y1)
			// and hence this = -this and thus 2(x1, y1) == infinity
			if (this.x.ToBigInteger().SignValue == 0)
				return this.curve.Infinity;

			F2mFieldElement lambda = (F2mFieldElement) this.x.Add(this.y.Divide(this.x));
			F2mFieldElement x2 = (F2mFieldElement)lambda.Square().Add(lambda).Add(this.curve.A);
			ECFieldElement ONE = this.curve.FromBigInteger(BigInteger.One);
			F2mFieldElement y2 = (F2mFieldElement)this.x.Square().Add(
				x2.Multiply(lambda.Add(ONE)));

			return new F2mPoint(this.curve, x2, y2, withCompression);
		}

		public override ECPoint Negate()
		{
			return new F2mPoint(curve, this.x, this.x.Add(this.y), withCompression);
		}

		/**
		 * Sets the appropriate <code>ECMultiplier</code>, unless already set. 
		 */
		internal override void AssertECMultiplier()
		{
			if (this.multiplier == null)
			{
				lock (this)
				{
					if (this.multiplier == null)
					{
						if (((F2mCurve) this.curve).IsKoblitz)
						{
							this.multiplier = new WTauNafMultiplier();
						}
						else
						{
							this.multiplier = new WNafMultiplier();
						}
					}
				}
			}
		}
	}
}