001: package org.bouncycastle.math.ec;
002:
003: import java.math.BigInteger;
004:
005: import org.bouncycastle.asn1.x9.X9IntegerConverter;
006:
007: /**
008: * base class for points on elliptic curves.
009: */
010: public abstract class ECPoint {
011: ECCurve curve;
012: ECFieldElement x;
013: ECFieldElement y;
014:
015: protected boolean withCompression;
016:
017: protected ECMultiplier multiplier = null;
018:
019: protected PreCompInfo preCompInfo = null;
020:
021: private static X9IntegerConverter converter = new X9IntegerConverter();
022:
023: protected ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y) {
024: this .curve = curve;
025: this .x = x;
026: this .y = y;
027: }
028:
029: public ECCurve getCurve() {
030: return curve;
031: }
032:
033: public ECFieldElement getX() {
034: return x;
035: }
036:
037: public ECFieldElement getY() {
038: return y;
039: }
040:
041: public boolean isInfinity() {
042: return x == null && y == null;
043: }
044:
045: public boolean isCompressed() {
046: return withCompression;
047: }
048:
049: public boolean equals(Object other) {
050: if (other == this ) {
051: return true;
052: }
053:
054: if (!(other instanceof ECPoint)) {
055: return false;
056: }
057:
058: ECPoint o = (ECPoint) other;
059:
060: if (this .isInfinity()) {
061: return o.isInfinity();
062: }
063:
064: return x.equals(o.x) && y.equals(o.y);
065: }
066:
067: public int hashCode() {
068: if (this .isInfinity()) {
069: return 0;
070: }
071:
072: return x.hashCode() ^ y.hashCode();
073: }
074:
075: // /**
076: // * Mainly for testing. Explicitly set the <code>ECMultiplier</code>.
077: // * @param multiplier The <code>ECMultiplier</code> to be used to multiply
078: // * this <code>ECPoint</code>.
079: // */
080: // public void setECMultiplier(ECMultiplier multiplier)
081: // {
082: // this.multiplier = multiplier;
083: // }
084:
085: /**
086: * Sets the <code>PreCompInfo</code>. Used by <code>ECMultiplier</code>s
087: * to save the precomputation for this <code>ECPoint</code> to store the
088: * precomputation result for use by subsequent multiplication.
089: * @param preCompInfo The values precomputed by the
090: * <code>ECMultiplier</code>.
091: */
092: void setPreCompInfo(PreCompInfo preCompInfo) {
093: this .preCompInfo = preCompInfo;
094: }
095:
096: public abstract byte[] getEncoded();
097:
098: public abstract ECPoint add(ECPoint b);
099:
100: public abstract ECPoint subtract(ECPoint b);
101:
102: public abstract ECPoint negate();
103:
104: public abstract ECPoint twice();
105:
106: /**
107: * Sets the default <code>ECMultiplier</code>, unless already set.
108: */
109: synchronized void assertECMultiplier() {
110: if (this .multiplier == null) {
111: this .multiplier = new FpNafMultiplier();
112: }
113: }
114:
115: /**
116: * Multiplies this <code>ECPoint</code> by the given number.
117: * @param k The multiplicator.
118: * @return <code>k * this</code>.
119: */
120: public ECPoint multiply(BigInteger k) {
121: if (this .isInfinity()) {
122: return this ;
123: }
124:
125: if (k.signum() == 0) {
126: return this .curve.getInfinity();
127: }
128:
129: assertECMultiplier();
130: return this .multiplier.multiply(this , k, preCompInfo);
131: }
132:
133: /**
134: * Elliptic curve points over Fp
135: */
136: public static class Fp extends ECPoint {
137:
138: /**
139: * Create a point which encodes with point compression.
140: *
141: * @param curve the curve to use
142: * @param x affine x co-ordinate
143: * @param y affine y co-ordinate
144: */
145: public Fp(ECCurve curve, ECFieldElement x, ECFieldElement y) {
146: this (curve, x, y, false);
147: }
148:
149: /**
150: * Create a point that encodes with or without point compresion.
151: *
152: * @param curve the curve to use
153: * @param x affine x co-ordinate
154: * @param y affine y co-ordinate
155: * @param withCompression if true encode with point compression
156: */
157: public Fp(ECCurve curve, ECFieldElement x, ECFieldElement y,
158: boolean withCompression) {
159: super (curve, x, y);
160:
161: if ((x != null && y == null) || (x == null && y != null)) {
162: throw new IllegalArgumentException(
163: "Exactly one of the field elements is null");
164: }
165:
166: this .withCompression = withCompression;
167: }
168:
169: /**
170: * return the field element encoded with point compression. (S 4.3.6)
171: */
172: public byte[] getEncoded() {
173: if (this .isInfinity()) {
174: return new byte[1];
175: }
176:
177: int qLength = converter.getByteLength(x);
178:
179: if (withCompression) {
180: byte PC;
181:
182: if (this .getY().toBigInteger().testBit(0)) {
183: PC = 0x03;
184: } else {
185: PC = 0x02;
186: }
187:
188: byte[] X = converter.integerToBytes(this .getX()
189: .toBigInteger(), qLength);
190: byte[] PO = new byte[X.length + 1];
191:
192: PO[0] = PC;
193: System.arraycopy(X, 0, PO, 1, X.length);
194:
195: return PO;
196: } else {
197: byte[] X = converter.integerToBytes(this .getX()
198: .toBigInteger(), qLength);
199: byte[] Y = converter.integerToBytes(this .getY()
200: .toBigInteger(), qLength);
201: byte[] PO = new byte[X.length + Y.length + 1];
202:
203: PO[0] = 0x04;
204: System.arraycopy(X, 0, PO, 1, X.length);
205: System.arraycopy(Y, 0, PO, X.length + 1, Y.length);
206:
207: return PO;
208: }
209: }
210:
211: // B.3 pg 62
212: public ECPoint add(ECPoint b) {
213: if (this .isInfinity()) {
214: return b;
215: }
216:
217: if (b.isInfinity()) {
218: return this ;
219: }
220:
221: // Check if b = this or b = -this
222: if (this .x.equals(b.x)) {
223: if (this .y.equals(b.y)) {
224: // this = b, i.e. this must be doubled
225: return this .twice();
226: }
227:
228: // this = -b, i.e. the result is the point at infinity
229: return this .curve.getInfinity();
230: }
231:
232: ECFieldElement gamma = b.y.subtract(this .y).divide(
233: b.x.subtract(this .x));
234:
235: ECFieldElement x3 = gamma.square().subtract(this .x)
236: .subtract(b.x);
237: ECFieldElement y3 = gamma.multiply(this .x.subtract(x3))
238: .subtract(this .y);
239:
240: return new ECPoint.Fp(curve, x3, y3);
241: }
242:
243: // B.3 pg 62
244: public ECPoint twice() {
245: if (this .isInfinity()) {
246: // Twice identity element (point at infinity) is identity
247: return this ;
248: }
249:
250: if (this .y.toBigInteger().signum() == 0) {
251: // if y1 == 0, then (x1, y1) == (x1, -y1)
252: // and hence this = -this and thus 2(x1, y1) == infinity
253: return this .curve.getInfinity();
254: }
255:
256: ECFieldElement TWO = this .curve.fromBigInteger(BigInteger
257: .valueOf(2));
258: ECFieldElement THREE = this .curve.fromBigInteger(BigInteger
259: .valueOf(3));
260: ECFieldElement gamma = this .x.square().multiply(THREE).add(
261: curve.a).divide(y.multiply(TWO));
262:
263: ECFieldElement x3 = gamma.square().subtract(
264: this .x.multiply(TWO));
265: ECFieldElement y3 = gamma.multiply(this .x.subtract(x3))
266: .subtract(this .y);
267:
268: return new ECPoint.Fp(curve, x3, y3, this .withCompression);
269: }
270:
271: // D.3.2 pg 102 (see Note:)
272: public ECPoint subtract(ECPoint b) {
273: if (b.isInfinity()) {
274: return this ;
275: }
276:
277: // Add -b
278: return add(b.negate());
279: }
280:
281: public ECPoint negate() {
282: return new ECPoint.Fp(curve, this .x, this .y.negate(),
283: this .withCompression);
284: }
285:
286: // TODO Uncomment this to enable WNAF algorithm for Fp point multiplication
287: // /**
288: // * Sets the default <code>ECMultiplier</code>, unless already set.
289: // */
290: // synchronized void assertECMultiplier()
291: // {
292: // if (this.multiplier == null)
293: // {
294: // this.multiplier = new WNafMultiplier();
295: // }
296: // }
297: }
298:
299: /**
300: * Elliptic curve points over F2m
301: */
302: public static class F2m extends ECPoint {
303: /**
304: * @param curve base curve
305: * @param x x point
306: * @param y y point
307: */
308: public F2m(ECCurve curve, ECFieldElement x, ECFieldElement y) {
309: this (curve, x, y, false);
310: }
311:
312: /**
313: * @param curve base curve
314: * @param x x point
315: * @param y y point
316: * @param withCompression true if encode with point compression.
317: */
318: public F2m(ECCurve curve, ECFieldElement x, ECFieldElement y,
319: boolean withCompression) {
320: super (curve, x, y);
321:
322: if ((x != null && y == null) || (x == null && y != null)) {
323: throw new IllegalArgumentException(
324: "Exactly one of the field elements is null");
325: }
326:
327: if (x != null) {
328: // Check if x and y are elements of the same field
329: ECFieldElement.F2m.checkFieldElements(this .x, this .y);
330:
331: // Check if x and a are elements of the same field
332: if (curve != null) {
333: ECFieldElement.F2m.checkFieldElements(this .x,
334: this .curve.getA());
335: }
336: }
337:
338: this .withCompression = withCompression;
339: }
340:
341: /**
342: * @deprecated use ECCurve.getInfinity()
343: * Constructor for point at infinity
344: */
345: public F2m(ECCurve curve) {
346: super (curve, null, null);
347: }
348:
349: /* (non-Javadoc)
350: * @see org.bouncycastle.math.ec.ECPoint#getEncoded()
351: */
352: public byte[] getEncoded() {
353: if (this .isInfinity()) {
354: return new byte[1];
355: }
356:
357: int byteCount = converter.getByteLength(this .x);
358: byte[] X = converter.integerToBytes(this .getX()
359: .toBigInteger(), byteCount);
360: byte[] PO;
361:
362: if (withCompression) {
363: // See X9.62 4.3.6 and 4.2.2
364: PO = new byte[byteCount + 1];
365:
366: PO[0] = 0x02;
367: // X9.62 4.2.2 and 4.3.6:
368: // if x = 0 then ypTilde := 0, else ypTilde is the rightmost
369: // bit of y * x^(-1)
370: // if ypTilde = 0, then PC := 02, else PC := 03
371: // Note: PC === PO[0]
372: if (!(this .getX().toBigInteger()
373: .equals(ECConstants.ZERO))) {
374: if (this .getY().multiply(this .getX().invert())
375: .toBigInteger().testBit(0)) {
376: // ypTilde = 1, hence PC = 03
377: PO[0] = 0x03;
378: }
379: }
380:
381: System.arraycopy(X, 0, PO, 1, byteCount);
382: } else {
383: byte[] Y = converter.integerToBytes(this .getY()
384: .toBigInteger(), byteCount);
385:
386: PO = new byte[byteCount + byteCount + 1];
387:
388: PO[0] = 0x04;
389: System.arraycopy(X, 0, PO, 1, byteCount);
390: System.arraycopy(Y, 0, PO, byteCount + 1, byteCount);
391: }
392:
393: return PO;
394: }
395:
396: /**
397: * Check, if two <code>ECPoint</code>s can be added or subtracted.
398: * @param a The first <code>ECPoint</code> to check.
399: * @param b The second <code>ECPoint</code> to check.
400: * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
401: * cannot be added.
402: */
403: private static void checkPoints(ECPoint a, ECPoint b) {
404: // Check, if points are on the same curve
405: if (!(a.curve.equals(b.curve))) {
406: throw new IllegalArgumentException(
407: "Only points on the same "
408: + "curve can be added or subtracted");
409: }
410:
411: // ECFieldElement.F2m.checkFieldElements(a.x, b.x);
412: }
413:
414: /* (non-Javadoc)
415: * @see org.bouncycastle.math.ec.ECPoint#add(org.bouncycastle.math.ec.ECPoint)
416: */
417: public ECPoint add(ECPoint b) {
418: checkPoints(this , b);
419: return addSimple((ECPoint.F2m) b);
420: }
421:
422: /**
423: * Adds another <code>ECPoints.F2m</code> to <code>this</code> without
424: * checking if both points are on the same curve. Used by multiplication
425: * algorithms, because there all points are a multiple of the same point
426: * and hence the checks can be omitted.
427: * @param b The other <code>ECPoints.F2m</code> to add to
428: * <code>this</code>.
429: * @return <code>this + b</code>
430: */
431: public ECPoint.F2m addSimple(ECPoint.F2m b) {
432: ECPoint.F2m other = b;
433: if (this .isInfinity()) {
434: return other;
435: }
436:
437: if (other.isInfinity()) {
438: return this ;
439: }
440:
441: ECFieldElement.F2m x2 = (ECFieldElement.F2m) other.getX();
442: ECFieldElement.F2m y2 = (ECFieldElement.F2m) other.getY();
443:
444: // Check if other = this or other = -this
445: if (this .x.equals(x2)) {
446: if (this .y.equals(y2)) {
447: // this = other, i.e. this must be doubled
448: return (ECPoint.F2m) this .twice();
449: }
450:
451: // this = -other, i.e. the result is the point at infinity
452: return (ECPoint.F2m) this .curve.getInfinity();
453: }
454:
455: ECFieldElement.F2m lambda = (ECFieldElement.F2m) (this .y
456: .add(y2)).divide(this .x.add(x2));
457:
458: ECFieldElement.F2m x3 = (ECFieldElement.F2m) lambda
459: .square().add(lambda).add(this .x).add(x2).add(
460: this .curve.getA());
461:
462: ECFieldElement.F2m y3 = (ECFieldElement.F2m) lambda
463: .multiply(this .x.add(x3)).add(x3).add(this .y);
464:
465: return new ECPoint.F2m(curve, x3, y3, withCompression);
466: }
467:
468: /* (non-Javadoc)
469: * @see org.bouncycastle.math.ec.ECPoint#subtract(org.bouncycastle.math.ec.ECPoint)
470: */
471: public ECPoint subtract(ECPoint b) {
472: checkPoints(this , b);
473: return subtractSimple((ECPoint.F2m) b);
474: }
475:
476: /**
477: * Subtracts another <code>ECPoints.F2m</code> from <code>this</code>
478: * without checking if both points are on the same curve. Used by
479: * multiplication algorithms, because there all points are a multiple
480: * of the same point and hence the checks can be omitted.
481: * @param b The other <code>ECPoints.F2m</code> to subtract from
482: * <code>this</code>.
483: * @return <code>this - b</code>
484: */
485: public ECPoint.F2m subtractSimple(ECPoint.F2m b) {
486: if (b.isInfinity()) {
487: return this ;
488: }
489:
490: // Add -b
491: return addSimple((ECPoint.F2m) b.negate());
492: }
493:
494: /* (non-Javadoc)
495: * @see org.bouncycastle.math.ec.ECPoint#twice()
496: */
497: public ECPoint twice() {
498: if (this .isInfinity()) {
499: // Twice identity element (point at infinity) is identity
500: return this ;
501: }
502:
503: if (this .x.toBigInteger().signum() == 0) {
504: // if x1 == 0, then (x1, y1) == (x1, x1 + y1)
505: // and hence this = -this and thus 2(x1, y1) == infinity
506: return this .curve.getInfinity();
507: }
508:
509: ECFieldElement.F2m lambda = (ECFieldElement.F2m) this .x
510: .add(this .y.divide(this .x));
511:
512: ECFieldElement.F2m x3 = (ECFieldElement.F2m) lambda
513: .square().add(lambda).add(this .curve.getA());
514:
515: ECFieldElement ONE = this .curve
516: .fromBigInteger(ECConstants.ONE);
517: ECFieldElement.F2m y3 = (ECFieldElement.F2m) this .x
518: .square().add(x3.multiply(lambda.add(ONE)));
519:
520: return new ECPoint.F2m(this .curve, x3, y3, withCompression);
521: }
522:
523: public ECPoint negate() {
524: return new ECPoint.F2m(curve, this .getX(), this .getY().add(
525: this .getX()), withCompression);
526: }
527:
528: // TODO Uncomment this to enable WNAF/WTNAF F2m point multiplication
529: // /**
530: // * Sets the appropriate <code>ECMultiplier</code>, unless already set.
531: // */
532: // synchronized void assertECMultiplier()
533: // {
534: // if (this.multiplier == null)
535: // {
536: // if (((ECCurve.F2m)(this.curve)).isKoblitz())
537: // {
538: // this.multiplier = new WTauNafMultiplier();
539: // }
540: // else
541: // {
542: // this.multiplier = new WNafMultiplier();
543: // }
544: // }
545: // }
546: }
547: }
|