Method and apparatus for distributing keys to secure devices such as a postage meter

• US 6,295,359 B1
• Filed: 05/21/1998
• Issued: 09/25/2001
• Est. Priority Date: 05/21/1998
• Status: Expired due to Term

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Ryan, Frederick W. Jr., Cordery, Robert A., Singer, Ari P.
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): KABAKOFF, STEPHEN ERIC
• Application Number:
  US09/082,698
• Time in Patent Office: 1,223 Days
• Field of Search: 713/157, 713/165, 713/176, 713/177, 713/180, 380/44, 380/286, 380/28, 380/30
• US Class Current: 380/44
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/4097 using mutual authentication between devices and transaction partners
• CPC Class Codes: G07B 17/00733 Cryptography or similar special procedures in a franking system
• CPC Class Codes: G07B 2017/00758 Asymmetric, public-key algorithms, e.g. RSA, Elgamal
• CPC Class Codes: G07B 2017/00766 Digital signature, e.g. DSA, DSS, ECDSA, ESIGN
• 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: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system

Abstract

A method for assigning keys to a plurality of devices in a public key cryptographic system includes generating a set of more than one master private keys; calculating for each master private key a corresponding master public key; installing in each of the plurality of devices a corresponding device private key derived as a linear combination of at least two of the master private keys from the set of master private keys whereby knowledge of the corresponding device private key installed in any one of the plurality of devices is not sufficient to determine the corresponding device private key of any other of the plurality of devices. A device public key can be calculated as a corresponding combination of the master public keys.

Claims

1. A method for assigning keys to a plurality of devices in a public key cryptographic system, the method comprising the steps of:

a) generating a set of more than one master private keys;

b) calculating for each master private key a corresponding master public key;

c) installing in each of the plurality of devices a corresponding device private key derived as a linear combination of at least two of the master private keys from the set of master private keys whereby knowledge of the corresponding device private key installed in any one of the plurality of devices is not sufficient to determine the corresponding device private key of any other of the plurality of devices and wherein each of the plurality of devices uses its corresponding device private key to generate a signature.

2. A method as recited in claim 1 further comprising the steps of generating a set of more than one master public keys based on the set of more than one master private keys and calculating a device public key for each of the plurality of devices based on a combination of the master public keys.

3. A method as recited in claim 1, further comprising the steps of

utilizing an algorithm to generate a matrix of coefficients, wherein each of the coefficients is associated with one of the master private keys and one of the plurality of devices and each of the plurality of devices has a row of coefficients associated therewith;

deriving the corresponding device private key for any particular one of the plurality of devices by utilizing the row of coefficients for the any particular one of the plurality of devices to determine the linear combination of master private keys for the any particular one of the plurality of devices.

4. A method as recited in claim 3, wherein the algorithm utilized to generate the matrix of coefficients is such that a number of the plurality of devices corresponding secure device private keys that need to be compromised to compromise the security of at least one other of the plurality of devices is equal to a total number of the master private keys.

5. A method as recited in claim 3, wherein the algorithm utilized to generate the matrix of coefficients is such that a predetermined number of the corresponding device private keys less than a total number of master private keys but greater than one are needed to compromise the security of at least one other of the plurality of devices.

6. A method as recited in claim 3, wherein the algorithm utilized to generate the matrix of coefficients utilizes data which identifies a specific one of the plurality of devices.

7. A method as recited in claim 6, wherein the data is a serial number associated with the specific one of the plurality of devices.

8. A method as recited in claim 6, wherein the data is a special key identifier which is different from a serial number associated with a specific one of the plurality of devices.

9. A method as recited in claim 3, wherein each row of coefficients of the matrix has at most N non-zero coefficients where N is less than a total number of master private keys but greater than 1.

10. A method as recited in claim 3, wherein a total number of the master private keys is divided into separate sets of master private keys and the algorithm is such that the row of coefficients for the any particular one of the plurality of devices only has one non-zero coefficient associated with each of the separate sets of master private keys such that the corresponding device private key for the any particular one of the plurality of devices is derived based on a linear combination of one private master key from each of the separate sets of master keys.

11. A method as recited in claim 10, wherein the number of sets of master private keys is 4.

12. A method as recited in claim 3 wherein all of the coefficients are either 1 or 0.

13. A method as recited in claim 1, wherein the plurality of devices are postage meters.