Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-28
2001-11-20
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06321247
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to processing data, and more particularly to a system and method for using a fast implementation of modulo multiplication.
BACKGROUND OF THE INVENTION
Modulo multiplication is an arithmetic process of determining the remainder of the product of two numbers. Modulo multiplication is a particularly versatile tool that has many applications in the computer field. For example, specific implementations of cryptography use modulo multiplication to perform certain processing functions. The remainder of modulo multiplication, also known as the residue of the modulo of the product of two numbers is typically used in many data processing applications.
In the field of cryptography many different types of encryption and decryption have been developed to prevent unauthorized file access. IDEA, a block cipher, developed by Xuejia Lai and James Massey and patented under International Patent PCT/CH91/00117 on Nov. 28, 1991, and a patent held by Ascom-Tech AG of Magenwil, Switzerland, is one example of a type of encryption/decryption method that utilizes modulo multiplication. On page 320 of
Applied Cryptography
, Bruce Schneier describes IDEA as a cipher that operates on 64-bit plaintext blocks and has a key of 128 bits in length. IDEA uses the same algorithm for both encryption and decryption.
IDEA uses an algorithm that includes a combination of operations from different algebraic groups. The three algebraic groups include “XOR,” “Addition modulo 2
16
,” and “multiplication modulo 2
16
+1.” The three algebraic groups of IDEA can be implemented in both hardware and software to perform the encryption/decryption of this cipher.
Although IDEA is effective in its use of multiplication modulo 2
16
+1, the conventional process for determining a remainder from the division of two binary numbers requires reductions that are both costly and time consuming. Furthermore, a conventional hardware implementation of modulo multiplication requires a divider circuit. An example of a conventional process for performing modulo multiplication is shown below.
(1) A*B mod M
(2) Where: M=2
N
+1
(3) N=4
(4) M=2
4
+1
(5) M=17 (base 10)
(6) A=01010 (base 2)=10 (base 10)
(7) B=01110 (base 2)=14 (base 10)
(
8
)
A
*
B
:
(
base
2
)
01010
01110
_
010100
01010
01010
00000
_
(
9
)
10001100
Line 1 above shows the modulo multiplication equation of (A*B mod M), where A, B and M are each binary numbers. Line 2 shows that modulus “M” is equal to two to the power of N, plus one, where “N+1” is the length in bits of both variables A and B. Line 3 shows that in this example the bit length of N is equal to four. Hence, in line 4, “M” is equal to two to the fourth power plus one. Line 5 shows that the result of the equation of line 4 has the base 10 value of 17. Lines 6 and 7 show both the binary and corresponding decimal values chosen for the variables “A” and “B” of line 1. Line 8 shows multiplication of the binary values of variable “A” and “B.” Line 9 shows that the resulting product of the equation of line 8 is the binary value “10001100.”
FIG. 1
shows an example of a conventional process for determining the resulting modulus of the product of variables “A” and “B.” As shown, a conventional process for this example requires four successive reductions of the product of A and B by modulus “M.” The result of the four reductions yields the resulting modulus, also known as a remainder or residue, having a binary value “00000100.”
A conventional hardware circuit of the modulo operation of
FIG. 1
would include a divider circuit to perform the successive reductions required to determine the remainder of the product of “A” and “B.” The four successive reductions would require four repetitive cycles of a divider circuit. One of ordinary skill in the art will understand, that as “A,” “B” and the resulting product of “A” and “B” grow larger, the number of repetitive cycles needed to determine the remainder will also increase. It will be appreciated that a need to perform numerous cycles of a divider circuit to determine a remainder is costly, slow and requires excessive processing resources.
Therefore, there is a need to provide a system and method for performing fast and efficient modulo multiplication that minimizes processing requirements.
SUMMARY OF THE INVENTION
The present invention provides a first and second embodiment of a system and method for performing a modulo multiplication of two numbers, where the remainder is determined without a need to perform successive reductions. In the first embodiment, the present invention performs modulo multiplication of two numbers N+1 bits long with a modulus for all numbers having a value of 2
N
+1. In the second embodiment which is applicable to “IDEA” cryptography where the value “0” is used to represent 2
N
, the present invention performs modulo multiplication of two numbers N+1 bits long with a modulus for prime numbers having a value of 2
N
+1. It will be appreciated that since “0” is used to represent
2
N
, the two numbers are stored as N bits but are multiplied as two N+1 bit numbers, the additional bit being generated for identifying the zero case. Since the present invention eliminates the need to perform successive reductions, a hardware implementation of the present invention does not require a divider circuit. One of ordinary skill in the art will understand that eliminating successive reductions reduces processing cycles, thereby promoting performance gains and cost savings.
From a system point of view, a first embodiment of the invention performs modulo multiplication of two numbers N+1 bits in length with a modulus equal to 2
N
+1 and where each of the numbers has a value less than a value of the modulus. The system of the first embodiment comprises: a multiplier module for multiplying the two numbers to yield a resulting product having a 2N+1 bit result, a high bit portion and a low bit portion; an inverter module coupled to the multiplier module for inverting the bits of the high bit portion; a compare module coupled to the multiplier module for comparing the high bit portion and the low bit portion to determine an additional value; and a first adder module coupled to the multiplier module and the inverter module for determining a remainder from a sum of the inverted high bit portion, the low bit portion, a value of one and the additional value.
From a system point of view, a second embodiment of the invention performs modulo multiplication of two numbers N+1 bits in length with a modulus equal to 2
N
+1 and where a value of zero is used to represent 2
N
and where each of the numbers has a value less than a value of the modulus. The system of the second embodiment comprises: a multiplier module for multiplying the two numbers to yield a resulting product having a high bit portion and a low bit portion; an inverter module coupled to the multiplier module for inverting the bits of the high bit portion; a compare module coupled to the multiplier module for comparing the high bit portion and the low bit portion to determine an additional value; and a first adder module coupled to the multiplier module and the inverter module for determining a remainder from a sum of the inverted high bit portion, the low bit portion, a value of one and the additional value.
From a method point of view, a first embodiment of the invention performs modulo multiplication of two numbers N+1 bits in length with a modulus equal to 2
N
+1 and where each of the numbers has a value less than a value of the modulus. The method of the first embodiment comprises: multiplying two numbers to yield a resulting product having a 2N+1 bit, a high bit portion and a low bit portion; inverting all bits of the high bit portion; determining a remainder
Langford Susan K.
Matthews, Jr. Donald P.
Compaq Computer Corporation
Fenwick & West LLP
Mai Tan V.
LandOfFree
System and method for multiplication modulo (2N+1) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for multiplication modulo (2N+1), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for multiplication modulo (2N+1) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2576692