US5513133A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compact microelectronic device for performing modular multiplication and exponentiation over large numbers
Assignee: Western Digital Israel Ltd
•
Filing: 1993-11-18
•
Granted: 1996-04-30
•
Expires: 2013-11-18
Abstract
Abstract A compact synchronous microelectronic peripheral machine for standard microprocessors with means for proper clocking and control, has as essential elements: three main subdivided, switched and docked shift registers, B, S, and N; two only multiplexed serial/parallel multipliers; borrow detectors, ancillary subtractors and adders; delay registers and switching elements; all of which embody a totally integrated concurrent and synchronous process approach to modular multiplication, squaring, and exponentiation. A method for carrying out modular multiplication, wherein the multiplicand A , the multiplier B and the modul, N, comprise m characters of k bits each, the multiplier not being greater than the modulus, is also described, wherein the multiplicand can be much larger than the modulus. It is demonstrated how the device can be used as a large number processor in the normal field of numbers.
Inventors
- 👤 Carmi D. Cressel
- 👤 David Hendel
- 👤 Itai Dror
- 👤 Isaac Hadad
- 👤 Benjamin Arazi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 18:13
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/728
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
276 words
Microelectronic apparatus for performing modular multiplication of a multiplier by a multiplicand, the apparatus comprising: first (B), second (S) and third (N) main switched and clocked serial -in serial-out registers respectively operative to store the multiplier, a partial result and a modulus; a first multiplying device in which the multiplicand resides and which is operative, for each of a plurality of portions of the multiplicand in turn, to receive the multiplier from the B register, to multiply the multiplier by a current portion of the multiplicand, and to generate an output comprising a product of said multiplication; a serial adder operating on the output of the first multiplying device and a limited congruence of the partial result residing in the s register and operative to provide an output; a second multiplying device receiving, in a first phase, the output of the serial adder and a Montgomery constant and receiving, in a second phase, the modulus from the N register, and operative, in the first phase, to compute a first phase product of the Montgomery constant by a portion of the output of the serial adder and, in the second phase, to multiply the modulus by the first phase product, thereby to generate a second phase output which, when combined with the serial adder output, generates said partial result; and a subtractor for subtracting the modulus from the contents of the S register, to produce a limited congruence thereof wherein, after the plurality of portions of the multiplicand have been processed by the first multiplying device, said partial result constitutes a limited congruence of a result of performing said modular multiplication of said multiplier by said multiplicand.
Claim 2
Dependent Claim
276 words
Microelectronic apparatus for performing modular multiplication of a multiplier by a multiplicand, the apparatus comprising: first (B), second (S) and third (N) main switched and clocked serial -in serial-out registers respectively operative to store the multiplier, a partial result and a modulus; a first multiplying device in which the multiplicand resides and which is operative, for each of a plurality of portions of the multiplicand in turn, to receive the multiplier from the B register, to multiply the multiplier by a current portion of the multiplicand, and to generate an output comprising a product of said multiplication; a serial adder operating on the output of the first multiplying device and a limited congruence of the partial result residing in the s register and operative to provide an output; a second multiplying device receiving, in a first phase, the output of the serial adder and a Montgomery constant and receiving, in a second phase, the modulus from the N register, and operative, in the first phase, to compute a first phase product of the Montgomery constant by a portion of the output of the serial adder and, in the second phase, to multiply the modulus by the first phase product, thereby to generate a second phase output which, when combined with the serial adder output, generates said partial result; and a subtractor for subtracting the modulus from the contents of the S register, to produce a limited congruence thereof wherein, after the plurality of portions of the multiplicand have been processed by the first multiplying device, said partial result constitutes a limited congruence of a result of performing said modular multiplication of said multiplier by said multiplicand.
Claim 3
Dependent Claim
63 words
Apparatus according to claim 1 further comprising a second subtractor for subtracting the modulus from the contents of the B register, to produce the contents of the B register reduced by the modulus, and wherein said first multiplying device includes a first serial/parallel multiplying device serially receiving said contents of the B register reduced by the modulus, and receiving the multiplicand in parallel.
Claim 4
Dependent Claim
20 words
Apparatus according to claim 1 wherein said first multiplying device includes a first input latch in which the multiplicand resides.
Claim 5
Dependent Claim
19 words
Apparatus according to claim 1 wherein the second multiplying device includes a second input latch which receives the multiplicand.
Claim 6
Dependent Claim
17 words
Apparatus according to claim 1 employing no multiplying devices other than said first and second multiplying devices.
Claim 7
Dependent Claim
16 words
Apparatus according to claim 1 wherein said second multiplying device comprises a multiplexed serial/parallel multiplying device.
Claim 8
Dependent Claim
41 words
Apparatus according to claim 1 wherein a Montgomery constant J 0 resides in the second multiplying device in the first phase and the first phase output of the second multiplying device resides in the second multiplying device in the second phase.
Claim 9
Dependent Claim
47 words
Apparatus according to claim 7 comprising an array of 2-to-1 multiplexers operative to feed the Montgomery constant into said second multiplying device in the first phase, and to feed the first phase output of the second multiplying device into the second multiplying device, in the second phase.
Claim 10
Dependent Claim
41 words
Apparatus according to claim 8 comprising a serial/parallel register serially receiving the output of the second multiplying device in the first phase and feeding the output in parallel into said second multiplying device via said multiplexer array in the second phase.
Claim 11
Dependent Claim
132 words
Apparatus according to claim 9 wherein the lengths of the first and second multiplying devices are both k, the apparatus also comprising a second adder operative to receive, with a delay of k effective clock cycles, the output of the serial adder and to receive the second phase output of the second multiplying device and to add these outputs, thereby to generate second adder output in which the k least significant bits are zeros, and to feed said second adder output into a selected one of the B register or the S register, wherein said array of multiplexers comprises k 2-to-1 multiplexers and wherein said serial/parallel register is of length k; and a k-bit delay unit intermediate the first and second adders operative to provide the delay of k effective clock cycles.
Claim 12
Dependent Claim
114 words
Apparatus according to claim 1 wherein the lengths of the first and second multiplying devices are both k, the apparatus also comprising: a second adder operative to receive, with a delay of k effective clock cycles, the output of the serial adder and to receive the second phase output of the second multiplying device and to add these outputs, thereby to generate second adder output in which the k least significant bits are zeros, and to feed said second adder output into a selected one of the B register or the S register; and a k-bit delay unit intermediate the serial and second adders operative to provide the delay of K effective clock cycles.
Claim 13
Dependent Claim
37 words
Apparatus according to claim 11 also comprising a borrow sensing device operative to receive output from the second adder and to determine whether the output of the second adder is larger than or equal to the module.
Claim 14
Dependent Claim
53 words
Apparatus according to claim 11 also comprising a first serial subtracter receiving the contents of the B register, subtracting therefrom the modulus, thereby to compute a modularly reduced multiplier, if the second adder output is larger than or equal to the modulus, and feeding the modularly reduced multiplier to said first multiplying device.
Claim 15
Dependent Claim
59 words
Apparatus according to claim 13 also comprising: a second subtracter receiving the contents of the S register; and a comparator determining whether the second adder output is larger than or equal to the modulus, wherein the comparator is operatively associated with the second subtracter so as to control subtraction of the modulus from the contents of the S register.
Claim 16
Dependent Claim
58 words
Apparatus according to claim 13 comprising: a second subtracter receiving the contents of the B register; and a comparator determining whether the second adder output is larger than or equal to the modulus, wherein the comparator is operatively associated with the second subtracter so as to control subtraction of the modulus from the contents of the B register.
Claim 17
Dependent Claim
56 words
Apparatus according to claim 1 also comprising a second subtracter receiving the contents of the S register and subtracting therefrom the modulus, thereby to compute a modularly reduced multiplier, if the second adder output is larger than or equal to the modulus, and feeding the modularly reduced output of the S register to said multiplying device.
Claim 18
Dependent Claim
13 words
Apparatus according to claim 11 wherein said second adder comprises a serial adder.
Claim 19
Dependent Claim
30 words
Apparatus according to claim 1 wherein said first and second multiplying devices are each of length k and wherein the duration of the first phase is k effective clock cycles.
Claim 20
Dependent Claim
26 words
Apparatus according to claim 1 wherein the serial adder operates on the output of the first multiplying device and modularly reduced contents of the S register.
Claim 21
Dependent Claim
14 words
Apparatus according to claim 1 wherein said main switched and clocked registers are subdivided.
Claim 22
Dependent Claim
13 words
Apparatus according to claim 1 wherein said second phase output comprises serial output.
References Cited (Backward Citations)
US4625076A
Cited
EP0281303A2
Cited
US4891781A
Cited
EP0350278A2
Cited
US5073870A
Cited
US5121431A
Cited
US5210710A
Cited
US5101431A
Cited
EP0502782A2
Cited
US5261001A
Cited
EP0531158A2
Cited
US5321752A
Cited
US5159632A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-30 | 1999-10-30 | 2000-04-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-30 | 2003-10-30 | 2004-04-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-30 | 2007-10-30 | 2008-04-30 | $7700.00 | Window Closed / Lapsed |