Apparatus and method for encrypting communications without exchanging an encryption key

• US 5,455,862 A
• Filed: 12/02/1993
• Issued: 10/03/1995
• Est. Priority Date: 12/02/1993
• Status: Expired due to Term

• Current Assignee: Crestech LLC
• Original Assignee: Crest Industries LLC
• Inventors: Hoskinson, John D.
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/160,897
• Time in Patent Office: 670 Days
• Field of Search: 380/21, 380/23, 380/49, 380/46
• US Class Current: 380/262
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/16 the keys or algorithms being changed during operation

Abstract

An encryption/decryption unit (EDU) and method for determining a data encryption key used in encrypting and decrypting data transmitted over a non-secure communication link. Each EDU includes a central processing unit (CPU) that controls its operation, random access memory (RAM) in which one or more sets of seed keys are stored, and a data encryption standard (DES) coprocessor that implements a data encryption algorithm developed by the U.S. National Bureau of Standards. The CPU includes special circuitry enabling it to operate in an encrypted mode so that it cannot be interrogated to discover the program or data stored therein. Each EDU randomly generates a pointer, bytes of which determine the number of times that a loop is repeated in which values (initially determined by two of the seed keys) are XORed together and encrypted using one of the seed keys to determine a portion of the data encryption key (DEK). The pointer is encrypted, along with other information, producing an encrypted key header that is transmitted to the other EDU establishing the link. Upon receiving the encrypted key header, it is decrypted, and the decrypted pointer is used by the receiving EDU to determine the portion of the DEK developed by the other EDU. The two portions of the DEK are then logically combined at each EDU to produce the final DEK, which is then used during the current communication session for encrypting data exchange between the two EDUs.

Claims

1. A method for establishing secure communications between a first station and a second station that are coupled together by an unsecure communication link, comprising the steps of:

(a) providing the first and the second stations with a plurality of seed keys that are common to both stations, but are not publicly known;

(b) at the first station, randomly selecting a first pointer value, and at the second station, randomly selecting a second pointer value;

(c) at each station, cyclically and repetitively encrypting a succession of values using one of the seed keys as an encryption key, each encrypted value determining a new value that is then encrypted, a first value of the succession of values that is initially thus encrypted being determined as a function of at least one of the plurality of seed keys, encryption of the succession of values occurring for a number of times determined as a function of the first pointer value at the first station, and as a function of the second pointer value at the second station, a last encrypted value thus determined at the first station corresponding to a first portion of a session data encryption key, and a last encrypted value thus determined at the second station corresponding to a second portion of the session data encryption key, said first and second portions of the session data encryption keys being temporarily stored at the respective stations;

(d) using one of the seed keys as an encryption key, encrypting the first pointer at the first station and the second pointer at the second station, to produce a first encrypted header at the first station and a second encrypted header at the second station, respectively;

(e) interchanging the first and the second encrypted headers between the first and the second stations;

(f) using said one seed key, decrypting the first encrypted header at the second station and the second encrypted header at the first station to recover the first and second pointers, respectively;

(g) repeating step (c), to determine the first portion of the session data encryption key as a function of the first pointer at the second station, and to determine the second portion of the session data encryption key as a function of the second pointer at the first station, respectively;

(g) at each station, combining the first and second portions of the session data encryption key to determine a final session data encryption key; and

(h) using the final session data encryption key at each station to encrypt and decrypt data exchanged between the two stations.

2. The method of claim 1, wherein each station is provided with identical first, second, and third seed keys.

3. The method of claim 2, wherein step (c) of claim 1 comprises the steps of:

(a) logically combining the third seed key with the second seed key to form the first value;

(b) encrypting the first value with the first seed key to form an encrypted value;

(c) logically combining the encrypted value with the first value to form a new value;

(d) encrypting the new value with the first seed key to form a new encrypted value;

