Adding a generator for tests to the modexp model and core.

10 files changed, 227 insertions, 0 deletions

diff --git a/src/testgenerator/.classpath b/src/testgenerator/.classpath
new file mode 100644
index 0000000..fb565a5
--- /dev/null
+++ b/src/testgenerator/.classpath
@@ -0,0 +1,6 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" path="src"/>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.7"/>
+	<classpathentry kind="output" path="bin"/>
+</classpath>
diff --git a/src/testgenerator/.gitignore b/src/testgenerator/.gitignore
new file mode 100644
index 0000000..ae3c172
--- /dev/null
+++ b/src/testgenerator/.gitignore
@@ -0,0 +1 @@
+/bin/
diff --git a/src/testgenerator/.project b/src/testgenerator/.project
new file mode 100644
index 0000000..aa04832
--- /dev/null
+++ b/src/testgenerator/.project
@@ -0,0 +1,17 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>TestGenerator</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
diff --git a/src/testgenerator/.settings/org.eclipse.jdt.core.prefs b/src/testgenerator/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..7341ab1
--- /dev/null
+++ b/src/testgenerator/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,11 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.7
+org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
+org.eclipse.jdt.core.compiler.compliance=1.7
+org.eclipse.jdt.core.compiler.debug.lineNumber=generate
+org.eclipse.jdt.core.compiler.debug.localVariable=generate
+org.eclipse.jdt.core.compiler.debug.sourceFile=generate
+org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
+org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
+org.eclipse.jdt.core.compiler.source=1.7
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGenerator.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGenerator.java
new file mode 100644
index 0000000..af5850b
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGenerator.java
@@ -0,0 +1,19 @@
+package org.crypttech.modexp.testgenerator;
+
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.crypttech.modexp.testgenerator.format.GeneratorC;
+
+public class TestGenerator {
+	public static void main(String[] argv) throws Exception {
+		List<TestVector> vectors = new ArrayList<TestVector>();
+		vectors.addAll(TestGeneratorBasic.getTestVectors());
+		PrintWriter pw = new PrintWriter("../model/c/src/autogenerated_tests.c");
+		try (GeneratorC genC = new GeneratorC(pw)) {
+			for (TestVector vector : vectors)
+				genC.format(vector);
+		}
+	}
+}
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGeneratorBasic.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGeneratorBasic.java
new file mode 100644
index 0000000..71b56ac
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestGeneratorBasic.java
@@ -0,0 +1,35 @@
+package org.crypttech.modexp.testgenerator;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+public class TestGeneratorBasic {
+	public static final List<TestVector> getTestVectors() {
+		Random rng = new Random(0); //any static seed
+		ArrayList<TestVector> list = new ArrayList<TestVector>();
+		
+		generateTestVectors(rng, list, 33, 2);
+		generateTestVectors(rng, list, 30, 1);
+		//generateTestVectors(rng, list, 32, 1); //will generate failing tests in C model 
+		//generateTestVectors(rng, list, 31, 1); //will generate failing tests in C model 
+		return list;
+	}
+
+	private static void generateTestVectors(Random rng,
+			ArrayList<TestVector> list, int bitLength, int wordLength) {
+		for(int i = 0; i < 10; i++) {
+			final long seed = rng.nextLong();
+			rng.setSeed(seed);
+			BigInteger m = BigInteger.probablePrime(bitLength, rng);
+			BigInteger x = BigInteger.probablePrime(bitLength, rng);
+			BigInteger e = BigInteger.probablePrime(bitLength, rng);
+			BigInteger z = x.modPow(e, m);
+			TestVector tv = Util.generateTestVector("BASIC", Long.toString(seed), wordLength, m, x, e, z);
+			list.add(tv);
+		}
+	}
+
+
+}
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestVector.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestVector.java
new file mode 100644
index 0000000..a9931c1
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/TestVector.java
@@ -0,0 +1,23 @@
+package org.crypttech.modexp.testgenerator;
+
+public class TestVector {
+	public final String generator; 
+	public final String seed; 
+	public final int length; 
+	public final int[] X; 
+	public final int[] E; 
+	public final int[] M; 
+	public final int[] expected;
+	
+	public TestVector(String generator, String seed, int length, int[] x,
+			int[] e, int[] m, int[] expected) {
+		super();
+		this.generator = generator;
+		this.seed = seed;
+		this.length = length;
+		X = x;
+		E = e;
+		M = m;
+		this.expected = expected;
+	}
+}
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/Util.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/Util.java
new file mode 100644
index 0000000..5fbe052
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/Util.java
@@ -0,0 +1,28 @@
+package org.crypttech.modexp.testgenerator;
+
+import java.math.BigInteger;
+
+public class Util {
+	public static TestVector generateTestVector(String generator, String seed, int length, 
+			BigInteger m, BigInteger x, BigInteger e, BigInteger z) {
+		//System.out.printf("%s %s %s %s\n", m.toString(16), x.toString(16), e.toString(16), z.toString(16));
+		int[] mi = toInt(length, m);
+		int[] xi = toInt(length, x);
+		int[] ei = toInt(length, e);
+		int[] zi = toInt(length, z);
+		return new TestVector(generator, seed, length, xi, ei, mi, zi);
+	}
+
+	
+	public static int[] toInt(int length, BigInteger bi) {
+		byte[] ba = bi.toByteArray();
+		int[] ia = new int[length];
+		for (int j = ba.length-1; j >= 0; j--) {
+			int changeByte = ((ba.length-1-j)%4);
+			int jj = length -1 - (ba.length-1-j)/4;
+			ia[jj] |= (ba[j] & 0xff) << (changeByte*8);
+		}
+		return ia;
+	}
+
+}
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/GeneratorC.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/GeneratorC.java
new file mode 100644
index 0000000..fbfd852
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/GeneratorC.java
@@ -0,0 +1,61 @@
+package org.crypttech.modexp.testgenerator.format;
+
+import java.io.PrintWriter;
+
+import org.crypttech.modexp.testgenerator.TestVector;
+
+public class GeneratorC extends ModExpTestFormater {
+	private static final char LF = (char) 10;
+
+	public GeneratorC(PrintWriter pw) {
+		super(pw);
+		out("#include <stdio.h>" + LF);
+		out("#include <stdlib.h>" + LF);
+		out("#include \"montgomery_array.h\"" + LF);
+		out("#include \"bignum_uint32_t.h\"" + LF);
+	}
+
+	StringBuilder footer = new StringBuilder();
+
+	@Override
+	public void format(TestVector testVector) {
+		String testname = ("autogenerated_" + testVector.generator + "_" + testVector.seed)
+				.replace("-", "M");
+		footer.append("  ").append(testname).append("();").append(LF);
+
+		StringBuilder sb = new StringBuilder();
+		sb.append("void ").append(testname).append("(void) {").append(LF);
+		sb.append("  printf(\"=== ").append(testname).append(" ===\\n\");")
+				.append(LF);
+		appendCArray(sb, "X", testVector.X);
+		appendCArray(sb, "E", testVector.E);
+		appendCArray(sb, "M", testVector.M);
+		appendCArray(sb, "expected", testVector.expected);
+		int[] Z = new int[testVector.length];
+		appendCArray(sb, "Z", Z);
+		sb.append("  mod_exp_array(").append(testVector.length)
+				.append(", X, E, M, Z);").append(LF);
+		sb.append("  assertArrayEquals(").append(testVector.length)
+				.append(", expected, Z);").append(LF);
+		sb.append("}").append(LF);
+		out(sb.toString());
+	}
+
+	private void appendCArray(StringBuilder sb, String arrayName, int[] array) {
+		sb.append("  uint32_t ").append(arrayName).append("[] = ");
+		sb.append("{ ");
+		for (int m : array)
+			sb.append(String.format("0x%08x, ", m));
+		sb.replace(sb.length() - 2, sb.length(), " };");
+		sb.append(LF);
+	}
+
+	@Override
+	public void close() throws Exception {
+		out("void autogenerated_tests(void) {" + LF);
+		out(footer.toString());
+		out("}" + LF);
+		super.close();
+	}
+
+}
diff --git a/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/ModExpTestFormater.java b/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/ModExpTestFormater.java
new file mode 100644
index 0000000..c15ca88
--- /dev/null
+++ b/src/testgenerator/src/org/crypttech/modexp/testgenerator/format/ModExpTestFormater.java
@@ -0,0 +1,26 @@
+package org.crypttech.modexp.testgenerator.format;
+
+import java.io.PrintWriter;
+
+import org.crypttech.modexp.testgenerator.TestVector;
+
+public abstract class ModExpTestFormater implements AutoCloseable {
+	private PrintWriter pw;
+	
+	public ModExpTestFormater(PrintWriter pw) {
+		this.pw = pw;
+	}
+	
+	public abstract void format(TestVector testVector);
+
+	protected final void out(String s) {
+		pw.print(s);
+	}
+	
+	@Override
+	public void close() throws Exception {
+		pw.close();
+	}
+	
+	
+}