diff options
Diffstat (limited to 'src/org/bouncycastle/math/ec/ECFieldElement.java')
| -rw-r--r-- | src/org/bouncycastle/math/ec/ECFieldElement.java | 780 |
1 files changed, 0 insertions, 780 deletions
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; -// } -// } -} |