Cryptographic key recovery system

The present invention relates to a cryptographic key recovery system, and more particularly to a key recovery system that works with an existing system to establish a key between communicating parties. Data encryption systems are well known in the field of data processing technology. Generally, such a system operates by using an encryption key to perform an encryption operation on a plaintext input block to create a ciphertext output block. The recipient of the encrypted message uses the decryption key to perform the corresponding decryption operation to recover the plaintext block. Cryptographic systems can be divided into two types. Symmetric (or private key) encryption systems, such as the Data Encryption Standard (DES) system, use the same sensitive key for both message encryption and decryption. The DES system uses a key with 56 bits that can be specified independently to convert a 64-bit plaintext block into a ciphertext block and vice versa. Asymmetric (or public key) encryption systems, on the other hand, use different keys for encryption and decryption that cannot be easily inferred from each other. The person who wants to receive the message generates a pair of corresponding encryption and decryption keys. The encryption key is made public, but the corresponding decryption key is made private. Anyone who wants to communicate with the recipient can use the recipient's public key to encrypt the message. However, since only the recipient has the private key, only the recipient can decrypt the message. Perhaps the best-known asymmetric cryptosystem is the RSA cryptosystem, named after its founders Rivest, Shamir, and Adleman. Asymmetric cryptosystems generally require more computation than symmetric cryptosystems, but have the advantage of not requiring a secure channel to carry the encryption key. For this reason, asymmetric encryption systems are often used to transfer secret data such as symmetric encryption keys. All types of data encryption systems attract the attention of government intelligence and law enforcement agencies ing. This is because the same security level that prevents unauthorized third parties from decrypting also prevents decryption by information or law enforcement officials who have a legitimate reason to want to access plaintext data. Because of such concerns, the government either bans the use or export of strong cryptosystems, or key consumption attacks (ie, systematically test all possible keys until the correct key is found). Subject to government approval for the use of vulnerable and vulnerable keys. Such weak cryptosystems have the obvious drawback of being vulnerable not only to authorized government officials, but also to unauthorized third parties. Recently, various ciphers are a compromise between the communication party's demands for privacy in electronic communications and the law enforcement agency's demands for access to such communications when a crime or threat to national security needs to be detected. A key recovery system has been proposed. Generally, in such a key recovery system, all or part of the key used by the communicating party actually gives the key part to the key recovery agent (in this case, the key part is said to be "escrowped"). Or it can be obtained by one or more key recovery agents by providing sufficient information to the communication itself (such as by encrypting the key part) so that the key recovery agent can regenerate part of the key. is there. Key recovery agents will only escrow or escrow if accurate evidence of authority is presented, such as a court order authorizing interception. Cryptographic systems have the obvious drawback of being vulnerable not only to authorized government officials, but also to unauthorized third parties. Recently, various ciphers are a compromise between the communication party's demands for privacy in electronic communications and the law enforcement agency's demands for access to such communications when a crime or threat to national security needs to be detected. A key recovery system has been proposed. Generally, in such a key recovery system, all or part of the key used by the communicating party actually gives the key part to the key recovery agent (in this case, the key part is said to be "escrowped"). Or it can be obtained by one or more key recovery agents by providing sufficient information to the communication itself (such as by encrypting the key part) so that the key recovery agent can regenerate part of the key. is there. Key recovery agents will only escrow or escrow if accurate evidence of authority is presented, such as a court order authorizing interception. Cryptographic systems have the obvious drawback of being vulnerable not only to authorized government officials, but also to unauthorized third parties. Recently, various ciphers are a compromise between the communication party's demands for privacy in electronic communications and the law enforcement agency's demands for access to such communications when a crime or threat to national security needs to be detected. A key recovery system has been proposed. Generally, in such a key recovery system, all or part of the key used by the communicating party actually gives the key part to the key recovery agent (in this case, the key part is said to be "escrowped"). Or it can be obtained by one or more key recovery agents by providing sufficient information to the communication itself (such as by encrypting the key part) so that the key recovery agent can regenerate part of the key. is there. Key recovery agents will only escrow or escrow if accurate evidence of authority is presented, such as a court order authorizing interception.Will reveal the regenerated key portion to the requesting law enforcement agent. When using multiple key recovery agents, all agents must work together to recover the key, and it is unlikely that a law enforcement agent will use a rogue key recovery agent to recover a key fraudulently. It can be suppressed to the limit. The key recovery system meets the communication's interest in privacy. This is because their cryptosystems are strong enough against third parties and do not need to be weakened to comply with national restrictions on cryptography or to meet export requirements. At the same time, the key recovery system can intercept encrypted communications in situations where unencrypted communications have been intercepted in advance (such as when a court order has been obtained), which is a legitimate need for law enforcement. Meet. Other than meeting the needs of law enforcement, key recovery systems can be applied in purely private situations. Therefore, organizations are worried about employees using strong encryption of important files whose keys cannot be recovered. Losing the key means losing important stored data. Some desirable features of the key recovery system have been established. Therefore, first considering the high priority features, the key recovery system must be able to be implemented in the form of software or hardware. The key recovery system must not require communication with a third party to generate a message or establish a connection. The key recovery system must provide common operability between users in different countries. The algorithm used must be publicly known and its mechanism must be algorithm-independent. The design must be publicly available and can be implemented by multiple vendors based on published specifications. The key recovery system must provide key recovery capabilities independently for each country. A key recovery system must provide different levels of security flexibility in different environments in a single system, and the highest level of cryptographic security permitted by law. All protection must be provided. The key recovery system must be a module extension (add-on) of an existing cryptosystem. The key recovery system can be used with any key exchange mechanism and must at the same time hold a control point for key recovery. The confidentiality of the exchanged keys must be maintained, except to allow recovery. Other features, albeit low priority, are fairly desirable. The key recovery system should support both a store-and-forward environment and an interactive environment. The key recovery system should not require communication with a third party for installation (ie, the key recovery system operates "out of the box"). Key recovery systems should support policy choices that require the collaboration of multiple key recovery agents to recover keys (to provide protection against rogue key recovery agents). The key recovery system should allow external verifiers (without access to the key recovery key) some confidence in the parties' use of the system's unpatched implementation. (Note that in an interactive environment, if both parties encrypt using the same public key and key recovery information, a third party can check for ciphertext identity.) Key recovery system Should prevent patch (illegal) implementations from collaborating with unpatched (compliant) implementations. It is difficult to change the method for use in bulk data confidentiality channels. DE Denning and DK Branstad's "A Taxonomy for Key Escrow Encryption Systems", Communications of the ACM, vol. 39, no. 3, March 1996, where various types of key recovery systems are incorporated by reference. , Pp, 34-40. Two specific key recovery systems are shown below. DB filed on April 10, 1996 Johnson et al., Patent Application No. 08/629815, "Cryptographic Key Recovery System," describes a partial key recovery system that uses multiple key recovery agents. In one version of the system described in the application, the sender produces a set of key recovery values (or key parts) P, Q and (optionally) R. The session key is generated by combining the P value and Q value by XOR addition, concatenating the result with R, hashing the concatenated result, and generating the key. The public key of each key recovery agent is then used to encrypt the P and Q values, and the encrypted P and Q values (along with other recovery information) are attached to the encrypted message in the section header. Put inside. When an R-value is generated, it is not made available to any key recovery agent and is kept private to provide a significant work factor for law enforcement agents attempting to recover the key. To. As is clear from the above description, the key recovery procedure described in the above patent application uses the mechanism of the key recovery procedure itself to establish a sensitive session key used to encrypt the message. There is a need. The disclosed key recovery procedure does not fit into the existing key matching procedure because the user cannot specify the session key independently. PCT Published Patent Specification WO 96/05673 (Trusted Information) In other key recovery systems described in Systems), the sender sets the first session key portion to be equal to a random number, and sets the second session key portion to that random number and its session. -Split the session key into a first session key part and a second session key part by setting it to be equal to the XOR with the key. The sender uses the public encryption keys of the first and second key recovery agents to encrypt each session key portion and concatenates the two encryption products to enforce the law enforcement access field. Generate (LEAF). The sender also generates a LEAF validation string (LVS) by concatenating the original session key portion and encrypts it with the session key to form an encrypted LEAF validation string (ELVS). .. Finally, the sender sends the encrypted message to the recipient along with LEAF and ELVS. Before decrypting the encrypted message, the recipient actually performs a LEAF to verify that the sender has generated an appropriate LEAF that allows the session key to be recovered through the key recovery agent. Reproduce. This is done by decrypting ELVS to obtain the session key portion and then encrypting each session key portion using the public encryption keys of the first and second key recovery agents. If the recipient succeeds in reproducing the transmitted LEAF in this way, he concludes that the LEAF is authentic and begins decrypting the message. Otherwise, the recipient concludes that the LEAF is fraudulent and does not start the decryption step. This key recovery system allows the use of arbitrarily generated session keys by introducing additional sensitive amounts (random numbers) that the recipient does not have into the key splitting procedure. Due to this additional confidentiality, the recipient cannot play the key parts independently (to confirm the LEAF) and play them (by LEVS) from the sender. Must be obtained as additional information. According to the first aspect of the present invention, a method of recovering an encryption key by using a plurality of collaborative key recovery agents without requiring additional private information as a function of the key. A step of generating a plurality of shared key recovery values so that the key can be regenerated from the shared key recovery value, and the shared key recovery value to facilitate recovery of the key using the key recovery agent. Is provided with a step of making the key recovery agent available to the key recovery agent. According to a second aspect of the present invention, there is provided a program storage device that is readable by a machine and embodies a program of instructions that can be executed by the machine to perform the method steps defined in the method claims below. To. The present invention is intended for a system that handles key recovery. The present invention applies to DB Johnson et al. Patent Application by allowing a user to establish a session key using a desired key distribution or key matching procedure (eg, a procedure with the attribute of full transfer confidentiality). Enhance the system described. The mechanism used to establish the session key is independent of the cryptographic key recovery procedure and is completely transparent to it. At the same time, the present invention provides a key distribution procedure in the absence of it. One feature of the invention is a new key inversion function that allows the P, Q, and R values required for key recovery procedures to be generated from a sensitive session key (ie, by working in reverse from the key). is there. That is, the session key is an independent variable, and the P, Q, and R values are dependent variables. On the other hand, DB In Johnson et al. Patent application, the P-value, Q-value, and R-value are independent variables, and the key is the dependent variable (ie, the key is derived from the P-value, Q-value, and R-value). One possible solution to the problem (that it does not fit into existing key establishment procedures) is by using a method called "key sharing" or "key splitting" as described in the PCT application above. there were. However, as mentioned above, key sharing introduces additional sensitive variables that must be sent confidentially from the sender to the recipient under the key recovery procedure. It is an object of the present invention to avoid such requirements and to eliminate the need for the sender to convey sensitive information to the recipient so that the recipient can carry out his or her own portion of the key recovery procedure. This issue is circumvented by configuring a special entropy-storing key inversion function that allows the P, Q, and R values to be calculated from the sensitive session key and the public information used by the key recovery procedure. The difference between the key inversion function and the key sharing of the embodiment described below will be further described. The key inversion function is used to convert a key to "equivalent display". Key inversion is based solely on the key as input and the public parameters. Therefore, key inversion can be easily verified by anyone with access to the key. Also, given an output (ie, key recovery) value, the key can be easily verified (since verification requires only the output value and public variables). Key inversion differs from the "confidential sharing" technique because it uses only the key and public parameters and does not require the additional random bits used for confidentiality sharing. Therefore, when splitting a key into two values (as in the PCT application above), the "entropy" (ie, randomness content) of the split is doubled compared to the first key. On the contrary, the key inversion of the present invention does not increase the "entropy" of the key because the inversion mechanism does not require additional randomness. For this entropy preservation, the key inversion function of the embodiment described is actually invertable and The output value can be derived starting from the key, or the key can be derived starting from the output value. This is important for output validation and its usage. Confidentiality techniques do not consider such verification. As described below, the present invention allows (1) the parties to agree to the key or to use an independently established key, and (2) the key recovery information relevant to the recipient. To be able to verify, (3) to give the authorized entity the ability to recover key components, and (4) to give the authorized entity the key recovery given by the key recovery agent. Send a session context that contains enough information to give you the ability to verify that the information is correct. Confidential values are made available in various ways. Confidential values may be encrypted and made available to third parties. Alternatively, the sensitive value may be encrypted and sent with the encrypted data. In that case, the sensitive value must be accessed via electronic means. The latter method is described in the examples herein. The present invention is implemented as an "add-on" rather than a replacement for an existing key distribution scheme. According to the "add-on" approach, existing cryptographic systems can benefit from the present invention (longer keys) and at the same time do not require modification of the system's existing key distribution components. Therefore, one of the main objectives of the present invention is to be as self-contained and independent as possible, and to minimize the necessary changes to existing cryptosystems or applications to perform key recovery. .. A brief summary of the advantages of the systems and methods described below. This system and method is an add-on solution that can work with key distribution procedures and provides it in the absence of key distribution. This system and method allows recovery agents to recover lost cryptographic keys. No user key is held by the key recovery agent. The key recovery agent is not responsible for generating the user key. This system And the method is a multi-way key recovery method. According to systems and methods, make strong cryptography available worldwide. This system and method addresses the need for legitimate and authorized law enforcement, while at the same time the weaknesses inherent in other key recovery proposals (eg, infrastructure requirements or special for establishing user keys). Address hardware device requirements). This system and method has no key length restrictions and no algorithmic restrictions. This system and method can work with all key exchange mechanisms. Only the session encryption key can be recovered. Some of the key recovery information will be made available according to the policy. A uniform (cryptographic algorithm independent) work factor is provided for complete key recovery. Since the present invention uses only encryption, it is difficult to change the method for use on bulk data confidentiality channels. As described below, embodiments of the present invention provide a great deal of flexibility. For example, the invention can comply with and comply with national laws and regulations. The present invention has built-in flexibility for non-escrow key lengths and key escrow key lengths. For bilateral communication, escrow rules reduce the values of P and R by default, resulting in a smaller work factor. Key management is done in a variety of ways that are consistent with modern standard industry practices. The present invention does not attempt to detect two collaborative unauthorized users. Two users can always "do their own thing" outside this system. The present invention addresses the communication needs of users and authorized key recovery agents from different countries. The present invention is applicable to a wide variety of cryptographic algorithms and key lengths. The present specification uses the example of Triple DES with a total key length of 168 bits. The present invention assumes the use of public key cryptography when working with key recovery agents. The present invention does not assume the use of public key cryptography for key distribution between users. An example of key distribution herein is a public key cipher. Only use RSA or Diffie-Hellman key exchange (for example, RSA or Diffie-Hellman key exchange), but symmetric key ciphers (for example, Kerberos) can also be used. The present invention maintains the confidentiality provided by the key distribution mechanism. The present invention enhances the key recovery ability. For example, if the key distribution has full transfer confidentiality, this property is maintained. The present invention assumes that the public keys of the user as well as the key recovery agent are proven. Procedures and mechanisms for performing such proofs are well known in the art and are outside the scope of this system. Each country can use multiple key recovery agents. Each key recovery agent has a unique ID. The public keys of the key recovery agents and / or their certifiers, or the safeguards to obtain these public keys, are provided in the client's hardware or software using one of several mechanisms. Therefore, each key recovery agent generates its own public / private key pair (for example, a 1024-bit RSA key), exposing the public key but keeping the private key confidential. (Cryptographic devices can handle variable key sizes). This will allow cryptographic products to be shipped that have the ability to act as a turnkey solution "out of the box". A system incorporating the disclosed key recovery system can be preconfigured with a country ID that indicates the country in which the system is located and can operate. The user can also configure the system with other information required for the key recovery procedure. For cryptographic products that have only key recovery capabilities, the embodiment does not allow the application program to bypass the key recovery system by calling the cryptographic algorithm directly. The key recovery system ensures that the key recovery procedure steps are taken after being called. That is, the key used for data privacy encryption will not be made available to the application program or user until the procedural steps are successfully completed. Next, for embodiments of the present invention, only as an example. The explanation will be given with reference to the attached drawings. FIG. 1 is a schematic block diagram of a communication system in which the present invention is used. FIG. 2 is a schematic block diagram of the general key reversal method of the present invention implemented for a specific country. FIG. 3A is a schematic block diagram of an exemplary key inversion function for generating key recovery values from session keys. FIG. 3B is a schematic block diagram of an alternate key inversion function for generating key recovery values from session keys. FIG. 4 is a flow diagram of a procedure used by a sender who wants to send an encrypted message to a recipient using an independently established session key. FIG. 5 is a flow chart of the procedure taken by the receiver when receiving a message packet from the sender. FIG. 6 is a schematic block diagram of the session context of the message header. FIG. 7 is a schematic block diagram of the session header of the message packet. FIG. 8 is a schematic block diagram of message packets. FIG. 9 is a schematic block diagram of session context recovery information. FIG. 10 is a schematic block diagram of the key recovery agent key header of the session context of FIG. 9, and FIG. 11 is a schematic block diagram of the procedure for encrypting the shared key recovery value. FIG. 12 is a diagram showing a global communication policy table used in the present invention. FIG. 13 is a schematic block diagram of a possible system embodiment of the present invention. FIG. 14 is a schematic block diagram of the Shehri function used in the key inversion function of FIG. 3A. FIG. 15 is a schematic block diagram of the inversion of the Shehri function shown in FIG. FIG. 16 is a schematic block diagram of a method of subdividing one of the blocks used in the Shehri function shown in FIG. It is a figure. FIG. 3B is a schematic block diagram of an alternate key inversion function for generating key recovery values from session keys. FIG. 4 is a flow diagram of a procedure used by a sender who wants to send an encrypted message to a recipient using an independently established session key. FIG. 5 is a flow chart of the procedure taken by the receiver when receiving a message packet from the sender. FIG. 6 is a schematic block diagram of the session context of the message header. FIG. 7 is a schematic block diagram of the session header of the message packet. FIG. 8 is a schematic block diagram of message packets. FIG. 9 is a schematic block diagram of session context recovery information. FIG. 10 is a schematic block diagram of the key recovery agent key header of the session context of FIG. 9, and FIG. 11 is a schematic block diagram of the procedure for encrypting the shared key recovery value. FIG. 12 is a diagram showing a global communication policy table used in the present invention. FIG. 13 is a schematic block diagram of a possible system embodiment of the present invention. FIG. 14 is a schematic block diagram of the Shehri function used in the key inversion function of FIG. 3A. FIG. 15 is a schematic block diagram of the inversion of the Shehri function shown in FIG. FIG. 16 is a schematic block diagram of a method of subdividing one of the blocks used in the Shehri function shown in FIG. It is a figure. FIG. 3B is a schematic block diagram of an alternate key inversion function for generating key recovery values from session keys. FIG. 4 is a flow diagram of a procedure used by a sender who wants to send an encrypted message to a recipient using an independently established session key. FIG. 5 is a flow chart of the procedure taken by the receiver when receiving a message packet from the sender. FIG. 6 is a schematic block diagram of the session context of the message header. FIG. 7 is a schematic block diagram of the session header of the message packet. FIG. 8 is a schematic block diagram of message packets. FIG. 9 is a schematic block diagram of session context recovery information. FIG. 10 is a schematic block diagram of the key recovery agent key header of the session context of FIG. 9, and FIG. 11 is a schematic block diagram of the procedure for encrypting the shared key recovery value. FIG. 12 is a diagram showing a global communication policy table used in the present invention. FIG. 13 is a schematic block diagram of a possible system embodiment of the present invention. FIG. 14 is a schematic block diagram of the Shehri function used in the key inversion function of FIG. 3A. FIG. 15 is a schematic block diagram of the inversion of the Shehri function shown in FIG. FIG. 16 is a schematic block diagram of a method of subdividing one of the blocks used in the Shehri function shown in FIG. It is a schematic block diagram of the recovery information of a state context. FIG. 10 is a schematic block diagram of the key recovery agent key header of the session context of FIG. 9, and FIG. 11 is a schematic block diagram of the procedure for encrypting the shared key recovery value. FIG. 12 is a diagram showing a global communication policy table used in the present invention. FIG. 13 is a schematic block diagram of a possible system embodiment of the present invention. FIG. 14 is a schematic block diagram of the Shehri function used in the key inversion function of FIG. 3A. FIG. 15 is a schematic block diagram of the inversion of the Shehri function shown in FIG. FIG. 16 is a schematic block diagram of a method of subdividing one of the blocks used in the Shehri function shown in FIG. It is a schematic block diagram of the recovery information of a state context. FIG. 10 is a schematic block diagram of the key recovery agent key header of the session context of FIG. 9, and FIG. 11 is a schematic block diagram of the procedure for encrypting the shared key recovery value. FIG. 12 is a diagram showing a global communication policy table used in the present invention. FIG. 13 is a schematic block diagram of a possible system embodiment of the present invention. FIG. 14 is a schematic block diagram of the Shehri function used in the key inversion function of FIG. 3A. FIG. 15 is a schematic block diagram of the inversion of the Shehri function shown in FIG. FIG. 16 is a schematic block diagram of a method of subdividing one of the blocks used in the Shehri function shown in FIG.<u style="single">General environment</u>FIG. 1 shows a communication system 100 in which the key recovery system of the present invention is used. In system 100, country X sender 102 (Alice) is a country Y recipient by sending one or more encrypted messages (which make up a communication session) over communication channel 106. Communicate with 104 ("Bob"). The sender 102 and the receiver 104 each include a computer workstation that is properly programmed to provide the encryption and key recovery functions described below. Although the example in FIG. 1 assumes that the sender 102 and the receiver 104 are located in different countries (X and Y), the invention can also be used in a completely single country. The transmitted message is encrypted by the sender 102 using the session encryption key and decrypted by the receiver 104 using the corresponding session decryption key. When using symmetric encryption (eg DES), the session encryption key (which is also the session decryption key) is the "confidential" session key for key recovery. On the other hand, when using asymmetric cryptography (eg RSA), the private session decryption key is the "confidential" session key for key recovery, as described further below. The pair of key recovery agents 108 and 110 (in this particular example) is selected in country X, and the pair of key recovery agents 112 and 114 is selected in country Y. The establishment of a key recovery agent can be part of the establishment of an open house key infrastructure. It is assumed that communication via communication channel 106 is vulnerable to interception by third parties, including country X and Y law enforcement agents 116 and 118, respectively. A private third party who intercepts encrypted communications cannot decrypt the communications without successful use of one or more cryptanalysis techniques. On the other hand, a legitimate law enforcement agent 116 or 118 uses a session key using his country's key recovery agents 108, 110 or 112, 114 as described below.<u style="single">Key reversal function: general form</u>FIG. 2 shows the general key reversal scheme 200 of the present invention implemented for (for example) country X. Sender 102 calls the key reversal function 204 with a pair of shared key recovery values P and Q (206 and 208) depending on the sensitive session key K (202) and public information, and optionally a non-shared key recovery value. Generate R (210). As described more fully below, sender 102 encrypts the shared key recovery values P and Q with each public recovery key of the key recovery agent, and the encrypted key recovery values P'and Q. By generating a', the shared key recovery values P and Q are made available to the first and second key recovery agents 108 and 110 in country X. Sender 102 includes encrypted key recovery values P'and Q'in the header associated with the first message, at least up to receiver 104 via communication channel 106. On the other hand, the non-shared key recovery value R (if generated) is not revealed to any third party. The key reversal function 204 (1) gives a one-to-one correspondence between the key K and the generated key recovery value, and (2) easily replays the key K from the key recovery value by reversing the function. It is reversible in the sense that it can be done. If the generated key recovery values contain only P and Q (ie R is not generated), the key K is entirely determined by P and Q and can be easily regenerated if these values are known. If the generated key recovery value contains R, the key is completely determined only by P, Q, R and cannot be easily determined from P and Q alone. However, the number of possible R-values generated by the key inversion function 204 can be used by law enforcement agents who know P and Q to exhaust the space for possible R-values, as explained below. Small enough to play well. The work factor required to verify R is designed to discourage the normal decryption of messages by law enforcement agents, even if they obtain P and Q values. Law enforcement d Agent 116 extracts the encrypted key recovery values P'and Q'from the session header to decrypt the message it intercepts, and keys them along with accurate evidence of authority (such as a court order). Present to recovery agents 108 and 110. When key escrow agents 108 and 110 were convinced that they were authorized by the law enforcement agent, they used their private decryption keys to decrypt the encrypted key recovery values and the recovered values P and Q. To the law enforcement agent 116. The law enforcement agent then generates successive test values for R and feeds them as input to the key inversion function 204 along with the recovered P and Q values until the original session key K is recovered. ..<u style="single">Key reversal function: particular embodiment</u>FIG. 3A shows an exemplary key inversion function 300 that generates key recovery values P, Q, R from session key K, or session key K from key recovery values P, Q, R. The exemplary key reversal function 300 generates P and Q values for two key recovery agents per user, but the sender and receiver each generate two or more key recovery agents or only one key recovery agent. The key inversion function can produce any number of outputs to deal with the case of having. The key inversion function 300 requires the following inputs. That is, (1) key K, (2) length of key K represented by bits, (3) length of R represented by bits represented by r, (4) first and first of communication parties 102 and 104. Recovery information 610 to describe, including 2 key recovery agent IDs 912, 916, 922, 926 (Figure 9). The original key K is preprocessed by embedding up to 15 0 bits in the most significant bit position to form the n-bit processed key 302. However, n is a multiple of 16. The example in Figure 3A shows the case where the sender uses an r-bit R value in country X and the receiver uses a 0-bit R value in country Y. The n-bit embedded key 302 is processed by the first invertable "Shahri" function 304 (discussed further below) to produce the n-bit output value 306 represented by F (P, Q, R). .. Every bit of F (P, Q, R) depends pseudo-randomly on all key bits. F (P, Q, R) is a representative or modified form of key K. The sender's agent Px and Qx values are generated from F (P, Q, R) as follows: Define any r bit (for example, the least significant r bit) of F (P, Q, R) as the value R (308). Define the remaining nr bits of F (P, Q, R) (for example, the most significant nr bit) as the first input value F (Px, Qx) (310) (to the Shehri function to be described). The second input value Hx (316) of the (n + r) bit is the first input value F (Px, Qx) (310) of the (nr) bit. Prefixed to generate a 2n-bit extended input value 317. The extended input value 317 is then processed using the second invertable Shehri function 318 to generate a 2n-bit output value 319. Finally, the output value 319 is divided into a part composed of an n-bit value Px (320) and an n-bit value Qx (322). The Shehri function 318 is the same as the Shehri function 304 except for the length of the input value 317 and the output value 319. The number of bits in Hx ensures that the last input to the Shehri function 318 is always an even number of bytes (regardless of the number of key recovery agents). The (n + r) bit value (316) of Hx is calculated as follows. Sender 1st and 2nd key recovery agent IDs 912 and 916 (Fig. 9), hash values calculated based on recovery information (T1) H (T1) 610 (Fig. 9), F (P, Q, R), as well as the public headers, are concatenated in a predetermined order (eg, in the order described above) to form the data block indicated by D1. D1 = (Sender's First Key Recovery Agent ID || Sender's Second Key Recovery Agent ID || H (T1) || F (P, Q, R) || Public Header) Recovery Information 610 ( (Represented by T1) is defined and described in Figure 9. The sender's first and second key recovery agents IDs 912 and 916 are part of this key recovery information. The public header has an 8-byte structure defined as follows. 1 byte identifier: Data to be hashed = "PQ key recovery agent ID" 1 byte Counter: 0, 1, 2, etc. 6 bytes Reserved: Hash the set data block D1 to 0 (the counter in the public header is initially 0) to generate the hash value H (D1). If the length of H (D1) is less than n + r, concatenate successive hashes H (D1) until the total length is equal to or greater than n + r (the counter is for each subsequent hash). Increments to). Hx is defined as the least significant n + r bit. This technique prevents the workload factor from becoming smaller for larger R lengths. The values Px (320) and Qx (322) are the most significant n bits and the least significant n bits of the 2n bit output 319 generated from the Shehri function 318, respectively. Px (320) is the value encrypted with the public key of the sender's first key recovery agent 108. Qx (322) is the value encrypted with the public key of the sender's second key recovery agent 110. The recipient's agent Py and Qy values are similarly generated from the original key as follows: Since the recipient 104 does not have an R-value (in this example), we define the total F (P, Q, R) value 306 as the n-bit first input value F (Py, Qy) (324). The n-bit second input value Hy (326) is prepended to the n-bit first input value F (Py, Qy) (324) to generate the extended input value 327. The extension input 327 is then processed using the Shehri function 328 (similar to the Shehri function described earlier) to generate a 2n-bit output value 329, which is n-bit Py (330) and n-bit Qy (n-bit Qy (330)). 332) Divide into. Calculate Hy in the same way as Hx. However, when forming a data block (indicated here by D2), the sender's first and second key recovery agent ID 912, 916 instead of the recipient's first and second key recovery agent ID 922, Use 926 (Fig. 9). The particular key recovery agents designated as the first or second key recovery agents for a given party are determined by the order in which their IDs appear in recovery information 610 (Figure 9). Sender's 1st and 2nd The key recovery agents IDs 912 and 916 and the recipient's first and second key recovery agents IDs 922 and 926 are arranged in the order classified in the recovery information 610, respectively. Therefore, the process of generating P, Q, R values and salt values (discussed below) and constructing data structures is a completely deterministic process. The key inversion function 300 is an entropy-storing function because the values of P, Q, and R generated thereby are derived from the sensitive key K and other public information. That is, the number of key combinations is the same as the number of PQR combinations. In the secret sharing method, the entropy increases with the number of splits required to recover the original key. The key inversion function 300 requires the entire key K in the process of calculating the values of P, Q, and R. Therefore, even if you know the value of P (for example), you can execute the key inversion function in the forward or reverse direction to thoroughly determine Q with a work factor that is smaller than the work factor for thoroughly determining the key K. Will not be able to decide. The sender 102 does not need to convey sensitive protocol information to the receiver 104. The only sensitive value that recipient 104 needs to validate the encrypted P and Q values is the sensitive session key K. Optionally, the sender 102 has a sensitive signature generation key and the recipient 104 has a valid copy of the sender's public verification key. In addition, the sender 102 and the receiver 104 do not need a special key established between them to perform the encryption procedure of the present invention. The present invention provides uniformity in work factors (visible to law enforcement agents) for all cryptographic key types. In addition, the work factor is consistent for all types of cryptographic algorithms. That is, the 40-bit work factor is always 40 bits for DES, public keys, RC2 / 4/5, or other algorithms. The key inversion function 300 has the additional advantage of adapting to situations where the secret key K is not an independent random variable (eg an RSA secret key). Tato For example, if the public key is a fixed constant (eg 216-1), then the private key is the dependent variable. Such a sensitive key cannot be generated from independent P, Q, R values. You need to use the key inversion function to generate P, Q, and R values from a secret key. Step 300 in Figure 3A can be extended to handle any number of key recovery agents. For example, if sender 102 has three key recovery agents, prefix F (Px, Qx) with 2n + r bits of Hx. In such cases, data block D1 has three concatenated key recovery agent IDs instead of two. In general, if you have k key recovery agents, prefix F (Px, Qx) with the (k-1) n + r bits. In such cases, data block D1 has k concatenated key recovery agent IDs instead of two. Similarly, if the recipient 104 has three key recovery agents, prefix F (Py, Qy) with 2n bits of Hy. Since the recipient does not have an R value, r does not appear in the recipient's equation. If the recipient 104 has k key recovery agents, prefix F (Py, Qy) with (k-1) n-bit Hy. The recipient's data block D2 is also modified by including the required additional key recovery agent ID. If there is only one key recovery agent (for example, country X sender 102 uses only one key recovery agent), the procedure is slightly modified. Calculate the P and Q values as if you needed two key recovery agents. However, the calculation of the Hx value (Fig. 3A) is slightly different). In this case, hash the data block D1 = (first key recovery agent ID || first key recovery agent ID || H (T1) || F (P, Q, R) || public header) , Generates a 160-bit hash value H (D1). If H (D1) is less than n, then the counter is followed by a counter until the total length is equal to or greater than n, as described above. Used with Shu value H (D1). This technique prevents the workload factor from becoming smaller for larger R lengths. The same process is used even if recipient 104 has only one key recovery agent. In that case, Hy calculates in the same way as Hx, but uses the recipient's agent ID instead of the sender's agent ID. The number of key recovery agents varies from country to country or from application to application. For example, the sender may use two key recovery agents and the recipient may use one or three key recovery agents. To recover session key K, law enforcement agent 116 or 118 (Figure 1) reverses the key inversion function 300 to generate a key from the values of P and Q. To do this, it is necessary to execute the Shehri functions 304, 318, 328 in the opposite direction as described below. Further, the process is executed for the recovered Hx or Hy value. After the key K is recovered, the salt values used to encrypt P and Q (discussed below) are recalculated, the encrypted P and Q values are regenerated, and the intercepted cipher. Check for identity with the converted P and Q values. The key recovery operation will be further described using country X as an example. With reference to FIG. 3A, the first operation to be performed is to "unshuffle" Px (320) and Qx (322) (ie, run the Shahula function 318 in reverse) for Hx (316) and F. To get (Px, Qx) (310). The next step requires a thorough search for R (308). The exact R can be detected with extremely high accuracy by calculating the Hx based on the candidate R and matching the result with the unshuffled Hx. Given F (Px, Qx) (310) and R (308), the quantity F (P, Q, R) (306) is unshuffled and embedded (by running the Shehri function 304 in reverse). Get key 302. In Fig. 3B, there is only one shuffling operation for each country, and there are three sets. An alternative embodiment 350 of the key reversal function in which all key recovery values P, Q, and R are generated at the same stage of the procedure is shown. In this alternative embodiment, the sender's agent Px and Qx values are generated from the original n-bit key K (352) as follows: Precede the n-bit key 352 with the (n + r + s) bit value Hx (354) (calculated in the same way as the Hx value 316 above) and obtain the (2n + r + s) bit input value. Process 356 with Shehri function 358 to generate (2n + r + s) bit output value 360. s is an integer from 0 to 15 such that 2n + r + s is a multiple of 16. Next, the output value 360 is divided into an r-bit R value 362, a (n + s / 2) bit Q value 364, and a (n + ss / 2) bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352 and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Is shown. In this alternative embodiment, the sender's agent Px and Qx values are generated from the original n-bit key K (352) as follows: Precede the n-bit key 352 with the (n + r + s) bit value Hx (354) (calculated in the same way as the Hx value 316 above) and obtain the (2n + r + s) bit input value. Process 356 with Shehri function 358 to generate (2n + r + s) bit output value 360. s is an integer from 0 to 15 such that 2n + r + s is a multiple of 16. Next, the output value 360 is divided into an r-bit R value 362, a (n + s / 2) bit Q value 364, and a (n + ss / 2) bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352 and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Is shown. In this alternative embodiment, the sender's agent Px and Qx values are generated from the original n-bit key K (352) as follows: Precede the n-bit key 352 with the (n + r + s) bit value Hx (354) (calculated in the same way as the Hx value 316 above) and obtain the (2n + r + s) bit input value. Process 356 with Shehri function 358 to generate (2n + r + s) bit output value 360. s is an integer from 0 to 15 such that 2n + r + s is a multiple of 16. Next, the output value 360 is divided into an r-bit R value 362, a (n + s / 2) bit Q value 364, and a (n + ss / 2) bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352 and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Prepend the n-bit key 352 (calculated in the same way as the Hx value 316 above), process the resulting (2n + r + s) bit input value 356 with the Shehri function 358, and (2n + r). + s) Generate a bit output value of 360. s is an integer from 0 to 15 such that 2n + r + s is a multiple of 16. Next, the output value 360 is divided into an r-bit R value 362, a (n + s / 2) bit Q value 364, and a (n + ss / 2) bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352, and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Prepend the n-bit key 352 (calculated in the same way as the Hx value 316 above), process the resulting (2n + r + s) bit input value 356 with the Shehri function 358, and (2n + r). + s) Generate a bit output value of 360. s is an integer from 0 to 15 such that 2n + r + s is a multiple of 16. Next, the output value 360 is divided into an r-bit R value 362, a (n + s / 2) bit Q value 364, and a (n + ss / 2) bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352, and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. -s / 2) Divide into bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352, and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. -s / 2) Divide into bit P value 366. s / 2 is defined as the integer component of the fractional value. For all practical purposes, P indicates the output bits that remain after Q and R have been extracted. The extraction method ensures that all bits in the output are allocated in the values P, Q, R, and that the lengths of P and Q differ by at most 1 bit. The sender's agent Py and Qy values are generated from the original key (K) 352 as follows: Prefix the (n + s) bit value Hy (368) (calculated in the same way as the Hy value 326 above) to the n-bit key 352, and use the resulting (2n + s) bit input value 370 as the shuffle function. Process with 372 to generate (2n + s) bit output value 374. The variable r is dropped from the equation because r = 0. Also, r is an integer from 0 to 15 such that 2n + s is a multiple of 16. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Is an integer in. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit. Is an integer in. The output value 374 is then divided into (n + s / 2) bit Q value 376 and (n + ss / 2) bit P value 378. s / 2 is defined as above. For all practical purposes, P indicates the output bits that remain after Q is extracted. The extraction method ensures that all bits in output 374 are allocated in P and Q, and that the lengths of P and Q differ by at most one bit.<u style="single">Communication procedure</u>Figure 4 shows step 400 used by country X sender 102 (Figure 1) who wants to send a message encrypted using an independently specified session key to country Y recipient 104. Shown. The inputs to step 400 are (1) a sensitive key, (2) an application-specific portion of the recovery information, and (3) an optional confidential random salt. Salt is a random value used to increase the randomness of plaintext. Salt is used only once. Confidential random salt is called SALT0 when given to the procedure. Otherwise, SALT0 is pseudo-randomly derived from the specified sensitive key as described below. Referring to FIG. 4, the sender 102 and the receiver 104 first establish a confidential session key K (step 402). Sender 102 and recipient 104 can use any key distribution or key matching procedure they desire to establish a key K. Generally, the session key K is a symmetric encryption key used by the sender 102 to encrypt a message to the receiver 104 and by the receiver to decrypt the message from the sender. When using the public key as the session key, the procedure is used by defining K = (PKa, SKa). PKa is the public encryption key used by sender 102 and SKa is the corresponding sensitive decryption key used by recipient 104. Sender 102 then uses the sensitive session key K and the key reversal function 300 (Figure 3A) to use Country X's first and second key recovery agents 108, 110 (sender's key recovery agents). Generate P and Q values for, and P and Q values for the first and second key recovery agents 112, 114 (recipient key recovery agents) in country Y (step 404). Although this example shows only two key recovery agents per country, any number of key recovery agents can be used as described in the description of the key inversion function 300. Sender 102 then sends the confidential session key Use K to generate multiple salt values as described below (step 406). Referring to FIG. 6, sender 102 uses the generated salt value together with the public key and other information of key recovery agents 108-114 for the encrypted P and Q values of country X. Generate 602, 604 and country Y encrypted P and Q values 606, 608 (step 408). Using this information, sender 102 generates session context 612 (Figure 6), which consists of a concatenation of encrypted P and Q values 602-608 and recovery information 610 (step 410). .. Referring to FIG. 7, sender 102 then uses the private signature key to generate a digital signature 614 for session context 612 (step 412). This is done in the usual way by generating a hash of session context 612 and encrypting this hash with the sender's private signature key. The session context 612 and the signature 614 for this context are then concatenated to form the session header 616 (step 414). The digital signature 614 allows the recipient 104 to validate the session context 612 with a valid copy of the sender's public verification key. However, the digital signature 614 is only an option and can be omitted from the session header 616 if desired. Then, referring to FIG. 8, the sender 102 then uses the session key K to encrypt the first message (message 1) to generate the encrypted first message 618 (step 416). Finally, the sender 102 can send the receiver 104 a packet 620 consisting of the session header 616 and the encrypted first message 618 (step 418). FIG. 5 illustrates step 500 that recipient 104 follows when it receives message packet 620 from sender 102. Session header 616 in session context 612 If the signature 614 is included, the recipient 104 first validates the signature using the sender's public verification key (step 502). This is usually done by generating a hash of session context 612 using the same hash function as the sender, decrypting signature 616 using the sender's public verification key, and comparing the results for equality. It is done in form. If the two results do not match (step 504), it indicates that either session context 612 or signature 614 was corrupted during transmission, and recipient 104 exits without further processing the message (step 518). .. If not, or if the signature is not used, recipient 104 proceeds to the next step. Following the signature check, the recipient 104 validates the encrypted P and Q values 602-608 received by repeating the steps performed by the sender 102. That is, recipient 104 generates P, Q, and R values from confidential session key K (step 506) and salt values from key K (step 510). Steps 506-510 are the same as steps 404-408 performed by sender 102. Recipient 104 then compares the thus generated encrypted P and Q values to a pair of encrypted P and Q values 602 to 608 received from sender 102. The recipient also checks the recovery information 610 received from the sender to see if it matches similar information maintained by the recipient (step 1108). If the validation of the encrypted P and Q values 602-608 and the recovery information 606 received from the sender 102 is successful (step 514), the recipient 104 is required to decrypt the first message. Proceed to the final step of enabling the sensitive session key K to use (step 516). Otherwise, recipient 104 cannot verify that the values 602-610 required for key recovery have been sent and exits the procedure without further processing the message (518). The above procedure (Figs. 4 to 5) So assume that the sender 102 and the receiver 104 had previously established a sensitive session key K using any key transfer or key matching procedure. Alternatively, the key K can be generated by the sender 102 independently of the receiver 104 and included as part of the transmit packet 620. Next, the changes associated with key establishment will be described in this procedure. Now assume that the sensitive value is shared between the sender and the receiver. The inputs to the system are (1) the recipient's public key to be used to send the key from the sender to the recipient, and (2) the application-specific part of the recovery information. In this case, the key recovery system will generate a sensitive session key K and a random secret SALT0. The sender 102 encrypts the session key K using the public key of the recipient 104 and includes the encrypted session key as an additional part (not shown) of the session context 612. The session key K is encrypted with the following values: K'= ePUb (H (T1); K; SALT0; SALT) In the above equation, K'is the encrypted session key. PUb is the public key of recipient 104. H (T1), K and SALT0 are those defined earlier. SALT is an additional 160-bit sensitive random value that does not correlate with SALT0 or K. SALT guarantees the security of K and SALT0 exchanged between the parties. K is preferably encrypted using the encryption procedure (described below) used to encrypt the P and Q key recovery values. Recipient 104 recovers the session key from session context 612 by decrypting it using its secret decryption key according to signature validation steps (504-506). Otherwise, use the same procedure as shown in Figures 4 and 5. SALT) In the above formula, K'is the encrypted session key. PUb is the public key of recipient 104. H (T1), K and SALT0 are those defined earlier. SALT is an additional 160-bit sensitive random value that does not correlate with SALT0 or K. SALT guarantees the security of K and SALT0 exchanged between the parties. K is preferably encrypted using the encryption procedure (described below) used to encrypt the P and Q key recovery values. Recipient 104 recovers the session key from session context 612 by decrypting it using its secret decryption key according to signature validation steps (504-506). Otherwise, use the same procedure as shown in Figures 4 and 5.<u style="single">Recovery information</u>With reference to FIG. 9, recovery information 610 allows (1) the recipient 104 to see the encrypted P and Q values 602-608 for each key recovery agent 108-114, and (2) It is provided so that the key recovery agent can perform an integrity check on the decrypted P and Q values. Sender ID 902 allows recipient 104 to obtain the public key proof required to verify the optional signature 614 generated by sender 102 for session context 612. Recipient ID 906 allows recipient 104 to determine that message 620 is actually directed to itself. The source country ID904 and the destination country ID908 reproduce the equivalent encrypted P and Q values and compare for identity with the received encrypted P and Q values 602-608. This allows the recipient 104 to see the contents of session context 612. The sender's key recovery agent group 910 is the sender's first key recovery agent ID 912, the sender's first key recovery agent header 914, the sender's second key recovery agent ID 916, and the sender's. It consists of a second key recovery agent header 918. The recipient's key recovery agent group 920 is the recipient's first key recovery agent ID 922, the recipient's first key recovery agent header 924, the recipient's second key recovery agent ID 926, and the recipient's. It consists of a second key recovery agent header 928. Sender and recipient first and second key recovery agent IDs 912, 916, 922, 926 allow recipient 104 to verify that the authentic key recovery agent is being used according to the key recovery procedure. .. The key recovery agent ID also allows you to obtain a public key proof for each key recovery agent. The key recovery agent ID is also which key recovery agent is the user's P and Q Allows law enforcement agents to know if a value can be decrypted. Set the default key recovery agent ID for each user to X. It can also be included in the extension of the 509 version 3 certification. The sender and receiver first and second key recovery agent key headers 914, 918, 924, 928 contain information about public keys belonging to the key recovery agent. Referring to FIG. 10, each key header contains the encryption algorithm ID 946 (which specifies the public key algorithm to be used), the key length 948 in bits of the public key, and the key ID 950. Key ID 950 allows the recipient to determine the public key that encrypts the values of P and Q. The recipient needs these public keys to verify the encrypted P and Q values 602 and 604. Key ID 950 allows the key recovery agent to determine the public key that encrypts the P and Q values, and thus the private key needed to decrypt the P and Q values. The unique session ID 930 allows senders and recipients to commit sessions. The key encryption period 932 is specified by the start and end dates and times of key usage. The value of P or Q will not be released unless the duration of the court order overlaps part of the encryption period of the key. The key recovery system enforces a relatively short cryptographic period (eg less than a day), which is a national policy decision. This helps ensure that the session context is dynamically established and transmitted between the sender and the recipient. This also guarantees better security protection for frequent key changes. The generation date and time 934 indicates the date and time (UTC coding) when the session context was generated. The recipient checks date and time 934 as part of the integrity check. The date and time must come within the period of the court order to access the value of P or Q. The session key header 936 includes the session encryption algorithm ID 938, the session key length in bits 940, and the session key ID 942. Session key length 940 depends on the government if the key needs to be recalculated from the value of P or Q Is needed. The session encryption algorithm ID 938 is required by the government when R needs to be calculated thoroughly. The cryptographic algorithm ID allows the key recovery procedure to be parameterized. That is, the sizes of P, Q, and R can depend on the cryptographic algorithm used for data encryption. Recovery information 610 originates from various sources. Therefore, the key headers 914, 918, 924, 928 and encryption period 932 can be listed in the policy table 1200 (Figure 12) described below. The generation date and time 934 originates from the cryptosystem itself. The key recovery agent IDs 912,916,922,926 and hash IDs can be generated from the application or can be preconfigured, and the remaining entries can be generated from the application.<u style="single">P-value and Q-value encryption</u>Next, the procedure (steps 408 and 510) for generating the encrypted P and Q values 602 to 608 will be described. In the following, the encryption of the input X by the key K is shown by eK (X). "E" indicates encryption, and eK (X) = Y is the output. Decryption of Y by key K is indicated by dK (Y). "D" indicates cryptanalysis. Public key cryptography uses a pair of public and private keys (PU, PR) for encryption / decryption. The encryption of input X by the public key PU is shown by ePU (X). Decryption of Y by private key PR is shown by dRP (Y). The encrypted P and Q values 602 to 608 are defined as follows. Px'= ePUx1 (H (T1); Px; SALT &lt;for Px&gt;) Qx'= ePUx2 (H (T1); Qx; SALT &lt;for Qx&gt;) Py'= ePUy1 (H (T1); Py; SALT &lt; for Py&gt;) Qy'= ePUy2 (H (T1); Qy; SALT &lt;for Qy&gt;) In the above equation, PUx1 is the public key of Key Recovery Agent 1 in Country X. PUx2 is the public key for Key Recovery Agent 2 in Country X. PUy1 is the public key for Key Recovery Agent 1 in Country Y. PUy2 is the public key for Key Recovery Agent 2 in Country Y. H (T1) is a 160-bit non-confidential hash value. T1 is non-confidential recovery information 610 (Fig. 9). Px and Qx are P-values and Q-values that can be used by a key recovery agent authorized by Country X. Py and Qy are P-values and Q-values available to country Y-authorized key recovery agents. Px', Qx', Py', Qy'are encrypted versions of Px, Qx, Py, Qy. SALT &lt;for Px&gt;, SALT &lt;for Qx&gt;, SALT &lt;for Py&gt;, and SALT &lt;for Qy&gt; are 160-bit confidential derived values. The encryption procedure used is ANSI X9.44RSA Key Transport draft standard, and the 1996 DB in San Francisco, Calif., Which is part of this specification by reference. The Enhanced Optimal Asymmetric Encryption (EOAE) procedure detailed in Johnson and SM Matyas' Enhanced Optical Asymmetric Encryption: Reverse Signatures and ANSI X9.44, Proceedings of the 1996 RSA Data Security Conference is preferred. However, other procedures can be used instead. H (T1) is a hash value calculated from the recovery information 610 (T1) using the public one-way hash function. H (T1) gives the form of "reverse signature" for the information in T1. Reverse signatures tightly bind information confidentially. Anyone can calculate the reverse signature, but either knows all the secrets in the encrypted block (so it can be regenerated using the public key) or knows the private key ( Only users (thus who can recover confidentiality directly) can verify the reverse signature. For more information on reverse signing, see the DB above Seen in Johnson and SM Matyas treatises. SALT0 is a 160-bit secret random value that is specified as an additional input to the encryption procedure or is pseudo-randomly generated from the sensitive session key K. The present invention allows senders and receivers to establish a sensitive value for SALT0 regardless of session key K. For example, a party can generate SALT0 using bits from the Diffie-Hellman procedure that are not used to generate key K. Generating SALT0 in this way independently of session key K can provide additional protection against a type of cryptanalysis attack. If SALT0 is generated from confidential session key K, it is generated by hashing (K || H (T1) || public header) with SHA-1. However, H (T1) is defined as above, and the public header is an 8-byte structure defined as follows. 1-byte identifier: "Salt 0" ID 7 bytes Reserved: Set to 0 SHA-1 is a cryptographically strong hash algorithm, the Secure Hash Algorithm (SHA-1). As expected. However, you can use any suitable strong cryptographic hash function instead of SHA-1. SALT0 is used as input to the public one-way function to generate additional salt values: SALT &lt;for Px&gt;, SALT &lt;for Qx&gt;, SALT &lt;for Py&gt;, SALT &lt;for Qy&gt;. The one-way function makes it easy to calculate SALT &lt;for Px&gt;, SALT &lt;for Qx&gt;, SALT &lt;for Py&gt;, SALT &lt;for Qy&gt; from SALT0, but any of these derived salt values It is computationally impossible to generate SALT0 from it. Salt (SALT &lt;for Px&gt;, SALT &lt; for Qx&gt;, SALT &lt;for Py&gt;, SALT &lt;for Qy&gt;) protects encrypted P and Q values 602-608. Salts (SALT &lt;for Px&gt;, SALT &lt;for Qx&gt;, SALT &lt;for Py&gt;, SALT &lt;for Qy&gt;) are specially configured to have different values. If SALT0 is a sensitive random value specified as input to the encryption procedure, this means that all blocks to be encrypted for the key recovery agent depend on SALT0 (a sensitive random 160-bit value unrelated to the key). Guarantee to have sex. If SALT0 is pseudo-randomly generated from the key, this ensures that every block to be encrypted to the key recovery agent has a pseudo-random dependency on the entire key. H (T1) is contained in the encrypted P and Q values 602-608 and gives a strong bond of recovery information 610 to the encrypted P or Q value, thereby the encrypted P or Q. Gives the key recovery agent a means of determining whether the value of is satisfied with the stated conditions of the court order presented. Encrypted P and Q values 602-608 also include an indicator that specifies whether the encrypted value is a P or Q value. Referring to FIG. 11, the H (T1), P or Q values, indicators, and salts are formatted in blocks (1102), with 0 bits embedded on the left as needed, preferably the DB above. It is encrypted with the public key of the key recovery agent using the Enhanced Optimal Asymmetric Encryption (EOAE) procedure described in Johnson et al. As described in that document, the EOAE procedure first applies the formatted block 1102 to multiple masking rounds 1104 (one half input is used alternately to mask the other half input). The result of the masking round is then encrypted (1106). The randomly appearing salts used in the encrypted Px, Qx, Py, and Qy values are generated so that the recipient can verify that they are accurate. This is done by encrypting the plaintext values with the key recovery agent's public key and comparing them for identity with the received values, as the recipient does not know the private keys that belong to the key recovery agent. This is made possible by deriving the salt in the encrypted Px, Qx, Py, Qy values from SALT0. Suppose Uv represents one of the values of P and Q in the set (Px, Qx, Py, Qy). The salt value used to encrypt the Uv, indicated by Salt &lt;for Uv&gt;, is the SHA-1 of the data (SALT0 || Uv || Key Recovery Agent ID || Sender or Recipient ID || Public Header). Defined as a hash. The sender's ID is used when the salt should be used for encryption for the sender's key recovery agent. Otherwise, the recipient's ID is used. The public header has an 8-byte structure defined as follows. 1-byte identifier: "SALT" ID (for all salts except SALT0) 1-byte Chain value: 0, 1, etc. indicating the order of encrypted blocks when there are many blocks. 1 byte Last chain: Number of last chain values 5 bytes Reserved: According to this technique, which is set to 0, each derived salt value of the encrypted Px, Qx, Py, and Qy values appears independently. Rogue key recovery agents cannot use derived salt values to reduce the security of other encrypted P or Q values. To supply a value of P or Q to an authorized requester, the key recovery agent can also supply the derived salt used, so the authorized requester can recover the key. The public key can be used to verify that the correct decryption was done by the key recovery agent. If the length of P or Q is greater than m (m is the maximum length of P or Q that can be encrypted with the intended public key of the key recovery agent), the value (P or Q) is split into blocks of m bits. Will be done. The last block is a short block. If there are "i" such blocks, then "i" different salt values are calculated so that different (but predictable) salt values are calculated for each mbit block to be encrypted. Guarantee. For example, suppose m = 256 and P is 512 bits long. In that case, P is divided into two blocks of size 256 bits and the two salt values are calculated using the algorithm described above. The first salt value is calculated using a header with a chain value of zero (0). The second salt value is calculated using a header with a chain value of 1. In this case, the two headers are equal except for the chain value. The "last chain" is the number of last chain values. For example, if there are "i" blocks to chain, the "last chain" value is i-1. The "Last Chain" field ensures that all encrypted blocks in a given chain are considered. It can be verified that the decryption was performed by the key recovery agent. If the length of P or Q is greater than m (m is the maximum length of P or Q that can be encrypted with the intended public key of the key recovery agent), the value (P or Q) is split into blocks of m bits. Will be done. The last block is a short block. If there are "i" such blocks, then "i" different salt values are calculated so that different (but predictable) salt values are calculated for each mbit block to be encrypted. Guarantee. For example, suppose m = 256 and P is 512 bits long. In that case, P is divided into two blocks of size 256 bits and the two salt values are calculated using the algorithm described above. The first salt value is calculated using a header with a chain value of zero (0). The second salt value is calculated using a header with a chain value of 1. In this case, the two headers are equal except for the chain value. The "last chain" is the number of last chain values. For example, if there are "i" blocks to chain, the "last chain" value is i-1. The "Last Chain" field ensures that all encrypted blocks in a given chain are considered. It is possible to verify that the decryption was performed by the key recovery agent. If the length of P or Q is greater than m (m is the maximum length of P or Q that can be encrypted with the intended public key of the key recovery agent), the value (P or Q) is split into blocks of m bits. Will be done. The last block is a short block. If there are "i" such blocks, then "i" different salt values are calculated so that different (but predictable) salt values are calculated for each mbit block to be encrypted. Guarantee. For example, suppose m = 256 and P is 512 bits long. In that case, P is divided into two blocks of size 256 bits and the two salt values are calculated using the algorithm described above. The first salt value is calculated using a header with a chain value of zero (0). The second salt value is calculated using a header with a chain value of 1. In this case, the two headers are equal except for the chain value. The "last chain" is the number of last chain values. For example, if there are "i" blocks to chain, the "last chain" value is i-1. The "Last Chain" field ensures that all encrypted blocks in a given chain are considered. Calculated using the data. The second salt value is calculated using a header with a chain value of 1. In this case, the two headers are equal except for the chain value. The "last chain" is the number of last chain values. For example, if there are "i" blocks to chain, the "last chain" value is i-1. The "Last Chain" field ensures that all encrypted blocks in a given chain are considered. Calculated using the data. The second salt value is calculated using a header with a chain value of 1. In this case, the two headers are equal except for the chain value. The "last chain" is the number of last chain values. For example, if there are "i" blocks to chain, the "last chain" value is i-1. The "Last Chain" field ensures that all encrypted blocks in a given chain are considered.<u style="single">Enhanced Optimal Asymmetric Encryption (EOAE) Procedure</u>The extended optimal asymmetric encryption (EOAE) procedure of the present invention is described in M. Bellare and P. Bellare (described in DB Johnson et al.). It differs from Rogaway's traditional Optimal Asymmetric Encryption (OAE) procedure in that it uses a hash of control information in place of the OAE's non-adaptive bits. In the case of the present invention, the non-adaptive bit is replaced with a hash of H (T1), that is, recovery information (T1) 612 (Fig. 9). Certain embodiments of EOAE also differ from OAE in other respects. In OAE, input X is processed by first adding a secret random number (RN) to input X to form X || RN. However, the length of the RN is equal to the length of the hash algorithm you are using (for example, 128 for MD5 and 160 for SHA-1). However, the X value to be encrypted by the key recovery system already has a confidential random salt value as the rightmost (lowest) part of each X value. Input X does not need to have an additional sensitive random value. Therefore, if X is the input to be processed by EOAE, first rewrite X as X = X'|| Salt. However, X'is an OAE input, and Salt is a random number generated by OAE and added to X'. Then process X'|| Salt in the usual way with OAE (ie, use Salt as a seed to generate a masking value to mask X', and hash the masked X'with SHA-1. To generate the hash value used to mask the Salt). Specific details of the masking part of EOAE and OAE processing are shown in the following description of the Shehri function.<u style="single">Communication scenario</u>As explained below, various communication scenarios are possible. In many cases, mobile users must make recovery information available not only to end-user agents, but also to base (ie, infrastructure features that connect airlinks and wired networks) agents. In systems that perform key distribution using symmetric key cryptography, such as Kerberos, the same information is stored and given by the Key Distribution Center (KDC). The KDC also prepares encrypted P and Q values. A special key recovery version of Kerberos is required to perform integrity checks on encrypted P and Q values. A multicasting scenario has one sender and many recipients. It is treated as a duplicate of a single session or as a collection of recipients. In the former case, each recipient gets a copy of the encryption to the sender's key recovery agent and an encryption to his own agent. In the latter case, each recipient gets all P, Q encryption and verifies the encryption of itself and the sender. There is also the option of having a special agent for multicasting across many countries to aid in scalability.<u style="single">Global communication policy table</u>With reference to FIG. 12, the information required for the key recovery system of the present invention is stored in table 1200, which is called the global communication policy table. Table 1200 is for illustration purposes only. In a practical embodiment, the data will probably be properly stored in a separate table, some specifying the public key of the key recovery agent and some specifying the rules. Table 1200 contains information that allows the system to calculate the key size and P, Q, R for specific algorithms and users in different countries. Table 1200 also contains the public keys of the key recovery agents authorized by country. The numbers in the table 1200 are merely examples to illustrate the flexibility that the present invention allows. There are virtually no restrictions on the type. In particular, each country can have a large number of key recovery agents. In interlateral communications, the key recovery system can determine the recipient's country ID 908 (Figure 9) from the recipient's public key proof or equivalent system configuration information. Using the sender's source country ID and recipient's destination country ID, as well as the algorithm ID of the intended cryptographic algorithm that the sender and receiver should use, the key recovery system is (1) the sender and Determine the maximum key length that the recipient can use, (2) the allowed R value that may differ between the sender and the receiver, and (3) the required key recovery agent ID required for the key reversal function. The key recovery system then sends this information to the key inversion function. The key length is the smaller of the two key length values. For example, in country X and country Y, if the DES key value is 64-bit and 128-bit, then 64 is the value used.<u style="single">Collaboration with other systems</u>The "PQR" key recovery system of the present invention provides limited collaboration between it and other "non-PQR" systems. Therefore, sender 102 can be determined by (1) when the sender and receiver each use a PQR system, (2) when the sender and receiver each use a non-PQR system, or (3) when the sender uses a PQR system. If the system is used and the recipient uses a non-PQR system, the encrypted message can be sent to the recipient 104. If the sender uses a non-PQR system and the recipient uses a PQR system, the sender cannot send encrypted messages to the recipient. Basically, the recipient's PQR system attempts to verify that the sender's system has generated a valid PQR "key blob". Otherwise, the recipient's PQR system will not make the key available to the recipient's application in a form that can be used to decrypt the data received from the sender.<u style="single">Key recovery procedure</u>An authorized law enforcement agent obtains a guarantee or court order to access the encrypted data of a particular suspect for a particular period of time. The law enforcement agent has access to encrypted information about the suspect, including the session context. The law enforcement agent can verify that the user ID and date and time values are valid, that is, specified in a warrant or court order. Other public information can be confirmed as appropriate. The law enforcement agent provides the session context with the appropriate key recovery agent along with a warrant or court order. The key recovery agent validates the recovery information, including the user ID and date and time, to ensure that all requirements of the warrant or court order have been met. This is done by checking the hash identity of the decrypted H (T1) and the received recovery information (T1). The key recovery agent then recovers the P and Q values and returns the values and associated salts to the law enforcement agent. The key recovery agent may also sign the decrypted information and then release it, thereby proving the time and date when the key recovery took place. The law enforcement agent can verify that the key recovery agent returned the correct P or Q value by regenerating the encrypted P or Q from the plaintext value. After assembling all the required P and Q values, the law enforcement agent executes a key inversion function to regenerate F (P, Q), derives the key, and decrypts the information. A thorough search for R can be performed. Since a thorough search of R is required, the cost of key recovery is high even if the key recovery agent colludes.<u style="single">Cryptographic system embodiments</u>FIG. 13 shows a possible embodiment 1300 of a key recovery system within a cryptographic system. The key recovery system 1300 interacts with encryption / decryption functions that are called through application programming interfaces (APIs). That is, the session or file key processed by the key recovery system 1300 is a data key that is made available for use only by the encryption / decryption function. The enablement process is only allowed through the key recovery system 1300. FIG. 13 shows four new cryptographic services: PQR generation service (1310), PQR verification service (1320), PQR encryption service (1330), and PQR decryption service (1340). The PQR generation service 1310 generates a set of P, Q, and R values from the input key K. The PQR generation service (1310) also converts the key K into a form K'that works in the PQR encryption service 1330. The PQR verification service 1320 verifies a set of P, Q, and R values, and when the verification is successful, converts the key K into a form K'that works in the PQR decryption service 1340. The PQR Cryptography Service 1330 and PQR Cryptanalysis Service 1340 are the same as the regular Cryptography Service and Cryptanalysis Service, but in a special transformed form where the input key is recognized by the PQR Cryptography Service and PQR Cryptanalysis Service. Must be. The key K will not work properly in the PQR encryption service 1330 and the PQR decryption service 1340 unless it is first converted to the form K'.<u style="single">Shehri function</u>FIG. 14 is a high-level block diagram of the Shehri function 304 used in the key inversion function 300 (FIG. 3A). As mentioned above, the Shehri function 304 transforms the n-bit input X into a "shuffled" n-bit output Y. The n-bit input X (including an even number of octets) is split into a left half XL (1402) and a right half XR (1404). XL and XR each contain n / 2 bits. In the particular example shown in FIG. 14, the bit lengths of XL (1402) and XR (1404) are the same as the length of the hash value (160 bits) generated by the hash function used. Procedures for XL and XR with other bit lengths are further described below. In hash iteration 1, XR (1404) is hashed (1406) to generate a 160-bit hash value H (XR) (1408), which is XORed with XL (1402) (1410). , Produces a once masked output mXL (1412). In hash iteration 2, mXL (1412) is hashed (1414) to generate a 160-bit hash value H (mXL) (1416), which is XORed with XR (1404) (1418). , Produces a once masked output mXR (1420). In hash iteration 3, the mXR (1420) is hashed (1422) to produce the 160-bit hash value H (mXR) (1424), which is exclusively ORed with the once masked output mXL (1412). 1426) is taken to produce a twice masked output mmXL (1428). The output Y is composed of the once masked output mXR (1420) and the twice masked output mmXL (1428), and the following equation holds. Y = mmXL || mXR Figure 15 shows the inverse Shehri function 1500 that "unshuffles" mmXL || mXR to recover the original input XL || XR. In the inverse Shehri function 1500, the hash iterations 1-3 (1406, 1414, 1422) of the Shehri function 304 are of hash iterations 3, 2, 1 It is carried out in the reverse order. In hash iteration 3, mXR (1420) is hashed (1502) and recovers the 160-bit hash value H (mXR) (1504), which is XORed with mmXL (1428) (1506). , Recover mXL (1508). In hash iteration 2, mXL (1508) is hashed (1510) and recovers the 160-bit hash value H (mXL) (1512), which is XORed with mXR (1420) (1514). , Recover the original input XR (1516). In hash iteration 1, XR (1516) is hashed (1518) and recovers the 160-bit hash value H (XR) (1520), which is XORed with mXL (1508) (1522). , Recover the original input XL (1524). Next, the processing when XL and XR are not each composed of 160 bits will be described. The procedure as a whole is as described above. The n-bit input X (including an even number of octets) is divided into a left half XL and a right half XR, and XL and XR each contain n / 2 bits. The XL is masked using XR to generate a once masked XL, and then the XR is masked using the once masked XL. The masked XR is then used to further mask the once masked XL to produce a twice masked XL. However, to address the block size of the hashing algorithm, XL and XR are each processed in consecutive chunks. Referring to FIG. 16, since XL is masked using XR, XL is first separated into i blocks consisting of k or less bits. Here k is defined as the block size of the hash algorithm. For example, if SHA-1 is a hash algorithm, then k = 160. If MD5 is a hash algorithm, then k = 128. Unless otherwise stated herein, SHA-1 is the hash algorithm used by the Shehri function. Where n is a multiple of k If so, each block contains k bits. If n is not a multiple of k, XL consists of one short block i (&lt;k bits) and optionally one or more k-bit blocks. If a short block exists, it is constructed from the most significant bit of XL. The hashed input is defined as: Input = XR || Public Header In the above formula, the public header has the following 10-byte coded structure. 1-byte identifier: "Shafra" ID 4-bit iteration: 1 = First iteration 4-bit Algorithm: Hashing algorithm ID 4-byte Counter: 1, 2, etc. The counter matches the number of blocks in the masked XL. 4-byte length: Key length expressed in bits (also indicates whether 0 embedding was performed when k = odd number). The maximum key length per header is 232 bits. The masking operation is executed as follows. Initially the counter is set to 1 and the input (XR || public header) is hashed with SHA-1 to generate a 160-bit hash H1. H1 is XORed with block 1 from XL to produce masked block 1 (represented by mblock1). The counter is then incremented to 2 and the input (XR || public header) is hashed with SHA-1 to generate a 160-bit hash H2. H2 is XORed with block 2 from XL to produce masked block 2 (represented by mblock2). The operation continues in this way until the last block (block i) is masked. The last block is the j bit (j &lt; In the case of a short block containing k), the block i is masked by exclusively ORing the least significant j bit of Hi with the block i to generate a masked block i (represented by mblock i). The masked XL (consisting of the concatenation of masked blocks 1 to i) is represented by mXL. The XR masking operation using the masked XL (represented by mXL) is performed in the same way. The XR is split into blocks in the same way that the XL is split. The actual mask operation is also performed in the same way, except that the number of iterations in the public header is set to 2 (representing "second iteration"). In this case, the public header is postfixed to mXL. The input to be hashed is: Input = mXL || Public Header In the above formula, the number of iterations in the public header is set to 2, which stands for "second iteration". The counter is reset and incremented to 1, 2, etc. as before. The mask operation consists of hashing the input and exclusively ORing the resulting hash value with the block in the XR. Masked XR (consisting of the concatenation of masked blocks 1 to i) is represented by mXR. The value mXL is masked with mXR in the same way that XL was masked with XR, except that the number of iterations in the public header is set to 3 (representing "third iteration"). The masked mXL is represented by mmXL. The output of the Shahula is mmXL || mXR. It is incremented to 2 and so on. The mask operation consists of hashing the input and exclusively ORing the resulting hash value with the block in the XR. Masked XR (consisting of the concatenation of masked blocks 1 to i) is represented by mXR. The value mXL is masked with mXR in the same way that XL was masked with XR, except that the number of iterations in the public header is set to 3 (representing "third iteration"). The masked mXL is represented by mmXL. The output of the Shahula is mmXL || mXR. It is incremented to 2 and so on. The mask operation consists of hashing the input and exclusive-ORing the hash value thus generated with the block in the XR. Masked XR (consisting of the concatenation of masked blocks 1 to i) is represented by mXR. The value mXL is masked with mXR in the same way that XL was masked with XR, except that the number of iterations in the public header is set to 3 (representing "third iteration"). The masked mXL is represented by mmXL. The output of the Shahula is mmXL || mXR.<u style="single">Public header</u>Each public header described herein has a 1-byte identifier field. The identifier field is defined as follows: X'01'"Salt 0" X'02' "Salt" other than Salt 0 "Salt" X'03'" PQ key recovery agent ID" X'04' "Shahula"<u style="single">Miscellaneous</u>Each user's public key certification complies with the X.509 version 3 certification standard, and the v3 extended version has some kind of key recovery procedure such as user ID, country ID, first key recovery agent ID, second key recovery agent ID, etc. It is intended to be able to retain the necessary information. It is also intended that sender and recipient public key proofs can be used in key recovery systems. Therefore, when the user's public key becomes available for the purpose of performing key distribution, the information required to perform key recovery is also available and can be validated. The proof seems to be the natural place to carry this information. By incorporating the user's key recovery information into its public key proof, the user is less likely to abuse the recovery system, for example by claiming a different country ID with a more favorable key recovery option.<u style="single">attack</u>There are several possible types of attacks against the disclosed key recovery system. Some are based on rogue key recovery agents. If a single key recovery agent is a rogue and reveals a P-value for a user, the Q-value is still unknown to the attacker and should not be a problem. Without knowing Q or R, the attacker has the same problem as determining the entire key. Therefore, this partial recovery solution is preferred over the method in which the key recovery agent recovers the entire key. The rogue key recovery agent cannot analyze another encrypted P or Q using the salt value associated with the encrypted P or Q. This is because each salt is derived by passing SALT0 through the one-way function. Therefore, each salt appears to be independent. If (nr) is a small value, a rogue agent may try omnidirectional shuffling across all F (Px, Qx) to find its decrypted P. This attack is F (P, Q, Prevented by including R). Other attacks are based on unauthorized users. If both sender 102 and receiver 104 are fraudulent, they can use their cryptographic methods to bypass any software system checks. The present invention does not attempt to prevent attacks when both users are fraudulent. This is a basic premise to make things easier. If the sender 102 is invalid and does not send the key recovery information 610 (Figs. 6 and 9), the recipient 104 cannot validate it. If a rogue transmission is detected, the decryption process will not be enabled. If the recipient 104 is invalid and does not validate the key recovery values, the sender 102 is still sending those values and making them accessible as needed. Dynamic and frequent sessions limit the cryptographic period and help the session context to access it. Other attacks are possible. One of them is the so-called "squeeze attack". Y. Frankel and M. Jung, "Escrow Encryption Systems Visited: Attacks, Analysis and Designs", Crypto '95 Conference Proceedings, August 1995 showed how to transfer keys between sessions so that session headers can be identified by other users. To avoid such attacks, it is recommended that users use active key distribution methods (eg, based on the Diffie-Hellman key exchange) when there is concern that the key has been abused. By signing the exchange, session information, party ID, and messages during the session to identify their source, the user will not be able to open them by the recovery agent unless the user himself has been tapped. Can be done. This compensates for the fact that the message is combined with that source and the message from the non-eavesdropped source is not considered valid as required by the minimization principle in the connection (ie listening only to the suspicious). To do. Some applications should also require the other party to sign session-headers, etc. to ensure the authenticity of the two endpoints. These communications applications are protected because the signature is uniquely generated by the two parties. Some sort of attack is possible when a "fake agent" duplicates an agent's key. Therefore, it is assumed that the agent key table contains keys that have been verified to belong to an agent in a real country. It is also possible that a "non-fresh" key will be inserted into the key management procedure. Therefore, it is recommended that the session ID in an interactive application be derived from "fresh information" or the date and time. With proper "key distribution" mechanisms, freshness is ensured on its own. In the non-interactive version, the session ID can be derived from the date and time and related to the date and time, and can be checked by the recipient's application (based on the expected delay expected by that application). As for how encryption for key recovery helps attackers in pre-established key scenarios, All public key encryption under the agent's key is different, and also depends on the 160-bit random number SALT0 and part of the key, or if the key is the only input to the process. Is made dependent on the "whole key" by pseudo-random derivation of the salt. This ensures that, as far as we can understand, encryption against the agent does not derive an attacker "search space" that is smaller than the key itself. The use of this variability and optimal asymmetric encryption ensures that the various plaintexts to the agent are pseudo-randomly independent of each other.<u style="single">Conclusion</u>The benefits of this key recovery system will be reiterated. This system supports a large number of algorithms. Supports any key distribution procedure and provides it if it is not available. Supports a large number of key recovery agents. It can support many countries and handle the special requirements of one country. The system is also self-contained, where the recipient validates the "enabled" value for the key recovery agent. In contrast to using exportable cryptographic specifications (eg 40-bit keys), the user pays the cost of doing more work on the user's system to all but the authorized entity. On the other hand, you get stronger encryption key strength. The user gains maximum strength according to the law. Law enforcement agents can verify that key recovery agents are giving them accurate information. It helps alleviate the worry that the key recovery agent is completely unreliable. In a key escrow system based on sending an encrypted key to an escrow agent, the cost is proportional to the number of sessions, whereas in this system the cost is proportional to the number of accesses. The "enabled" key is a session-level key. This allows for compartmentalization and proper access. Compartmentalization means that there is a natural time limit for the key, which corresponds closely to the allowed key recovery time frame. Proper access means that the key needed to reveal the encrypted data is recovered, rather than a more persistent key or a key for another user. On the other hand, recovering the private key of the public key algorithm is not a good idea as it allows access to encrypted messages received from others rather than messages sent to others. Also, these normally long-lived keys are frequently rolled over to ensure proper compartmentalization. More information on this subject can be found in the Frankel and Jung publications mentioned above, which are incorporated herein by reference. Various of the present invention A good example of modification will be apparent to those skilled in the art. The present invention can be implemented as hardware, software, or a combination of both. The shuffle procedure, hash procedure, and encryption procedure used may differ from those described above. Modifications that include additional strings and constants are also possible. Other modifications may come to mind to those skilled in the art.