1 package org.bouncycastle.math.ec; 2 3 import java.math.BigInteger; 4 import java.util.Random; 5 6 public 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
