001: package org.bouncycastle.math.ec.test;
002:
003: import java.math.BigInteger;
004: import java.security.SecureRandom;
005: import java.util.Enumeration;
006:
007: import junit.framework.Test;
008: import junit.framework.TestCase;
009: import junit.framework.TestSuite;
010:
011: import org.bouncycastle.asn1.sec.SECNamedCurves;
012: import org.bouncycastle.asn1.x9.X9ECParameters;
013: import org.bouncycastle.math.ec.ECCurve;
014: import org.bouncycastle.math.ec.ECFieldElement;
015: import org.bouncycastle.math.ec.ECPoint;
016:
017: /**
018: * Test class for {@link org.bouncycastle.math.ec.ECPoint ECPoint}. All
019: * literature values are taken from "Guide to elliptic curve cryptography",
020: * Darrel Hankerson, Alfred J. Menezes, Scott Vanstone, 2004, Springer-Verlag
021: * New York, Inc.
022: */
023: public class ECPointTest extends TestCase {
024: /**
025: * Random source used to generate random points
026: */
027: private SecureRandom secRand = new SecureRandom();
028:
029: private ECPointTest.Fp fp = null;
030:
031: private ECPointTest.F2m f2m = null;
032:
033: /**
034: * Nested class containing sample literature values for <code>Fp</code>.
035: */
036: public static class Fp {
037: private final BigInteger q = new BigInteger("29");
038:
039: private final BigInteger a = new BigInteger("4");
040:
041: private final BigInteger b = new BigInteger("20");
042:
043: private final ECCurve.Fp curve = new ECCurve.Fp(q, a, b);
044:
045: private final ECPoint.Fp infinity = (ECPoint.Fp) curve
046: .getInfinity();
047:
048: private final int[] pointSource = { 5, 22, 16, 27, 13, 6, 14, 6 };
049:
050: private ECPoint.Fp[] p = new ECPoint.Fp[pointSource.length / 2];
051:
052: /**
053: * Creates the points on the curve with literature values.
054: */
055: private void createPoints() {
056: for (int i = 0; i < pointSource.length / 2; i++) {
057: ECFieldElement.Fp x = new ECFieldElement.Fp(q,
058: new BigInteger(Integer
059: .toString(pointSource[2 * i])));
060: ECFieldElement.Fp y = new ECFieldElement.Fp(q,
061: new BigInteger(Integer
062: .toString(pointSource[2 * i + 1])));
063: p[i] = new ECPoint.Fp(curve, x, y);
064: }
065: }
066: }
067:
068: /**
069: * Nested class containing sample literature values for <code>F2m</code>.
070: */
071: public static class F2m {
072: // Irreducible polynomial for TPB z^4 + z + 1
073: private final int m = 4;
074:
075: private final int k1 = 1;
076:
077: // a = z^3
078: private final ECFieldElement.F2m aTpb = new ECFieldElement.F2m(
079: m, k1, new BigInteger("1000", 2));
080:
081: // b = z^3 + 1
082: private final ECFieldElement.F2m bTpb = new ECFieldElement.F2m(
083: m, k1, new BigInteger("1001", 2));
084:
085: private final ECCurve.F2m curve = new ECCurve.F2m(m, k1, aTpb
086: .toBigInteger(), bTpb.toBigInteger());
087:
088: private final ECPoint.F2m infinity = (ECPoint.F2m) curve
089: .getInfinity();
090:
091: private final String[] pointSource = { "0010", "1111", "1100",
092: "1100", "0001", "0001", "1011", "0010" };
093:
094: private ECPoint.F2m[] p = new ECPoint.F2m[pointSource.length / 2];
095:
096: /**
097: * Creates the points on the curve with literature values.
098: */
099: private void createPoints() {
100: for (int i = 0; i < pointSource.length / 2; i++) {
101: ECFieldElement.F2m x = new ECFieldElement.F2m(m, k1,
102: new BigInteger(pointSource[2 * i], 2));
103: ECFieldElement.F2m y = new ECFieldElement.F2m(m, k1,
104: new BigInteger(pointSource[2 * i + 1], 2));
105: p[i] = new ECPoint.F2m(curve, x, y);
106: }
107: }
108: }
109:
110: public void setUp() {
111: fp = new ECPointTest.Fp();
112: fp.createPoints();
113:
114: f2m = new ECPointTest.F2m();
115: f2m.createPoints();
116: }
117:
118: /**
119: * Tests, if inconsistent points can be created, i.e. points with exactly
120: * one null coordinate (not permitted).
121: */
122: public void testPointCreationConsistency() {
123: try {
124: ECPoint.Fp bad = new ECPoint.Fp(fp.curve,
125: new ECFieldElement.Fp(fp.q, new BigInteger("12")),
126: null);
127: fail();
128: } catch (IllegalArgumentException expected) {
129: }
130:
131: try {
132: ECPoint.Fp bad = new ECPoint.Fp(fp.curve, null,
133: new ECFieldElement.Fp(fp.q, new BigInteger("12")));
134: fail();
135: } catch (IllegalArgumentException expected) {
136: }
137:
138: try {
139: ECPoint.F2m bad = new ECPoint.F2m(f2m.curve,
140: new ECFieldElement.F2m(f2m.m, f2m.k1,
141: new BigInteger("1011")), null);
142: fail();
143: } catch (IllegalArgumentException expected) {
144: }
145:
146: try {
147: ECPoint.F2m bad = new ECPoint.F2m(f2m.curve, null,
148: new ECFieldElement.F2m(f2m.m, f2m.k1,
149: new BigInteger("1011")));
150: fail();
151: } catch (IllegalArgumentException expected) {
152: }
153: }
154:
155: /**
156: * Tests <code>ECPoint.add()</code> against literature values.
157: *
158: * @param p
159: * The array of literature values.
160: * @param infinity
161: * The point at infinity on the respective curve.
162: */
163: private void implTestAdd(ECPoint[] p, ECPoint infinity) {
164: assertEquals("p0 plus p1 does not equal p2", p[2], p[0]
165: .add(p[1]));
166: assertEquals("p1 plus p0 does not equal p2", p[2], p[1]
167: .add(p[0]));
168: for (int i = 0; i < p.length; i++) {
169: assertEquals("Adding infinity failed", p[i], p[i]
170: .add(infinity));
171: assertEquals("Adding to infinity failed", p[i], infinity
172: .add(p[i]));
173: }
174: }
175:
176: /**
177: * Calls <code>implTestAdd()</code> for <code>Fp</code> and
178: * <code>F2m</code>.
179: */
180: public void testAdd() {
181: implTestAdd(fp.p, fp.infinity);
182: implTestAdd(f2m.p, f2m.infinity);
183: }
184:
185: /**
186: * Tests <code>ECPoint.twice()</code> against literature values.
187: *
188: * @param p
189: * The array of literature values.
190: */
191: private void implTestTwice(ECPoint[] p) {
192: assertEquals("Twice incorrect", p[3], p[0].twice());
193: assertEquals("Add same point incorrect", p[3], p[0].add(p[0]));
194: }
195:
196: /**
197: * Calls <code>implTestTwice()</code> for <code>Fp</code> and
198: * <code>F2m</code>.
199: */
200: public void testTwice() {
201: implTestTwice(fp.p);
202: implTestTwice(f2m.p);
203: }
204:
205: /**
206: * Goes through all points on an elliptic curve and checks, if adding a
207: * point <code>k</code>-times is the same as multiplying the point by
208: * <code>k</code>, for all <code>k</code>. Should be called for points
209: * on very small elliptic curves only.
210: *
211: * @param p
212: * The base point on the elliptic curve.
213: * @param infinity
214: * The point at infinity on the elliptic curve.
215: */
216: private void implTestAllPoints(ECPoint p, ECPoint infinity) {
217: ECPoint adder = infinity;
218: ECPoint multiplier = infinity;
219: int i = 1;
220: do {
221: adder = adder.add(p);
222: multiplier = p
223: .multiply(new BigInteger(Integer.toString(i)));
224: assertEquals(
225: "Results of add() and multiply() are inconsistent "
226: + i, adder, multiplier);
227: i++;
228: } while (!(adder.equals(infinity)));
229: }
230:
231: /**
232: * Calls <code>implTestAllPoints()</code> for the small literature curves,
233: * both for <code>Fp</code> and <code>F2m</code>.
234: */
235: public void testAllPoints() {
236: for (int i = 0; i < fp.p.length; i++) {
237: implTestAllPoints(fp.p[0], fp.infinity);
238: }
239:
240: for (int i = 0; i < f2m.p.length; i++) {
241: implTestAllPoints(f2m.p[0], f2m.infinity);
242: }
243: }
244:
245: /**
246: * Simple shift-and-add multiplication. Serves as reference implementation
247: * to verify (possibly faster) implementations in
248: * {@link org.bouncycastle.math.ec.ECPoint ECPoint}.
249: *
250: * @param p
251: * The point to multiply.
252: * @param k
253: * The multiplier.
254: * @return The result of the point multiplication <code>kP</code>.
255: */
256: private ECPoint multiply(ECPoint p, BigInteger k) {
257: ECPoint q = p.getCurve().getInfinity();
258: int t = k.bitLength();
259: for (int i = 0; i < t; i++) {
260: if (k.testBit(i)) {
261: q = q.add(p);
262: }
263: p = p.twice();
264: }
265: return q;
266: }
267:
268: /**
269: * Checks, if the point multiplication algorithm of the given point yields
270: * the same result as point multiplication done by the reference
271: * implementation given in <code>multiply()</code>. This method chooses a
272: * random number by which the given point <code>p</code> is multiplied.
273: *
274: * @param p
275: * The point to be multiplied.
276: * @param numBits
277: * The bitlength of the random number by which <code>p</code>
278: * is multiplied.
279: */
280: private void implTestMultiply(ECPoint p, int numBits) {
281: BigInteger k = new BigInteger(numBits, secRand);
282: ECPoint ref = multiply(p, k);
283: ECPoint q = p.multiply(k);
284: assertEquals("ECPoint.multiply is incorrect", ref, q);
285: }
286:
287: /**
288: * Checks, if the point multiplication algorithm of the given point yields
289: * the same result as point multiplication done by the reference
290: * implementation given in <code>multiply()</code>. This method tests
291: * multiplication of <code>p</code> by every number of bitlength
292: * <code>numBits</code> or less.
293: *
294: * @param p
295: * The point to be multiplied.
296: * @param numBits
297: * Try every multiplier up to this bitlength
298: */
299: private void implTestMultiplyAll(ECPoint p, int numBits) {
300: BigInteger bound = BigInteger.valueOf(2).pow(numBits);
301: BigInteger k = BigInteger.ZERO;
302:
303: do {
304: ECPoint ref = multiply(p, k);
305: ECPoint q = p.multiply(k);
306: assertEquals("ECPoint.multiply is incorrect", ref, q);
307: k = k.add(BigInteger.ONE);
308: } while (k.compareTo(bound) < 0);
309: }
310:
311: /**
312: * Tests <code>ECPoint.add()</code> and <code>ECPoint.subtract()</code>
313: * for the given point and the given point at infinity.
314: *
315: * @param p
316: * The point on which the tests are performed.
317: * @param infinity
318: * The point at infinity on the same curve as <code>p</code>.
319: */
320: private void implTestAddSubtract(ECPoint p, ECPoint infinity) {
321: assertEquals("Twice and Add inconsistent", p.twice(), p.add(p));
322: assertEquals("Twice p - p is not p", p, p.twice().subtract(p));
323: assertEquals("p - p is not infinity", infinity, p.subtract(p));
324: assertEquals("p plus infinity is not p", p, p.add(infinity));
325: assertEquals("infinity plus p is not p", p, infinity.add(p));
326: assertEquals("infinity plus infinity is not infinity ",
327: infinity, infinity.add(infinity));
328: }
329:
330: /**
331: * Calls <code>implTestAddSubtract()</code> for literature values, both
332: * for <code>Fp</code> and <code>F2m</code>.
333: */
334: public void testAddSubtractMultiplySimple() {
335: for (int iFp = 0; iFp < fp.pointSource.length / 2; iFp++) {
336: implTestAddSubtract(fp.p[iFp], fp.infinity);
337:
338: // Could be any numBits, 6 is chosen at will
339: implTestMultiplyAll(fp.p[iFp], 6);
340: implTestMultiplyAll(fp.infinity, 6);
341: }
342:
343: for (int iF2m = 0; iF2m < f2m.pointSource.length / 2; iF2m++) {
344: implTestAddSubtract(f2m.p[iF2m], f2m.infinity);
345:
346: // Could be any numBits, 6 is chosen at will
347: implTestMultiplyAll(f2m.p[iF2m], 6);
348: implTestMultiplyAll(f2m.infinity, 6);
349: }
350: }
351:
352: /**
353: * Test encoding with and without point compression.
354: *
355: * @param p
356: * The point to be encoded and decoded.
357: */
358: private void implTestEncoding(ECPoint p) {
359: // Not Point Compression
360: ECPoint unCompP;
361:
362: // Point compression
363: ECPoint compP;
364:
365: if (p instanceof ECPoint.Fp) {
366: unCompP = new ECPoint.Fp(p.getCurve(), p.getX(), p.getY(),
367: false);
368: compP = new ECPoint.Fp(p.getCurve(), p.getX(), p.getY(),
369: true);
370: } else {
371: unCompP = new ECPoint.F2m(p.getCurve(), p.getX(), p.getY(),
372: false);
373: compP = new ECPoint.F2m(p.getCurve(), p.getX(), p.getY(),
374: true);
375: }
376:
377: byte[] unCompBarr = unCompP.getEncoded();
378: ECPoint decUnComp = p.getCurve().decodePoint(unCompBarr);
379: assertEquals("Error decoding uncompressed point", p, decUnComp);
380:
381: byte[] compBarr = compP.getEncoded();
382: ECPoint decComp = p.getCurve().decodePoint(compBarr);
383: assertEquals("Error decoding compressed point", p, decComp);
384: }
385:
386: /**
387: * Calls <code>implTestAddSubtract()</code>,
388: * <code>implTestMultiply</code> and <code>implTestEncoding</code> for
389: * the standard elliptic curves as given in <code>SECNamedCurves</code>.
390: */
391: public void testAddSubtractMultiplyTwiceEncoding() {
392: Enumeration curveEnum = SECNamedCurves.getNames();
393: while (curveEnum.hasMoreElements()) {
394: String name = (String) curveEnum.nextElement();
395: X9ECParameters x9ECParameters = SECNamedCurves
396: .getByName(name);
397:
398: BigInteger n = x9ECParameters.getN();
399:
400: // The generator is multiplied by random b to get random q
401: BigInteger b = new BigInteger(n.bitLength(), secRand);
402: ECPoint g = x9ECParameters.getG();
403: ECPoint q = g.multiply(b);
404:
405: // Get point at infinity on the curve
406: ECPoint infinity = x9ECParameters.getCurve().getInfinity();
407:
408: implTestAddSubtract(q, infinity);
409: implTestMultiply(q, n.bitLength());
410: implTestMultiply(infinity, n.bitLength());
411: implTestEncoding(q);
412: }
413: }
414:
415: public static Test suite() {
416: return new TestSuite(ECPointTest.class);
417: }
418: }
|