diff options
Diffstat (limited to 'src/org/bouncycastle/math')
-rw-r--r-- | src/org/bouncycastle/math/ec/ECConstants.java | 12 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/ECCurve.java | 179 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/ECFieldElement.java | 780 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/ECMultiplier.java | 19 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/ECPoint.java | 335 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/FpNafMultiplier.java | 39 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/PreCompInfo.java | 10 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/WNafMultiplier.java | 240 | ||||
-rw-r--r-- | src/org/bouncycastle/math/ec/WNafPreCompInfo.java | 44 |
9 files changed, 1658 insertions, 0 deletions
diff --git a/src/org/bouncycastle/math/ec/ECConstants.java b/src/org/bouncycastle/math/ec/ECConstants.java new file mode 100644 index 0000000..864f746 --- /dev/null +++ b/src/org/bouncycastle/math/ec/ECConstants.java @@ -0,0 +1,12 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public interface ECConstants +{ + public static final BigInteger ZERO = BigInteger.valueOf(0); + public static final BigInteger ONE = BigInteger.valueOf(1); + public static final BigInteger TWO = BigInteger.valueOf(2); + public static final BigInteger THREE = BigInteger.valueOf(3); + public static final BigInteger FOUR = BigInteger.valueOf(4); +} diff --git a/src/org/bouncycastle/math/ec/ECCurve.java b/src/org/bouncycastle/math/ec/ECCurve.java new file mode 100644 index 0000000..ee7ddc3 --- /dev/null +++ b/src/org/bouncycastle/math/ec/ECCurve.java @@ -0,0 +1,179 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * 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 decodePoint(byte[] encoded); + + public abstract ECPoint getInfinity(); + + public ECFieldElement getA() + { + return a; + } + + public ECFieldElement getB() + { + return b; + } + + /** + * 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; + } + + @Override + public int getFieldSize() + { + return q.bitLength(); + } + + @Override + public ECFieldElement fromBigInteger(BigInteger x) + { + return new ECFieldElement.Fp(this.q, x); + } + + @Override + public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression) + { + return new ECPoint.Fp(this, fromBigInteger(x), fromBigInteger(y), withCompression); + } + + /** + * 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. + */ + @Override + public ECPoint decodePoint(byte[] encoded) + { + ECPoint p = null; + + switch (encoded[0]) + { + // infinity + case 0x00: + if (encoded.length > 1) + { + throw new RuntimeException("Invalid point encoding"); + } + p = getInfinity(); + break; + // compressed + case 0x02: + case 0x03: + int ytilde = encoded[0] & 1; + byte[] i = new byte[encoded.length - 1]; + + System.arraycopy(encoded, 1, i, 0, i.length); + + ECFieldElement x = new ECFieldElement.Fp(this.q, new BigInteger(1, i)); + 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"); + } + + int bit0 = (beta.toBigInteger().testBit(0) ? 1 : 0); + + if (bit0 == ytilde) + { + p = new ECPoint.Fp(this, x, beta, true); + } + else + { + p = new ECPoint.Fp(this, x, + new ECFieldElement.Fp(this.q, q.subtract(beta.toBigInteger())), true); + } + break; + // uncompressed + case 0x04: + // hybrid + case 0x06: + case 0x07: + byte[] xEnc = new byte[(encoded.length - 1) / 2]; + byte[] yEnc = new byte[(encoded.length - 1) / 2]; + + System.arraycopy(encoded, 1, xEnc, 0, xEnc.length); + System.arraycopy(encoded, xEnc.length + 1, yEnc, 0, yEnc.length); + + p = new ECPoint.Fp(this, + new ECFieldElement.Fp(this.q, new BigInteger(1, xEnc)), + new ECFieldElement.Fp(this.q, new BigInteger(1, yEnc))); + break; + default: + throw new RuntimeException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16)); + } + + return p; + } + + @Override + public ECPoint getInfinity() + { + return infinity; + } + + @Override + 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); + } + + @Override + public int hashCode() + { + return a.hashCode() ^ b.hashCode() ^ q.hashCode(); + } + } +} diff --git a/src/org/bouncycastle/math/ec/ECFieldElement.java b/src/org/bouncycastle/math/ec/ECFieldElement.java new file mode 100644 index 0000000..8c8f96e --- /dev/null +++ b/src/org/bouncycastle/math/ec/ECFieldElement.java @@ -0,0 +1,780 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; +import java.util.Random; + +public abstract class ECFieldElement + implements ECConstants +{ + + public abstract BigInteger toBigInteger(); + public abstract String getFieldName(); + public abstract int getFieldSize(); + public abstract ECFieldElement add(ECFieldElement b); + public abstract ECFieldElement subtract(ECFieldElement b); + public abstract ECFieldElement multiply(ECFieldElement b); + public abstract ECFieldElement divide(ECFieldElement b); + public abstract ECFieldElement negate(); + public abstract ECFieldElement square(); + public abstract ECFieldElement invert(); + public abstract ECFieldElement sqrt(); + + @Override + public String toString() + { + return this.toBigInteger().toString(2); + } + + public static class Fp extends ECFieldElement + { + BigInteger x; + + BigInteger q; + + public Fp(BigInteger q, BigInteger x) + { + this.x = x; + + if (x.compareTo(q) >= 0) + { + throw new IllegalArgumentException("x value too large in field element"); + } + + this.q = q; + } + + @Override + public BigInteger toBigInteger() + { + return x; + } + + /** + * return the field name for this field. + * + * @return the string "Fp". + */ + @Override + public String getFieldName() + { + return "Fp"; + } + + @Override + public int getFieldSize() + { + return q.bitLength(); + } + + public BigInteger getQ() + { + return q; + } + + @Override + public ECFieldElement add(ECFieldElement b) + { + return new Fp(q, x.add(b.toBigInteger()).mod(q)); + } + + @Override + public ECFieldElement subtract(ECFieldElement b) + { + return new Fp(q, x.subtract(b.toBigInteger()).mod(q)); + } + + @Override + public ECFieldElement multiply(ECFieldElement b) + { + return new Fp(q, x.multiply(b.toBigInteger()).mod(q)); + } + + @Override + public ECFieldElement divide(ECFieldElement b) + { + return new Fp(q, x.multiply(b.toBigInteger().modInverse(q)).mod(q)); + } + + @Override + public ECFieldElement negate() + { + return new Fp(q, x.negate().mod(q)); + } + + @Override + public ECFieldElement square() + { + return new Fp(q, x.multiply(x).mod(q)); + } + + @Override + public ECFieldElement invert() + { + return new Fp(q, x.modInverse(q)); + } + + // D.1.4 91 + /** + * return a sqrt root - the routine verifies that the calculation + * returns the right value - if none exists it returns null. + */ + @Override + public ECFieldElement sqrt() + { + if (!q.testBit(0)) + { + throw new RuntimeException("not done yet"); + } + + // note: even though this class implements ECConstants don't be tempted to + // remove the explicit declaration, some J2ME environments don't cope. + // p mod 4 == 3 + if (q.testBit(1)) + { + // z = g^(u+1) + p, p = 4u + 3 + ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q)); + + return z.square().equals(this) ? z : null; + } + + // p mod 4 == 1 + BigInteger qMinusOne = q.subtract(ECConstants.ONE); + + BigInteger legendreExponent = qMinusOne.shiftRight(1); + if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) + { + return null; + } + + BigInteger u = qMinusOne.shiftRight(2); + BigInteger k = u.shiftLeft(1).add(ECConstants.ONE); + + BigInteger Q = this.x; + BigInteger fourQ = Q.shiftLeft(2).mod(q); + + BigInteger U, V; + Random rand = new Random(); + do + { + BigInteger P; + do + { + P = new BigInteger(q.bitLength(), rand); + } + while (P.compareTo(q) >= 0 + || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne))); + + BigInteger[] result = lucasSequence(q, P, Q, k); + U = result[0]; + V = result[1]; + + if (V.multiply(V).mod(q).equals(fourQ)) + { + // Integer division by 2, mod q + if (V.testBit(0)) + { + V = V.add(q); + } + + V = V.shiftRight(1); + + //assert V.multiply(V).mod(q).equals(x); + + return new ECFieldElement.Fp(q, V); + } + } + while (U.equals(ECConstants.ONE) || U.equals(qMinusOne)); + + return null; + +// BigInteger qMinusOne = q.subtract(ECConstants.ONE); +// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO); +// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) +// { +// return null; +// } +// +// Random rand = new Random(); +// BigInteger fourX = x.shiftLeft(2); +// +// BigInteger r; +// do +// { +// r = new BigInteger(q.bitLength(), rand); +// } +// while (r.compareTo(q) >= 0 +// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne))); +// +// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR); +// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR); +// +// BigInteger wOne = WOne(r, x, q); +// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q); +// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r); +// +// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q) +// .multiply(x).mod(q) +// .multiply(wSum).mod(q); +// +// return new Fp(q, root); + } + +// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p) +// { +// if (n.equals(ECConstants.ONE)) +// { +// return wOne; +// } +// boolean isEven = !n.testBit(0); +// n = n.shiftRight(1);//divide(ECConstants.TWO); +// if (isEven) +// { +// BigInteger w = W(n, wOne, p); +// return w.multiply(w).subtract(ECConstants.TWO).mod(p); +// } +// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p); +// BigInteger w2 = W(n, wOne, p); +// return w1.multiply(w2).subtract(wOne).mod(p); +// } +// +// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p) +// { +// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p); +// } + + private static BigInteger[] lucasSequence( + BigInteger p, + BigInteger P, + BigInteger Q, + BigInteger k) + { + int n = k.bitLength(); + int s = k.getLowestSetBit(); + + BigInteger Uh = ECConstants.ONE; + BigInteger Vl = ECConstants.TWO; + BigInteger Vh = P; + BigInteger Ql = ECConstants.ONE; + BigInteger Qh = ECConstants.ONE; + + for (int j = n - 1; j >= s + 1; --j) + { + Ql = Ql.multiply(Qh).mod(p); + + if (k.testBit(j)) + { + Qh = Ql.multiply(Q).mod(p); + Uh = Uh.multiply(Vh).mod(p); + Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); + Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p); + } + else + { + Qh = Ql; + Uh = Uh.multiply(Vl).subtract(Ql).mod(p); + Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); + Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); + } + } + + Ql = Ql.multiply(Qh).mod(p); + Qh = Ql.multiply(Q).mod(p); + Uh = Uh.multiply(Vl).subtract(Ql).mod(p); + Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); + Ql = Ql.multiply(Qh).mod(p); + + for (int j = 1; j <= s; ++j) + { + Uh = Uh.multiply(Vl).mod(p); + Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); + Ql = Ql.multiply(Ql).mod(p); + } + + return new BigInteger[]{ Uh, Vl }; + } + + @Override + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof ECFieldElement.Fp)) + { + return false; + } + + ECFieldElement.Fp o = (ECFieldElement.Fp)other; + return q.equals(o.q) && x.equals(o.x); + } + + @Override + public int hashCode() + { + return q.hashCode() ^ x.hashCode(); + } + } + +// /** +// * Class representing the Elements of the finite field +// * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) +// * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial +// * basis representations are supported. Gaussian normal basis (GNB) +// * representation is not supported. +// */ +// public static class F2m extends ECFieldElement +// { +// BigInteger x; +// +// /** +// * Indicates gaussian normal basis representation (GNB). Number chosen +// * according to X9.62. GNB is not implemented at present. +// */ +// public static final int GNB = 1; +// +// /** +// * Indicates trinomial basis representation (TPB). Number chosen +// * according to X9.62. +// */ +// public static final int TPB = 2; +// +// /** +// * Indicates pentanomial basis representation (PPB). Number chosen +// * according to X9.62. +// */ +// public static final int PPB = 3; +// +// /** +// * TPB or PPB. +// */ +// private int representation; +// +// /** +// * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. +// */ +// private int m; +// +// /** +// * 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; +// +// /** +// * 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; +// +// /** +// * 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; +// +// /** +// * Constructor for 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 x The BigInteger representing the value of the field element. +// */ +// public F2m( +// int m, +// int k1, +// int k2, +// int k3, +// BigInteger x) +// { +//// super(x); +// this.x = x; +// +// if ((k2 == 0) && (k3 == 0)) +// { +// this.representation = TPB; +// } +// else +// { +// if (k2 >= k3) +// { +// throw new IllegalArgumentException( +// "k2 must be smaller than k3"); +// } +// if (k2 <= 0) +// { +// throw new IllegalArgumentException( +// "k2 must be larger than 0"); +// } +// this.representation = PPB; +// } +// +// if (x.signum() < 0) +// { +// throw new IllegalArgumentException("x value cannot be negative"); +// } +// +// this.m = m; +// this.k1 = k1; +// this.k2 = k2; +// this.k3 = k3; +// } +// +// /** +// * Constructor for 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 x The BigInteger representing the value of the field element. +// */ +// public F2m(int m, int k, BigInteger x) +// { +// // Set k1 to k, and set k2 and k3 to 0 +// this(m, k, 0, 0, x); +// } +// +// public BigInteger toBigInteger() +// { +// return x; +// } +// +// public String getFieldName() +// { +// return "F2m"; +// } +// +// public int getFieldSize() +// { +// return m; +// } +// +// /** +// * Checks, if the ECFieldElements <code>a</code> and <code>b</code> +// * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> +// * (having the same representation). +// * @param a field element. +// * @param b field element to be compared. +// * @throws IllegalArgumentException if <code>a</code> and <code>b</code> +// * are not elements of the same field +// * <code>F<sub>2<sup>m</sup></sub></code> (having the same +// * representation). +// */ +// public static void checkFieldElements( +// ECFieldElement a, +// ECFieldElement b) +// { +// if ((!(a instanceof F2m)) || (!(b instanceof F2m))) +// { +// throw new IllegalArgumentException("Field elements are not " +// + "both instances of ECFieldElement.F2m"); +// } +// +// if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0)) +// { +// throw new IllegalArgumentException( +// "x value may not be negative"); +// } +// +// ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; +// ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; +// +// if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) +// || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) +// { +// throw new IllegalArgumentException("Field elements are not " +// + "elements of the same field F2m"); +// } +// +// if (aF2m.representation != bF2m.representation) +// { +// // Should never occur +// throw new IllegalArgumentException( +// "One of the field " +// + "elements are not elements has incorrect representation"); +// } +// } +// +// /** +// * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is +// * the reduction polynomial of <code>this</code>. +// * @param a The polynomial <code>a(z)</code> to be multiplied by +// * <code>z mod f(z)</code>. +// * @return <code>z * a(z) mod f(z)</code> +// */ +// private BigInteger multZModF(final BigInteger a) +// { +// // Left-shift of a(z) +// BigInteger az = a.shiftLeft(1); +// if (az.testBit(this.m)) +// { +// // If the coefficient of z^m in a(z) equals 1, reduction +// // modulo f(z) is performed: Add f(z) to to a(z): +// // Step 1: Unset mth coeffient of a(z) +// az = az.clearBit(this.m); +// +// // Step 2: Add r(z) to a(z), where r(z) is defined as +// // f(z) = z^m + r(z), and k1, k2, k3 are the positions of +// // the non-zero coefficients in r(z) +// az = az.flipBit(0); +// az = az.flipBit(this.k1); +// if (this.representation == PPB) +// { +// az = az.flipBit(this.k2); +// az = az.flipBit(this.k3); +// } +// } +// return az; +// } +// +// public ECFieldElement add(final ECFieldElement b) +// { +// // No check performed here for performance reasons. Instead the +// // elements involved are checked in ECPoint.F2m +// // checkFieldElements(this, b); +// if (b.toBigInteger().signum() == 0) +// { +// return this; +// } +// +// return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger())); +// } +// +// public ECFieldElement subtract(final ECFieldElement b) +// { +// // Addition and subtraction are the same in F2m +// return add(b); +// } +// +// +// public ECFieldElement multiply(final ECFieldElement b) +// { +// // Left-to-right shift-and-add field multiplication in F2m +// // Input: Binary polynomials a(z) and b(z) of degree at most m-1 +// // Output: c(z) = a(z) * b(z) mod f(z) +// +// // No check performed here for performance reasons. Instead the +// // elements involved are checked in ECPoint.F2m +// // checkFieldElements(this, b); +// final BigInteger az = this.x; +// BigInteger bz = b.toBigInteger(); +// BigInteger cz; +// +// // Compute c(z) = a(z) * b(z) mod f(z) +// if (az.testBit(0)) +// { +// cz = bz; +// } +// else +// { +// cz = ECConstants.ZERO; +// } +// +// for (int i = 1; i < this.m; i++) +// { +// // b(z) := z * b(z) mod f(z) +// bz = multZModF(bz); +// +// if (az.testBit(i)) +// { +// // If the coefficient of x^i in a(z) equals 1, b(z) is added +// // to c(z) +// cz = cz.xor(bz); +// } +// } +// return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz); +// } +// +// +// public ECFieldElement divide(final ECFieldElement b) +// { +// // There may be more efficient implementations +// ECFieldElement bInv = b.invert(); +// return multiply(bInv); +// } +// +// public ECFieldElement negate() +// { +// // -x == x holds for all x in F2m +// return this; +// } +// +// public ECFieldElement square() +// { +// // Naive implementation, can probably be speeded up using modular +// // reduction +// return multiply(this); +// } +// +// public ECFieldElement invert() +// { +// // Inversion in F2m using the extended Euclidean algorithm +// // Input: A nonzero polynomial a(z) of degree at most m-1 +// // Output: a(z)^(-1) mod f(z) +// +// // u(z) := a(z) +// BigInteger uz = this.x; +// if (uz.signum() <= 0) +// { +// throw new ArithmeticException("x is zero or negative, " + +// "inversion is impossible"); +// } +// +// // v(z) := f(z) +// BigInteger vz = ECConstants.ZERO.setBit(m); +// vz = vz.setBit(0); +// vz = vz.setBit(this.k1); +// if (this.representation == PPB) +// { +// vz = vz.setBit(this.k2); +// vz = vz.setBit(this.k3); +// } +// +// // g1(z) := 1, g2(z) := 0 +// BigInteger g1z = ECConstants.ONE; +// BigInteger g2z = ECConstants.ZERO; +// +// // while u != 1 +// while (!(uz.equals(ECConstants.ZERO))) +// { +// // j := deg(u(z)) - deg(v(z)) +// int j = uz.bitLength() - vz.bitLength(); +// +// // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j +// if (j < 0) +// { +// final BigInteger uzCopy = uz; +// uz = vz; +// vz = uzCopy; +// +// final BigInteger g1zCopy = g1z; +// g1z = g2z; +// g2z = g1zCopy; +// +// j = -j; +// } +// +// // u(z) := u(z) + z^j * v(z) +// // Note, that no reduction modulo f(z) is required, because +// // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) +// // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) +// // = deg(u(z)) +// uz = uz.xor(vz.shiftLeft(j)); +// +// // g1(z) := g1(z) + z^j * g2(z) +// g1z = g1z.xor(g2z.shiftLeft(j)); +//// if (g1z.bitLength() > this.m) { +//// throw new ArithmeticException( +//// "deg(g1z) >= m, g1z = " + g1z.toString(2)); +//// } +// } +// return new ECFieldElement.F2m( +// this.m, this.k1, this.k2, this.k3, g2z); +// } +// +// public ECFieldElement sqrt() +// { +// throw new RuntimeException("Not implemented"); +// } +// +// /** +// * @return the representation of the field +// * <code>F<sub>2<sup>m</sup></sub></code>, either of +// * TPB (trinomial +// * basis representation) or +// * PPB (pentanomial +// * basis representation). +// */ +// public int getRepresentation() +// { +// return this.representation; +// } +// +// /** +// * @return the degree <code>m</code> of the reduction polynomial +// * <code>f(z)</code>. +// */ +// public int getM() +// { +// return this.m; +// } +// +// /** +// * @return 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> +// */ +// public int getK1() +// { +// return this.k1; +// } +// +// /** +// * @return TPB: Always returns <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> +// */ +// public int getK2() +// { +// return this.k2; +// } +// +// /** +// * @return 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> +// */ +// public int getK3() +// { +// return this.k3; +// } +// +// public boolean equals(Object anObject) +// { +// if (anObject == this) +// { +// return true; +// } +// +// if (!(anObject instanceof ECFieldElement.F2m)) +// { +// return false; +// } +// +// ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; +// +// return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) +// && (this.k3 == b.k3) +// && (this.representation == b.representation) +// && (this.x.equals(b.x))); +// } +// +// public int hashCode() +// { +// return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; +// } +// } +} diff --git a/src/org/bouncycastle/math/ec/ECMultiplier.java b/src/org/bouncycastle/math/ec/ECMultiplier.java new file mode 100644 index 0000000..4d72e33 --- /dev/null +++ b/src/org/bouncycastle/math/ec/ECMultiplier.java @@ -0,0 +1,19 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Interface for classes encapsulating a point multiplication algorithm + * for <code>ECPoint</code>s. + */ +interface ECMultiplier +{ + /** + * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e. + * <code>p</code> is added <code>k</code> times to itself. + * @param p The <code>ECPoint</code> to be multiplied. + * @param k The factor by which <code>p</code> i multiplied. + * @return <code>p</code> multiplied by <code>k</code>. + */ + ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo); +} diff --git a/src/org/bouncycastle/math/ec/ECPoint.java b/src/org/bouncycastle/math/ec/ECPoint.java new file mode 100644 index 0000000..f4056bb --- /dev/null +++ b/src/org/bouncycastle/math/ec/ECPoint.java @@ -0,0 +1,335 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * 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; + } + + @Override + 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); + } + + @Override + 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 abstract byte[] getEncoded(); + + 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() + { + return null; + // BEGIN connectbot-removed +// if (this.isInfinity()) +// { +// return new byte[1]; +// } +// +// int qLength = converter.getByteLength(x); +// +// if (withCompression) +// { +// 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 + @Override + 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); + } + + // B.3 pg 62 + @Override + 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:) + @Override + public ECPoint subtract(ECPoint b) + { + if (b.isInfinity()) + { + return this; + } + + // Add -b + return add(b.negate()); + } + + @Override + public ECPoint negate() + { + return new ECPoint.Fp(curve, this.x, this.y.negate(), this.withCompression); + } + + /** + * Sets the default <code>ECMultiplier</code>, unless already set. + */ + @Override + synchronized void assertECMultiplier() + { + if (this.multiplier == null) + { + this.multiplier = new WNafMultiplier(); + } + } + } +} diff --git a/src/org/bouncycastle/math/ec/FpNafMultiplier.java b/src/org/bouncycastle/math/ec/FpNafMultiplier.java new file mode 100644 index 0000000..35e601d --- /dev/null +++ b/src/org/bouncycastle/math/ec/FpNafMultiplier.java @@ -0,0 +1,39 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm. + */ +class FpNafMultiplier implements ECMultiplier +{ + /** + * D.3.2 pg 101 + * @see org.bouncycastle.math.ec.ECMultiplier#multiply(org.bouncycastle.math.ec.ECPoint, java.math.BigInteger) + */ + public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) + { + // TODO Probably should try to add this + // BigInteger e = k.mod(n); // n == order of p + BigInteger e = k; + BigInteger h = e.multiply(BigInteger.valueOf(3)); + + ECPoint neg = p.negate(); + ECPoint R = p; + + for (int i = h.bitLength() - 2; i > 0; --i) + { + R = R.twice(); + + boolean hBit = h.testBit(i); + boolean eBit = e.testBit(i); + + if (hBit != eBit) + { + R = R.add(hBit ? p : neg); + } + } + + return R; + } +} diff --git a/src/org/bouncycastle/math/ec/PreCompInfo.java b/src/org/bouncycastle/math/ec/PreCompInfo.java new file mode 100644 index 0000000..804dcf7 --- /dev/null +++ b/src/org/bouncycastle/math/ec/PreCompInfo.java @@ -0,0 +1,10 @@ +package org.bouncycastle.math.ec; + +/** + * Interface for classes storing precomputation data for multiplication + * algorithms. Used as a Memento (see GOF patterns) for + * <code>WNafMultiplier</code>. + */ +interface PreCompInfo +{ +} diff --git a/src/org/bouncycastle/math/ec/WNafMultiplier.java b/src/org/bouncycastle/math/ec/WNafMultiplier.java new file mode 100644 index 0000000..10c8ed2 --- /dev/null +++ b/src/org/bouncycastle/math/ec/WNafMultiplier.java @@ -0,0 +1,240 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the WNAF (Window Non-Adjacent Form) multiplication + * algorithm. + */ +class WNafMultiplier implements ECMultiplier +{ + /** + * Computes the Window NAF (non-adjacent Form) of an integer. + * @param width The width <code>w</code> of the Window NAF. The width is + * defined as the minimal number <code>w</code>, such that for any + * <code>w</code> consecutive digits in the resulting representation, at + * most one is non-zero. + * @param k The integer of which the Window NAF is computed. + * @return The Window NAF of the given width, such that the following holds: + * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> + * </code>, where the <code>k<sub>i</sub></code> denote the elements of the + * returned <code>byte[]</code>. + */ + public byte[] windowNaf(byte width, BigInteger k) + { + // The window NAF is at most 1 element longer than the binary + // representation of the integer k. byte can be used instead of short or + // int unless the window width is larger than 8. For larger width use + // short or int. However, a width of more than 8 is not efficient for + // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than + // 1000 Bits are currently not used in practice. + byte[] wnaf = new byte[k.bitLength() + 1]; + + // 2^width as short and BigInteger + short pow2wB = (short)(1 << width); + BigInteger pow2wBI = BigInteger.valueOf(pow2wB); + + int i = 0; + + // The actual length of the WNAF + int length = 0; + + // while k >= 1 + while (k.signum() > 0) + { + // if k is odd + if (k.testBit(0)) + { + // k mod 2^width + BigInteger remainder = k.mod(pow2wBI); + + // if remainder > 2^(width - 1) - 1 + if (remainder.testBit(width - 1)) + { + wnaf[i] = (byte)(remainder.intValue() - pow2wB); + } + else + { + wnaf[i] = (byte)remainder.intValue(); + } + // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1] + + k = k.subtract(BigInteger.valueOf(wnaf[i])); + length = i; + } + else + { + wnaf[i] = 0; + } + + // k = k/2 + k = k.shiftRight(1); + i++; + } + + length++; + + // Reduce the WNAF array to its actual length + byte[] wnafShort = new byte[length]; + System.arraycopy(wnaf, 0, wnafShort, 0, length); + return wnafShort; + } + + /** + * Multiplies <code>this</code> by an integer <code>k</code> using the + * Window NAF method. + * @param k The integer by which <code>this</code> is multiplied. + * @return A new <code>ECPoint</code> which equals <code>this</code> + * multiplied by <code>k</code>. + */ + public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) + { + WNafPreCompInfo wnafPreCompInfo; + + if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo)) + { + wnafPreCompInfo = (WNafPreCompInfo)preCompInfo; + } + else + { + // Ignore empty PreCompInfo or PreCompInfo of incorrect type + wnafPreCompInfo = new WNafPreCompInfo(); + } + + // floor(log2(k)) + int m = k.bitLength(); + + // width of the Window NAF + byte width; + + // Required length of precomputation array + int reqPreCompLen; + + // Determine optimal width and corresponding length of precomputation + // array based on literature values + if (m < 13) + { + width = 2; + reqPreCompLen = 1; + } + else + { + if (m < 41) + { + width = 3; + reqPreCompLen = 2; + } + else + { + if (m < 121) + { + width = 4; + reqPreCompLen = 4; + } + else + { + if (m < 337) + { + width = 5; + reqPreCompLen = 8; + } + else + { + if (m < 897) + { + width = 6; + reqPreCompLen = 16; + } + else + { + if (m < 2305) + { + width = 7; + reqPreCompLen = 32; + } + else + { + width = 8; + reqPreCompLen = 127; + } + } + } + } + } + } + + // The length of the precomputation array + int preCompLen = 1; + + ECPoint[] preComp = wnafPreCompInfo.getPreComp(); + ECPoint twiceP = wnafPreCompInfo.getTwiceP(); + + // Check if the precomputed ECPoints already exist + if (preComp == null) + { + // Precomputation must be performed from scratch, create an empty + // precomputation array of desired length + preComp = new ECPoint[]{ p }; + } + else + { + // Take the already precomputed ECPoints to start with + preCompLen = preComp.length; + } + + if (twiceP == null) + { + // Compute twice(p) + twiceP = p.twice(); + } + + if (preCompLen < reqPreCompLen) + { + // Precomputation array must be made bigger, copy existing preComp + // array into the larger new preComp array + ECPoint[] oldPreComp = preComp; + preComp = new ECPoint[reqPreCompLen]; + System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen); + + for (int i = preCompLen; i < reqPreCompLen; i++) + { + // Compute the new ECPoints for the precomputation array. + // The values 1, 3, 5, ..., 2^(width-1)-1 times p are + // computed + preComp[i] = twiceP.add(preComp[i - 1]); + } + } + + // Compute the Window NAF of the desired width + byte[] wnaf = windowNaf(width, k); + int l = wnaf.length; + + // Apply the Window NAF to p using the precomputed ECPoint values. + ECPoint q = p.getCurve().getInfinity(); + for (int i = l - 1; i >= 0; i--) + { + q = q.twice(); + + if (wnaf[i] != 0) + { + if (wnaf[i] > 0) + { + q = q.add(preComp[(wnaf[i] - 1)/2]); + } + else + { + // wnaf[i] < 0 + q = q.subtract(preComp[(-wnaf[i] - 1)/2]); + } + } + } + + // Set PreCompInfo in ECPoint, such that it is available for next + // multiplication. + wnafPreCompInfo.setPreComp(preComp); + wnafPreCompInfo.setTwiceP(twiceP); + p.setPreCompInfo(wnafPreCompInfo); + return q; + } + +} diff --git a/src/org/bouncycastle/math/ec/WNafPreCompInfo.java b/src/org/bouncycastle/math/ec/WNafPreCompInfo.java new file mode 100644 index 0000000..fc0d5fe --- /dev/null +++ b/src/org/bouncycastle/math/ec/WNafPreCompInfo.java @@ -0,0 +1,44 @@ +package org.bouncycastle.math.ec; + +/** + * Class holding precomputation data for the WNAF (Window Non-Adjacent Form) + * algorithm. + */ +class WNafPreCompInfo implements PreCompInfo +{ + /** + * Array holding the precomputed <code>ECPoint</code>s used for the Window + * NAF multiplication in <code> + * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() + * WNafMultiplier.multiply()}</code>. + */ + private ECPoint[] preComp = null; + + /** + * Holds an <code>ECPoint</code> representing twice(this). Used for the + * Window NAF multiplication in <code> + * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() + * WNafMultiplier.multiply()}</code>. + */ + private ECPoint twiceP = null; + + protected ECPoint[] getPreComp() + { + return preComp; + } + + protected void setPreComp(ECPoint[] preComp) + { + this.preComp = preComp; + } + + protected ECPoint getTwiceP() + { + return twiceP; + } + + protected void setTwiceP(ECPoint twiceThis) + { + this.twiceP = twiceThis; + } +} |