(e) repeating steps (c) and (d) for the number of times determined by one of the first and second pointers to obtain the last encrypted value which corresponds to one of the first and the second portions of the session data encryption key.

4. The method of claim 3, wherein the first and second pointers are used as a counter indices to determines the number of times that the steps of logically combining and encrypting are implemented.

5. The method of claim 4, wherein the first and second pointers each comprise a plurality of bytes, each byte serving as a successive counter index to determine the number of times that the steps of logically combining and encrypting are implemented, until the number of times determined by a last byte of the pointer is completed.

6. The method of claim 1, further comprising the steps of accumulating a cyclic redundancy check value for each portion of the session data encryption key;

and encrypting the cyclic redundancy check values at each station as part of the first and second encrypted headers, said cyclic redundancy check values being decrypted after the first and second encrypted headers are interchanged between the first and the second stations and used to determine whether an error has occurred in the determination of the first and second portions of the data session encryption key by the second and the first stations, respectively.

7. The method of claim 1, further comprising the step of including network cyclic redundancy check values as part of the first and second encrypted headers that are interchanged by the first and the second stations, said network cyclic redundancy check values being decrypted to confirm that the first and the second stations are both members of a common network.

8. The method of claim 1, wherein each station is identified by a unique station identification code that is unalterable, further comprising the step of including the station identification code in at least one of the first and second encrypted headers, said station identification code being used to ensure that a secure communication link is established only between two stations intending to communicate and not with a third station.

9. A method for ensuring secure communications between two sites, comprising:

(a) randomly selecting a pointer;

(b) providing a plurality of seed keys, each having their own initial value;

(c) using one of the seed keys, encrypting a value initially determined by another seed key to produce an encrypted value, said encrypted value being used to determine a successive value that replaces a previous value;

(d) repeating step (c) for a number of times determined as a function of the pointer, each successive value that is encrypted replacing the encrypted value previously determined, the encrypted value last produced comprising a portion of a session data encryption key;

(e) encrypting the pointer with one of the seed keys to produce a locally encrypted pointer;

(f) transmitting the locally encrypted pointer to another site;

(g) receiving a remotely encrypted pointer from another site;

(h) decrypting the remotely encrypted pointer received from the other site;

(i) using the pointer that was decrypted in step (h), repeating steps (c) and (d) to determine a different portion of the session data encryption key;

(j) logically combining the portions of the session data encryption key to form a complete session data encryption key; and

(k) using the complete session data encryption key to encrypt and decrypt data sent and received between the two sites.

10. The method of claim 9, wherein the other site carries out substantially the same steps (a) through (d) to determine the different portion of the session data encryption key.

11. The method of claim 9, wherein the pointers each comprise a plurality of bytes, each byte serving as a counter index for determining the number of times that step (d) is repeated, the encrypted value produced using a preceding byte of the pointer as the counter index being used in repeating step (d) additional times determined by a current byte of the pointer.

12. The method of claim 9, wherein three seed keys are provided for use in determining the portion of the session data encryption key, one of the three seed keys being used to encrypt a logical combination of the other two seed keys to produce the encrypted value in step (c) also being used to encrypt the pointer in step (e).

13. The method of claim 9, further comprising the steps of encrypting at least one cyclic redundancy check value for transmission to the other site, said cyclic redundancy check value being used to detect errors.

14. The method of claim 9, further comprising the step of encrypting a unique station identifier for transmission to the other site using one of the seed keys.

15. The method of claim 9, further comprising the step of selecting one of a plurality of sets of seed keys for use in determining the portion of the session data encryption key and for use in encrypting the pointer.

16. The method of claim 15, wherein a unique set of the seed keys is provided in common to all sites comprising a private network.

17. Apparatus for encrypting and decrypting data, comprising:

(a) encryption processor means for encrypting and decrypting data using an encryption key that is input thereto;

