Broadcast key distribution apparatus and method using Chinese Remainder

• US 5,663,896 A
• Filed: 09/22/1994
• Issued: 09/02/1997
• Est. Priority Date: 09/22/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Aucsmith, David W.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): PEESO, THOMAS R
• Application Number:
  US08/310,845
• Time in Patent Office: 1,076 Days
• Field of Search: 364/709.05, 364/514 R, 380/30, 380/4, 380/28, 380/37, 380/44, 178/89, 178/79
• US Class Current: 713/163
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

A communication system utilizing low bandwidth requirements for transmitting an encoded value formulated using the Chinese Remainder procedure to receivers having a private key. The system offers the advantages of low bandwidth transmission of single standard key systems but the security of private key systems. Each receiver contains a private key and a prime number associated with the receiver. The transmitter system utilizes the Chinese Remainder procedure and the private key and the prime number associated with each receiver to generate a unique value X that solves a particular set of relationships for a set of authorized receivers of the communication network and no others. The value X is broadcast to all receivers and each receiver utilizes its prime number and its private decryption key to arrive at a master key. Unauthorized receivers will not obtain a valid master key because their prime numbers are outside of the set relationships that X solves. By broadcasting only X, the system avoids the requirement of broadcasting a separate encoded version of the master key to each authorized receiver. The system may be used to also broadcast new private keys to the receivers or a subset of receivers within the network.

Claims

1. An apparatus for performing network communication, said apparatus comprising:

a plurality of receiver units individually having a prime value and a private key;

transmitter processing logic selecting a subset of said plurality of receiver units and individually encrypting a master key, K, with each private key of said subset of receiver units;

said transmitter processing logic further solving a set of relationships that contain values associated with said subset of receiver units wherein a single value, X, solves each relationship, said set of relationships including an individual prime value, an individual encrypted master key, and said single value X for each receiver unit of said subset; and

broadcast processing logic coupled to communicate with said transmitter processing logic for transmitting said single value, X, to each receiver unit of said plurality of receiver units.

2. An apparatus as described in claim 1 wherein said transmitter processing logic utilizes the Chinese Remainder procedure to solve said set of relationships to determine said single value X.

3. An apparatus as described in claim 1 wherein said set of relationships associated with said subset comprise:

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)) (i=1 to n),

wherein n is the number of receiver units within said subset, p(i) is said prime value for a receiver unit, i, of said subset and K'"'"'(i) is said encrypted master key of said receiver unit, i, of said subset.

4. An apparatus as described in claim 1 wherein an individual receiver unit of said plurality of receiver units comprises:

receiver processing logic for receiving said single value, X, from said broadcast processing logic;

computation processing logic for computing an encrypted master key associated with said individual receiver unit, said encrypted master key computed based on a prime value and a private key associated with said individual receiver unit; and

key decryption processing logic for decrypting said encrypted master key of said individual receiver unit based on said private key of said individual receiver unit to obtain said master key, K.

5. An apparatus as described in claim 4 wherein said computation processing logic computes said encrypted master key according to:

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)),

wherein K'"'"'(i) is said encrypted master key for said individual receiver unit, i, and p(i) is said prime value for said individual receiver unit, i.

6. An apparatus as described in claim 5 wherein said transmitter processing logic utilizes the Chinese Remainder procedure to solve said set of relationships to determine said single value X.

7. An apparatus as described in claim 4:

wherein said transmitter processing logic comprises encryption processing logic for encrypting a message using said master key, K, to obtain a cipher message and said broadcast processing logic is also for broadcasting said cipher message; and

wherein said individual receiver unit of said plurality of receiver units comprises message decryption processing logic for decrypting said cipher message with said master key to obtain said message.

8. An apparatus for performing network communication, said apparatus comprising:

a plurality of receivers individually having a prime value and a private key associated therewith;

transmitter processing logic selecting a subset of receivers of said plurality of receivers and for encrypting a master key, K, individually with each private key of said subset of receivers to produce an encrypted master key, K'"'"'(i), for each receiver of said subset of receivers;

wherein said transmitter processing logic is also for solving a set of relationships, in a form of;

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)) (i=1 to n),

that are associated with said subset of receivers wherein a single value, X, solves each relationship and wherein n is the number of receivers within said subset, p(i) is said prime value for a receiver, i, and K'"'"'(i) is said encrypted master key of said receiver, i, said transmitter processing logic utilizing the Chinese Remainder procedure to solve for said value X; and

broadcast processing logic coupled to communicate with said transmitter processing logic for transmitting said value, X, to each receiver of said plurality of receivers.

9. An apparatus as described in claim 8 wherein an individual receiver unit of said plurality of receivers comprises:

receiver processing logic for receiving said value, X, from said broadcast processing logic;

computation processing logic for computing an encrypted master key associated with said individual receiver, said encrypted master key computed based on a prime value and a private key associated with said individual receiver; and

key decryption processing logic for decrypting said encrypted master key of said individual receiver based on said private key of said individual receiver to obtain said master key.

