ds.ov2.bignat
Class Testbignat

java.lang.Object
  ds.ov2.bignat.Testbignat

public class Testbignat
extends Object

Cardless test frame for the Bignat library. Tests various functionality of Bignat, Vector and Modulus and of some host data types on a conventional Java virtual machine, that is, not on a Java Card.

The test frame and parts of the tested sources require preprocessing with cpp, the C preprocessor. So compile with make and run the test frame with the script run-testbignat in the directory of the original sources (src/bignat).

The single tests are enabled with command line options. To see what test are available look at the options list produced by -h or -help. Apart from the options that enable specific tests there are also general options for setting the Bignat size or the number of rounds the tests are performed. Not all tests are sensible to all options, using test data files is for instance only supported in the vector exponent test (option -vec-exp).

The tests usually run with random data. In case an error is detected the test frame prints the relevant numbers for the test that failed and exits immediately. To repeat a test with some given numbers, numbers can be passed in via the option -i or -hex. The latter accepts the hex output produced by the test frame itself, that is, dots in the hex number are filtered out.

By using different defines for the cpp preprocessing different versions of the code can be selected (and tested). The following defines can be used.

BIGNAT_USE_INT

Use the int/long configuration of the Bignat library instead of byte/short.

OPT_DOUBLE_ADD

Optimization: In Montgomery multiplication do addition and Montgomery correction in one loop.

OPT_SKIP_DEVIDE

Optimization: Skip final division in Montgomery multiplication if not strictly neccessary.

OPT_SPECIAL_SQUARE

Optimization: Use a special squaring method instead of the general multiplication for squaring.

I tested the optimizations in this test frame. Here they only have marginal effect and two of them even slow down the code. I have not yet done measurements on the card.

The defines should be put into the CPPFLAGS makefile variable with a -D switch prepended. For instance

    CPPFLAGS:=-DOPT_SPECIAL_SQUARE
 

in src/ConfigMakefile or src/bignat/LocalMakefile. To set them on the command line use

    make 'CPPFLAGS=-DOPT_SPECIAL_SQUARE'
 

For a number of general topics see also the package description.

CPP Preprocessing

This class uses the following cpp defines: DOUBLE_DIGIT_TYPE

Execution Environment:

host

Author:

Hendrik Tews

Version:

$Revision: 1.36 $

Last Commit:

$Date: 2010-09-20 11:20:15 $ by $Author: tews $

Field Summary

private static short	bignat_size Bignat size of the -size option.
private static boolean	bignat_size_set Records whether bignat_size has been changed via the -size option.
private static BigInteger_inputs	fix_inputs User provided inputs.
static String	long_application_name Long name for diagnostics printing.
private static int	max_bits Bit size parameter for random BigInteger creation.
private static short	mont_bignat_size Montgomery size.
static Option[]	options Declaration of all options that this test frame recognizes.
private static Reference<String>	read_from_file Value of the -read option.
private static Reference<Integer>	rounds Value of the -rounds option.
private static Reference<Boolean>	run_add Remember the -add option.
private static Reference<Boolean>	run_convenience_exponent Remember the -conv-exp option.
private static Reference<Boolean>	run_convenience_vector_exponent Remember the -conv-vec-exp option.
private static Reference<Boolean>	run_double_mult Remember the -double-mult option.
private static Reference<Boolean>	run_exponent Remember the -exp option.
private static Reference<Boolean>	run_mont_mult Remember the -mont-mult option.
private static Reference<Boolean>	run_remainder_divide Remember the -div option.
private static Reference<Boolean>	run_slow_mult Remember the -mult option.
private static Reference<Boolean>	run_square_mult Remember the -mult-square option.
private static Reference<Boolean>	run_square_mult_4 Remember the -mult-square-4 option.
private static Reference<Boolean>	run_times_minus Remember the -times-minus option.
private static Reference<Boolean>	run_vector_exponent Remember the -vec-exp option.
static String	short_application_name Short name for diagnostics printing.
private static Reference<Integer>	vector_exponent_length Value of the -vec-exp-size option.
private static Reference<Integer>	vector_exponent_variable_bases Value of the -vec-exp-var option.
private static Reference<Integer>	verbosity Verbosity.
private static Reference<String>	write_to_file Value of the -write option.

Constructor Summary

protected

Testbignat() Static class, object creation disabled.

Method Summary

