Computing a secure elliptic curve scalar multiplication using an unsecured and secure environment

1. A system for securely performing elliptic curve scalar multiplication, the system comprising an unsecure processor, a memory device and an secure processor separate from the unsecure processor,

the secure processor including secure memory, the secure processor configured to:

split a secure scalar K into m 2 random values k i , where i is an integer index;

randomly select m 1 -m 2 values k i , for the indices m 2 <i≤m 1 ;

select m l mask values δ i ;

compute m 1 residues c i based upon random residues a i , δ π(i) −1 , and k π(i) , wherein π(i) is a random permutation;

compute m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied;

and

the unsecure processor in communication with the memory device, wherein the unsecure processor receives the computationally intensive computations for the elliptic curve scalar multiplication to boost the system's computation performance, the unsecure processor being configured to:

receive, from the secure processor, the m 1 residues c i and elliptic curve points G i ;

compute m i elliptic curve points P i based upon the m 1 residues c i and elliptic curve points G i ; and

send the m 1 elliptic curve points P i to the secure processor, wherein the secure processor, receives the m 1 , elliptic curve points and computes the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and by removing the mask values δ i from the portion of the received elliptic curve points.

2. The system of claim 1 , wherein the secure processor is further configured to:

randomly select m 1 residues a i ; and

store the m 1 residues a i in the secure memory.

3. The system of claim 1 , wherein the m 1 mask values δ i are selected from set of pre-computed random values stored in the secure memory.

4. The system of claim 1 , wherein computing m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied is computed as:

G i =( a i −1 mod n )· G,

for 1≤i≤m 1 , where G is elliptic point of the elliptic curve to be multiplied and n is the multiplicative order of the elliptic point G.

5. The system of claim 1 , wherein splitting a secure scalar K into m 2 random values k i includes selecting m 2 −1 random values k i , for 1≤i<m 2 −1, and computing k m 2 =k−(Σ i=1 m 2 −1 k i )mod n, where n is the multiplicative order of the elliptic point.

6. The system of claim 1 , wherein computing m 1 residues c i is computed as:

c i =a i ·δ π(i) −1 ·k π(i) mod n,

where n is the multiplicative order of the elliptic point.

7. The system of claim 1 , wherein computing m 1 elliptic curve points P i is computed as:

P i =c i ·G i .

8. The system of claim 1 , wherein computing the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and removing the mask values δ i from the portion of the received elliptic curve points is computed as:

k·G=Σ i=1 m 2 δ i ·P π −1 (i) ,

where G is elliptic point of the elliptic curve to be multiplied.

9. A method for securely performing elliptic curve scalar multiplication, using a secure processor separate from a unsecure processor, comprising:

by the secure processor:

splitting a secure scalar K into m 2 random values k i , where i is an integer index;

randomly selecting m 1 -m 2 values k i , for the indices m 2 <i≤m 1 ;

selecting m 1 mask values δ i ;

computing m 1 residues c i based upon random residues a i , δ π(i) −1 , and k π(i) , wherein π(i) is a random permutation;

computing m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied;

and

by the unsecure processor;

receiving, from the secure processor, the m 1 residues c i and elliptic curve points G i ;

computing m 1 elliptic curve points P i based upon the m 1 residues c i and elliptic curve points G i ; and

sending the m 1 elliptic curve points P i to the secure processor, wherein the unsecure processor performs the computationally intensive computations for the elliptic curve scalar multiplication to boost the system's computation performance and wherein the secure processor, receives the m 1 elliptic curve points and computes the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and by removing the mask values δ i from the portion of the received elliptic curve points.

10. The system of claim 1 , wherein the secure processor further:

randomly selects m 1 residues a i ; and

stores the m 1 residues a i in a secure memory.

11. The method of claim 9 , wherein the m 1 mask values δ i are selected from set of pre-computed random values stored in a secure memory.

12. The method of claim 9 , wherein computing m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied is computed as:

G i =( a i −1 mod n )· G,