10. An apparatus as described in claim 9 wherein said computation processing logic computes said encrypted master key of said individual receiver according to:

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)),

wherein K'"'"'(i) is said encrypted master key of said individual receiver, i, and p(i) is said prime value of said individual receiver, i.

11. An apparatus as described in claim 9

wherein said transmitter processing logic comprises encryption processing logic for encrypting a message using said master key to obtain a cipher message and said broadcast processing logic is also for broadcasting said cipher message;

and

wherein said individual receiver of said plurality of receivers comprises message decryption processing logic for decrypting said cipher message with said master key to obtain said message.

12. A computer implemented apparatus for updating private keys associated with receivers within a communication network, said apparatus comprising:

a plurality of receiver units individually having a prime value and a current private key;

key generation logic for generating a new private key for each receiver unit of said plurality of receiver units;

transmitter encryption logic for encrypting each new private key of each receiver unit with said current private key of each receiver unit to generate a set of encrypted new private keys for said plurality of receiver units;

transmitter computation logic for solving a set of relationships, each relationship involving a prime value and an encrypted new private key, for each individual receiver unit within said plurality of receiver units, wherein a single value, X, solves each relationship; and

broadcast processing logic coupled to communicate with said transmitter computation logic for transmitting said single value, X, to each receiver unit of said plurality of receiver units.

13. A computer implemented apparatus as described in claim 12 wherein said transmitter computation logic utilizes the Chinese Remainder procedure to solve said set of relationships to determine said single value X.

14. A computer implemented apparatus as described in claim 13 wherein said set of relationships comprise relationships of a form:

space="preserve" listing-type="equation">k'"'"'(i)=X mod (p(i)) (i=1 to n),

wherein n is the number of receiver units within said network, p(i) is said prime value for an individual receiver unit, i, and wherein k'"'"'(i) is an encrypted new private key of said individual receiver unit, i.

15. A computer implemented apparatus as described in claim 12 wherein an individual receiver unit of said plurality of receiver units comprises:

receiver processing logic for receiving said single value, X, from said broadcast processing logic;

receiver computation logic for computing an encrypted new private key associated with said individual receiver unit, said encrypted new private key computed based on a prime value and a current private key associated with said individual receiver unit; and

key decryption processing logic for decrypting said encrypted new private key of said individual receiver unit based on said current private key of said individual receiver unit to obtain said new private key of said individual receiver unit.

16. A computer implemented apparatus as described in claim 15 wherein said individual receiver unit of said plurality of receiver units comprises processing for replacing said current private key with said new private key.

17. A computer implemented apparatus as described in claim 15 wherein said receiver computation logic computes said individual encrypted new private key for said individual receiver unit according to:

space="preserve" listing-type="equation">k'"'"'(i)=X mod (p(i)),

wherein k'"'"'(i) is said encrypted new private key of said individual receiver, and p(i) is said prime value of said individual receiver.

18. A computer implemented method for network communication comprising the computer implemented steps of:

providing a transmitter and a plurality of receivers, wherein each receiver has a corresponding prime value and private key;

determining a subset of receivers of said plurality of receivers;

generating a master key, K, and storing said master key in memory;

encrypting said master key, K, with each private key of said receivers of said subset to produce a set of encrypted master keys;

generating a single value, X, by solving a set of relationships, wherein each relationship includes X, an encrypted master key, and a prime value for individual receivers of said subset; and

broadcasting said single value, X, from said transmitter to said plurality of receivers.

19. A computer implemented method as described in claim 18 wherein said set of relationships of said step of generating a single value, X, comprise:

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)) (i=1 to n)

wherein K'"'"'(i) is an encrypted master key for receiver, i, p(i) is a prime value for receiver, i, and n is the number of receivers within said subset of receivers.

20. A computer implemented method as described in claim 19 wherein said step of generating a single value, X, comprises the step of solving said set of relationships using the Chinese Remainder procedure.

21. A computer implemented method as described in claim 18 further comprising the step of:

receiving, at a given receiver within said subset, said broadcast value of X;

generating, at said given receiver, an encrypted master key value associated with said given receiver; and

decrypting said encrypted master key value, at said given receiver, by using a private key associated with said given receiver to obtain said master key.

22. A computer implemented method as described in claim 21 wherein said step of generating an encrypted master key value is performed by said step of generating said encrypted master key value utilizing a relationship:

space="preserve" listing-type="equation">K'"'"'(i)=X mod (p(i)),

wherein K'"'"'(i) is said encrypted master key for said given receiver, and p(i) is a prime value for said given receiver.

23. A computer implemented method as described in claim 21 further comprising the steps of:

encrypting a message, at said transmitter, by using said master key, K, to obtain a cipher message;

broadcasting said cipher message to all receivers;

decrypting said cipher message, at said receivers within said subset, with said master key.

24. A Computer implemented method as described in claim 18 further comprising the step of:

receiving, at a given receiver within said subset, said broadcast value of X;

generating, at said given receiver, an encrypted new private key associated with said given receiver; and

