0001: package org.bouncycastle.math.ec;
0002:
0003: import java.math.BigInteger;
0004: import java.util.Random;
0005:
0006: public abstract class ECFieldElement implements ECConstants {
0007:
0008: public abstract BigInteger toBigInteger();
0009:
0010: public abstract String getFieldName();
0011:
0012: public abstract int getFieldSize();
0013:
0014: public abstract ECFieldElement add(ECFieldElement b);
0015:
0016: public abstract ECFieldElement subtract(ECFieldElement b);
0017:
0018: public abstract ECFieldElement multiply(ECFieldElement b);
0019:
0020: public abstract ECFieldElement divide(ECFieldElement b);
0021:
0022: public abstract ECFieldElement negate();
0023:
0024: public abstract ECFieldElement square();
0025:
0026: public abstract ECFieldElement invert();
0027:
0028: public abstract ECFieldElement sqrt();
0029:
0030: public String toString() {
0031: return this .toBigInteger().toString(2);
0032: }
0033:
0034: public static class Fp extends ECFieldElement {
0035: BigInteger x;
0036:
0037: BigInteger q;
0038:
0039: public Fp(BigInteger q, BigInteger x) {
0040: this .x = x;
0041:
0042: if (x.compareTo(q) >= 0) {
0043: throw new IllegalArgumentException(
0044: "x value too large in field element");
0045: }
0046:
0047: this .q = q;
0048: }
0049:
0050: public BigInteger toBigInteger() {
0051: return x;
0052: }
0053:
0054: /**
0055: * return the field name for this field.
0056: *
0057: * @return the string "Fp".
0058: */
0059: public String getFieldName() {
0060: return "Fp";
0061: }
0062:
0063: public int getFieldSize() {
0064: return q.bitLength();
0065: }
0066:
0067: public BigInteger getQ() {
0068: return q;
0069: }
0070:
0071: public ECFieldElement add(ECFieldElement b) {
0072: return new Fp(q, x.add(b.toBigInteger()).mod(q));
0073: }
0074:
0075: public ECFieldElement subtract(ECFieldElement b) {
0076: return new Fp(q, x.subtract(b.toBigInteger()).mod(q));
0077: }
0078:
0079: public ECFieldElement multiply(ECFieldElement b) {
0080: return new Fp(q, x.multiply(b.toBigInteger()).mod(q));
0081: }
0082:
0083: public ECFieldElement divide(ECFieldElement b) {
0084: return new Fp(q, x.multiply(b.toBigInteger().modInverse(q))
0085: .mod(q));
0086: }
0087:
0088: public ECFieldElement negate() {
0089: return new Fp(q, x.negate().mod(q));
0090: }
0091:
0092: public ECFieldElement square() {
0093: return new Fp(q, x.multiply(x).mod(q));
0094: }
0095:
0096: public ECFieldElement invert() {
0097: return new Fp(q, x.modInverse(q));
0098: }
0099:
0100: // D.1.4 91
0101: /**
0102: * return a sqrt root - the routine verifies that the calculation
0103: * returns the right value - if none exists it returns null.
0104: */
0105: public ECFieldElement sqrt() {
0106: if (!q.testBit(0)) {
0107: throw new RuntimeException("not done yet");
0108: }
0109:
0110: // p mod 4 == 3
0111: if (q.testBit(1)) {
0112: // z = g^(u+1) + p, p = 4u + 3
0113: ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2)
0114: .add(ONE), q));
0115:
0116: return z.square().equals(this ) ? z : null;
0117: }
0118:
0119: // p mod 4 == 1
0120: BigInteger qMinusOne = q.subtract(ECConstants.ONE);
0121:
0122: BigInteger legendreExponent = qMinusOne.shiftRight(1);
0123: if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) {
0124: return null;
0125: }
0126:
0127: BigInteger u = qMinusOne.shiftRight(2);
0128: BigInteger k = u.shiftLeft(1).add(ECConstants.ONE);
0129:
0130: BigInteger Q = this .x;
0131: BigInteger fourQ = Q.shiftLeft(2).mod(q);
0132:
0133: BigInteger U, V;
0134: Random rand = new Random();
0135: do {
0136: BigInteger P;
0137: do {
0138: P = new BigInteger(q.bitLength(), rand);
0139: } while (P.compareTo(q) >= 0
0140: || !(P.multiply(P).subtract(fourQ).modPow(
0141: legendreExponent, q).equals(qMinusOne)));
0142:
0143: BigInteger[] result = lucasSequence(q, P, Q, k);
0144: U = result[0];
0145: V = result[1];
0146:
0147: if (V.multiply(V).mod(q).equals(fourQ)) {
0148: // Integer division by 2, mod q
0149: if (V.testBit(0)) {
0150: V = V.add(q);
0151: }
0152:
0153: V = V.shiftRight(1);
0154:
0155: //assert V.multiply(V).mod(q).equals(x);
0156:
0157: return new ECFieldElement.Fp(q, V);
0158: }
0159: } while (U.equals(ECConstants.ONE) || U.equals(qMinusOne));
0160:
0161: return null;
0162:
0163: // BigInteger qMinusOne = q.subtract(ECConstants.ONE);
0164: // BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO);
0165: // if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
0166: // {
0167: // return null;
0168: // }
0169: //
0170: // Random rand = new Random();
0171: // BigInteger fourX = x.shiftLeft(2);
0172: //
0173: // BigInteger r;
0174: // do
0175: // {
0176: // r = new BigInteger(q.bitLength(), rand);
0177: // }
0178: // while (r.compareTo(q) >= 0
0179: // || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne)));
0180: //
0181: // BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR);
0182: // BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR);
0183: //
0184: // BigInteger wOne = WOne(r, x, q);
0185: // BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q);
0186: // BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r);
0187: //
0188: // BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q)
0189: // .multiply(x).mod(q)
0190: // .multiply(wSum).mod(q);
0191: //
0192: // return new Fp(q, root);
0193: }
0194:
0195: // private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
0196: // {
0197: // if (n.equals(ECConstants.ONE))
0198: // {
0199: // return wOne;
0200: // }
0201: // boolean isEven = !n.testBit(0);
0202: // n = n.shiftRight(1);//divide(ECConstants.TWO);
0203: // if (isEven)
0204: // {
0205: // BigInteger w = W(n, wOne, p);
0206: // return w.multiply(w).subtract(ECConstants.TWO).mod(p);
0207: // }
0208: // BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p);
0209: // BigInteger w2 = W(n, wOne, p);
0210: // return w1.multiply(w2).subtract(wOne).mod(p);
0211: // }
0212: //
0213: // private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
0214: // {
0215: // return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p);
0216: // }
0217:
0218: private static BigInteger[] lucasSequence(BigInteger p,
0219: BigInteger P, BigInteger Q, BigInteger k) {
0220: int n = k.bitLength();
0221: int s = k.getLowestSetBit();
0222:
0223: BigInteger Uh = ECConstants.ONE;
0224: BigInteger Vl = ECConstants.TWO;
0225: BigInteger Vh = P;
0226: BigInteger Ql = ECConstants.ONE;
0227: BigInteger Qh = ECConstants.ONE;
0228:
0229: for (int j = n - 1; j >= s + 1; --j) {
0230: Ql = Ql.multiply(Qh).mod(p);
0231:
0232: if (k.testBit(j)) {
0233: Qh = Ql.multiply(Q).mod(p);
0234: Uh = Uh.multiply(Vh).mod(p);
0235: Vl = Vh.multiply(Vl).subtract(P.multiply(Ql))
0236: .mod(p);
0237: Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(
0238: p);
0239: } else {
0240: Qh = Ql;
0241: Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
0242: Vh = Vh.multiply(Vl).subtract(P.multiply(Ql))
0243: .mod(p);
0244: Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(
0245: p);
0246: }
0247: }
0248:
0249: Ql = Ql.multiply(Qh).mod(p);
0250: Qh = Ql.multiply(Q).mod(p);
0251: Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
0252: Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
0253: Ql = Ql.multiply(Qh).mod(p);
0254:
0255: for (int j = 1; j <= s; ++j) {
0256: Uh = Uh.multiply(Vl).mod(p);
0257: Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
0258: Ql = Ql.multiply(Ql).mod(p);
0259: }
0260:
0261: return new BigInteger[] { Uh, Vl };
0262: }
0263:
0264: public boolean equals(Object other) {
0265: if (other == this ) {
0266: return true;
0267: }
0268:
0269: if (!(other instanceof ECFieldElement.Fp)) {
0270: return false;
0271: }
0272:
0273: ECFieldElement.Fp o = (ECFieldElement.Fp) other;
0274: return q.equals(o.q) && x.equals(o.x);
0275: }
0276:
0277: public int hashCode() {
0278: return q.hashCode() ^ x.hashCode();
0279: }
0280: }
0281:
0282: // /**
0283: // * Class representing the Elements of the finite field
0284: // * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
0285: // * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
0286: // * basis representations are supported. Gaussian normal basis (GNB)
0287: // * representation is not supported.
0288: // */
0289: // public static class F2m extends ECFieldElement
0290: // {
0291: // BigInteger x;
0292: //
0293: // /**
0294: // * Indicates gaussian normal basis representation (GNB). Number chosen
0295: // * according to X9.62. GNB is not implemented at present.
0296: // */
0297: // public static final int GNB = 1;
0298: //
0299: // /**
0300: // * Indicates trinomial basis representation (TPB). Number chosen
0301: // * according to X9.62.
0302: // */
0303: // public static final int TPB = 2;
0304: //
0305: // /**
0306: // * Indicates pentanomial basis representation (PPB). Number chosen
0307: // * according to X9.62.
0308: // */
0309: // public static final int PPB = 3;
0310: //
0311: // /**
0312: // * TPB or PPB.
0313: // */
0314: // private int representation;
0315: //
0316: // /**
0317: // * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
0318: // */
0319: // private int m;
0320: //
0321: // /**
0322: // * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
0323: // * x<sup>k</sup> + 1</code> represents the reduction polynomial
0324: // * <code>f(z)</code>.<br>
0325: // * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
0326: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0327: // * represents the reduction polynomial <code>f(z)</code>.<br>
0328: // */
0329: // private int k1;
0330: //
0331: // /**
0332: // * TPB: Always set to <code>0</code><br>
0333: // * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
0334: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0335: // * represents the reduction polynomial <code>f(z)</code>.<br>
0336: // */
0337: // private int k2;
0338: //
0339: // /**
0340: // * TPB: Always set to <code>0</code><br>
0341: // * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
0342: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0343: // * represents the reduction polynomial <code>f(z)</code>.<br>
0344: // */
0345: // private int k3;
0346: //
0347: // /**
0348: // * Constructor for PPB.
0349: // * @param m The exponent <code>m</code> of
0350: // * <code>F<sub>2<sup>m</sup></sub></code>.
0351: // * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
0352: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0353: // * represents the reduction polynomial <code>f(z)</code>.
0354: // * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
0355: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0356: // * represents the reduction polynomial <code>f(z)</code>.
0357: // * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
0358: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0359: // * represents the reduction polynomial <code>f(z)</code>.
0360: // * @param x The BigInteger representing the value of the field element.
0361: // */
0362: // public F2m(
0363: // int m,
0364: // int k1,
0365: // int k2,
0366: // int k3,
0367: // BigInteger x)
0368: // {
0369: //// super(x);
0370: // this.x = x;
0371: //
0372: // if ((k2 == 0) && (k3 == 0))
0373: // {
0374: // this.representation = TPB;
0375: // }
0376: // else
0377: // {
0378: // if (k2 >= k3)
0379: // {
0380: // throw new IllegalArgumentException(
0381: // "k2 must be smaller than k3");
0382: // }
0383: // if (k2 <= 0)
0384: // {
0385: // throw new IllegalArgumentException(
0386: // "k2 must be larger than 0");
0387: // }
0388: // this.representation = PPB;
0389: // }
0390: //
0391: // if (x.signum() < 0)
0392: // {
0393: // throw new IllegalArgumentException("x value cannot be negative");
0394: // }
0395: //
0396: // this.m = m;
0397: // this.k1 = k1;
0398: // this.k2 = k2;
0399: // this.k3 = k3;
0400: // }
0401: //
0402: // /**
0403: // * Constructor for TPB.
0404: // * @param m The exponent <code>m</code> of
0405: // * <code>F<sub>2<sup>m</sup></sub></code>.
0406: // * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
0407: // * x<sup>k</sup> + 1</code> represents the reduction
0408: // * polynomial <code>f(z)</code>.
0409: // * @param x The BigInteger representing the value of the field element.
0410: // */
0411: // public F2m(int m, int k, BigInteger x)
0412: // {
0413: // // Set k1 to k, and set k2 and k3 to 0
0414: // this(m, k, 0, 0, x);
0415: // }
0416: //
0417: // public BigInteger toBigInteger()
0418: // {
0419: // return x;
0420: // }
0421: //
0422: // public String getFieldName()
0423: // {
0424: // return "F2m";
0425: // }
0426: //
0427: // public int getFieldSize()
0428: // {
0429: // return m;
0430: // }
0431: //
0432: // /**
0433: // * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
0434: // * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
0435: // * (having the same representation).
0436: // * @param a field element.
0437: // * @param b field element to be compared.
0438: // * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
0439: // * are not elements of the same field
0440: // * <code>F<sub>2<sup>m</sup></sub></code> (having the same
0441: // * representation).
0442: // */
0443: // public static void checkFieldElements(
0444: // ECFieldElement a,
0445: // ECFieldElement b)
0446: // {
0447: // if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
0448: // {
0449: // throw new IllegalArgumentException("Field elements are not "
0450: // + "both instances of ECFieldElement.F2m");
0451: // }
0452: //
0453: // if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0))
0454: // {
0455: // throw new IllegalArgumentException(
0456: // "x value may not be negative");
0457: // }
0458: //
0459: // ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
0460: // ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
0461: //
0462: // if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
0463: // || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
0464: // {
0465: // throw new IllegalArgumentException("Field elements are not "
0466: // + "elements of the same field F2m");
0467: // }
0468: //
0469: // if (aF2m.representation != bF2m.representation)
0470: // {
0471: // // Should never occur
0472: // throw new IllegalArgumentException(
0473: // "One of the field "
0474: // + "elements are not elements has incorrect representation");
0475: // }
0476: // }
0477: //
0478: // /**
0479: // * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is
0480: // * the reduction polynomial of <code>this</code>.
0481: // * @param a The polynomial <code>a(z)</code> to be multiplied by
0482: // * <code>z mod f(z)</code>.
0483: // * @return <code>z * a(z) mod f(z)</code>
0484: // */
0485: // private BigInteger multZModF(final BigInteger a)
0486: // {
0487: // // Left-shift of a(z)
0488: // BigInteger az = a.shiftLeft(1);
0489: // if (az.testBit(this.m))
0490: // {
0491: // // If the coefficient of z^m in a(z) equals 1, reduction
0492: // // modulo f(z) is performed: Add f(z) to to a(z):
0493: // // Step 1: Unset mth coeffient of a(z)
0494: // az = az.clearBit(this.m);
0495: //
0496: // // Step 2: Add r(z) to a(z), where r(z) is defined as
0497: // // f(z) = z^m + r(z), and k1, k2, k3 are the positions of
0498: // // the non-zero coefficients in r(z)
0499: // az = az.flipBit(0);
0500: // az = az.flipBit(this.k1);
0501: // if (this.representation == PPB)
0502: // {
0503: // az = az.flipBit(this.k2);
0504: // az = az.flipBit(this.k3);
0505: // }
0506: // }
0507: // return az;
0508: // }
0509: //
0510: // public ECFieldElement add(final ECFieldElement b)
0511: // {
0512: // // No check performed here for performance reasons. Instead the
0513: // // elements involved are checked in ECPoint.F2m
0514: // // checkFieldElements(this, b);
0515: // if (b.toBigInteger().signum() == 0)
0516: // {
0517: // return this;
0518: // }
0519: //
0520: // return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger()));
0521: // }
0522: //
0523: // public ECFieldElement subtract(final ECFieldElement b)
0524: // {
0525: // // Addition and subtraction are the same in F2m
0526: // return add(b);
0527: // }
0528: //
0529: //
0530: // public ECFieldElement multiply(final ECFieldElement b)
0531: // {
0532: // // Left-to-right shift-and-add field multiplication in F2m
0533: // // Input: Binary polynomials a(z) and b(z) of degree at most m-1
0534: // // Output: c(z) = a(z) * b(z) mod f(z)
0535: //
0536: // // No check performed here for performance reasons. Instead the
0537: // // elements involved are checked in ECPoint.F2m
0538: // // checkFieldElements(this, b);
0539: // final BigInteger az = this.x;
0540: // BigInteger bz = b.toBigInteger();
0541: // BigInteger cz;
0542: //
0543: // // Compute c(z) = a(z) * b(z) mod f(z)
0544: // if (az.testBit(0))
0545: // {
0546: // cz = bz;
0547: // }
0548: // else
0549: // {
0550: // cz = ECConstants.ZERO;
0551: // }
0552: //
0553: // for (int i = 1; i < this.m; i++)
0554: // {
0555: // // b(z) := z * b(z) mod f(z)
0556: // bz = multZModF(bz);
0557: //
0558: // if (az.testBit(i))
0559: // {
0560: // // If the coefficient of x^i in a(z) equals 1, b(z) is added
0561: // // to c(z)
0562: // cz = cz.xor(bz);
0563: // }
0564: // }
0565: // return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz);
0566: // }
0567: //
0568: //
0569: // public ECFieldElement divide(final ECFieldElement b)
0570: // {
0571: // // There may be more efficient implementations
0572: // ECFieldElement bInv = b.invert();
0573: // return multiply(bInv);
0574: // }
0575: //
0576: // public ECFieldElement negate()
0577: // {
0578: // // -x == x holds for all x in F2m
0579: // return this;
0580: // }
0581: //
0582: // public ECFieldElement square()
0583: // {
0584: // // Naive implementation, can probably be speeded up using modular
0585: // // reduction
0586: // return multiply(this);
0587: // }
0588: //
0589: // public ECFieldElement invert()
0590: // {
0591: // // Inversion in F2m using the extended Euclidean algorithm
0592: // // Input: A nonzero polynomial a(z) of degree at most m-1
0593: // // Output: a(z)^(-1) mod f(z)
0594: //
0595: // // u(z) := a(z)
0596: // BigInteger uz = this.x;
0597: // if (uz.signum() <= 0)
0598: // {
0599: // throw new ArithmeticException("x is zero or negative, " +
0600: // "inversion is impossible");
0601: // }
0602: //
0603: // // v(z) := f(z)
0604: // BigInteger vz = ECConstants.ZERO.setBit(m);
0605: // vz = vz.setBit(0);
0606: // vz = vz.setBit(this.k1);
0607: // if (this.representation == PPB)
0608: // {
0609: // vz = vz.setBit(this.k2);
0610: // vz = vz.setBit(this.k3);
0611: // }
0612: //
0613: // // g1(z) := 1, g2(z) := 0
0614: // BigInteger g1z = ECConstants.ONE;
0615: // BigInteger g2z = ECConstants.ZERO;
0616: //
0617: // // while u != 1
0618: // while (!(uz.equals(ECConstants.ZERO)))
0619: // {
0620: // // j := deg(u(z)) - deg(v(z))
0621: // int j = uz.bitLength() - vz.bitLength();
0622: //
0623: // // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
0624: // if (j < 0)
0625: // {
0626: // final BigInteger uzCopy = uz;
0627: // uz = vz;
0628: // vz = uzCopy;
0629: //
0630: // final BigInteger g1zCopy = g1z;
0631: // g1z = g2z;
0632: // g2z = g1zCopy;
0633: //
0634: // j = -j;
0635: // }
0636: //
0637: // // u(z) := u(z) + z^j * v(z)
0638: // // Note, that no reduction modulo f(z) is required, because
0639: // // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
0640: // // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
0641: // // = deg(u(z))
0642: // uz = uz.xor(vz.shiftLeft(j));
0643: //
0644: // // g1(z) := g1(z) + z^j * g2(z)
0645: // g1z = g1z.xor(g2z.shiftLeft(j));
0646: //// if (g1z.bitLength() > this.m) {
0647: //// throw new ArithmeticException(
0648: //// "deg(g1z) >= m, g1z = " + g1z.toString(2));
0649: //// }
0650: // }
0651: // return new ECFieldElement.F2m(
0652: // this.m, this.k1, this.k2, this.k3, g2z);
0653: // }
0654: //
0655: // public ECFieldElement sqrt()
0656: // {
0657: // throw new RuntimeException("Not implemented");
0658: // }
0659: //
0660: // /**
0661: // * @return the representation of the field
0662: // * <code>F<sub>2<sup>m</sup></sub></code>, either of
0663: // * TPB (trinomial
0664: // * basis representation) or
0665: // * PPB (pentanomial
0666: // * basis representation).
0667: // */
0668: // public int getRepresentation()
0669: // {
0670: // return this.representation;
0671: // }
0672: //
0673: // /**
0674: // * @return the degree <code>m</code> of the reduction polynomial
0675: // * <code>f(z)</code>.
0676: // */
0677: // public int getM()
0678: // {
0679: // return this.m;
0680: // }
0681: //
0682: // /**
0683: // * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
0684: // * x<sup>k</sup> + 1</code> represents the reduction polynomial
0685: // * <code>f(z)</code>.<br>
0686: // * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
0687: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0688: // * represents the reduction polynomial <code>f(z)</code>.<br>
0689: // */
0690: // public int getK1()
0691: // {
0692: // return this.k1;
0693: // }
0694: //
0695: // /**
0696: // * @return TPB: Always returns <code>0</code><br>
0697: // * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
0698: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0699: // * represents the reduction polynomial <code>f(z)</code>.<br>
0700: // */
0701: // public int getK2()
0702: // {
0703: // return this.k2;
0704: // }
0705: //
0706: // /**
0707: // * @return TPB: Always set to <code>0</code><br>
0708: // * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
0709: // * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0710: // * represents the reduction polynomial <code>f(z)</code>.<br>
0711: // */
0712: // public int getK3()
0713: // {
0714: // return this.k3;
0715: // }
0716: //
0717: // public boolean equals(Object anObject)
0718: // {
0719: // if (anObject == this)
0720: // {
0721: // return true;
0722: // }
0723: //
0724: // if (!(anObject instanceof ECFieldElement.F2m))
0725: // {
0726: // return false;
0727: // }
0728: //
0729: // ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
0730: //
0731: // return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
0732: // && (this.k3 == b.k3)
0733: // && (this.representation == b.representation)
0734: // && (this.x.equals(b.x)));
0735: // }
0736: //
0737: // public int hashCode()
0738: // {
0739: // return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
0740: // }
0741: // }
0742:
0743: /**
0744: * Class representing the Elements of the finite field
0745: * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
0746: * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
0747: * basis representations are supported. Gaussian normal basis (GNB)
0748: * representation is not supported.
0749: */
0750: public static class F2m extends ECFieldElement {
0751: /**
0752: * Indicates gaussian normal basis representation (GNB). Number chosen
0753: * according to X9.62. GNB is not implemented at present.
0754: */
0755: public static final int GNB = 1;
0756:
0757: /**
0758: * Indicates trinomial basis representation (TPB). Number chosen
0759: * according to X9.62.
0760: */
0761: public static final int TPB = 2;
0762:
0763: /**
0764: * Indicates pentanomial basis representation (PPB). Number chosen
0765: * according to X9.62.
0766: */
0767: public static final int PPB = 3;
0768:
0769: /**
0770: * TPB or PPB.
0771: */
0772: private int representation;
0773:
0774: /**
0775: * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
0776: */
0777: private int m;
0778:
0779: /**
0780: * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
0781: * x<sup>k</sup> + 1</code> represents the reduction polynomial
0782: * <code>f(z)</code>.<br>
0783: * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
0784: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0785: * represents the reduction polynomial <code>f(z)</code>.<br>
0786: */
0787: private int k1;
0788:
0789: /**
0790: * TPB: Always set to <code>0</code><br>
0791: * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
0792: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0793: * represents the reduction polynomial <code>f(z)</code>.<br>
0794: */
0795: private int k2;
0796:
0797: /**
0798: * TPB: Always set to <code>0</code><br>
0799: * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
0800: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0801: * represents the reduction polynomial <code>f(z)</code>.<br>
0802: */
0803: private int k3;
0804:
0805: /**
0806: * The <code>IntArray</code> holding the bits.
0807: */
0808: private IntArray x;
0809:
0810: /**
0811: * The number of <code>int</code>s required to hold <code>m</code> bits.
0812: */
0813: private int t;
0814:
0815: /**
0816: * Constructor for PPB.
0817: * @param m The exponent <code>m</code> of
0818: * <code>F<sub>2<sup>m</sup></sub></code>.
0819: * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
0820: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0821: * represents the reduction polynomial <code>f(z)</code>.
0822: * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
0823: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0824: * represents the reduction polynomial <code>f(z)</code>.
0825: * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
0826: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
0827: * represents the reduction polynomial <code>f(z)</code>.
0828: * @param x The BigInteger representing the value of the field element.
0829: */
0830: public F2m(int m, int k1, int k2, int k3, BigInteger x) {
0831: // t = m / 32 rounded up to the next integer
0832: t = (m + 31) >> 5;
0833: this .x = new IntArray(x, t);
0834:
0835: if ((k2 == 0) && (k3 == 0)) {
0836: this .representation = TPB;
0837: } else {
0838: if (k2 >= k3) {
0839: throw new IllegalArgumentException(
0840: "k2 must be smaller than k3");
0841: }
0842: if (k2 <= 0) {
0843: throw new IllegalArgumentException(
0844: "k2 must be larger than 0");
0845: }
0846: this .representation = PPB;
0847: }
0848:
0849: if (x.signum() < 0) {
0850: throw new IllegalArgumentException(
0851: "x value cannot be negative");
0852: }
0853:
0854: this .m = m;
0855: this .k1 = k1;
0856: this .k2 = k2;
0857: this .k3 = k3;
0858: }
0859:
0860: /**
0861: * Constructor for TPB.
0862: * @param m The exponent <code>m</code> of
0863: * <code>F<sub>2<sup>m</sup></sub></code>.
0864: * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
0865: * x<sup>k</sup> + 1</code> represents the reduction
0866: * polynomial <code>f(z)</code>.
0867: * @param x The BigInteger representing the value of the field element.
0868: */
0869: public F2m(int m, int k, BigInteger x) {
0870: // Set k1 to k, and set k2 and k3 to 0
0871: this (m, k, 0, 0, x);
0872: }
0873:
0874: private F2m(int m, int k1, int k2, int k3, IntArray x) {
0875: t = (m + 31) >> 5;
0876: this .x = x;
0877: this .m = m;
0878: this .k1 = k1;
0879: this .k2 = k2;
0880: this .k3 = k3;
0881:
0882: if ((k2 == 0) && (k3 == 0)) {
0883: this .representation = TPB;
0884: } else {
0885: this .representation = PPB;
0886: }
0887:
0888: }
0889:
0890: public BigInteger toBigInteger() {
0891: return x.toBigInteger();
0892: }
0893:
0894: public String getFieldName() {
0895: return "F2m";
0896: }
0897:
0898: public int getFieldSize() {
0899: return m;
0900: }
0901:
0902: /**
0903: * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
0904: * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
0905: * (having the same representation).
0906: * @param a field element.
0907: * @param b field element to be compared.
0908: * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
0909: * are not elements of the same field
0910: * <code>F<sub>2<sup>m</sup></sub></code> (having the same
0911: * representation).
0912: */
0913: public static void checkFieldElements(ECFieldElement a,
0914: ECFieldElement b) {
0915: if ((!(a instanceof F2m)) || (!(b instanceof F2m))) {
0916: throw new IllegalArgumentException(
0917: "Field elements are not "
0918: + "both instances of ECFieldElement.F2m");
0919: }
0920:
0921: ECFieldElement.F2m aF2m = (ECFieldElement.F2m) a;
0922: ECFieldElement.F2m bF2m = (ECFieldElement.F2m) b;
0923:
0924: if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
0925: || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) {
0926: throw new IllegalArgumentException(
0927: "Field elements are not "
0928: + "elements of the same field F2m");
0929: }
0930:
0931: if (aF2m.representation != bF2m.representation) {
0932: // Should never occur
0933: throw new IllegalArgumentException(
0934: "One of the field "
0935: + "elements are not elements has incorrect representation");
0936: }
0937: }
0938:
0939: public ECFieldElement add(final ECFieldElement b) {
0940: // No check performed here for performance reasons. Instead the
0941: // elements involved are checked in ECPoint.F2m
0942: // checkFieldElements(this, b);
0943: IntArray iarrClone = (IntArray) this .x.clone();
0944: F2m bF2m = (F2m) b;
0945: iarrClone.addShifted(bF2m.x, 0);
0946: return new F2m(m, k1, k2, k3, iarrClone);
0947: }
0948:
0949: public ECFieldElement subtract(final ECFieldElement b) {
0950: // Addition and subtraction are the same in F2m
0951: return add(b);
0952: }
0953:
0954: public ECFieldElement multiply(final ECFieldElement b) {
0955: // Right-to-left comb multiplication in the IntArray
0956: // Input: Binary polynomials a(z) and b(z) of degree at most m-1
0957: // Output: c(z) = a(z) * b(z) mod f(z)
0958:
0959: // No check performed here for performance reasons. Instead the
0960: // elements involved are checked in ECPoint.F2m
0961: // checkFieldElements(this, b);
0962: F2m bF2m = (F2m) b;
0963: IntArray mult = x.multiply(bF2m.x, m);
0964: mult.reduce(m, new int[] { k1, k2, k3 });
0965: return new F2m(m, k1, k2, k3, mult);
0966: }
0967:
0968: public ECFieldElement divide(final ECFieldElement b) {
0969: // There may be more efficient implementations
0970: ECFieldElement bInv = b.invert();
0971: return multiply(bInv);
0972: }
0973:
0974: public ECFieldElement negate() {
0975: // -x == x holds for all x in F2m
0976: return this ;
0977: }
0978:
0979: public ECFieldElement square() {
0980: IntArray squared = x.square(m);
0981: squared.reduce(m, new int[] { k1, k2, k3 });
0982: return new F2m(m, k1, k2, k3, squared);
0983: }
0984:
0985: public ECFieldElement invert() {
0986: // Inversion in F2m using the extended Euclidean algorithm
0987: // Input: A nonzero polynomial a(z) of degree at most m-1
0988: // Output: a(z)^(-1) mod f(z)
0989:
0990: // u(z) := a(z)
0991: IntArray uz = (IntArray) this .x.clone();
0992:
0993: // v(z) := f(z)
0994: IntArray vz = new IntArray(t);
0995: vz.setBit(m);
0996: vz.setBit(0);
0997: vz.setBit(this .k1);
0998: if (this .representation == PPB) {
0999: vz.setBit(this .k2);
1000: vz.setBit(this .k3);
1001: }
1002:
1003: // g1(z) := 1, g2(z) := 0
1004: IntArray g1z = new IntArray(t);
1005: g1z.setBit(0);
1006: IntArray g2z = new IntArray(t);
1007:
1008: // while u != 0
1009: while (!uz.isZero())
1010: // while (uz.getUsedLength() > 0)
1011: // while (uz.bitLength() > 1)
1012: {
1013: // j := deg(u(z)) - deg(v(z))
1014: int j = uz.bitLength() - vz.bitLength();
1015:
1016: // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
1017: if (j < 0) {
1018: final IntArray uzCopy = uz;
1019: uz = vz;
1020: vz = uzCopy;
1021:
1022: final IntArray g1zCopy = g1z;
1023: g1z = g2z;
1024: g2z = g1zCopy;
1025:
1026: j = -j;
1027: }
1028:
1029: // u(z) := u(z) + z^j * v(z)
1030: // Note, that no reduction modulo f(z) is required, because
1031: // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
1032: // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
1033: // = deg(u(z))
1034: // uz = uz.xor(vz.shiftLeft(j));
1035: // jInt = n / 32
1036: int jInt = j >> 5;
1037: // jInt = n % 32
1038: int jBit = j & 0x1F;
1039: IntArray vzShift = vz.shiftLeft(jBit);
1040: uz.addShifted(vzShift, jInt);
1041:
1042: // g1(z) := g1(z) + z^j * g2(z)
1043: // g1z = g1z.xor(g2z.shiftLeft(j));
1044: IntArray g2zShift = g2z.shiftLeft(jBit);
1045: g1z.addShifted(g2zShift, jInt);
1046:
1047: }
1048: return new ECFieldElement.F2m(this .m, this .k1, this .k2,
1049: this .k3, g2z);
1050: }
1051:
1052: public ECFieldElement sqrt() {
1053: throw new RuntimeException("Not implemented");
1054: }
1055:
1056: /**
1057: * @return the representation of the field
1058: * <code>F<sub>2<sup>m</sup></sub></code>, either of
1059: * TPB (trinomial
1060: * basis representation) or
1061: * PPB (pentanomial
1062: * basis representation).
1063: */
1064: public int getRepresentation() {
1065: return this .representation;
1066: }
1067:
1068: /**
1069: * @return the degree <code>m</code> of the reduction polynomial
1070: * <code>f(z)</code>.
1071: */
1072: public int getM() {
1073: return this .m;
1074: }
1075:
1076: /**
1077: * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
1078: * x<sup>k</sup> + 1</code> represents the reduction polynomial
1079: * <code>f(z)</code>.<br>
1080: * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
1081: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
1082: * represents the reduction polynomial <code>f(z)</code>.<br>
1083: */
1084: public int getK1() {
1085: return this .k1;
1086: }
1087:
1088: /**
1089: * @return TPB: Always returns <code>0</code><br>
1090: * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
1091: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
1092: * represents the reduction polynomial <code>f(z)</code>.<br>
1093: */
1094: public int getK2() {
1095: return this .k2;
1096: }
1097:
1098: /**
1099: * @return TPB: Always set to <code>0</code><br>
1100: * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
1101: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
1102: * represents the reduction polynomial <code>f(z)</code>.<br>
1103: */
1104: public int getK3() {
1105: return this .k3;
1106: }
1107:
1108: public boolean equals(Object anObject) {
1109: if (anObject == this ) {
1110: return true;
1111: }
1112:
1113: if (!(anObject instanceof ECFieldElement.F2m)) {
1114: return false;
1115: }
1116:
1117: ECFieldElement.F2m b = (ECFieldElement.F2m) anObject;
1118:
1119: return ((this .m == b.m) && (this .k1 == b.k1)
1120: && (this .k2 == b.k2) && (this .k3 == b.k3)
1121: && (this .representation == b.representation) && (this .x
1122: .equals(b.x)));
1123: }
1124:
1125: public int hashCode() {
1126: return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
1127: }
1128: }
1129: }
|