Table driven method for calculating arithmetic inverse for use in cryptography
AssigneeMatsushita Electric Industrial Co., Ltd.
InventorGregory M. Perkins
Life of this patent
Estimating the term…
Abstract
A method for calculating the arithmetic inverse of a number V modulo U, where U is a prime number, that may be used in cryptography, uses a modified extended greatest common divisor (GCD) algorithm that includes a plurality of reduction steps and a plurality of inverse calculations. In this algorithm, the values U and V are assigned to respective temporary variables U3 and V3 and initial values are assigned to respective temporary variables U2 and V2. The algorithm then tests a condition and, if the condition tests true, combines multiple ones of the plurality of reduction steps and multiple ones of the inverse calculations into a single iteration of the GCD algorithm.
Claims18
A method for performing modular division operations used in a cryptographic process over a finite field FU defined for a prime number U, in which values are divided by an integer divisor V modulo U, 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;
- testing a condition and, if the condition tests true,
- 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 condition tests false,
- performing a single one of the reduction steps;
- and
- performing a single one of the inverse calculation steps.
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 values are divided by an integer divisor V modulo U, 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;
- testing a condition and, if the condition tests true,
- 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 condition tests false,
- performing a single one of the reduction steps;
- and
- performing a single one of the inverse calculation steps.
Cryptographic apparatus which performs division operations over a finite field FU defined for a prime number U, in which values are divided by an integer divisor V modulo U, 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 testing a condition;
- and
- means for combining multiple ones of the plurality of reduction steps and multiple ones of the inverse calculations if the condition test true;
Dependencies are inferred from the claim text.