1 package org.bouncycastle.math.ec; 2 3 import java.math.BigInteger; 4 import java.util.Hashtable; 5 import java.util.Random; 6 7 import org.bouncycastle.math.ec.endo.ECEndomorphism; 8 import org.bouncycastle.math.ec.endo.GLVEndomorphism; 9 import org.bouncycastle.math.field.FiniteField; 10 import org.bouncycastle.math.field.FiniteFields; 11 import org.bouncycastle.util.BigIntegers; 12 import org.bouncycastle.util.Integers; 13 14 /** 15 * base class for an elliptic curve 16 */ 17 public abstract class ECCurve 18 { 19 public static final int COORD_AFFINE = 0; 20 public static final int COORD_HOMOGENEOUS = 1; 21 public static final int COORD_JACOBIAN = 2; 22 public static final int COORD_JACOBIAN_CHUDNOVSKY = 3; 23 public static final int COORD_JACOBIAN_MODIFIED = 4; 24 public static final int COORD_LAMBDA_AFFINE = 5; 25 public static final int COORD_LAMBDA_PROJECTIVE = 6; 26 public static final int COORD_SKEWED = 7; 27 28 public static int[] getAllCoordinateSystems() 29 { 30 return new int[]{ COORD_AFFINE, COORD_HOMOGENEOUS, COORD_JACOBIAN, COORD_JACOBIAN_CHUDNOVSKY, 31 COORD_JACOBIAN_MODIFIED, COORD_LAMBDA_AFFINE, COORD_LAMBDA_PROJECTIVE, COORD_SKEWED }; 32 } 33 34 public class Config 35 { 36 protected int coord; 37 protected ECEndomorphism endomorphism; 38 protected ECMultiplier multiplier; 39 40 Config(int coord, ECEndomorphism endomorphism, ECMultiplier multiplier) 41 { 42 this.coord = coord; 43 this.endomorphism = endomorphism; 44 this.multiplier = multiplier; 45 } 46 47 public Config setCoordinateSystem(int coord) 48 { 49 this.coord = coord; 50 return this; 51 } 52 53 public Config setEndomorphism(ECEndomorphism endomorphism) 54 { 55 this.endomorphism = endomorphism; 56 return this; 57 } 58 59 public Config setMultiplier(ECMultiplier multiplier) 60 { 61 this.multiplier = multiplier; 62 return this; 63 } 64 65 public ECCurve create() 66 { 67 if (!supportsCoordinateSystem(coord)) 68 { 69 throw new IllegalStateException("unsupported coordinate system"); 70 } 71 72 ECCurve c = cloneCurve(); 73 if (c == ECCurve.this) 74 { 75 throw new IllegalStateException("implementation returned current curve"); 76 } 77 78 // NOTE: Synchronization added to keep FindBugs happy 79 synchronized (c) 80 { 81 c.coord = coord; 82 c.endomorphism = endomorphism; 83 c.multiplier = multiplier; 84 } 85 86 return c; 87 } 88 } 89 90 protected FiniteField field; 91 protected ECFieldElement a, b; 92 protected BigInteger order, cofactor; 93 94 protected int coord = COORD_AFFINE; 95 protected ECEndomorphism endomorphism = null; 96 protected ECMultiplier multiplier = null; 97 98 protected ECCurve(FiniteField field) 99 { 100 this.field = field; 101 } 102 103 public abstract int getFieldSize(); 104 105 public abstract ECFieldElement fromBigInteger(BigInteger x); 106 107 public abstract boolean isValidFieldElement(BigInteger x); 108 109 public synchronized Config configure() 110 { 111 return new Config(this.coord, this.endomorphism, this.multiplier); 112 } 113 114 public ECPoint validatePoint(BigInteger x, BigInteger y) 115 { 116 ECPoint p = createPoint(x, y); 117 if (!p.isValid()) 118 { 119 throw new IllegalArgumentException("Invalid point coordinates"); 120 } 121 return p; 122 } 123 124 /** 125 * @deprecated per-point compression property will be removed, use {@link #validatePoint(BigInteger, BigInteger)} 126 * and refer {@link ECPoint#getEncoded(boolean)} 127 */ 128 public ECPoint validatePoint(BigInteger x, BigInteger y, boolean withCompression) 129 { 130 ECPoint p = createPoint(x, y, withCompression); 131 if (!p.isValid()) 132 { 133 throw new IllegalArgumentException("Invalid point coordinates"); 134 } 135 return p; 136 } 137 138 public ECPoint createPoint(BigInteger x, BigInteger y) 139 { 140 return createPoint(x, y, false); 141 } 142 143 /** 144 * @deprecated per-point compression property will be removed, use {@link #createPoint(BigInteger, BigInteger)} 145 * and refer {@link ECPoint#getEncoded(boolean)} 146 */ 147 public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression) 148 { 149 return createRawPoint(fromBigInteger(x), fromBigInteger(y), withCompression); 150 } 151 152 protected abstract ECCurve cloneCurve(); 153 154 protected abstract ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression); 155 156 protected abstract ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression); 157 158 protected ECMultiplier createDefaultMultiplier() 159 { 160 if (endomorphism instanceof GLVEndomorphism) 161 { 162 return new GLVMultiplier(this, (GLVEndomorphism)endomorphism); 163 } 164 165 return new WNafL2RMultiplier(); 166 } 167 168 public boolean supportsCoordinateSystem(int coord) 169 { 170 return coord == COORD_AFFINE; 171 } 172 173 public PreCompInfo getPreCompInfo(ECPoint point, String name) 174 { 175 checkPoint(point); 176 synchronized (point) 177 { 178 Hashtable table = point.preCompTable; 179 return table == null ? null : (PreCompInfo)table.get(name); 180 } 181 } 182 183 /** 184 * Adds <code>PreCompInfo</code> for a point on this curve, under a given name. Used by 185 * <code>ECMultiplier</code>s to save the precomputation for this <code>ECPoint</code> for use 186 * by subsequent multiplication. 187 * 188 * @param point 189 * The <code>ECPoint</code> to store precomputations for. 190 * @param name 191 * A <code>String</code> used to index precomputations of different types. 192 * @param preCompInfo 193 * The values precomputed by the <code>ECMultiplier</code>. 194 */ 195 public void setPreCompInfo(ECPoint point, String name, PreCompInfo preCompInfo) 196 { 197 checkPoint(point); 198 synchronized (point) 199 { 200 Hashtable table = point.preCompTable; 201 if (null == table) 202 { 203 point.preCompTable = table = new Hashtable(4); 204 } 205 table.put(name, preCompInfo); 206 } 207 } 208 209 public ECPoint importPoint(ECPoint p) 210 { 211 if (this == p.getCurve()) 212 { 213 return p; 214 } 215 if (p.isInfinity()) 216 { 217 return getInfinity(); 218 } 219 220 // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any Z coordinates. 221 p = p.normalize(); 222 223 return validatePoint(p.getXCoord().toBigInteger(), p.getYCoord().toBigInteger(), p.withCompression); 224 } 225 226 /** 227 * Normalization ensures that any projective coordinate is 1, and therefore that the x, y 228 * coordinates reflect those of the equivalent point in an affine coordinate system. Where more 229 * than one point is to be normalized, this method will generally be more efficient than 230 * normalizing each point separately. 231 * 232 * @param points 233 * An array of points that will be updated in place with their normalized versions, 234 * where necessary 235 */ 236 public void normalizeAll(ECPoint[] points) 237 { 238 normalizeAll(points, 0, points.length, null); 239 } 240 241 /** 242 * Normalization ensures that any projective coordinate is 1, and therefore that the x, y 243 * coordinates reflect those of the equivalent point in an affine coordinate system. Where more 244 * than one point is to be normalized, this method will generally be more efficient than 245 * normalizing each point separately. An (optional) z-scaling factor can be applied; effectively 246 * each z coordinate is scaled by this value prior to normalization (but only one 247 * actual multiplication is needed). 248 * 249 * @param points 250 * An array of points that will be updated in place with their normalized versions, 251 * where necessary 252 * @param off 253 * The start of the range of points to normalize 254 * @param len 255 * The length of the range of points to normalize 256 * @param iso 257 * The (optional) z-scaling factor - can be null 258 */ 259 public void normalizeAll(ECPoint[] points, int off, int len, ECFieldElement iso) 260 { 261 checkPoints(points, off, len); 262 263 switch (this.getCoordinateSystem()) 264 { 265 case ECCurve.COORD_AFFINE: 266 case ECCurve.COORD_LAMBDA_AFFINE: 267 { 268 if (iso != null) 269 { 270 throw new IllegalArgumentException("'iso' not valid for affine coordinates"); 271 } 272 return; 273 } 274 } 275 276 /* 277 * Figure out which of the points actually need to be normalized 278 */ 279 ECFieldElement[] zs = new ECFieldElement[len]; 280 int[] indices = new int[len]; 281 int count = 0; 282 for (int i = 0; i < len; ++i) 283 { 284 ECPoint p = points[off + i]; 285 if (null != p && (iso != null || !p.isNormalized())) 286 { 287 zs[count] = p.getZCoord(0); 288 indices[count++] = off + i; 289 } 290 } 291 292 if (count == 0) 293 { 294 return; 295 } 296 297 ECAlgorithms.montgomeryTrick(zs, 0, count, iso); 298 299 for (int j = 0; j < count; ++j) 300 { 301 int index = indices[j]; 302 points[index] = points[index].normalize(zs[j]); 303 } 304 } 305 306 public abstract ECPoint getInfinity(); 307 308 public FiniteField getField() 309 { 310 return field; 311 } 312 313 public ECFieldElement getA() 314 { 315 return a; 316 } 317 318 public ECFieldElement getB() 319 { 320 return b; 321 } 322 323 public BigInteger getOrder() 324 { 325 return order; 326 } 327 328 public BigInteger getCofactor() 329 { 330 return cofactor; 331 } 332 333 public int getCoordinateSystem() 334 { 335 return coord; 336 } 337 338 protected abstract ECPoint decompressPoint(int yTilde, BigInteger X1); 339 340 public ECEndomorphism getEndomorphism() 341 { 342 return endomorphism; 343 } 344 345 /** 346 * Sets the default <code>ECMultiplier</code>, unless already set. 347 */ 348 public synchronized ECMultiplier getMultiplier() 349 { 350 if (this.multiplier == null) 351 { 352 this.multiplier = createDefaultMultiplier(); 353 } 354 return this.multiplier; 355 } 356 357 /** 358 * Decode a point on this curve from its ASN.1 encoding. The different 359 * encodings are taken account of, including point compression for 360 * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17). 361 * @return The decoded point. 362 */ 363 public ECPoint decodePoint(byte[] encoded) 364 { 365 ECPoint p = null; 366 int expectedLength = (getFieldSize() + 7) / 8; 367 368 byte type = encoded[0]; 369 switch (type) 370 { 371 case 0x00: // infinity 372 { 373 if (encoded.length != 1) 374 { 375 throw new IllegalArgumentException("Incorrect length for infinity encoding"); 376 } 377 378 p = getInfinity(); 379 break; 380 } 381 case 0x02: // compressed 382 case 0x03: // compressed 383 { 384 if (encoded.length != (expectedLength + 1)) 385 { 386 throw new IllegalArgumentException("Incorrect length for compressed encoding"); 387 } 388 389 int yTilde = type & 1; 390 BigInteger X = BigIntegers.fromUnsignedByteArray(encoded, 1, expectedLength); 391 392 p = decompressPoint(yTilde, X); 393 if (!p.satisfiesCofactor()) 394 { 395 throw new IllegalArgumentException("Invalid point"); 396 } 397 398 break; 399 } 400 case 0x04: // uncompressed 401 { 402 if (encoded.length != (2 * expectedLength + 1)) 403 { 404 throw new IllegalArgumentException("Incorrect length for uncompressed encoding"); 405 } 406 407 BigInteger X = BigIntegers.fromUnsignedByteArray(encoded, 1, expectedLength); 408 BigInteger Y = BigIntegers.fromUnsignedByteArray(encoded, 1 + expectedLength, expectedLength); 409 410 p = validatePoint(X, Y); 411 break; 412 } 413 case 0x06: // hybrid 414 case 0x07: // hybrid 415 { 416 if (encoded.length != (2 * expectedLength + 1)) 417 { 418 throw new IllegalArgumentException("Incorrect length for hybrid encoding"); 419 } 420 421 BigInteger X = BigIntegers.fromUnsignedByteArray(encoded, 1, expectedLength); 422 BigInteger Y = BigIntegers.fromUnsignedByteArray(encoded, 1 + expectedLength, expectedLength); 423 424 if (Y.testBit(0) != (type == 0x07)) 425 { 426 throw new IllegalArgumentException("Inconsistent Y coordinate in hybrid encoding"); 427 } 428 429 p = validatePoint(X, Y); 430 break; 431 } 432 default: 433 throw new IllegalArgumentException("Invalid point encoding 0x" + Integer.toString(type, 16)); 434 } 435 436 if (type != 0x00 && p.isInfinity()) 437 { 438 throw new IllegalArgumentException("Invalid infinity encoding"); 439 } 440 441 return p; 442 } 443 444 protected void checkPoint(ECPoint point) 445 { 446 if (null == point || (this != point.getCurve())) 447 { 448 throw new IllegalArgumentException("'point' must be non-null and on this curve"); 449 } 450 } 451 452 protected void checkPoints(ECPoint[] points) 453 { 454 checkPoints(points, 0, points.length); 455 } 456 457 protected void checkPoints(ECPoint[] points, int off, int len) 458 { 459 if (points == null) 460 { 461 throw new IllegalArgumentException("'points' cannot be null"); 462 } 463 if (off < 0 || len < 0 || (off > (points.length - len))) 464 { 465 throw new IllegalArgumentException("invalid range specified for 'points'"); 466 } 467 468 for (int i = 0; i < len; ++i) 469 { 470 ECPoint point = points[off + i]; 471 if (null != point && this != point.getCurve()) 472 { 473 throw new IllegalArgumentException("'points' entries must be null or on this curve"); 474 } 475 } 476 } 477 478 public boolean equals(ECCurve other) 479 { 480 return this == other 481 || (null != other 482 && getField().equals(other.getField()) 483 && getA().toBigInteger().equals(other.getA().toBigInteger()) 484 && getB().toBigInteger().equals(other.getB().toBigInteger())); 485 } 486 487 public boolean equals(Object obj) 488 { 489 return this == obj || (obj instanceof ECCurve && equals((ECCurve)obj)); 490 } 491 492 public int hashCode() 493 { 494 return getField().hashCode() 495 ^ Integers.rotateLeft(getA().toBigInteger().hashCode(), 8) 496 ^ Integers.rotateLeft(getB().toBigInteger().hashCode(), 16); 497 } 498 499 public static abstract class AbstractFp extends ECCurve 500 { 501 protected AbstractFp(BigInteger q) 502 { 503 super(FiniteFields.getPrimeField(q)); 504 } 505 506 public boolean isValidFieldElement(BigInteger x) 507 { 508 return x != null && x.signum() >= 0 && x.compareTo(this.getField().getCharacteristic()) < 0; 509 } 510 511 protected ECPoint decompressPoint(int yTilde, BigInteger X1) 512 { 513 ECFieldElement x = this.fromBigInteger(X1); 514 ECFieldElement rhs = x.square().add(this.a).multiply(x).add(this.b); 515 ECFieldElement y = rhs.sqrt(); 516 517 /* 518 * If y is not a square, then we haven't got a point on the curve 519 */ 520 if (y == null) 521 { 522 throw new IllegalArgumentException("Invalid point compression"); 523 } 524 525 if (y.testBitZero() != (yTilde == 1)) 526 { 527 // Use the other root 528 y = y.negate(); 529 } 530 531 return this.createRawPoint(x, y, true); 532 } 533 } 534 535 /** 536 * Elliptic curve over Fp 537 */ 538 public static class Fp extends AbstractFp 539 { 540 private static final int FP_DEFAULT_COORDS = ECCurve.COORD_JACOBIAN_MODIFIED; 541 542 BigInteger q, r; 543 ECPoint.Fp infinity; 544 545 public Fp(BigInteger q, BigInteger a, BigInteger b) 546 { 547 this(q, a, b, null, null); 548 } 549 550 public Fp(BigInteger q, BigInteger a, BigInteger b, BigInteger order, BigInteger cofactor) 551 { 552 super(q); 553 554 this.q = q; 555 this.r = ECFieldElement.Fp.calculateResidue(q); 556 this.infinity = new ECPoint.Fp(this, null, null); 557 558 this.a = fromBigInteger(a); 559 this.b = fromBigInteger(b); 560 this.order = order; 561 this.cofactor = cofactor; 562 this.coord = FP_DEFAULT_COORDS; 563 } 564 565 protected Fp(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b) 566 { 567 this(q, r, a, b, null, null); 568 } 569 570 protected Fp(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b, BigInteger order, BigInteger cofactor) 571 { 572 super(q); 573 574 this.q = q; 575 this.r = r; 576 this.infinity = new ECPoint.Fp(this, null, null); 577 578 this.a = a; 579 this.b = b; 580 this.order = order; 581 this.cofactor = cofactor; 582 this.coord = FP_DEFAULT_COORDS; 583 } 584 585 protected ECCurve cloneCurve() 586 { 587 return new Fp(this.q, this.r, this.a, this.b, this.order, this.cofactor); 588 } 589 590 public boolean supportsCoordinateSystem(int coord) 591 { 592 switch (coord) 593 { 594 case ECCurve.COORD_AFFINE: 595 case ECCurve.COORD_HOMOGENEOUS: 596 case ECCurve.COORD_JACOBIAN: 597 case ECCurve.COORD_JACOBIAN_MODIFIED: 598 return true; 599 default: 600 return false; 601 } 602 } 603 604 public BigInteger getQ() 605 { 606 return q; 607 } 608 609 public int getFieldSize() 610 { 611 return q.bitLength(); 612 } 613 614 public ECFieldElement fromBigInteger(BigInteger x) 615 { 616 return new ECFieldElement.Fp(this.q, this.r, x); 617 } 618 619 protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) 620 { 621 return new ECPoint.Fp(this, x, y, withCompression); 622 } 623 624 protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) 625 { 626 return new ECPoint.Fp(this, x, y, zs, withCompression); 627 } 628 629 public ECPoint importPoint(ECPoint p) 630 { 631 if (this != p.getCurve() && this.getCoordinateSystem() == ECCurve.COORD_JACOBIAN && !p.isInfinity()) 632 { 633 switch (p.getCurve().getCoordinateSystem()) 634 { 635 case ECCurve.COORD_JACOBIAN: 636 case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: 637 case ECCurve.COORD_JACOBIAN_MODIFIED: 638 return new ECPoint.Fp(this, 639 fromBigInteger(p.x.toBigInteger()), 640 fromBigInteger(p.y.toBigInteger()), 641 new ECFieldElement[]{ fromBigInteger(p.zs[0].toBigInteger()) }, 642 p.withCompression); 643 default: 644 break; 645 } 646 } 647 648 return super.importPoint(p); 649 } 650 651 public ECPoint getInfinity() 652 { 653 return infinity; 654 } 655 } 656 657 public static abstract class AbstractF2m extends ECCurve 658 { 659 public static BigInteger inverse(int m, int[] ks, BigInteger x) 660 { 661 return new LongArray(x).modInverse(m, ks).toBigInteger(); 662 } 663 664 /** 665 * The auxiliary values <code>s<sub>0</sub></code> and 666 * <code>s<sub>1</sub></code> used for partial modular reduction for 667 * Koblitz curves. 668 */ 669 private BigInteger[] si = null; 670 671 private static FiniteField buildField(int m, int k1, int k2, int k3) 672 { 673 if (k1 == 0) 674 { 675 throw new IllegalArgumentException("k1 must be > 0"); 676 } 677 678 if (k2 == 0) 679 { 680 if (k3 != 0) 681 { 682 throw new IllegalArgumentException("k3 must be 0 if k2 == 0"); 683 } 684 685 return FiniteFields.getBinaryExtensionField(new int[]{ 0, k1, m }); 686 } 687 688 if (k2 <= k1) 689 { 690 throw new IllegalArgumentException("k2 must be > k1"); 691 } 692 693 if (k3 <= k2) 694 { 695 throw new IllegalArgumentException("k3 must be > k2"); 696 } 697 698 return FiniteFields.getBinaryExtensionField(new int[]{ 0, k1, k2, k3, m }); 699 } 700 701 protected AbstractF2m(int m, int k1, int k2, int k3) 702 { 703 super(buildField(m, k1, k2, k3)); 704 } 705 706 public boolean isValidFieldElement(BigInteger x) 707 { 708 return x != null && x.signum() >= 0 && x.bitLength() <= this.getFieldSize(); 709 } 710 711 public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression) 712 { 713 ECFieldElement X = this.fromBigInteger(x), Y = this.fromBigInteger(y); 714 715 int coord = this.getCoordinateSystem(); 716 717 switch (coord) 718 { 719 case ECCurve.COORD_LAMBDA_AFFINE: 720 case ECCurve.COORD_LAMBDA_PROJECTIVE: 721 { 722 if (X.isZero()) 723 { 724 if (!Y.square().equals(this.getB())) 725 { 726 throw new IllegalArgumentException(); 727 } 728 } 729 /* 730 * NOTE: A division could be avoided using a projective result, except at present 731 * callers will expect that the result is already normalized. 732 */ 733 // else if (coord == COORD_LAMBDA_PROJECTIVE) 734 // { 735 // ECFieldElement Z = X; 736 // X = X.square(); 737 // Y = Y.add(X); 738 // return createRawPoint(X, Y, new ECFieldElement[]{ Z }, withCompression); 739 // } 740 else 741 { 742 // Y becomes Lambda (X + Y/X) here 743 Y = Y.divide(X).add(X); 744 } 745 break; 746 } 747 default: 748 { 749 break; 750 } 751 } 752 753 return this.createRawPoint(X, Y, withCompression); 754 } 755 756 /** 757 * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). 758 * 759 * @param yTilde 760 * ~yp, an indication bit for the decompression of yp. 761 * @param X1 762 * The field element xp. 763 * @return the decompressed point. 764 */ 765 protected ECPoint decompressPoint(int yTilde, BigInteger X1) 766 { 767 ECFieldElement x = this.fromBigInteger(X1), y = null; 768 if (x.isZero()) 769 { 770 y = this.getB().sqrt(); 771 } 772 else 773 { 774 ECFieldElement beta = x.square().invert().multiply(this.getB()).add(this.getA()).add(x); 775 ECFieldElement z = solveQuadraticEquation(beta); 776 if (z != null) 777 { 778 if (z.testBitZero() != (yTilde == 1)) 779 { 780 z = z.addOne(); 781 } 782 783 switch (this.getCoordinateSystem()) 784 { 785 case ECCurve.COORD_LAMBDA_AFFINE: 786 case ECCurve.COORD_LAMBDA_PROJECTIVE: 787 { 788 y = z.add(x); 789 break; 790 } 791 default: 792 { 793 y = z.multiply(x); 794 break; 795 } 796 } 797 } 798 } 799 800 if (y == null) 801 { 802 throw new IllegalArgumentException("Invalid point compression"); 803 } 804 805 return this.createRawPoint(x, y, true); 806 } 807 808 /** 809 * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 810 * D.1.6) The other solution is <code>z + 1</code>. 811 * 812 * @param beta 813 * The value to solve the quadratic equation for. 814 * @return the solution for <code>z<sup>2</sup> + z = beta</code> or 815 * <code>null</code> if no solution exists. 816 */ 817 private ECFieldElement solveQuadraticEquation(ECFieldElement beta) 818 { 819 if (beta.isZero()) 820 { 821 return beta; 822 } 823 824 ECFieldElement gamma, z, zeroElement = this.fromBigInteger(ECConstants.ZERO); 825 826 int m = this.getFieldSize(); 827 Random rand = new Random(); 828 do 829 { 830 ECFieldElement t = this.fromBigInteger(new BigInteger(m, rand)); 831 z = zeroElement; 832 ECFieldElement w = beta; 833 for (int i = 1; i < m; i++) 834 { 835 ECFieldElement w2 = w.square(); 836 z = z.square().add(w2.multiply(t)); 837 w = w2.add(beta); 838 } 839 if (!w.isZero()) 840 { 841 return null; 842 } 843 gamma = z.square().add(z); 844 } 845 while (gamma.isZero()); 846 847 return z; 848 } 849 850 /** 851 * @return the auxiliary values <code>s<sub>0</sub></code> and 852 * <code>s<sub>1</sub></code> used for partial modular reduction for 853 * Koblitz curves. 854 */ 855 synchronized BigInteger[] getSi() 856 { 857 if (si == null) 858 { 859 si = Tnaf.getSi(this); 860 } 861 return si; 862 } 863 864 /** 865 * Returns true if this is a Koblitz curve (ABC curve). 866 * @return true if this is a Koblitz curve (ABC curve), false otherwise 867 */ 868 public boolean isKoblitz() 869 { 870 return this.order != null && this.cofactor != null && this.b.isOne() && (this.a.isZero() || this.a.isOne()); 871 } 872 } 873 874 /** 875 * Elliptic curves over F2m. The Weierstrass equation is given by 876 * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>. 877 */ 878 public static class F2m extends AbstractF2m 879 { 880 private static final int F2M_DEFAULT_COORDS = ECCurve.COORD_LAMBDA_PROJECTIVE; 881 882 /** 883 * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 884 */ 885 private int m; // can't be final - JDK 1.1 886 887 /** 888 * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 889 * x<sup>k</sup> + 1</code> represents the reduction polynomial 890 * <code>f(z)</code>.<br> 891 * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 892 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 893 * represents the reduction polynomial <code>f(z)</code>.<br> 894 */ 895 private int k1; // can't be final - JDK 1.1 896 897 /** 898 * TPB: Always set to <code>0</code><br> 899 * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 900 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 901 * represents the reduction polynomial <code>f(z)</code>.<br> 902 */ 903 private int k2; // can't be final - JDK 1.1 904 905 /** 906 * TPB: Always set to <code>0</code><br> 907 * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 908 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 909 * represents the reduction polynomial <code>f(z)</code>.<br> 910 */ 911 private int k3; // can't be final - JDK 1.1 912 913 /** 914 * The point at infinity on this curve. 915 */ 916 private ECPoint.F2m infinity; // can't be final - JDK 1.1 917 918 /** 919 * Constructor for Trinomial Polynomial Basis (TPB). 920 * @param m The exponent <code>m</code> of 921 * <code>F<sub>2<sup>m</sup></sub></code>. 922 * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 923 * x<sup>k</sup> + 1</code> represents the reduction 924 * polynomial <code>f(z)</code>. 925 * @param a The coefficient <code>a</code> in the Weierstrass equation 926 * for non-supersingular elliptic curves over 927 * <code>F<sub>2<sup>m</sup></sub></code>. 928 * @param b The coefficient <code>b</code> in the Weierstrass equation 929 * for non-supersingular elliptic curves over 930 * <code>F<sub>2<sup>m</sup></sub></code>. 931 */ 932 public F2m( 933 int m, 934 int k, 935 BigInteger a, 936 BigInteger b) 937 { 938 this(m, k, 0, 0, a, b, null, null); 939 } 940 941 /** 942 * Constructor for Trinomial Polynomial Basis (TPB). 943 * @param m The exponent <code>m</code> of 944 * <code>F<sub>2<sup>m</sup></sub></code>. 945 * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 946 * x<sup>k</sup> + 1</code> represents the reduction 947 * polynomial <code>f(z)</code>. 948 * @param a The coefficient <code>a</code> in the Weierstrass equation 949 * for non-supersingular elliptic curves over 950 * <code>F<sub>2<sup>m</sup></sub></code>. 951 * @param b The coefficient <code>b</code> in the Weierstrass equation 952 * for non-supersingular elliptic curves over 953 * <code>F<sub>2<sup>m</sup></sub></code>. 954 * @param order The order of the main subgroup of the elliptic curve. 955 * @param cofactor The cofactor of the elliptic curve, i.e. 956 * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. 957 */ 958 public F2m( 959 int m, 960 int k, 961 BigInteger a, 962 BigInteger b, 963 BigInteger order, 964 BigInteger cofactor) 965 { 966 this(m, k, 0, 0, a, b, order, cofactor); 967 } 968 969 /** 970 * Constructor for Pentanomial Polynomial Basis (PPB). 971 * @param m The exponent <code>m</code> of 972 * <code>F<sub>2<sup>m</sup></sub></code>. 973 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 974 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 975 * represents the reduction polynomial <code>f(z)</code>. 976 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 977 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 978 * represents the reduction polynomial <code>f(z)</code>. 979 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 980 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 981 * represents the reduction polynomial <code>f(z)</code>. 982 * @param a The coefficient <code>a</code> in the Weierstrass equation 983 * for non-supersingular elliptic curves over 984 * <code>F<sub>2<sup>m</sup></sub></code>. 985 * @param b The coefficient <code>b</code> in the Weierstrass equation 986 * for non-supersingular elliptic curves over 987 * <code>F<sub>2<sup>m</sup></sub></code>. 988 */ 989 public F2m( 990 int m, 991 int k1, 992 int k2, 993 int k3, 994 BigInteger a, 995 BigInteger b) 996 { 997 this(m, k1, k2, k3, a, b, null, null); 998 } 999 1000 /** 1001 * Constructor for Pentanomial Polynomial Basis (PPB). 1002 * @param m The exponent <code>m</code> of 1003 * <code>F<sub>2<sup>m</sup></sub></code>. 1004 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 1005 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1006 * represents the reduction polynomial <code>f(z)</code>. 1007 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 1008 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1009 * represents the reduction polynomial <code>f(z)</code>. 1010 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 1011 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 1012 * represents the reduction polynomial <code>f(z)</code>. 1013 * @param a The coefficient <code>a</code> in the Weierstrass equation 1014 * for non-supersingular elliptic curves over 1015 * <code>F<sub>2<sup>m</sup></sub></code>. 1016 * @param b The coefficient <code>b</code> in the Weierstrass equation 1017 * for non-supersingular elliptic curves over 1018 * <code>F<sub>2<sup>m</sup></sub></code>. 1019 * @param order The order of the main subgroup of the elliptic curve. 1020 * @param cofactor The cofactor of the elliptic curve, i.e. 1021 * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. 1022 */ 1023 public F2m( 1024 int m, 1025 int k1, 1026 int k2, 1027 int k3, 1028 BigInteger a, 1029 BigInteger b, 1030 BigInteger order, 1031 BigInteger cofactor) 1032 { 1033 super(m, k1, k2, k3); 1034 1035 this.m = m; 1036 this.k1 = k1; 1037 this.k2 = k2; 1038 this.k3 = k3; 1039 this.order = order; 1040 this.cofactor = cofactor; 1041 1042 this.infinity = new ECPoint.F2m(this, null, null); 1043 this.a = fromBigInteger(a); 1044 this.b = fromBigInteger(b); 1045 this.coord = F2M_DEFAULT_COORDS; 1046 } 1047 1048 protected F2m(int m, int k1, int k2, int k3, ECFieldElement a, ECFieldElement b, BigInteger order, BigInteger cofactor) 1049 { 1050 super(m, k1, k2, k3); 1051 1052 this.m = m; 1053 this.k1 = k1; 1054 this.k2 = k2; 1055 this.k3 = k3; 1056 this.order = order; 1057 this.cofactor = cofactor; 1058 1059 this.infinity = new ECPoint.F2m(this, null, null); 1060 this.a = a; 1061 this.b = b; 1062 this.coord = F2M_DEFAULT_COORDS; 1063 } 1064 1065 protected ECCurve cloneCurve() 1066 { 1067 return new F2m(this.m, this.k1, this.k2, this.k3, this.a, this.b, this.order, this.cofactor); 1068 } 1069 1070 public boolean supportsCoordinateSystem(int coord) 1071 { 1072 switch (coord) 1073 { 1074 case ECCurve.COORD_AFFINE: 1075 case ECCurve.COORD_HOMOGENEOUS: 1076 case ECCurve.COORD_LAMBDA_PROJECTIVE: 1077 return true; 1078 default: 1079 return false; 1080 } 1081 } 1082 1083 protected ECMultiplier createDefaultMultiplier() 1084 { 1085 if (isKoblitz()) 1086 { 1087 return new WTauNafMultiplier(); 1088 } 1089 1090 return super.createDefaultMultiplier(); 1091 } 1092 1093 public int getFieldSize() 1094 { 1095 return m; 1096 } 1097 1098 public ECFieldElement fromBigInteger(BigInteger x) 1099 { 1100 return new ECFieldElement.F2m(this.m, this.k1, this.k2, this.k3, x); 1101 } 1102 1103 protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) 1104 { 1105 return new ECPoint.F2m(this, x, y, withCompression); 1106 } 1107 1108 protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) 1109 { 1110 return new ECPoint.F2m(this, x, y, zs, withCompression); 1111 } 1112 1113 public ECPoint getInfinity() 1114 { 1115 return infinity; 1116 } 1117 1118 public int getM() 1119 { 1120 return m; 1121 } 1122 1123 /** 1124 * Return true if curve uses a Trinomial basis. 1125 * 1126 * @return true if curve Trinomial, false otherwise. 1127 */ 1128 public boolean isTrinomial() 1129 { 1130 return k2 == 0 && k3 == 0; 1131 } 1132 1133 public int getK1() 1134 { 1135 return k1; 1136 } 1137 1138 public int getK2() 1139 { 1140 return k2; 1141 } 1142 1143 public int getK3() 1144 { 1145 return k3; 1146 } 1147 1148 /** 1149 * @deprecated use {@link #getOrder()} instead 1150 */ 1151 public BigInteger getN() 1152 { 1153 return this.order; 1154 } 1155 1156 /** 1157 * @deprecated use {@link #getCofactor()} instead 1158 */ 1159 public BigInteger getH() 1160 { 1161 return this.cofactor; 1162 } 1163 } 1164 } 1165