Public key cryptosystem key management based on control vectors5200999
Abstract
A data processing system, method and program are disclosed, for managing a public key cryptographic system. The method includes the steps of generating a first public key and a first private key as a first pair in the data processing system, for use with a first public key algorithm and further generating a second public key and a second private key as a second pair in the data processing system, for use with a second public key algorithm. The method then continues by assigning a private control vector for the first private key and the second private key in the data processing system, for defining permitted uses for the first and second private keys. Then the method continues by forming a private key record which includes the first private key and the second private key in the data processing system, and encrypting the private key record under a first master key expression which is a function of the private control vector. The method then forms a private key token which includes the private control vector and the private key record, and stores the private key token in the data processing system. At a later time, the method receives a first key use request in the data processing system, requiring the first public key algorithm. In response to this, the method continues by accessing the private key token in the data processing system and checking the private control vector to determine if the private key record contains a key having permitted uses which will satisfy the first request. The method then decrypts the private key record under the first master key expression in the data processing system and extracts the first private key from the private key record. The method selects the first public key algorithm in the data processing system for the first key use request and executes the first public key algorithm in the data processing system using the first private key to perform a cryptographic operation to satisfy the first key use request.
Claims
What is claimed is:
1. In a data processing system, a method for managing a public key cryptographic system, comprising the steps of:
generating a first public key and a first private key as a first pair in said data processing system, for use with a first public key algorithm;
generating a second public key and a second private key as a second pair in said data processing system, for use with a second public key algorithm;
assigning a private control vector for said first private key and said second private key in said data processing system, for defining permitted uses for said first and second private keys;
forming a private key record which includes said first private key and said second private key in said data processing system, and encrypting said private key record under a first master key expression which is a function of said private control vector;
forming a private key token which includes said private control vector and said private key record, and storing said private key token in said data processing system;
receiving a first key use request in said data processing system, reguiring said first public key algorithm;
accessing said private key token in said data processing system and checking said private control vector to determine if said private key record contains a key having permitted uses which will satisfy said first request;
decrypting said private key record under said first master key expression in said data processing system and extracting said first private key from said private key record;
selecting said first public key algorithm in said data processing system for said first key use request;
selecting said first public key algorithm in said data processing system using said first private key to perform a cryptographic operation to satisfy said first key use request.
2. The method of claim 1, which further comprises:
said private key record including first parse data to locate said first private key and said second private key in said key record;
said extracting step including using said parse data for extracting said first private key from said private key record.
3. The method of claim 1, which further comprises:
forming a first private key authentication record in said data processing system, by computing a hash value using a hashing function on said private key record and encrypting said first private key authentication record under a second master key expression which is a function of said private control vector;
said private key token including said first private key authentication record.
4. The method of claim 3, which further comprises:
after said decrypting step, computing a second private key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted private key record and comparing said second a private key authentication record with said first private key authentication record;
aborting further processing of said first key use request in said data processing system, if said second private key authentication record is not equal to said first private key authentication record.
5. The method of claim 4, which further comprises:
said private key token including first header data to locate said control vector, said private key record and said private key authentication record in said private key token;
said accessing step including using said header data to locate said private key record in said private key token.
6. The method of claim 1, which further comprises:
assigning a public control vector for said first public key and said second public key in said data processing system, for defining permitted uses for said first and second public keys;
forming a public key record which includes said first public key and said second public key in said data processing system, and encrypting said public key record under a third master key expression which is a function of said public control vector;
forming a public key token which includes said public control vector and said public key record, and storing said public key token in said data processing system;
receiving a second key use request in said data processing system, regulating said second public key algorithm;
accessing said public key token in said data processing system and checking said public control vector to determine if said public key record contains a key having permitted uses which will satisfy said second request;
decrypting said public key record under said third master key expression in said data processing system and extracting said first public key from said public key record;
selecting said second public key algorithm in said data processing system for said second key use request;
selecting said second public key algorithm in said data processing system using said first public key to perform a cryptographic operation to satisfy said second key use request.
7. The method of claim 6, which further comprises:
said public key record including second parse data to locate said first public key and said second public key in said key record;
said extracting step for said first public key including using said parse data for extracting said first public key from said public key record.
8. The method of claim 6, which further comprises:
forming a second public key authentication record in said data processing system, by computing a hash value using said hashing function on said public key record and encrypting said second public key authentication record under a fourth master key expression which is a function of said public control vector;
said public key token including said second public key authentication record.
9. The method of claim 8, which further comprises:
after said decrypting step for said public key record, computing a second public key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted public key record and comparing said second a public key authentication record with said second public key authentication record;
aborting further processing of said second key use request in said data processing system, if said second public key authentication record is not equal to said second public key authentication record.
10. The method of claim 9, which further comprises:
said public key token including second header data to locate said control vector, said public key record and said public key authentication record in said public key token;
said accessing step for said public key token including using said header data to locate said public key record in said public key token.
11. In a data processing system, a method for managing a public key cryptographic system, comprising the steps of:
generating a public key and a private key as a pair in said data processing system, for use with a public key algorithm;
assigning a private control vector for said private key in said data processing system, for defining permitted uses for said private key;
forming a private key record which includes said private key in said data processing system, and encrypting said private key record under a first master key expression which is a function of said private control vector;
forming a private key token which includes said private control vector and said encrypted private key record and storing said private key token in said data processing system;
receiving a first key use request in said data processing system, requiring execution of said public key algorithm with a private key;
accessing said private key token in said data processing system and checking said private control vector to determine if said private key record contains a key having permitted uses which will satisfy said first request;
decrypting said private key record under said first master key expression in said data processing system and extracting said private key from said private key record;
executing said public key algorithm in said data processing system using said private key to perform a cryptographic operation to satisfy said first key use request.
12. The method of claim 11, which further comprises:
assigning a public control vector for said public key in said data processing system, for defining permitted uses for said public key;
forming a public key record which includes said public key in said data processing system, and encrypting said public key record under a second master key expression which is a function of said public control vector;
forming a public key token which includes said public control vector and said public key record and storing said public key token in said data processing system;
receiving a second key use request in said data processing system, requiring execution of said public key algorithm with a public key;
accessing said public key token in said data processing system and checking said public control vector to determine if said public key record contains a key having permitted uses which will satisfy said second request;
decrypting said public key record under said second master key expression in said data processing system and extracting said public key from said public key record;
executing said public key algorithm in said data processing system using said public key to perform a cryptographic operation to satisfy said second key use request.
13. The method of claim 12, which further comprises:
forming a first private key authentication record in said data processing system, by computing a hash value using a hashing function on said private key record;
said private key token including said first private key authentication record.
14. The method of claim 13, which further comprises:
after said decrypting step for said private key record, computing a second private key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted private key record and comparing said second a private key authentication record with said first private key authentication record;
aborting further processing of said first key use request in said data processing system, if said second private key authentication record is not equal to said first private key authentication record.
15. The method of claim 14, which further comprises:
forming a second public key authentication record in said data processing system, by computing a hash value using said hashing function on said public key record;
said public key token including said second public key authentication record.
16. The method of claim 15, which further comprises:
after said decrypting step for said public key record, computing a second public key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted public key record and comparing said second a public key authentication record with said second public key authentication record;
aborting further processing of said second key use request in said data processing system, if said second public key authentication record is not equal to said second public key authentication record.
17. In a data processing system, a method for managing a public key cryptographic system, comprising the steps of:
generating a public key and a private key in said cryptographic system;
assigning a public key control vector to said public key in accordance with intended uses for said public key;
assigning a private key control vector to said private key in accordance with intended uses for said private key;
storing said public key in a public key record and storing said private key in a private key record;
encrypting said public key record under a master key and encrypting said private key under said master key;
forming a modification detection code on a concatenated expression of said public key control vector and said public key record as a public key authentication record;
forming a modification detection code on a concatenated expression of said private key control vector and said private key record to produce a private key authentication record;
encrypting said public key authentication record under said master key and encrypting said private key authentication record under said master key;
forming a public key token which includes said public key control vector in a first field, said encrypted public key record in a second field, and said encrypted public key authentication record in a third field;
forming a private key token including said private key control vector in a first field, said encrypted private key record in a second field, and said encrypted private key authentication record in a third field.
18. The method of claim 17 wherein said master key is a secret key belonging to a symmetric key algorithm.
19. The method of claim 18 wherein said secret key is a data encryption algorithm key.
20. In a data processing system, a computer program for managing a public key cryptographic system, which when executed on said data processing system, performs a method comprising the steps of:
generating a first public key and a first private key as a first pair in said data processing system, for use with a first public key algorithm;
generating a second public key and a second private key as a second pair in said data processing system, for use with a second public key algorithm;
assigning a private control vector for said first private key and said second private key in said data processing system, for defining permitted uses for said first and second private keys;
forming a private key record which includes said first private key and said second private key in said data processing system, and encrypting said private key record under a first master key expression which is a function of said private control vector;
forming a private key token which includes said private control vector and said private key record, and storing said private key token in said data processing system;
receiving a first key use request in said data processing system, regulating said first public key algorithm;
accessing said private key token in said data processing system and checking said private control vector to determine if said private key record contains a key having permitted uses which will satisfy said first request;
decrypting said private key record under said first master key expression in said data processing system and extracting said first private key from said private key record;
selecting said first public key algorithm in said data processing system for said first key use request;
selecting said first public key algorithm in said data processing system using said first private key to perform a cryptographic operation to satisfy said first key use request.
21. The method of claim 20, which further comprises:
said private key record including first parse data to locate said first private key and said second private key in said key record;
said extracting step including using said parse data for extracting said first private key from said private key record.
22. The method of claim 20, which when executed on said data processing system, performs the further steps, comprising:
forming a first private key authentication record in said data processing system, by computing a hash value using a hashing function on said private key record and encrypting said first private key authentication record under a second master key expression which is a function of said private control vector;
said private key token including said first private key authentication record.
23. The method of claim 22, which when executed on said data processing system, performs the further steps, comprising:
after said decrypting step, computing a second private key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted private key record and comparing said second a private key authentication record with said first private key authentication record;
aborting further processing of said first key use request in said data processing system, if said second private key authentication record is not equal to said first private key authentication record.
24. The method of claim 23, which further comprises:
said private key token including first header data to locate said control vector, said private key record and said private key authentication record in said private key token;
said accessing step including using said header data to locate said private key record in said private key token.
25. In a data processing system, a computer program for managing a public key cryptographic system, which when executed on said data processing system, performs a method comprising the steps of:
generating a public key and a private key as a pair in said data processing system, for use with a public key algorithm;
assigning a private control vector for said private key in said data processing system, for defining permitted uses for said private key;
forming a private key record which includes said private key in said data processing system, and encrypting said private key record under a first master key expression which is a function of said private control vector;
forming a private key token which includes said private control vector and said encrypted private key record and storing said private key token in said data processing system;
receiving a first key use request in said data processing system, requiring execution of said public key algorithm with a private key;
accessing said private key token in said data processing system and checking said private control vector to determine if said private key record contains a key having permitted uses which will satisfy said first request;
decrypting said private key record under said first master key expression in said data processing system and extracting said private key from said private key record;
executing said public key algorithm in said data processing system using said private key to perform a cryptographic operation to satisfy said first key use request.
26. The method of claim 25, which when executed on said data processing system, performs the further steps, comprising:
assigning a public control vector for said public key in said data processing system, for defining permitted uses for said public key;
forming a public key record which includes said public key in said data processing system, and encrypting said public key record under a second master key expression which is a function of said public control vector;
forming a public key token which includes said public control vector and said public key record, and storing said public key token in said data processing system;
receiving a second key use request in said data processing system, requiring execution of said public key algorithm with a public key;
accessing said public key token in said data processing system and checking said public control vector to determine if said public key record contains a key having permitted uses which will satisfy said second request;
decrypting said public key record under said second master key expression in said data processing system and extracting said public key from said public key record;
executing said public key algorithm in said data processing system using said public key to perform a cryptographic operation to satisfy said second key use request.
27. The method of claim 26, which when executed on said data processing system, performs the further steps, comprising:
forming a first private key authentication record in said data processing system, by computing a hash value using a hashing function on said private key record;
said private key token including said first private key authentication record.
28. The computer program of claim 27, which when executed on said data processing system, performs the further steps, comprising:
after said decryption step for said private key record, computing a second private key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted private key record and comparing said second a private key authentication record with said first private key authentication record;
aborting further processing of said first key use request in said data processing system, if said second private key authentication record is not equal to said first private key authentication record.
29. The computer system of claim 28, which when executed on said data processing system, performs the further steps, comprising:
forming a second public key authentication record in said data processing system, by computing a hash value using a hashing function on said public key record;
said public key token including said second public key authentication record.
30. The computer program of claim 29, which when executed on said data processing system, performs the further steps, comprising:
after said decrypting step for said public key record, computing a second public key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted public key record and comparing said second a public key authentication record with said first public key authentication record;
aborting further processing of said second key use request in said data processing system, if said second public key authentication record is not equal to said second public key authentication record.
31. A data processing system for managing a public key cryptographic system, comprising:
first generating means for generating a first public key and a first private key as a first pair in said data processing system, for use with a first public key algorithm;
second generating means for generating a second public key and a second private key as a second pair in said data processing system, for use with a second public key algorithm;
assigning means for assigning a private control vector for said first private key in said second private key in said data processing system, for defining permitted uses for said first and second private keys;
key record forming means coupled to said first and second generating means, for forming a private key record which includes said first private key and said second private key in said data processing system, encrypting means coupled to said key record forming means and said assigning means, for encrypting said private key record under a first master key expression which is a function of said private control vector;
key token forming means coupled to said assigning means and to said key record forming means, for forming a private key token which includes said private control vector and said private key record;
storing means coupled to said key token forming means, for storing said private key token in said data processing system;
receiving means coupled to a user input, for receiving a first key use request in said data processing system, requiring said first public key algorithm;
accessing means coupled to said receiving means and to said storing means, for accessing said private key token in said data processing system and checking said private control vector to determine if said private key record contains a key having permitted uses which will satisfy said first request;
decrypting means coupled to said accessing means, for decrypting said private key record under said first master key expression in said data processing system and extracting said first private key from said private key record;
selecting means coupled to said receiving means, for selecting said first public key algorithm in said data processing system for said first key use request;
executing means coupled to said selecting means and to said decrypting means, for executing said first public key algorithm in said data processing system using said first private key to perform a cryptographic operation to satisfy said first key use request.
32. The system of claim 31, which further comprises:
authentication record forming means coupled to said key record forming means, for forming a first private key authentication recording said data processing system, by computing a hash value using a hashing function on said private key record and encrypting said first private key authentication record under a second master key expression which is a function of said private control vector;
said private key token including said first private key authentication record.
33. The system of claim 32, which further comprises:
computing means coupled to said decryption means, for computing a second private key authentication record in said data processing system, by computing a second hash value using said hashing function on said decrypted private key record and comparing said second a private key authentication record with said first private key authentication record;
terminating means coupled to said computing means, for aborting further processing of said first key use request in said data processing system, if said second private key authentication record is not equal to said first private key authentication record.
Description
BACKGROUND OF THE INVENTION
1. Technical Field
The invention disclosed broadly relates to data processing systems and methods and more particularly relates to cryptographic systems and methods for use in data processing systems to enhance security.
2. Background Art
The following co-pending patent applications are related to this invention and are incorporated herein by reference:
B. Brachtl, et al., "Controlled Use of Cryptographic Keys Via Generating Stations Established Control Values," U.S. Pat. No. 4,850,017, issued Jul. 18, 1989, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors," U.S. Pat. No. 4,941,176, issued Jul. 10, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Data Cryptography Operations Using Control Vectors," U.S. Pat. No. 4,918,728, issued Apr. 17, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Personal Identification Number Processing Using Control Vectors," U.S. Pat. No. 4,924,514, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Extended Control Vectors," U.S. Pat. No. 4,924,515, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors with Multi-Path Checking," Ser. No. 07/596,637, filed Oct. 12, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Cryptographic Operations Using Alternate Modes of Control Vector Enforcement," Ser. No. 07/574,012, filed Aug. 22, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Key Management Using Programmable Control Vector Checking," U.S. Pat. No. 5,007,089, issued Apr. 9, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Control Vector Translation," U.S. Pat. No. 4,993,069 issued Feb. 12, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Data Authentication Using Modification Detection Codes Based on a Public One Way Encryption Function," U.S. Pat. No. 4,908,861, issued Mar. 13, 1990, assigned to IBM Corporation and incorporated herein by reference.
D. Abraham, et al., "Smart Card Having External Programming Capability and Method of Making Same," Ser. No. 004,501, filed Jan. 19, 1987, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, "Technique for Reducing RSA Crypto Variable Storage", U.S. Pat. No. 4,736,423, issued Apr. 5, 1988, assigned to IBM Corporation and incorporated by reference.
S. M. Matyas, et al., "Method and Apparatus for Controlling the Use of a Public Key, Based on the Level of Import Integrity for the Key, " Ser. No. 07/602,989, filed Oct. 24, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors," Ser. No. 07/748,407, filed Aug. 22, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Generating Public and Private Key Pairs Using a Passphrase," filed on the same day as the instant application, assigned to IBM Corporation and incorporated herein by reference.
The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on associating with a cryptographic key, a control vector which provides the authorization for the uses of the key intended by the originator of the key. The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on the Data Encryption Algorithm (DEA), see American National Standard X3.92-1981, Data Encryption Algorithm, American Standards Institute, New York, (Dec. 31, 1981), whereas the present invention is based on both a secret key algorithm, such as the DEA, and a public key algorithm. Various key management functions, data cryptography functions, and other data processing functions are possible using control vectors, in accordance with the invention. A system administrator can exercise flexibility in the implementation of his security policy by selecting appropriate control vectors in accordance with the invention. A cryptographic facility (CF) in the cryptographic architecture is described in the above cited patents by S. M. Matyas, et al. The CF is an instruction processor for a set of cryptographic instructions, implementing methods and key generation methods. A memory in the cryptographic facility stores a set of internal cryptographic variables. Each cryptographic instruction is described in terms of a sequence of processing steps required to transform to a set of output parameters. A cryptographic facility application program (CFAP) is also described in there referenced patents and patent applications, which defines an invocation method, as a calling sequence, for each cryptographic instruction consisting of an instruction mnemonic and an address with corresponding input and output parameters.
Public key encryption algorithms are described in a paper by W. Diffie and M. E. Hellman entitled "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the IEEE, Volume 67, No. 3, March 1979, pp. 397-427. Public key systems are based on dispensing with the secret key distribution channel, as long as the channel has a sufficient level of integrity. In a public key cryptographic system, two keys are used, one for enciphering and one for deciphering. Public key algorithm systems are designed so that it is easy to generate a random pair of inverse keys PU for enciphering and PR for deciphering and it is easy to operate with PU and PR, but is computationally infeasible to compute PR from PU. Each user generates a pair of inverse transforms, PU and PR. He keeps the deciphering transformation PR secret, and makes the enciphering transformation PU public by placing it in a public directory. Anyone can now encrypt messages and send them to the user, but no one else can decipher messages intended for him. It is possible, and often desirable, to encipher with PU and decipher with PR. For this reason, PU is usually called a public key and PR is usually called a private key. A corollary feature of public key cryptographic systems is the provision of a digital signature which uniquely identifies the sender of a message. If user A wishes to send a signed message M to user B, he operates on it with his private key PR to produce the signed messages. PR was used as A's deciphering key when privacy was desired, but it is now used as his "enciphering" key. When user B receives the message S, he can recover the message M by operating on the ciphertext S with A's public PU. By successfully decrypting A's message, the receiver B has conclusive proof it came from sender A. Examples of public key cryptography are provided in the following U.S. patents: U.S. Pat. No. 4,218,582 to Hellman, et al., "Public Key Cryptographic Apparatus and Method;" U.S. Pat. No. 4,200,770 to Hellman, et al., "Cryptographic Apparatus and Method;" and U.S. Pat. No. 4,405,829 to Rivest, et al., "Cryptographic Communications System and Method."
Most cryptographic systems make use of many different types of keys, so that information encrypted with a key of one type is not affected by using a key of another type. A key assigned on the basis of the information the key encrypts or the use being make of the key. For example, a data-encrypting key encrypts data. A key-encrypting key encrypts keys. A PIN-encrypting key encrypts personal identification numbers (PINs) used in electronic funds transfer and point-of-sale applications. A MAC key is used to generate and authenticate message authentication codes (MACs).
The use of encryption is based on a strategy of protecting a large amount of information (a data file or communications session) with a smaller additional amount of information (a single key). Sophisticated key hierarchies have been divised using this principle. For example, U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, which are based on a symmetric key algorithm such as the Data Encryption Algorithm (DEA), make use of a key hierarchy wherein keys belonging to a cryptographic device are encrypted with a single master key and stored in a key data set. The master key is stored in clear form within the cryptographic hardware. The concept of using a single master key to encrypt keys stored in a key set is known as the master key concept (see C. H. Meyer and S. M. Matyas, Cryptography--A New Dimension in Computer Data Security, John Wiley & Sons, Inc., New York, 1982.). Until now, the master key concept has been applied only to cryptographic systems based on a symmetric key cryptographic algorithm. However, the present invention extends the master key concept and teaches how it may be applied to cryptographic systems based on an asymmetric key cryptographic algorithm, and more particularly how it may be applied cryptographic systems incorporating both asymmetric and symmetric key cryptographic algorithms, generally called employing (1) an asymmetric algorithm or (2) both asymmetric and symmetric algorithms, there is still a need to use many public and private keys pairs. Hence, at a minimum, the private keys must be stored in encrypted form outside the cryptographic hardware.
In order for a cryptographic system employing the master key concept to be made operable, each device must be first initialized with a master key and one or more other keys to permit the cryptographic system to communicate cryptographically with other cryptographic systems or to distribute keys to other cryptographic systems. Typically, these keys are generated and installed using manual entry techniques. In a well designed cryptographic system, all other keys are generated and handled by the cryptographic system automatically. Keys generated by the cryptographic system are stored in encrypted form in a cryptographic key data set or transmitted in encrypted form to a designated receiving device where the key is imported (i.e. re-encrypted to a form suitable for storage and use at the receiving device). Thus, an important feature of any key management scheme is the method used to encrypt keys for sage storage in a cryptographic key data set.
At the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the form of each generated key. For example, a generated key can be produced (1) in clear form, (2) in encrypted form suitable for storage in a cryptographic key data set, or (3) form suitable for distribution to a designated receiving device. Generally, cryptographic systems have different options for generating keys in these different forms. Also, at the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the type and usage of each generated key. Type and usage information are examples of a class of key-related information called control information. For example, in U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, and 5,007,089, the control information is embodied within a data variable called the control vector. The control vector concepts taught in these U.S. patents and IBM dockets is summarized in a paper by S. M. Matyas entitled "Key handling with control vectors," IBM Systems Journal, Volume 30, No. 2, 1991, pp 151-174.
In a cryptographic system employing control vectors, every key K has an associated control vector C. Thus, K and C denote a 2-tuple, where K initializes the cryptographic algorithm by selecting an enciphering transformation and C initializes the cryptographic hardware by selecting a set of cryptographic instructions, modes, and usage that K is granted. Implementation of the control vector concept requires that K and C be coupled cryptographically. Otherwise, the key-usage attributes granted to K by C could be changed by merely replacing C with another control vector. The method for accomplishing this is based on integrating C into the functions used to encrypt and decrypt keys, called control vector encryption (CVE) and control vector decryption (CVD). FIG. 1 is a block diagram illustration showing the implementation of the CVE and CVD algorithms within a cryptographic facility 30. CF 30 contains a CVE algorithm 1, a CVD algorithm 2, a master key (KM) 3, to-be-encrypted key K 4, and a recovered key K 5. The CVE algorithm 1 encrypts a clear key K 4 within CF 30 using a variant key KM+C formed as the Exclusive OR product of master key KM 3 stored within CF 30 and control vector C 6 specified as an input to CF 30 to produce an output encrypted key value of the form e*KM+C(K) 7. Note that "+" denotes the Exclusive OR operation and e* denotes encryption with a 128-bit key. The operation of encryption consists of encrypting K with the leftmost 64 bits of KM+C then decrypting the result with the rightmost 64 bits of KM+C and then encrypting that result with the leftmost 64 bits of KM+C. The CVD algorithm 2 decrypts the encrypted key e*KM+C(K) 9 specified as an input to CF 30 with the variant key KM+C formed as the Exclusive-OR produce of master key KM 3 stored within CF 30 and control vector C 8 specified as an input to CF 30 to produce an output clear key K 5. The operation of decryption consists of decrypting e*KM+C(K) with the leftmost 64 bit of KM+C them encrypting the result with the rightmost 64 bits of KM+C and then decrypting that result with the leftmost 64 bits of KM+C. The CVE algorithm is used to encrypt and protect keys stored outside the CF. The CVD algorithm is used to decrypt and recover keys to be processed within the CF.
FIG. 2 is a block diagram illustration of the control vector encryption (CVE) algorithm. Referring to FIG. 2, C is an input control vector whose length is a multiple of 64 bits; KK is a 128-bit key-encrypting key consisting of a leftmost 64-bit part KKL and a rightmost 64- bit KKR, i.e., KK=(KKL,KKR); K is a 64-bit key or the leftmost or rightmost 64-bit part of a 128-bit to be encrypted. The specification of KK is meant to be very general. For example, KK can be the master key KM, or some other key-encrypting key. The inputs are processed as follows. Control vector C is operated on by hashing algorithm ha, described below, to produce the 128-bit output hash vector H. H is Exclusive-ORed with KK to produce 128-bit output KK+H. Finally, K is encrypted with KK+H to produce output e*KK+H(K), where e* indicates encryption with 128-bit key KK+H using an encryption-decryption-encryption (e-d-e) algorithm as defined in ANSI Standard X9.17-1985 entitled "American National Standard for Financial Institution Key Management (Wholesale)", 1985, and is ISO Standard 8732 entitled "Banking--Key Management (Wholesale)", 1988.
FIG. 3 is a block diagram illustration of the control vector decryption (CVD) algorithm. Referring to FIG. 3, C is an input control vector whose length is a multiple of 64 bits; KK is a 128-bit key-encrypting key consisting of a leftmost 64-bit part KKL and a rightmost 64-bit part KKR, i.e., KK=(KKL,KKR); e*KK+H(K) is the encrypted key to be decrypted. Control vector C is operated on by hashing algorithm ha, described below, to produce the 128-bit output hash vector H. H is Exclusive-ORed with KK to produce 128-bit output KK+H. Finally, e*KK+H(K) is decrypted with KK+H using a decryption-encryption-decryption (d-e-d) algorithm to produce output K. The d-e-d algorithm is just the inverse of the e-d-e algorithm.
FIG. 4 is a block diagram illustration of hashing algorithm ha. Hashing algorithm ha operates on input control vector C (whose length is a multiple of 64 bits) to produce a 128-bit output H, where H=ha(C). If C is 64 bits, ha(C) is set equal to (C,C), where the comma denotes concatenation, and the extension field (bits 45,46) in ha(C) is set equal to B`00`. That is, ha acts like a concatenation function. If C is 128 bits, ha(C) is set equal to C, and the extension field in ha(C) is set equal to B`01`. That is, ha acts like an identity function. If C is greater than 128 bits, ha(C) is set equal to a 128-bit one way cryptographic function of C, e.g. a 128-bit modification detection code calculated by the MDC-2 algorithm in FIG. 5, and the extension field in ha(C) is set equal to B`10`. In each of the three cases, the eighth bit of each byte in ha(C) is adjusted such that each byte has even parity. This adjustment ensures that when ha(C) is exclusive-ORed with KK, the variant key KK+h(C) has the same parity as KK. The extension field in ha(C) serves to ensure, for a fixed KK, that the set of keys of the form KK+h(C) consists of three disjoint subsets S1, S2, and S3, where S1 denotes the keys resulting from all 64-bit control vectors, S2 denotes the keys resulting from all 128-bit control vectors, and S3 denotes the key resulting from all control vectors larger than 128 bits. This prevents a form of cheating wherein the CVD algorithm is tricked into decrypting an encrypted key using a false control vector. Hashing algorithm has fulfills two important objectives. First, it handles both short and long control vectors, thus ensuring that a key-management scheme based on the control vector concept is open-ended. Second, the processing overhead to handle short control vectors (64 and 128 bits) is minimized so as to have minimal impact on the key management scheme.
As an alternate embodiment, the length of the input control vector to the hashing algorithm ha can be encoded in the extension field (bits 45,46). If the input control vector is 64 bits long, the field is B`0`, if the input control vector is 128 bits long, the field is set to B`01` and if the input control vector is longer than 128 bits, the field is set to B`10`. This has the advantage of simplifying the hashing algorithm ha so that it does not need to set the extension field in the resulting output H, except if the input control vector was greater than 128 bits.
FIG. 5 is a block diagram illustration of a cryptographic function for calculating a 128-bit modification detecting code (MDC), called the MDC-2 algorithm. Referring to FIG. 5, K1=X`5252525252525252` and L1=X`2525252525252525` are two 64-bit nonsecret constant keys. They are used only to process the first 64-bit block of plaintext, Y1. Thereafter, input value K2, K3, . . . , etc. are based on output values (A1,D1), (A2,D2), . . . , etc., and input values L2, L3, . . . , etc. are based on output values (C1,B1), (C2,B2), . . . , etc. That is, the outputs of each iteration are fed back and used as the keys at the next iteration. The 32-bit swapping function merely replaces 32-bit value B with 32-bit value D and 32-bit value D with 32-bit value B.
In summary, the prior art describes a method for controlling key usage in cryptographic systems based on a symmetric key cryptographic algorithm such as the DEA. Key usage information is stored in a control vector C which is cryptographically coupled with the key K using control vector encryption and control vector decryption algorithms, CVE and CVD, respectively. The CVE and CVD algorithms can handle both short and long control vectors. The only restriction on length is that the control vector must be a multiple of 64 bits. The control vector itself consists of a group of subfields, where each subfield has it own definition and use within the key management to control the processing of the key. Encoding the control vector as a group of independent subfields has many advantages. The processing control vector checking need only concern itself with those subfields that pertain tot he requested key usage. Thus, while the control vector may have many subfields, a particular cryptographic instruction may only need to check the encoded information in a few subfields. This speeds up the control vector checking process. Another important characteristic of the control vector is that the control vector accompanies (either explicitly or implicitly) the key wherever it goes. This is because the correct non-secret control vector must be specified to recover the correct secret key value. Thus, the control vector is available and can be checked at many different places within the cryptographic system: application program, cryptographic software, and cryptographic hardware.
Within a cryptographic system, the CVE and CVD algorithms are implemented so that their operation is transparent to the system. All clear keys are encrypted with the CVE algorithm before the keys are output from the cryptographic hardware. All encrypted keys are decrypted with the CVD algorithm before they are processed within the cryptographic hardware. Even within the cryptographic hardware, these services can be provided transparently from the cryptographic instructions that process keys. By employing a single pair of control vector encryption and decryption functions, most of the complexity associated with key handling can be encoded as information fields within the control vector and within the checking processes themselves, whereas the process of encrypting and decrypting keys and linking control vector information to the key can be handled with one common method.
The present invention provides a method for incorporating control vectors into a key management scheme that uses a public key algorithm. The reader will appreciate that while the advantages of controlling key usage with the control vector are universal in nature, the methods for accomplishing this can vary depending on the attributes of the cryptographic algorithm employed. For example, consider the method of encrypting K with a variant key KK+C to produce eKK+C(K). In this case, K is encrypted using the Data Encryption Algorithm, in which case the Exclusive-OR product of KK and C is always guaranteed to produce a valid DEA key, as DEA keys, ignoring parity bits, are maximally dense in the set of all binary numbers of their magnitude. When the cryptographic algorithm is an asymmetric algorithm such as the RSA algorithm, there are two keys PU and PR. In general, if (PU,PR) is a valid key pair, then (PU+C,PR+C) is not a valid key pair for an arbitrary value C. This is because the PU and PR key values meet certain mathematical constraints and are sparse in the set of all binary numbers of their magnitude. Thus, an alternate method for coupling C to PU and PR is needed. Moreover, encrypting one key with another can sometimes be cumbersome, e.g., when an the RSA algorithm is employed it is cumbersome to encrypt a key of one modulus value with a key of another modulus value if the value of the first modulus is greater than the value of the second modulus. This cumbersome situation must be dealt with in the underlying design so that a general methodology is achieved. The present invention will show how this is accomplished. In hybrid cryptographic systems where both a symmetric and asymmetric algorithm are implemented, the public and private keys belonging to the asymmetric algorithm can be encrypted with keys belonging to the symmetric key algorithm. In that case, the method for coupling a key and control vector can be similar to that described in the prior art. However, even here there are subtle differences that affect the design choice. For example, the public and private keys belonging to the asymmetric key algorithm are typically longer than the keys belonging to the symmetric key algorithm. Also, the possibility that the public and private keys will be of different and varying lengths must be addressed. 512-bit RSA keys are not uncommon, where a DEA master key is generally 128 bits. Thus, the CVE and CVD algorithms must be adjusted to permit long asymmetric keys to be encrypted with shorter (e.g., 128-bit) symmetric keys. Another difference is that, in theory, the public keys need not be encrypted when stored in a cryptographic key data set. However, there are advantages to handling both the public and private keys similarly. As examples, the same method for coupling the control vector and the private key can be used to couple the control vector and the public key, and the same method of authenticating the key value can be used. Also, handling the public and private keys in the same way means that all keys are handled and processed just one way, which reduces the complexity of the key management design. That is, as the private key must be encrypted to ensure that its value does not become known, the public key may also be encrypted to simplify the internal key management design, as then the key (whether public or private) will always be decrypted before being processed further.
When a public key algorithm is employed, the key lengths or key sizes are not fixed by the algorithm as with the DEA. In this case, the cryptographic system will most likely have to operate with public and private keys of different lengths, varying as much as several hundred bits. Therefore, the CVE and CVD algorithms must be designed to handle public and private keys with varying lengths. It is also important that the length of the key be made transparent from the application and the cryptographic system using the key.
In cryptographic systems based on the DEA, many cryptographic instructions that handle bulk data must be streamlined so that performance is not degraded by the introduction of the control vector and the encryption and decryption algorithms (CVE and CVD). However, when a public key (PK) algorithm is employed, the individual steps of encryption and decryption are orders of magnitude slower than encryption and decryption with the DEA. Thus, the design of a key management scheme based on a PK algorithm can have different underlying objectives. For example, key processing and key handling operations that introduce unwarranted processing overhead in a DEA-based key management, may indeed be appropriate for a PK-based key management. This is because the processing overhead while large compared to one DEA encryption may be insignificant compared to one PK encryption. In the present invention, a strategy is pursued of authenticating a key dynamically within the cryptographic hardware as part of the CVD algorithm. Relatively speaking, while this introduces significant processing overhead in a DEA-based key management scheme, it adds very little processing overhead in a PK-based key management scheme. However, this ensures that valid and strong PR and PU keys are used, and that an invalid (i.e., insecure) key value is not inadvertently used.
OBJECTS OF THE INVENTION
It is therefore an object of the invention to provide an improved method for controlling the usage of public and private keys.
It is another object of the invention to permit large amounts of control information for the public and private keys.
It is another object of the invention to permit the application, the system software, and the system hardware to check and set portions of the control information.
It is another object of the invention to permit keys to be authenticated within the crypto hardware as part of the key recovery process, so that all keys are authenticated before they are used by the crypto hardware.
It is another object of the invention to permit an open-ended design allowing new and expanded key usage to be added to the architecture.
It is another object of the invention to provide a single consistent method for handling both public and private keys.
It is another object of the invention to allow the physical makeup of the keys to appear transparent.
It is another object of the invention to allow users to port their public and private keys from one cryptographic system to another.
It is another object of the invention to base control vector encrypt and decrypt on a DEA master key of 128 bits.
It is another object of the invention to provide a general method for control vector encrypt and decrypt where the system master key is a private and public key pair of a commutative asymmetric cryptographic algorithm (i.e., no DEA or other symmetric algorithm master key is used).
It is another object of the invention to provide a general method for control vector encrypt and decrypt where the system master key is a quadruple of two key pairs of private and public keys of a non-commutative asymmetric cryptographic algorithm. Specifically the system master key quadruple consists of (1) a PU1 master key used to encrypt the public and private keys kept outside the cryptographic facility, (2) a PR1 master key used to decrypt the public and private keys kept outside the cryptographic facility, (3) a PR2 master key used to generate an authentication signature for the public and private keys kept outside the cryptographic facility, and (4) a PU2 master key used to verify the authentication signature of the public and private keys kept outside the cryptographic facility.
It is another object of the invention to provide a general method for control vector encrypt and decrypt where the system master key is a quadruple of one key pair of private and public keys using public key algorithm 1 and another key pair of private and public keys using public key algorithm 2. Specifically the system master key quadruple consists of (1) a PU1 master key (based on public key algorithm 1) used to encrypt the public and private keys kept outside the cryptographic facility, (2) a PR1 master key (using public key algorithm 1) used to decrypt the public and private keys kept outside the cryptographic facility, (3) a PR2 master key (using public key algorithm 2) used to generate an authentication signature for the public and private keys kept outside the cryptographic facility, and (4) a PU2 master key (using public key algorithm 2) used to verify the authentication signature for the public and private keys kept outside the cryptographic facility.
SUMMARY OF THE INVENTION
These and other objects, features, and advantages are accomplished by the invention disclosed herein.
The invention describes a method for encrypting the public and private keys of a cryptographic asymmetric key (public key) algorithm, when these keys are stored outside the secure boundary of the cryptographic facility (i.e., cryptographic hardware) and for decrypting these keys when they are processed or used within the secure boundary of the cryptographic facility. The so-produced encrypted keys may be kept in a cryptographic key data set belonging to the cryptographic system software or they may be managed by the cryptographic application programs that use the keys. The public and private keys are encrypted by a system master key stored in clear form within the secure boundary of the cryptographic facility. In situations where the cryptographic system implements a symmetric key algorithm in addition to the asymmetric key algorithm the system master key can be a symmetric key. For example, if the cryptographic system implements both DEA and RSA algorithms, then the RSA public and private keys are protected with a 128-bit DEA master key.
In situations where the cryptographic system implements a commutative asymmetric key algorithm (such as the RSA algorithm), the system master key consists of a special public and private key pair (PU0,PR0) stored in clear form within the cryptographic facility. A commutative asymmetric key algorithm in one where the operation of encryption followed by decryption is equal to the operation of decryption followed by encryption in that both result in the original plaintext. The master public key PU0 is used to encrypt and verify authenticity for public and private keys stored outside the cryptographic facility and the master private key PR0 is used to decrypt and generate authentication signatures on the public and private keys stored outside the cryptographic facility. In addition to providing a means to encrypt and decrypt the public and private keys stored outside the cryptographic facility, the invention also provides a means to cryptographically couple the control vector with the public and private keys and to authenticate the public and private keys using a special authenticator produced within the cryptographic facility.
In situations where the cryptographic system implements only a non-commutative asymmetric key algorithm, the system master key may consist of a special quadruple composed of a two public and private key paris ((PU1,PR1),(PU2,PR2)) stored in clear form within the cryptographic facility. A non-commutative asymmetric key algorithm is one where encryption must always be done before decryption. Master public key PU1 is used to encrypt public and private keys stored outside the cryptographic facility and master private keys PR1 is used to decrypt public and private keys stored outside the cryptographic facility. Master public key PU2 is used to verify the authenticity of and private keys stored outside the cryptographic facility and master private key PR2 is used to generate authentication signatures for the public and private keys stored outside the cryptographic facility.
In situations where the cryptographic system implements two different asymmetric algorithms, where one algorithm is used for key encryption/decryption and another (different) algorithm is used for authentication, the system master key consists of a special quadruple composed of a two public and private key pairs ((PU1,PR1),(PU2,PR2)) stored in clear form within the cryptographic facility. (PU1,PR1) comprise an asymmetric key pair from a first public key algorithm and (PU2,PR2) comprise an asymmetric key pair from a second public key algorithm, which is different from the first algorithm. Master public key PU1 is used to encrypt public and private keys stored outside the cryptographic facility and master private key PR1 is used to decrypt public and private keys stored outside the cryptographic facility. Master public key PU2 is used to verify the authenticity of public and private keys stored outside the cryptographic facility and master private key PR2 is used to generate authentication signatures for the public and private keys stored outside the cryptographic facility.
Note also, as an alternate embodiment, if the public key algorithm is not commutative, if both the public key and the private keys that are used as the master key pair are kept secret, then only one master key pair is needed. In this case, the (secret) public key is used to encrypt the authentication record and the private key is used to decrypt it. Normally this would represent a security exposure, but as the public key is secret and known only inside the cryptographic facility, there is no exposure. Care must be taken to ensure that the (secret) public key is never inadvertently exposed.
FIG. 6 illustrates a cryptographic facility 30 containing a commutative asymmetric algorithm master key. In this case, the public and private keys stored outside the cryptographic facility 30 are protected (i.e., encrypted for privacy and authenticated) with an asymmetric master key pair, designated (PU0,PR0). Outside the cryptographic facility 30, all public and private keys are stored in key tokens. Public keys are stored in public key tokens (PU key tokens) and private keys are stored in private key tokens (PR key tokens). The PU Key tokens and PR key tokens are stored in a cryptographic key data set 32 managed by the cryptographic system software, or they may be managed by the cryptographic application programs themselves (not shown in FIG. 6).
FIG. 7 illustrates a cryptographic facility 30 containing an asymmetric key algorithm and a symmetric key algorithm. In this case, the public and private keys stored outside the cryptographic facility 30 are protected with a symmetric system master key, designated KM. If the symmetric key algorithm is the DEA, then KM is a 128-bit key, as described in the prior art. As in FIG. 6, the public and private keys are stored in PU key tokens and PR key tokens. The PU key tokens and PR key tokens are stored in a cryptographic key data set 32 managed by the cryptographic system software, or they may be managed by the cryptographic application programs themselves (not shown in FIG. 7).
The reader will appreciate from the full description of the invention, provided below that, except for the special functions that encrypt and decrypt the keys in the key tokens, the means for protecting keys based on any of the following methods:
(1) a symmetric system master key (KM),
(2) a commutative asymmetric system master key pair (PU0,PR0),
(3) a non-commutative asymmetric master key pair (PU0,PR0) where both the public and private key are kept secret,
(4) a non-commutative asymmetric master key quadruple ((PU1,PR1),(PU2,PR2)), or
(5) a master key quadruple ((PU1,PR1),(PU2,PR2)) when the first key pair uses one public key algorithm for key encryption/decryption and the second key pair uses another public key algorithm different from the first for authentication
can be made transparent to the user of a cryptographic system. Thus, the cryptographic instructions that process and use the public and private keys and the cryptographic software and cryptographic application programs that handle the public and private key tokens are unaffected by the particular encryption and decryption means for storage and recovery of the public and private keys. This is so because the keys are treated as logical entities. Their physical characteristics such as length, format, component make up, etc., are kept transparent to the cryptographic system. This is partially accomplished through the use of special records called the public key record (PU key record) and private key record (PR key record) which may have varying length, as the keys they contain may have varying length. All public and private keys generated within the cryptographic system are stored in these varying-length key records. As an alternate embodiment, the key records may be set to a fixed size that will contain the largest size public and private keys that will be generated and/or used on the system.
FIG. 8 illustrates the production of public and private keys using a public key key generation algorithm (KGA) 152. In response to a request to generate a (PU,PR) key pair, public key generation algorithm 152 causes a (PU,PR) key pair to be generated. The generated public key PU is stored in a PU key record and the generated private key PR is stored in PR key record. The PU key record and PR key record are returned as outputs. In addition to returning the PU key record and PR key record, the public key generation algorithm 152 may also optionally return a PU.sub.-- length parameter indicating the length of PU key record and a PR.sub.-- length parameter indicating the length of PR key record. The optional length parameters may be useful in implementations where the lengths of PU key record and PR key record may vary.
FIG. 9 illustrates the formats of the PU key record and PR key record. The PU key record contains parse data that permits the public key to be recovered from the record. The parse data may be length and displacement data of fields in the record. The PU key record also contains control information that may be useful in describing the record type and type of key or keys stored within the record. The PU key record also permits one or more public keys to be stored as a single logical public key. This may be particularly useful in situations where a first public key algorithm is used for DEA key encryption/decryption purposes, e.g., to distribute DEA keys from one device to another, and a second public key algorithm is used for generating and verifying digital signatures. Thus, a first public key PU1 is used to encrypt DEA keys and a second public key PU2 is used verify digital signatures. In such situations, the cryptographic system is designed in such a way that the key processing operations will know from the context of the operations being performed whether the public key to be used is PU1 or PU2. The PR key record also contains parse data that permits the private key to be recovered from the record. The PR key record also contains control information that may be useful in describing the record type and type of key or keys stored within the record. The PR key record also permits one or more private keys to be stored as a single logical private key. Thus, a first private key PR1 is used to decrypt a DEA key encrypted by the first public key PU1, and a second private key PR2 is used to generate digital signatures for later verification by the second public key PU2. In such situations, the cryptographic system is designed in such a way that the key processing operations will know from the context of the operations being performed whether the private key to be used is PR1 or PR2. The PU and PR key records keep algorithm specific and key specific information transparent to the cryptographic system. Only the public key algorithm itself that processes the key records need be aware of the internal structure and makeup of these key records.
As an alternate embodiment, in certain situations, there may be advantages to maintaining the logical key records in two forms: the first containing both the private keys and public keys for the owner or creator of the keys and the second containing just the public keys for distribution to others. As before, if using the owner's logical key record containing both private and public keys, the correct key to use can be determined from context.
FIG. 10 illustrates the production of public and private key pairs using a Generate Public and Private Key Pair (GPUPR) instruction. The GPUPR instruction is described in detail in co-pending patent application by S. M. Matyas, et al. entitled "Generating Public and Private Key Paris Using a Passphrase", as cited in the background art. Referring now to FIG. 10, the GPUPR instruction 52 is contained in an instruction processor 142 within the cryptographic facility (CF) 30. In practice, the CF 30 is implemented within secure hardware, so that keys and cryptographic variables stored within the CF 30 are protected, i.e., both the secrecy and integrity of these keys and cryptographic variables are protected. The CF 30 also contains a CF environment memory 146 for the storage if keys and cryptographic variables such as a master key 15. FIG. 10 does not specify whether the master key is (1) a symmetric master key KM, (2) an asymmetric commutative master key pair (PU0,PR0), (3) a non-commutative asymmetric master key pair (PU0,PR0) where both the public and private keys are kept secret, (4) an asymmetric non-commutative master key quadruple ((PU1,PR1),(PU2,PR2)), or ( 5) an asymmetric two-PK-algorithm master key quadruple ((PU1,PR1),(PU2,PR2)) where the first pair uses one public key algorithm and the second pair uses a different public key algorithm from the first. The CF 30 also contains cryptographic algorithms 144, which includes an asymmetric key algorithm 10, an optional symmetric key algorithm 11, and an asymmetric key key generation algorithm (KGA) 152. The inputs to the GPUPR instruction at 50 consist of a mode, an optional code word, PU control vector, and PR control vector. In response to a request to execute the GPUPR instruction 50, the GPUPR instruction invokes the KGA 152, at 53, passing the mode and optional code word. The mode indicates to KGA 152 whether the to-be-generated public and private key pair (PU,PR) are generated from a code word (mode=`PP`) or not (mode=`no.sub.-- PP`). In response the KGA 152 produces a public and private key pair (PU,PR) which are formatted in a PU key record and PR key record. The PU key record and PR key record are returned to the GPUPR instruction at 54. In response, the GPUPR instruction builds a PU key token and a PR key token containing the encrypted PU key record and encrypted PR key record, respectively. Each key token contains a control vector and an authenticator, as further described below. The GPUPR instruction 52 also performs consistency checking on the mode and control vector supplied as inputs at 50, see also co-pending patent application by S. M. Matyas, et al. entitled "Generating Public and Private Key Pairs Using a Passphrase," cited in the background art, for a further discussion of this consistency checking. The so-produced PU key token and PR key token are returned as outputs at 51.
FIG. 11 illustrates the formats of the PU key token and PR key token. The PU key token consists of a header, a PU control vector, an encrypted PU key record, and a PU authenticator. As an alternate embodiment, the PU key token may consist of a header, a PU control vector, a plaintext PU key record, and a PU authenticator. The preferred embodiment has an encrypted PU key record in the PU key token as the PR key token must contain an encrypted PR key record (to maintain its secrecy) and doing both PU and PR key tokens in the same manner simplifies the processing. The PR key token consists of a header, a PR control vector, an encrypted PR key record, and a PR authenticator. The header in the PU key token consists of information (e.g., offsets or displacements to start of fields, offsets or displacements to end of fields, and/or lengths of fields) that enable the system to determine the start and end of each other field in the PU key token. The PU control vector consists of a PU key type, PU key usage data, PR key usage data (for history purposes), algorithm identifier, algorithm-specific data, key start date/time, key expiration data/time, device identifier, user identifier, key identifier, logical device identifier, and user-defined data. The fields of PU control vectors are presented in more detail under "Description of the Best Mode for Carrying Out the Invention." If the system master key is a symmetric key KM, then PU key record is encrypted with a variant key derived from KM, as explained below. If the system master key is an asymmetric key pair (PU0,PR0), then PU key record is encrypted with PU0, as explained below. The PU authenticator is a special authentication code produced at the time the PU key token is constructed. Later, when the PU key token is specified as a parameter input to a cryptographic instruction, the PU authenticator is used to validate the public key as part of key recovery, before the recovered PU is processed within the cryptographic instruction.
The header in the PR key token consists of information (e.g., offsets or displacements to start of fields, offsets or displacements to end of fields, and/or lengths of fields) that enable the system to determine the start and end of each other field in the PR key token. The PR control vector consists of a PR key type, PR key usage data, PU key usage data (for history purposes), algorithm identifier, algorithm-specific data, key start date/time, key expiration data/time, device identifier, user identifier, key identifier, logical device identifier, and user-defined data. The fields of PR control vectors are presented in more detail under "Description of the Best Mode for Carrying Out the Invention." If the system master key is a symmetric key KM, then PR key record is encrypted with a variant key derived from KM, as explained below. If the system master key is an asymmetric key pair (PU0,PR0), then the PR key record is encrypted with PU0, as explained below. The PR authenticator is a special authentication code produced at the time the PR key token is constructed. Later, when the PR key token is specified as a parameter input to a cryptographic instruction, the PR authenticator is used to validate the public key as part of key recovery, before the recovered PR is processed within the cryptographic instruction.
In co-pending patent application by S. M. Matyas, et al. entitled "Generating Public and Private Key Pairs Using a Passphrase", cited in the background art, the outputs of key generator algorithm 152 are the generated public and private key, PU and PR. Actually, the outputs are a PU key record and a PR key record, containing the generated PU and PR, respectively, as defined here. Those skilled in the art will appreciate that the description of the GPUPR instruction and the key generation algorithm in co-pending patent application by S. M. Matyas, et al. entitled "Generating Public and Private Key Pairs Using a Passphrase", is for all intents and purposes the same as the description provided here, and that returning PU and PR as outputs from the key generation algorithm 152, instead of return PU and PR key records does not depend from the underlying invention.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other objects, features, and advantages of the invention will be more fully appreciated with reference to the accompanying figures.
FIG. 1 is a block diagram illustration of the process to encrypting keys and decrypting keys in a DEA-based cryptographic system using the control vector encrypt (CVE) and control vector decrypt (CVD) algorithms.
FIG. 2 is a block diagram illustration of the CVE algorithm implemented in a DEA-based cryptographic system.
FIG. 3 is a block diagram illustration of the CVD algorithm implemented in a DEA-based cryptographic system.
FIG. 4 is a block diagram illustration of the hashing algorithm ha implemented in the CVE and CVD algorithms of FIGS. 1, 2, and 3.
FIG. 5 is a block diagram illustration of the MDC-2 algorithm.
FIG. 6 is a block diagram illustration of a first embodiment of the invention wherein the generated public and private keys stored outside the cryptographic facility are protected with a commutative asymmetric system master key pair (PU0,PR0).
FIG. 7 is a block diagram illustration of a second embodiment of the invention wherein the generated public and private keys stored outside the cryptographic facility are protected with a symmetric system master key KM.
FIG. 8 is a block diagram illustration of a public key key generation algorithm (KGA).
FIG. 9 illustrates the formats of the PU key record and PR key record.
FIG. 10 is a block diagram illustration of the GPUPR instruction.
FIG. 11 illustrates the formats of the PU key token and the PR key token.
FIG. 12 illustrates a communications network 10 including a plurality of data processors, each of which includes a cryptographic system.
FIG. 13 is a block diagram of a cryptographic system 22.
FIG. 14 is a block diagram of a cryptographic facility 30.
FIG. 15 is a block diagram illustration of the cryptographic algorithms 144 component of the cryptographic facility 30 containing the key record encrypt and key record decrypt algorithms.
FIG. 16 is a flow diagram of a first embodiment of key record encrypt algorithm 12.
FIG. 17 is a flow diagram of a first embodiment of key record decrypt algorithm 13.
FIG. 18 is a flow diagram of a second embodiment of key record encrypt algorithm 12.
FIG. 19 is a flow diagram of a second embodiment of key record decrypt algorithm 13.
FIG. 20 is a functional block diagram illustrating the recovery of two private keys and their use in two public key algorithms to fulfill two different cryptographic service requests.
FIG. 21 is a block diagram showing the production of an internal key token from a key record and the production of an external key token from a key record.
FIG. 22 is a block diagram showing the production of an internal key token from an internal key unit produced from a key record and the production of an external key token from an external key unit produced from a key record.
FIG. 23 lists the components of the Instruction Processor 142.
FIG. 24 shows the elements of the Configuration Table in the CF Environment Memory 146.
FIG. 25 shows the main elements of the Cryptographic Algorithms 144.
FIG. 26 is a block diagram illustration of the components of the CF Environment.
FIG. 27 shows the instructions controlled by the DEFINE, AUTH CONTROL, AUTH, and ENABLE fields in the Configuration Vector.
FIG. 28 is a block diagram illustration of the MDC Table.
FIG. 29 is a block diagram illustration of the Counter Table.
FIG. 30 illustrates the control vector hierarchy of PKCD keys.
FIG. 31 is a block diagram illustration of the fields in a control vector associated with a private authentication key.
FIG. 32 is a block diagram illustration of the fields in a control vector associated with a private certification key.
FIG. 33 is a block diagram illustration of the fields in a control vector associated with a private key management key.
FIG. 34 is a block diagram illustration of the fields in a control vector associated with a private user key.
FIG. 35 is a block diagram illustration of the fields in a control vector associated with a public authentication key.
FIG. 36 is a block diagram illustration of the fields in a control vector associated with a public certification key.
FIG. 37 is a block diagram illustration of the fields in a control vector associated with a public key management key.
FIG. 38 is a block diagram illustration of the fields in a control vector associated with a public user key.
FIG. 39 is a block diagram illustration of the fields in a has vector.
DESCRIPTION OF THE BEST MODE FOR CARRYING OUT THE INVENTION
Environment Description
FIG. 12 illustrates a network block diagram showing a communications network 10 to which is connected a plurality of data processors including data processor 20, data processor 20', and data processor 20". Also included in each data processor is a cryptographic system, as shown in FIG. 12. Data processor 20 includes cryptographic system 22, data processor 20' includes cryptographic system 22' and data processor 20" includes cryptographic system 22". Each data processor supports the processing of one or more applications which require access to cryptographic services such as for the encryption, decryption and authenticating of application data and the generation and installation of cryptographic keys. The cryptographic services are provided by a secure cryptographic facility in each cryptographic system. The network provides the means for the data processors to send and receive encrypted data and keys. Various protocols, that is, formats and procedural rules, govern the exchange of cryptographic quantities between communicating data processors in order to ensure the interoperability between them.
FIG. 13 illustrates the cryptographic system 22. In the cryptographic system 22, the cryptographic facility (CF) 30 has an input 37 from a physical interface. The cryptographic facility access program (CFAP) 34 is coupled to the cryptographic facility 30 by means of the interface 31. The cryptographic key data set (CKDS) 32 is connected to the cryptographic facility access program 34 by means of the interface 33. The application programs (APPL) 36 are connected to the cryptographic facility access program 34 by means of the interface 35.
A typical request for cryptographic service is initiated by APPL 36 via a function call to the CFAP 34 at the interface 35. The service request includes key and data parameters, as well as key identifiers which the CFAP 34 uses to access encrypted keys from the CKDS 32 at the interface 33. The CFAP 34 processes the service request by issuing one or more cryptographic access instructions to the CF 30 at the interface 31. The CF 30 may also have an optional physical interface 37 for direct entry of cryptographic variables into the CF 30. Each cryptographic access instruction invoked at the interface 31 has a set of input parameters processed by the CF 30 to produce a set of output parameters returned by the CF 30 to the CFAP 34. In turn, the CFAP 34 may return output parameters to the APPL 36. The CFAP 34 may also use the output parameters and input parameters to subsequently invoke instructions. If the output parameters contain encrypted keys, then the CFAP 34, in many cases, may store these encrypted keys in the CKDS 32.
FIG. 14 illustrates the cryptographic facility 30. The cryptographic facility 30 is maintained within a secure boundary 140. The cryptographic facility 30 includes the instruction processor 142 which is coupled to the cryptographic algorithms 144 which are embodied as executable code. The cryptographic facility environment memory 146 is coupled to the instruction processor 142. The physical interface can be coupled over line 37 to the CF environment memory 146, as shown in the figure. The instruction processor 142 is coupled to the cryptographic facility access program (CFAP) 34 by means of the interface at 31.
The instruction processor 142 is a functional element which executes cryptographic microinstructions invoked by the CFAP access instruction at the interface 31. For each access instruction, the interface 31 first defines an instruction mnemonic or operation code used to select particular microinstructions for execution. Secondly a set of input parameters is passed from the CFAP 34 to the CF 30. Thirdly, a set of output parameters is returned by the CF 30 to the CFAP 34. The instruction processor 142 executes the selected instruction by performing an instruction specific sequence of cryptographic processing steps embodied as microinstructions stored in cryptographic microinstruction memory 144. The control flow and subsequent output of the cryptographic processing steps depend on the values of the input parameters and the contents of the CF environment memory 146. The CF environment memory 146 consists of a set of cryptographic variables, for example keys, flags, counters, CF configuration information, etc., which are collectively stored within the CF 30. The CF environment variables in memory 146 are initialized via the interface 31, that is by execution of certain CF microinstructions which read input parameters and load them into the CF environment memory 146. Alternatively, initialization can be dome via an optional physical interface which permits cryptographic variables to be loaded directly into the CF environment memory 146, for example via an attached key entry device.
The physical embodiment of the cryptographic facility secure boundary 140, incorporates the following physical security features. The physical embodiment resists probing by an insider adversary who has limited access to the cryptographic facility 30. The term "limited" is measured in minutes or hours as opposed to days or weeks. The adversary is constrained to a probing attack at the customer's site using limited electronic devices as opposed to a laboratory attack launched at a site under the control of the adversary using sophisticated electronic and mechanical equipment. The physical embodiment also detects attempts at physical probing or intruding, through the use of a variety of electro-mechanical sensing devices. Also, the physical embodiment of the cryptographic facility 30 provides for the zeroization of all internally stored secret cryptographic variables. Such zeroization is done automatically whenever an attempted probing or intrusion has been detected. The physical embodiment also provides a manual facility for a zeroization of internally stored secret cryptographic variables. Reference to the Abraham, et al. patent application cited above, will give an example of how such physical security features can be implemented.
Key Record Encryption/Decryption
FIG. 15 is a block diagram illustration of cryptographic facility 30 incorporating the key record encrypt and key record decrypt algorithms. Cryptographic facility 30 contains an instruction processor 142 consisting of a plurality of cryptographic instructions (not shown in FIG. 15), a CF environment memory 146 containing a master key 15, and cryptographic algorithm 144. Cryptographic algorithms 144 contains an asymmetric key cryptographic algorithm 10, an optional symmetric-key cryptographic algorithm 11, an asymmetric-key key generation algorithm 152, a key record encrypt algorithm 12, and a key record decrypt algorithm 13. Key record encrypt algorithm 12 is a low-level functions used by instruction processor 142 to encrypt a key record (PU key record or PR key record) and produce an encrypted key authenticator record (KAR), which serves to authenticate the key record and associated control vector to the cryptographic facility 30. During key generation (via the GPUPR instruction), the PU and PR key records produced by the asymmetric key key generation algorithm 152 are encrypted and then stored in key tokens constructed by the instruction processor. These key tokens are returned as outputs at 51. The key record encrypt algorithm 12 is invoked by the instruction processor 142 at 14, passing a key record and control vector. In response, key record encrypt algorithm 12 encrypts the key record with master key 15, or a variant key derived from master key 15, as explained below. Key record encrypt algorithm 12 also produces a key authenticator record (KAR) from the key record or from the control vector and key record, again as explained below. The so-produced KAR is then encrypted with master key 15, or a variant key derived from master key 15 (different from the variant key used to encrypt the key record), as explained below. Note that if the KAR was not encrypted, this might represent a security exposure, as the control vector and key record for a public key and the KAR generation algorithm are all assumed to be public knowledge. This would possibly allow substitution of a incorrect public key or incorrect control vector for the correct values, for example, in the cryptographic key data set. While the KAR for a private key may not need to be encrypted for security, in the preferred embodiment, it is encrypted to allow consistent processing of the KAR for both public and private keys. As an alternate embodiment, the KAR for the private key could just be the output of a strong cryptographic one-way function, such as the MDC-2 function described elsewhere. The encrypted key record and encrypted KAR are returned at 16 to the instruction processor 142. Key record decrypt algorithm 13 is a low-level function used by instruction processor 142 to decrypt a key record (PU key record or PR key record) and authenticate the key record and associated control vector to the cryptographic facility 30 before permitting instruction processor 142 to process or use the key in the decrypted key record. Many of the cryptographic instructions executing in the instruction processor 142 make use of cryptographic keys stored in key tokens and supplied as inputs at 50 to the instruction processor 142. Before a key can be processed or used by the instruction processor 142, it must be recovered. During key recovery, the encrypted PU and PR key records contained in the input key tokens (at 50) are decrypted and authenticated. The key record decrypt algorithm 13 is invoked at 17 by the instruction processor 142, passing a key record and control vector as inputs. In response, key record decrypt algorithm 13 decrypts the encrypt key record with master key 15, or a variant key derived from master key 15, as explained below. Key record decrypt algorithm 13 also produces a key authenticator record (KAR) from the recovered key record, or from the control vector and recovered key record, again as explained below. The key record decrypt algorithm 13 then decrypts the encrypted KAR and compares the recovered value of KAR and the generated or produced KAR for equality. If the two values of KAR are equal, the key record decrypt algorithm 13 returns the recovered key record and a return code (e.g., RC=0) indicating that the key record has been successfully authenticated via the KAR. Otherwise, if the two value of KAR are unequal, the key record decrypt algorithm 13 returns only a return code (e.g., RC=1) indicating that the key record has failed to be authenticated via the KAR.
FIG. 16 is a block diagram illustration of a first embodiment of the key record encrypt algorithm 12. The first embodiment of the invention covers the case where the cryptographic system implements both a symmetric key algorithm and an asymmetric key algorithm, and where the master key used to encrypt the key records in the key token stored outside the cryptographic facility is a symmetric key KM. Referring now to FIG. 16, the inputs (a) key record and (b) control vector are read at step 500. Key record is the key record to by encrypted and control vector is key-related data, or data related to the key stored in key record. Control vector is the same control vector stored in the key token, as described in FIG. 11. At step 501, a hash value HASH1 is calculated on the control vector using hash algorithm ha1. For example, when the master key is a 128-bit DEA master key, HASH1 can be a 128-bit MDC calculated with the MDC-2 algorithm of FIG. 5. At step 502, hash vectors H1 and H2 are calculated from HASH1. For example, when the master key is a 128 -bit DEA master key and H1 and H2 are both 128-bit has vectors, the procedures for calculating H1 and H2 is as follows. The 128-bit hash vector H1 is calculated from HASH1 as follows:
1. Set bit 30 of HASH1 equal to B`0`.
2. Set bit 38 of HASH1 equal to B`1`.
3. Set bit 45 . . . 46 of HASH1 equal to B`10`.
4. Set bit 62 of HASH1 equal B`0`.
5. For each byte in HASH1 (bits are numbered b0 through b7), set bit b7 so that bits b0 through b7 have an even number of one bits (i.e., to have even parity).
Bits 30 and 38 are anti-variant bits whose values are set so that the resulting hash vector H is guaranteed to be different from a variant value in which each byte of the variant has the same bit pattern. Bits 45 and 46 are set to B`10` to distinguish H1 from a 64-bit control vector (bits 45 . . . 46 equal to B`00`) and a 128-bit control vector (bits 45 . . . 46 equal to B`01`). In this case, B`10` indicates that H1 has been derived from a "long" control vector whose length exceeds 128 bits. Bit 62 indicates whether the control vector is associated with a key record (B`0`) or a key authenticator record (B`1`). The 128-bit has vector H2 is calculated from H1 as follows:
1. Set H2 equal to H1.
2. Set bit 62 of H2 equal to B`1`.
3. Invert bit 63 of H2 (i.e., the parity bit).
Basically, H2 differs from H1 only in that H1 is associated with a key record (bit 62 equals B`0`) and H2 is associated with a key authenticator record (bit 62 equals B`1`). The parity bit is adjusted to maintain even parity. Otherwise, H1 and H2 are equal. At step 503, variant key KM+H1 is formed as the Exclusive-OR product of master key KM and has vector H1 and variant key KM+H2 is formed as the Exclusive-OR product of master key KM and control vector H2. In the event that the length of KM differs from the length of H1 and H2, H1 and H2 can be Exclusive-ORed with a portion of KM only. Those skilled in the art will recognize that a combining operation other than the Exclusive-OR operation can be performed instead of the Exclusive-OR operation, without departing from the spirit of the invention. When KM is a DEA master key of 128 bits, then the Exclusive-OR operation calculates the Exclusive-OR product of two 128-bit values, which is the straightforward way in which this operation works. At step 504, the key record supplied as input at 50 is encrypted with variant key KM+H1 to produce the encrypted key record value eKM+H1(key record). Again, those skilled in the art will recognize that many different modes of encryption can be used here, since the goal is to protect the secrecy of the key record but not necessarily to pursue one single strategy for providing an encryption capability. For example, if the variant key KM+H1 is a 64-bit DEA key, then the key record can be encrypted using the Cipher Block Chaining (CBC) mode of encryption. If the variant key KM+H1 is a 128-bit DEA key, then key record can be encrypted using a variation on the CBC mode of encryption. In that case, key record is first encrypted with CBC mode using the leftmost 64 bits of KM+H1, the result is next decrypted with CBC mode using the rightmost 64-bits of KM+H1, and finally that result is encrypted with CBC mode using the leftmost 64-bits of KM+H1. An initialization vector (IV) of zero is used throughout the encryption and decryption operations. In each case, inverse decryption operations are employed in the key record decrypt algorithm, discussed below. Those skilled in the art will recognize that encryption methods other than those illustrated here can be used without departing from the spirit of the invention. At step 505, a hash value HASH2 is calculated on key record using hash algorithm ha2. Hash algorithm ha2 may be different from hash algorithm ha1 or it may be the same. For example, hash algorithm ha2 may be the MDC-2 algorithm of FIG. 5 and HASH2 a 128-bit MDC value. The value HASH2 is for practical purposes defined to be the key authenticator record (KAR). However, the KAR may contain additional data besides HASH2. At step 506, KAR is encrypted with variant key KM+H2 t produce the encrypted KAR value eKM+H2(KAR). Again, those skilled in the art will recognize that many different modes of encryption can be used here, since the goal is to protect the integrity of the KAR by making it infeasible for an adversary to substitute an alternate value of KAR of his or her choosing. Since an adversary has no ability to exercise the encryption function using KM+H2, it is not possible to substitute an encrypted KAR value that will authenticate an encrypted key record, except by mere chance. For example, if the variant key KM+H2 is a 64-bit DEA key, then KAR can be encrypted using the Cipher Block Chaining (CBC) mode of encryption. If the variant key KM+H2 is a 128-bit DEA key, then KAR can be encrypted using a variation on the CBC mode of encryption as described above for the encryption of the key record. In each case, inverse decryption operations are employed in the key record decrypt algorithm, discussed below. Those skilled in the art will recognize that encryption methods other than those illustrated here can be used without departing from the spirit of the invention. At step 507, the calculated values (a) eKM+H1(key record) and (b) eKM+H2(KAR) are returned as outputs.
FIG. 17 is block diagram illustration of a first embodiment of the key record decrypt algorithm 13. The first embodiment of the invention covers the case where the cryptographic system implements both a symmetric key algorithm and an asymmetric key algorithm, and where the master key used to encrypt the key records in the key tokens stored outside the cryptographic facility is a symmetric key KM. The key record encrypt algorithm 12 of FIG. 16 and the key record decrypt algorithm 13 of FIG. 17 are inverse algorithms, i.e., key records encrypted with key record encrypt algorithm 12 of FIG. 16 are decrypted with key record decrypt algorithm 13 of FIG. 17. Referring now to FIG. 17, the inputs (a) control vector, (b) eKM+H1(key record), and (c) eKM+H2(KAR) are read at step 510. Control vector is key-related data, or data related to the key stored in key record. Control vector is the same control vector stored in the key token, as described in FIG. 11. eKM+H1(key record) and eKM+H2(KAR) are values produced by the key record encrypt algorithm 12 of FIG. 16. At step 511, a hash value HASH1 is calculated on the control vector using hash algorithm ha1 using the same method as described in step 501 of FIG. 16. At step 512, hash vectors H1 and H2 are calculated from HASH1 using the same method as described in step 502 of FIG. 16. At step 513, variant keys KM+H1 and KM+H2 are calculated from master key KM and hash vectors H1 and H2 using the same method as described in step 503 of FIG. 16. At step 514, the encrypted key record, eKM+H1(key record), supplied as input at 510 is decrypted with variant key KM+H1 to produce the clear value of key record. The method of decryption at step 514 of FIG. 17 is just the inverse operation of encryption at step 504 of FIG. 16. At step 515, a hash value HASH2 is calculated on key record using hash algorithm ha2. Step 515 of FIG. 17 is the same as step 505 of FIG. 16. At step 516, the encrypted KAR, eKM+H2(KAR), supplied as input at 510, is decrypted with variant key KM+H2 to produce the clear value of KAR. The method of decryption at step 516 of FIG. 17 is just the inverse operation of encryption at step 506 of FIG. 16. At step 517, the generated KAR is compared for equality with the decrypted KAR. If equal, then a return code is set equal to "success". If unequal, then a return code is set equal to "failure" and key record is set equal to null (i.e., the recovered key record is erased). At step 518, the values of (a) return code and (b) key record are returned as outputs. If the key record authenticates properly, it is returned as an output at step 518. Otherwise a null value is returned. Those skilled in the art will recognize that there are other ways in which the output values can be returned or not returned. The intent here is for key record decrypt algorithm 13 to return the recovered key record when it authenticates properly and to not return it when it does not authenticate properly. The return code could be omitted from the design, if desired, provided that a protocol is adopted wherein the key record has a special reserved value, say zero, to indicate a failure condition (a nonzero value indicates success).
FIG. 18 is block diagram illustration of a second embodiment of the key record encrypt algorithm 12. The second embodiment of the invention covers the case where the cryptographic system implements an commutative asymmetric key algorithm, and where the master key is an asymmetric key pair (PU0,PR0). Master public key PU0 is used to encrypt key records and to verify digital signatures. Master private key PR0 is used to decrypt key records and to generate digital signatures. Referring now to FIG. 18, the inputs (a) key record and (b) control vector are read at step 520. Key record is the key record to be encrypted and control vector is key-related data, or data related to the key stored in key record. Control vector is the same control vector stored in the key token, as described in FIG. 11. At step 521, the key record supplied as input at 520 is encrypted with public master key PU0 to produce the encrypted key record value ePU0(key record). Since the length of key record may be greater than the block size (or modulus size) of the asymmetric key algorithm, an encryption means must be employed to handle "long" key records. One approach is to use a means similar to Cipher Block Chaining (CBC) mode, as defined for the DEA. In this case, key record is divided into blocks whose length is such that each block can be encrypted with the asymmetric key algorithm. After each step of encryption, the so-produced ciphertext block is Exclusive-ORed with the next block of input plaintext in key record. Those skilled in the art will appreciate that there are many ways in which the encryption with PU0 can be performed and that these various alternate means do not depart from the spirit of the invention. At step 522 control vector and key record are concatenated to form an intermediate value called HA-IN. At step 523, a hash value HASH2 is calculated on HA-IN using hash algorithm ha2. For example, hash algorithm ha2 may be the MDC-2 algorithm of FIG. 5 and HASH2 a 128-bit MDC value. The value HASH2 is for practical purposes defined to be the key authenticator record (KAR). However, the KAR may contain additional data besides HASH2. At step 524, KAR is decrypted with private master key PR0 to produce dPR0(KAR). In public key cryptography, the ciphertext dPR0(KAR) is called a digital signature. In this case, dPR0(KAR) is a digital signature on HA-IN (the concatenation of control vector and key record). At step 525, the calculated values (a) ePU0(key record) and (b) dPR0(KAR) are returned as outputs.
FIG. 19 is a block diagram illustration of a second embodiment of the key record decrypt algorithm 13. The second embodiment of the invention covers the case where the cryptographic system implements a commutative asymmetric key algorithm, and where the master key is an asymmetric key pair (PU0,PR0). Master public key PU0 is used to encrypt key records and to verify digital signatures. Master private key PR0 is used to decrypt key records and to generate digital signatures. The key record encrypt algorithm 12 of FIG. 18 and the key record decrypt algorithm 13 of FIG. 19 are inverse algorithms, i.e., key records encrypted with key record encrypt algorithm 12 of FIG. 18 are decrypted with key record decrypt algorithm 13 of FIG. 19. Referring now to FIG. 19, the inputs (a) control vector, (b) ePU0(key record), and (c) dPR0(KAR) are read at step 530. Control vector is key-related data, or data related to the key stored in key record. Control vector is the same control vector stored in the key token, as described in FIG. 11. ePU0(key record) and dPR0(KAR) are values produced by the key record encrypt algorithm 12 of FIG. 18. At step 531, the encrypted key record, ePU0(key record), supplied as input at 530 is decrypted with private master key PR0 to produce a clear key record. The step of decryption is just the inverse operation of encryption performed at step 521 of FIG. 18. At step 532, control vector supplied as input at 530 and key record recovered at 531 are concatenated to form an intermediate value called HA-IN. Step 532 is just the same as step 522 in FIG. 18. At step 533, a hash value HASH2 is calculated on HA-IN using hash algorithm ha2. The value HASH2 is for practical purposes defined to be the key authenticator record (KAR). However, the KAR may contain additional data besides HASH2. Step 533 is just the same as step 523 in FIG. 18. At step 534, the decrypted KAR, dPR0(KAR), is encrypted with public master key PU0 to produce a clear value of KAR (called the recovered KAR). Note that this is the step that requires the asymmetric key algorithm be commutative. At step 535, the generated KAR is compared for equality with the recovered KAR. If equal, than a return code is set equal to "success". If unequal, then a return code is set equal to "failure" and key record is set equal to null (i.e., the recovered key record is erased). At step 536, the values of (a) return code and (b) key record are returned as outputs. If the key record authenticates properly, it is returned as an output at step 536. Otherwise a null value is returned. Those skilled in the art will recognize that there are other ways in which the output values can be returned or not returned. The intent here is for key record decrypt algorithm 13 to return the recovered key record when it authenticates properly and to not return it when it does not authenticate properly. The return code could be omitted from the design, if desired, provided that a protocol is adopted wherein the key record has a special reserved value, say zero, to indicate a failure condition (a nonzero value indicating success).
Those skilled in the art will recognize that step 521 in FIG. 18 could make use of a decryption operation using the public master key PU0 and step 531 of FIG. 19 could likewise make use of an encryption operation using the private master key PR0. In like master, step 524 in FIG. 18 could make use of an encrypt operation using private master key PR0 and step 534 of FIG. 19 could make use of a decrypt operation using public master key PU0, as long as both the public key PU0 and private key PR0 remain secret. In fact, the choice of encrypt or decrypt at step 521 of FIG. 18 is independent of the choice of encrypt or decrypt at step 524 of FIG. 18, so that alternate embodiments of the invention can make use of these alternate schemes of encryption versus decryption or decryption versus encryption. And those skilled in the art will recognize that these alternate embodiments do not depart from the spirit of the invention.
Those skilled in the art will also recognize that the key record encrypt algorithm 12 of FIG. 18 and the key record decrypt algorithm 13 of FIG. 19 could make use of a symmetric master key KM instead of a public and private master key (PU0,PR0). In that case, all operations performed with PU0 and PR0 are instead performed with KM. In an alternate approach, variant keys KM1 and KM2 (not equal to KM1) can be used as the master key. In this case, KM1 is used in place of PU0 and KM2 is used in place of PR0. This provides a form of cryptographic separation between the encryption and authentication components of the design. Thus, encryption of the key record is performed with KM1 and encryption of the KAR is performed with KM2. Those skilled in the art will appreciate that these alternate embodiments do not depart from the spirit of the invention.
FIG. 20 shows a functional block diagram of the cryptographic facility 30, for recovering a plurality of public and/or private keys from a key token for use in a plurality of public key algorithm, in response to a plurality of diverse cryptographic service requests. In particular, FIG. 20 depicts how two private keys, PR1 and PR2 can be recovered from a key token accessed from the cryptographic key data set CKDS 32 for use in two different public key algorithms, to fulfill two different cryptographic service requests. The first request R1 is to import the encrypted DEA key ePU1(key1), which was encrypted under a first public key PU1, and decrypt the key under the corresponding private key PR1 to obtain key1, using a first public key algorithm A1. The second request R2 is to generate a digital signature from Data2 under a second private key PR2, using a second public key algorithm A2.
The key token is input from the CKDS on line 50 to the key token register 700, with the header portion in the component register 704 and the concatenated control vector CV, encrypted key record eKM+H1(parse,Ct1,PR1,PR2) and encrypted key authentication record eKM+H2(KAR) in the component register 702. The header in register 704 defines the beginning and ending of the control vector, the encrypted key record and the encrypted key authentication record in register 702. The header register 704 output is connected to a control input of the multiplexor 706, which separates the control vector for output over line 17 to the control vector register 708, which separates the encrypted key record for output to the encrypted key record register 710 and which separates the encrypted key authentication record for output to the encrypted key authentication register 712.
The control vector checker 714 receives the control vector CV from the register 708. If the Import DEA Key request R1 is the cryptographic service request which has been made, then the control vector checker receives R1 and performs the checking operations on CV to ensure that the key record contains a key which is permitted to be applied to this use. If CV satisfies the control vector checker 714, then an enabling signal "ok" is sent to the gate 716, whose data input is connected to the output of the control vector register 708, passing CV to the control vector input of the key record decrypt algorithm 718 and 720. If CV fails to pass the checks by the control vector checker 714, then the process is aborted.
Alternately, if the Generate Digital Signature request R2 is the cryptographic service request which has been made, then the control vector checker receives R2 and performs the checking operations on CV to ensure that the key record contains a key which is permitted to be applied to this use. If CV satisfies the control vector checker 714, then an enabling signal "ok" is sent to the gate 716, whose data input is connected to the output of the control vector register 708, passing CV to the control vector input of the key record decrypt algorithm 718 and 720. If CV fails to pass these checks by the control vector checker 714, then the process is aborted.
The key record decrypt algorithm 13 in the flow diagram of FIG. 17 is executed by the functional blocks 718, 720, 722, 724, and 726 of FIG. 20. Two functional blocks, 718 and 720, are arranged in parallel and are labeled "Key Record Decrypt Algorithm", in FIG. 20, to provide a clear description of the decryption operations on the encrypted key record and on the encrypted key authentication record. However, in the preferred embodiment of the invention, the two functional blocks 718 and 720 would be combined into a single Key Record Decrypt Algorithm which would operate sequentially on the encrypted key record and on the encrypted key authentication record. Doing so enables second hash vector H2 to be produced from first hash vector H1 by changing only a single bit in H1. The key record decrypt algorithm 718 receives CV and performs the hashing operation described in steps 511 and 512 of FIG. 17, producing the hash vector H1. The master key KM is input from register 15 and the exclusive OR product with H1 is formed, yielding the variant key KM+H1, as described in step 513 of FIG. 17. The second key record decrypt algorithm 720 receives CV and performs the hashing operation described in steps 511 and 512 of FIG. 17, producing the second hash vector H2. The master key KM is input from register 15 and the exclusive OR product with H2 is formed, yielding the second variant key KM+H2, as described in step 513 of FIG. 17. The first key record decrypt algorithm 718 then uses the variant key KM+H1 to decrypt the encrypted key record, as described in step 514 of FIG. 17, yielding the key record (parse,Ct1,PR1,PR2). The key record from key record decrypt algorithm 718 is input to the hash algorithm 724, to produce the computed key authentication record (KAR), as described in step 515 of FIG. 17. Then the computed key authentication record (KAR) is input to a first side of the comparator 726. The second key record decrypt algorithm 720 uses the variant key KM+H2 to decrypt the encrypted key authentication record, as described in step 516 of FIG. 17, yielding the key authentication record KAR. Then the key authentication record KAR is input to a second side of the comparator 726. If the comparator 726 determines that the computed (KAR) is equal to the decrypted KAR, then an enabling signal "yes" is output to a control input of the gate 722, to pass the key record (parse,Ct1,PR1,PR2) from the first key record decrypt algorithm 718 to the key record register 728.
The key record is input to the key record register 728 over line 18, with the parse data in a first component register 730 and the concatenated control information Ct1, first private key PR1 and second private key PR2 in a second component register 732. The parse data in register 730 defines the beginning and ending of the control information Ct1, the first private key PR1 and the second private key PR2 in register 732. The parse data register 730 output is connected to a control input of the multiplexor 734, which separates the control information Ct1 for output through register 736 to the public key algorithms 10 and 10', which separates the first private key PR1 for output through register 738 to the gate 742 and which separates the second private key PR2 for output through register 740 to the gate 744.
Gate 742 has a control input connected to receive the Import DEA Key request signal R1, which enables the passing of the first private key PR1 to the first public key algorithm A1 at 10. The encrypted DEA key ePU1(key1) which was encrypted under a first public key PU1, is input to the operand input of the first public key algorithm A1. The control information Ct1 input to the first public key algorithm A1 describes the key type for the first private key PR1 (i.e., specifies PR1 is a decryption key). Using the first private key PR1, the public key algorithm A1 at 10 decrypts the encrypted DEA key ePU1(key1), which was encrypted under a first public key PU1, to obtain the clear text key1.
Gate 744 has a control input connected to receive the Generate Digital Signature request signal R2, which enables the passing of the second private key PR2 to the second public key algorithm A2 at 10'. The clear text Data2 expression is input to the operand input of the second public key algorithm A2. The control information Ct1 input to the second public key algorithm A2 describes the key type for the second private key PR2 (i.e., specifies PR2 is a decryption key). Using the second private key PR2, the public key algorithm A2 at 10' "decrypts" the clear text Data2 expression to obtain the requested digital signature.
Alternate embodiments of the functional block diagram of FIG. 20 can include providing a single key record decrypt algorithm which sequentially performs the functions of algorithms 718 and 720. Another alternate embodiment can include providing a single public key algorithm which sequentially performs the functions of algorithms 10 and 10'. Another alternate embodiment can include storing Key1 in a key block and receiving and processing the key in the encrypted form ePU1(key block). In that case, the output from public key algorithm A1 is a key block containing Key1. Another alternate embodiment eliminates the control information in the key record specifying that the key is a private key or a public key. Instead, the public key algorithms A1 and A2 include a control line indicating encryption or decryption, which is set by cryptographic facility 30 on the basis of the type of cryptographic operation requested. For example, for requests R1 and R2, cryptographic facility 30 will know that the key record contains a private key and that decryption with the private key is required. Thus, a decryption signal can be sent on the control line to the public key algorithms, A1 and A2.
Key Tokens and Key Units
Thus far the described invention has taught that a key token is produced within the cryptographic facility (CF) 30 from a control vector and a key record, as shown in FIG. 21, and the so-produced key tokens are stored outside CF 30 in a cryptographic key data set 32. Referring to FIG. 21, a key record 401 and associated control vector 400 are stored either in an internal key token 403 or an external key token 404. That is, a key token is either an internal key token (also referred to as a key token, i.e., without the modifier `internal`) or an external key token. An Internal Key Token 403 consists of a header 405, a control vector 406, and encrypted key record 407, and an encrypted authenticator 408. The encrypted key record 407 and encrypted authenticator record 408 are produced via key record encrypt algorithm 402, using as inputs control vector 400 and key record 401. Control vector 406 in internal key token 403 is just a copy of control vector 400, which is the control vector associated with key record 401. Key record encrypt algorithm 402 is the same key record encrypt algorithm 12 of FIG. 15. An External Key Token 404 consists of a header 409, a control vector 410, and a key record 411 (i.e., a clear key record). Control vector 410 in external key token 404 is just a copy of control vector 400, which is the control vector associated with key record 401. A key record is either a public key record (i.e., PU key record) or a private key record (i.e., PR key record). Likewise, an internal key token is either a internal PU key token or a internal PR key token, depending on whether the key token contains a PU key record or a PR key record, respectively, and an external key token is either an external PU key token or an external PR key token, depending on whether the key token contains a PU key record or a PR key record, respectively.
However, it may be advantageous to permit the cryptographic facility access program (CFAP) 34 to store key-related information in the key token, not directly available to the CF 30 and therefore not convenient or possible for the CF 30 to store in the key token. Thus, it may be more practical for the CFAP 34 to add certain information fields to the key token once the key token is returned to the CFAP 34 as an instruction output. In such situations where the CFAP is permitted to add information to the key token, a new set of terminology is introduced, as illustrated in FIG. 22. Thus, the internal key token 403 in FIG. 21 becomes internal key unit 423 in FIG. 22, and external key token 404 in FIG. 21 becomes external key unit 435 in FIG. 22. Likewise, control vector 400, key record 401, and key record encrypt algorithm of FIG. 21 are just control vector 420, key record 421, and key record encrypt algorithm 422 of FIG. 22. Likewise, header 405, control 406, encrypted key record 407 and encrypted authenticator record 408 of FIG. 21 are just header 425, control vector 426, encrypted key record 427, and encrypted authenticator record 423 of FIG. 22. Likewise header 409, control vector 410 and key record 411 of FIG. 21 are just header 429, control vector 430 and key record 431 of FIG. 22. Referring again to FIG. 22, internal key token 434 contains IKU 423 as well as other data 432 supplied by CFAP 34. Likewise, external key token 435 contains EKU 424 as well as other data 433 supplied by CFAP 34. Where convenient, the terminology IKU (i.e., internal key unit) and EKU (i.e., external key unit) will be used in lieu of internal key token and external key token when it is necessary to refer to quantities produced by CF 30.
Public Key Cryptographic Design
Full features and apparatus of the invention, which is referred to herein as the Public Key Cryptographic Design (PKCD), are now described. The reader will appreciate that the methods used for key record encryption and decryption described earlier are essential for coupling the usage control to a key in a public key cryptosystem. The reader will also notice that although alternate embodiments have been discussed earlier for key record encryption and decryption, only the first embodiment of FIG. 16 and FIG. 17 is incorporated in the PKCD.
COMPONENTS OF THE CRYPTOGRAPHIC FACILITY
The Cryptographic Facility contains three major components:
Instruction Processor
Cryptographic Algorithms
CF Environment
Instruction Processor
FIG. 23 is a block diagram illustration of the components of the Instruction Processor. They are:
Instructions: The CF instructions are invoked at the CFAP-To-CF interface. They provide the following cryptographic services to the CFAP:
System Digital Signatures
Application Digital Signatures
Key Management
CKDS Update
CF Backup
CF Audit
CF Initialization
CF Configuration
CF Control
Utility
Internal Routines: The internal routines are invoked only from within the CF. Collectively they represent a set of algorithms and processing functions that are common to many CF instructions. The internal routines have been specified to simplify the architectural description and definition, and to make each instruction's functional specification precise and less apt to contain errors and ambiguities. Although the internal routines are an integral part of the instruction functional specifications, an implementer may elect to implement the instructions and internal routines in a way that best suits or optimizes the particular implementation.
Configuration Table: The Configuration Table is a collection of constants that may vary in value from one implementation to another. The Configuration Table permits the Instructions and Internal Routines to be defined in a more general and open-ended way. Unlike the CF Environment, the Configuration Table is an integral part of the CF (e.g. hardware or ROS microcode).
FIG. 24 is a block diagram illustration of the elements in the Configuration Table.
Cryptographic Algorithms
FIG. 25 is a block diagram illustration of the main components of Cryptographic Algorithms of the CF.
The Cryptographic Algorithms components are these:
Data Encryption Algorithm (DEA): The DEA is described in the American National Standards Institute (ANSI) Data Encryption Algorithm (DEA) X3.92-1981. The DEA is a symmetric algorithm which encrypts or decrypts a 64 bit input with a 64 bit key to produce a 64 bit output. The 64 bit key specified to the algorithm consists of 56 key bits used by the algorithm and 8 non-key bits, which optionally may be used for error detection. According to ANSI X3.92-1981, the 8 non-key bits may be used for error detection. On the other hand, according to FIPS PUB 46, the 8 non-key bits shall be used for error detection and more specifically the error detection is based on byte-by-byte odd parity. Although the Symmetric Key Cryptographic Algorithm can be an optional component of the Cryptographic algorithms 144 shown in FIG. 15, the DEA is a required component in the PKCD, as it is needed for key record encryption and decryption.
Public Key Algorithm (PKA): PKA is a generic term referring to one of several possible public key algorithms. The PKCD does not specify the use of a particular PKA. However, the PKA must permit key distribution to be based on a key server concept wherein a DEA key, randomly generated and encrypted with a public key of a receiving device, is served to a receiving device where it is decrypted with the private key of the receiving device and reencrypted under the master key. The PKA must also permit generation and verification of digital signatures. A digital signature is produced by decrypting a signature record, containing a hash value, with a private key. A digital signature is verified by encrypting the signature with a public key and comparing hash values. The PKCD also permits key distribution with a first PKA and digital signatures to be implemented with a second PKA.
Public Key Algorithm Key Generator (PKAKG): PKAKG is a separate algorithm for the generation of keys used by the PKA.
Besides the main components, there are lower level algorithms, such as Key Record Encryption and Key Record Decryption algorithms needed for frequent encryption and decryption of public and private keys, as discussed earlier.
CF Environment
FIG. 26 is a block diagram illustration of the components of the CF Environment.
The CF Environment components are these:
Configuration Vector: The configuration vector is a collection of encoded fields that limit or restrict the operation of the cryptographic fac |
