| 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(); |
| |
| 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; |
| } |
| |
| public BigInteger toBigInteger() |
| { |
| return x; |
| } |
| |
| /** |
| * return the field name for this field. |
| * |
| * @return the string "Fp". |
| */ |
| public String getFieldName() |
| { |
| return "Fp"; |
| } |
| |
| public int getFieldSize() |
| { |
| return q.bitLength(); |
| } |
| |
| public BigInteger getQ() |
| { |
| return q; |
| } |
| |
| public ECFieldElement add(ECFieldElement b) |
| { |
| return new Fp(q, x.add(b.toBigInteger()).mod(q)); |
| } |
| |
| public ECFieldElement subtract(ECFieldElement b) |
| { |
| return new Fp(q, x.subtract(b.toBigInteger()).mod(q)); |
| } |
| |
| public ECFieldElement multiply(ECFieldElement b) |
| { |
| return new Fp(q, x.multiply(b.toBigInteger()).mod(q)); |
| } |
| |
| public ECFieldElement divide(ECFieldElement b) |
| { |
| return new Fp(q, x.multiply(b.toBigInteger().modInverse(q)).mod(q)); |
| } |
| |
| public ECFieldElement negate() |
| { |
| return new Fp(q, x.negate().mod(q)); |
| } |
| |
| public ECFieldElement square() |
| { |
| return new Fp(q, x.multiply(x).mod(q)); |
| } |
| |
| 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. |
| */ |
| 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 }; |
| } |
| |
| 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); |
| } |
| |
| 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; |
| // } |
| // } |
| |
| /** |
| * 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 |
| { |
| /** |
| * 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; |
| |
| /** |
| * The <code>IntArray</code> holding the bits. |
| */ |
| private IntArray x; |
| |
| /** |
| * The number of <code>int</code>s required to hold <code>m</code> bits. |
| */ |
| private int t; |
| |
| /** |
| * 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) |
| { |
| // t = m / 32 rounded up to the next integer |
| t = (m + 31) >> 5; |
| this.x = new IntArray(x, t); |
| |
| 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); |
| } |
| |
| private F2m(int m, int k1, int k2, int k3, IntArray x) |
| { |
| t = (m + 31) >> 5; |
| this.x = x; |
| this.m = m; |
| this.k1 = k1; |
| this.k2 = k2; |
| this.k3 = k3; |
| |
| if ((k2 == 0) && (k3 == 0)) |
| { |
| this.representation = TPB; |
| } |
| else |
| { |
| this.representation = PPB; |
| } |
| |
| } |
| |
| public BigInteger toBigInteger() |
| { |
| return x.toBigInteger(); |
| } |
| |
| 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"); |
| } |
| |
| 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"); |
| } |
| } |
| |
| 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); |
| IntArray iarrClone = (IntArray)this.x.clone(); |
| F2m bF2m = (F2m)b; |
| iarrClone.addShifted(bF2m.x, 0); |
| return new F2m(m, k1, k2, k3, iarrClone); |
| } |
| |
| public ECFieldElement subtract(final ECFieldElement b) |
| { |
| // Addition and subtraction are the same in F2m |
| return add(b); |
| } |
| |
| public ECFieldElement multiply(final ECFieldElement b) |
| { |
| // Right-to-left comb multiplication in the IntArray |
| // 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); |
| F2m bF2m = (F2m)b; |
| IntArray mult = x.multiply(bF2m.x, m); |
| mult.reduce(m, new int[]{k1, k2, k3}); |
| return new F2m(m, k1, k2, k3, mult); |
| } |
| |
| 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() |
| { |
| IntArray squared = x.square(m); |
| squared.reduce(m, new int[]{k1, k2, k3}); |
| return new F2m(m, k1, k2, k3, squared); |
| } |
| |
| |
| 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) |
| IntArray uz = (IntArray)this.x.clone(); |
| |
| // v(z) := f(z) |
| IntArray vz = new IntArray(t); |
| vz.setBit(m); |
| vz.setBit(0); |
| vz.setBit(this.k1); |
| if (this.representation == PPB) |
| { |
| vz.setBit(this.k2); |
| vz.setBit(this.k3); |
| } |
| |
| // g1(z) := 1, g2(z) := 0 |
| IntArray g1z = new IntArray(t); |
| g1z.setBit(0); |
| IntArray g2z = new IntArray(t); |
| |
| // while u != 0 |
| while (!uz.isZero()) |
| // while (uz.getUsedLength() > 0) |
| // while (uz.bitLength() > 1) |
| { |
| // 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 IntArray uzCopy = uz; |
| uz = vz; |
| vz = uzCopy; |
| |
| final IntArray 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)); |
| // jInt = n / 32 |
| int jInt = j >> 5; |
| // jInt = n % 32 |
| int jBit = j & 0x1F; |
| IntArray vzShift = vz.shiftLeft(jBit); |
| uz.addShifted(vzShift, jInt); |
| |
| // g1(z) := g1(z) + z^j * g2(z) |
| // g1z = g1z.xor(g2z.shiftLeft(j)); |
| IntArray g2zShift = g2z.shiftLeft(jBit); |
| g1z.addShifted(g2zShift, jInt); |
| |
| } |
| 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; |
| } |
| } |
| } |
