Fast precomputation for Montgomery multiplier

Patent metadata

Field	Value
Publication number	US-12079594-B2
Application number	US-202117180999-A
Country	US
Kind code	B2
Filing date	Feb 22, 2021
Priority date	Feb 22, 2021
Publication date	Sep 3, 2024
Grant date	Sep 3, 2024

Abstract

A Montgomery multiplication apparatus (MMA), for multiplying two multiplicands modulo a predefined number, includes a pre-compute circuit and a Montgomery multiplication circuit. The pre-compute circuit is configured to compute a Montgomery pre-compute value by performing a series of iterations. In a given iteration, the pre-compute circuit is configured to modify one or more intermediate values by performing bit-wise operations on the intermediate values calculated in a preceding iteration. The Montgomery multiplication circuit is configured to multiply the two multiplicands, modulo the predefined number, by performing a plurality of Montgomery reduction operations using the Montgomery pre-compute value computed by the pre-compute circuit.

First claim

The invention claimed is:

1. A Montgomery pre-compute circuit, comprising a carry-save-adder (CSA), a sum-shifter and a carry-shifter, which are to compute a Montgomery pre-compute value for a Montgomery multiplication operation by performing a series of iterations, wherein, in a given iteration in the series:
the CSA is to produce a sum-output and a carry-output; and
the sum-shifter and the carry-shifter are to left-shift the sum-output and the carry-output, respectively, and to feed-back the left-shifted sum-output and the left-shifted carry-output to respective inputs of the CSA.

2. The Montgomery pre-compute circuit according to claim 1 , wherein the Montgomery pre-compute value is given by (2 2n modulo R), n denoting a number of bits of the Montgomery multiplication operation, and R denoting a preselected number.

3. The Montgomery pre-compute circuit according to claim 2 , wherein R=N, N denoting a divisor of the Montgomery multiplication operation.

4. The Montgomery pre-compute circuit according to claim 1 , further comprising an adder, to calculate the Montgomery pre-compute value by summing the sum-output and the carry-output following the series of iterations.

5. The Montgomery pre-compute circuit according to claim 1 , wherein, in the given iteration, the CSA is further to receive as input a modulo-correction number set to N multiplied by −1, −2 or 0, N denoting a divisor of the Montgomery multiplication operation.

6. The Montgomery pre-compute circuit according to claim 1 , wherein the CSA is a three-input CSA that is further to receive as input a modulo-correction number set to N multiplied by −1, −2 or 0, N denoting a divisor of the Montgomery multiplication operation.

7. The Montgomery pre-compute circuit according to claim 1 , wherein the CSA is a four-input CSA that is further to receive as input (i) a first modulo-correction number set to N multiplied by −1 or 0, and (ii) a second modulo-correction number set to N multiplied by −1 or 0, N denoting a divisor of the Montgomery multiplication operation.

8. A method for computing a Montgomery pre-compute value for a Montgomery multiplication operation, the method comprising performing a series of iterations using a carry-save-adder (CSA), a sum-shifter and a carry-shifter, including, in a given iteration in the series:
producing a sum-output and a carry-output by the CSA; and
left-shifting the sum-output and the carry-output by the sum-shifter and the carry-shifter, respectively; and
feeding-back the left-shifted sum-output and the left-shifted carry-output to respective inputs of the CSA.

9. The method according to claim 8 , wherein the Montgomery pre-compute value is given by (2 2n modulo R), n denoting a number of bits of the Montgomery multiplication operation, and R denoting a preselected number.

10. The method according to claim 9 , wherein R=N, N denoting a divisor of the Montgomery multiplication operation.

11. The method according to claim 8 , further comprising calculating the Montgomery pre-compute value by summing the sum-output and the carry-output following the series of iterations.

12. The method according to claim 8 , further comprising, in the given iteration, receiving by the CSA as input a modulo-correction number set to N multiplied by −1, −2 or 0, N denoting a divisor of the Montgomery multiplication operation.

13. The method according to claim 8 , wherein the CSA is a three-input CSA, and comprising further receiving, as input to the CSA, a modulo-correction number set to N multiplied by −1, −2 or 0, N denoting a divisor of the Montgomery multiplication operation.

14. The method according to claim 8 , wherein the CSA is a four-input CSA, and comprising further receiving, as input to the CSA, (i) a first modulo-correction number set to N multiplied by −1 or 0, and (ii) a second modulo-correction number set to N multiplied by −1 or 0, N denoting a divisor of the Montgomery multiplication operation.

Assignees

• Mellanox Technologies Ltd

Inventors

• Zevulun Adir
• Basher Uria
• Shmuel Nir
• Witulski Ben

Classifications

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• G06F21/575

  Secure boot · CPC title

• G06F7/722

  Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title

• G06F7/728 Primary

  using Montgomery reduction · CPC title