static void	main(String[] args) Main test frame method.
private static int	max_bits_from_size(int size) Computes the successor of numBits argument for the BigInteger.BigInteger(int, Random) constructor out of a Bignat byte size.
static void	print_bi_array(String intro_format, String line_start, BigInteger[] bi) Prints an array of BigIntegers in decimal and dotted hex.
static boolean	test_add_once(Random rand) Test Bignat.add once.
static void	test_add(Random rand) Test Bignat.add rounds times.
static void	test_convenience_exponent(Random rand) Test Convenience.exponent_mod rounds times with randomly generated numbers.
static void	test_convenience_vector_exponent(Random rand) Test Convenience.vector_exponent_mod rounds times with randomly generated numbers.
static boolean	test_double_mult_once(Random rand) Test Bignat.mult once.
static void	test_double_mult(Random rand) Test Bignat.mult rounds times.
static long[]	test_exponent_once(Random rand, BufferedReader data_in, PrintWriter data_out) Test Bignat.exponent_mod once.
static void	test_exponent(Random rand, BufferedReader data_in, PrintWriter data_out) Test Bignat.exponent_mod twice rounds times.
static boolean	test_montgomery_mult_once(Random rand) Test Bignat.montgomery_mult once.
static void	test_montgomery_mult(Random rand) Test Bignat.montgomery_mult rounds times.
static boolean	test_mult_mod_once(Random rand) Test Bignat.mult_mod once.
static void	test_mult_mod(Random rand) Test Bignat.mult_mod rounds times.
static boolean	test_remainder_divide_once(Random rand) Test Bignat.remainder_divide once.
static void	test_remainder_divide(Random rand) Test Bignat.remainder_divide rounds times.
static void	test_square_mult_4(Random rand) Test Bignat.squared_rsa_mult_4 rounds times.
static void	test_square_mult(Random rand) Test Bignat.squared_rsa_mult_2 rounds times.
static void	test_times_minus(Random rand) Test Bignat.times_minus once.
static long[]	test_vector_exponent_once(Random rand, BufferedReader data_in, PrintWriter data_out) Tests Vector.exponent_mod once.
static void	test_vector_exponent(Random rand, BufferedReader data_in, PrintWriter data_out) Tests Vector.exponent_mod twice rounds times.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

short_application_name

public static final String short_application_name

Short name for diagnostics printing. Currently "Testbignat".

See Also:

Constant Field Values

long_application_name

public static final String long_application_name

Long name for diagnostics printing. Currently "Bignat Testframe".

See Also:

Constant Field Values

run_add

private static Reference<Boolean> run_add

Remember the -add option.

run_times_minus

private static Reference<Boolean> run_times_minus

Remember the -times-minus option.

run_remainder_divide

private static Reference<Boolean> run_remainder_divide

Remember the -div option.

run_slow_mult

private static Reference<Boolean> run_slow_mult

Remember the -mult option.

run_double_mult

private static Reference<Boolean> run_double_mult

Remember the -double-mult option.

run_mont_mult

private static Reference<Boolean> run_mont_mult

Remember the -mont-mult option.

run_exponent

private static Reference<Boolean> run_exponent

Remember the -exp option.

run_vector_exponent

private static Reference<Boolean> run_vector_exponent

Remember the -vec-exp option.

run_convenience_exponent

private static Reference<Boolean> run_convenience_exponent

Remember the -conv-exp option.

run_convenience_vector_exponent

private static Reference<Boolean> run_convenience_vector_exponent

Remember the -conv-vec-exp option.

run_square_mult

private static Reference<Boolean> run_square_mult

Remember the -mult-square option.

run_square_mult_4

private static Reference<Boolean> run_square_mult_4

Remember the -mult-square-4 option.

bignat_size_set

private static boolean bignat_size_set

Records whether bignat_size has been changed via the -size option.

bignat_size

private static short bignat_size

Bignat size of the -size option. Defaults to 12.

mont_bignat_size

private static short mont_bignat_size

Montgomery size. Size used for numbers that come in touch with Montgomery multiplication. Depends on bignat_size and therefore on the -size option. Two digits less than #bignat_size. The number of bytes dependes on Bignat.size_multiplier.

vector_exponent_length

private static Reference<Integer> vector_exponent_length

Value of the -vec-exp-size option. Defaults to 5.

vector_exponent_variable_bases

private static Reference<Integer> vector_exponent_variable_bases

Value of the -vec-exp-var option. Controls for how much bases precomputed base factors are used in the vector exponent test (testing Vector.exponent_mod). Defaults to -1. A value of -1 means to use randomly many precomputed factors.

max_bits

private static int max_bits

Bit size parameter for random BigInteger creation. Depends on bignat_size.

rounds

private static Reference<Integer> rounds

Value of the -rounds option. Number of rounds every test is run. Defaults to 5000.

write_to_file

private static Reference<String> write_to_file

Value of the -write option. File to write test data to. Default value null means to not write the test data.

