Accelerated montgomery multiplication using plural multipliers

• US 20020013799A1
• Filed: 05/04/2001
• Published: 01/31/2002
• Est. Priority Date: 05/11/2000
• Status: Active Grant

• Current Assignee: NBMK Encryption Technologies, Inc​.
• Original Assignee: Cyberguard Corporation (McAfee, LLC)
• Inventors: Blaker, David M.
• Granted Patent: US 6,691,143 B2
• Time in Patent Office: Days
• US Class Current: 708/491
• CPC Class Codes: G06F 21/123 by using dedicated hardware, e.g. dongles, smart cards, cryptographic processors, global positioning systems [GPS] devices
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/0877 using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]

Abstract

Montgomery multipliers and methods modular multiply a residue multiplicand by a residue multiplier to obtain a residue product, using 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. The scalar multiplier 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. The first vector multiplier is configured to multiply the scalar multiplier output by a modulus, to produce a first vector multiplier output. The 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 latency of Montgomery multiplication thereby can be reduced to nearly the latency of a single scalar multiplication.

Claims

1. A Montgomery multiplier that modulo multiplies a residue multiplicand by a residue multiplier to obtain a residue product, the Montgomery multiplier comprising:

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 that is configured to multiply the scalar multiplier output by a modulus to produce a first vector multiplier output;

a second vector multiplier that is configured to multiply a second selected digit of the multiplier by the multiplicand to produce a second vector multiplier output; and

an accumulator that is configured to add the first vector multiplier output and the second vector multiplier output to produce a product output.

2. A Montgomery multiplier according to claim 1 wherein 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 a negative of a least significant digit of the modulus to produce the scalar multiplier output.

3. A Montgomery multiplier according to claim 2 further comprising a first multiplexer 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.

4. A Montgomery multiplier according to claim 1 further comprising a first feedback path that is configured to feed the scalar multiplier output back into the scalar multiplier.

5. A Montgomery multiplier according to claim 1 further comprising a second feedback path that is configured to feed the product output back into the scalar multiplier.

6. A Montgomery multiplier according to claim 4 further comprising a second feedback path that is configured to feed the product output back into the scalar multiplier.

7. A Montgomery multiplier according to claim 6 further comprising a second summer that 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.

8. A Montgomery multiplier according to claim 7 further comprising a second multiplexer 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.

9. A Montgomery multiplier according to claim 4 further comprising a second multiplexer that is configured to multiplex the first selected digit of the multiplier and the scalar multiplier output into the scalar multiplier.

10. A Montgomery multiplier according to claim 5 further comprising a second multiplexer that is configured to multiplex the first selected digit of the multiplier and the product output into the scalar multiplier.

11. A Montgomery multiplier according to claim 1 further comprising a first register that is coupled between the scalar multiplier output and the first vector multiplier.

12. A Montgomery multiplier according to claim 5 further comprising a second register that is coupled between the product output and the second feedback path.

13. A Montgomery multiplier according to claim 1 wherein the first selected digit of the multiplier is different from the second selected digit of the multiplier.

14. A Montgomery multiplier according to claim 13 wherein the second selected digit of the multiplier is a next more significant digit of the multiplier, relative to the first selected digit of the multiplier.

15. A Montgomery multiplier that modulo multiplies a residue multiplicand by a residue multiplier to obtain a residue product, the Montgomery multiplier comprising:

a scalar multiplier;

a first vector multiplier;

a second vector multiplier; and

a controller that 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.

16. A Montgomery multiplier according to claim 15 wherein the controller is further configured to control the scalar multiplier to perform a scalar multiply using a least significant digit of the multiplier prior to controlling the vector multipliers to perform the vector multiplies using the modulus and the multiplicand.

17. A Montgomery multiplier according to claim 15 wherein the controller is further configured to control the scalar multiplier to multiply a least significant digit of the multiplicand by a first selected digit of the multiplier to produce a scalar multiplier output, to control the first vector multiplier to multiply the scalar multiplier output by the modulus to produce a first vector multiplier output and to control the second vector multiplier to multiply a second selected digit of the multiplier by the multiplicand to produce a second vector multiplier output.

