Browse Prior Art Database

Method for big number modulo inversion and big number division

IP.com Disclosure Number: IPCOM000020404D
Publication Date: 2003-Nov-19

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for big number modulo inversion and big number division. Benefits include improved functionality, improved performance, and improved cost effectiveness.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Method for big number modulo inversion and big number division

Disclosed is a method for big number modulo inversion and big number division. Benefits include improved functionality, improved performance, and improved cost effectiveness.

Background

         The big number modulo inversion function is a basic building block for many asymmetric-key cryptographic systems design. Conventional implementation is tailored for the desktop or more powerful server workstations. When adopted to the emerging handheld platforms, the resulting performance of these implementations is no longer optimal, due to their dependency on huge operational buffers.

         Conventional big number integer modulo inversion uses subtraction.

General description

         The disclosed method computes big number integer modulo inversion and big number division. For big number integer modulo inversion, the method improves performance by 30% and reduces the operational buffer by 50%. For big number division, the method improves performance by 30%.

Advantages

         The disclosed method provides advantages, including:
•         Improved functionality due to extending the Euclidean method of iteration
•         Improved performance due to using a MAC instruction

•         Improved performance due to reducing the number of intermediate variables and minimizing the operational buffer

•         Improved performance due to computing intermediate variables within a non-negative region

•         Improved performance due to using single-step correction and ensuring a definite ending process

•         Improved cost effectiveness due to reducing the operational buffer

Detailed description

         The disclosed method computes big number integer modulo inversion and big number division.

Big number integer modulo inversion

         The disclosed method is based on the relationships between the big number integer modulo, N, and the sequence of the remainders {Rk} generated during the course of the Euclidean iteration, such as, for k=0, 1, 2, …3. Intermediate variables, Uk and the remainders, Rk have the following relationship:

N = Uk* Rk+1 + Uk+1 * Rk

         This relationship enables the elimination of the buffer dedicated to keeping a copy of modulo N. Additionally, the buffer for the intermediate variables, Uk and Rk, is not required to be larger than that for modulo N, if all Uk values are computed within the non-negative region. That relationship reduces the size for the required operational buffer by 50%.

         To ensure the non-negative characteristics of the intermediate variables, Uk, the disclosed method adopts multiplier accumulator (MAC) based iteration, such as, by initializing U0 = 0, and U1 = 1, and within each iteration, computes as follows:

Uk+1 = Uk-1 + Uk*Qk

         The result is a 30% performance gain.

         The disclosed method can be implemented in a microprocessor-based platform and a micro-architectural-based cryptographic acceleration engine, which supports big number long division and MAC operation (see Figure 1).

         The disclosed scheme is verifiable by the proving two propo...