ECFieldElement.java revision e6bf3e8dfa2804891a82075cb469b736321b4827
1package org.bouncycastle.math.ec; 2 3import java.math.BigInteger; 4import java.util.Random; 5 6public abstract class ECFieldElement 7 implements ECConstants 8{ 9 10 public abstract BigInteger toBigInteger(); 11 public abstract String getFieldName(); 12 public abstract int getFieldSize(); 13 public abstract ECFieldElement add(ECFieldElement b); 14 public abstract ECFieldElement subtract(ECFieldElement b); 15 public abstract ECFieldElement multiply(ECFieldElement b); 16 public abstract ECFieldElement divide(ECFieldElement b); 17 public abstract ECFieldElement negate(); 18 public abstract ECFieldElement square(); 19 public abstract ECFieldElement invert(); 20 public abstract ECFieldElement sqrt(); 21 22 public String toString() 23 { 24 return this.toBigInteger().toString(2); 25 } 26 27 public static class Fp extends ECFieldElement 28 { 29 BigInteger x; 30 31 BigInteger q; 32 33 public Fp(BigInteger q, BigInteger x) 34 { 35 this.x = x; 36 37 if (x.compareTo(q) >= 0) 38 { 39 throw new IllegalArgumentException("x value too large in field element"); 40 } 41 42 this.q = q; 43 } 44 45 public BigInteger toBigInteger() 46 { 47 return x; 48 } 49 50 /** 51 * return the field name for this field. 52 * 53 * @return the string "Fp". 54 */ 55 public String getFieldName() 56 { 57 return "Fp"; 58 } 59 60 public int getFieldSize() 61 { 62 return q.bitLength(); 63 } 64 65 public BigInteger getQ() 66 { 67 return q; 68 } 69 70 public ECFieldElement add(ECFieldElement b) 71 { 72 return new Fp(q, x.add(b.toBigInteger()).mod(q)); 73 } 74 75 public ECFieldElement subtract(ECFieldElement b) 76 { 77 return new Fp(q, x.subtract(b.toBigInteger()).mod(q)); 78 } 79 80 public ECFieldElement multiply(ECFieldElement b) 81 { 82 return new Fp(q, x.multiply(b.toBigInteger()).mod(q)); 83 } 84 85 public ECFieldElement divide(ECFieldElement b) 86 { 87 return new Fp(q, x.multiply(b.toBigInteger().modInverse(q)).mod(q)); 88 } 89 90 public ECFieldElement negate() 91 { 92 return new Fp(q, x.negate().mod(q)); 93 } 94 95 public ECFieldElement square() 96 { 97 return new Fp(q, x.multiply(x).mod(q)); 98 } 99 100 public ECFieldElement invert() 101 { 102 return new Fp(q, x.modInverse(q)); 103 } 104 105 // D.1.4 91 106 /** 107 * return a sqrt root - the routine verifies that the calculation 108 * returns the right value - if none exists it returns null. 109 */ 110 public ECFieldElement sqrt() 111 { 112 if (!q.testBit(0)) 113 { 114 throw new RuntimeException("not done yet"); 115 } 116 117 // note: even though this class implements ECConstants don't be tempted to 118 // remove the explicit declaration, some J2ME environments don't cope. 119 // p mod 4 == 3 120 if (q.testBit(1)) 121 { 122 // z = g^(u+1) + p, p = 4u + 3 123 ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q)); 124 125 return z.square().equals(this) ? z : null; 126 } 127 128 // p mod 4 == 1 129 BigInteger qMinusOne = q.subtract(ECConstants.ONE); 130 131 BigInteger legendreExponent = qMinusOne.shiftRight(1); 132 if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 133 { 134 return null; 135 } 136 137 BigInteger u = qMinusOne.shiftRight(2); 138 BigInteger k = u.shiftLeft(1).add(ECConstants.ONE); 139 140 BigInteger Q = this.x; 141 BigInteger fourQ = Q.shiftLeft(2).mod(q); 142 143 BigInteger U, V; 144 Random rand = new Random(); 145 do 146 { 147 BigInteger P; 148 do 149 { 150 P = new BigInteger(q.bitLength(), rand); 151 } 152 while (P.compareTo(q) >= 0 153 || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne))); 154 155 BigInteger[] result = lucasSequence(q, P, Q, k); 156 U = result[0]; 157 V = result[1]; 158 159 if (V.multiply(V).mod(q).equals(fourQ)) 160 { 161 // Integer division by 2, mod q 162 if (V.testBit(0)) 163 { 164 V = V.add(q); 165 } 166 167 V = V.shiftRight(1); 168 169 //assert V.multiply(V).mod(q).equals(x); 170 171 return new ECFieldElement.Fp(q, V); 172 } 173 } 174 while (U.equals(ECConstants.ONE) || U.equals(qMinusOne)); 175 176 return null; 177 178// BigInteger qMinusOne = q.subtract(ECConstants.ONE); 179// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO); 180// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 181// { 182// return null; 183// } 184// 185// Random rand = new Random(); 186// BigInteger fourX = x.shiftLeft(2); 187// 188// BigInteger r; 189// do 190// { 191// r = new BigInteger(q.bitLength(), rand); 192// } 193// while (r.compareTo(q) >= 0 194// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne))); 195// 196// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR); 197// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR); 198// 199// BigInteger wOne = WOne(r, x, q); 200// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q); 201// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r); 202// 203// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q) 204// .multiply(x).mod(q) 205// .multiply(wSum).mod(q); 206// 207// return new Fp(q, root); 208 } 209 210// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p) 211// { 212// if (n.equals(ECConstants.ONE)) 213// { 214// return wOne; 215// } 216// boolean isEven = !n.testBit(0); 217// n = n.shiftRight(1);//divide(ECConstants.TWO); 218// if (isEven) 219// { 220// BigInteger w = W(n, wOne, p); 221// return w.multiply(w).subtract(ECConstants.TWO).mod(p); 222// } 223// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p); 224// BigInteger w2 = W(n, wOne, p); 225// return w1.multiply(w2).subtract(wOne).mod(p); 226// } 227// 228// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p) 229// { 230// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p); 231// } 232 233 private static BigInteger[] lucasSequence( 234 BigInteger p, 235 BigInteger P, 236 BigInteger Q, 237 BigInteger k) 238 { 239 int n = k.bitLength(); 240 int s = k.getLowestSetBit(); 241 242 BigInteger Uh = ECConstants.ONE; 243 BigInteger Vl = ECConstants.TWO; 244 BigInteger Vh = P; 245 BigInteger Ql = ECConstants.ONE; 246 BigInteger Qh = ECConstants.ONE; 247 248 for (int j = n - 1; j >= s + 1; --j) 249 { 250 Ql = Ql.multiply(Qh).mod(p); 251 252 if (k.testBit(j)) 253 { 254 Qh = Ql.multiply(Q).mod(p); 255 Uh = Uh.multiply(Vh).mod(p); 256 Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 257 Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p); 258 } 259 else 260 { 261 Qh = Ql; 262 Uh = Uh.multiply(Vl).subtract(Ql).mod(p); 263 Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 264 Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); 265 } 266 } 267 268 Ql = Ql.multiply(Qh).mod(p); 269 Qh = Ql.multiply(Q).mod(p); 270 Uh = Uh.multiply(Vl).subtract(Ql).mod(p); 271 Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 272 Ql = Ql.multiply(Qh).mod(p); 273 274 for (int j = 1; j <= s; ++j) 275 { 276 Uh = Uh.multiply(Vl).mod(p); 277 Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); 278 Ql = Ql.multiply(Ql).mod(p); 279 } 280 281 return new BigInteger[]{ Uh, Vl }; 282 } 283 284 public boolean equals(Object other) 285 { 286 if (other == this) 287 { 288 return true; 289 } 290 291 if (!(other instanceof ECFieldElement.Fp)) 292 { 293 return false; 294 } 295 296 ECFieldElement.Fp o = (ECFieldElement.Fp)other; 297 return q.equals(o.q) && x.equals(o.x); 298 } 299 300 public int hashCode() 301 { 302 return q.hashCode() ^ x.hashCode(); 303 } 304 } 305 306// /** 307// * Class representing the Elements of the finite field 308// * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 309// * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 310// * basis representations are supported. Gaussian normal basis (GNB) 311// * representation is not supported. 312// */ 313// public static class F2m extends ECFieldElement 314// { 315// BigInteger x; 316// 317// /** 318// * Indicates gaussian normal basis representation (GNB). Number chosen 319// * according to X9.62. GNB is not implemented at present. 320// */ 321// public static final int GNB = 1; 322// 323// /** 324// * Indicates trinomial basis representation (TPB). Number chosen 325// * according to X9.62. 326// */ 327// public static final int TPB = 2; 328// 329// /** 330// * Indicates pentanomial basis representation (PPB). Number chosen 331// * according to X9.62. 332// */ 333// public static final int PPB = 3; 334// 335// /** 336// * TPB or PPB. 337// */ 338// private int representation; 339// 340// /** 341// * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 342// */ 343// private int m; 344// 345// /** 346// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 347// * x<sup>k</sup> + 1</code> represents the reduction polynomial 348// * <code>f(z)</code>.<br> 349// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 350// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 351// * represents the reduction polynomial <code>f(z)</code>.<br> 352// */ 353// private int k1; 354// 355// /** 356// * TPB: Always set to <code>0</code><br> 357// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 358// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 359// * represents the reduction polynomial <code>f(z)</code>.<br> 360// */ 361// private int k2; 362// 363// /** 364// * TPB: Always set to <code>0</code><br> 365// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 366// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 367// * represents the reduction polynomial <code>f(z)</code>.<br> 368// */ 369// private int k3; 370// 371// /** 372// * Constructor for PPB. 373// * @param m The exponent <code>m</code> of 374// * <code>F<sub>2<sup>m</sup></sub></code>. 375// * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 376// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 377// * represents the reduction polynomial <code>f(z)</code>. 378// * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 379// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 380// * represents the reduction polynomial <code>f(z)</code>. 381// * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 382// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 383// * represents the reduction polynomial <code>f(z)</code>. 384// * @param x The BigInteger representing the value of the field element. 385// */ 386// public F2m( 387// int m, 388// int k1, 389// int k2, 390// int k3, 391// BigInteger x) 392// { 393//// super(x); 394// this.x = x; 395// 396// if ((k2 == 0) && (k3 == 0)) 397// { 398// this.representation = TPB; 399// } 400// else 401// { 402// if (k2 >= k3) 403// { 404// throw new IllegalArgumentException( 405// "k2 must be smaller than k3"); 406// } 407// if (k2 <= 0) 408// { 409// throw new IllegalArgumentException( 410// "k2 must be larger than 0"); 411// } 412// this.representation = PPB; 413// } 414// 415// if (x.signum() < 0) 416// { 417// throw new IllegalArgumentException("x value cannot be negative"); 418// } 419// 420// this.m = m; 421// this.k1 = k1; 422// this.k2 = k2; 423// this.k3 = k3; 424// } 425// 426// /** 427// * Constructor for TPB. 428// * @param m The exponent <code>m</code> of 429// * <code>F<sub>2<sup>m</sup></sub></code>. 430// * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 431// * x<sup>k</sup> + 1</code> represents the reduction 432// * polynomial <code>f(z)</code>. 433// * @param x The BigInteger representing the value of the field element. 434// */ 435// public F2m(int m, int k, BigInteger x) 436// { 437// // Set k1 to k, and set k2 and k3 to 0 438// this(m, k, 0, 0, x); 439// } 440// 441// public BigInteger toBigInteger() 442// { 443// return x; 444// } 445// 446// public String getFieldName() 447// { 448// return "F2m"; 449// } 450// 451// public int getFieldSize() 452// { 453// return m; 454// } 455// 456// /** 457// * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 458// * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 459// * (having the same representation). 460// * @param a field element. 461// * @param b field element to be compared. 462// * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 463// * are not elements of the same field 464// * <code>F<sub>2<sup>m</sup></sub></code> (having the same 465// * representation). 466// */ 467// public static void checkFieldElements( 468// ECFieldElement a, 469// ECFieldElement b) 470// { 471// if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 472// { 473// throw new IllegalArgumentException("Field elements are not " 474// + "both instances of ECFieldElement.F2m"); 475// } 476// 477// if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0)) 478// { 479// throw new IllegalArgumentException( 480// "x value may not be negative"); 481// } 482// 483// ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 484// ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 485// 486// if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) 487// || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) 488// { 489// throw new IllegalArgumentException("Field elements are not " 490// + "elements of the same field F2m"); 491// } 492// 493// if (aF2m.representation != bF2m.representation) 494// { 495// // Should never occur 496// throw new IllegalArgumentException( 497// "One of the field " 498// + "elements are not elements has incorrect representation"); 499// } 500// } 501// 502// /** 503// * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is 504// * the reduction polynomial of <code>this</code>. 505// * @param a The polynomial <code>a(z)</code> to be multiplied by 506// * <code>z mod f(z)</code>. 507// * @return <code>z * a(z) mod f(z)</code> 508// */ 509// private BigInteger multZModF(final BigInteger a) 510// { 511// // Left-shift of a(z) 512// BigInteger az = a.shiftLeft(1); 513// if (az.testBit(this.m)) 514// { 515// // If the coefficient of z^m in a(z) equals 1, reduction 516// // modulo f(z) is performed: Add f(z) to to a(z): 517// // Step 1: Unset mth coeffient of a(z) 518// az = az.clearBit(this.m); 519// 520// // Step 2: Add r(z) to a(z), where r(z) is defined as 521// // f(z) = z^m + r(z), and k1, k2, k3 are the positions of 522// // the non-zero coefficients in r(z) 523// az = az.flipBit(0); 524// az = az.flipBit(this.k1); 525// if (this.representation == PPB) 526// { 527// az = az.flipBit(this.k2); 528// az = az.flipBit(this.k3); 529// } 530// } 531// return az; 532// } 533// 534// public ECFieldElement add(final ECFieldElement b) 535// { 536// // No check performed here for performance reasons. Instead the 537// // elements involved are checked in ECPoint.F2m 538// // checkFieldElements(this, b); 539// if (b.toBigInteger().signum() == 0) 540// { 541// return this; 542// } 543// 544// return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger())); 545// } 546// 547// public ECFieldElement subtract(final ECFieldElement b) 548// { 549// // Addition and subtraction are the same in F2m 550// return add(b); 551// } 552// 553// 554// public ECFieldElement multiply(final ECFieldElement b) 555// { 556// // Left-to-right shift-and-add field multiplication in F2m 557// // Input: Binary polynomials a(z) and b(z) of degree at most m-1 558// // Output: c(z) = a(z) * b(z) mod f(z) 559// 560// // No check performed here for performance reasons. Instead the 561// // elements involved are checked in ECPoint.F2m 562// // checkFieldElements(this, b); 563// final BigInteger az = this.x; 564// BigInteger bz = b.toBigInteger(); 565// BigInteger cz; 566// 567// // Compute c(z) = a(z) * b(z) mod f(z) 568// if (az.testBit(0)) 569// { 570// cz = bz; 571// } 572// else 573// { 574// cz = ECConstants.ZERO; 575// } 576// 577// for (int i = 1; i < this.m; i++) 578// { 579// // b(z) := z * b(z) mod f(z) 580// bz = multZModF(bz); 581// 582// if (az.testBit(i)) 583// { 584// // If the coefficient of x^i in a(z) equals 1, b(z) is added 585// // to c(z) 586// cz = cz.xor(bz); 587// } 588// } 589// return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz); 590// } 591// 592// 593// public ECFieldElement divide(final ECFieldElement b) 594// { 595// // There may be more efficient implementations 596// ECFieldElement bInv = b.invert(); 597// return multiply(bInv); 598// } 599// 600// public ECFieldElement negate() 601// { 602// // -x == x holds for all x in F2m 603// return this; 604// } 605// 606// public ECFieldElement square() 607// { 608// // Naive implementation, can probably be speeded up using modular 609// // reduction 610// return multiply(this); 611// } 612// 613// public ECFieldElement invert() 614// { 615// // Inversion in F2m using the extended Euclidean algorithm 616// // Input: A nonzero polynomial a(z) of degree at most m-1 617// // Output: a(z)^(-1) mod f(z) 618// 619// // u(z) := a(z) 620// BigInteger uz = this.x; 621// if (uz.signum() <= 0) 622// { 623// throw new ArithmeticException("x is zero or negative, " + 624// "inversion is impossible"); 625// } 626// 627// // v(z) := f(z) 628// BigInteger vz = ECConstants.ZERO.setBit(m); 629// vz = vz.setBit(0); 630// vz = vz.setBit(this.k1); 631// if (this.representation == PPB) 632// { 633// vz = vz.setBit(this.k2); 634// vz = vz.setBit(this.k3); 635// } 636// 637// // g1(z) := 1, g2(z) := 0 638// BigInteger g1z = ECConstants.ONE; 639// BigInteger g2z = ECConstants.ZERO; 640// 641// // while u != 1 642// while (!(uz.equals(ECConstants.ZERO))) 643// { 644// // j := deg(u(z)) - deg(v(z)) 645// int j = uz.bitLength() - vz.bitLength(); 646// 647// // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 648// if (j < 0) 649// { 650// final BigInteger uzCopy = uz; 651// uz = vz; 652// vz = uzCopy; 653// 654// final BigInteger g1zCopy = g1z; 655// g1z = g2z; 656// g2z = g1zCopy; 657// 658// j = -j; 659// } 660// 661// // u(z) := u(z) + z^j * v(z) 662// // Note, that no reduction modulo f(z) is required, because 663// // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 664// // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 665// // = deg(u(z)) 666// uz = uz.xor(vz.shiftLeft(j)); 667// 668// // g1(z) := g1(z) + z^j * g2(z) 669// g1z = g1z.xor(g2z.shiftLeft(j)); 670//// if (g1z.bitLength() > this.m) { 671//// throw new ArithmeticException( 672//// "deg(g1z) >= m, g1z = " + g1z.toString(2)); 673//// } 674// } 675// return new ECFieldElement.F2m( 676// this.m, this.k1, this.k2, this.k3, g2z); 677// } 678// 679// public ECFieldElement sqrt() 680// { 681// throw new RuntimeException("Not implemented"); 682// } 683// 684// /** 685// * @return the representation of the field 686// * <code>F<sub>2<sup>m</sup></sub></code>, either of 687// * TPB (trinomial 688// * basis representation) or 689// * PPB (pentanomial 690// * basis representation). 691// */ 692// public int getRepresentation() 693// { 694// return this.representation; 695// } 696// 697// /** 698// * @return the degree <code>m</code> of the reduction polynomial 699// * <code>f(z)</code>. 700// */ 701// public int getM() 702// { 703// return this.m; 704// } 705// 706// /** 707// * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 708// * x<sup>k</sup> + 1</code> represents the reduction polynomial 709// * <code>f(z)</code>.<br> 710// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 711// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 712// * represents the reduction polynomial <code>f(z)</code>.<br> 713// */ 714// public int getK1() 715// { 716// return this.k1; 717// } 718// 719// /** 720// * @return TPB: Always returns <code>0</code><br> 721// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 722// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 723// * represents the reduction polynomial <code>f(z)</code>.<br> 724// */ 725// public int getK2() 726// { 727// return this.k2; 728// } 729// 730// /** 731// * @return TPB: Always set to <code>0</code><br> 732// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 733// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 734// * represents the reduction polynomial <code>f(z)</code>.<br> 735// */ 736// public int getK3() 737// { 738// return this.k3; 739// } 740// 741// public boolean equals(Object anObject) 742// { 743// if (anObject == this) 744// { 745// return true; 746// } 747// 748// if (!(anObject instanceof ECFieldElement.F2m)) 749// { 750// return false; 751// } 752// 753// ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 754// 755// return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) 756// && (this.k3 == b.k3) 757// && (this.representation == b.representation) 758// && (this.x.equals(b.x))); 759// } 760// 761// public int hashCode() 762// { 763// return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; 764// } 765// } 766 767 /** 768 * Class representing the Elements of the finite field 769 * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 770 * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 771 * basis representations are supported. Gaussian normal basis (GNB) 772 * representation is not supported. 773 */ 774 public static class F2m extends ECFieldElement 775 { 776 /** 777 * Indicates gaussian normal basis representation (GNB). Number chosen 778 * according to X9.62. GNB is not implemented at present. 779 */ 780 public static final int GNB = 1; 781 782 /** 783 * Indicates trinomial basis representation (TPB). Number chosen 784 * according to X9.62. 785 */ 786 public static final int TPB = 2; 787 788 /** 789 * Indicates pentanomial basis representation (PPB). Number chosen 790 * according to X9.62. 791 */ 792 public static final int PPB = 3; 793 794 /** 795 * TPB or PPB. 796 */ 797 private int representation; 798 799 /** 800 * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 801 */ 802 private int m; 803 804 /** 805 * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 806 * x<sup>k</sup> + 1</code> represents the reduction polynomial 807 * <code>f(z)</code>.<br> 808 * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 809 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 810 * represents the reduction polynomial <code>f(z)</code>.<br> 811 */ 812 private int k1; 813 814 /** 815 * TPB: Always set to <code>0</code><br> 816 * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 817 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 818 * represents the reduction polynomial <code>f(z)</code>.<br> 819 */ 820 private int k2; 821 822 /** 823 * TPB: Always set to <code>0</code><br> 824 * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 825 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 826 * represents the reduction polynomial <code>f(z)</code>.<br> 827 */ 828 private int k3; 829 830 /** 831 * The <code>IntArray</code> holding the bits. 832 */ 833 private IntArray x; 834 835 /** 836 * The number of <code>int</code>s required to hold <code>m</code> bits. 837 */ 838 private int t; 839 840 /** 841 * Constructor for PPB. 842 * @param m The exponent <code>m</code> of 843 * <code>F<sub>2<sup>m</sup></sub></code>. 844 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 845 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 846 * represents the reduction polynomial <code>f(z)</code>. 847 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 848 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 849 * represents the reduction polynomial <code>f(z)</code>. 850 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 851 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 852 * represents the reduction polynomial <code>f(z)</code>. 853 * @param x The BigInteger representing the value of the field element. 854 */ 855 public F2m( 856 int m, 857 int k1, 858 int k2, 859 int k3, 860 BigInteger x) 861 { 862 // t = m / 32 rounded up to the next integer 863 t = (m + 31) >> 5; 864 this.x = new IntArray(x, t); 865 866 if ((k2 == 0) && (k3 == 0)) 867 { 868 this.representation = TPB; 869 } 870 else 871 { 872 if (k2 >= k3) 873 { 874 throw new IllegalArgumentException( 875 "k2 must be smaller than k3"); 876 } 877 if (k2 <= 0) 878 { 879 throw new IllegalArgumentException( 880 "k2 must be larger than 0"); 881 } 882 this.representation = PPB; 883 } 884 885 if (x.signum() < 0) 886 { 887 throw new IllegalArgumentException("x value cannot be negative"); 888 } 889 890 this.m = m; 891 this.k1 = k1; 892 this.k2 = k2; 893 this.k3 = k3; 894 } 895 896 /** 897 * Constructor for TPB. 898 * @param m The exponent <code>m</code> of 899 * <code>F<sub>2<sup>m</sup></sub></code>. 900 * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 901 * x<sup>k</sup> + 1</code> represents the reduction 902 * polynomial <code>f(z)</code>. 903 * @param x The BigInteger representing the value of the field element. 904 */ 905 public F2m(int m, int k, BigInteger x) 906 { 907 // Set k1 to k, and set k2 and k3 to 0 908 this(m, k, 0, 0, x); 909 } 910 911 private F2m(int m, int k1, int k2, int k3, IntArray x) 912 { 913 t = (m + 31) >> 5; 914 this.x = x; 915 this.m = m; 916 this.k1 = k1; 917 this.k2 = k2; 918 this.k3 = k3; 919 920 if ((k2 == 0) && (k3 == 0)) 921 { 922 this.representation = TPB; 923 } 924 else 925 { 926 this.representation = PPB; 927 } 928 929 } 930 931 public BigInteger toBigInteger() 932 { 933 return x.toBigInteger(); 934 } 935 936 public String getFieldName() 937 { 938 return "F2m"; 939 } 940 941 public int getFieldSize() 942 { 943 return m; 944 } 945 946 /** 947 * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 948 * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 949 * (having the same representation). 950 * @param a field element. 951 * @param b field element to be compared. 952 * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 953 * are not elements of the same field 954 * <code>F<sub>2<sup>m</sup></sub></code> (having the same 955 * representation). 956 */ 957 public static void checkFieldElements( 958 ECFieldElement a, 959 ECFieldElement b) 960 { 961 if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 962 { 963 throw new IllegalArgumentException("Field elements are not " 964 + "both instances of ECFieldElement.F2m"); 965 } 966 967 ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 968 ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 969 970 if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) 971 || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) 972 { 973 throw new IllegalArgumentException("Field elements are not " 974 + "elements of the same field F2m"); 975 } 976 977 if (aF2m.representation != bF2m.representation) 978 { 979 // Should never occur 980 throw new IllegalArgumentException( 981 "One of the field " 982 + "elements are not elements has incorrect representation"); 983 } 984 } 985 986 public ECFieldElement add(final ECFieldElement b) 987 { 988 // No check performed here for performance reasons. Instead the 989 // elements involved are checked in ECPoint.F2m 990 // checkFieldElements(this, b); 991 IntArray iarrClone = (IntArray)this.x.clone(); 992 F2m bF2m = (F2m)b; 993 iarrClone.addShifted(bF2m.x, 0); 994 return new F2m(m, k1, k2, k3, iarrClone); 995 } 996 997 public ECFieldElement subtract(final ECFieldElement b) 998 { 999 // Addition and subtraction are the same in F2m 1000 return add(b); 1001 } 1002 1003 public ECFieldElement multiply(final ECFieldElement b) 1004 { 1005 // Right-to-left comb multiplication in the IntArray 1006 // Input: Binary polynomials a(z) and b(z) of degree at most m-1 1007 // Output: c(z) = a(z) * b(z) mod f(z) 1008 1009 // No check performed here for performance reasons. Instead the 1010 // elements involved are checked in ECPoint.F2m 1011 // checkFieldElements(this, b); 1012 F2m bF2m = (F2m)b; 1013 IntArray mult = x.multiply(bF2m.x, m); 1014 mult.reduce(m, new int[]{k1, k2, k3}); 1015 return new F2m(m, k1, k2, k3, mult); 1016 } 1017 1018 public ECFieldElement divide(final ECFieldElement b) 1019 { 1020 // There may be more efficient implementations 1021 ECFieldElement bInv = b.invert(); 1022 return multiply(bInv); 1023 } 1024 1025 public ECFieldElement negate() 1026 { 1027 // -x == x holds for all x in F2m 1028 return this; 1029 } 1030 1031 public ECFieldElement square() 1032 { 1033 IntArray squared = x.square(m); 1034 squared.reduce(m, new int[]{k1, k2, k3}); 1035 return new F2m(m, k1, k2, k3, squared); 1036 } 1037 1038 1039 public ECFieldElement invert() 1040 { 1041 // Inversion in F2m using the extended Euclidean algorithm 1042 // Input: A nonzero polynomial a(z) of degree at most m-1 1043 // Output: a(z)^(-1) mod f(z) 1044 1045 // u(z) := a(z) 1046 IntArray uz = (IntArray)this.x.clone(); 1047 1048 // v(z) := f(z) 1049 IntArray vz = new IntArray(t); 1050 vz.setBit(m); 1051 vz.setBit(0); 1052 vz.setBit(this.k1); 1053 if (this.representation == PPB) 1054 { 1055 vz.setBit(this.k2); 1056 vz.setBit(this.k3); 1057 } 1058 1059 // g1(z) := 1, g2(z) := 0 1060 IntArray g1z = new IntArray(t); 1061 g1z.setBit(0); 1062 IntArray g2z = new IntArray(t); 1063 1064 // while u != 0 1065 while (!uz.isZero()) 1066// while (uz.getUsedLength() > 0) 1067// while (uz.bitLength() > 1) 1068 { 1069 // j := deg(u(z)) - deg(v(z)) 1070 int j = uz.bitLength() - vz.bitLength(); 1071 1072 // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 1073 if (j < 0) 1074 { 1075 final IntArray uzCopy = uz; 1076 uz = vz; 1077 vz = uzCopy; 1078 1079 final IntArray g1zCopy = g1z; 1080 g1z = g2z; 1081 g2z = g1zCopy; 1082 1083 j = -j; 1084 } 1085 1086 // u(z) := u(z) + z^j * v(z) 1087 // Note, that no reduction modulo f(z) is required, because 1088 // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 1089 // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 1090 // = deg(u(z)) 1091 // uz = uz.xor(vz.shiftLeft(j)); 1092 // jInt = n / 32 1093 int jInt = j >> 5; 1094 // jInt = n % 32 1095 int jBit = j & 0x1F; 1096 IntArray vzShift = vz.shiftLeft(jBit); 1097 uz.addShifted(vzShift, jInt); 1098 1099 // g1(z) := g1(z) + z^j * g2(z) 1100// g1z = g1z.xor(g2z.shiftLeft(j)); 1101 IntArray g2zShift = g2z.shiftLeft(jBit); 1102 g1z.addShifted(g2zShift, jInt); 1103 1104 } 1105 return new ECFieldElement.F2m( 1106 this.m, this.k1, this.k2, this.k3, g2z); 1107 } 1108 1109 public ECFieldElement sqrt() 1110 { 1111 throw new RuntimeException("Not implemented"); 1112 } 1113 1114 /** 1115 * @return the representation of the field 1116 * <code>F<sub>2<sup>m</sup></sub></code>, either of 1117 * TPB (trinomial 1118 * basis representation) or 1119 * PPB (pentanomial 1120 * basis representation). 1121 */ 1122 public int getRepresentation() 1123 { 1124 return this.representation; 1125 } 1126 1127 /** 1128 * @return the degree <code>m</code> of the reduction polynomial 1129 * <code>f(z)</code>. 1130 */ 1131 public int getM() 1132 { 1133 return this.m; 1134 } 1135 1136 /** 1137 * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 1138 * x<sup>k</sup> + 1</code> represents the reduction polynomial 1139 * <code>f(z)</code>.<br> 1140 * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 1141 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1142 * represents the reduction polynomial <code>f(z)</code>.<br> 1143 */ 1144 public int getK1() 1145 { 1146 return this.k1; 1147 } 1148 1149 /** 1150 * @return TPB: Always returns <code>0</code><br> 1151 * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 1152 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1153 * represents the reduction polynomial <code>f(z)</code>.<br> 1154 */ 1155 public int getK2() 1156 { 1157 return this.k2; 1158 } 1159 1160 /** 1161 * @return TPB: Always set to <code>0</code><br> 1162 * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 1163 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1164 * represents the reduction polynomial <code>f(z)</code>.<br> 1165 */ 1166 public int getK3() 1167 { 1168 return this.k3; 1169 } 1170 1171 public boolean equals(Object anObject) 1172 { 1173 if (anObject == this) 1174 { 1175 return true; 1176 } 1177 1178 if (!(anObject instanceof ECFieldElement.F2m)) 1179 { 1180 return false; 1181 } 1182 1183 ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 1184 1185 return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) 1186 && (this.k3 == b.k3) 1187 && (this.representation == b.representation) 1188 && (this.x.equals(b.x))); 1189 } 1190 1191 public int hashCode() 1192 { 1193 return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; 1194 } 1195 } 1196} 1197