1 package org.bouncycastle.math.ec; 2 3 import java.math.BigInteger; 4 import java.util.Random; 5 6 /** 7 * base class for an elliptic curve 8 */ 9 public abstract class ECCurve 10 { 11 ECFieldElement a, b; 12 13 public abstract int getFieldSize(); 14 15 public abstract ECFieldElement fromBigInteger(BigInteger x); 16 17 public abstract ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression); 18 19 public abstract ECPoint decodePoint(byte[] encoded); 20 21 public abstract ECPoint getInfinity(); 22 23 public ECFieldElement getA() 24 { 25 return a; 26 } 27 28 public ECFieldElement getB() 29 { 30 return b; 31 } 32 33 /** 34 * Elliptic curve over Fp 35 */ 36 public static class Fp extends ECCurve 37 { 38 BigInteger q; 39 ECPoint.Fp infinity; 40 41 public Fp(BigInteger q, BigInteger a, BigInteger b) 42 { 43 this.q = q; 44 this.a = fromBigInteger(a); 45 this.b = fromBigInteger(b); 46 this.infinity = new ECPoint.Fp(this, null, null); 47 } 48 49 public BigInteger getQ() 50 { 51 return q; 52 } 53 54 public int getFieldSize() 55 { 56 return q.bitLength(); 57 } 58 59 public ECFieldElement fromBigInteger(BigInteger x) 60 { 61 return new ECFieldElement.Fp(this.q, x); 62 } 63 64 public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression) 65 { 66 return new ECPoint.Fp(this, fromBigInteger(x), fromBigInteger(y), withCompression); 67 } 68 69 /** 70 * Decode a point on this curve from its ASN.1 encoding. The different 71 * encodings are taken account of, including point compression for 72 * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17). 73 * @return The decoded point. 74 */ 75 public ECPoint decodePoint(byte[] encoded) 76 { 77 ECPoint p = null; 78 79 switch (encoded[0]) 80 { 81 // infinity 82 case 0x00: 83 if (encoded.length > 1) 84 { 85 throw new RuntimeException("Invalid point encoding"); 86 } 87 p = getInfinity(); 88 break; 89 // compressed 90 case 0x02: 91 case 0x03: 92 int ytilde = encoded[0] & 1; 93 byte[] i = new byte[encoded.length - 1]; 94 95 System.arraycopy(encoded, 1, i, 0, i.length); 96 97 ECFieldElement x = new ECFieldElement.Fp(this.q, new BigInteger(1, i)); 98 ECFieldElement alpha = x.multiply(x.square().add(a)).add(b); 99 ECFieldElement beta = alpha.sqrt(); 100 101 // 102 // if we can't find a sqrt we haven't got a point on the 103 // curve - run! 104 // 105 if (beta == null) 106 { 107 throw new RuntimeException("Invalid point compression"); 108 } 109 110 int bit0 = (beta.toBigInteger().testBit(0) ? 1 : 0); 111 112 if (bit0 == ytilde) 113 { 114 p = new ECPoint.Fp(this, x, beta, true); 115 } 116 else 117 { 118 p = new ECPoint.Fp(this, x, 119 new ECFieldElement.Fp(this.q, q.subtract(beta.toBigInteger())), true); 120 } 121 break; 122 // uncompressed 123 case 0x04: 124 // hybrid 125 case 0x06: 126 case 0x07: 127 byte[] xEnc = new byte[(encoded.length - 1) / 2]; 128 byte[] yEnc = new byte[(encoded.length - 1) / 2]; 129 130 System.arraycopy(encoded, 1, xEnc, 0, xEnc.length); 131 System.arraycopy(encoded, xEnc.length + 1, yEnc, 0, yEnc.length); 132 133 p = new ECPoint.Fp(this, 134 new ECFieldElement.Fp(this.q, new BigInteger(1, xEnc)), 135 new ECFieldElement.Fp(this.q, new BigInteger(1, yEnc))); 136 break; 137 default: 138 throw new RuntimeException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16)); 139 } 140 141 return p; 142 } 143 144 public ECPoint getInfinity() 145 { 146 return infinity; 147 } 148 149 public boolean equals( 150 Object anObject) 151 { 152 if (anObject == this) 153 { 154 return true; 155 } 156 157 if (!(anObject instanceof ECCurve.Fp)) 158 { 159 return false; 160 } 161 162 ECCurve.Fp other = (ECCurve.Fp) anObject; 163 164 return this.q.equals(other.q) 165 && a.equals(other.a) && b.equals(other.b); 166 } 167 168 public int hashCode() 169 { 170 return a.hashCode() ^ b.hashCode() ^ q.hashCode(); 171 } 172 } 173 174 /** 175 * Elliptic curves over F2m. The Weierstrass equation is given by 176 * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>. 177 */ 178 public static class F2m extends ECCurve 179 { 180 /** 181 * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 182 */ 183 private int m; // can't be final - JDK 1.1 184 185 /** 186 * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 187 * x<sup>k</sup> + 1</code> represents the reduction polynomial 188 * <code>f(z)</code>.<br> 189 * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 190 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 191 * represents the reduction polynomial <code>f(z)</code>.<br> 192 */ 193 private int k1; // can't be final - JDK 1.1 194 195 /** 196 * TPB: Always set to <code>0</code><br> 197 * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 198 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 199 * represents the reduction polynomial <code>f(z)</code>.<br> 200 */ 201 private int k2; // can't be final - JDK 1.1 202 203 /** 204 * TPB: Always set to <code>0</code><br> 205 * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 206 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 207 * represents the reduction polynomial <code>f(z)</code>.<br> 208 */ 209 private int k3; // can't be final - JDK 1.1 210 211 /** 212 * The order of the base point of the curve. 213 */ 214 private BigInteger n; // can't be final - JDK 1.1 215 216 /** 217 * The cofactor of the curve. 218 */ 219 private BigInteger h; // can't be final - JDK 1.1 220 221 /** 222 * The point at infinity on this curve. 223 */ 224 private ECPoint.F2m infinity; // can't be final - JDK 1.1 225 226 /** 227 * The parameter <code>μ</code> of the elliptic curve if this is 228 * a Koblitz curve. 229 */ 230 private byte mu = 0; 231 232 /** 233 * The auxiliary values <code>s<sub>0</sub></code> and 234 * <code>s<sub>1</sub></code> used for partial modular reduction for 235 * Koblitz curves. 236 */ 237 private BigInteger[] si = null; 238 239 /** 240 * Constructor for Trinomial Polynomial Basis (TPB). 241 * @param m The exponent <code>m</code> of 242 * <code>F<sub>2<sup>m</sup></sub></code>. 243 * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 244 * x<sup>k</sup> + 1</code> represents the reduction 245 * polynomial <code>f(z)</code>. 246 * @param a The coefficient <code>a</code> in the Weierstrass equation 247 * for non-supersingular elliptic curves over 248 * <code>F<sub>2<sup>m</sup></sub></code>. 249 * @param b The coefficient <code>b</code> in the Weierstrass equation 250 * for non-supersingular elliptic curves over 251 * <code>F<sub>2<sup>m</sup></sub></code>. 252 */ 253 public F2m( 254 int m, 255 int k, 256 BigInteger a, 257 BigInteger b) 258 { 259 this(m, k, 0, 0, a, b, null, null); 260 } 261 262 /** 263 * Constructor for Trinomial Polynomial Basis (TPB). 264 * @param m The exponent <code>m</code> of 265 * <code>F<sub>2<sup>m</sup></sub></code>. 266 * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 267 * x<sup>k</sup> + 1</code> represents the reduction 268 * polynomial <code>f(z)</code>. 269 * @param a The coefficient <code>a</code> in the Weierstrass equation 270 * for non-supersingular elliptic curves over 271 * <code>F<sub>2<sup>m</sup></sub></code>. 272 * @param b The coefficient <code>b</code> in the Weierstrass equation 273 * for non-supersingular elliptic curves over 274 * <code>F<sub>2<sup>m</sup></sub></code>. 275 * @param n The order of the main subgroup of the elliptic curve. 276 * @param h The cofactor of the elliptic curve, i.e. 277 * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. 278 */ 279 public F2m( 280 int m, 281 int k, 282 BigInteger a, 283 BigInteger b, 284 BigInteger n, 285 BigInteger h) 286 { 287 this(m, k, 0, 0, a, b, n, h); 288 } 289 290 /** 291 * Constructor for Pentanomial Polynomial Basis (PPB). 292 * @param m The exponent <code>m</code> of 293 * <code>F<sub>2<sup>m</sup></sub></code>. 294 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 295 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 296 * represents the reduction polynomial <code>f(z)</code>. 297 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 298 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 299 * represents the reduction polynomial <code>f(z)</code>. 300 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 301 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 302 * represents the reduction polynomial <code>f(z)</code>. 303 * @param a The coefficient <code>a</code> in the Weierstrass equation 304 * for non-supersingular elliptic curves over 305 * <code>F<sub>2<sup>m</sup></sub></code>. 306 * @param b The coefficient <code>b</code> in the Weierstrass equation 307 * for non-supersingular elliptic curves over 308 * <code>F<sub>2<sup>m</sup></sub></code>. 309 */ 310 public F2m( 311 int m, 312 int k1, 313 int k2, 314 int k3, 315 BigInteger a, 316 BigInteger b) 317 { 318 this(m, k1, k2, k3, a, b, null, null); 319 } 320 321 /** 322 * Constructor for Pentanomial Polynomial Basis (PPB). 323 * @param m The exponent <code>m</code> of 324 * <code>F<sub>2<sup>m</sup></sub></code>. 325 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 326 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 327 * represents the reduction polynomial <code>f(z)</code>. 328 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 329 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 330 * represents the reduction polynomial <code>f(z)</code>. 331 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 332 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 333 * represents the reduction polynomial <code>f(z)</code>. 334 * @param a The coefficient <code>a</code> in the Weierstrass equation 335 * for non-supersingular elliptic curves over 336 * <code>F<sub>2<sup>m</sup></sub></code>. 337 * @param b The coefficient <code>b</code> in the Weierstrass equation 338 * for non-supersingular elliptic curves over 339 * <code>F<sub>2<sup>m</sup></sub></code>. 340 * @param n The order of the main subgroup of the elliptic curve. 341 * @param h The cofactor of the elliptic curve, i.e. 342 * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. 343 */ 344 public F2m( 345 int m, 346 int k1, 347 int k2, 348 int k3, 349 BigInteger a, 350 BigInteger b, 351 BigInteger n, 352 BigInteger h) 353 { 354 this.m = m; 355 this.k1 = k1; 356 this.k2 = k2; 357 this.k3 = k3; 358 this.n = n; 359 this.h = h; 360 361 if (k1 == 0) 362 { 363 throw new IllegalArgumentException("k1 must be > 0"); 364 } 365 366 if (k2 == 0) 367 { 368 if (k3 != 0) 369 { 370 throw new IllegalArgumentException("k3 must be 0 if k2 == 0"); 371 } 372 } 373 else 374 { 375 if (k2 <= k1) 376 { 377 throw new IllegalArgumentException("k2 must be > k1"); 378 } 379 380 if (k3 <= k2) 381 { 382 throw new IllegalArgumentException("k3 must be > k2"); 383 } 384 } 385 386 this.a = fromBigInteger(a); 387 this.b = fromBigInteger(b); 388 this.infinity = new ECPoint.F2m(this, null, null); 389 } 390 391 public int getFieldSize() 392 { 393 return m; 394 } 395 396 public ECFieldElement fromBigInteger(BigInteger x) 397 { 398 return new ECFieldElement.F2m(this.m, this.k1, this.k2, this.k3, x); 399 } 400 401 public ECPoint createPoint(BigInteger x, BigInteger y, boolean withCompression) 402 { 403 return new ECPoint.F2m(this, fromBigInteger(x), fromBigInteger(y), withCompression); 404 } 405 406 /* (non-Javadoc) 407 * @see org.bouncycastle.math.ec.ECCurve#decodePoint(byte[]) 408 */ 409 public ECPoint decodePoint(byte[] encoded) 410 { 411 ECPoint p = null; 412 413 switch (encoded[0]) 414 { 415 // infinity 416 case 0x00: 417 if (encoded.length > 1) 418 { 419 throw new RuntimeException("Invalid point encoding"); 420 } 421 p = getInfinity(); 422 break; 423 // compressed 424 case 0x02: 425 case 0x03: 426 byte[] enc = new byte[encoded.length - 1]; 427 System.arraycopy(encoded, 1, enc, 0, enc.length); 428 if (encoded[0] == 0x02) 429 { 430 p = decompressPoint(enc, 0); 431 } 432 else 433 { 434 p = decompressPoint(enc, 1); 435 } 436 break; 437 // uncompressed 438 case 0x04: 439 // hybrid 440 case 0x06: 441 case 0x07: 442 byte[] xEnc = new byte[(encoded.length - 1) / 2]; 443 byte[] yEnc = new byte[(encoded.length - 1) / 2]; 444 445 System.arraycopy(encoded, 1, xEnc, 0, xEnc.length); 446 System.arraycopy(encoded, xEnc.length + 1, yEnc, 0, yEnc.length); 447 448 p = new ECPoint.F2m(this, 449 new ECFieldElement.F2m(this.m, this.k1, this.k2, this.k3, 450 new BigInteger(1, xEnc)), 451 new ECFieldElement.F2m(this.m, this.k1, this.k2, this.k3, 452 new BigInteger(1, yEnc)), false); 453 break; 454 455 default: 456 throw new RuntimeException("Invalid point encoding 0x" + Integer.toString(encoded[0], 16)); 457 } 458 459 return p; 460 } 461 462 public ECPoint getInfinity() 463 { 464 return infinity; 465 } 466 467 /** 468 * Returns true if this is a Koblitz curve (ABC curve). 469 * @return true if this is a Koblitz curve (ABC curve), false otherwise 470 */ 471 public boolean isKoblitz() 472 { 473 return ((n != null) && (h != null) && 474 ((a.toBigInteger().equals(ECConstants.ZERO)) || 475 (a.toBigInteger().equals(ECConstants.ONE))) && 476 (b.toBigInteger().equals(ECConstants.ONE))); 477 } 478 479 /** 480 * Returns the parameter <code>μ</code> of the elliptic curve. 481 * @return <code>μ</code> of the elliptic curve. 482 * @throws IllegalArgumentException if the given ECCurve is not a 483 * Koblitz curve. 484 */ 485 synchronized byte getMu() 486 { 487 if (mu == 0) 488 { 489 mu = Tnaf.getMu(this); 490 } 491 return mu; 492 } 493 494 /** 495 * @return the auxiliary values <code>s<sub>0</sub></code> and 496 * <code>s<sub>1</sub></code> used for partial modular reduction for 497 * Koblitz curves. 498 */ 499 synchronized BigInteger[] getSi() 500 { 501 if (si == null) 502 { 503 si = Tnaf.getSi(this); 504 } 505 return si; 506 } 507 508 /** 509 * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). 510 * 511 * @param xEnc 512 * The encoding of field element xp. 513 * @param ypBit 514 * ~yp, an indication bit for the decompression of yp. 515 * @return the decompressed point. 516 */ 517 private ECPoint decompressPoint( 518 byte[] xEnc, 519 int ypBit) 520 { 521 ECFieldElement xp = new ECFieldElement.F2m( 522 this.m, this.k1, this.k2, this.k3, new BigInteger(1, xEnc)); 523 ECFieldElement yp = null; 524 if (xp.toBigInteger().equals(ECConstants.ZERO)) 525 { 526 yp = (ECFieldElement.F2m)b; 527 for (int i = 0; i < m - 1; i++) 528 { 529 yp = yp.square(); 530 } 531 } 532 else 533 { 534 ECFieldElement beta = xp.add(a).add( 535 b.multiply(xp.square().invert())); 536 ECFieldElement z = solveQuadradicEquation(beta); 537 if (z == null) 538 { 539 throw new RuntimeException("Invalid point compression"); 540 } 541 int zBit = 0; 542 if (z.toBigInteger().testBit(0)) 543 { 544 zBit = 1; 545 } 546 if (zBit != ypBit) 547 { 548 z = z.add(new ECFieldElement.F2m(this.m, this.k1, this.k2, 549 this.k3, ECConstants.ONE)); 550 } 551 yp = xp.multiply(z); 552 } 553 554 return new ECPoint.F2m(this, xp, yp); 555 } 556 557 /** 558 * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 559 * D.1.6) The other solution is <code>z + 1</code>. 560 * 561 * @param beta 562 * The value to solve the qradratic equation for. 563 * @return the solution for <code>z<sup>2</sup> + z = beta</code> or 564 * <code>null</code> if no solution exists. 565 */ 566 private ECFieldElement solveQuadradicEquation(ECFieldElement beta) 567 { 568 ECFieldElement zeroElement = new ECFieldElement.F2m( 569 this.m, this.k1, this.k2, this.k3, ECConstants.ZERO); 570 571 if (beta.toBigInteger().equals(ECConstants.ZERO)) 572 { 573 return zeroElement; 574 } 575 576 ECFieldElement z = null; 577 ECFieldElement gamma = zeroElement; 578 579 Random rand = new Random(); 580 do 581 { 582 ECFieldElement t = new ECFieldElement.F2m(this.m, this.k1, 583 this.k2, this.k3, new BigInteger(m, rand)); 584 z = zeroElement; 585 ECFieldElement w = beta; 586 for (int i = 1; i <= m - 1; i++) 587 { 588 ECFieldElement w2 = w.square(); 589 z = z.square().add(w2.multiply(t)); 590 w = w2.add(beta); 591 } 592 if (!w.toBigInteger().equals(ECConstants.ZERO)) 593 { 594 return null; 595 } 596 gamma = z.square().add(z); 597 } 598 while (gamma.toBigInteger().equals(ECConstants.ZERO)); 599 600 return z; 601 } 602 603 public boolean equals( 604 Object anObject) 605 { 606 if (anObject == this) 607 { 608 return true; 609 } 610 611 if (!(anObject instanceof ECCurve.F2m)) 612 { 613 return false; 614 } 615 616 ECCurve.F2m other = (ECCurve.F2m)anObject; 617 618 return (this.m == other.m) && (this.k1 == other.k1) 619 && (this.k2 == other.k2) && (this.k3 == other.k3) 620 && a.equals(other.a) && b.equals(other.b); 621 } 622 623 public int hashCode() 624 { 625 return this.a.hashCode() ^ this.b.hashCode() ^ m ^ k1 ^ k2 ^ k3; 626 } 627 628 public int getM() 629 { 630 return m; 631 } 632 633 /** 634 * Return true if curve uses a Trinomial basis. 635 * 636 * @return true if curve Trinomial, false otherwise. 637 */ 638 public boolean isTrinomial() 639 { 640 return k2 == 0 && k3 == 0; 641 } 642 643 public int getK1() 644 { 645 return k1; 646 } 647 648 public int getK2() 649 { 650 return k2; 651 } 652 653 public int getK3() 654 { 655 return k3; 656 } 657 658 public BigInteger getN() 659 { 660 return n; 661 } 662 663 public BigInteger getH() 664 { 665 return h; 666 } 667 } 668 } 669
