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

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 m2 random values ki, where i is an integer index;
• randomly selecting m1 -m2 values ki, for the indices m2<i≤m1;
• selecting m1 mask values δi;
• computing m1 residues ci based upon random residues ai, δπ(i)−1, and kπ(i), wherein π(i) is a random permutation;
• computing m1 elliptic curve points Gi based upon random residues ai and an elliptic point to be multiplied;
• and
• by the unsecure processor;
• receiving, from the secure processor, the m1 residues ci and elliptic curve points Gi;
• computing m1elliptic curve points Pi based upon the m1 residues ci and elliptic curve points Gi;
• and
• sending the m1elliptic curve points Pi 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 m1 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.

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 m2 random values ki, where i is an integer index;
• instructions for randomly selecting m1 - m2 values ki, for the indices m2<i≤m1;
• instructions for selecting m1 mask values δi;
• instructions for computing m1 residues ci based upon random residues ai, δπ(i)−1, and kπ(i), wherein π(i), wherein π(i) is a random permutation;
• instructions for computing m1 elliptic curve points Gi based upon random residues ai 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 m1 residues ci and elliptic curve points Gi;
• instructions for computing m1elliptic curve points Pi based upon the m1 residues ci and elliptic curve points Gi;
• and
• instructions for sending the m1elliptic curve points Pi to the secure processor wherein the instructions for the secure processor enable the secure processor to receive the m1, 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.