diff options
Diffstat (limited to 'src/org/bouncycastle/math/ec')
-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, 0 insertions, 1658 deletions
diff --git a/src/org/bouncycastle/math/ec/ECConstants.java b/src/org/bouncycastle/math/ec/ECConstants.java deleted file mode 100644 index 864f746..0000000 --- a/src/org/bouncycastle/math/ec/ECConstants.java +++ /dev/null @@ -1,12 +0,0 @@ -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 deleted file mode 100644 index ee7ddc3..0000000 --- a/src/org/bouncycastle/math/ec/ECCurve.java +++ /dev/null @@ -1,179 +0,0 @@ -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 deleted file mode 100644 index 8c8f96e..0000000 --- a/src/org/bouncycastle/math/ec/ECFieldElement.java +++ /dev/null @@ -1,780 +0,0 @@ -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 deleted file mode 100644 index 4d72e33..0000000 --- a/src/org/bouncycastle/math/ec/ECMultiplier.java +++ /dev/null @@ -1,19 +0,0 @@ -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 deleted file mode 100644 index f4056bb..0000000 --- a/src/org/bouncycastle/math/ec/ECPoint.java +++ /dev/null @@ -1,335 +0,0 @@ -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 deleted file mode 100644 index 35e601d..0000000 --- a/src/org/bouncycastle/math/ec/FpNafMultiplier.java +++ /dev/null @@ -1,39 +0,0 @@ -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 deleted file mode 100644 index 804dcf7..0000000 --- a/src/org/bouncycastle/math/ec/PreCompInfo.java +++ /dev/null @@ -1,10 +0,0 @@ -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 deleted file mode 100644 index 10c8ed2..0000000 --- a/src/org/bouncycastle/math/ec/WNafMultiplier.java +++ /dev/null @@ -1,240 +0,0 @@ -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 deleted file mode 100644 index fc0d5fe..0000000 --- a/src/org/bouncycastle/math/ec/WNafPreCompInfo.java +++ /dev/null @@ -1,44 +0,0 @@ -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; - } -} |