read_from_file

private static Reference<String> read_from_file

Value of the -read option. File to read test data from. Default value null means to not read any data from file.

verbosity

private static Reference<Integer> verbosity

Verbosity. Controls the amount of messages printed during the run. Set to 1 by -v, to 5 by -d, to 10 by -dd and to 15 by -ddd.

fix_inputs

private static BigInteger_inputs fix_inputs

User provided inputs.

options

public static Option[] options

Declaration of all options that this test frame recognizes.

Constructor Detail

Testbignat

protected Testbignat()

Static class, object creation disabled.

Method Detail

main

public static void main(String[] args)
                 throws FileNotFoundException,
                        IOException

Main test frame method. Parses the command line and runs all tests that have been enabled.

Parameters:

args - option array

Throws:

FileNotFoundException - in case the test data file specified via -read does not exist

IOException - for errors when reading or writing the test data files

max_bits_from_size

private static int max_bits_from_size(int size)

Computes the successor of numBits argument for the BigInteger.BigInteger(int, Random) constructor out of a Bignat byte size. The successor is needed because the result is used like

    new BigInteger(rand.nextInt(max_bits_from_size(...)), rand)
 

where rand is an instance of Random.

Parameters:

size - size in bytes

Returns:

8 * size + 1

print_bi_array

public static void print_bi_array(String intro_format,
                                  String line_start,
                                  BigInteger[] bi)

Prints an array of BigIntegers in decimal and dotted hex. Argument intro_format is a format string for the heading, for instance "array foo with %d elements\n". It must contain at most one integer conversion and should be terminated with a newline. An empty intro format effectively discards the heading. Argument line_start is printed at the beginning of each line, for instance "foo".

Parameters:

intro_format - Format string for the heading with at most one integer conversion (for the number of elements in bi)

line_start - array name string printed for each array element

bi - the BigIntegers to be printed

test_add_once

public static boolean test_add_once(Random rand)

Test Bignat.add once. Takes the summands from the fixed inputs, if available. Otherwise generates random summands of a random size below the configured Bignat size.

Contains no protection against generating an overflow in Bignat.add, which would be reported as a failure.

Parameters:

rand - randomness source

Returns:

true if the test succeeded.

To Do:

fix random generation of x_bi, why mont_bignat_size?, protect against overflow

test_add

public static void test_add(Random rand)

Test Bignat.add rounds times. Exit if a failure is detected. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source

test_times_minus

public static void test_times_minus(Random rand)

Test Bignat.times_minus once. Test arguments are generated randomly in a fashion to simulate the use of times_minus in division. Underflows are avoided. No fixed inputs are used.

Parameters:

rand - randomness source

test_remainder_divide_once

public static boolean test_remainder_divide_once(Random rand)

Test Bignat.remainder_divide once. If fixed inputs are available the divident and divisor are taken in this order from the fixed inputs. Otherwise they are generated randomly in such a way that with a probability of 5 percent the divident is bigger than the divisor.

Parameters:

rand - randomness source

Returns:

true if the test succeeded

test_remainder_divide

public static void test_remainder_divide(Random rand)

Test Bignat.remainder_divide rounds times. Exists if a test fails. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source

test_mult_mod_once

public static boolean test_mult_mod_once(Random rand)

Test Bignat.mult_mod once. If fixed inputs are available the factors and the modulus are taken from the fixed inputs in this order. Otherwise they are generated randomly with the side condition that the modulus is non-zero.

Parameters:

rand - randomness source

Returns:

true if the test succeeded

To Do:

fix random generation, why mont_bignat_size?

test_mult_mod

public static void test_mult_mod(Random rand)

Test Bignat.mult_mod rounds times. Exists on the first error. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source

test_double_mult_once

public static boolean test_double_mult_once(Random rand)

Test Bignat.mult once. If fixed inputs are available the factors are taken from there. Otherwise they are generated randomly.

Parameters:

rand - randomness source

Returns:

true if the test succeeds

To Do:

fix random generation of x_bi

test_double_mult

public static void test_double_mult(Random rand)

Test Bignat.mult rounds times. Exists on the first error. If fixed inputs are available they will be used.

Parameters:

rand - randomness source

test_montgomery_mult_once

public static boolean test_montgomery_mult_once(Random rand)

Test Bignat.montgomery_mult once. If fixed inputs are available the factors and the modulus are taken in this order from there. Otherwise they are generated randomly such that the modulus is odd.

Parameters:

rand - randomness source

Returns:

true if the test succeeds

test_montgomery_mult

public static void test_montgomery_mult(Random rand)

