System and method of hiding cryptographic private keys

• US 20050002532A1
• Filed: 07/27/2004
• Published: 01/06/2005
• Est. Priority Date: 01/30/2002
• Status: Active Grant

• Current Assignee: Irdeto B.V. (MultiChoice Group Ltd.)
• Original Assignee: Irdeto Canada Corporation (MultiChoice Group Ltd.)
• Inventors: Chow, Stanley T., Zhou, Yongxin
• Granted Patent: US 7,634,091 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing

Abstract

The invention relates to a system and method of hiding cryptographic private keys. While public/private key encryption systems are considered to be secure, the private keys ultimately must be stored in some location—in fact, in some digital commerce systems the private key is sent to the end user as part of an executable file such as an audio player and audio file. Thus, attackers can obtain access to the private key. The broad concept of the invention is to split the private key up into parts which are obfuscated, but still kept in a form that allows the encrypted data to be decrypted. One technique for obfuscating the private key uses modulo arithmetic.

Claims

1. A method for blind use of private cryptographic keys comprising the steps of:

splitting said private key up into parts; and

obfuscating at least one of said parts of said private key;

whereby said private key is restructured so that it can be used without being revealed to an observer.

2. The method of claim 1, in which said step of splitting comprises the step of:

partitioning said private key by exploiting mathematical properties of said private key.

3. The method as claimed in claim 2, wherein said splitting comprises breaking the private key into a first part and a second part.

4. The method as claimed in claim 2, wherein said splitting comprises breaking the private key into multiple parts.

5. The method as claimed in claim 2, wherein said splitting comprises breaking the private key into an addition chain.

6. The method as claimed in claim 2, wherein said splitting comprises breaking the private key into a base-2 polynomial.

7. The method of claim 1, wherein said step of splitting comprises the steps of:

generating a private and public key pair (d, e); and

generating partial private keys based on said private key d, and containing all of the information in said private key d.

8. The method of claim 7, wherein d=d₁+d₂.

9. The method of claim 8, further comprising the steps of:

sending key information (e, n, d,) to a client;

encrypting a message using said public key e to form a private key encrypted message c;

encrypting said public key encrypted message c using partial private key d₂ to form a partial private key encrypted message c′

; and

sending said public key e, and said encrypted messages c and c′

to the client.

10. The method of claim 9, wherein the private key encrypted message is computed using the formula c=m^e (mod n).

11. The method of claim 10, wherein the partial private key encrypted message is computed using the formula c′

=c^d2 (mod n).

12. The method of claim 11, further comprising the step of decrypting the private key encrypted message using said partial private key d, and the partial private key embedded in said partial private key encrypted message c′

.

13. The method of claim 12, wherein the public key encrypted message is decrypted using the formula m=(c′

·

c^d1) (mod n).

14. The method of claim 1, wherein said steps of splitting and obfuscating comprise the steps of:

generating a series of components containing all of the information in said private key d; and

obfuscating one or more of said series of components.

15. The method of claim 14, wherein the step of creating comprises the step of converting d into an array of integers obtained using the summand representation:

d=d ₁ +d ₂ +. . . +d _t

where d_i are positive integers, for i=1, . . . , t.

16. The method of claim 14, wherein the step of creating comprises the step of converting d into an array of integers using binary representation:

d=dl*(2ⁱ¹)+d2*(2ⁱ²)+. . . +dj*(2^ij)+. . . +dt*(2^it)

where d_j and i_j are integers, for all j=1, 2, . . . , t.

17. The method of claim 14, wherein the step of creating comprises the step of converting d into an array of integers using a directed graph representation of an addition chain for d.

18. The method of claim 14, wherein the step of creating comprises the step of converting d into an array of integers using a combination of two or more of a summand representation, a binary representation and a graph representation.

19. The method of claim 14, wherein the step of obfuscating comprises the step of using an invertible matrix to encode elements of an array of integers representing the series of components.