18. A Montgomery multiplier according to claim 17 further comprising:

an accumulator that is configured to add the first vector multiplier output and the second vector multiplier output to produce a product output.

19. A Montgomery multiplier according to claim 17 the controller is further configured to control the scalar multiplier to multiply the least significant digit of the multiplicand by the first selected digit of the multiplier by and one over a negative of a least significant digit of a modulus to produce the scalar multiplier output.

20. A Montgomery multiplier according to claim 19 wherein the controller is further 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.

21. A Montgomery multiplier according to claim 20 wherein the controller is further 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.

22. A Montgomery multiplication method that modulo multiplies a residue multiplicand by a residue multiplier to obtain a residue product, the Montgomery multiplication method comprising:

multiplying a least significant digit of the multiplicand by a first selected digit of the multiplier in a scalar multiplier to produce a scalar multiplier output;

multiplying the scalar multiplier output by a modulus in a first vector multiplier to produce a first vector multiplier output;

multiplying a second selected digit of the multiplier by the multiplicand in a second vector multiplier to produce a second vector multiplier output; and

adding the first vector multiplier output and the second vector multiplier output to produce a product output.

23. A method according to claim 22 further comprising multiplying the least significant digit of the multiplicand by the first selected digit of the multiplier and by one over a negative of a least significant digit of the modulus in the scalar multiplier to produce the scalar multiplier output.

24. A method according to claim 23 further comprising multiplexing the least significant digit of the multiplicand and one over the negative of the least significant digit of the modulus into the scalar multiplier.

25. A method according to claim 22 further comprising feeding the scalar multiplier output back into the scalar multiplier.

26. A method according to claim 22 further comprising feeding the product output back into the scalar multiplier.

27. A method according to claim 25 further comprising feeding the product output back into the scalar multiplier.

28. A method according to claim 22 further comprising summing the scalar multiplier output and the product output, and providing the sum of the scalar multiplier output and the product output to the scalar multiplier.

29. A method according to claim 28 further comprising multiplexing the first selected digit of the multiplier and the sum of the scalar multiplier output and the product output into the scalar multiplier.

30. A method according to claim 25 further comprising multiplexing the first selected digit of the multiplier and the scalar multiplier output into the scalar multiplier.

31. A method according to claim 26 further comprising multiplexing the first selected digit of the multiplier and the product output into the scalar multiplier.

32. A method according to claim 22 wherein the first selected digit of the multiplier is different from the second selected digit of the multiplier.

33. A method according to claim 32 wherein the second selected digit of the multiplier is a next more significant digit of the multiplier, relative to the first selected digit of the multiplier.

34. A Montgomery multiplication method that modulo multiplies a residue multiplicand by a residue multiplier to obtain a residue product, using a scalar multiplier, a first vector multiplier and a second vector multiplier;

the Montgomery multiplication method comprising;

controlling 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.

35. A method according to claim 34 further comprising controlling the scalar multiplier to perform a scalar multiply using a least significant digit of the multiplier prior to controlling the vector multipliers to perform the vector multiplies using the modulus and the multiplicand.

36. A method according to claim 34 wherein the controlling comprises:

controlling the scalar multiplier to multiply a least significant digit of the multiplicand by a first selected digit of the multiplier to produce a scalar multiplier output;

controlling the first vector multiplier to multiply the scalar multiplier output by the modulus to produce a first vector multiplier output; and

controlling the second vector multiplier to multiply a second selected digit of the multiplier by the multiplicand to produce a second vector multiplier output.

37. A method according to claim 36 further comprising:

adding the first vector multiplier output and the second vector multiplier output to produce a product output.

38. A method according to claim 36 further comprising controlling the scalar multiplier to multiply the least significant digit of the multiplicand by the first selected digit of the multiplier and by one over a negative of a least significant digit of a modulus to produce the scalar multiplier output.

39. A method according to claim 38 further comprising multiplexing the least significant digit of the multiplicand and one over the negative of the least significant digit of the modulus into the scalar multiplier.

40. A method according to claim 39 further comprising multiplexing the first selected digit of the multiplier and the sum of the scalar multiplier output and the product output into the scalar multiplier.