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