ds.ov2.util.Serializable_array
ds.ov2.bignat.Bignat_array
ds.ov2.bignat.Vector
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
public class Vector
Bignat array with multi-exponent functionality. This class
defines two methods for computing multi-exponents. The first one is
a navtive Java implementation, using simultaneous squaring. The
second one uses an RSA_exponent and multiplies the results
with montgomery multiplication. The compatibility between the two
methods is limited, because different precomputations are required.
The biggest difference is that for the simultaneous squaring method
the bases must be montgomerized.
Inherits the functionality for providing the illusion of a
different array length from Bignat_array.
This is a card data type. For the protocol layer, an object of this class is compatible with
Host_vector of the same length and whose configured
bignat size equals the size of the Bignat's in this vector.
is_compatible_with.
For a number of general topics see also the package description.
| Field Summary | |
|---|---|
private byte[] |
buf
Temporary digit array of type DIGIT_TYPE used inside the exponent_mod method. |
static PrintWriter |
out
Debug and diagnostics output channel. |
private Bignat[] |
temp
References of temporaries used inside exponent_mod and mont_rsa_exponent_mod. |
| Fields inherited from class ds.ov2.bignat.Bignat_array |
|---|
length |
| Constructor Summary | |
|---|---|
Vector(short length,
boolean init_buf)
Non-allocating constructor. |
|
Vector(short bignat_size,
short length,
boolean init_buf,
boolean in_ram)
Allocating constructor. |
|
| Method Summary | |
|---|---|
void |
exponent_mod(Vector exponent,
Modulus modulus,
short base_factor_size,
Vector base_factors,
Bignat mont_one,
Bignat result,
Bignat temp_arg)
Montgomerized modular multi-exponent. |
boolean |
is_compatible_with(Object o)
Compatibility check for the OV-chip protocol layer. |
void |
mont_rsa_exponent_mod(Vector exponent,
Modulus modulus,
RSA_exponent_interface rsa_exponent,
Bignat rsa_vector_correction,
Bignat result,
Bignat temp_1,
Bignat temp_2)
Modular multi-exponent with Montgomery multiplication. |
void |
squared_rsa_exponent_mod(Vector exponent,
Modulus modulus,
Bignat result,
RSA_exponent_interface rsa_exponent,
RSA_exponent_interface square_exponent,
Bignat temp_1,
Bignat temp_2,
Bignat temp_3)
Modular multi-exponent with squared multiplication. |
| Methods inherited from class ds.ov2.bignat.Bignat_array |
|---|
allocate, copy_digit, get_array, get_bignat_length, get_bignat_size, get_length, get, register_long_bignats, register_short_bignats, set_length, set, size |
| Methods inherited from class ds.ov2.util.Serializable_array |
|---|
from_byte_array, to_byte_array |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Methods inherited from interface ds.ov2.util.APDU_Serializable |
|---|
from_byte_array, size, to_byte_array |
| Field Detail |
|---|
private byte[] buf
exponent_mod method. Only allocated if the
init_buf constructor argument is true. If it is
allocated its length will be the same as the length of the
underlying Bignat array of this vector. If DIGIT_TYPE is byte,
the array will be allocated as transient array.
private Bignat[] temp
exponent_mod and mont_rsa_exponent_mod.
Only allocated if the init_buf constructor argument is
true. If allocated the length of the array is 3. The method
exponent_mod uses the first two elements,
mont_rsa_exponent_mod uses all three.
Only the array and not the temporary bignat object themselves
belong to this object. The temporary bignats are passed as
arguments to the exponent_mod and mont_rsa_exponent_mod methods.
This array is not allocated in (transient) RAM, because I don't know how to downcast an object array to a Bignat array.
public static PrintWriter out
| Constructor Detail |
|---|
public Vector(short length,
boolean init_buf)
exponent_mod or mont_rsa_exponent_mod will ever be used on this
object then init_buf must be set to true. The
constructor will then allocate the temporary data structures
that these methods require (see fields buf and temp).
length - length of the underlying bignat arrayinit_buf - whether to initialize the temporary arrays
needed for exponent_mod and mont_rsa_exponent_mod
public Vector(short bignat_size,
short length,
boolean init_buf,
boolean in_ram)
length complete with all bignats, each of
size bignat_size. The argument in_ram is passed
through to the Bignat
constructor, if true all the bignats are allocated in
transient RAM.
If one of the methods exponent_mod or
mont_rsa_exponent_mod will ever be used on
this object then init_buf must be set to true. The
constructor will then allocate the temporary data structures
that these methods require (see fields buf and temp).
bignat_size - size of the Bignats in the array in byteslength - length of the underlying bignat arrayinit_buf - whether to initialize the temporary arrays
needed for exponent_mod and mont_rsa_exponent_modin_ram - allocate the bignats in transient RAM if true| Method Detail |
|---|
public void exponent_mod(Vector exponent,
Modulus modulus,
short base_factor_size,
Vector base_factors,
Bignat mont_one,
Bignat result,
Bignat temp_arg)
this.get(0)^exponent.get(0) * this.get(1)^exponent.get(1)...
modulo modulus up to the length of this vector. The
result will be stored in result. The bases in this
object must be montgomerized, the
exponents must not.
Asserts that the fields buf and temp are
non-null, that is, the constructor for this object must have
been called with init_buf == true.
The use of Montgomery multiplication implies other restrictions, namely that the first two digits of all bases and factors are zero (Montgomery digits) and that the modulus is odd, see Montgomery multiplication.
The argument base_factors must contain the precomputed
factors of the first base_factor_size bases (ie.
elements of this vector). See Host_vector.make_montgomerized_factors, for an easy way to
compute these factors.
The vector base_factor_size must have size base_factor_size^2 -1, where the -1 comes in because
the empty product of all bases is not needed. The argument
base_factor_size can be zero, in this case base_factors can also be a null reference. The factors in
base_factors must be montgomerized. The
base factors must be stored in the following order
base_factors.get(0) == this.get(0) base_factors.get(1) == this.get(1) base_factors.get(2) == this.get(1) * this.get(0) base_factors.get(3) == this.get(2) base_factors.get(4) == this.get(2) * this.get(0) base_factors.get(5) == this.get(2) * this.get(1) base_factors.get(6) == this.get(2) * this.get(1) * this.get(0) ...(If you want to take these lines literally, then ``*'' must denote montgomery multiplication and ``=='' equality of Bignat's.)
The general rule is as follows. Take a base factors index
i and look at the binary representation of i+1.
The base factor i is the product of those bases whose
index has a 1-bit in the binary representation of i+1.
For instance, for index 5, look at the binary representation of
6 == 110, ie., it must be the product of base 1 with
base 2.
base_factor_size can be shorter than the length of this
vector, but it must not be longer. Best performance is obtained
if base_factor_size equals the length of this vector.
Then 2 multiplications per exponent bit are needed. Otherwise
length - base_factor_size additional multiplications
each with probability 0.5 are needed for each exponent bit.
Asserts that base_factor_size is at most 15.
The argument mont_one is used to initialize the
internal multiplication akkumulator, it must therefore be a montgomerized 1. Note
that this is equal to the montgomery factor mont_fac, see
Host_modulus.mont_fac.
The computation requires an additional temporary that is used
together with result for intermediate results.
Therefore result and temp_arg must be different
from all other Bignat passed in as arguments.
The bases in this vector, the factors in base_factor_size, result and temp_arg must all
have the same size, otherwise an exception in Bignat.montgomery_mult might be thrown.
The size of the exponents is arbitrary, but all exponents must
have the same size.
For an example on how to convert normal number into the format
required by this method, see the source code of Convenience.vector_exponent_mod.
If OPT_SPECIAL_SQUARE is defined, squaring will be done with
Bignat.montgomery_square,
otherwise with Bignat.montgomery_mult.
exponent - exponentsmodulus - modulusbase_factor_size - number of bases for which precomputed
factors are available in base_factorsbase_factors - Base factor array of size 2^base_factor_size -1, use Host_vector.make_montgomerized_factors to compute itmont_one - a montgomerized one, equals the Montgomery factor mont_fac
, see Host_modulus.mont_fac.result - resulttemp_arg - a temporary of the same size as result
and the bases
public void mont_rsa_exponent_mod(Vector exponent,
Modulus modulus,
RSA_exponent_interface rsa_exponent,
Bignat rsa_vector_correction,
Bignat result,
Bignat temp_1,
Bignat temp_2)
RSA_exponent to compute single exponents. They are then
multiplied with Montgomery
multiplication. Computes this.get(0)^exponent.get(0) *
this.get(1)^exponent.get(1)... modulo modulus up to
the length of this vector. The result will be stored in result. The bases in this vector and the exponents must be in
normal form, i.e., not montgomerized.
The argument rsa_vector_correction is multiplied to the
product of all single exponents as a Montgomery correction
factor. For two bases two multiplications are performed in
total, so the rsa_vector_correction argument must be
mont_fac^2 to obtain a normal result, where mont_fac is the Montgomery
factor. For three bases it must be mont_fac^3, and so on.
If the multi-exponent computed here is only an intermediate
result, one can of course also use an higher exponent of the
Montgomery factor to also adjust for multiplications done
outside of this method.
Internally three temporaries are needed. The argument result is used as one of them, the two other temporaries must
be passed explicitely. The three arguments result,
temp_1 and temp_2 must be pairwise different
references and they must also differ from the bases and the
modulus.
The bases in this object must match the configured size of the
rsa_exponent that is used to compute the single
exponents. (This means that the size of the bases must be 2
bytes larger than the key size of the rsa_exponent.)
The modulus must have been installed (with set_modulus) in the rsa_exponent prior to calling this method.
This method can only be used if the object has been constructed
with init_buf == true.
This method has been written for use on the card with an RSA_exponent object for doing exponentiations on the crypto
coprocessor. However, for testing purposes, it can also be used
together with Fake_rsa_exponent.
exponent - vector with the exponents, must have the same
length as this vectormodulus - modulusrsa_exponent - RSA exponent object used for single exponentiationsrsa_vector_correction - Montgomery correction factorresult - result and 1st temporarytemp_1 - 2nd temporarytemp_2 - 3rd temporary
public void squared_rsa_exponent_mod(Vector exponent,
Modulus modulus,
Bignat result,
RSA_exponent_interface rsa_exponent,
RSA_exponent_interface square_exponent,
Bignat temp_1,
Bignat temp_2,
Bignat temp_3)
RSA_exponent to compute single exponents.
They are then multiplied with squared multiplication (Bignat.squared_rsa_mult_2 or Bignat.squared_rsa_mult_4 depending
on SQUARED_RSA_MULT).
Computes
this.get(0)^exponent.get(0) *
this.get(1)^exponent.get(1)... modulo modulus up to
the length of this vector. The result will be stored in result. The bases in this vector and the exponents must be in
normal form, i.e., not montgomerized.
Internally four temporaries are needed. The argument result is used as one of them, the three other temporaries
must be passed explicitely. The four arguments result,
temp_1, temp_2 and temp_3 must be
pairwise different references and they must also differ from
the bases and the modulus.
Both RSA exponents rsa_exponent and square_exponent must be configured for the same size. square_exponent must have the modulus modulus and an
exponent of 2 installed before entering this method. rsa_exponent must have the modulus modulus installed
before calling this method.
The bases in this object, the temporaries and the result must
have the same length, which must be identical to the configured
size of both rsa_exponent and square_exponent.
This method can only be used if the object has been constructed
with init_buf == true.
This method has been written for use on the card with an RSA_exponent object for doing exponentiations on the crypto
coprocessor. However, for testing purposes, it can also be used
together with Fake_rsa_exponent.
exponent - vector with the exponents, must have the same
length as this vectormodulus - modulusresult - result and 1st temporaryrsa_exponent - RSA exponent object used for single
exponentiations with arbitrary exponentssquare_exponent - RSA exponents object used for squaring
inside Bignat.squared_rsa_mult_2temp_1 - 2nd temporarytemp_2 - 3rd temporarytemp_3 - 4th temporarypublic boolean is_compatible_with(Object o)
Host_vectors of the same length and
whose configured bignat size equals the size of the Bignat's in
this vector. APDU_Serializable.is_compatible_with.
is_compatible_with in interface APDU_Serializableis_compatible_with in class Serializable_arrayo - actual argument or result
o.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||