diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/math/ec/ECPoint.java')
| -rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/ECPoint.java | 593 |
1 files changed, 593 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java b/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java new file mode 100644 index 00000000..cbc5aaf4 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java @@ -0,0 +1,593 @@ +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(); + } + } + } + } +} |