(b) control means, coupled to the encryption processor means, for controlling the operation of the encryption processor means, said control means controlling input to the encryption processor means of data from an external source for encryption and decryption and supplying the encryption processor means with the encryption key for use in encrypting and decrypting the data to produce an output signal in response to programmed instructions that cause the control means to automatically randomly select a pointer and to process a plurality of seed keys in repetitive cycles for a number of times determined as a function of the pointer, said seed keys initially being predefined, at least one of the seed keys being used as an encryption key that is input to the encryption processor by the control means to encrypt a temporary value derived as a function of at least one other seed key to produce a new temporary value for use in a next cycle, a last encrypted value thus produced comprising a part of a session data encryption key; and

(c) non-volatile memory means, coupled to the control means, for storing the plurality of seed keys, which are initially predefined, and for storing the programmed instructions, said programmed instructions also causing the control means to;

(i) encrypt the pointer that was randomly selected to form an encrypted pointer;

(ii) transmit the encrypted pointer to a remote site;

(iii) input a different encrypted pointer received from the remote site to the encryption processor means for decryption using one of the plurality of seed keys, producing a different pointer;

(iv) determine a different part of the session data encryption key as a function of the different pointer that was decrypted and the plurality of the seed keys that are predefined, using the encryption processor means; and

(v) logically combine the part of the session data encryption key determined locally with the different part of the session data encryption key determined as a function of the different pointer, to form a complete session data encryption key, said complete session data encryption key being input to the encryption processor means for encrypting and decrypting data during a communication session with the remote site.

18. The apparatus of claim 17, wherein the non-volatile memory means include an internal power source that supplies electrical power to maintain storage of the plurality of seed keys that are initially predefined, absent an external source providing electrical power.

19. The apparatus of claim 18, further comprising a potting material for encapsulating the encryption processor means, the control means, and the non-volatile memory means within a radio and light wave opaque material, said potting material being sufficiently hard and resistant to dissolution by solvents to prevent its removal without causing damage to interconnections coupling the non-volatile memory means to the control means and damage to interconnections supplying electrical power to the non-volatile memory means from the internal power source, such damage causing erasure of the plurality of seed keys and programmed instructions stored in the non-volatile memory means, said control means also responding to any attempt to externally interrogate the non-volatile memory means by causing erasure of the key encryption keys stored therein.

20. The apparatus of claim 17, further comprising means for selecting one of a plurality of sets of the seed keys that are stored in the non-volatile memory means, for use in a current communication session with the remote site, each set of seed keys being used on one of a corresponding plurality of different networks, so that encrypted data can be exchanged and decrypted only by using the same set of seed keys locally and at the remote site for encrypting and decrypting the pointers, thereby enabling encrypted communication only between sites in a common network.

21. The apparatus of claim 17, wherein the programmed instructions further cause the control means to determine at least one cyclic redundancy check value that is encrypted by the encryption processor means using one of the seed keys that is predefined to produce an encrypted cyclic redundancy check value that is transmitted to the remote, said at least one cyclic redundancy check value being used to determine whether an error has occurred.

22. The apparatus of claim 21, wherein the control means cause the encryption processor means to encrypt a cyclic redundancy check value for detecting an error in determining the part session data encryption key at the remote site as a function of the encrypted pointer that is transmitted thereto.

23. The apparatus of claim 21, wherein the control means causes the encryption processor means to encrypt a network cyclic redundancy check value for use in detecting an error at the remote site, if the remote site is not in an intended network.

24. The apparatus of claim 17, wherein the non-volatile memory means also store unique identification data for the apparatus that the programmed instructions preclude the control means from altering, and wherein the programmed instructions cause the control means to input the unique identification data to the encryption processor means for encryption using one of the plurality of seed keys that are predefined, for transmission to the remote site.

25. The apparatus of claim 24, wherein the programmed instructions cause the control means to terminate communications with the remote site if unique identification data that are received in an encrypted form from the remote site and then decrypted by the encryption processor means do not match the unique identification data stored in the non-volatile memory.