Method and apparatus for the generation and synchronization of cryptographic keys

• US 4,935,961 A
• Filed: 07/27/1988
• Issued: 06/19/1990
• Est. Priority Date: 07/27/1988
• Status: Expired due to Term

• Current Assignee: Pitney Bowes Incorporated WORL Headquarter Stamford Connecticut A Corporation OFDE
• Original Assignee: Pitney Bowes Incorporated WORL Headquarter Stamford Connecticut A Corporation OFDE
• Inventors: Gargiulo, Joseph L., Pastor, Jose
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/224,619
• Time in Patent Office: 692 Days
• Field of Search: 380/21, 380/28, 380/29, 380/36, 380/43, 380/44, 380/45, 380/48, 380/49
• US Class Current: 380/260
• CPC Class Codes: G07B 17/00733 Cryptography or similar special procedures in a franking system
• CPC Class Codes: G07B 2017/0079 Time-dependency
• CPC Class Codes: G07B 2017/0083 Postal data, e.g. postage, address, sender, machine ID, vendor
• CPC Class Codes: G07B 2017/00854 Key generation
• CPC Class Codes: G07B 2017/0087 Key distribution
• CPC Class Codes: G07B 2017/00887 using look-up tables, also called master tables with pointers
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/16 the keys or algorithms being changed during operation

Abstract

A method and apparatus for generating cryptographic keys for a postal manifest and for synchronizing cryptographic keys for transmitting postal data securely on a communication link is presented. The techniques for generating a key and for synchronizing keys use the same apparatus but use slightly different data to create a cryptographic key.

The postal data center maintains a unique set of data for each server station. Using this set of data along with a manifest sequence number (or communication transaction number) and the date, a cryptographic key is created. Each server station stores a fixed master key, KO, a permutation table, Pt, and ID, and GMT date. Using the manifest sequence number (or the communication transaction number) a row of the permutation table is altered and the master key KO is scrambled with the permutation table top get a new key K2. With K2, the date, server ID, and manifest sequence number (our communication transaction number) are encrypted. The result of this encryption yields another key K3. K3 is then used for encrypting the postal manifest or for communicating with a postal data center.

Claims

1. A method for generating encryption keys for a sequence of messages comprising the steps of:

(a) determining a sequence of N different encryption keys;

(b) associating a value of a sequence variable T_i, with each of said messages; and

(c) selecting one of said N encryption keys as a function of said variable T_i for each of said messages and encrypting at least a portion of each of said messages in accordance with an encryption key derived in a predetermined manner from the corresponding one of said selected keys; and

wherein

(d) said step of selecting one of said encryption keys produces results identical to the steps of;

(d1) storing a fixed master key K₀ having C elements;

(d2) storing a permutation table, said table having C columns and N rows, the columns of said table sequentially corresponding to the element positions of key K₀, the elements of said table consisting of numbers from 1 to C; and

(d3) selecting a row N_i of said table in accordance with said variable T_i ; and

(d4) scrambling key K_o to derive an encryption key K₁, having C elements, by, for all of said elements of K₁, setting the jth element of K₁ equal to the yth element of K₀, where y is the number at column j, row N_i of said permutation table, where j is an integral variable ranging from 1 to C.

2. The method of claim 1 further comprising expanding K₁ in a predetermined manner to derive an expanded encryption key K₂.

3. The method of claim 2 further comprising adjacent K₂ for parity.

4. The method of claim 2 further comprising modifying K₂ to form an encryption key K₃, said step of modifying comprising encryption variable data with K₂ to generate K₃.

5. The method of claim 4 wherein said step of encrypting variable data comprises encrypting a sequence dependent variable.

6. The method of claim 2 further comprising modifying K₂ to form an encryption key K₃, said step of modifying comprising encrypting variable data with K₂ to generate K₃.

7. The method of claim 6 wherein said step of encrypting variable data comprises encrypting a sequence dependent variable.

8. The method of claim 1 further comprising storing said permutation table in algorithmic form.

9. A method for synchronizing the generation of an encryption key K₃ at first and second stations comprising the steps of:

(a) providing identical sequences of N different encryption keys at said first and second stations;

(b) selecting a value for a variable T_i ;

(c) selecting one of said N encryption keys in accordance with said selected value and a predetermined function of said variable T_i at each of said first and second stations to obtain encryption keys K₁ and K'"'"'₁ respectively;

(d) encrypting a block of data D at said first station using an encryption key derived in a predetermined manner from said key K₁ to generate a message V₁ ;

(e) providing the plain text of said block D at said second station;

(f) transmitting said message V_i from said first station to said second station;

(g) decrypting said message V_i using a key derived from said key K'"'"'₁ in said predetermined manner to provide a block of data D; and

,

(h) comparing said data D and data D'"'"' to verify synchronization at said second station.

10. A method as described in claim 9 comprising the further steps of:

(i) encrypting a block of data D" at said second station using said key derived from key K'"'"'₁ to generate a message V_i ";

(j) providing the plain text of said block D" at said first station;

(k) transmitting said message V_i " to said first station;

(l) decrypting said message V_i " at said first station using said key derived from key K₁ to obtain a block of data D'"'"'";

(m) comparing said data D'"'"'" and data D" to verify synchronization at said first station.

11. The method of claim 9 wherein said predetermined manner of generating further comprises expanding K₁ and K'"'"'₁ in a predetermined manner at each of said stations, to form identical keys K₂ and K'"'"'₂.

12. The method of claim 11 further comprising modifying K₂ and K'"'"'₂ at each of said stations to generate keys for encryption and decryption of said blocks D and D'"'"' by encrypting identical variable data with K₂ and K'"'"'₂.

13. The method of claim 12 wherein said step of encrypting identical variable data comprises encrypting data identifying said first station.

14. Apparatus for generating encryption keys for a sequence of messages comprising:

(a) means for determining a sequence of N different encryption keys;

(b) means for associating a value of a sequence variable, T_i, with each of said messages; and

(c) means for selecting one of said N encryption keys as a function of said variable T_i for each of said messages and encrypting at least a portion of each of said messages in accordance with an encryption key derived in a predetermined manner from the corresponding one of said selected keys;

said selecting means further comprising,

(d) means for selecting one of said N encryption keys so as to produce results identical to the steps of;

(d1) storing a fixed master key K₀ ;

(d2) storing a permutation table, said table having C columns and N rows, the columns of said table sequentially corresponding to the element positions of key K₀, the elements of said table consisting of numbers from 1 to C and

(d3) selecting a row N_i of said table in accordance with said variable T_i ; and

(d4) scrambling key K₀ to derive an encryption key K₁, having C elements, by, for all elements of K₁, setting the jth element of K₁ equal to the yth element of K₀, where y is the number at column j row N_i of said permutation table, where j is an integral variable ranging from 1 to C.

15. The apparatus of claim 14 further comprising means for expanding K₁ in a predetermined manner to derive an expanded encryption key K₂.

16. The apparatus of claim 15 further comprising means for modifying K₂ to form an encryption key K₃, said modifying means comprising means for encrypting variable data with K₂ to generate K₃.

17. The apparatus of claim 16 wherein said means for encrypting variable data comprises for encrypting a sequence dependent variable.

18. The apparatus of claim 15 further comprising means for modifying K₂ to form an encryption key K₃, said modifying means comprising means for encrypting variable data with K₂ to generate K₃.

19. The apparatus of claim 18 wherein said means for encrypting variable data comprises means for encrypting a sequence dependent variable.

20. The apparatus of claim 14 further comprising means for storing said permutation table in complete form.