SYSTEM AND METHOD FOR GENERATING AND PROTECTING CRYPTOGRAPHIC KEYS

• US 20150333906A1
• Filed: 02/09/2012
• Published: 11/19/2015
• Est. Priority Date: 02/09/2012
• Status: Active Grant

• Current Assignee: Irdeto B.V. (MultiChoice Group Ltd.)
• Original Assignee: Irdeto Canada Corporation (MultiChoice Group Ltd.)
• Inventors: RAHMAN, SK MD Mizanur, MUIR, James
• Granted Patent: US 9,503,259 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

In the present disclosure, implementations of Diffie-Hellman key agreement are provided that, when embodied in software, resist extraction of cryptographically sensitive parameters during software execution by white-box attackers. Four embodiments are taught that make extraction of sensitive parameters difficult during the generation of the public key and the computation of the shared secret. The embodiments utilize transformed random numbers in the derivation of the public key and shared secret. The traditional attack model for Diffie-Hellman implementations considers only black-box attacks, where attackers analyze only the inputs and outputs of the implementation. In contrast, white-box attacks describe a much more powerful type of attacker who has total visibility into the software implementation as it is being executed.

Claims

1. A method of generating public key for an elliptic curve Diffie-Hellman (ECDH) key exchange protocol without disclosing the private key during computation of the public key, the method comprising the steps of:

generating a random number;

interpreting that random number as a linearly transformed random number; and

generating a public key using the transformed number.

2. The method of claim 1, wherein the linear transformation is {circumflex over (r)}=k₁r+k₂ mod n where k₁ and k₂ are two instance specific, compile time random values and are elements of Z*_n.

3. The method of claim 2 wherein the step of generating a public key computes Ĝ

=k₁<sup>−

1</sup>G, U₁={circumflex over (r)}Ĝ

, and U₂=(k₁−

k₂)Ĝ and

then Q=U₁+U₂.

4. The method of claim 2 wherein k₂=0.

5. The method of claim 4 wherein the step of generating a public key computes Ĝ

=k₁<sup>−

1</sup>G, U₁={circumflex over (r)}Ĝ

, and then Q=U₁+G.

6. The method of claim 1 wherein the step of generating a random number generates two random numbers r₁ and r₂.

7. The method of claim 6 wherein the step of linearly transforming the random number includes the steps of first applying a linear transform to random numbers r₁ and r₂, then applying a second transformation thereto.

8. The method of claim 7 wherein the linear transformation is, r₁=k₁₁r₁+k₁₂ mod n and {circumflex over (r)}₂=k₂₁r₂+k₂₂ mod n, where k₁₁, k₁₂, k₂₁, k₂₂ are instance specific, compile time randomly picked numbers and k₁₁, k₁₂, k₂₁, k₂₂ε

Z_n*.