for 1≤i≤m 1 , where G is elliptic point of the elliptic curve to be multiplied and n is the multiplicative order of the elliptic point G.

13. The method of claim 9 , wherein splitting a secure scalar K into m 2 random values k i includes selecting m 2 −1 random values k i , for 1≤i<m 2 −1, and computing k m 2 =k−(Σ i=1 m 2 −1 k i )mod n, where n is the multiplicative order of the elliptic point.

14. The method of claim 9 , wherein computing m 1 residues c I is computed as:

c i =a i ·δ π(i) −1 ·k π(i) mod n,

where n is the multiplicative order of the elliptic point.

15. The method of claim 9 , wherein computing m 1 elliptic curve points P i is computed as:

P i =c i ·G i .

16. The method of claim 9 , wherein computing the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and removing the mask values δ i from the portion of the received elliptic curve points is computed as:

k·G=Σ i=1 m 2 δ i ·P π −1 (i) ,

where G is elliptic point of the elliptic curve to be multiplied.

17. A non-transitory machine-readable storage medium encoded with instructions for securely performing elliptic curve scalar multiplication using, an unsecure processor and an secure processor separate from the unsecure processor comprising:

instructions for execution by the secure processor including:

instructions for splitting a secure scalar K into m 2 random values k i , where i is an integer index;

instructions for randomly selecting m 1 - m 2 values k i , for the indices m 2 <i≤m 1 ;

instructions for selecting m 1 mask values δ i ;

instructions for computing m 1 residues c i based upon random residues a i , δ π(i) −1 , and k π(i) , wherein π(i), wherein π(i) is a random permutation;

instructions for computing m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied;

instructions for execution by the unsecure processor for performing the computationally intensive computations for the elliptic curve scalar multiplication to boost the system's computation performance by including:

instructions for receiving, from the secure processor, the m 1 residues c i and elliptic curve points G i ;

instructions for computing m 1 elliptic curve points P i based upon the m 1 residues c i and elliptic curve points G i ; and

instructions for sending the m 1 elliptic curve points P i to the secure processor wherein the instructions for the secure processor enable the secure processor to receive the m 1 , elliptic curve points and compute the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and by removing the mask values δ i from the portion of the received elliptic curve points.

18. The non-transitory machine-readable storage medium of claim 17 , wherein the instructions for execution by the secure processor further include:

instructions for randomly selecting m 1 residues a i ; and

instructions for storing the m 1 residues a i in a secure memory.

19. The non-transitory machine-readable storage medium of claim 17 , wherein the m 1 mask values δ i are selected from set of pre-computed random values stored in a secure memory.

20. The non-transitory machine-readable storage medium of claim 17 , wherein computing m 1 elliptic curve points G i based upon random residues a i and an elliptic point to be multiplied is computed as:

G i =( a i −1 mod n )· G,

for 1≤i≤m 1 , where G is elliptic point of the elliptic curve to be multiplied and n is the multiplicative order of the elliptic point G.

21. The non-transitory machine-readable storage medium of claim 17 , wherein splitting a secure scalar K into m 2 random values k i includes selecting m 2 −1 random values k i , for 1≤i<m 2 −1, and computing k m 2 =k−(Σ i=1 m 2 −1 k i )mod n, where n is the multiplicative order of the elliptic point.

22. The non-transitory machine-readable storage medium of claim 17 , wherein computing m 1 residues c I is computed as:

c i =a i ·δ π(i) −1 ·k π(i) mod n,

where n is the multiplicative order of the elliptic point.

23. The non-transitory machine-readable storage medium of claim 17 , wherein computing m 1 elliptic curve points P i is computed as:

P i =c i ·G i .

24. The non-transitory machine-readable storage medium of claim 17 , wherein computing the elliptic curve scalar multiplication by combining a portion of the received elliptic curve points and removing the mask values δ i from the portion of the received elliptic curve points is computed as:

k·G=Σ i=1 m 2 δ i ·P π −1 (i) ,

where G is elliptic point of the elliptic curve to be multiplied.