Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2003-09-12
2004-10-19
Malzahn, D. H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06807555
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 11-310619, filed Nov. 1, 1999, the entire contents of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
The present invention relates to a modular arithmetic processing apparatus and method for performing an arithmetic operation of a large integer at a high speed by parallel processing on the basis of a residue number system.
As a method of executing an efficient arithmetic operation of a large integer, a modular arithmetic or residue number system is known. In the residue number system, a set of relatively small integers {a
1
, a
2
, . . . , a
n
}, which are relatively prime to each other, is prepared, and a large integer as an expression target is expressed by residues obtained by dividing the integer by these integers. This set of integers will be referred to as the base of the residue number system hereinafter. The number n of elements will be referred to as a base size.
For example, when a base {a
1
, a
2
, . . . , a
n
} is given, an integer n is expressed by n residues {x
1
, x
2
, . . . , x
n
} obtained by dividing the integer x by the base a
i
(i=1, 2, . . . , n). If the number x is a positive integer smaller than a product A (=a
1
a
2
. . . a
n
) of the base elements, the number x can be uniquely expressed modulo the product A of the base elements. In other words, the number x and its residue number system expression {x
1
, x
2
, . . . , x
n
} are in a one-to-one correspondence.
In such residue number system expression, to calculate the product of two integers x and y, the product is obtained in units of elements, and then, residues are obtained by dividing the integers by a corresponding base a
i
. In other words, generally, a product modulo the product A of base elements is obtained by calculating products modulo the corresponding base a
i
in units of elements. This also applies to addition and subtraction. For elements x
i
and y
i
corresponding to the base a
i
, an addition or subtraction modulo a
i
is executed.
In the arithmetic operation using such a residue number system, a multiplication, addition, or subtraction is executed by arithmetic operation modulo bases independently corresponding to the elements. For example, when values within the word length of a computer are employed as a base, the arithmetic operation of a very large integer can be realized by repeating a single-precision arithmetic operation.
Since the single-precision arithmetic operations can be independently executed in units of bases, preparing a plurality of calculators allows parallel processing. For example, when the base size is n, n multipliers with a residue function are prepared and parallelly operated whereby multiplication modulo the product A of base elements can be completed within the same time as that for one multiplication with single-precision residue.
A current computer normally uses binary expression. Calculation of a large integer based on binary expression takes a processing time proportional to the total number of digits (or bit length) of the large integer because carry propagates from the LSB (Least Significant Bit) to the MSB (Most Significant Bit). This is disadvantageous in processing speed as compared to parallel processing using a residue number system.
On the other hand, the residue number system is known for a long time as a scheme of efficiently executing a multiplication, addition, or subtraction of a large integer relative to radix representation represented by binary expression because no carry between words occurs.
However, for a division or comparison between two numbers, a more efficient means than the radix representation has been unknown. For this reason, how to apply the residue number system in detail has not been known until 80s, although it is supposed that the residue number system is suitable to an application for executing arithmetic operation of a large integer at a high speed, like public key cryptography system.
Posch et al. have proposed a scheme of executing arithmetic operation of RSA cryptography of a public key cryptography system using the residue number system in “Modulo Reduction in Residue Number Systems” (IEEE Transaction on Parallel and Distributed Systems, Vol. 6, No. 5, May 1995, pp. 449-454) and “RNS-Modulo Reduction Upon a Restricted Base Value Set and its, Applicability to RSA Cryptography” (Computer & Security, Vol. 17, pp. 637-650, 1998).
In addition, Kornerup et al. have proposed a similar high-speed arithmetic scheme in “An RNS Montgomery Modular Multiplication Algorithm” (13th IEEE Symposium on Computer Arithmetic (Proceedings of ARITH13), IEEE Computer Society, pp. 234-239), and Paillier has proposed a similar scheme in “Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor” (Springer-Verlag, Lecture Notes in Computer Science No. 1560 Public Key Cryptography (PKC '99), pp. 223-234).
The main reason why the residue number system is used for RSA cryptography is that this cryptography is constructed by repeating a residue multiplication of a very large integer with 200 decimal digits or more, and high-speed processing can be realized using the above-described characteristic of the residue number system, which allows high-speed multiplication and addition/subtraction.
A common point of the schemes of Posch et al., Kornerup et al., and Paillier is that the Montgomery algorithm is combined with the residue number system to avoid a division disadvantageous for the residue number system. As another common point of the three schemes, base conversion or base extension is executed in the course of processing to obtain a value that expresses an integer, which is expressed by a residue using a certain base, with another base. In any scheme, whether base conversion or base extension can be efficiency executed affects the efficiency of the entire processing.
Two terms “base conversion” and “base extension” are used here. Base conversion means that a value expressed by a given base is re-expressed using another base prime to the given base. Base extension means that a value expressed by a base with the size n is expressed by a base with a size (n+1), i.e., a base obtained by adding, to the original base, an integer that is prime to the original base, and the (n+1)th element at that time is obtained. With the base extension scheme, base conversion can be constituted by repeating the base extension n times. In realizing RSA cryptography using the residue number system, a scheme and apparatus for efficiently executing base conversion (or base extension) are necessary.
However, the above-described three base conversion schemes and the base conversion schemes that have been conventionally proposed are inefficient in some points, as will be described below.
In the scheme proposed by Posch et al., the base conversion scheme mentioned in the arithmetic operation of RSA cryptography may generate an error in the value after conversion when the value before conversion is smaller than a predetermined value. To avoid this, Posch et al. has proposed a procedure in which an appropriate offset is added to the input of base conversion processing to convert the input into a value that causes no error in base conversion processing, the conversion result is base-converted, and the effect of offset is removed from the obtained base conversion result. However, such pre-processing and post-processing for offset increase the entire arithmetic amount, resulting in low efficiency.
Additionally, since the scheme of Posch et al. considerably limits the size of the RSA cryptography key calculable by a given base and requires a multiplier to calculate a correction term necessary for base conversion, it is also disadvantageous in the area in circuitry and processing delay.
FIG. 5
is a block diagram showing the schematic arrangement of a modular arithmetic circuit used for the RSA cryptography ari
Kabushiki Kaisha Toshiba
Malzahn D. H.
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
LandOfFree
Modular arithmetic apparatus and method having high-speed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modular arithmetic apparatus and method having high-speed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular arithmetic apparatus and method having high-speed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326770