20. The method of claim 19, wherein the step of encoding comprises the steps of:

selecting a prime number p which is greater than all of the array elements;

setting the base ring of the invertible matrix to be Z/(p), where Z is the integer domain; and

selecting an invertible matrix H over Z/(p).

21. The method of claim 20, further comprising the steps of:

inserting random values into private key bits of the array; and

using the random values for row or column bits in matrix H.

22. The method of claim 14, wherein the step of obfuscating comprises the step of using a group ring to encode elements of an array of integers representing the series of components.

23. The method of claim 22, wherein the step of encoding comprises the steps of:

employing a group ring ZG, where Z is the ring of the integers and G is a group of the array elements; and

selecting a bijection f from ZG to ZG to encode segments of the array elements.

24. The method of claim 22, wherein the step of encoding comprises the steps of:

employing a Galois field group ring GF (2¹) G, where G is a group of the array elements and 1 is the number of bits of |G|; and

selecting a bijection f from GF (2¹) G to GF (2¹) G encode segments of the array elements.

25. The method of claim 14, wherein the step of obfuscating comprises the step of encoding elements of an array of integers representing the series of components using a combination of one or more of linear mappings and group ring mappings, and one or more parameters of mappings.

26. The method of claim 14, wherein the step of creating comprises the steps of:

converting d of size keySize into a binary representation;

d=dl*(2ⁱ¹)+d2*(2ⁱ²)+. . . +dj*(2^ij)+. . . +dt*(2^it)

determining a keyPartitionSize value based upon the bit size of keySize;

creating a keyCoefficients integer array of size keyPartitionSize to store coefficients of the binary representation of d;

creating a keyExponents integer array of size keyPartitionSize to store exponents of the binary representation of d;

choosing keyPartitionSize of values {p₁, p₂, . . . , p_{keyPartitionSize}} such that their sum is keySize;

partitioning a bit-vector OF D into keyPartitionSize consecutive bit-vectors v₁ of bit length p_i with value w_i, where

keyCoefficient [i]=w₁

and keyExponents [i] are the bit position of a low-order bit of v_i in the bit vector of d, where i=0, . . . , keyPartitionSize−

1; and

defining d such that;

$d=\underset{i=1}{\overset{\mathrm{keyPartitionSize}}{\sum <br><br>}}<br><br>\mathrm{keyCoefficients}<br><br>\left[i\right]<br><br>{\mathrm{x2}}^{\mathrm{keyExponents}<br><br>\left[i\right]}$

27. The method of claim 26, further including the step of injecting random values into both arrays, the step of injecting comprising the steps of:

creating a coefficientsAndEntropy array to store true values and entropy for the keyCoefficients integer array, and an exponentsAndEntropy array for storing true values and entropy for keyExponents integer array;

setting values of the coefficientsAndEntropy array based on the keySize;

determining an entropyNumber of random values based on the keyPartitionSize;

randomly inserting these random values into the coefficientsAndEntropy array; and

storing indices of the random values in a coefficientEntropyNumberIndices array.

28. The method of claim 27, further including the step of setting the elements of the exponentsAndEntropy array, comprising the steps of:

using the same number of random values entropyNumber;

having the random values lie between 1 and keySize; and

constructing the exponentsAndEntropy array from the keyExponents array and the random values.

29. The method of claim 28, further comprising the step of encoding the coefficientsAndEntropy array and the exponentsAndEntropy array, comprising the steps of:

selecting a non-Abelian group G with order |G|;

selecting a unit u from ZG;

defining a bijection f(x)=xu from ZG to ZG;

creating a coefficientGRElements two-dimensional array and an exponentGRElements two-dimensional array, wherein each sub-array in these two dimensional arrays is a group ring element;

setting the coefficientGRElements array based on the order of G, with elements assigned from coefficientsAndEntropy;

setting the elementsexponentGRElements array based on the order of G, with elements assigned from exponentsAndEntropy;

