System and method of hiding cryptographic private keys

1. A computer implemented method of hiding a private key comprising the steps of:

generating a private and public key pair at a single server;

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

providing to a single client:

said public key;

said first part of said private key; and

a program configured to decrypt messages;

using said public key and a 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; and

deciphering said cipher at the client using said first part of said private key and said obfuscated second part of said private key.

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

3. The method of claim 2 , 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.

4. The method of claim 3 , wherein said private key is an RSA private key.

5. The method of claim 3 wherein said step of obfuscating comprises the step of generating a series of components which describe said second part and further comprises the steps of inserting entropy into said series or set of components.

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

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

8. The method of claim 5 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.

9. The method of claim 3 wherein said step of obfuscating comprises the step of generating a series of components which describe said second part and further comprises the steps of encrypting said series or set of components.

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

11. A computer implemented method that transforms a software application from a first form to a more secure form allowing the blind use of private cryptographic keys wherein said first form includes a single private key, said method comprising the steps of:

splitting said private key up into parts; and

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

producing said more secure form in which said private key is restructured so that it can be used without being revealed to an observer;

said step of splitting comprises the step of: partitioning said private key by exploiting mathematical properties of said private key;

said private key is restructured by obfuscating the parts into which it is partitioned, within a public application.

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

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

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

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

16. The method of claim 11 , 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.

17. The method of claim 16 , wherein d=d 1 +d 2 .

18. The method of claim 17 , 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 2 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.

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

20. The method of claim 19 , wherein the partial private key encrypted message is computed using the formula c′=c d2 (mod n).

21. The method of claim 20 , 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′.

22. The method of claim 21 , wherein the public key encrypted message is decrypted using the formula m=(c′·c d1 )(mod n).

23. The method of claim 11 , 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.

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

d=d 1 +d 2 + . . . +d t

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

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

d=dl *(2 i1 )+ d 2*(2 i2 )+ . . . + dj *(2 ij )+ . . . + dt *(2 it )

where d j and ij are integers, for all j=1, 2, . . . , t.

26. The method of claim 23 , 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 ford.

27. The method of claim 23 , 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.

28. The method of claim 23 , 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.

29. The method of claim 28 , 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).

30. The method of claim 29 , 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.

31. The method of claim 23 , 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.

32. The method of claim 31 , 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.

33. The method of claim 31 , wherein the step of encoding comprises the steps of:

employing a Galois field group ring GF (2 1 ) 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 1 ) G to GF (2 1 ) G encode segments of the array elements.

34. The method of claim 23 , 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.

35. The method of claim 23 , wherein the step of creating comprises the steps of:

converting d of size keySize into a binary representation:

d=dl *(2 i 1)+ d 2*(2 i2 )+ . . . + 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 1 , p 2 , . . . , p keyPartitionSize }such that their sum is keySize;

partitioning a bit-vector OF D into keyPartitionSize consecutive bit-vectors v 1 of bit length p i with value w i , where

keyCoefficient[i]=w 1

and keyExponents [i] are the bit position of a low-order bit of vi in the bit vector of d,

where i=0, . . . , keyPartitionSize−1; and

defining d such that:

d

=

∑

i

=

1

keyPartitionSize

⁢

keyCoefficients

⁡

[

i

]

⁢

x2

keyExponents

⁡

[

i

]

.

36. The method of claim 35 , 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.

37. The method of claim 36 , 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.

38. The method of claim 37 , 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.

39. The method of claim 11 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.

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

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

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

43. The method of claim 11 wherein said step of obfuscating comprises the step of:

expanding said private key into an addition chain.

44. The method of claim 11 wherein said step of obfuscating comprises the step of:

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

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

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

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

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

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

expanding said private key using number splitting.

48. The method of claim 11 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.

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

50. 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 configured 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; and

a program configured to decrypt 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 encrypted message using said first part of said private key and said obfuscated second part of said private key.

51. A computer readable storage memory storing software code that when executed by a processor transforms a software application from a first form to a more secure form by hiding a private key, said code when executed causes the processor to perform the steps of:

generating a private and public key pair at a single server;

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

providing to a single client:

said public key;

said first part of said private key; and

a program configured to decrypt messages;

using said public key and a 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; and

deciphering said cipher at the client using said first part of said private key and said obfuscated second part of said private key.