Reduction calculations in elliptic curve cryptography

1. A method of performing a reduction operation in a cryptographic calculation in a digital computer, the method comprising:

selecting a modulus having a first section with a plurality of “1” Most Significant Word states and a second section which further comprises: a plurality of “1” or “0” states whereby a number formed of the two sections is a modulus; and

operating a reduction operation on the modulus comprising:

multiplying a first variable n 0 ′ by a second variable r 3 to produce a first result;

adding the first result to a third variable r 1 and B multiplied by a fourth variable r 2 to produce a first sum, wherein the first sum corresponds to a first equation: n 0 ′r 3 +Br 2 +r 1 ;

dividing the first sum into an upper half and a lower half;

multiplying the upper half by the first variable n 0 ′ to produce a second result;

adding the second result to the lower half and a fifth variable r 0 to produce a second sum, thereby permitting use of the second sum as the modulus; and

using the modulus in the cryptographic calculation.

2. The method of claim 1 , further comprising:

effecting a plurality of multiplication operations.

3. The method of claim 2 , further comprising:

effecting a plurality of multiplication operations followed by effecting the reduction operation.

4. The method claim 3 , further comprising:

repeating the effecting step of claim 3 .

5. The method of claim 1 , further comprising:

using a multiple of the modulus.

6. The method of claim 1 , further comprising:

adding an overflow from a last multiplication to a part of a selected number.

7. The method of claim 6 , further comprising:

adding the first variable n 0 ′ to the overflow.

8. The method of claim 1 , wherein a carry c between two adjacent multiplications is effected as an addend in a subsequent multiplication.

9. The method of claim 1 , further comprising:

monitoring a number of leading “1”s to determine if the number is less than (k−2).

10. The method of claim 9 , further comprising:

initiating a next calculation.

11. The method of claim 1 , the method further comprising:

operating 192-bit Elliptic Curve Crytography (ECC) and a word size of 64-bit,

the modulus comprises a first section of 138 bits and a second section of 54 bits.

12. The method of claim 1 , the method further comprising:

operating 128-bit Elliptic Curve Crytography (ECC) and a word size of 64-bit,

the modulus comprises a first section of 74 bits and a second section of 54 bits.

13. The method of claim 1 , the method further comprising:

operating 256-bit Elliptic Curve Crytography (ECC) and a word size of 64-bit,

the modulus comprises a first section of 202 bits and a second section of 54 bits.

14. A computer program product directly loadable into an internal memory of the digital computer, comprising:

software code portions for performing the method of claim 1 on the digital computer.

15. A computer program directly loadable into an internal memory of the digital computer, comprising:

software code portions for performing the method of claim 1 on the digital computer.

16. An apparatus that performs a reduction operation in a cryptographic calculation on a digital computer, the apparatus comprising:

a plurality of input registers that store a plurality of input operands;

a plurality of output registers that store a plurality of outputs; and

a multiplier that produces said outputs using a function that operates on variables from both said input registers and said output registers; wherein said multiplier selects a modulus having a first section with a plurality of “1” states and a second section having a plurality of “1” or “0” states whereby a number formed of the two sections is a modulus and performs a reduction operation on the modulus, the reduction operation comprising:

multiplying a first variable n 0 ′ by a second variable r 3 to produce a first result;

adding the first result to a third variable r 1 and B multiplied by a fourth variable r 2 to produce a first sum, wherein the first sum corresponds to a first equation: n 0 ′r 3 +Br 2 +r 1 ;

dividing the first sum into an upper half and a lower half;

multiplying the upper half by the first variable n 0 ′ to produce a second result; adding the second result to the lower half and a fifth variable r 0 to produce a second sum, thereby permitting use of the second sum as the modulus; and

using the modulus in the cryptographic calculation.

17. The apparatus of claim 16 , further comprising:

means to effect a plurality of multiplication operations.

18. The apparatus of claim 17 , further comprising:

means to effect a plurality of multiplication operations followed by the reduction operation.

19. The apparatus of claim 18 , further comprising:

means to repeat the plurality of multiplication operations and the reduction operation.

20. The apparatus of claim 16 , further comprising:

means to use a multiple of the modulus.

21. The apparatus of claim 16 , further comprising:

means to add an overflow from a last multiplication to part of a selected number.

22. The apparatus of claim 21 , further comprising:

means to add the first variable n 0 ′ to the overflow.

23. The apparatus of claim 16 , further comprising:

means to effect a carry c between two adjacent multiplications as an addend in a subsequent multiplication.

24. The apparatus of claim 16 , further comprising:

means to monitor a number of leading “1”s to determine if the number is less than (k−2).

25. The apparatus of claim 24 , further comprising:

means to initiate a next calculation.

26. The apparatus of claim 16 ,

wherein the modulus comprises a first section of 74 bits and a second section of 54 bits.

27. The apparatus of claim 16 ,

wherein the modulus comprises a first section of 74 bits and a second section of 54 bits.

28. The apparatus of claim 16 , wherein the modulus comprises a first section of 202 bits and a second section of 54 bits.