diff options
Diffstat (limited to 'core/src/test/java/org/spongycastle/math')
6 files changed, 1282 insertions, 0 deletions
diff --git a/core/src/test/java/org/spongycastle/math/ec/test/AllTests.java b/core/src/test/java/org/spongycastle/math/ec/test/AllTests.java new file mode 100644 index 00000000..5388c743 --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/AllTests.java @@ -0,0 +1,40 @@ +package org.spongycastle.math.ec.test; + +import java.util.ArrayList; +import java.util.Enumeration; +import java.util.List; + +import junit.framework.Test; +import junit.framework.TestSuite; + +public class AllTests +{ + public static void main (String[] args) + throws Exception + { + junit.textui.TestRunner.run(suite()); + } + + public static Test suite() + throws Exception + { + TestSuite suite = new TestSuite("EC Math tests"); + + suite.addTest(ECAlgorithmsTest.suite()); + suite.addTest(ECPointTest.suite()); + + return suite; + } + + static List enumToList(Enumeration en) + { + List rv = new ArrayList(); + + while (en.hasMoreElements()) + { + rv.add(en.nextElement()); + } + + return rv; + } +} diff --git a/core/src/test/java/org/spongycastle/math/ec/test/ECAlgorithmsTest.java b/core/src/test/java/org/spongycastle/math/ec/test/ECAlgorithmsTest.java new file mode 100644 index 00000000..153738b5 --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/ECAlgorithmsTest.java @@ -0,0 +1,168 @@ +package org.spongycastle.math.ec.test; + +import java.math.BigInteger; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.spongycastle.asn1.x9.ECNamedCurveTable; +import org.spongycastle.asn1.x9.X9ECParameters; +import org.spongycastle.crypto.ec.CustomNamedCurves; +import org.spongycastle.math.ec.ECAlgorithms; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECPoint; + +public class ECAlgorithmsTest extends TestCase +{ + private static final int SCALE = 4; + private static final SecureRandom RND = new SecureRandom(); + + public void testSumOfMultiplies() + { + ArrayList x9s = getTestCurves(); + Iterator it = x9s.iterator(); + while (it.hasNext()) + { + X9ECParameters x9 = (X9ECParameters)it.next(); + + ECPoint[] points = new ECPoint[SCALE]; + BigInteger[] scalars = new BigInteger[SCALE]; + for (int i = 0; i < SCALE; ++i) + { + points[i] = getRandomPoint(x9); + scalars[i] = getRandomScalar(x9); + } + + ECPoint u = x9.getCurve().getInfinity(); + for (int i = 0; i < SCALE; ++i) + { + u = u.add(points[i].multiply(scalars[i])); + + ECPoint v = ECAlgorithms.sumOfMultiplies(copyPoints(points, i + 1), copyScalars(scalars, i + 1)); + + ECPoint[] results = new ECPoint[]{ u, v }; + x9.getCurve().normalizeAll(results); + + assertPointsEqual("ECAlgorithms.sumOfMultiplies is incorrect", results[0], results[1]); + } + } + } + + public void testSumOfTwoMultiplies() + { + ArrayList x9s = getTestCurves(); + Iterator it = x9s.iterator(); + while (it.hasNext()) + { + X9ECParameters x9 = (X9ECParameters)it.next(); + + ECPoint p = getRandomPoint(x9); + BigInteger a = getRandomScalar(x9); + + for (int i = 0; i < SCALE; ++i) + { + ECPoint q = getRandomPoint(x9); + BigInteger b = getRandomScalar(x9); + + ECPoint u = p.multiply(a).add(q.multiply(b)); + ECPoint v = ECAlgorithms.shamirsTrick(p, a, q, b); + ECPoint w = ECAlgorithms.sumOfTwoMultiplies(p, a, q, b); + + ECPoint[] results = new ECPoint[]{ u, v, w }; + x9.getCurve().normalizeAll(results); + + assertPointsEqual("ECAlgorithms.shamirsTrick is incorrect", results[0], results[1]); + assertPointsEqual("ECAlgorithms.sumOfTwoMultiplies is incorrect", results[0], results[2]); + + p = q; + a = b; + } + } + } + + private void assertPointsEqual(String message, ECPoint a, ECPoint b) + { + assertEquals(message, a, b); + } + + private ECPoint[] copyPoints(ECPoint[] ps, int len) + { + ECPoint[] result = new ECPoint[len]; + System.arraycopy(ps, 0, result, 0, len); + return result; + } + + private BigInteger[] copyScalars(BigInteger[] ks, int len) + { + BigInteger[] result = new BigInteger[len]; + System.arraycopy(ks, 0, result, 0, len); + return result; + } + + private ECPoint getRandomPoint(X9ECParameters x9) + { + return x9.getG().multiply(getRandomScalar(x9)); + } + + private BigInteger getRandomScalar(X9ECParameters x9) + { + return new BigInteger(x9.getN().bitLength(), RND); + } + + private ArrayList getTestCurves() + { + ArrayList x9s = new ArrayList(); + Set names = new HashSet(AllTests.enumToList(ECNamedCurveTable.getNames())); + names.addAll(AllTests.enumToList(CustomNamedCurves.getNames())); + + Iterator it = names.iterator(); + while (it.hasNext()) + { + String name = (String)it.next(); + + X9ECParameters x9 = ECNamedCurveTable.getByName(name); + if (x9 != null) + { + addTestCurves(x9s, x9); + } + + x9 = CustomNamedCurves.getByName(name); + if (x9 != null) + { + addTestCurves(x9s, x9); + } + } + return x9s; + } + + private void addTestCurves(ArrayList x9s, X9ECParameters x9) + { + ECCurve curve = x9.getCurve(); + + int[] coords = ECCurve.getAllCoordinateSystems(); + for (int i = 0; i < coords.length; ++i) + { + int coord = coords[i]; + if (curve.getCoordinateSystem() == coord) + { + x9s.add(x9); + } + else if (curve.supportsCoordinateSystem(coord)) + { + ECCurve c = curve.configure().setCoordinateSystem(coord).create(); + x9s.add(new X9ECParameters(c, c.importPoint(x9.getG()), x9.getN(), x9.getH())); + } + } + } + + public static Test suite() + { + return new TestSuite(ECAlgorithmsTest.class); + } + +} diff --git a/core/src/test/java/org/spongycastle/math/ec/test/ECPointPerformanceTest.java b/core/src/test/java/org/spongycastle/math/ec/test/ECPointPerformanceTest.java new file mode 100644 index 00000000..6be0c00b --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/ECPointPerformanceTest.java @@ -0,0 +1,198 @@ +package org.spongycastle.math.ec.test; + +import java.math.BigInteger; +import java.security.SecureRandom; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; +import java.util.SortedSet; +import java.util.TreeSet; + +import junit.framework.TestCase; +import org.spongycastle.asn1.ASN1ObjectIdentifier; +import org.spongycastle.asn1.x9.ECNamedCurveTable; +import org.spongycastle.asn1.x9.X9ECParameters; +import org.spongycastle.crypto.ec.CustomNamedCurves; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.Times; + +/** + * Compares the performance of the the window NAF point multiplication against conventional point + * multiplication. + */ +public class ECPointPerformanceTest extends TestCase +{ + static final int MILLIS_PER_ROUND = 200; + static final int MILLIS_WARMUP = 1000; + + static final int MULTS_PER_CHECK = 16; + static final int NUM_ROUNDS = 10; + + private static String[] COORD_NAMES = new String[]{ "AFFINE", "HOMOGENEOUS", "JACOBIAN", "JACOBIAN-CHUDNOVSKY", + "JACOBIAN-MODIFIED", "LAMBDA-AFFINE", "LAMBDA-PROJECTIVE", "SKEWED" }; + + private void randMult(String curveName) throws Exception + { + X9ECParameters spec = ECNamedCurveTable.getByName(curveName); + if (spec != null) + { + randMult(curveName, spec); + } + + spec = CustomNamedCurves.getByName(curveName); + if (spec != null) + { + randMult(curveName + " (custom)", spec); + } + } + + private void randMult(String label, X9ECParameters spec) throws Exception + { + ECCurve C = spec.getCurve(); + ECPoint G = (ECPoint)spec.getG(); + BigInteger n = spec.getN(); + + SecureRandom random = SecureRandom.getInstance("SHA1PRNG", "SUN"); + random.setSeed(System.currentTimeMillis()); + + System.out.println(label); + + int[] coords = ECCurve.getAllCoordinateSystems(); + for (int i = 0; i < coords.length; ++i) + { + int coord = coords[i]; + if (C.supportsCoordinateSystem(coord)) + { + ECCurve c = C; + ECPoint g = G; + + boolean defaultCoord = (c.getCoordinateSystem() == coord); + if (!defaultCoord) + { + c = C.configure().setCoordinateSystem(coord).create(); + g = c.importPoint(G); + } + + double avgRate = randMult(random, g, n); + String coordName = COORD_NAMES[coord]; + StringBuffer sb = new StringBuffer(); + sb.append(" "); + sb.append(defaultCoord ? '*' : ' '); + sb.append(coordName); + for (int j = sb.length(); j < 30; ++j) + { + sb.append(' '); + } + sb.append(": "); + sb.append(avgRate); + sb.append(" mults/sec"); + for (int j = sb.length(); j < 64; ++j) + { + sb.append(' '); + } + sb.append('('); + sb.append(1000.0 / avgRate); + sb.append(" millis/mult)"); + System.out.println(sb.toString()); + } + } + } + + private double randMult(SecureRandom random, ECPoint g, BigInteger n) throws Exception + { + BigInteger[] ks = new BigInteger[128]; + for (int i = 0; i < ks.length; ++i) + { + ks[i] = new BigInteger(n.bitLength() - 1, random); + } + + int ki = 0; + ECPoint p = g; + + { + long startTime = Times.nanoTime(); + long goalTime = startTime + 1000000L * MILLIS_WARMUP; + + do + { + BigInteger k = ks[ki]; + p = g.multiply(k); + if ((ki & 1) != 0) + { + g = p; + } + if (++ki == ks.length) + { + ki = 0; + } + } + while (Times.nanoTime() < goalTime); + } + + double minRate = Double.MAX_VALUE, maxRate = Double.MIN_VALUE, totalRate = 0.0; + + for (int i = 1; i <= NUM_ROUNDS; i++) + { + long startTime = Times.nanoTime(); + long goalTime = startTime + 1000000L * MILLIS_PER_ROUND; + long count = 0, endTime; + + do + { + ++count; + + for (int j = 0; j < MULTS_PER_CHECK; ++j) + { + BigInteger k = ks[ki]; + p = g.multiply(k); + if ((ki & 1) != 0) + { + g = p; + } + if (++ki == ks.length) + { + ki = 0; + } + } + + endTime = Times.nanoTime(); + } + while (endTime < goalTime); + + double roundElapsed = (double)(endTime - startTime); + double roundRate = count * MULTS_PER_CHECK * 1000000000L / roundElapsed; + + minRate = Math.min(minRate, roundRate); + maxRate = Math.max(maxRate, roundRate); + totalRate += roundRate; + } + + return (totalRate - minRate - maxRate) / (NUM_ROUNDS - 2); + } + + public void testMultiply() throws Exception + { + SortedSet names = new TreeSet(AllTests.enumToList(ECNamedCurveTable.getNames())); + names.addAll(AllTests.enumToList(CustomNamedCurves.getNames())); + + Set oids = new HashSet(); + + Iterator it = names.iterator(); + while (it.hasNext()) + { + String name = (String)it.next(); + ASN1ObjectIdentifier oid = ECNamedCurveTable.getOID(name); + if (oid == null) + { + oid = CustomNamedCurves.getOID(name); + } + if (oid != null && !oids.add(oid)) + { + continue; + } + + randMult(name); + } + } +} diff --git a/core/src/test/java/org/spongycastle/math/ec/test/ECPointTest.java b/core/src/test/java/org/spongycastle/math/ec/test/ECPointTest.java new file mode 100644 index 00000000..5987e22f --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/ECPointTest.java @@ -0,0 +1,521 @@ +package org.spongycastle.math.ec.test; + +import java.math.BigInteger; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.Enumeration; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.spongycastle.asn1.x9.ECNamedCurveTable; +import org.spongycastle.asn1.x9.X9ECParameters; +import org.spongycastle.crypto.ec.CustomNamedCurves; +import org.spongycastle.math.ec.ECAlgorithms; +import org.spongycastle.math.ec.ECConstants; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.BigIntegers; + +/** + * Test class for {@link org.spongycastle.math.ec.ECPoint ECPoint}. All + * literature values are taken from "Guide to elliptic curve cryptography", + * Darrel Hankerson, Alfred J. Menezes, Scott Vanstone, 2004, Springer-Verlag + * New York, Inc. + */ +public class ECPointTest extends TestCase +{ + /** + * Random source used to generate random points + */ + private SecureRandom secRand = new SecureRandom(); + + private ECPointTest.Fp fp = null; + + private ECPointTest.F2m f2m = null; + + /** + * Nested class containing sample literature values for <code>Fp</code>. + */ + public static class Fp + { + private final BigInteger q = new BigInteger("29"); + + private final BigInteger a = new BigInteger("4"); + + private final BigInteger b = new BigInteger("20"); + + private final BigInteger n = new BigInteger("38"); + + private final BigInteger h = new BigInteger("1"); + + private final ECCurve curve = new ECCurve.Fp(q, a, b, n, h); + + private final ECPoint infinity = curve.getInfinity(); + + private final int[] pointSource = { 5, 22, 16, 27, 13, 6, 14, 6 }; + + private ECPoint[] p = new ECPoint[pointSource.length / 2]; + + /** + * Creates the points on the curve with literature values. + */ + private void createPoints() + { + for (int i = 0; i < pointSource.length / 2; i++) + { + p[i] = curve.createPoint( + new BigInteger(Integer.toString(pointSource[2 * i])), + new BigInteger(Integer.toString(pointSource[2 * i + 1]))); + } + } + } + + /** + * Nested class containing sample literature values for <code>F2m</code>. + */ + public static class F2m + { + // Irreducible polynomial for TPB z^4 + z + 1 + private final int m = 4; + + private final int k1 = 1; + + // a = z^3 + private final BigInteger aTpb = new BigInteger("1000", 2); + + // b = z^3 + 1 + private final BigInteger bTpb = new BigInteger("1001", 2); + + private final BigInteger n = new BigInteger("23"); + + private final BigInteger h = new BigInteger("1"); + + private final ECCurve.F2m curve = new ECCurve.F2m(m, k1, aTpb, bTpb, n, h); + + private final ECPoint.F2m infinity = (ECPoint.F2m) curve.getInfinity(); + + private final String[] pointSource = { "0010", "1111", "1100", "1100", + "0001", "0001", "1011", "0010" }; + + private ECPoint[] p = new ECPoint[pointSource.length / 2]; + + /** + * Creates the points on the curve with literature values. + */ + private void createPoints() + { + for (int i = 0; i < pointSource.length / 2; i++) + { + p[i] = curve.createPoint( + new BigInteger(pointSource[2 * i], 2), + new BigInteger(pointSource[2 * i + 1], 2)); + } + } + } + + public void setUp() + { + fp = new ECPointTest.Fp(); + fp.createPoints(); + + f2m = new ECPointTest.F2m(); + f2m.createPoints(); + } + + /** + * Tests, if inconsistent points can be created, i.e. points with exactly + * one null coordinate (not permitted). + */ + public void testPointCreationConsistency() + { + try + { + ECPoint bad = fp.curve.createPoint(new BigInteger("12"), null); + fail(); + } + catch (IllegalArgumentException expected) + { + } + + try + { + ECPoint bad = fp.curve.createPoint(null, new BigInteger("12")); + fail(); + } + catch (IllegalArgumentException expected) + { + } + + try + { + ECPoint bad = f2m.curve.createPoint(new BigInteger("1011"), null); + fail(); + } + catch (IllegalArgumentException expected) + { + } + + try + { + ECPoint bad = f2m.curve.createPoint(null, new BigInteger("1011")); + fail(); + } + catch (IllegalArgumentException expected) + { + } + } + + /** + * Tests <code>ECPoint.add()</code> against literature values. + * + * @param p + * The array of literature values. + * @param infinity + * The point at infinity on the respective curve. + */ + private void implTestAdd(ECPoint[] p, ECPoint infinity) + { + assertPointsEqual("p0 plus p1 does not equal p2", p[2], p[0].add(p[1])); + assertPointsEqual("p1 plus p0 does not equal p2", p[2], p[1].add(p[0])); + for (int i = 0; i < p.length; i++) + { + assertPointsEqual("Adding infinity failed", p[i], p[i].add(infinity)); + assertPointsEqual("Adding to infinity failed", p[i], infinity.add(p[i])); + } + } + + /** + * Calls <code>implTestAdd()</code> for <code>Fp</code> and + * <code>F2m</code>. + */ + public void testAdd() + { + implTestAdd(fp.p, fp.infinity); + implTestAdd(f2m.p, f2m.infinity); + } + + /** + * Tests <code>ECPoint.twice()</code> against literature values. + * + * @param p + * The array of literature values. + */ + private void implTestTwice(ECPoint[] p) + { + assertPointsEqual("Twice incorrect", p[3], p[0].twice()); + assertPointsEqual("Add same point incorrect", p[3], p[0].add(p[0])); + } + + /** + * Calls <code>implTestTwice()</code> for <code>Fp</code> and + * <code>F2m</code>. + */ + public void testTwice() + { + implTestTwice(fp.p); + implTestTwice(f2m.p); + } + + private void implTestThreeTimes(ECPoint[] p) + { + ECPoint P = p[0]; + ECPoint _3P = P.add(P).add(P); + assertPointsEqual("ThreeTimes incorrect", _3P, P.threeTimes()); + assertPointsEqual("TwicePlus incorrect", _3P, P.twicePlus(P)); + } + + /** + * Calls <code>implTestThreeTimes()</code> for <code>Fp</code> and + * <code>F2m</code>. + */ + public void testThreeTimes() + { + implTestThreeTimes(fp.p); + implTestThreeTimes(f2m.p); + } + + /** + * Goes through all points on an elliptic curve and checks, if adding a + * point <code>k</code>-times is the same as multiplying the point by + * <code>k</code>, for all <code>k</code>. Should be called for points + * on very small elliptic curves only. + * + * @param p + * The base point on the elliptic curve. + * @param infinity + * The point at infinity on the elliptic curve. + */ + private void implTestAllPoints(ECPoint p, ECPoint infinity) + { + ECPoint adder = infinity; + ECPoint multiplier = infinity; + + BigInteger i = BigInteger.valueOf(1); + do + { + adder = adder.add(p); + multiplier = p.multiply(i); + assertPointsEqual("Results of add() and multiply() are inconsistent " + + i, adder, multiplier); + i = i.add(BigInteger.ONE); + } + while (!(adder.equals(infinity))); + } + + /** + * Calls <code>implTestAllPoints()</code> for the small literature curves, + * both for <code>Fp</code> and <code>F2m</code>. + */ + public void testAllPoints() + { + for (int i = 0; i < fp.p.length; i++) + { + implTestAllPoints(fp.p[0], fp.infinity); + } + + for (int i = 0; i < f2m.p.length; i++) + { + implTestAllPoints(f2m.p[0], f2m.infinity); + } + } + + /** + * Checks, if the point multiplication algorithm of the given point yields + * the same result as point multiplication done by the reference + * implementation given in <code>multiply()</code>. This method chooses a + * random number by which the given point <code>p</code> is multiplied. + * + * @param p + * The point to be multiplied. + * @param numBits + * The bitlength of the random number by which <code>p</code> + * is multiplied. + */ + private void implTestMultiply(ECPoint p, int numBits) + { + BigInteger k = new BigInteger(numBits, secRand); + ECPoint ref = ECAlgorithms.referenceMultiply(p, k); + ECPoint q = p.multiply(k); + assertPointsEqual("ECPoint.multiply is incorrect", ref, q); + } + + /** + * Checks, if the point multiplication algorithm of the given point yields + * the same result as point multiplication done by the reference + * implementation given in <code>multiply()</code>. This method tests + * multiplication of <code>p</code> by every number of bitlength + * <code>numBits</code> or less. + * + * @param p + * The point to be multiplied. + * @param numBits + * Try every multiplier up to this bitlength + */ + private void implTestMultiplyAll(ECPoint p, int numBits) + { + BigInteger bound = BigInteger.ONE.shiftLeft(numBits); + BigInteger k = BigInteger.ZERO; + + do + { + ECPoint ref = ECAlgorithms.referenceMultiply(p, k); + ECPoint q = p.multiply(k); + assertPointsEqual("ECPoint.multiply is incorrect", ref, q); + k = k.add(BigInteger.ONE); + } + while (k.compareTo(bound) < 0); + } + + /** + * Tests <code>ECPoint.add()</code> and <code>ECPoint.subtract()</code> + * for the given point and the given point at infinity. + * + * @param p + * The point on which the tests are performed. + * @param infinity + * The point at infinity on the same curve as <code>p</code>. + */ + private void implTestAddSubtract(ECPoint p, ECPoint infinity) + { + assertPointsEqual("Twice and Add inconsistent", p.twice(), p.add(p)); + assertPointsEqual("Twice p - p is not p", p, p.twice().subtract(p)); + assertPointsEqual("TwicePlus(p, -p) is not p", p, p.twicePlus(p.negate())); + assertPointsEqual("p - p is not infinity", infinity, p.subtract(p)); + assertPointsEqual("p plus infinity is not p", p, p.add(infinity)); + assertPointsEqual("infinity plus p is not p", p, infinity.add(p)); + assertPointsEqual("infinity plus infinity is not infinity ", infinity, infinity.add(infinity)); + assertPointsEqual("Twice infinity is not infinity ", infinity, infinity.twice()); + } + + /** + * Calls <code>implTestAddSubtract()</code> for literature values, both + * for <code>Fp</code> and <code>F2m</code>. + */ + public void testAddSubtractMultiplySimple() + { + int fpBits = fp.curve.getOrder().bitLength(); + for (int iFp = 0; iFp < fp.pointSource.length / 2; iFp++) + { + implTestAddSubtract(fp.p[iFp], fp.infinity); + + implTestMultiplyAll(fp.p[iFp], fpBits); + implTestMultiplyAll(fp.infinity, fpBits); + } + + int f2mBits = f2m.curve.getOrder().bitLength(); + for (int iF2m = 0; iF2m < f2m.pointSource.length / 2; iF2m++) + { + implTestAddSubtract(f2m.p[iF2m], f2m.infinity); + + implTestMultiplyAll(f2m.p[iF2m], f2mBits); + implTestMultiplyAll(f2m.infinity, f2mBits); + } + } + + /** + * Test encoding with and without point compression. + * + * @param p + * The point to be encoded and decoded. + */ + private void implTestEncoding(ECPoint p) + { + // Not Point Compression + byte[] unCompBarr = p.getEncoded(false); + ECPoint decUnComp = p.getCurve().decodePoint(unCompBarr); + assertPointsEqual("Error decoding uncompressed point", p, decUnComp); + + // Point compression + byte[] compBarr = p.getEncoded(true); + ECPoint decComp = p.getCurve().decodePoint(compBarr); + assertPointsEqual("Error decoding compressed point", p, decComp); + } + + private void implAddSubtractMultiplyTwiceEncodingTest(ECCurve curve, ECPoint q, BigInteger n) + { + // Get point at infinity on the curve + ECPoint infinity = curve.getInfinity(); + + implTestAddSubtract(q, infinity); + implTestMultiply(q, n.bitLength()); + implTestMultiply(infinity, n.bitLength()); + + ECPoint p = q; + for (int i = 0; i < 10; ++i) + { + implTestEncoding(p); + p = p.twice(); + } + } + + private void implSqrtTest(ECCurve c) + { + if (ECAlgorithms.isFpCurve(c)) + { + BigInteger p = c.getField().getCharacteristic(); + BigInteger pMinusOne = p.subtract(ECConstants.ONE); + BigInteger legendreExponent = p.shiftRight(1); + + int count = 0; + while (count < 10) + { + BigInteger nonSquare = BigIntegers.createRandomInRange(ECConstants.TWO, pMinusOne, secRand); + if (!nonSquare.modPow(legendreExponent, p).equals(ECConstants.ONE)) + { + ECFieldElement root = c.fromBigInteger(nonSquare).sqrt(); + assertNull(root); + ++count; + } + } + } + } + + private void implAddSubtractMultiplyTwiceEncodingTestAllCoords(X9ECParameters x9ECParameters) + { + BigInteger n = x9ECParameters.getN(); + ECPoint G = x9ECParameters.getG(); + ECCurve C = x9ECParameters.getCurve(); + + int[] coords = ECCurve.getAllCoordinateSystems(); + for (int i = 0; i < coords.length; ++i) + { + int coord = coords[i]; + if (C.supportsCoordinateSystem(coord)) + { + ECCurve c = C; + ECPoint g = G; + + if (c.getCoordinateSystem() != coord) + { + c = C.configure().setCoordinateSystem(coord).create(); + g = c.importPoint(G); + } + + // The generator is multiplied by random b to get random q + BigInteger b = new BigInteger(n.bitLength(), secRand); + ECPoint q = g.multiply(b).normalize(); + + implAddSubtractMultiplyTwiceEncodingTest(c, q, n); + + implSqrtTest(c); + } + } + } + + /** + * Calls <code>implTestAddSubtract()</code>, + * <code>implTestMultiply</code> and <code>implTestEncoding</code> for + * the standard elliptic curves as given in <code>SECNamedCurves</code>. + */ + public void testAddSubtractMultiplyTwiceEncoding() + { + Set names = new HashSet(enumToList(ECNamedCurveTable.getNames())); + names.addAll(enumToList(CustomNamedCurves.getNames())); + + Iterator it = names.iterator(); + while (it.hasNext()) + { + String name = (String)it.next(); + + X9ECParameters x9ECParameters = ECNamedCurveTable.getByName(name); + if (x9ECParameters != null) + { + implAddSubtractMultiplyTwiceEncodingTestAllCoords(x9ECParameters); + } + + x9ECParameters = CustomNamedCurves.getByName(name); + if (x9ECParameters != null) + { + implAddSubtractMultiplyTwiceEncodingTestAllCoords(x9ECParameters); + } + } + } + + private List enumToList(Enumeration en) + { + List rv = new ArrayList(); + + while (en.hasMoreElements()) + { + rv.add(en.nextElement()); + } + + return rv; + } + + private void assertPointsEqual(String message, ECPoint a, ECPoint b) + { + assertEquals(message, a, b); + } + + public static Test suite() + { + return new TestSuite(ECPointTest.class); + } +} diff --git a/core/src/test/java/org/spongycastle/math/ec/test/F2mProofer.java b/core/src/test/java/org/spongycastle/math/ec/test/F2mProofer.java new file mode 100644 index 00000000..9d7e5195 --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/F2mProofer.java @@ -0,0 +1,203 @@ +package org.spongycastle.math.ec.test; + +import java.io.FileInputStream; +import java.io.FileOutputStream; +import java.io.IOException; +import java.math.BigInteger; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.util.Iterator; +import java.util.Properties; +import java.util.Set; + +import org.spongycastle.asn1.sec.SECNamedCurves; +import org.spongycastle.asn1.x9.X9ECParameters; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; + +public class F2mProofer +{ + private static final int NUM_SAMPLES = 1000; + + private static final String PATH = "crypto/test/src/org/spongycastle/math/ec/test/samples/"; + + private static final String INPUT_FILE_NAME_PREFIX = "Input_"; + + private static final String RESULT_FILE_NAME_PREFIX = "Output_"; + + /** + * The standard curves on which the tests are done + */ + public static final String[] CURVES = { "sect163r2", "sect233r1", + "sect283r1", "sect409r1", "sect571r1" }; + + private String pointToString(ECPoint.F2m p) + { + ECFieldElement.F2m x = (ECFieldElement.F2m) p.getAffineXCoord(); + ECFieldElement.F2m y = (ECFieldElement.F2m) p.getAffineYCoord(); + + int m = x.getM(); + int len = m / 2 + 5; + + StringBuffer sb = new StringBuffer(len); + sb.append('('); + sb.append(x.toBigInteger().toString(16)); + sb.append(", "); + sb.append(y.toBigInteger().toString(16)); + sb.append(')'); + + return sb.toString(); + } + + private void generateRandomInput(X9ECParameters x9ECParameters) + throws NoSuchAlgorithmException, IOException + { + ECPoint.F2m g = (ECPoint.F2m) x9ECParameters.getG(); + int m = ((ECFieldElement.F2m) (g.getAffineXCoord())).getM(); + + SecureRandom secRand = SecureRandom.getInstance("SHA1PRNG"); + Properties inputProps = new Properties(); + for (int i = 0; i < NUM_SAMPLES; i++) + { + BigInteger rand = new BigInteger(m, secRand); + inputProps.put(Integer.toString(i), rand.toString(16)); + } + String bits = Integer.toString(m); + FileOutputStream fos = new FileOutputStream(PATH + + INPUT_FILE_NAME_PREFIX + bits + ".properties"); + inputProps.store(fos, "Input Samples of length" + bits); + } + + private void multiplyPoints(X9ECParameters x9ECParameters, + String classPrefix) throws IOException + { + ECPoint.F2m g = (ECPoint.F2m) x9ECParameters.getG(); + int m = ((ECFieldElement.F2m) (g.getAffineXCoord())).getM(); + + String inputFileName = PATH + INPUT_FILE_NAME_PREFIX + m + + ".properties"; + Properties inputProps = new Properties(); + inputProps.load(new FileInputStream(inputFileName)); + + Properties outputProps = new Properties(); + + for (int i = 0; i < NUM_SAMPLES; i++) + { + BigInteger rand = new BigInteger(inputProps.getProperty(Integer + .toString(i)), 16); + ECPoint.F2m result = (ECPoint.F2m) g.multiply(rand).normalize(); + String resultStr = pointToString(result); + outputProps.setProperty(Integer.toString(i), resultStr); + } + + String outputFileName = PATH + RESULT_FILE_NAME_PREFIX + classPrefix + + "_" + m + ".properties"; + FileOutputStream fos = new FileOutputStream(outputFileName); + outputProps.store(fos, "Output Samples of length" + m); + } + + private Properties loadResults(String classPrefix, int m) + throws IOException + { + FileInputStream fis = new FileInputStream(PATH + + RESULT_FILE_NAME_PREFIX + classPrefix + "_" + m + ".properties"); + Properties res = new Properties(); + res.load(fis); + return res; + + } + + private void compareResult(X9ECParameters x9ECParameters, + String classPrefix1, String classPrefix2) throws IOException + { + ECPoint.F2m g = (ECPoint.F2m) x9ECParameters.getG(); + int m = ((ECFieldElement.F2m) (g.getAffineXCoord())).getM(); + + Properties res1 = loadResults(classPrefix1, m); + Properties res2 = loadResults(classPrefix2, m); + + Set keys = res1.keySet(); + Iterator iter = keys.iterator(); + while (iter.hasNext()) + { + String key = (String) iter.next(); + String result1 = res1.getProperty(key); + String result2 = res2.getProperty(key); + if (!(result1.equals(result2))) + { + System.err.println("Difference found: m = " + m + ", " + + result1 + " does not equal " + result2); + } + } + + } + + private static void usage() + { + System.err.println("Usage: F2mProofer [-init | -multiply <className> " + + "| -compare <className1> <className2>]"); + } + + public static void main(String[] args) throws Exception + { + if (args.length == 0) + { + usage(); + return; + } + F2mProofer proofer = new F2mProofer(); + if (args[0].equals("-init")) + { + System.out.println("Generating random input..."); + for (int i = 0; i < CURVES.length; i++) + { + X9ECParameters x9ECParameters = SECNamedCurves + .getByName(CURVES[i]); + proofer.generateRandomInput(x9ECParameters); + } + System.out + .println("Successfully generated random input in " + PATH); + } + else if (args[0].equals("-compare")) + { + if (args.length < 3) + { + usage(); + return; + } + String classPrefix1 = args[1]; + String classPrefix2 = args[2]; + System.out.println("Comparing results..."); + for (int i = 0; i < CURVES.length; i++) + { + X9ECParameters x9ECParameters = SECNamedCurves + .getByName(CURVES[i]); + proofer.compareResult(x9ECParameters, classPrefix1, + classPrefix2); + } + System.out.println("Successfully compared results in " + PATH); + } + else if (args[0].equals("-multiply")) + { + if (args.length < 2) + { + usage(); + return; + } + String classPrefix = args[1]; + System.out.println("Multiplying points..."); + for (int i = 0; i < CURVES.length; i++) + { + X9ECParameters x9ECParameters = SECNamedCurves + .getByName(CURVES[i]); + proofer.multiplyPoints(x9ECParameters, classPrefix); + } + System.out.println("Successfully generated multiplied points in " + + PATH); + } + else + { + usage(); + } + } +} diff --git a/core/src/test/java/org/spongycastle/math/ec/test/TnafTest.java b/core/src/test/java/org/spongycastle/math/ec/test/TnafTest.java new file mode 100644 index 00000000..bd527c6f --- /dev/null +++ b/core/src/test/java/org/spongycastle/math/ec/test/TnafTest.java @@ -0,0 +1,152 @@ +//package org.spongycastle.math.ec.test; +// +//import java.math.BigInteger; +//import java.util.Random; +// +//import junit.framework.TestCase; +// +//import org.spongycastle.asn1.sec.SECNamedCurves; +//import org.spongycastle.asn1.x9.X9ECParameters; +//import org.spongycastle.math.ec.ECCurve; +//import org.spongycastle.math.ec.ECPoint; +//import org.spongycastle.math.ec.NafL2RMultiplier; +//import org.spongycastle.math.ec.ReferenceMultiplier; +//import org.spongycastle.math.ec.WNafL2RMultiplier; +//import org.spongycastle.math.ec.WTauNafMultiplier; +// +//public class TnafTest extends TestCase +//{ +// private Random m_rand = new Random(); +// +// private String ecPointToString(ECPoint p) { +// StringBuffer sb = new StringBuffer("x = "); +// sb.append(p.getX().toBigInteger().toString()); +// sb.append("; y = "); +// sb.append(p.getY().toBigInteger().toString()); +// return sb.toString(); +// } +// +// private ECPoint repeatedMultiply(ECPoint p, BigInteger k) +// { +// ECPoint result = p.multiply(k); +// for (int i = 1; i < 10; ++i) +// { +// ECPoint check = p.multiply(k); +// assertEquals(result, check); +// } +// return result; +// } +// +// private void implTestMultiplyTnaf(String curveName) { +// X9ECParameters x9ECParameters = SECNamedCurves.getByName(curveName); +// +// ECCurve.F2m curve = (ECCurve.F2m)x9ECParameters.getCurve(); +// BigInteger n = curve.getN(); +// +// // The generator is multiplied by random b to get random q +// BigInteger b = new BigInteger(n.bitLength(), m_rand); +// ECPoint g = x9ECParameters.getG(); +// ECPoint.F2m p = (ECPoint.F2m)g.multiply(b); +// +// BigInteger k = new BigInteger(n.bitLength(), m_rand); +// long now1 = System.currentTimeMillis(); +// p.setECMultiplier(new WTauNafMultiplier()); +// ECPoint refRWTnaf = repeatedMultiply(p, k); +// long now2 = System.currentTimeMillis(); +// p.setECMultiplier(new WNafL2RMultiplier()); +// ECPoint refWnaf = repeatedMultiply(p, k); +// long now3 = System.currentTimeMillis(); +// p.setECMultiplier(new NafL2RMultiplier()); +// ECPoint refFpNaf = repeatedMultiply(p, k); +// long now4 = System.currentTimeMillis(); +// p.setECMultiplier(new ReferenceMultiplier()); +// ECPoint reference = repeatedMultiply(p, k); +// long now5 = System.currentTimeMillis(); +// +// assertEquals("WTNAF multiplication is incorrect", refRWTnaf, reference); +// assertEquals("FPNAF multiplication is incorrect", refFpNaf, reference); +// assertEquals("WNAF multiplication is incorrect", refWnaf, reference); +// +// System.out.println(curveName + ": Multiply WTNAF took millis: " + (now2 - now1)); +// System.out.println(curveName + ": Multiply WNAF took millis: " + (now3 - now2)); +// System.out.println(curveName + ": Multiply FPNAF took millis: " + (now4 - now3)); +// System.out.println(curveName + ": Multiply REFE took millis: " + (now5 - now4)); +// +//// System.out.println(curveName + ": refRWTnaf = " + ecPointToString(refRWTnaf)); +//// System.out.println(curveName + ": refWnaf = " + ecPointToString(refWnaf)); +//// System.out.println(curveName + ": refFpNaf = " + ecPointToString(refFpNaf)); +//// System.out.println(curveName + ": reference = " + ecPointToString(reference) + "\n"); +// System.out.println(); +// } +// +// public void testMultiplyTnaf() { +// System.out.println("\n\n\n***** Start test multiplications on F2m (Koblitz) *****"); +// implTestMultiplyTnaf("sect163k1"); +// implTestMultiplyTnaf("sect233k1"); +// implTestMultiplyTnaf("sect239k1"); +// implTestMultiplyTnaf("sect283k1"); +// implTestMultiplyTnaf("sect409k1"); +// implTestMultiplyTnaf("sect571k1"); +// } +// +// private void implTestMultiplyWnaf(String curveName) { +// X9ECParameters x9ECParameters = SECNamedCurves.getByName(curveName); +// +// BigInteger r = x9ECParameters.getN(); +// +// // The generator is multiplied by random b to get random q +// BigInteger b = new BigInteger(r.bitLength(), m_rand); +// ECPoint g = x9ECParameters.getG(); +// ECPoint p = g.multiply(b); +// +// BigInteger k = new BigInteger(r.bitLength(), m_rand); +// long now1 = System.currentTimeMillis(); +// p.setECMultiplier(new WNafL2RMultiplier()); +// ECPoint refWnaf = repeatedMultiply(p, k); +// long now2 = System.currentTimeMillis(); +// p.setECMultiplier(new NafL2RMultiplier()); +// ECPoint refFpNaf = repeatedMultiply(p, k); +// long now3 = System.currentTimeMillis(); +// p.setECMultiplier(new ReferenceMultiplier()); +// ECPoint reference = repeatedMultiply(p, k); +// long now4 = System.currentTimeMillis(); +// +// assertEquals("WNAF multiplication is incorrect", refWnaf, reference); +// assertEquals("FPNAF multiplication is incorrect", refFpNaf, reference); +// +// System.out.println(curveName + ": Multiply WNAF took millis: " + (now2 - now1)); +// System.out.println(curveName + ": Multiply FPNAF took millis: " + (now3 - now2)); +// System.out.println(curveName + ": Multiply REFE took millis: " + (now4 - now3)); +// +//// System.out.println(curveName + ": refWnaf = " + ecPointToString(refWnaf)); +//// System.out.println(curveName + ": refFpNaf = " + ecPointToString(refFpNaf)); +//// System.out.println(curveName + ": reference = " + ecPointToString(reference)); +// System.out.println(); +// } +// +// public void testMultiplyWnaf() { +// System.out.println("\n\n\n***** Start test multiplications on F2m *****"); +// implTestMultiplyWnaf("sect113r1"); +// implTestMultiplyWnaf("sect113r2"); +// implTestMultiplyWnaf("sect131r1"); +// implTestMultiplyWnaf("sect131r2"); +// implTestMultiplyWnaf("sect163r1"); +// implTestMultiplyWnaf("sect163r2"); +// implTestMultiplyWnaf("sect193r1"); +// implTestMultiplyWnaf("sect193r2"); +// implTestMultiplyWnaf("sect233r1"); +// implTestMultiplyWnaf("sect283r1"); +// implTestMultiplyWnaf("sect409r1"); +// implTestMultiplyWnaf("sect571r1"); +// +// System.out.println("\n\n\n***** Start test multiplications on Fp *****"); +// implTestMultiplyWnaf("secp112r1"); +// implTestMultiplyWnaf("secp128r1"); +// implTestMultiplyWnaf("secp160r1"); +// implTestMultiplyWnaf("secp192r1"); +// implTestMultiplyWnaf("secp224r1"); +// implTestMultiplyWnaf("secp256r1"); +// implTestMultiplyWnaf("secp384r1"); +// implTestMultiplyWnaf("secp521r1"); +// } +//} |