9. The method of claim 8 wherein the second transformation is t₂ on the transformed-random numbers {circumflex over (r)}₁ and {circumflex over (r)}₂ and is defined as {circumflex over ({circumflex over (r)}₁₁=({circumflex over (r)}₁+{circumflex over (r)}₂)mod 2^N, and {circumflex over ({circumflex over (r)}₂₂=({circumflex over (r)}₁+2{circumflex over (r)}₂)mod 2^N.

10. The method of claim 9 wherein is r₁ chosen for computing the public key.

11. The method of claim 10 where the step of generating a public key computes Ĝ

₁₁=k₁₁<sup>−

1</sup>Ĝ

;

Ĝ

₁₂=k₁₁<sup>−

1</sup>Ĝ

₁₁;

u₁₁=(2{circumflex over ({circumflex over (r)}₁₁−

{circumflex over ({circumflex over (r)}₂₂ mod 2^N)k₁₁ mod n and U₁₂=(k₁₁−

k₁₂)Ĝ

₁₁ and Q=u₁₁Ĝ

₁₂+U₁₂.

12. The method of claim 9 wherein is r₂ chosen for computing the public key.

13. The method of claim 12 where the step of generating a public key computes Ĝ

₂₁=k₂₁<sup>−

1</sup>G, Ĝ

₂₂=k₂₁<sup>−

1</sup>Ĝ

₂₁, u₂₁=({circumflex over ({circumflex over (r)}₂₂−

{circumflex over ({circumflex over (r)}₁₁ mod 2^N)k₂₁ mod n and U₂₂=(k₂₁−

k₂₂)Ĝ

₂₁ and Q=u₂₁*Ĝ

₂₂+U₂₂.

14. The method of claim 7 wherein the linear transformation is, {circumflex over (r)}₁=k₁₁r₁ and {circumflex over (r)}=k₂₁r₂, where k₁₁, and k₂₁ are instance specific, compile time randomly picked numbers, and k₁₁,k₂₁ε

Z_n*. Thus, r₁=k₁₁<sup>−

1</sup>{circumflex over (r)}₁, and r₂=k₂₁<sup>−

1</sup>{circumflex over (r)}₂.

15. The method of claim 14 wherein the second transformation on the transformed-random numbers {circumflex over (r)}₁ and {circumflex over (r)}₂ is defined as {circumflex over ({circumflex over (r)}₁₁=({circumflex over (r)}₁+{circumflex over (r)}₂)mod 2^N, and {circumflex over ({circumflex over (r)}=({circumflex over (r)}₁+2{circumflex over (r)}₂)mod 2^N.

16. The method of claim 15 wherein is r₁ chosen for computing the public key.

17. The method of claim 16 wherein the step of generating a public key computes Ĝ

₁₁=k₁₁<sup>−

1</sup>G;

Ĝ

₁₂=k₁₁<sup>−

1</sup>Ĝ

₁₁;

u₁₁=(2{circumflex over ({circumflex over (r)}₁₁−

{circumflex over ({circumflex over (r)}₂₂ mod 2^N)k₁₁ mod n; and

Q=u₁₁Ĝ

₁₂+G.

18. The method of claim 15 wherein is r₂ chosen for computing the public key.

19. The method of claim 18 wherein the step of generating a public key computes Ĝ

₂₁=k₂₁<sup>−

1</sup>G;

Ĝ

₂₂=k₂₁<sup>−

1</sup>Ĝ

₂₁;

u₂₁=({circumflex over ({circumflex over (r)}₂₂−

{circumflex over ({circumflex over (r)}₁₁ mod 2^N)k₂₁ mod n; and

Q=u₂₁*Ĝ

₂₂+G.

20. The method of claim 1 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random number.

21. The method of claim 3 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random number.

22. The method of claim 21 wherein the step of deriving the shared secret computes points {circumflex over (Q)}_B1=k_1(A)⁻

1Q_B;

{circumflex over (Q)}_B2={circumflex over (r)}_A{circumflex over (Q)}_B1; and

{circumflex over (Q)}_B3=(k_1(A)−

k_2(A)){circumflex over (Q)}_B1 and then P={circumflex over (Q)}_B2+{circumflex over (Q)}_B3 where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random number and party B'"'"'s public key.

23. The method of claim 5 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random number.

24. The method of claim 23 wherein the step of deriving the shared secret computes points {circumflex over (Q)}_B1=k_1(A)⁻

1Q_B; and

{circumflex over (Q)}_B2={circumflex over (r)}_A{circumflex over (Q)}_B1 and then P={circumflex over (Q)}_B2+Q where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random number and party B'"'"'s public key.

25. The method of claim 11 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random numbers.

26. The method of claim 25 wherein the step of deriving the shared secret computes {circumflex over (Q)}_B11=k_11(A)⁻

1Q_B;

{circumflex over (Q)}_B12=(2{circumflex over ({circumflex over (r)}_11(A)−

{circumflex over ({circumflex over (r)}_22(A) mod 2^N){circumflex over (Q)}_B11; and

{circumflex over (Q)}_B13=(k_11(A)−

k_12(A)){circumflex over (Q)}_B11 and then P={circumflex over (Q)}_B12+{circumflex over (Q)}_B13

where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random numbers and party B'"'"'s public key.

27. The method of claim 13 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random numbers.

28. The method of claim 27 wherein the step of deriving the shared secret computes {circumflex over (Q)}_B21=k_21(A)⁻

1Q_B;

{circumflex over (Q)}_B22({circumflex over ({circumflex over (r)}−

_22(A)−

{circumflex over ({circumflex over (r)}_11(A) mod 2^N){circumflex over (Q)}_B21; and

{circumflex over (Q)}_B23=(k_21(A)−

k_22(A)){circumflex over (Q)}_B21 and then P={circumflex over (Q)}_B22+{circumflex over (Q)}_B23

where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random numbers and party B'"'"'s public key.

29. The method of claim 17 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random number.

30. The method of claim 29 wherein the step of deriving the shared secret computes {circumflex over (Q)}_B11=k_11(A)⁻

1Q_B; and

{circumflex over (Q)}_B12=(2{circumflex over ({circumflex over (r)}_11(A)−

{circumflex over ({circumflex over (r)}_22(A)mod 2^N){circumflex over (Q)}_B11; and

then P={circumflex over (Q)}_B12+Q_B where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random number and party B'"'"'s public key.

31. The method of claim 19 further comprising the steps of receiving a public key from another party and deriving a shared secret therefrom using the transformed random number.

32. The method of claim 31 wherein the step of deriving the shared secret computes {circumflex over (Q)}_B21=k_21(A)⁻

1Q_B; and

{circumflex over (Q)}_B22=({circumflex over ({circumflex over (r)}_22(A)−

{circumflex over ({circumflex over (r)}_11(A) mod 2^N){circumflex over (Q)}_B21; and

then P={circumflex over (Q)}_B22+Q_B

where the shared secret is Z=x_P where x_P is the x-coordinate of P, party A uses its transformed random numbers and party B'"'"'s public key.

33. The method of any claim 1, wherein some values are computed off-line.