Utilizing SIMD instructions within montgomery multiplication

1. A processing system comprising:

a processor having a set of registers; and

the processor executes a set of SIMD instruction to perform Montgomery multiplication:

montmul( A, B )=rem(( AB−qN )/ R, N ), where q=rem( AB N′, R;

where A and B are integers, q is a quotient, N is a modulus, R is an integer that is coprime to modulus N, and N′ is an integer such that NNT′≡1 (mod R), wherein the integer B and the modulus N are implemented as arrays, and at least one SIMD instruction is used to update a first array T 1 with multiples of B for computing AB and to update a second array T 2 with multiples of N for computing qN, wherein a first register holds elements of the B and N arrays;

a second register holds an element of the first array T 1 and an element of the second array T 2 ; and

a third register is used to hold results of the first array T 1 being updated with a multiple of B and the second array T 2 being updated with multiples of N.

2. A processing system as recited in claim 1 , wherein the processor executes a cryptographic function and the Montgomery multiplication is used to compute exponentiations in the cryptographic function.

3. A processing system as recited in claim 1 , wherein the SIMD instructions comprise a single SIMD instruction that simultaneously performs parts of the multiplications AB and qN.

4. A processing system as recited in claim 1 , wherein a single SIMD instruction is used to update the first array T 1 and the second array T 2 simultaneously.

5. A computer readable storage medium comprising computer-executable SIMD instructions that, when executed, direct a processor to perform Montgomery multiplication, the instructions comprising:

a first SIMD instruction to load elements of array B and N into a first register;

a second SIMD instruction to load elements of arrays T 1 and T 2 into a second register;

a third SIMD instruction to multiple an element in the array B by a first multiple and an element in the array N by a second multiple;

fourth and fifth SIMD instructions to add results of the third SIMD instruction to the array elements loaded by the second SIMD instruction and to any carries saved from a previous iteration;

sixth and seventh SIMD instructions to separate each output of the fifth SIMD instruction into two reduced size results, one that fits into the arrays T 1 and T 2 and another that represents a carry for a next iteration;

an eighth SIMD instruction to update an element of array T 1 and an element of array T 2 in memory; and an instruction to store the result of the final iteration.

6. A computer readable storage medium as recited in claim 5 , wherein the SIMD instructions comprise SSE2 instructions.

7. A method for computing Montgomery multiplication, whereby Montgomery multiplication is performed within a cryptographic function in a computer, the method comprising:

montmul( A, B )=r rem( ( AB−qN )/ R, N ), where q=rem( AB N′, R ):

where A and B are integers, q is a quotient, N is a modulus, R is an integer that is coprime to modulus N, and N′ is an integer such that N N′≡1 (mod R), the method comprising:

iteratively performing, for each digit of integer A from right to left:

with array T 1 being updated by a product of input B times the digit of integer A, determining what multiple of modulus N allows the updated arrays T 1 , T 2 to end with the same digit;

multiplying the input B by the digit of integer A and multiplying the modulus N by the determined multiple; and

updating the arrays T 1 , T 2 storing the result of the final iteration.

8. A method as recited in claim 7 , wherein the performing comprises using SIMD instructions.

9. A method as recited in claim 7 , wherein the multiplying is performed by a single SIMD instruction.

10. A method as recited in claim 7 , further comprising initializing the arrays T 1 , T 2 and the modulus N prior to said performing.

11. One or more computer readable storage media storing computer executable instructions that, when executed by a computer, perform the method as recited in claim 7 .

12. A method as recited in claim 7 , wherein the computing comprises using the Montgomery multiplication to compute exponentiations in a cryptographic function.

13. A method as recited in claim 7 , wherein the computing comprises using SSE2 instructions.