math/ec/ECPoint.java

package org.bouncycastle.math.ec;

import java.math.BigInteger;

import org.bouncycastle.asn1.x9.X9IntegerConverter;

/**
 * base class for points on elliptic curves.
 */
public abstract class ECPoint
{
    ECCurve        curve;
    ECFieldElement x;
    ECFieldElement y;

    protected boolean withCompression;

    protected ECMultiplier multiplier = null;

    protected PreCompInfo preCompInfo = null;

    private static X9IntegerConverter converter = new X9IntegerConverter();

    protected ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y)
    {
        this.curve = curve;
        this.x = x;
        this.y = y;
    }

    public ECCurve getCurve()
    {
        return curve;
    }

    public ECFieldElement getX()
    {
        return x;
    }

    public ECFieldElement getY()
    {
        return y;
    }

    public boolean isInfinity()
    {
        return x == null && y == null;
    }

    public boolean isCompressed()
    {
        return withCompression;
    }

    public boolean equals(
        Object  other)
    {
        if (other == this)
        {
            return true;
        }

        if (!(other instanceof ECPoint))
        {
            return false;
        }

        ECPoint o = (ECPoint)other;

        if (this.isInfinity())
        {
            return o.isInfinity();
        }

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

    public int hashCode()
    {
        if (this.isInfinity())
        {
            return 0;
        }

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

//    /**
//     * Mainly for testing. Explicitly set the <code>ECMultiplier</code>.
//     * @param multiplier The <code>ECMultiplier</code> to be used to multiply
//     * this <code>ECPoint</code>.
//     */
//    public 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>.
     */
    void setPreCompInfo(PreCompInfo preCompInfo)
    {
        this.preCompInfo = preCompInfo;
    }

    public byte[] getEncoded()
    {
        return getEncoded(withCompression);
    }

    public abstract byte[] getEncoded(boolean compressed);

    public abstract ECPoint add(ECPoint b);
    public abstract ECPoint subtract(ECPoint b);
    public abstract ECPoint negate();
    public abstract ECPoint twice();

    /**
     * Sets the default <code>ECMultiplier</code>, unless already set.
     */
    synchronized void assertECMultiplier()
    {
        if (this.multiplier == null)
        {
            this.multiplier = new FpNafMultiplier();
        }
    }

    /**
     * Multiplies this <code>ECPoint</code> by the given number.
     * @param k The multiplicator.
     * @return <code>k * this</code>.
     */
    public ECPoint multiply(BigInteger k)
    {
        if (k.signum() < 0)
        {
            throw new IllegalArgumentException("The multiplicator cannot be negative");
        }

        if (this.isInfinity())
        {
            return this;
        }

        if (k.signum() == 0)
        {
            return this.curve.getInfinity();
        }

        assertECMultiplier();
        return this.multiplier.multiply(this, k, preCompInfo);
    }

    /**
     * Elliptic curve points over Fp
     */
    public static class Fp extends ECPoint
    {

        /**
         * 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 Fp(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 Fp(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression)
        {
            super(curve, x, y);

            if ((x != null && y == null) || (x == null && y != null))
            {
                throw new IllegalArgumentException("Exactly one of the field elements is null");
            }

            this.withCompression = withCompression;
        }

        /**
         * return the field element encoded with point compression. (S 4.3.6)
         */
        public byte[] getEncoded(boolean compressed)
        {
            if (this.isInfinity())
            {
                return new byte[1];
            }

            int qLength = converter.getByteLength(x);

            if (compressed)
            {
                byte    PC;

                if (this.getY().toBigInteger().testBit(0))
                {
                    PC = 0x03;
                }
                else
                {
                    PC = 0x02;
                }

                byte[]  X = converter.integerToBytes(this.getX().toBigInteger(), qLength);
                byte[]  PO = new byte[X.length + 1];

                PO[0] = PC;
                System.arraycopy(X, 0, PO, 1, X.length);

                return PO;
            }
            else
            {
                byte[]  X = converter.integerToBytes(this.getX().toBigInteger(), qLength);
                byte[]  Y = converter.integerToBytes(this.getY().toBigInteger(), qLength);
                byte[]  PO = new byte[X.length + Y.length + 1];

                PO[0] = 0x04;
                System.arraycopy(X, 0, PO, 1, X.length);
                System.arraycopy(Y, 0, PO, X.length + 1, Y.length);

                return PO;
            }
        }

        // B.3 pg 62
        public 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();
                }

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

            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 ECPoint.Fp(curve, x3, y3, withCompression);
        }

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

            if (this.y.toBigInteger().signum() == 0)
            {
                // if y1 == 0, then (x1, y1) == (x1, -y1)
                // and hence this = -this and thus 2(x1, y1) == infinity
                return this.curve.getInfinity();
            }

            ECFieldElement TWO = this.curve.fromBigInteger(BigInteger.valueOf(2));
            ECFieldElement THREE = this.curve.fromBigInteger(BigInteger.valueOf(3));
            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 ECPoint.Fp(curve, x3, y3, this.withCompression);
        }

        // D.3.2 pg 102 (see Note:)
        public ECPoint subtract(ECPoint b)
        {
            if (b.isInfinity())
            {
                return this;
            }

            // Add -b
            return add(b.negate());
        }

        public ECPoint negate()
        {
            return new ECPoint.Fp(curve, this.x, this.y.negate(), this.withCompression);
        }

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

    /**
     * Elliptic curve points over F2m
     */
    public static class F2m extends ECPoint
    {
        /**
         * @param curve base curve
         * @param x x point
         * @param y y point
         */
        public F2m(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 F2m(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression)
        {
            super(curve, x, y);

            if ((x != null && y == null) || (x == null && y != null))
            {
                throw new IllegalArgumentException("Exactly one of the field elements is null");
            }

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

                // Check if x and a are elements of the same field
                if (curve != null)
                {
                    ECFieldElement.F2m.checkFieldElements(this.x, this.curve.getA());
                }
            }

            this.withCompression = withCompression;
        }

        /* (non-Javadoc)
         * @see org.bouncycastle.math.ec.ECPoint#getEncoded()
         */
        public byte[] getEncoded(boolean compressed)
        {
            if (this.isInfinity())
            {
                return new byte[1];
            }

            int byteCount = converter.getByteLength(this.x);
            byte[] X = converter.integerToBytes(this.getX().toBigInteger(), byteCount);
            byte[] PO;

            if (compressed)
            {
                // See X9.62 4.3.6 and 4.2.2
                PO = new byte[byteCount + 1];

                PO[0] = 0x02;
                // 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)
                // if ypTilde = 0, then PC := 02, else PC := 03
                // Note: PC === PO[0]
                if (!(this.getX().toBigInteger().equals(ECConstants.ZERO)))
                {
                    if (this.getY().multiply(this.getX().invert())
                            .toBigInteger().testBit(0))
                    {
                        // ypTilde = 1, hence PC = 03
                        PO[0] = 0x03;
                    }
                }

                System.arraycopy(X, 0, PO, 1, byteCount);
            }
            else
            {
                byte[] Y = converter.integerToBytes(this.getY().toBigInteger(), byteCount);

                PO = new byte[byteCount + byteCount + 1];

                PO[0] = 0x04;
                System.arraycopy(X, 0, PO, 1, byteCount);
                System.arraycopy(Y, 0, PO, byteCount + 1, byteCount);
            }

            return PO;
        }

        /**
         * 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 IllegalArgumentException("Only points on the same "
                        + "curve can be added or subtracted");
            }

//            ECFieldElement.F2m.checkFieldElements(a.x, b.x);
        }

        /* (non-Javadoc)
         * @see org.bouncycastle.math.ec.ECPoint#add(org.bouncycastle.math.ec.ECPoint)
         */
        public ECPoint add(ECPoint b)
        {
            checkPoints(this, b);
            return addSimple((ECPoint.F2m)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>
         */
        public ECPoint.F2m addSimple(ECPoint.F2m b)
        {
            ECPoint.F2m other = b;
            if (this.isInfinity())
            {
                return other;
            }

            if (other.isInfinity())
            {
                return this;
            }

            ECFieldElement.F2m x2 = (ECFieldElement.F2m)other.getX();
            ECFieldElement.F2m y2 = (ECFieldElement.F2m)other.getY();

            // Check if other = this or other = -this
            if (this.x.equals(x2))
            {
                if (this.y.equals(y2))
                {
                    // this = other, i.e. this must be doubled
                    return (ECPoint.F2m)this.twice();
                }

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

            ECFieldElement.F2m lambda
                = (ECFieldElement.F2m)(this.y.add(y2)).divide(this.x.add(x2));

            ECFieldElement.F2m x3
                = (ECFieldElement.F2m)lambda.square().add(lambda).add(this.x).add(x2).add(this.curve.getA());

            ECFieldElement.F2m y3
                = (ECFieldElement.F2m)lambda.multiply(this.x.add(x3)).add(x3).add(this.y);

            return new ECPoint.F2m(curve, x3, y3, withCompression);
        }

        /* (non-Javadoc)
         * @see org.bouncycastle.math.ec.ECPoint#subtract(org.bouncycastle.math.ec.ECPoint)
         */
        public ECPoint subtract(ECPoint b)
        {
            checkPoints(this, b);
            return subtractSimple((ECPoint.F2m)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>
         */
        public ECPoint.F2m subtractSimple(ECPoint.F2m b)
        {
            if (b.isInfinity())
            {
                return this;
            }

            // Add -b
            return addSimple((ECPoint.F2m)b.negate());
        }

        /* (non-Javadoc)
         * @see org.bouncycastle.math.ec.ECPoint#twice()
         */
        public ECPoint twice()
        {
            if (this.isInfinity())
            {
                // Twice identity element (point at infinity) is identity
                return this;
            }

            if (this.x.toBigInteger().signum() == 0)
            {
                // if x1 == 0, then (x1, y1) == (x1, x1 + y1)
                // and hence this = -this and thus 2(x1, y1) == infinity
                return this.curve.getInfinity();
            }

            ECFieldElement.F2m lambda
                = (ECFieldElement.F2m)this.x.add(this.y.divide(this.x));

            ECFieldElement.F2m x3
                = (ECFieldElement.F2m)lambda.square().add(lambda).
                    add(this.curve.getA());

            ECFieldElement ONE = this.curve.fromBigInteger(ECConstants.ONE);
            ECFieldElement.F2m y3
                = (ECFieldElement.F2m)this.x.square().add(
                    x3.multiply(lambda.add(ONE)));

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

        public ECPoint negate()
        {
            return new ECPoint.F2m(curve, this.getX(), this.getY().add(this.getX()), withCompression);
        }

        /**
         * Sets the appropriate <code>ECMultiplier</code>, unless already set.
         */
        synchronized void assertECMultiplier()
        {
            if (this.multiplier == null)
            {
                if (((ECCurve.F2m)this.curve).isKoblitz())
                {
                    this.multiplier = new WTauNafMultiplier();
                }
                else
                {
                    this.multiplier = new WNafMultiplier();
                }
            }
        }
    }
}