Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-04
2004-02-10
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06691143
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to multiplication circuits and methods, and more particularly to Montgomery multiplication circuits and methods.
BACKGROUND OF THE INVENTION
Montgomery multiplication is widely used to perform modular multiplication. Modular multiplication is widely used in encryption/decryption, authentication, key distribution and many other applications. Montgomery multiplication also may be used for the basis for Montgomery exponentials, which also is widely used in the above-described and other applications.
Montgomery multiplication is described in U.S. Pat. No. 6,185,596 to Hadad et al. entitled
Apparatus
&
Method for Modular Multiplication
&
Exponentiation Based on Montgomery Multiplication
; U.S. Pat. No. 6,061,706 to Gai et al. entitled
Systolic Linear
-
Array Modular Multiplier with Pipeline Processing Elements
; U.S. Pat. No. 6,085,210 to Buer entitled
High
-
Speed Modular Exponentiator and Multiplier
; U.S. Pat. No. 5,513,133 to Cressel et al. entitled
Compact Microelectronic Device for Performing Modular Multiplication and Exponentiation Over Large Numbers
; and European Patent Application 0 656 709 A2 to Yamamoto et al. entitled
Encryption Device and Apparatus for Encryption/Decryption Based on the Montgomery Method Using Efficient Modular Multiplication
. Montgomery multiplication also is described in publications by Gutub et al. entitled An
Expandable Montgomery Modular Multiplication Processor
, Eleventh International Conference on Microelectronics, Nov. 22-24, 1999, pp. 173-176; Tenca et al. entitled
A Scalable Architecture for Montgomery Multiplication
, First International Workshop, Cryptographic Hardware and Embedded Systems, Lecture Notes on Computer Science, Vol. 1717, 1999, pp. 94-108; and Freking et al. entitled
Montgomery Modular Multiplication and Exponentiation in the Residue Number System
, Conference Record of the Thirty-Third Asilomar Conference Signals, Systems, and Computers, Vol. 2, 1999, pp. 1312-1316. The disclosure of all of these references is hereby incorporated herein in their entirety as if set forth fully herein.
Montgomery multiplication often is used with large numbers. Accordingly, it may be desirable to accelerate Montgomery multiplication so that rapid encryption/decryption, authentication, key management and/or other applications may be provided.
SUMMARY OF THE INVENTION
Embodiments of the invention provide Montgomery multipliers and methods that modular multiply a residue multiplicand by a residue multiplier to obtain a residue product. Embodiments of Montgomery multipliers and methods include a scalar multiplier, a first vector multiplier and a second vector multiplier. A controller is configured to control the scalar multiplier, the first vector multiplier and the second vector multiplier, to overlap scalar multiplies using a selected digit of the multiplier and vector multiplies using a modulus and the multiplicand. It will be understood that as used herein, digit refers to a number place in any base number system, including decimal, hexidecimal and binary. The latency of Montgomery multiplication thereby can be reduced to nearly the latency of a single scalar multiplication.
Montgomery multipliers and methods according to other embodiments of the invention include a scalar multiplier that is configured to multiply a least significant digit of the multiplicand by a first selected digit of the multiplier, to produce a scalar multiplier output. A first vector multiplier is configured to multiply the scalar multiplier output by a modulus, to produce a first vector multiplier output. A second vector multiplier is configured to multiply a second selected digit of the multiplier by the multiplicand, to produce a second vector multiplier output. An accumulator is configured to add the first vector multiplier output and the second vector multiplier output, to produce a product output. The first selected digit of the multiplier preferably is a next more significant digit of the multiplier, relative to the first selected digit of the multiplier.
In other embodiments of the invention, the scalar multiplier is further configured to multiply the least significant digit of the multiplicand by the first selected digit of the multiplier and by one over (i.e., divided by) a negative of a least significant digit of the modulus, to produce the scalar multiplier output. In yet other embodiments, a first multiplexer also may be provided that is configured to multiplex the least significant digit of the multiplicand and one over the negative of the least significant digit of the modulus into the scalar multiplier.
In still other embodiments of the invention, a first feedback path is configured to feed the scalar multiplier output back into the scalar multiplier. A second feedback path is configured to feed the product output into the scalar multiplier. A summer is configured to sum the scalar multiplier output and the product output from the respective first and second feedback paths and to provide the sum of the scalar multiplier output and the product output to the scalar multiplier. A second multiplexer also is provided that is configured to multiplex the first selected digit of the multiplier and the sum of the scalar multiplier output and the product output into the scalar multiplier. A first register is coupled between the scalar multiplier output and the first vector multiplier and a second register is coupled between the product output and the second feedback path. Accordingly, latency in Montgomery multiplication can be reduced.
REFERENCES:
patent: 5274707 (1993-12-01), Schlafly
patent: 5329623 (1994-07-01), Smith et al.
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5961626 (1999-10-01), Harrison et al.
patent: 5987131 (1999-11-01), Clapp
patent: 6061706 (2000-05-01), Gai et al.
patent: 6081895 (2000-06-01), Harrison et al.
patent: 6085210 (2000-07-01), Buer
patent: 6185596 (2001-02-01), Hadad et al.
patent: 6209016 (2001-03-01), Hobson et al.
patent: 6219789 (2001-04-01), Little et al.
patent: 2002/0120658 (2002-08-01), Chen et al.
patent: 0 531 158 (1993-03-01), None
patent: 0 601 907 (1994-06-01), None
patent: 0 656 709 (1995-06-01), None
Gutub et al. entitledAn Expandable Montgomery Modular Multiplication Processor, Eleventh International Conference on Microelectronics, Nov. 22-24, 1999, pp. 173-176.
Tenca et al. entitledA Scalable Architecture for Montgomery Multiplication, First International Workshop, Cryptographic Hardware and Embedded Systems, Lecture Notes on Computer Science, vol. 1717, 1999, pp. 94-108.
Freking et al. entitledMontgomery Modular Multiplication and Exponentiation in the Residue Number System, Conference Record of the Thirty-Third Asilomar Conference Signals, Systems, and Computers, vol. 2, 1999, pp. 1312-1316.
Menezes et al., Chapter 14,Efficient Implementation, Handbook of Applied CryptographyCRC Press, Inc., 1997, p. 591-634.
International Search Report, PCT/US01/14616, Feb. 27, 2002.
International Search Report, PCT/US01/14561, Feb. 27, 2002.
Tiountchik,Systolic Modular Exponentiation Via Montgomery Algorithm, Electronics Letters, vol. 34, No. 9, Apr. 30, 1998, pp. 874-875.
Koç et al.,Analyzing and Comparing Montgomery Multiplication Algorithms, IEEE Micro, vol. 16, No. 1, Jun. 1, 1996, pp. 26-33.
Eldridge et al.,Hardware Implementation of Montgomery's Modular Multiplication Algorithm, IEEE Transactions on Computers, vol. 42, No. 6, Jun. 1993, pp. 693-699.
Sauerbrey,A Modular Exponentiation Unit Based on Systolic Arrays, Advances in Cryptology-Auscrypt. Gold Coast, Queensland, Dec. 13-16, 1992, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, vol. Conf. 3, Dec. 13, 1992, pp. 505-516.
Kent et al.Security Architecture for the Internet Protocol. Nov. 1998, pp. 1-66.
Hifn 6500 Public Key Processor. http://www.hifn.com/products/6500.html, printed Apr. 29, 2001.
FastMap Integrated Circuit. Rainbow Technologies Internet Security Group. Oct. 1, 1998.
Preuss, Lisa. “Rainbow Technologies Announces OEM Availability of FastMap
CyberGuard Corporation
Mai Tan V.
Myers Bigel & Sibley & Sajovec
LandOfFree
Accelerated montgomery multiplication using plural multipliers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accelerated montgomery multiplication using plural multipliers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated montgomery multiplication using plural multipliers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301061