ds.ov2.bignat.Bignat
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
public class Bignat
Allocation free big natural numbers for Java Card. A number of general topics are discussed in the package description.
size -1. The internal representation is
therefore almost compatible with BigInteger.
The length of the digit array is determined by the size
argument of the constructors. It stays constant for every
object. Different big naturals can have different sizes.
Methods that combine different big naturals check the size
constraint in an assertion. Some methods permit to combine big
naturals of different sizes. Size constraints are lifted on a
by-need basis, so some methods may still be overly
restrictive.
It is the responsibility of the user to make sure that no overflow occurs. Some methods assert a precondition that implies that no overflow occurs. In such a case the user has still to make sure that the assertion holds. There is no error recovery possible, because, when assertions are disabled, overflowing digits are just droped (I believe).
BigIntegerBigInteger.toByteArray() is variable in size.BigInteger.BigInteger(byte[]) will interpred the
byte array as negative value.
When converting from Bignat to BigInteger make sure the first bit is zero, possibly by prepending a zero byte.
When DIGIT_TYPE is int one has to convert every int into 4 bytes in the obvious way.
Convertion can be done with Convert_serializable which works regardless of the
setting of DIGIT_TYPE.
Use Convert_serializable.to(bignat, bigint) and Convert_serializable.from(bignat, bigint). Note that Convert_serializable.to(bigint, bignat) will not work, see
Bignat.is_compatible_with and
APDU_BigInteger.is_compatible_with.
| Field Summary | |
|---|---|
static short |
bignat_base
The base as a double digit. |
static short |
digit_first_bit_mask
Bitmask for the highest bit in a digit. |
static short |
digit_first_two_bit_mask
Bitmask for the two highest bits in a digit. |
private static String |
digit_format
Format string to print a digit. |
static short |
digit_len
Size in bits of one digit. |
static short |
digit_mask
Bitmask for extracting a digit out of a longer int/short value. |
static short |
digit_second_bit_mask
Bitmask for the second highest bit in a digit. |
private static String |
double_digit_format
Format string to print a double digit. |
private static short |
double_digit_len
Size in bits of a double digit. |
static short |
highest_digit_bit
Bitmask for the highest bit in a double digit. |
static short |
highest_double_digit_bit
Bitmask with just the highest bit in a double digit. |
private static short |
positive_double_digit_mask
Bitmask for erasing the sign bit in a double digit. |
private short |
size
Length in digits. |
static short |
size_multiplier
Factor for converting digit size into byte length. |
static boolean |
use_byte_digits
True for the byte/short configuration, false otherwise. |
private byte[] |
value
Digit array. |
static int |
verbosity
Controls the amount of debug messages printed. |
| Constructor Summary | |
|---|---|
Bignat(short size)
Convenience constructor for the host. |
|
Bignat(short size,
boolean ram)
Construct a Bignat of size size in bytes. |
|
| Method Summary | |
|---|---|
boolean |
add_carry(Bignat other)
Addition with carry report. |
void |
add(Bignat other)
Addition. |
byte[] |
as_byte_array()
Return this Bignat as byte array. |
void |
copy(Bignat other)
Copies other into this. |
void |
demontgomerize(Modulus mod)
Demontgomerization. |
void |
div_2()
Division by 2. |
void |
div_4()
Division by 4. |
void |
exponent_mod(Bignat base,
Bignat exponent,
Modulus modulus,
Bignat mont_one,
Bignat temp)
Modular power. |
short |
from_byte_array(short len,
short this_index,
byte[] byte_array,
short byte_index)
Deserialization of this object for the OV-chip protocol layer. |
byte[] |
get_digit_array()
Return the digit array. |
byte |
get_first_digit_mask(short first_digit_index)
Bitmask for first digit. |
private static short |
highest_bit(short x)
Index of the most significant 1 bit. |
boolean |
is_compatible_with(Object o)
Compatibility check for the OV-chip protocol layer. |
boolean |
is_zero()
Test equality with zero. |
short |
length()
Return the size in digits. |
boolean |
lesser(Bignat other)
Comparison. |
void |
modular_div_2(Modulus mod)
Modular division by 2. |
void |
modular_div_4(Modulus mod)
Modular division by 4. |
void |
modular_subtraction(Bignat other,
Modulus mod)
Modular subtraction. |
void |
montgomery_factor(Bignat mod,
Bignat mont_fac)
montgomery factors. |
void |
montgomery_mult(Bignat x,
Bignat y,
Modulus mod)
Montgomery multiplication (special modular multiplication). |
void |
montgomery_square(Bignat x,
Modulus mod)
Optimization for modular Montgomery squares. |
void |
mult_mod(Bignat x,
Bignat y,
Bignat mod)
Inefficient modular multiplication. |
void |
mult(Bignat x,
Bignat y)
Multiplication. |
void |
one()
Stores one in this object. |
void |
rand_mod(Random rand,
Bignat mod,
short first_mod_digit,
byte first_digit_mask)
Modular random number generator. |
void |
remainder_divide(Bignat divisor,
Bignat quotient)
Remainder and Quotient. |
(package private) void |
resize(short new_size)
Resize this Bignat. |
boolean |
same_value(Bignat other)
Equality check. |
private static short |
shift_bits(short high,
byte middle,
byte low,
short shift)
Shift to the left and fill. |
void |
shift_left()
One digit left shift. |
boolean |
shift_lesser_debug(Bignat other,
short shift,
short start)
Comparison with debug output. |
boolean |
shift_lesser(Bignat other,
short shift,
short start)
Scaled comparison. |
void |
shift_right()
One digit right shift. |
void |
short_squared_rsa_mult_2(Bignat x,
Bignat y,
RSA_exponent_interface square_exp,
Bignat temp_1,
Bignat temp_2)
Multiplication of short bignats. |
void |
short_squared_rsa_mult_4(Bignat x,
Bignat y,
RSA_exponent_interface square_exp,
Bignat temp_1,
Bignat temp_2)
Another multiplication of short bignats. |
short |
size()
Size in bytes necessary to send or receive this object via the OV-chip protocol layer, see APDU_Serializable.size(). |
void |
squared_rsa_mult_2(Bignat x,
Bignat y,
Modulus mod,
RSA_exponent_interface square_exp,
Bignat temp)
Modular multiplication. |
void |
squared_rsa_mult_4(Bignat x,
Bignat y,
Modulus mod,
RSA_exponent_interface square_exp,
Bignat temp)
Yet another modular multiplication. |
boolean |
subtract(Bignat other)
Subtraction. |
void |
times_add_add(Bignat second,
short second_mult,
Bignat third,
short third_mult)
Special addition for optimizing montgomery_mult. |
void |
times_add_shift(Bignat other,
short shift,
short mult)
Scaled addition. |
void |
times_add(Bignat other,
short mult)
Scaled addition. |
void |
times_minus(Bignat other,
short shift,
short mult)
Scaled subtraction. |
short |
to_byte_array(short len,
short this_index,
byte[] byte_array,
short byte_index)
Serialization of this object for the OV-chip protocol layer. |
String |
to_hex_string()
Convert into a hex number as string with dots every 4 digits. |
void |
two()
Stores two in this object. |
void |
zero()
Stores zero in this object. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
|---|
public static final boolean use_byte_digits
public static final short size_multiplier
public static final short digit_mask
public static final short digit_first_bit_mask
public static final short digit_second_bit_mask
public static final short digit_first_two_bit_mask
public static final short digit_len
private static final short double_digit_len
private static final short positive_double_digit_mask
public static final short highest_digit_bit
public static final short bignat_base
public static final short highest_double_digit_bit
private static final String digit_format
private static final String double_digit_format
private byte[] value
private short size
resize(short) method.
Note that the size() method returns something different,
which is admittedly confusing.
public static int verbosity
| Constructor Detail |
|---|
public Bignat(short size,
boolean ram)
size in bytes.
Allocated in RAM if ram is true, in EEPROM otherwise.
In the int/long configuration asserts that size is divisable by 4.
In this configuration the number of digits is obviously
size / 4.
Relies on Misc.allocate_transient_byte_array for allocation in transient
(RAM) memory.
size - the size of the new Bignat in bytes, must be
divisible by 4 for the int/long configurationram - allocate in transient RAM if truepublic Bignat(short size)
Bignat(size, false) on the host, where the
ram argument has no meaning.
size - the size of the new Bignat in bytes, must be
divisible by 4 for the int/long configuration| Method Detail |
|---|
public byte[] get_digit_array()
DIGIT_TYPE[].
The value field is simply returned, without making a copy.
Modifying the returned array will modify this Bignat.
value of type DIGIT_TYPE[]public byte[] as_byte_array()
void resize(short new_size)
s is smaller or equal to the
size specified in the constructor.
new_size - new size in bytes, must be
divisible by 4 for the int/long configurationpublic short size()
APDU_Serializable.size().
For configurations different from
byte/short the returned value obviously differs from the length of
the value array and also from the size attribute.
The return value is adjusted by resize(short).
size in interface APDU_Serializablepublic short length()
size field.
The return value is adjusted by resize(short).
public void zero()
public void one()
public void two()
public void copy(Bignat other)
other into this. No size requirements. If other has more digits then the superfluous leading digits
of other are asserted to be zero. If this bignat has
more digits than its leading digits are correctly initilized to
zero.
other - Bignat to copy into this object.public boolean same_value(Bignat other)
other - Bignat to compare
public boolean subtract(Bignat other)
other from this and store
the result in this. If an overflow occurs the return
value is true and the value of this is the correct negative
result in two's complement. If there is no overflow the return
value is false.
It would be more natural to report the overflow with an UserException, however its throwIt method dies
with a null pointer exception when it runs in a host test
frame...
No size constraints, in particular, other can be longer
than this. However, if other is longer than
this the additional digits of other are
asserted to be zero. Without assertion checks these additional
digits of other are ignored and the method silently
returns a wrong result.
other - value to subtract from this
public void modular_subtraction(Bignat other,
Modulus mod)
(this - other) modulo mod
and stores the result in this Bignat. This bignat and other must be less then mod, otherwise strange things
can happen.
other - value to subtractmod - modulus
public void times_minus(Bignat other,
short shift,
short mult)
mult * 2^(digit_len* shift) * other
from this.
That is, shifts mult * other precisely shift digits to
the left and subtracts that value from this.
mult must be less than bignat_base, that is,
it must fit into one digit. It is only declared as
DOUBLE_DIGIT_TYPE here to avoid negative values.
mult has type DOUBLE_DIGIT_TYPE.
No size constraint. However, an assertion is thrown,
if the result would be negative. other can have more
digits than this object, but then sufficiently many leading digits
must be zero to avoid the underflow.
Used in division.
other - Bignat to subtract from this objectshift - number of digits to shift other to the leftmult - of type DOUBLE_DIGIT_TYPE, multiple of other
to subtract from this object. Must be below
bignat_base.private static short highest_bit(short x)
x has type DOUBLE_DIGIT_TYPE.
Utility method, used in division.
x - of type DOUBLE_DIGIT_TYPE
x, returns
double_digit_len for x == 0.
private static short shift_bits(short high,
byte middle,
byte low,
short shift)
high middle low as 4 digits,
shifts them shift bits to the left and returns the most
significant double_digit_len bits.
Utility method, used in division.
high - of type DOUBLE_DIGIT_TYPE,
most significant double_digit_len bitsmiddle - of type DIGIT_TYPE, middle digit_len bitslow - of type DIGIT_TYPE,
least significant digit_len bitsshift - amount of left shift
double_digit_len as DOUBLE_DIGIT_TYPE
public boolean shift_lesser(Bignat other,
short shift,
short start)
other * 2^(
digit_len * shift). That is, shifts other
shift digits to the left and compares then. This bignat
and other will not be modified inside this method.
As optimization start can be greater than zero to skip
the first start digits in the comparison. These first
digits must be zero then, otherwise an assertion is thrown.
(So the optimization takes only effect when NO_CARD_ASSERT
is defined.)
other - Bignat to compare toshift - left shift of other before the comparisonstart - digits to skip at the beginning
other, false otherwise.public boolean lesser(Bignat other)
other - Bignat to compare with
other,
false otherwise.public boolean is_zero()
public boolean shift_lesser_debug(Bignat other,
short shift,
short start)
shift_lesser(ds.ov2.bignat.Bignat, short, short)
but prints debug output if verbosity is big enough.
Only available if JAVACARD_APPLET is undefined.
other - Bignat to compare toshift - left shift of other before the comparisonstart - digits to skip at the beginning
other, false otherwise.
public void remainder_divide(Bignat divisor,
Bignat quotient)
divisor
and store the remainder in this. If quotient is non-null
store the quotient there.
There are no direct size constraints, but if quotient
is non-null, it must be big enough for the quotient, otherwise
an assertion is thrown.
Uses schoolbook division inside and has O^2 complexity in the difference of significant digits of the divident (in this number) and the divisor. For numbers of equal size complexity is linear.
divisor - must be non-zeroquotient - gets the quotient if non-nullpublic boolean add_carry(Bignat other)
this will
then be the correct result of an addition modulo the first
number that does not fit into this (2^(digit_len* this.size)), i.e.,
only one leading 1 bit is missing. If there is no overflow the
method will return false.
It would be more natural to report the overflow with an UserException, however its throwIt method dies
with a null pointer exception when it runs in a host test
frame...
Asserts that the size of other is not greater than the size of this.
other - Bignat to addpublic void add(Bignat other)
Same as times_add(other, 1)
but without the multiplication overhead.
Asserts that the size of other is not greater than the size of this.
other - Bignat to add
public void times_add(Bignat other,
short mult)
mult * other to this number.
mult must be below bignat_base, that is,
it must fit into one digit. It is only
declared as a DOUBLE_DIGIT_TYPE here to avoid negative numbers.
Asserts (overly restrictive) that this and other have the same size.
Same as times_add_shift(other, 0, mult)
but without the shift overhead.
Used in multiplication.
other - Bignat to addmult - of DOUBLE_DIGIT_TYPE, factor to multiply other
with before addition. Must be less
than bignat_base.
public void times_add_add(Bignat second,
short second_mult,
Bignat third,
short third_mult)
montgomery_mult.
Adds second * second_mult + third * third_mult to this.
This is an apparent optimization however, my measurements show that
it slows down the code (in the Bignat test frame).
second_mult and third_mult
must be below bignat_base, that is,
they must fit into one digit. They are only
declared as a DOUBLE_DIGIT_TYPE here to avoid negative numbers.
Only available if OPT_DOUBLE_ADD is defined.
Asserts that this, second and third have the same size.
second - bignat to add, multiplied with second_mult
before addedsecond_mult - of type DOUBLE_DIGIT_TYPE. Must be less
than bignat_base.third - other bignat to add, multiplied with
third_mult before addedthird_mult - of type DOUBLE_DIGIT_TYPE. Must be less
than bignat_base.
public void times_add_shift(Bignat other,
short shift,
short mult)
mult * other * 2^(digit_len* shift)
to this. That is, shifts other shift digits to the left,
multiplies it with mult and adds then.
mult must be less than bignat_base, that is,
it must fit into one digit. It is only
declared as a DOUBLE_DIGIT_TYPE here to avoid negative numbers.
Asserts that the size of this is greater than or equal to
other.size + shift + 1.
other - Bignat to addmult - of DOUBLE_DIGIT_TYPE, factor to multiply other
with before addition. Must be less
than bignat_base.shift - number of digits to shift other to the left,
before addition.
public void mult(Bignat x,
Bignat y)
x * y in this. To ensure this is big enough for
the result it is asserted that the size of this is greater than
or equal to the sum of the sizes of x and y.
x - first factory - second factorpublic void shift_left()
Asserts that the first digit is zero.
public void mult_mod(Bignat x,
Bignat y,
Bignat mod)
x * y modulo mod.
Inefficient, because it computes the modules with
remainder_divide in each multiplication round.
To avoid overflow the first two digits of x and mod
must be zero (which plays nicely with the requirements for
montgomery multiplication, see montgomery_mult).
Asserts that x and mod have the same size. Argument
y can be arbitrary in size.
Included here to make it possible to compute the squared montgomery factor, which is needed to montgomerize numbers before montgomery multiplication. Until now this has never been used, because the montgomery factors are computed on the host and then installed on the card. Or numbers are montgomerized on the host already.
x - first factor, first two digits must be zeroy - second factormod - modulus, first two digits must be zeropublic void shift_right()
public void montgomery_factor(Bignat mod,
Bignat mont_fac)
mod and mont_fac.size in argument mont_fac and the squared montgomery
factor in this bignat. Asserts that this and the two arguments have the same size.
The argument mont_fac started out as temporary, that is
needed to compute the squared montgomery
factor. When writing the documentation I noticed that it
acidentially contains the montgomery
factor at the end.
mod - modulusmont_fac - gets the montgomery
factor assigned
public void montgomery_mult(Bignat x,
Bignat y,
Modulus mod)
x * y / mont_fac (modulo mod) in this bignat, where mont_fac is the montgomery
factor for mod and this.size. Computes the
modular montgomerized product if the arguments are
montgomerized.
Asserts that this and the arguments all have the same size.
Further the first two digits of x, y and mod
must be zero.
As unchecked assumption mod must be odd. Strange things
will happen for even moduli (Note that with the standard procedure to
obtain a Modulus, namely by initializing and sending a
Host_modulus to the card, it is impossible to obtain
an even modulus).
The requirement for an odd modulus comes from the following.
The dividision by mont_fac is actually done by shifting
the akkumulator one digit to the right after each multiplication
round. Because the first two digits of all arguments are zero, we do
size -2 multiplication rounds, that is, with one shift
each round, we precisely divide by
2^(digit_len * (size - 2)), ie, by mont_fac.
Before the right shift the least significant digit must be
zero, otherwise we compute wrong results. To get a zero
there we just add x * mod, where x is precisely that
factor that makes the last digit of the sum zero.
Assume byte digits (BIGNAT_USE_BYTE) and that the
last digit of the akkumulator is 255. Then we need to add x *
mod such that x * mod = 1 (modulo 256).
That is, x must be the modular inverse of mod
modulo 256. If the last digit is 254 we simply add
2 * x * mod, which equals 2 (modulo 256).
The required modular inverse exists precisely when mod
and 256 (or bignat_base, more generally) are coprime,
which happens precisely when mod is odd.
With some computations one can show that after the right shift the
akkumulator always fits into size -1 digits without the
need of computing remainders modulo mod in between.
To ensure the result fits in size -2 digits and is actually
less then mod a final
remainder_divide is done.
x - first factor, first two digits must be zeroy - second factor, first two digits must be zeromod - modulus, must be odd, first two digits must be zero
public void montgomery_square(Bignat x,
Modulus mod)
x *
x / mont_fac (modulo mod) in this
bignat, where mont_fac is the montgomery
factor for mod and this.size. Computes the
modular montgomerized square of x if x is
montgomerized. Equivalent to montgomery_mult(x, x, mod).
Asserts that this and the arguments all have the same size
and that the first two digits of x and mod are zero.
Does only work for odd moduli, as explained for
montgomery_mult.
Only available when OPT_SPECIAL_SQUARE is defined.
The optimization is based on the fact that for squares about
half of the single digit multiplications can be saved. There are
however some complications, because some intermediate results do
not fit into DOUBLE_DIGIT_TYPE any longer (as they do inside montgomery_mult).
Does not deliver any speedups in my measurements.
x - number to square, first two digits must be zeromod - modulus, first two digits must be zeropublic void demontgomerize(Modulus mod)
this by the
montgomery factor.
Equivalent to montgomery multiplication with 1, but
twice as fast.
Asserts that this and mod have the same size and
that the first two digits of this and mod are zero.
mod must be odd, see disscussion in montgomery_mult.
mod - modulus, the first two digits must be zero
public void exponent_mod(Bignat base,
Bignat exponent,
Modulus modulus,
Bignat mont_one,
Bignat temp)
base^exponent (modulo
modulus) and stores the result in this bignat. base
must be montgomerized and exponent must not. The result
will be montgomerized. Needs a temporary for the computation
and a montgomerized 1 (which is equal to the montgomery
factor and can be found, for instance, in Host_modulus.mont_fac) to initialize the akkumulator.
Asserts that this, base, modulus,
mont_one and temp all have the same size.
The size of the exponent can be arbitrary.
base and modulus must fulfill the preconditions
of montgomery multiplication, that is, there first two digits must
be zero.
Uses the repeated squaring method internally without further optimizations (so it pays off if there are not too many leading zeros in the exponent).
base - montgomerized baseexponent - exponent (not montgomerized)modulus - the modulusmont_one - 1, montgomerized (which equals the montgomery
factor, see Host_modulus.mont_fac)temp - a temporary, different from all other arguments.public void div_2()
public void modular_div_2(Modulus mod)
x modulo
mod on the assumption that 2x modulo mod is in this
bignat before calling this method.
The most significant bit of the modulus mod (and
therefore also the most significant bit of this bignat) must be
zero, otherwise an assertion might get triggered inside add.
mod - modulus
public void squared_rsa_mult_2(Bignat x,
Bignat y,
Modulus mod,
RSA_exponent_interface square_exp,
Bignat temp)
x * y modulo mod and
stores the result in this bignat. Internally the equation
x*y = ((x+y)^2 - x^2 - y^2)/2 will be exploited,
whereby the squares are computed via RSA_exponent on
the crypto coprocessor.
The most significant bit of the modulus mod must be
zero, otherwise an overflow might lead to a failing assertion
inside add.
The modulus and the exponent 2 must have been installed
in square_exp before calling this method.
This bignat and the arguments x, y, mod, and temp must all have the same size, which must
be equal to the key size of square_exp.
x - first factory - second factormod - modulussquare_exp - the instance for fast squaringtemp - temporary
public void short_squared_rsa_mult_2(Bignat x,
Bignat y,
RSA_exponent_interface square_exp,
Bignat temp_1,
Bignat temp_2)
x * y and
stores the result in this bignat. Internally the equation
x*y = ((x+y)^2 - x^2 - y^2)/2 will be exploited,
whereby the squares are computed via RSA_exponent on
the crypto coprocessor.
Does only work correctly under the following assumptions.
square_exp is greater then
(x + y)^2.(x + y)^2.2 have been installed
in square_exp before calling this method.temp_1, temp_2, mod and square_exp
have the same size.
The conditions permit in particular x and y
that are shorter than half the size of mod.
x - first factory - second factorsquare_exp - the instance for fast squaringtemp_1 - temporarytemp_2 - temporarypublic void div_4()
public void modular_div_4(Modulus mod)
x modulo
mod on the assumption that 4x modulo mod is in this
bignat before calling this method.
The two most significant bits of the modulus mod (and
therefore also the most significant bit of this bignat) must be
zero, otherwise an assertion might get triggered inside add.
The multiples of the modulus must had been allocated with
Modulus.allocate_multiples
before the modulus has been initialized via Modulus.from_byte_array.
The modulus must be equivalent to 1 modulo 4 otherwise
wrong results may be computed.
mod - modulus
public void squared_rsa_mult_4(Bignat x,
Bignat y,
Modulus mod,
RSA_exponent_interface square_exp,
Bignat temp)
x * y
modulo mod and stores the result in this bignat. This time
the equation x*y = ((x+y)^2 - (x-y)^2)/4 will be
exploited. The squares are computed via RSA_exponent on the crypto coprocessor.
The first two most significant bits of the modulus mod
must be zero, otherwise an overflow might lead to a failing
assertion inside add. The multiples of the modulus
must had been allocated with Modulus.allocate_multiples before the modulus has been
initialized via Modulus.from_byte_array.
The modulus must be equivalent to 1 modulo
4 otherwise wrong results may be computed.
The modulus and the exponent 2 must have been installed
in square_exp before calling this method.
This bignat and the arguments x, y, mod, and temp must all have the same size, which must
be equal to the key size of square_exp.
The second argument y is used as second temporary and
will therefore be modified.
x - first factory - second factor (used as temporary and modified in this method)mod - modulussquare_exp - the instance for fast squaringtemp - temporary
public void short_squared_rsa_mult_4(Bignat x,
Bignat y,
RSA_exponent_interface square_exp,
Bignat temp_1,
Bignat temp_2)
x * y
and stores the result in this bignat. Internally the equation
x*y = ((x+y)^2 - (x - y)^2)/4 is used, whereby the
squares are computed via RSA_exponent on the crypto
coprocessor. Does only work correctly under the following assumptions.
square_exp is greater then
(x + y)^2.(x + y)^2.2 have been installed
in square_exp before calling this method.temp_1, temp_2, mod and square_exp
have the same size.
The conditions permit in particular x and y
that are shorter than half the size of mod. This bignat
should have the double size of x but can be smaller
than mod.
x - first factory - second factorsquare_exp - the instance for fast squaringtemp_1 - temporarytemp_2 - temporarypublic byte get_first_digit_mask(short first_digit_index)
& that masks all bits
obove the most significant 1 bit in the first digit of this bignat.
For instance, if the first digit is 10, then the mask
returned is 0x1F.
Needed to improve the efficiency of modular random number generation,
see rand_mod.
Asserts that digits before first_digit_index are zero.
first_digit_index - the index of the first digit
public void rand_mod(Random rand,
Bignat mod,
short first_mod_digit,
byte first_digit_mask)
mod. To be efficient
certain characteristics of the modulus mod must be passed
in as arguments. first_mod_digit is the index of the
first non-zero digit of mod and first_digit_mask
(of type DIGIT_TYPE) is a mask as computed by
get_first_digit_mask. If the modulus is
constant these data can be computed once (therefore it is passed in
as argument here). If this data is wrong, the random number might not
be evenly distributed or this method might not return for a very long
time.
Asserts that this bignat and mod have the same size.
Relies on Misc.rand_data,
for BIGNAT_USE_BYTE, and on
Misc.rand_data_int, for
BIGNAT_USE_INT, respectively, for filling the digit array with
random data.
The random number generator
has type RandomData
on the card and Random on the host. Therefore
the first argument changes its type, depending on the environment.
To generate a random number lesser than mod one cannot
just take the remainder of the division by mod, because
this would result in random values that are not evenly distributed.
Therefore we just generate random data in a loop until we are
so lucky that one is below mod. To improve our chances
we zero out all bits in the random data that are above the most
significant 1 bit in mod.
rand - of type RANDOM, random number generatormod - modulusfirst_mod_digit - index of the first non-zero digit in modfirst_digit_mask - of type DIGIT_TYPE, mask for masking
bits above the most significant 1 bit in the first
non-zero digit of mod, as returned by
get_first_digit_mask.public boolean is_compatible_with(Object o)
APDU_Serializable.is_compatible_with.
Bignat objects are compatible to Bignat's and APDU_BigInteger's of the same size.
is_compatible_with in interface APDU_Serializableo - actual argument or result
o is either a Bignat or an APDU_BigInteger of the same size.
public short to_byte_array(short len,
short this_index,
byte[] byte_array,
short byte_index)
APDU_Serializable.to_byte_array.
to_byte_array in interface APDU_Serializablelen - available space in byte_arraythis_index - number of bytes that
have already been written in preceeding callsbyte_array - data array to serialize the state intobyte_index - index in byte_array
len bytes, in this case len + 1 is
returned.
public short from_byte_array(short len,
short this_index,
byte[] byte_array,
short byte_index)
APDU_Serializable.from_byte_array.
from_byte_array in interface APDU_Serializablelen - available data in byte_arraythis_index - number of bytes that
have already been read in preceeding callsbyte_array - data array to deserialize frombyte_index - index in byte_array
len bytes, in this case len + 1 is
returned.public String to_hex_string()
Only available if HOST_TESTFRAME is defined.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||