Package ds.ov2.bignat

Big integer library for Java Card, including a test frame.

See:
Description

Interface Summary

RSA_exponent_interface

Common interface of RSA_exponent and Fake_rsa_exponent.

Class Summary

APDU_BigInteger	Mutable APDU_Serializable wrapper around BigInteger.
Bignat	Allocation free big natural numbers for Java Card.
Bignat_array	APDU_Serializable interface around an array of Bignats.
Convenience	BigInteger convenience interface to selected Bignat methods.
Convenience.Timed_result	BigInteger, long tuple for methods that produce such results.
Fake_rsa_exponent	RSA_exponent_interface implementation for the host.
Host_modulus	Host counterpart of Modulus.
Host_vector	Host counterpart of Vector.
Inverse_mod_256	Modular inverse modulo 256 for Java Card (currently unused).
Modulus	Division modulus for Java Card.
Resize	Centralized resizing of Bignats, Bignat arrays and RSA exponents.
RSA_exponent	Compute modular powers on the crypto coprocessor of the Java Card.
Testbignat	Cardless test frame for the Bignat library.
Vector	Bignat array with multi-exponent functionality.

Package ds.ov2.bignat Description

Big integer library for Java Card, including a test frame.

Warning

Depending on the configuration some types might be different from what is shown in the documentation here. Especially some method parameters of type short might have type long, because they are declared as DOUBLE_DIGIT_TYPE.

The source code in this package cannot be used without the cpp preprocessor, see below.

Overview

This package implements an allocation free big natural number library for Java Cards. Allocation free means that only the constructors allocate on the heap. Normal methods only allocate on the stack, never on the heap. The package only implements non-negative natural numbers, we refer to them as big naturals.

The allocation constraint implies that (in contrast to BigInteger) objects are mutable and that the big numbers are fixed in size. The (maximal) size of a big natural is determined by an constructor argument. In case of an overflow an assertion is thrown (compare Misc.myassert(boolean, short)). Further, because of the allocation constraint some methods require additional arguments that are only used as temporaries in computations in side the method.

Features have been added to this package on a by-need basis. Therefore this package supports much less operations than a normal BigInteger class. However, there is also support for computing multi exponents that I have never seen in any other BigInteger class.

Besides the classes that form the big natural library (Bignat, Bignat_array, Inverse_mod_256, Modulus, RSA_exponent and Vector) this package contains also support code for test frames (Resize, Fake_rsa_exponent), the test frame itself (Testbignat) and support code for host applications (APDU_BigInteger, Host_modulus, Host_vector).

Standard Java Card does not support int and long. Therefore this package normally only uses byte and short for all computations (of course the test frame and the host support code do not obey this restriction). However, it is possible to configure this package to perform all computations with int and long. For Java Cards with int support it should be relatively easy to add a configuration that uses short/int.

Standard Java maintains the wrong illusion of the absolut absense of the just described architectural differences. Therefore it is absolutely impossible to express architecture specific changes such as turning a local variable of type byte into type int within the Java language. [As a corollary of the wrong assumption that there are no architectural differences we obtain that Java is completely unsuitable for programming Java Cards.] This package solves the architecture configuration problem by using cpp macros. For example, many variables in the source code are declared as DIGIT_TYPE, where a preprocessor run expands DIGIT_TYPE to either byte or int, depending on the configuration.

The source code in this package cannot be used without the cpp preprocessor.

Operations

This class provides addition, subtraction, modular multiplication (in three versions), and division and remainder. Multi-exponent is provided by Vector.exponent_mod and Vector.mont_rsa_exponent_mod. RSA_exponent computes a (single) exponent by abusing RSA public key encryption.

Montgomery factor, montgomerization and Montgomery multiplication

Montgomery multiplication produces intermediate results that are up to two digits longer than the arguments. Therefore the first two digits of each factor and of the modulus must be zero to ensure no overflow can occur. The maximal modulus for montgomery multiplication for a given size is therefore 2^(Bignat.digit_len * (size - 2)) - 1.

When using Montgomery multiplication, all numbers must be two digits longer than their maximal value. These two additional Montgomery digits are assumed to be always zero.

At some places the Montgomery digits are hardwired. At other places (for example in RSA_exponent) one has to specify the number of Montgomery digits in an additional argument. For a given modulus mod and a number size size the montgomery factor mont_fac is defined as 2^(Bignat.digit_len * (size - 2)) (modulo mod). (Note the -2 that takes care of the Montgomery digits.)

To montgomerize a bignat x means to compute x * mont_fac. On the host this is conveniently done as x.mult(hmod.mont_fac).mod(hmod.m), where hmod is a Host_modulus initialized from the right size and modulus. On the card one can use montgomery multiplication with the squared montgomery factor.

In Montgomery multiplication the computation of the multiplication and the modulus are done simultaneously. This saves a lot of space. All intermediate results have the same length as the arguments (provided there are two leading Montgomery digits). As a side effect Montgomery multiplication works only with odd moduli. If the modulus is even the construction of the necessary auxiliary data (see Modulus.last_digit_inverse) is impossible. The initializing Host_modulus constructor will, for instance, terminate with an ArithmeticException (thrown by BigInteger.modInverse(java.math.BigInteger) BigInteger.modInverse).

Montgomery multiplication only works with montgomerized arguments. That is, before multiplying x with y one first has to montgomerize x and y, ie, compute x * mont_fac and y * mont_fac. From the montgomerized arguments montgomery multiplication computes x * y * mont_fac, ie, the montgomerization of the product x * y.

To obtain the real result one has to demontgomerize. On the card one can use Montgomery multiplication with a (not montgomerized) 1. Or, more efficiently, with demontgomerize. On the host one can use the demontgomerization factor in the Host_modulus, i.e., compute x.mult(hmod.demont_fac).mod(hmod.m) for a suitable Host_modulus.

When multiplying n numbers a_1,...,a_n instead of montgomerizing the a_i and demontgomerizing the result one can add mont_fac^(n-1) as additional factor. The result is then in normal form (not montgomerized).

Resizing

Once allocated, the size of numbers (Bignat's) and arrays (Bignat arrays) in this package stays constant. Also the key size of the RSA ciphers used for exponentiation does not change.

However, for use in test frames (if VARIABLE_SIZE_BIGNATS is defined) Bignats, Bignat arrays and RSA exponents can provide the illusion of having a different size or length. This works by changing the Bignat.size field in Bignat's to a value smaller than the size of the digit array (see Bignat.value). For bignat arrays and vectors their Bignat_array.length field is changed. For RSA_exponent a new public RSA key is internally allocated. The last indices of the respective arrays stay then simply unused. Note that these arrays will never be reallocated, in particular, one cannot use Bignat.resize to make the Bignat larger than originally specified in the constructor.

Additional support for resizing numbers and arrays is provided by Resize.

Other topics

For the internal representation of Bignat's, see here.