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