White-box elliptic curve point multiplication

• US 10,068,070 B2
• Filed: 07/31/2015
• Issued: 09/04/2018
• Est. Priority Date: 05/05/2015
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Hoogerbrugge, Jan, Michiels, Wil, Vullers, Pim
• Primary Examiner(s): Cervetti, David Garcia
• Application Number:
  US14/815,474
• Publication Number:
  US 20160328542A1
• Time in Patent Office: 1,131 Days
• CPC Class Codes: G06F 21/1066 Hiding content
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: G06F 21/50 Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A method of obscuring software code implementing an elliptic curve cryptography (ECC) point multiplication function, including: receiving ECC parameters including a multiplier d having N bits; transforming multiplier d into an array d(i) with −1, 0, and +1 values while maintaining the same value for d; and generating ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations.

Claims

1. A method of obscuring software code that implements an elliptic curve cryptography (ECC) point multiplication function, comprising:

receiving ECC parameters including a multiplier d having N bits;

transforming multiplier d into an array d(i) with −

1, 0, and +1 values while maintaining the same value for d;

generating ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations; and

producing, by a processor, an obscured software code implementing the generated ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations.

2. The method of claim 1, wherein generating ECC point multiplication function operations further comprises:

generating a point addition-subtraction operation based upon d(i), wherein the point addition-subtraction performs a point addition when d(i)=+1 and wherein the point addition-subtraction operation performs a point subtraction when d(i)=−

1; and

generating a point doubling operation.

3. The method of claim 2, wherein the steps of generating a point addition-subtraction operation and generating a point doubling operation are repeated N times producing operations for each of the N values of i.

4. The method of claim 2, wherein a prime of the elliptic curve is used as a modulus in the split variables.

5. The method of claim 2, wherein split variables are determined using a split variable expression using first and second secret splitting multiplicative values and a modulus value.

6. The method of claim 5, wherein the split variables are further determined using a secret splitting additive value.

7. The method of claim 6, wherein the split variable expression is arranged so that none of the splitting secret multiplicative values and the secret splitting additive value are observable to an attacker.

8. The method of claim 1, wherein the method of obscuring software code is carried out by a compiler.

9. A non-transitory machine-readable storage medium encoded with instructions for obscuring software code that implements an elliptic curve cryptography (ECC) point multiplication function, the non-transitory machine-readable storage medium comprising:

instructions for receiving ECC parameters including a multiplier d having N bits;

instructions for transforming multiplier d into an array d(i) with −

1, 0, and +1 values while maintaining the same value for d;

instructions for generating ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations; and

instructions for producing, by a processor, an obscured software code implementing the generated ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations.

10. The non-transitory machine-readable storage medium of claim 9, wherein instructions for generating ECC point multiplication function operations further comprises:

instructions for generating a point addition-subtraction operation based upon d(i), wherein the point addition-subtraction performs a point addition when d(i)=+1 and wherein the point addition-subtraction operation performs a point subtraction when d(i)=−

1; and

instructions for generating a point doubling operation.

11. The non-transitory machine-readable storage medium of claim 10, wherein the instructions for generating a point addition-subtraction operation and instructions for generating a point doubling operation are repeated N times producing operations for each of the N values of i.

12. The non-transitory machine-readable storage medium of claim 10, wherein a prime of the elliptic curve is used as a modulus in the split variables.

13. The non-transitory machine-readable storage medium of claim 9, wherein a split variables are determined using a split variable expression using first and second secret splitting multiplicative values and a modulus value.

14. The non-transitory machine-readable storage medium of claim 13, wherein the split variables are further determined using a secret splitting additive value.

15. The non-transitory machine-readable storage medium of claim 14, wherein the split variable expression is arranged so that none of the splitting secret multiplicative values and the secret splitting additive value are observable to an attacker.

16. The non-transitory machine-readable storage medium of claim 9, wherein instructions for obscuring software code implementing an elliptic curve cryptography (ECC) point multiplication function are part of a compiler.

17. A method of controlling a server that provides an application that implements a white-box implementation of a cryptographic function that includes obscured software code implementing an elliptic curve cryptography (ECC) point multiplication function, comprising:

receiving a request from a user for the application that implements a white-box implementation of a cryptographic function that includes obscured software code implementing an elliptic curve cryptography (ECC) point multiplication function; and

providing the user the application that implements a white-box implementation of a cryptographic function that includes obscured software code implementing an elliptic curve cryptography (ECC) point multiplication function, wherein the application was created by;

receiving ECC parameters including a multiplier d having N bits;

transforming multiplier d into an array d(i) with −

1, 0, and +1 values while maintaining the same value for d;

generating ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations; and

producing, by a processor, the obscured software code implementing the generated ECC point multiplication function operations using the transformed multiplier array d(i) and N, wherein the generated ECC point multiplication function operations are split variable operations.

18. The method of claim 17, wherein generating ECC point multiplication function operations further comprises:

generating a point addition-subtraction operation based upon d(i), wherein the point addition-subtraction performs a point addition when d(i)=+1 and wherein the point addition-subtraction operation performs a point subtraction when d(i)=−

1; and

generating a point doubling operation.

19. The method of claim 18, wherein the steps of generating a point addition-subtraction operation and generating a point doubling operation are repeated N times producing operations for each of the N values of i.

20. The method of claim 18, wherein a prime of the elliptic curve is used as the modulus in a split variables.