001: package org.bouncycastle.math.ec;
002:
003: import java.math.BigInteger;
004: import java.util.Random;
005:
006: /**
007: * base class for an elliptic curve
008: */
009: public abstract class ECCurve {
010: ECFieldElement a, b;
011:
012: public abstract int getFieldSize();
013:
014: public abstract ECFieldElement fromBigInteger(BigInteger x);
015:
016: public abstract ECPoint createPoint(BigInteger x, BigInteger y,
017: boolean withCompression);
018:
019: public abstract ECPoint decodePoint(byte[] encoded);
020:
021: public abstract ECPoint getInfinity();
022:
023: public ECFieldElement getA() {
024: return a;
025: }
026:
027: public ECFieldElement getB() {
028: return b;
029: }
030:
031: /**
032: * Elliptic curve over Fp
033: */
034: public static class Fp extends ECCurve {
035: BigInteger q;
036: ECPoint.Fp infinity;
037:
038: public Fp(BigInteger q, BigInteger a, BigInteger b) {
039: this .q = q;
040: this .a = fromBigInteger(a);
041: this .b = fromBigInteger(b);
042: this .infinity = new ECPoint.Fp(this , null, null);
043: }
044:
045: public BigInteger getQ() {
046: return q;
047: }
048:
049: public int getFieldSize() {
050: return q.bitLength();
051: }
052:
053: public ECFieldElement fromBigInteger(BigInteger x) {
054: return new ECFieldElement.Fp(this .q, x);
055: }
056:
057: public ECPoint createPoint(BigInteger x, BigInteger y,
058: boolean withCompression) {
059: return new ECPoint.Fp(this , fromBigInteger(x),
060: fromBigInteger(y), withCompression);
061: }
062:
063: /**
064: * Decode a point on this curve from its ASN.1 encoding. The different
065: * encodings are taken account of, including point compression for
066: * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17).
067: * @return The decoded point.
068: */
069: public ECPoint decodePoint(byte[] encoded) {
070: ECPoint p = null;
071:
072: switch (encoded[0]) {
073: // infinity
074: case 0x00:
075: p = getInfinity();
076: break;
077: // compressed
078: case 0x02:
079: case 0x03:
080: int ytilde = encoded[0] & 1;
081: byte[] i = new byte[encoded.length - 1];
082:
083: System.arraycopy(encoded, 1, i, 0, i.length);
084:
085: ECFieldElement x = new ECFieldElement.Fp(this .q,
086: new BigInteger(1, i));
087: ECFieldElement alpha = x.multiply(x.square().add(a))
088: .add(b);
089: ECFieldElement beta = alpha.sqrt();
090:
091: //
092: // if we can't find a sqrt we haven't got a point on the
093: // curve - run!
094: //
095: if (beta == null) {
096: throw new RuntimeException(
097: "Invalid point compression");
098: }
099:
100: int bit0 = (beta.toBigInteger().testBit(0) ? 1 : 0);
101:
102: if (bit0 == ytilde) {
103: p = new ECPoint.Fp(this , x, beta, true);
104: } else {
105: p = new ECPoint.Fp(this , x, new ECFieldElement.Fp(
106: this .q, q.subtract(beta.toBigInteger())),
107: true);
108: }
109: break;
110: // uncompressed
111: case 0x04:
112: // hybrid
113: case 0x06:
114: case 0x07:
115: byte[] xEnc = new byte[(encoded.length - 1) / 2];
116: byte[] yEnc = new byte[(encoded.length - 1) / 2];
117:
118: System.arraycopy(encoded, 1, xEnc, 0, xEnc.length);
119: System.arraycopy(encoded, xEnc.length + 1, yEnc, 0,
120: yEnc.length);
121:
122: p = new ECPoint.Fp(this , new ECFieldElement.Fp(this .q,
123: new BigInteger(1, xEnc)),
124: new ECFieldElement.Fp(this .q, new BigInteger(1,
125: yEnc)));
126: break;
127: default:
128: throw new RuntimeException("Invalid point encoding 0x"
129: + Integer.toString(encoded[0], 16));
130: }
131:
132: return p;
133: }
134:
135: public ECPoint getInfinity() {
136: return infinity;
137: }
138:
139: public boolean equals(Object anObject) {
140: if (anObject == this ) {
141: return true;
142: }
143:
144: if (!(anObject instanceof ECCurve.Fp)) {
145: return false;
146: }
147:
148: ECCurve.Fp other = (ECCurve.Fp) anObject;
149:
150: return this .q.equals(other.q) && a.equals(other.a)
151: && b.equals(other.b);
152: }
153:
154: public int hashCode() {
155: return a.hashCode() ^ b.hashCode() ^ q.hashCode();
156: }
157: }
158:
159: /**
160: * Elliptic curves over F2m. The Weierstrass equation is given by
161: * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>.
162: */
163: public static class F2m extends ECCurve {
164: /**
165: * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
166: */
167: private int m; // can't be final - JDK 1.1
168:
169: /**
170: * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
171: * x<sup>k</sup> + 1</code> represents the reduction polynomial
172: * <code>f(z)</code>.<br>
173: * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
174: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
175: * represents the reduction polynomial <code>f(z)</code>.<br>
176: */
177: private int k1; // can't be final - JDK 1.1
178:
179: /**
180: * TPB: Always set to <code>0</code><br>
181: * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
182: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
183: * represents the reduction polynomial <code>f(z)</code>.<br>
184: */
185: private int k2; // can't be final - JDK 1.1
186:
187: /**
188: * TPB: Always set to <code>0</code><br>
189: * PPB: The integer <code>k3</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 k3; // can't be final - JDK 1.1
194:
195: /**
196: * The order of the base point of the curve.
197: */
198: private BigInteger n; // can't be final - JDK 1.1
199:
200: /**
201: * The cofactor of the curve.
202: */
203: private BigInteger h; // can't be final - JDK 1.1
204:
205: /**
206: * The point at infinity on this curve.
207: */
208: private ECPoint.F2m infinity; // can't be final - JDK 1.1
209:
210: /**
211: * The parameter <code>μ</code> of the elliptic curve if this is
212: * a Koblitz curve.
213: */
214: private byte mu = 0;
215:
216: /**
217: * The auxiliary values <code>s<sub>0</sub></code> and
218: * <code>s<sub>1</sub></code> used for partial modular reduction for
219: * Koblitz curves.
220: */
221: private BigInteger[] si = null;
222:
223: /**
224: * Constructor for Trinomial Polynomial Basis (TPB).
225: * @param m The exponent <code>m</code> of
226: * <code>F<sub>2<sup>m</sup></sub></code>.
227: * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
228: * x<sup>k</sup> + 1</code> represents the reduction
229: * polynomial <code>f(z)</code>.
230: * @param a The coefficient <code>a</code> in the Weierstrass equation
231: * for non-supersingular elliptic curves over
232: * <code>F<sub>2<sup>m</sup></sub></code>.
233: * @param b The coefficient <code>b</code> in the Weierstrass equation
234: * for non-supersingular elliptic curves over
235: * <code>F<sub>2<sup>m</sup></sub></code>.
236: */
237: public F2m(int m, int k, BigInteger a, BigInteger b) {
238: this (m, k, 0, 0, a, b, null, null);
239: }
240:
241: /**
242: * Constructor for Trinomial Polynomial Basis (TPB).
243: * @param m The exponent <code>m</code> of
244: * <code>F<sub>2<sup>m</sup></sub></code>.
245: * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
246: * x<sup>k</sup> + 1</code> represents the reduction
247: * polynomial <code>f(z)</code>.
248: * @param a The coefficient <code>a</code> in the Weierstrass equation
249: * for non-supersingular elliptic curves over
250: * <code>F<sub>2<sup>m</sup></sub></code>.
251: * @param b The coefficient <code>b</code> in the Weierstrass equation
252: * for non-supersingular elliptic curves over
253: * <code>F<sub>2<sup>m</sup></sub></code>.
254: * @param n The order of the main subgroup of the elliptic curve.
255: * @param h The cofactor of the elliptic curve, i.e.
256: * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
257: */
258: public F2m(int m, int k, BigInteger a, BigInteger b,
259: BigInteger n, BigInteger h) {
260: this (m, k, 0, 0, a, b, n, h);
261: }
262:
263: /**
264: * Constructor for Pentanomial Polynomial Basis (PPB).
265: * @param m The exponent <code>m</code> of
266: * <code>F<sub>2<sup>m</sup></sub></code>.
267: * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
268: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
269: * represents the reduction polynomial <code>f(z)</code>.
270: * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
271: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
272: * represents the reduction polynomial <code>f(z)</code>.
273: * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
274: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
275: * represents the reduction polynomial <code>f(z)</code>.
276: * @param a The coefficient <code>a</code> in the Weierstrass equation
277: * for non-supersingular elliptic curves over
278: * <code>F<sub>2<sup>m</sup></sub></code>.
279: * @param b The coefficient <code>b</code> in the Weierstrass equation
280: * for non-supersingular elliptic curves over
281: * <code>F<sub>2<sup>m</sup></sub></code>.
282: */
283: public F2m(int m, int k1, int k2, int k3, BigInteger a,
284: BigInteger b) {
285: this (m, k1, k2, k3, a, b, null, null);
286: }
287:
288: /**
289: * Constructor for Pentanomial Polynomial Basis (PPB).
290: * @param m The exponent <code>m</code> of
291: * <code>F<sub>2<sup>m</sup></sub></code>.
292: * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
293: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
294: * represents the reduction polynomial <code>f(z)</code>.
295: * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
296: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
297: * represents the reduction polynomial <code>f(z)</code>.
298: * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
299: * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
300: * represents the reduction polynomial <code>f(z)</code>.
301: * @param a The coefficient <code>a</code> in the Weierstrass equation
302: * for non-supersingular elliptic curves over
303: * <code>F<sub>2<sup>m</sup></sub></code>.
304: * @param b The coefficient <code>b</code> in the Weierstrass equation
305: * for non-supersingular elliptic curves over
306: * <code>F<sub>2<sup>m</sup></sub></code>.
307: * @param n The order of the main subgroup of the elliptic curve.
308: * @param h The cofactor of the elliptic curve, i.e.
309: * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
310: */
311: public F2m(int m, int k1, int k2, int k3, BigInteger a,
312: BigInteger b, BigInteger n, BigInteger h) {
313: this .m = m;
314: this .k1 = k1;
315: this .k2 = k2;
316: this .k3 = k3;
317: this .n = n;
318: this .h = h;
319:
320: if (k1 == 0) {
321: throw new IllegalArgumentException("k1 must be > 0");
322: }
323:
324: if (k2 == 0) {
325: if (k3 != 0) {
326: throw new IllegalArgumentException(
327: "k3 must be 0 if k2 == 0");
328: }
329: } else {
330: if (k2 <= k1) {
331: throw new IllegalArgumentException(
332: "k2 must be > k1");
333: }
334:
335: if (k3 <= k2) {
336: throw new IllegalArgumentException(
337: "k3 must be > k2");
338: }
339: }
340:
341: this .a = fromBigInteger(a);
342: this .b = fromBigInteger(b);
343: this .infinity = new ECPoint.F2m(this , null, null);
344: }
345:
346: public int getFieldSize() {
347: return m;
348: }
349:
350: public ECFieldElement fromBigInteger(BigInteger x) {
351: return new ECFieldElement.F2m(this .m, this .k1, this .k2,
352: this .k3, x);
353: }
354:
355: public ECPoint createPoint(BigInteger x, BigInteger y,
356: boolean withCompression) {
357: return new ECPoint.F2m(this , fromBigInteger(x),
358: fromBigInteger(y), withCompression);
359: }
360:
361: /* (non-Javadoc)
362: * @see org.bouncycastle.math.ec.ECCurve#decodePoint(byte[])
363: */
364: public ECPoint decodePoint(byte[] encoded) {
365: ECPoint p = null;
366:
367: switch (encoded[0]) {
368: // infinity
369: case 0x00:
370: p = getInfinity();
371: break;
372: // compressed
373: case 0x02:
374: case 0x03:
375: byte[] enc = new byte[encoded.length - 1];
376: System.arraycopy(encoded, 1, enc, 0, enc.length);
377: if (encoded[0] == 0x02) {
378: p = decompressPoint(enc, 0);
379: } else {
380: p = decompressPoint(enc, 1);
381: }
382: break;
383: // uncompressed
384: case 0x04:
385: // hybrid
386: case 0x06:
387: case 0x07:
388: byte[] xEnc = new byte[(encoded.length - 1) / 2];
389: byte[] yEnc = new byte[(encoded.length - 1) / 2];
390:
391: System.arraycopy(encoded, 1, xEnc, 0, xEnc.length);
392: System.arraycopy(encoded, xEnc.length + 1, yEnc, 0,
393: yEnc.length);
394:
395: p = new ECPoint.F2m(this , new ECFieldElement.F2m(
396: this .m, this .k1, this .k2, this .k3,
397: new BigInteger(1, xEnc)),
398: new ECFieldElement.F2m(this .m, this .k1,
399: this .k2, this .k3, new BigInteger(1,
400: yEnc)), false);
401: break;
402:
403: default:
404: throw new RuntimeException("Invalid point encoding 0x"
405: + Integer.toString(encoded[0], 16));
406: }
407:
408: return p;
409: }
410:
411: public ECPoint getInfinity() {
412: return infinity;
413: }
414:
415: /**
416: * Returns true if this is a Koblitz curve (ABC curve).
417: * @return true if this is a Koblitz curve (ABC curve), false otherwise
418: */
419: public boolean isKoblitz() {
420: return ((n != null)
421: && (h != null)
422: && ((a.toBigInteger().equals(ECConstants.ZERO)) || (a
423: .toBigInteger().equals(ECConstants.ONE))) && (b
424: .toBigInteger().equals(ECConstants.ONE)));
425: }
426:
427: /**
428: * Returns the parameter <code>μ</code> of the elliptic curve.
429: * @return <code>μ</code> of the elliptic curve.
430: * @throws IllegalArgumentException if the given ECCurve is not a
431: * Koblitz curve.
432: */
433: synchronized byte getMu() {
434: if (mu == 0) {
435: mu = Tnaf.getMu(this );
436: }
437: return mu;
438: }
439:
440: /**
441: * @return the auxiliary values <code>s<sub>0</sub></code> and
442: * <code>s<sub>1</sub></code> used for partial modular reduction for
443: * Koblitz curves.
444: */
445: synchronized BigInteger[] getSi() {
446: if (si == null) {
447: si = Tnaf.getSi(this );
448: }
449: return si;
450: }
451:
452: /**
453: * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2).
454: *
455: * @param xEnc
456: * The encoding of field element xp.
457: * @param ypBit
458: * ~yp, an indication bit for the decompression of yp.
459: * @return the decompressed point.
460: */
461: private ECPoint decompressPoint(byte[] xEnc, int ypBit) {
462: ECFieldElement xp = new ECFieldElement.F2m(this .m, this .k1,
463: this .k2, this .k3, new BigInteger(1, xEnc));
464: ECFieldElement yp = null;
465: if (xp.toBigInteger().equals(ECConstants.ZERO)) {
466: yp = (ECFieldElement.F2m) b;
467: for (int i = 0; i < m - 1; i++) {
468: yp = yp.square();
469: }
470: } else {
471: ECFieldElement beta = xp.add(a).add(
472: b.multiply(xp.square().invert()));
473: ECFieldElement z = solveQuadradicEquation(beta);
474: if (z == null) {
475: throw new RuntimeException(
476: "Invalid point compression");
477: }
478: int zBit = 0;
479: if (z.toBigInteger().testBit(0)) {
480: zBit = 1;
481: }
482: if (zBit != ypBit) {
483: z = z.add(new ECFieldElement.F2m(this .m, this .k1,
484: this .k2, this .k3, ECConstants.ONE));
485: }
486: yp = xp.multiply(z);
487: }
488:
489: return new ECPoint.F2m(this , xp, yp);
490: }
491:
492: /**
493: * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
494: * D.1.6) The other solution is <code>z + 1</code>.
495: *
496: * @param beta
497: * The value to solve the qradratic equation for.
498: * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
499: * <code>null</code> if no solution exists.
500: */
501: private ECFieldElement solveQuadradicEquation(
502: ECFieldElement beta) {
503: ECFieldElement zeroElement = new ECFieldElement.F2m(this .m,
504: this .k1, this .k2, this .k3, ECConstants.ZERO);
505:
506: if (beta.toBigInteger().equals(ECConstants.ZERO)) {
507: return zeroElement;
508: }
509:
510: ECFieldElement z = null;
511: ECFieldElement gamma = zeroElement;
512:
513: Random rand = new Random();
514: do {
515: ECFieldElement t = new ECFieldElement.F2m(this .m,
516: this .k1, this .k2, this .k3, new BigInteger(m,
517: rand));
518: z = zeroElement;
519: ECFieldElement w = beta;
520: for (int i = 1; i <= m - 1; i++) {
521: ECFieldElement w2 = w.square();
522: z = z.square().add(w2.multiply(t));
523: w = w2.add(beta);
524: }
525: if (!w.toBigInteger().equals(ECConstants.ZERO)) {
526: return null;
527: }
528: gamma = z.square().add(z);
529: } while (gamma.toBigInteger().equals(ECConstants.ZERO));
530:
531: return z;
532: }
533:
534: public boolean equals(Object anObject) {
535: if (anObject == this ) {
536: return true;
537: }
538:
539: if (!(anObject instanceof ECCurve.F2m)) {
540: return false;
541: }
542:
543: ECCurve.F2m other = (ECCurve.F2m) anObject;
544:
545: return (this .m == other.m) && (this .k1 == other.k1)
546: && (this .k2 == other.k2) && (this .k3 == other.k3)
547: && a.equals(other.a) && b.equals(other.b);
548: }
549:
550: public int hashCode() {
551: return this .a.hashCode() ^ this .b.hashCode() ^ m ^ k1 ^ k2
552: ^ k3;
553: }
554:
555: public int getM() {
556: return m;
557: }
558:
559: /**
560: * Return true if curve uses a Trinomial basis.
561: *
562: * @return true if curve Trinomial, false otherwise.
563: */
564: public boolean isTrinomial() {
565: return k2 == 0 && k3 == 0;
566: }
567:
568: public int getK1() {
569: return k1;
570: }
571:
572: public int getK2() {
573: return k2;
574: }
575:
576: public int getK3() {
577: return k3;
578: }
579:
580: public BigInteger getN() {
581: return n;
582: }
583:
584: public BigInteger getH() {
585: return h;
586: }
587: }
588: }
|