decrypting said encrypted new private key value, at said given receiver, by using a current private key associated with said given receiver to obtain said new private key for said given receiver.

25. A computer implemented method as described in claim 24 wherein said step of generating an encrypted new private key is performed by said step of generating said encrypted new private key utilizing a relationship:

space="preserve" listing-type="equation">k'"'"'(i)=X mod (p(i)),

wherein k'"'"'(i) is said encrypted new private key for said given receiver, i, and p(i) is a prime value for said given receiver, i.

26. A computer implemented method as described in claim 24 further comprising the step of replacing, within said given receiver, said current private key with said new private key.

27. A computer implemented method for broadcasting new private keys to receivers within a communication network, said method comprising the computer implemented steps of:

providing a transmitter and a plurality of receivers, wherein each receiver has a corresponding prime value and current private key;

generating a new private key, kn(i), for each receiver of said network;

encrypting each new private key, kn(i), with each current private key of each of said plurality of receivers to produce a set of encrypted new private keys;

generating a single value, X, by solving a set of relationships, wherein each relationship includes X, an encrypted new private key, and a prime value for individual receivers of network; and

broadcasting said single value, X, from said transmitter to said plurality of receivers of said network.

28. A computer implemented method as described in claim 27 wherein said set of relationships of said step of generating a single value, X, comprise:

space="preserve" listing-type="equation">k'"'"'(i)=X mod (p(i)) (i=1 to n),

wherein k'"'"'(i) is an encrypted new private key for receiver, i, p(i) is a prime value for receiver, i, and n is the number of receivers within said plurality of receivers.

29. A computer implemented method as described in claim 27 wherein said step of generating a single value, X, comprises the step of solving said set of relationships using the Chinese Remainder procedure.

30. Within a network in which receivers individually contain a prime value, p(i), and a current private key, ko(i), a computer implemented method of broadcasting new private keys to receivers of said network, said method comprising the steps of:

generating master key, K;

generating a set of new private keys, kn(i), for a subset of said receivers;

individually encrypting each new private key of said set of new private keys with each current private key of said receivers of said subset to generate a set of encrypted new private keys, k'"'"'(i);

encrypting said master key, K, with each of said new private keys, kn(i), to generate a set of encrypted master keys, K'"'"'(i) for said subset;

generating a single value, X, from a set of relationships in the form of

space="preserve" listing-type="equation">k'"'"'(i)=X mod (p(i)),

for each receiver, i, of said subset;

generating a single value Y, from a set of relationships in the form of K'"'"'(i)=X mod (p(i)), for each receiver, i, of said subset;

encrypting Y using K to obtain Y'"'"'; and

broadcasting X, Y and Y'"'"' to all receivers within said network.

31. A computer implemented method as described in claim 30 wherein said steps of generating a single value, X, and generating a single value, Y, utilize the Chinese Remainder procedure.

32. A computer implemented method as described in claim 31 further comprising the steps of:

receiving, at a given receiver, i, within said subset, said broadcast value of X, Y and Y'"'"';

generating, at said given receiver, an encrypted new private key, k'"'"'(i), associated with said given receiver by k'"'"'(i)=X mod (p(i)); and

decrypting said encrypted new private key value, at said given receiver, by using a current private key, ko(i), associated with said given receiver to obtain said new private key for said given receiver, kn(i).

33. A computer implemented method as described in claim 32 further comprising the steps of:

generating, at said given receiver, an encrypted master key, K'"'"', based on K'"'"'=Y mod (p(i));

decrypting K'"'"' by said new private key, kn(i), for said given receiver to obtain said master key, K; and

decrypting Y'"'"' with K to obtain a value Y?.

34. A computer implemented method as described in claim 33 further comprising the step of replacing, within said given receiver, said current private key, ko(i), with said new private key, kn(i), provided Y is equal to Y? for said given receiver.

35. In a communication network having a transmitter and a plurality of receivers, each receiver having a private key, k(i), and a prime value, p(i), associated therewith, a method of broadcasting information therein, said method comprising the computer implemented steps of:

determining an arbitrary subset of receivers within said network;

generating a master key, K;

generating a set of encrypted master keys, K'"'"'(i), by encrypting said master key with each private key of said subset of receivers;

generating a set of relationships in the form of K'"'"'(i)=X mod (p(i)) for each receiver, i, of said subset of receivers;

solving said set of relationships for X; and

broadcasting X over said network to said plurality of receivers of said network.

36. A method as described in claim 35 wherein said step of solving said set of relationships for X comprises the step of utilizing the Chinese Remainder procedure on said set of relationships.

37. A method as described in claim 36 wherein an individual receiver, performs the steps of:

receiving X over said network;

computing K'"'"'(i)=X mod (p(i)) to solve for an encrypted master key for said individual receiver; and

decrypting K'"'"'(i) using a private key, k(i), of said individual receiver to generate said master key, K.

38. A method as described in claim 37 further comprising the steps of:

encrypting a message with said master key and broadcasting a cipher message to all receivers of said network; and

decrypting said cipher message at said individual receiver using said master key.