Table driven method for calculating arithmetic inverse for use in cryptography

A method for performing modular division operations used in a cryotographic process over a finite field FU defined for a prime number U to generate a cryptographic key, in which cryptographic process, at least one value is divided by an integer divisor V modulo U, the method comprising the steps of calculating an arithmetic inverse of V modulo U using an extending greatest common divisor (GCD) method which includes a plurality of reduction steps and a plurality of inverse calculations, including the steps of

• assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V;
• assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V modulo U;
• determining whether a bit position of a most significant bit (MSB) of the value in U3 differs by less than a predetermined number from a bit position of an MSB of the value in V3, and if the bit position of the MSB of the value in U3 differs by less than the predetermined number from the bit position of the MSB of the value in V3,
• combining multiple ones of the plurality of reduction steps for calculating the GCD;
• and
• combining multiple ones of the plurality of inversion calculations;
• and
• if the bit position of the MSB of the value in the U3 does not differ by less than the predetermined number from the bit position of the MSB of the value in the V3,
• performing a single one of the reduction steps;
• and
• performing a single one of the inverse calculation steps;
• returning, as a result of the plurality of reduction steps and the plurality of inverse calculations, the arithmetic inverse of V;
• and
• as a part of the cryptographic process, multiplying the at least one value by the returned arithmetic inverse in place of the integer division to produce the cryptographic key.

A computer readable carrier including computer program instructions that cause a computer to perform modular division operations over a finite field FU defined for a prime number U and used in a cryptographic process in which at least one value is divided by an integer divisor V modulo U to generate a cryptographic key, the method comprising the steps of calculating an arithmetic inverse of V modulo U using an extended greatest common divisor (GCD) method which includes a plurality of reduction steps and a plurality of inverse calculations, including the steps of:

• assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V;
• assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V modulo U;
• determining whether U3 has a number, N, of zero-valued least significant bits (LSBs), where N is an integer greater than two, and if N is greater than two,
• combining multiple ones of the plurality of reduction steps for calculating the GCD;
• and
• combining multiple ones of the plurality of inversion calculations;
• and
• if N is not greater than two,
• performing a single one of the reduction steps;
• and
• performing a single one of the inverse calculation steps;
• returning, as a result of the plurality of reduction steps and the plurality of inverse calculations, the arithmetic inverse of V;
• and
• as a part or the cryptographic process, multiplying the at least one value by the returned arithmetic inverse in place of the integer division to produce the cryptographic key.

A computer readable carrier including computer program instructions that cause a computer to perform modular division operations over a finite field FU that defined for a prime number U and used in a cryptographic process in which at least one value is divided by an integer divisor V modulo U to generate a cryptographic key, the method comprising the steps of calculating an arithmetic inverse of V modulo U using an extended greatest common divisor (GCD) method which includes a plurality of reduction steps and a plurality of inverse calculations, including the steps of:

• assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V;
• assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V modulo U;
• determining whether a bit position of a most significant bit (MSB) of the value in U3 differs by less than a predetermined number from a bit position of an MSB of the value in V3, and if the bit position of the MSB of the value in U3 differs by less than the predetermined number from the bit position of the MSB of the value in V3,
• combining multiple ones of the plurality of reduction steps for calculating the GCD;
• and
• combining multiple ones of the plurality of inversion calculations;
• and
• if the bit position of the MSB of the value in the U3 does not differ less than the predetermined number from the bit position of the MSB of the value in the V3,
• performing a single one of the reduction steps;
• and
• performing a single one of the inverse calculation steps;
• returning, as a result of the plurality of reduction steps and the plurality of inverse calculations, the arithmetic inverse or V;
• and
• as a part of the cryptographic process, multiplying the at least one value by the returned arithmetic inverse in place of the integer division to produce the cryptographic key.

Cryptographic apparatus which performs division operations over a finite field FU defined for a prime number U, in which at least one value is divided by an integer divisor V modulo U to generate a cryptographic key, the apparatus calculating an arithmetic inverse of V modulo U using an extended greatest common divisor (GCD) algorithm which includes a plurality of reduction steps and a plurality of inverse calculations, the apparatus comprising:

• means for assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V;
• means for assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V modulo U;
• means for determining whether U3 has a number, N, of zero-value least significant bits (LSBs), where N is an integer greater than two;
• and
• means for combining multiple ones of the plurality of reduction steps and multiple ones of the inverse calculations if N is greater than two;
• means for returning, as a result of the plurality of reduction steps and the plurality of inverse calculations, the arithmetic inverse of V;
• and
• as a part of the cryptographic process, means for multiplying the at least one value by the returned arithmetic inverse in place of the integer division to produce the cryptographic key.

Cryptographic apparatus which performs division operations over a finite field FU defined for a prime number U, in which at least one value is divided by an integer divisor V modulo U to generate a cryptographic key, the apparatus calculating an arithmetic inverse of V modulo U using an extended greatest common divisor (GCD) algorithm which includes a plurality of reduction steps and a plurality of inverse calculations, the apparatus comprising:

• means for assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V;
• means for assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V modulo U;
• means for determining whether a bit position of a most significant bit (MSB) of the value in U3 differs by less than a predetermined number from a bit position of an MSB of the value in V3;
• and
• means for combining multiple ones of the plurality of reduction steps and multiple ones of the inverse calculations if the bit position of the MSB of the value in U3 differs by less than the predetermined number from the bit position of the MSB of the value in V3.