diff options
author | Victor Chang <vichang@google.com> | 2023-08-16 12:21:18 +0800 |
---|---|---|
committer | Victor Chang <vichang@google.com> | 2023-08-16 13:52:38 +0800 |
commit | a350a9074df9452e3003b90961d0196f030bbf69 (patch) | |
tree | 781ed0d8721f32557da93352667ec12de63a6e43 /bcprov/src/test | |
parent | cc398bcfed63db9672aa1c17466a4957a1a8b123 (diff) | |
download | bouncycastle-a350a9074df9452e3003b90961d0196f030bbf69.tar.gz |
Port upstream org.bouncycastle.math tests to AOSP
Bug: 283789481
Test: m bouncycastle-host-tests
Change-Id: I533b6efa6853dffe51e3ebf629b6bceddbacff53
Diffstat (limited to 'bcprov/src/test')
14 files changed, 2208 insertions, 0 deletions
diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP256R1FieldTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP256R1FieldTest.java new file mode 100644 index 00000000..b59f1924 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP256R1FieldTest.java @@ -0,0 +1,175 @@ +package org.bouncycastle.math.ec.custom.sec.test; + +import java.math.BigInteger; +import java.security.SecureRandom; + +import org.bouncycastle.asn1.sec.SECObjectIdentifiers; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.raw.Nat256; + +import junit.framework.TestCase; + +public class SecP256R1FieldTest extends TestCase +{ + private static final SecureRandom RANDOM = new SecureRandom(); + + private static final X9ECParameters DP = CustomNamedCurves + .getByOID(SECObjectIdentifiers.secp256r1); + private static final BigInteger Q = DP.getCurve().getField().getCharacteristic(); + + public void testMultiply1() + { + int COUNT = 1000; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateMultiplyInput_Random(); + ECFieldElement y = generateMultiplyInput_Random(); + + BigInteger X = x.toBigInteger(), Y = y.toBigInteger(); + BigInteger R = X.multiply(Y).mod(Q); + + ECFieldElement z = x.multiply(y); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + public void testMultiply2() + { + int COUNT = 100; + ECFieldElement[] inputs = new ECFieldElement[COUNT]; + BigInteger[] INPUTS = new BigInteger[COUNT]; + + for (int i = 0; i < inputs.length; ++i) + { + inputs[i] = generateMultiplyInput_Random(); + INPUTS[i] = inputs[i].toBigInteger(); + } + + for (int j = 0; j < inputs.length; ++j) + { + for (int k = 0; k < inputs.length; ++k) + { + BigInteger R = INPUTS[j].multiply(INPUTS[k]).mod(Q); + + ECFieldElement z = inputs[j].multiply(inputs[k]); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + } + + public void testSquare() + { + int COUNT = 1000; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateMultiplyInput_Random(); + + BigInteger X = x.toBigInteger(); + BigInteger R = X.multiply(X).mod(Q); + + ECFieldElement z = x.square(); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + /** + * Test multiplication with specifically selected values that triggered a bug in the modular + * reduction in OpenSSL (last affected version 0.9.8g). + * + * See "Practical realisation and elimination of an ECC-related software bug attack", B. B. + * Brumley, M. Barbarosa, D. Page, F. Vercauteren. + */ + public void testMultiply_OpenSSLBug() + { + int COUNT = 100; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateMultiplyInputA_OpenSSLBug(); + ECFieldElement y = generateMultiplyInputB_OpenSSLBug(); + + BigInteger X = x.toBigInteger(), Y = y.toBigInteger(); + BigInteger R = X.multiply(Y).mod(Q); + + ECFieldElement z = x.multiply(y); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + /** + * Test squaring with specifically selected values that triggered a bug in the modular reduction + * in OpenSSL (last affected version 0.9.8g). + * + * See "Practical realisation and elimination of an ECC-related software bug attack", B. B. + * Brumley, M. Barbarosa, D. Page, F. Vercauteren. + */ + public void testSquare_OpenSSLBug() + { + int COUNT = 100; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateSquareInput_OpenSSLBug(); + + BigInteger X = x.toBigInteger(); + BigInteger R = X.multiply(X).mod(Q); + + ECFieldElement z = x.square(); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + private ECFieldElement fe(BigInteger x) + { + return DP.getCurve().fromBigInteger(x); + } + + private ECFieldElement generateMultiplyInput_Random() + { + return fe(new BigInteger(DP.getCurve().getFieldSize() + 32, RANDOM).mod(Q)); + } + + private ECFieldElement generateMultiplyInputA_OpenSSLBug() + { + int[] x = Nat256.create(); + x[0] = RANDOM.nextInt() >>> 1; + x[4] = 3; + x[7] = -1; + + return fe(Nat256.toBigInteger(x)); + } + + private ECFieldElement generateMultiplyInputB_OpenSSLBug() + { + int[] x = Nat256.create(); + x[0] = RANDOM.nextInt() >>> 1; + x[3] = 1; + x[7] = -1; + + return fe(Nat256.toBigInteger(x)); + } + + private ECFieldElement generateSquareInput_OpenSSLBug() + { + int[] x = Nat256.create(); + x[0] = RANDOM.nextInt() >>> 1; + x[4] = 2; + x[7] = -1; + + return fe(Nat256.toBigInteger(x)); + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP384R1FieldTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP384R1FieldTest.java new file mode 100644 index 00000000..be6f5d19 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/custom/sec/test/SecP384R1FieldTest.java @@ -0,0 +1,140 @@ +package org.bouncycastle.math.ec.custom.sec.test; + +import java.math.BigInteger; +import java.security.SecureRandom; + +import org.bouncycastle.asn1.sec.SECObjectIdentifiers; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.raw.Nat; + +import junit.framework.TestCase; + +public class SecP384R1FieldTest extends TestCase +{ + private static final SecureRandom RANDOM = new SecureRandom(); + + private static final X9ECParameters DP = CustomNamedCurves + .getByOID(SECObjectIdentifiers.secp384r1); + private static final BigInteger Q = DP.getCurve().getField().getCharacteristic(); + + public void testMultiply1() + { + int COUNT = 1000; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateMultiplyInput_Random(); + ECFieldElement y = generateMultiplyInput_Random(); + + BigInteger X = x.toBigInteger(), Y = y.toBigInteger(); + BigInteger R = X.multiply(Y).mod(Q); + + ECFieldElement z = x.multiply(y); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + public void testMultiply2() + { + int COUNT = 100; + ECFieldElement[] inputs = new ECFieldElement[COUNT]; + BigInteger[] INPUTS = new BigInteger[COUNT]; + + for (int i = 0; i < inputs.length; ++i) + { + inputs[i] = generateMultiplyInput_Random(); + INPUTS[i] = inputs[i].toBigInteger(); + } + + for (int j = 0; j < inputs.length; ++j) + { + for (int k = 0; k < inputs.length; ++k) + { + BigInteger R = INPUTS[j].multiply(INPUTS[k]).mod(Q); + + ECFieldElement z = inputs[j].multiply(inputs[k]); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + } + + public void testSquare() + { + int COUNT = 1000; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateMultiplyInput_Random(); + + BigInteger X = x.toBigInteger(); + BigInteger R = X.multiply(X).mod(Q); + + ECFieldElement z = x.square(); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + public void testSquare_CarryBug() + { + int COUNT = 100; + + for (int i = 0; i < COUNT; ++i) + { + ECFieldElement x = generateSquareInput_CarryBug(); + + BigInteger X = x.toBigInteger(); + BigInteger R = X.multiply(X).mod(Q); + + ECFieldElement z = x.square(); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + } + + /* + * Based on another example input demonstrating the carry propagation bug in Nat192.square, as + * reported by Joseph Friel on dev-crypto. + */ + public void testSquare_CarryBug_Reported() + { + ECFieldElement x = fe(new BigInteger("2fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd", 16)); + + BigInteger X = x.toBigInteger(); + BigInteger R = X.multiply(X).mod(Q); + + ECFieldElement z = x.square(); + BigInteger Z = z.toBigInteger(); + + assertEquals(R, Z); + } + + private ECFieldElement fe(BigInteger x) + { + return DP.getCurve().fromBigInteger(x); + } + + private ECFieldElement generateMultiplyInput_Random() + { + return fe(new BigInteger(DP.getCurve().getFieldSize() + 32, RANDOM).mod(Q)); + } + + private ECFieldElement generateSquareInput_CarryBug() + { + int[] x = Nat.create(12); + x[0] = RANDOM.nextInt() >>> 1; + x[6] = 2; + x[10] = -1 << 16; + x[11] = -1; + + return fe(Nat.toBigInteger(12, x)); + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/test/AllTests.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/AllTests.java new file mode 100644 index 00000000..4b8ffdee --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/AllTests.java @@ -0,0 +1,64 @@ +package org.bouncycastle.math.ec.test; + +import java.util.ArrayList; +import java.util.Enumeration; +import java.util.List; + +import junit.extensions.TestSetup; +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.bouncycastle.test.PrintTestResult; + +public class AllTests + extends TestCase +{ + public static void main (String[] args) + throws Exception + { + PrintTestResult.printResult( junit.textui.TestRunner.run(suite())); + } + + public static Test suite() + throws Exception + { + TestSuite suite = new TestSuite("EC Math tests"); + + suite.addTestSuite(ECAlgorithmsTest.class); + suite.addTestSuite(ECPointTest.class); + suite.addTestSuite(FixedPointTest.class); + + return new BCTestSetup(suite); + } + + static List enumToList(Enumeration en) + { + List rv = new ArrayList(); + + while (en.hasMoreElements()) + { + rv.add(en.nextElement()); + } + + return rv; + } + + static class BCTestSetup + extends TestSetup + { + public BCTestSetup(Test test) + { + super(test); + } + + protected void setUp() + { + + } + + protected void tearDown() + { + + } + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECAlgorithmsTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECAlgorithmsTest.java new file mode 100644 index 00000000..20b8d323 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECAlgorithmsTest.java @@ -0,0 +1,194 @@ +package org.bouncycastle.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 org.bouncycastle.asn1.x9.ECNamedCurveTable; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.asn1.x9.X9ECPoint; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECAlgorithms; +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECPoint; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; + +public class ECAlgorithmsTest extends TestCase +{ + private static final int SCALE = 4; + private static final SecureRandom RND = new SecureRandom(); + + public void testSumOfMultiplies() + { + X9ECParameters x9 = CustomNamedCurves.getByName("secp256r1"); + assertNotNull(x9); + doTestSumOfMultiplies(x9); + } + + // TODO Ideally, mark this test not to run by default + public void testSumOfMultipliesComplete() + { + ArrayList x9s = getTestCurves(); + Iterator it = x9s.iterator(); + while (it.hasNext()) + { + X9ECParameters x9 = (X9ECParameters)it.next(); + doTestSumOfMultiplies(x9); + } + } + + public void testSumOfTwoMultiplies() + { + X9ECParameters x9 = CustomNamedCurves.getByName("secp256r1"); + assertNotNull(x9); + doTestSumOfTwoMultiplies(x9); + } + + // TODO Ideally, mark this test not to run by default + public void testSumOfTwoMultipliesComplete() + { + ArrayList x9s = getTestCurves(); + Iterator it = x9s.iterator(); + while (it.hasNext()) + { + X9ECParameters x9 = (X9ECParameters)it.next(); + doTestSumOfTwoMultiplies(x9); + } + } + + private void doTestSumOfMultiplies(X9ECParameters x9) + { + 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]); + } + } + + private void doTestSumOfTwoMultiplies(X9ECParameters x9) + { + 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, new X9ECPoint(c.importPoint(x9.getG()), false), x9.getN(), x9.getH())); + } + } + } + + public static Test suite() + { + return new TestSuite(ECAlgorithmsTest.class); + } + +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointPerformanceTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointPerformanceTest.java new file mode 100644 index 00000000..9be8d3ea --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointPerformanceTest.java @@ -0,0 +1,198 @@ +package org.bouncycastle.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.bouncycastle.asn1.ASN1ObjectIdentifier; +import org.bouncycastle.asn1.x9.ECNamedCurveTable; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.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/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointTest.java new file mode 100644 index 00000000..f53c9828 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/ECPointTest.java @@ -0,0 +1,737 @@ +package org.bouncycastle.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.Random; +import java.util.Set; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.bouncycastle.asn1.x9.ECNamedCurveTable; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.asn1.x9.X9ECPoint; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECAlgorithms; +import org.bouncycastle.math.ec.ECConstants; +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.ec.WNafUtil; +import org.bouncycastle.util.Arrays; +import org.bouncycastle.util.BigIntegers; +import org.bouncycastle.util.Integers; +import org.bouncycastle.util.encoders.Hex; + +/** + * Test class for {@link org.bouncycastle.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("1063"); + + 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 = { 1, 5, 4, 10, 234, 1024, 817, 912 }; + + 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[i], fp.infinity); + } + + for (int i = 0; i < f2m.p.length; i++) + { + implTestAllPoints(f2m.p[i], 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()); + + int logSize = 32 - Integers.numberOfLeadingZeros(curve.getFieldSize() - 1); + int rounds = Math.max(2, Math.min(10, 32 - 3 * logSize)); + + ECPoint p = q; + for (int i = 0; i < rounds; ++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); + + ECFieldElement zero = c.fromBigInteger(BigInteger.ZERO); + assertEquals(zero, zero.sqrt()); + + ECFieldElement one = c.fromBigInteger(BigInteger.ONE); + assertEquals(one, one.sqrt()); + + for (int i = 0; i < 20; ++i) + { + BigInteger x = BigIntegers.createRandomInRange(ECConstants.TWO, pMinusOne, secRand); + ECFieldElement fe = c.fromBigInteger(x); + ECFieldElement root = fe.sqrt(); + + if (root == null) + { + assertEquals(pMinusOne, x.modPow(legendreExponent, p)); + } + else + { + assertEquals(fe, root.square()); + } + } + } + else if (ECAlgorithms.isF2mCurve(c)) + { + int m = c.getFieldSize(); + BigInteger x = new BigInteger(m, secRand); + ECFieldElement fe = c.fromBigInteger(x); + for (int i = 0; i < 100; ++i) + { + ECFieldElement sq = fe.square(); + ECFieldElement check = sq.sqrt(); + assertEquals(fe, check); + fe = sq; + } + } + } + + private void implValidityTest(ECCurve c, ECPoint g) + { + assertTrue(g.isValid()); + + if (ECAlgorithms.isF2mCurve(c)) + { + BigInteger h = c.getCofactor(); + if (null != h) + { + if (!h.testBit(0)) + { + ECFieldElement sqrtB = c.getB().sqrt(); + ECPoint order2 = c.createPoint(ECConstants.ZERO, sqrtB.toBigInteger()); + assertTrue(order2.twice().isInfinity()); + assertFalse(order2.isValid()); + ECPoint bad2 = g.add(order2); + assertFalse(bad2.isValid()); + ECPoint good2 = bad2.add(order2); + assertTrue(good2.isValid()); + + if (!h.testBit(1)) + { + ECFieldElement L = solveQuadraticEquation(c, c.getA()); + assertNotNull(L); + ECFieldElement T = sqrtB; + ECFieldElement x = T.sqrt(); + ECFieldElement y = T.add(x.multiply(L)); + ECPoint order4 = c.createPoint(x.toBigInteger(), y.toBigInteger()); + assertTrue(order4.twice().equals(order2)); + assertFalse(order4.isValid()); + ECPoint bad4_1 = g.add(order4); + assertFalse(bad4_1.isValid()); + ECPoint bad4_2 = bad4_1.add(order4); + assertFalse(bad4_2.isValid()); + ECPoint bad4_3 = bad4_2.add(order4); + assertFalse(bad4_3.isValid()); + ECPoint good4 = bad4_3.add(order4); + assertTrue(good4.isValid()); + } + } + } + } + } + + 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); + + implValidityTest(c, g); + } + } + } + + /** + * 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 x9A = ECNamedCurveTable.getByName(name); + X9ECParameters x9B = CustomNamedCurves.getByName(name); + + if (x9A != null && x9B != null) + { + assertEquals(x9A.getCurve().getField(), x9B.getCurve().getField()); + assertEquals(x9A.getCurve().getA().toBigInteger(), x9B.getCurve().getA().toBigInteger()); + assertEquals(x9A.getCurve().getB().toBigInteger(), x9B.getCurve().getB().toBigInteger()); + assertOptionalValuesAgree(x9A.getCurve().getCofactor(), x9B.getCurve().getCofactor()); + assertOptionalValuesAgree(x9A.getCurve().getOrder(), x9B.getCurve().getOrder()); + + assertPointsEqual("Custom curve base-point inconsistency", x9A.getG(), x9B.getG()); + + assertEquals(x9A.getH(), x9B.getH()); + assertEquals(x9A.getN(), x9B.getN()); + assertOptionalValuesAgree(x9A.getSeed(), x9B.getSeed()); + + BigInteger k = new BigInteger(x9A.getN().bitLength(), secRand); + ECPoint pA = x9A.getG().multiply(k); + ECPoint pB = x9B.getG().multiply(k); + assertPointsEqual("Custom curve multiplication inconsistency", pA, pB); + } + + if (x9A != null) + { + implAddSubtractMultiplyTwiceEncodingTestAllCoords(x9A); + } + + if (x9B != null) + { + implAddSubtractMultiplyTwiceEncodingTestAllCoords(x9B); + } + } + } + + public void testExampleFpB0() throws Exception + { + /* + * The supersingular curve y^2 = x^3 - 3.x (i.e. with 'B' == 0) from RFC 6508 2.1, with + * curve parameters from RFC 6509 Appendix A. + */ + BigInteger p = fromHex( + "997ABB1F0A563FDA65C61198DAD0657A" + + "416C0CE19CB48261BE9AE358B3E01A2E" + + "F40AAB27E2FC0F1B228730D531A59CB0" + + "E791B39FF7C88A19356D27F4A666A6D0" + + "E26C6487326B4CD4512AC5CD65681CE1" + + "B6AFF4A831852A82A7CF3C521C3C09AA" + + "9F94D6AF56971F1FFCE3E82389857DB0" + + "80C5DF10AC7ACE87666D807AFEA85FEB"); + BigInteger a = p.subtract(BigInteger.valueOf(3)); + BigInteger b = BigInteger.valueOf(0); + byte[] S = null; + BigInteger n = p.add(BigInteger.valueOf(1)).shiftRight(2); + BigInteger h = BigInteger.valueOf(4); + + ECCurve curve = configureCurve(new ECCurve.Fp(p, a, b, n, h)); + + X9ECPoint G = configureBasepoint(curve, "04" + // Px + + "53FC09EE332C29AD0A7990053ED9B52A" + + "2B1A2FD60AEC69C698B2F204B6FF7CBF" + + "B5EDB6C0F6CE2308AB10DB9030B09E10" + + "43D5F22CDB9DFA55718BD9E7406CE890" + + "9760AF765DD5BCCB337C86548B72F2E1" + + "A702C3397A60DE74A7C1514DBA66910D" + + "D5CFB4CC80728D87EE9163A5B63F73EC" + + "80EC46C4967E0979880DC8ABEAE63895" + // Py + + "0A8249063F6009F1F9F1F0533634A135" + + "D3E82016029906963D778D821E141178" + + "F5EA69F4654EC2B9E7F7F5E5F0DE55F6" + + "6B598CCF9A140B2E416CFF0CA9E032B9" + + "70DAE117AD547C6CCAD696B5B7652FE0" + + "AC6F1E80164AA989492D979FC5A4D5F2" + + "13515AD7E9CB99A980BDAD5AD5BB4636" + + "ADB9B5706A67DCDE75573FD71BEF16D7"); + + X9ECParameters x9 = new X9ECParameters(curve, G, n, h, S); + + implAddSubtractMultiplyTwiceEncodingTestAllCoords(x9); + } + + private void assertPointsEqual(String message, ECPoint a, ECPoint b) + { + // NOTE: We intentionally test points for equality in both directions + assertEquals(message, a, b); + assertEquals(message, b, a); + } + + private void assertOptionalValuesAgree(Object a, Object b) + { + if (a != null && b != null) + { + assertEquals(a, b); + } + } + + private void assertOptionalValuesAgree(byte[] a, byte[] b) + { + if (a != null && b != null) + { + assertTrue(Arrays.areEqual(a, b)); + } + } + + private static X9ECPoint configureBasepoint(ECCurve curve, String encoding) + { + X9ECPoint G = new X9ECPoint(curve, Hex.decode(encoding)); + WNafUtil.configureBasepoint(G.getPoint()); + return G; + } + + private static ECCurve configureCurve(ECCurve curve) + { + return curve; + } + + private List enumToList(Enumeration en) + { + List rv = new ArrayList(); + + while (en.hasMoreElements()) + { + rv.add(en.nextElement()); + } + + return rv; + } + + private static BigInteger fromHex( + String hex) + { + return new BigInteger(1, Hex.decode(hex)); + } + + private static ECFieldElement solveQuadraticEquation(ECCurve c, ECFieldElement rhs) + { + if (rhs.isZero()) + { + return rhs; + } + + ECFieldElement gamma, z, zeroElement = c.fromBigInteger(ECConstants.ZERO); + + int m = c.getFieldSize(); + Random rand = new Random(); + do + { + ECFieldElement t = c.fromBigInteger(new BigInteger(m, rand)); + z = zeroElement; + ECFieldElement w = rhs; + for (int i = 1; i < m; i++) + { + ECFieldElement w2 = w.square(); + z = z.square().add(w2.multiply(t)); + w = w2.add(rhs); + } + if (!w.isZero()) + { + return null; + } + gamma = z.square().add(z); + } + while (gamma.isZero()); + + return z; + } + + public static Test suite() + { + return new TestSuite(ECPointTest.class); + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/ec/test/F2mProofer.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/F2mProofer.java new file mode 100644 index 00000000..b6875203 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/F2mProofer.java @@ -0,0 +1,204 @@ +package org.bouncycastle.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.bouncycastle.asn1.sec.SECNamedCurves; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.util.BigIntegers; + +public class F2mProofer +{ + private static final int NUM_SAMPLES = 1000; + + private static final String PATH = "crypto/test/src/org/bouncycastle/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 = BigIntegers.createRandomBigInteger(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/bcprov/src/test/java/org/bouncycastle/math/ec/test/FixedPointTest.java b/bcprov/src/test/java/org/bouncycastle/math/ec/test/FixedPointTest.java new file mode 100644 index 00000000..08d4c087 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/ec/test/FixedPointTest.java @@ -0,0 +1,90 @@ +package org.bouncycastle.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 org.bouncycastle.asn1.x9.ECNamedCurveTable; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.crypto.ec.CustomNamedCurves; +import org.bouncycastle.math.ec.ECAlgorithms; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.ec.FixedPointCombMultiplier; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; + +public class FixedPointTest + extends TestCase +{ + private static final SecureRandom RANDOM = new SecureRandom(); + + private static final int TESTS_PER_CURVE = 5; + + public void testFixedPointMultiplier() + { + final FixedPointCombMultiplier M = new FixedPointCombMultiplier(); + + 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 x9A = ECNamedCurveTable.getByName(name); + X9ECParameters x9B = CustomNamedCurves.getByName(name); + + X9ECParameters x9 = x9B != null ? x9B : x9A; + + for (int i = 0; i < TESTS_PER_CURVE; ++i) + { + BigInteger k = new BigInteger(x9.getN().bitLength(), RANDOM); + ECPoint pRef = ECAlgorithms.referenceMultiply(x9.getG(), k); + + if (x9A != null) + { + ECPoint pA = M.multiply(x9A.getG(), k); + assertPointsEqual("Standard curve fixed-point failure", pRef, pA); + } + + if (x9B != null) + { + ECPoint pB = M.multiply(x9B.getG(), k); + assertPointsEqual("Custom curve fixed-point failure", pRef, pB); + } + } + } + } + + 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) + { + // NOTE: We intentionally test points for equality in both directions + assertEquals(message, a, b); + assertEquals(message, b, a); + } + + public static Test suite() + { + return new TestSuite(FixedPointTest.class); + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/raw/test/AllTests.java b/bcprov/src/test/java/org/bouncycastle/math/raw/test/AllTests.java new file mode 100644 index 00000000..c15cb94d --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/raw/test/AllTests.java @@ -0,0 +1,46 @@ +package org.bouncycastle.math.raw.test; + +import junit.extensions.TestSetup; +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.bouncycastle.test.PrintTestResult; + +public class AllTests + extends TestCase +{ + public static void main (String[] args) + throws Exception + { + PrintTestResult.printResult( junit.textui.TestRunner.run(suite())); + } + + public static Test suite() + throws Exception + { + TestSuite suite = new TestSuite("Raw math tests"); + + suite.addTest(InterleaveTest.suite()); + + return new BCTestSetup(suite); + } + + static class BCTestSetup + extends TestSetup + { + public BCTestSetup(Test test) + { + super(test); + } + + protected void setUp() + { + + } + + protected void tearDown() + { + + } + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/raw/test/InterleaveTest.java b/bcprov/src/test/java/org/bouncycastle/math/raw/test/InterleaveTest.java new file mode 100644 index 00000000..d701030b --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/raw/test/InterleaveTest.java @@ -0,0 +1,86 @@ +package org.bouncycastle.math.raw.test; + +import java.security.SecureRandom; + +import org.bouncycastle.math.raw.Interleave; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; + +public class InterleaveTest extends TestCase +{ + private static final int ITERATIONS = 1000; + + private static final SecureRandom R = new SecureRandom(); + + public void testExpand8To16() + { + // NOTE: Just test all inputs here + for (int iteration = 0; iteration < 256; ++iteration) + { + // NOTE: Implementation is expected to mask input + int x = iteration | (R.nextInt() << 8); + int expected = (int)referenceShuffle(x & 0xFFL); + int actual = Interleave.expand8to16(x); + assertEquals(expected, actual); + } + } + + public void testExpand16To32() + { + for (int iteration = 0; iteration < ITERATIONS; ++iteration) + { + // NOTE: Implementation is expected to mask input + int x = R.nextInt(); + int expected = (int)referenceShuffle(x & 0xFFFFL); + int actual = Interleave.expand16to32(x); + assertEquals(expected, actual); + } + } + + public void testExpand32To64() + { + for (int iteration = 0; iteration < ITERATIONS; ++iteration) + { + int x = R.nextInt(); + long expected = referenceShuffle(x & 0xFFFFFFFFL); + long actual = Interleave.expand32to64(x); + assertEquals(expected, actual); + } + } + + public void testExpand64To128() + { + for (int iteration = 0; iteration < ITERATIONS; ++iteration) + { + long x = R.nextLong(); + long expected = referenceShuffle(x); + long[] actual = new long[9]; + int offset = iteration % 8; + // NOTE: Implementation must overwrite existing values + actual[offset ] = R.nextLong(); + actual[offset + 1] = R.nextLong(); + Interleave.expand64To128(x, actual, offset); + assertEquals((expected ) & 0x5555555555555555L, actual[offset ]); + assertEquals((expected >>> 1) & 0x5555555555555555L, actual[offset + 1]); + } + } + + public static Test suite() + { + return new TestSuite(InterleaveTest.class); + } + + private static long referenceShuffle(long x) + { + long result = 0, y = x >>> 32; + for (int bit = 0; bit < 32; ++bit) + { + long selector = 1L << bit; + result |= ((x & selector) << (bit )); + result |= ((y & selector) << (bit + 1)); + } + return result; + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/test/AllTests.java b/bcprov/src/test/java/org/bouncycastle/math/test/AllTests.java new file mode 100644 index 00000000..f849b508 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/test/AllTests.java @@ -0,0 +1,46 @@ +package org.bouncycastle.math.test; + +import junit.extensions.TestSetup; +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.bouncycastle.test.PrintTestResult; + +public class AllTests + extends TestCase +{ + public static void main (String[] args) + throws Exception + { + PrintTestResult.printResult( junit.textui.TestRunner.run(suite())); + } + + public static Test suite() + throws Exception + { + TestSuite suite = new TestSuite("Math tests"); + + suite.addTestSuite(PrimesTest.class); + + return new BCTestSetup(suite); + } + + static class BCTestSetup + extends TestSetup + { + public BCTestSetup(Test test) + { + super(test); + } + + protected void setUp() + { + + } + + protected void tearDown() + { + + } + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/math/test/PrimesTest.java b/bcprov/src/test/java/org/bouncycastle/math/test/PrimesTest.java new file mode 100644 index 00000000..13af4cac --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/math/test/PrimesTest.java @@ -0,0 +1,183 @@ +package org.bouncycastle.math.test; + +import java.math.BigInteger; +import java.security.SecureRandom; + +import junit.framework.Test; +import junit.framework.TestCase; +import junit.framework.TestSuite; +import org.bouncycastle.crypto.Digest; +import org.bouncycastle.crypto.digests.SHA1Digest; +import org.bouncycastle.crypto.digests.SHA256Digest; +import org.bouncycastle.math.Primes; +import org.bouncycastle.math.Primes.MROutput; +import org.bouncycastle.math.Primes.STOutput; +import org.bouncycastle.util.Arrays; +import org.bouncycastle.util.BigIntegers; + +public class PrimesTest extends TestCase +{ + private static final int ITERATIONS = 10; + private static final int PRIME_BITS = 256; + private static final int PRIME_CERTAINTY = 100; + + private static final BigInteger TWO = BigInteger.valueOf(2); + + private static final SecureRandom R = new SecureRandom(); + + public void testHasAnySmallFactors() + { + for (int iterations = 0; iterations < ITERATIONS; ++iterations) + { + BigInteger prime = randomPrime(); + assertFalse(Primes.hasAnySmallFactors(prime)); + + // NOTE: Loop through ALL small values to be sure no small primes are missing + for (int smallFactor = 2; smallFactor <= Primes.SMALL_FACTOR_LIMIT; ++smallFactor) + { + BigInteger nonPrimeWithSmallFactor = BigInteger.valueOf(smallFactor).multiply(prime); + assertTrue(Primes.hasAnySmallFactors(nonPrimeWithSmallFactor)); + } + } + } + + public void testEnhancedMRProbablePrime() + { + int mrIterations = (PRIME_CERTAINTY + 1) / 2; + for (int iterations = 0; iterations < ITERATIONS; ++iterations) + { + BigInteger prime = randomPrime(); + MROutput mr = Primes.enhancedMRProbablePrimeTest(prime, R, mrIterations); + assertFalse(mr.isProvablyComposite()); + assertFalse(mr.isNotPrimePower()); + assertNull(mr.getFactor()); + + BigInteger primePower = prime; + for (int i = 0; i <= (iterations % 8); ++i) + { + primePower = primePower.multiply(prime); + } + + MROutput mr2 = Primes.enhancedMRProbablePrimeTest(primePower, R, mrIterations); + assertTrue(mr2.isProvablyComposite()); + assertFalse(mr2.isNotPrimePower()); + assertEquals(mr2.getFactor(), prime); + + BigInteger nonPrimePower = randomPrime().multiply(prime); + MROutput mr3 = Primes.enhancedMRProbablePrimeTest(nonPrimePower, R, mrIterations); + assertTrue(mr3.isProvablyComposite()); + assertTrue(mr3.isNotPrimePower()); + assertNull(mr.getFactor()); + } + } + + public void testMRProbablePrime() + { + int mrIterations = (PRIME_CERTAINTY + 1) / 2; + for (int iterations = 0; iterations < ITERATIONS; ++iterations) + { + BigInteger prime = randomPrime(); + assertTrue(Primes.isMRProbablePrime(prime, R, mrIterations)); + + BigInteger nonPrime = randomPrime().multiply(prime); + assertFalse(Primes.isMRProbablePrime(nonPrime, R, mrIterations)); + } + } + + public void testMRProbablePrimeToBase() + { + int mrIterations = (PRIME_CERTAINTY + 1) / 2; + for (int iterations = 0; iterations < ITERATIONS; ++iterations) + { + BigInteger prime = randomPrime(); + assertTrue(referenceIsMRProbablePrime(prime, mrIterations)); + + BigInteger nonPrime = randomPrime().multiply(prime); + assertFalse(referenceIsMRProbablePrime(nonPrime, mrIterations)); + } + } + + public void testSTRandomPrime() + { + Digest[] digests = new Digest[]{ new SHA1Digest(), new SHA256Digest() }; + for (int digestIndex = 0; digestIndex < digests.length; ++digestIndex) + { + int coincidenceCount = 0; + + Digest digest = digests[digestIndex]; + for (int iterations = 0; iterations < ITERATIONS; ++iterations) + { + try + { + byte[] inputSeed = new byte[16]; + R.nextBytes(inputSeed); + + STOutput st = Primes.generateSTRandomPrime(digest, PRIME_BITS, inputSeed); + assertTrue(isPrime(st.getPrime())); + + STOutput st2 = Primes.generateSTRandomPrime(digest, PRIME_BITS, inputSeed); + assertEquals(st.getPrime(), st2.getPrime()); + assertEquals(st.getPrimeGenCounter(), st2.getPrimeGenCounter()); + assertTrue(Arrays.areEqual(st.getPrimeSeed(), st2.getPrimeSeed())); + + for (int i = 0; i < inputSeed.length; ++i) + { + inputSeed[i] ^= 0xFF; + } + + STOutput st3 = Primes.generateSTRandomPrime(digest, PRIME_BITS, inputSeed); + assertTrue(!st.getPrime().equals(st3.getPrime())); + assertFalse(Arrays.areEqual(st.getPrimeSeed(), st3.getPrimeSeed())); + + if (st.getPrimeGenCounter() == st3.getPrimeGenCounter()) + { + ++coincidenceCount; + } + } + catch (IllegalStateException e) + { + if (e.getMessage().startsWith("Too many iterations")) + { + --iterations; + continue; + } + + throw e; + } + } + + assertTrue(coincidenceCount * coincidenceCount < ITERATIONS); + } + } + + public static Test suite() + { + return new TestSuite(PrimesTest.class); + } + + private static boolean referenceIsMRProbablePrime(BigInteger x, int numBases) + { + BigInteger xSubTwo = x.subtract(TWO); + + for (int i = 0; i < numBases; ++i) + { + BigInteger b = BigIntegers.createRandomInRange(TWO, xSubTwo, R); + if (!Primes.isMRProbablePrimeToBase(x, b)) + { + return false; + } + } + + return true; + } + + private static boolean isPrime(BigInteger x) + { + return x.isProbablePrime(PRIME_CERTAINTY); + } + + private static BigInteger randomPrime() + { + return BigIntegers.createRandomPrime(PRIME_BITS, PRIME_CERTAINTY, R); + } +} diff --git a/bcprov/src/test/java/org/bouncycastle/test/PrintTestResult.java b/bcprov/src/test/java/org/bouncycastle/test/PrintTestResult.java new file mode 100644 index 00000000..2cca70b2 --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/test/PrintTestResult.java @@ -0,0 +1,36 @@ +package org.bouncycastle.test; + + +import java.util.Enumeration; + +import junit.framework.TestResult; + +public class PrintTestResult +{ + public static void printResult(TestResult result) + { + Enumeration e = result.failures(); + if (e != null) + { + while (e.hasMoreElements()) + { + System.out.println(e.nextElement()); + } + } + + e = result.errors(); + if (e != null) + { + while (e.hasMoreElements()) + { + System.out.println(e.nextElement()); + } + } + + if (!result.wasSuccessful()) + { + System.exit(1); + } + } +} + diff --git a/bcprov/src/test/java/org/bouncycastle/util/Times.java b/bcprov/src/test/java/org/bouncycastle/util/Times.java new file mode 100644 index 00000000..617d00bd --- /dev/null +++ b/bcprov/src/test/java/org/bouncycastle/util/Times.java @@ -0,0 +1,9 @@ +package org.bouncycastle.util; + +public final class Times +{ + public static long nanoTime() + { + return System.nanoTime(); + } +} |