Test Bignat.montgomery_mult rounds times. Exists on the first error. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source

test_exponent_once

public static long[] test_exponent_once(Random rand,
                                        BufferedReader data_in,
                                        PrintWriter data_out)
                                 throws IOException

Test Bignat.exponent_mod once. Honours the -read and -write options. If 3 fixed inputs are available the base, the exponent and the modulus are taken from there. Otherwise, if -read was given, the data is taken from the next 3 lines of the input file. Otherwise they are generated randomly such that the base and the modulus have mont_bignat_size significant bytes, and the exponent has 10 percent of this size. If -write was given the data is written to the output file.

The time needed to compute the exponent with both the Bignat library and with BigInteger is measured and returned. For the Bignat library only the time for Bignat.exponent_mod is measured without the necessary preparations.

Exists if the test fails.

Parameters:

rand - randomness source

data_in - input data file or null for no input

data_out - output data file or null for no output throws IOException if reading from data_in fails

Throws:

IOException

test_exponent

public static void test_exponent(Random rand,
                                 BufferedReader data_in,
                                 PrintWriter data_out)
                          throws FileNotFoundException,
                                 IOException

Test Bignat.exponent_mod twice rounds times. The first time for warming the cache and JIT compilation, the second time for real measurements. Exists immediately in case of an error.

If fixed inputs are available, they will be used. Otherwise, if -read was given, the test data is taken from that file. After the first rounds test the file is reopened to do the real measurements with exactly the same data.

Without -read the test data is generated randomly. If -write was given the data is written to that file during the first rounds tests and read from there afterwards.

Exists on the first error.

Parameters:

rand - randomness source

data_in - input data file or null for no input file

data_out - output data file or null for no output

Throws:

FileNotFoundException - if reopening read_from_file fails throws IOException if reading from data_in fails XXXX

IOException

test_vector_exponent_once

public static long[] test_vector_exponent_once(Random rand,
                                               BufferedReader data_in,
                                               PrintWriter data_out)
                                        throws IOException

Tests Vector.exponent_mod once. Honours the -read and -write options. If enough fixed inputs are present vector_exponent_length bases, the same number of exponents and the modulus are taken from there in this order. Otherwise, if -read was given, the data is taken from the next 2 *vector_exponent_length+ 1 lines of the input file. Otherwise the data is generated randomly such that bases and modulus have mont_bignat_size significant bytes and the exponents are 10 percent of this size. If -write was given the data is written to the output file.

The time needed to compute the multi-exponent with both the Bignat library and with BigInteger is measured and returned. For the Bignat library only the time for Vector.exponent_mod is measured without the necessary preparations.

Exits if an error is detected.

Parameters:

rand - randomness source

data_in - input data file or null for no input

data_out - output data file or null for no output

Returns:

a pair {bignat_time, biginteger_time} of the measured computation time in nanoseconds. throws IOException if reading from data_in fails

Throws:

IOException

test_vector_exponent

public static void test_vector_exponent(Random rand,
                                        BufferedReader data_in,
                                        PrintWriter data_out)
                                 throws FileNotFoundException,
                                        IOException

Tests Vector.exponent_mod twice rounds times. The first time for warming the cache and JIT compilation, the second time for real measurements. Exists immediately in case of an error.

If sufficient fixed inputs are available, they will be used. Every round discards the first 2 *vector_exponent_length+ 1 fixed inputs. Otherwise, if -read was given, the test data is taken from that file. After the first rounds test the file is reopened to do the real measurements with exactly the same data.

Without -read the test data is generated randomly. If -write was given the data is written to that file during the first rounds tests and read from there afterwards.

Exists on the first error.

Parameters:

rand - randomness source

data_in - input data file or null for no input file

data_out - output data file or null for no output

Throws:

FileNotFoundException - if reopening read_from_file fails

IOException - if reading from data_in fails or some other file error occurs

test_convenience_exponent

public static void test_convenience_exponent(Random rand)

Test Convenience.exponent_mod rounds times with randomly generated numbers. Exit if a failure is detected.

Parameters:

rand - randomness source

test_convenience_vector_exponent

public static void test_convenience_vector_exponent(Random rand)

Test Convenience.vector_exponent_mod rounds times with randomly generated numbers. Exit if a failure is detected.

Parameters:

rand - randomness source

test_square_mult

public static void test_square_mult(Random rand)

Test Bignat.squared_rsa_mult_2 rounds times. Exists on the first error. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source

test_square_mult_4

public static void test_square_mult_4(Random rand)

Test Bignat.squared_rsa_mult_4 rounds times. Exists on the first error. If fixed inputs are available, they will be used.

Parameters:

rand - randomness source