applying map f to the coefficientGRElements array to form a finalCoefficientGRElements array;

applying map f to the elementexponentGRElements array to form a finalElementexponentGRElements array; and

flattening the finalCoefficientGRElements array and the finalElementexponentGRElements array to a one dimensional array in a cryptosystem program.

40. The method of claim 2, in which said private key is restructured by obfuscating the parts into which it is partitioned, within a public application.

41. The method of claim 40 wherein said step of obfuscating comprises the steps of obfuscating said private key by:

generating coefficient and exponent arrays which define said private key; and

storing said coefficient and exponent arrays.

42. The method of claim 40 wherein said step of obfuscating comprises the step of expanding said private key into an arithmetic series.

43. The method of claim 40 wherein said step of obfuscating comprises the step of expanding said private key into an exponential series.

44. The method of claim 40 wherein said step of obfuscating comprises the step of reducing said private key into a set of modulo coordinates.

45. The method of claim 40 wherein said step of obfuscating comprises the step of:

expanding said private key into an addition chain.

46. The method of claim 40 wherein said step of obfuscating comprises the step of:

expanding said private key into the sum of a set of numbers.

47. The method of claim 40 wherein said step of obfuscating comprises the step of:

expanding said private key into the product of a set of factors.

48. The method of claim 40 wherein said step of obfuscating comprises the step of:

expanding said private key into a base-2 polynomial series.

49. The method of claim 40 wherein said step of obfuscating comprises the step of:

expanding said private key using number splitting.

50. The method of claim 40 wherein said step of obfuscating comprises the step of:

splitting said private key arithmetically; and

transmitting an arithmetic component of said private key to a decrypting party

51. The method as claimed in claim 1, further comprising the step of embedding another one of said parts of said private key in an executable program.

30. A method of hiding a private key comprising the steps of:

generating a private and public key pair;

splitting said private key into a first part and a second part;

providing to a client;

said public key;

said first part of said private key; and

a program for decrypting messages;

using said public key and said modulus to encrypt a message into a cipher;

obfuscating said second part of said private key; and

providing said cipher and said obfuscated second part of said private key to said client;

whereby said client can decipher said cipher using said first part of said private key and said obfuscated second part of said private key.

31. The method of claim 30, wherein said first part of said private key is embedded into said program for decrypting messages.

32. The method of claim 31, wherein said step of obfuscating said second part of said private key comprises the step of generating a second cipher using said second part of the private key to encrypt said first cipher.

33. The method of claim 31, wherein said executable program is protected using tamper resistant software encoding techniques.

34. The method of claim 32, wherein said private key is an RSA private key.

35. The method of claim 32 wherein said step of obfuscating comprises the step of inserting entropy into said series or set of components.

36. The method of claim 35 wherein said step of obfuscating comprises the step of mixing random or pseudo-random values in with said series or set of components.

37. The method of claim 35 wherein said step of obfuscating comprises the step of inserting entropy into said series or set of components by means of a linear mapping.

38. The method of claim 35 wherein said step of obfuscating comprises the step of inserting entropy into said series or set of components by means of a group ring mapping.

39. The method of claim 32 wherein said step of obfuscating comprises the step of encrypting said series or set of components.

52. A system for secure communication comprising:

a first computer;

a second computer;

a communication network for interconnecting said first computer with said second computer;

said first computer being operable to;

generate a private and public key pair;

split said private key into a first part and a second part;

encrypt a message using said public key;

transmit to said second computer;

said public key;

said first part of said private key;

a program for decrypting messages;

obfuscate said second part of said private key; and

transmit said encrypted message and said obfuscated second part of said private key to said second computer;

whereby said second computer can decipher said cipher using said first part of said private key and said obfuscated second part of said private key.

53. A computer readable memory for storing software code executable to perform the method of hiding a private key comprising the steps of:

splitting said private key up into parts; and

obfuscating at least one of said parts of said private key.