JPH1028114A - Work quantity reducing method, ciphering secret key supply method, cipher system executing method, ciphered message data structure and computer medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To obtain a ciphering system capable of safe communication by deciding a first partial key by means of an authorized person or a corporation and supplying information for enabling the decoding of a ciphered message by means of the acquirement of the first partial key. SOLUTION: The secret key is a random number and is generated at every message in ST10 so as to cipher the message in ST12. The one-way hash of the secret key is generated in ST14 in order to facilitate a suitable section work quantity system. The secret key and a salt are ciphered through the use of the open key of a prescribed receiver. The secret key is divided into at least two partial keys in ST18 so as to permit the authorized person or the corporation to decode the message. The partial keys, the hashed and the whole or a part of solts are ciphered by using the open key in ST20. The ciphered value is transmitted to the receiver together with the ciphered message and the ciphering secret key in ST22. The receiver decodes the ciphering secret key where the secret key is used in ST24.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

TECHNICAL FIELD OF THE INVENTION

(Notes on Copyright) A part of this patent specification includes matters subject to copyright protection. Like publishing a patent file or registration at the Patent and Trademark Office, the copyright holder does not object to the reproduction of the patent specification by anyone, but retains all other copyrights.

The present invention generally provides cryptography, and in particular, cryptographic methods and systems that provide secure communication methods to unauthorized users while meeting governmental regulations on the use, export or import of strong cryptographic systems. Related to the field.

[0003]

2. Description of the Related Art Common types of cryptography include secret key cryptography and public key cryptography.
key cryptography). In secret key cryptography or symmetric cryptography, a message to be transmitted from a sender to a given recipient (referred to as "plaintext") is encrypted using a secret number or secret key, and the given recipient is Decrypt an encrypted message using the same secret key (also referred to as "cipher text" or "encryption"). Only private keys can be used to encrypt and decrypt messages, and other keys cannot decrypt messages. In this system, it is necessary to provide a secure means for a sender to notify a predetermined recipient of a secret key by, for example, a secure courier. A widely used secret key system is the Data Encryption Standard that uses a 56-bit key and 8 non-key parity bits.
dard, DES). DES was issued in 1977 as the United States Federal Information Processing Standard.

[0004] In public key (public key) cryptography or asymmetric cryptography whose copyright has been abandoned, a key different from the key used for decryption is used for encryption, and one key is logically derived from the other key. Can not. Each natural or corporate member participating in the public key system has two keys, the key used for encryption is made public, and the key used for decryption is kept secret. As a result, the sender can transmit a message to a predetermined recipient by encrypting the message with the recipient's public key, and only the recipient can decrypt the message using its own private key or private key. Central governments often encourage the use of public keys and issue certificates proving that the keys are authentic. One example of a commercially available public key system is described in US Pat. No. 4,405,829.
The SA algorithm, which can be implemented using RSA Data Security software of Redwood City, California.

[0005] Public key systems are frequently used to encrypt and transmit the private key used in the private key system. Public key systems are also used for digital signatures, in which the sender encrypts the signature using his private key. Since the signature can be decrypted only with the sender's public key, the recipient can use the sender's public key to verify the signature with the sender.

[0006] The degree of security or strength guaranteed by an encryption system is often evaluated by the number of bits in the key. For example, in a private key encryption system, a three-byte (24-bit) key is relatively simple by decrypting the message by trying each of 2 24 possible keys until the encryption is decrypted. Will be deciphered. This type of attack, which attempts to guess the key until a readable plaintext is obtained, is also referred to as a "brute-force attack" or "exhaustive cryptanalysis." In some public key systems, including RSA, encrypting the same value twice results in the same result. In these systems, an unauthorized user who knows the public key used to encrypt a message attempts various messages, encrypts each with the public key, and matches the resulting encrypted data. The encrypted message is decrypted by systematically comparing it with the encrypted message. Although the strength of the key size for different algorithms cannot be readily compared, the strength of a public key system depends on the key size. RSA requires a key size on the order of 500-1000 bits as a reasonable level of security against attacks.

[0007] The decryption of a cryptographic system, ie the decipherment of a message without all the cryptographic keys, or the average effort or work required to decipher the secret key of all or part of the cryptographic text, Work volume or work characteristics. This is evaluated in an appropriate unit such as, for example, the operation time on one or two or more fixed computer systems required for decryption of the encryption, and the cost in dollars. If the amount of work is large enough, the encryption system may not be practically or economically decipherable, which is said to be "economically infeasible".
Communication systems that use encryption mechanisms that are economically impractical to decipher are generally considered secure.

[0008] Of course, the amount of work required to decipher a given cryptographic system varies from time to time due to technological advances such as improvements in computer speed and capacity. For example, a 40-bit secret key encryption mechanism can now be decrypted in less than a year by a high-speed personal computer or in a short time by a room-full personal computer, while future computer technology advances This workload will be greatly reduced.

[0009] There is a great deal of literature on other background information and the state of the art of cryptography relating to said publications, for example US Pat. No. 4,908,861, 5,261,0.
02 and 5,323,464 and Gustavas J. Simmons, "Modern Cryptography: The Science of Information Security" (IEEE Press, 199).
2 years), which is referred to as the prior art in this specification.

[0010] Governments may impose restrictions on the use, export or import of cryptographic hardware and software with a high amount of work. For example, citing national security rights, for a number of reasons, the United States government has banned the export of certain cryptographic hardware, software, or technical data. Exports of these items are subject to the Arms Export Control Law (Vol. 22, Articles 2751 to 2794) and the International Trade in Weapons (Federal Law Enforcement Regulations, Volume 22, Articles 120 to 130). Regulated by the US State Department. The U.S. Department of State may delegate jurisdiction over certain cryptographic algorithms or products to the U.S. Department of Commerce, thereby requiring the Export Control Act (Vol. 50, U.S. Pat.
Article 2420) and export control of products are controlled.

Export of certain cryptographic algorithms or products with restricted key sizes from the United States is permitted. For example, algorithms RC2 and RC4 developed by RSA Data Security are currently licensed for export, subject to restrictions on keys having a length of 40 bits. As a result, many U.S. companies have one version with strong cryptography available for sale in the United States and another called "export", "short key" or "cryptolight" versions for overseas sale. Market two versions of one edition of the product. However, cryptolite systems generally do not provide adequate security against unauthorized users, and as a result, cryptolite systems do not sell well. The inability of U.S. companies to sell software products with strong cryptography in foreign markets effectively eliminates their ability to compete with foreign companies that do not face the same export restrictions. Other background information and effects on US export controls on the software market can be found in the Technical Assessment of Networked Environments, US Conference on Information Security and Privacy, OTA-TCT.
-606 (Washington US Government Printing Office, September 1994)
Mon) is described in Chapter 4 and is also quoted here.

[0012] In 1994, the Ministry of Commerce established the Federal Information Processing Standard as Escrowed Enc.
ryption Standard, EES) was approved. EES can be used to encrypt voice, facsimile, and computer data in telephone communications. EES specifies a symmetric encryption algorithm (called skipjack) that runs on a chip commonly known as a "clipper chip." Each EES chip has a chip-specific key that is divided into two parts after programming into the chip. Each part of the key is stored in one of the two designated governmental third party escrow agents (escrow agents), and when supervised, such as through investigation and authorization, the law enforcement agent You can obtain two parts from a third party deposit agent. The two parts are then recombined to form the entire key, and without further effort, the government uses it to decrypt the EES encrypted message.

It was the official purpose of the EES to be able to easily approve exports for strong encryption. However, for a number of reasons, there is a risk that the key may be erroneously disclosed by a third-party deposit agent or its employees due to accidents or other reasons, and that the International Bilateral Act on the needs of foreign governments be enforced. Because of the need to be established, third party key escrow systems such as EES are generally considered undesirable.

[0014] Accordingly, a cryptographic system that provides the advantages of both a short key system that properly refers to government security rights and a sufficient third party escrow system provided to securely communicate to unauthorized users. Is still needed. The present invention substantially solves these problems and provides an unprecedented cryptographic system.

[0015]

SUMMARY OF THE INVENTION It is a first object of the present invention to solve the above-mentioned problems associated with conventional encryption systems.

A second object of the present invention is to provide an encryption system for reducing, without removing, the amount of work required for decrypting an encrypted message by one or more authorized natural persons or corporations such as government organizations. It is to be.

A third object of the present invention is to provide an encryption system that can be legally exported from the United States and can communicate securely.

A fourth object of the present invention is to enable a US software developer to sell cryptographic software in a foreign market, effectively competing with a foreign software developer.

A fifth object of the present invention is to provide a cryptographic system with a fractional workload that does not require one or more authorizations to install and maintain a large key database.

A sixth object of the present invention is to provide an implementation method and system for use in an encryption system in which all or part of an encryption private key is encrypted with a public key of an authority and transmitted in an encrypted message. It is.

[0021]

SUMMARY OF THE INVENTION Some or all of the above and other objects of the present invention are provided by a method by which an authorized natural person or corporation reduces, but does not eliminate, the amount of work required to decrypt an encrypted message. Achieved. Here, the encrypted message requires an encrypted secret key to decrypt the message, and the encrypted secret key is supplied or notified to a predetermined recipient of the message other than the authorized natural person or corporation. The method according to the invention comprises the steps of dividing the encrypted secret key into at least two partial keys in order to reduce, without eliminating, the work required for decrypting the encrypted message by knowing the first partial key; Determining the first partial key by the identified natural person or legal entity and providing the authorized natural person or legal entity with information that can use the first partial key for decrypting the encrypted message.

In a preferred embodiment, the secret key is a random number (irregular number) or a pseudo-random number (pseudo-irregular number) generated by an unpredictable random number generator and used for encrypting a message (hereinafter, referred to as a pseudo-random number). The term "random" is used to encompass both true random numbers and pseudorandom numbers). The private key is encrypted using the predetermined recipient's public key and provided to the predetermined recipient along with the encrypted message. Thereafter, a given recipient can use the private key or the private key to decrypt the private key.

An authorized natural or legal person by direct transmission to an authorized natural or legal person is given a first partial key. In addition, the first partial key is encrypted using an authorized natural person or a public key of a corporation and attached to the encrypted communication message, and the natural message is obtained by obtaining the communication message by intercepting the communication message being transmitted. Alternatively, the legal entity may obtain the encrypted first partial key. The first partial key is a cryptographic combination such as a hash (hash, meaningless data) of the encrypted secret key described later, a hash of a secret key connected by a salt (salt, seasoned data) described later, or all or part of the encryption key. Together with additional information such as salt and control information. Also, when using a salt, the salt is encrypted with a private key that is encrypted using the public key of the given recipient.

Since the hash can be calculated by the recipient from the secret key and the salt, can be encrypted with an authorized natural or corporate public key, and can be compared with the encrypted hash and the partial key attached to the encrypted message. The use of a hash of encrypted partial key fields or other cryptographic combinations provides a method of implementing a partial key system. The use of a salt facilitates control of the amount of work required for a licensed natural or legal person to use a hash to decipher a message.
Another method of implementing the partial key system is to cryptographically combine the entire private key with a first partial key encrypted with a public key of an authorized natural person or corporation using a hash function or the like, and encrypting the header part of the message and the like. To provide a cryptographic connection with the message. The recipient's system can then reproduce (recalculate) the hash using the secret and encrypted partial keys and compare the hashed value with the hash value received with the encrypted message. If the numbers do not match, the recipient's system can reject the message.

The authorized natural or legal person may be an individual trustee who retains the partial key in the event that the entire private key is lost and should be recovered, or may use encryption hardware or a cryptographic key that uses an encryption key larger than a predetermined size. Use of software,
It may be a natural person or legal entity such as an individual or government holding a partial key that meets government regulations on imports or exports. In the latter case, the secret key is split as the size of the remaining partial key after splitting the first partial key from an encrypted secret key that is less than or equal to the restricted encryption key size. By forming multiple partial key fields, the system can supply multiple governments for multiple segmented workloads. Of course, it is necessary to obtain a specific license from each government regarding the use, export or import of the encryption system, but here, the specific license concerning the right to use, export or import the products using the encryption method and system of the present invention is required. I omit explanations about the government. In addition, an object of the present invention is to reduce the amount of work required for a natural person or a corporation authorized to decrypt an encrypted encrypted message because the encrypted secret key is required for decrypting the message. Achieved by a fractional workload system, government authorities impose one or more restrictions on the use, import or export of cryptographic hardware or software that uses cryptographic keys larger than a predetermined size.

The system requires that the encryption private key be
Includes means to divide the first partial key into two partial keys, reducing the knowledge of the first partial key without removing the amount of work required to decrypt the encrypted message and dividing the first partial key from the encrypted private key The size of at least one remaining partial key does not exceed the predetermined size of the encryption key according to one or more regulations of governmental authorities. In addition, the system provides means for encrypting at least the first partial key using the public key of the authorized natural or legal person, and if the authorized natural or legal person obtains the encrypted message and wishes to decrypt it. At least the first partial key encrypted using the secret key of the natural or legal person authorized by the authorized natural or legal person shall be decrypted and at least capable of decrypting the message using the first partial key. Means for supplying the first encrypted partial key together with the encrypted message.

In a preferred embodiment, the system further comprises:
Means for preventing decryption of the encrypted message by a given recipient of the encrypted message if at least the first encrypted partial key is not supplied with the encrypted message or if it is determined that interference has occurred. Including. The means preferably uses a hash of a private key (including possibly a salt) encrypted with an authorized natural or corporate public key.

The method and system of the present invention can be incorporated into software stored on a computer information medium such as a hard disk, floppy disk, CD-ROM, or other electrical, magnetic or optical storage device. Also, as known to those skilled in the art, the method or system may be embodied in a hardware element such as a specially designed integrated circuit.

In another aspect of the invention, the data structure is provided in an encrypted message stored in a storage device or transmitted from one to another computer system, wherein the data structure is provided by an authorized natural or legal person. Provides a reduced amount of work to decode the sentence. The data structure reduces the knowledge of the first substantive encrypted data, including at least the encrypted secret key and the message to be encrypted, and the partial key without removing the amount of work required to decrypt the encrypted message. The second substantive encrypted data including the partial key of the encrypted private key encrypted using the public key of the natural person or the corporation authorized to do so and attached to the first substantive encrypted data. Including. Further, the data structure may include at least an encrypted private key encrypted with a public key of a predetermined recipient of the communication message, and may include third substantial encrypted data attached to the encrypted communication message.

In a preferred embodiment, the second substantively encrypted data is a random number (ie, a random or pseudo-random number), a hash of at least a portion of the encrypted secret key, and / or the encrypted secret key and the salt. And a partial key combined with all or some of the salt. If a salt is used, the third substantively encrypted data may include an encryption secret key associated with the salt.

In another aspect of the present invention, a method for implementing a partitioned workload encryption system is provided. In a piece of work encryption system, a message sent to a given recipient other than the authority is encrypted using the encryption private key and the portion of the encryption private key that is encrypted using the authority's public key. Sent with key. In this method, an encrypted partial key is supplied together with the encrypted message when the encrypted message is received by a predetermined recipient and is determined to be valid, and the encrypted partial key is supplied together with the encrypted message. Refusal to decrypt the encrypted message if it is not valid or invalid. By including the hash of the private key in the partial key field, the validity of the partial key field may be determined, and the hash can be generated again by the recipient, re-encrypted with the public key of the authority, and encrypted with the encrypted message. It can be compared with the transmitted encrypted hash and partial key.

The decision on the validity of the partial key field may be made by including a cryptographic binding, such as a hash of the private key, combined with the partial key field in the header of the encrypted message, where the recipient determines the hash Is recalculated and the result is compared with the value received in the header.

The above-described method can also be used in an encryption system that supplies an entire encrypted secret key to an authority by encrypting with the public key of the authority and transmitting the message with the message. The process of determining whether the encryption key field is present and valid is the same as the previous process, except that all keys are used instead of partial keys.

[0034]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Preferred embodiments of the present invention will be described below with reference to the flowcharts of FIGS. 1 and 2 and the block diagrams of FIGS.

The present invention is illustrated in FIGS. 1-7, which are exemplary rather than limiting, and use the same notation for the same concepts.

In the present invention, a message to be transmitted is encrypted, and a large secret key is required to decrypt the message. The secret key may be the same key used for encrypting the message, or the secret key of a predetermined recipient of the message. As shown in FIGS. 1 and 2, in a preferred embodiment, the secret key is a random number (ie, a random number or a pseudo-random number).
Is generated for each message, and in step 12, the message is encrypted. Irregular key generators generate numbers in an unpredictable way so that an unauthorized user who decrypts one message encrypted with the generated secret key cannot use the random number generator algorithm to guess the next key Is preferred. Methods of generating an unpredictable series of random numbers are well known to those skilled in the art and may be incorporated into conventional encryption systems, such as those using the RSA Data Security RC4 algorithm used in the preferred embodiment of the present invention. Have been.

The amount of work required to decrypt the encrypted message is increased, and a sufficiently large secret key is used so that the encrypted message cannot be decrypted economically. The preferred embodiment uses a 64-bit sized secret key. As mentioned above, the size of the secret key required for secure communication varies depending on the encryption algorithm used and the nature of the technology available for decryption. Therefore, a larger key size is required to ensure secure communication in the future, and those skilled in the art will be able to recognize the size of the secret key required to secure secure communication.

To facilitate the preferred embodiment of the partitioned workload system, a one-way hash of the secret key is generated at step 14, as described below. A one-way hash is a well-known cryptographic function that operates on an input value to produce an output value called a hash or message digest, thereby determining the input value from the hash or two input values. Becomes impossible to calculate as a hash for the same value. Various strength hash functions are well known, including the hash functions MD2, MD4 and MD5 from RSA Data Security. One skilled in the art will appreciate that various hash functions are applicable to the present invention.

In a further preferred embodiment, a hash function is generated using a secret key and an additional bit string as input values. A bit string called a "salt" is a number, preferably a random number, concatenated with a secret key and an unauthorized user using a look-up table that has pre-calculated the hash value of a possible key to determine the secret key Interfere with. The longer the salt, the stronger the encryption, and in the preferred embodiment the salt is 64 bits long.

At step 16, the secret key and salt are encrypted using the public key of the given recipient. As described below, this encrypted value is decrypted by the recipient, who can then use the private key to decrypt the encrypted message.

At step 18 the secret key must be at least as large as necessary and appropriate (eg, upon obtaining legitimate search authorization) so that a licensed natural or legal person, such as a government or individual trustee, can decrypt the message. A large part that is split into two part keys, greatly reducing the amount of work sufficient to make the key economically decipherable and meeting government restrictions on the use, export or import of encryption technology The key is authorized. In a preferred embodiment, the U.S. government licenses 24 of the 64 bits because the remaining 40-bit partial key is economically decipherable and the 40-bit key is in a situation that allows it to be exported from the United States. I do. When using the DES encryption algorithm, the authorized partial key is 16
The partial key, which consists of key bits and 8 non-key bits and is kept secret from the authorities, consists of 40 key bits of the secret key.

The secret key can be split in any suitable way, for example by splitting the first or last 24 bits of a 64-bit key. The method of splitting the key is preferably known to both the intended recipient of the message and the authority.

Partial keys can be provided to authorities in several ways. In one embodiment, the partial key is sent directly to the authority via secure means, for example, encrypted and transmitted with the authority's public key. Authorities could then maintain a database of all encrypted partial keys, as each would have access to it as needed to decrypt the message.

In a preferred embodiment, in step 20,
The partial key, hash and all or part of the salt are encrypted using the public key of the authority, and the encrypted value is transmitted to the intended recipient together with the encrypted message and the encrypted secret key in step 22. . For example, when an authority obtains a message by receiving from the sender or receiver, copying from the sender or receiver's computer system memory, intercepting during transmission, etc., the communication encrypted with the authority's public key. Part of the sentence can be decrypted, thus obtaining the partial key, hash and all or part of the salt. The partial key can then be used by conventional authorities such as thorough cryptanalysis, for example, to perform a thorough cryptanalysis, or use a thorough cryptanalysis, i.e., to find the secret key. Sometimes it is possible to systematically try the various keys that concatenate each with a salt, hash each value, and compare the hashed value to the hash included with the encrypted partial key until a partner is found.

The provision of the partial key reduces the amount of work required to decrypt the encrypted message without removing it, so that authorities such as governmental agents can receive and decrypt each encrypted message that they wish to decrypt. Does not require much effort. As a result, authorization should be selective in determining which messages to decrypt, and simply cannot decrypt any encrypted messages without significant resource expenditure. Thus, individuals can maintain a certain level of privacy against government intervention added by manipulating the law.

When a predetermined receiver receives the transmitted message, the receiver decrypts an encrypted secret key using the secret key in step 24. Then, the recipient obtains a secret key for decrypting the encrypted message. In a preferred embodiment, the salt is included in the portion that is encrypted with the recipient's public key, and the recipient also gets the salt.

As described below, a hash function and
If used, salt is used to implement a partial key system. After receiving the encrypted message and the accompanying encryption key field, the recipient's system concatenates with the salt with the private key and, in step 26, converts the resulting string in the same manner performed by the sender. And hash using the same hash function used by the sender. Also, at step 28, the recipient's system splits the secret key into at least two partial keys in the same manner as the sender split key. Then, in step 30, the recipient's system uses the public key of the authority to encrypt the partial key, hash, and all or some salt, and
At 2, the encrypted value is compared with the encrypted partial key received by the recipient. If the encryption values do not match, step 3
At 4, the recipient's system refuses to decrypt the encrypted message with the secret key. If the encryption values match, step 36
The encrypted message is decrypted using the secret key.

Thus, improper encryption of the partial key field by the sender, such as deletion of the encrypted partial key field from the message by the sender, use of an incorrect public key to prevent authorities from decrypting the field, etc. Or
A partial key system can be implemented for various misuses, including intentional or accidental scrambling of partial key fields upon transmission or upon reception by a recipient.

FIGS. 3-7 illustrate various embodiments of a data structure having an encryption key field according to the present invention.
FIG. 3 shows a basic embodiment of encrypting a 64-bit secret key with a random number or random pad using a given recipient's public key. Certain public key systems, such as RSA, require that fixed-size blocks of plaintext be encrypted according to the size of the coefficients of a given recipient's public key, so that the irregular pad combines with the secret key and the irregular key. Supplies additional plaintext to be encrypted. Also, the 24-bit partial key, which is encrypted using the public key of the authority, is connected to the irregular pad for the same reason, so that an unauthorized user can determine one of the irregular pads and determine the other Preferably, it cannot be calculated using the predictable random number generator that it has to guess.

The embodiment shown in FIG. 3 uses the encryption system of the present invention in a software system having the owner's non-document file format that does not use the hash function or salt but does not delete or scramble the partial key field. Gives an evaluation of the implementation of the partial key system. Also, by including a random number with a partial key to be encrypted so that an unauthorized user must guess not only the partial key but also the random number for decrypting the encrypted message, the encrypted partial key field can be successfully decrypted. Provides protection against cryptanalysis attacks. The recipient can ignore these random numbers.

In a typical scenario, at least three governments, the government of the sender, the government of the recipient, and the government to which the system using the present invention is exported, will have access to the partial key using the present invention. Would require. The sender can be notified of the identity certificate of the recipient's authorization by including it in the recipient's public key identity certificate. FIG.
Shows other embodiments suitable for use with two authorities, and one skilled in the art will clearly understand how to extend the system to any number of authorities. As mentioned above, the 64-bit secret key and the irregular pad are encrypted using the given recipient's public key, and the 24-bit partial key and the irregular pad use one authority's public key. Encrypted. If a second authority is given the same 24-bit partial key, the partial key and the same or another irregular pad are encrypted with the second authority's public key, and the substantive encrypted data is transmitted Sent with

Alternatively, the second authority can place more stringent requirements on the allowable key bit size, in which case it will require a larger partial key (eg, a 28-bit partial key). In this case, as shown in FIG.
The private key is split into two other partial keys, 28 bits and 36 bits, and the second authority is given a 28 bit partial key by encrypting with the second authority's public key. The partial key given to the first and second authorities must not be the complementary part of the secret key, so that the government cannot cooperate to obtain the whole key by combining them. Preferably, the larger partial key encompasses the entire smaller partial key. As shown in FIG. 4, both encrypted partial keys are attached to the encrypted message and transmitted. The recipient's system can implement each partial key system by examining the existence and validity of each encrypted partial key field as described above.

As a further alternative, one or more authorities may be provided with a full private key, while all other authorities are provided with a partial key, or all authorities may be provided with a full private key which is encrypted with a different public key. Can be The quantity and format of the additional information having all or part of the encryption private key can vary from authority to authority.

In the above embodiment, the recipient receives the message correctly, but the authorized natural person or legal entity can delete it by deleting or distorting the encrypted partial key field after the message is generated so that it cannot be decrypted. The problem is that it can be invalidated. Such interference can be countered by including a hash or other cryptographic combination of the entire secret key and the encrypted partial key in the header of the message. The recipient's system recalculates this hash value using the secret key and the partial key and refuses to decrypt the message if the recalculated value does not match what was received in the message. Since only natural persons or corporations who know all the keys can recalculate the hash value, it is impossible to change the encrypted message without detecting the generated encryption key field.

FIGS. 5-7 show a message data structure having a more powerful implementation mechanism, in which case even if the software that generates the encrypted message is changed,
The recipient decrypts correctly but cannot generate a message that prevents an authorized natural or legal person from obtaining the partial key. These embodiments use a public key system, such as RSA, that generates the same ciphertext for the same plaintext.

In FIG. 5, the 64-bit secret key and the irregular pad are encrypted using the given recipient's public key as described above, and the 24-bit partial key, the hash of the full secret key and the irregular pad are concatenated. And encrypted with the authority's public key. The sender generates a non-random pad from predetermined information to the recipient, such as a portion of the recipient's irregular pad, so that the recipient is not required to guess the pad value of the authority requiring extra work of the recipient. . As described above, the private key using the recipient's private key is decrypted, a partial key is formed, a hash of the entire key is generated, and the public key of the authority is used to encrypt the partial key, hash and irregular pad. And the recipient's system implements a partial key system. The recipient's system compares the resulting encrypted material data with the encrypted material data received in the transmitted message,
Only when the values match, the message can be decrypted with the secret key.

Although the message data structure shown in FIG. 5 allows for the implementation of a partial key system, the authority may be required to determine the secret key more easily from the hashed secret key contained in the authority's partial key field. A lookup table of hash values for the hash function can be used. One way to increase the difficulty of calculating the table is to perform the hash function multiple times. However, this increases the processing time of the recipient of the message when checking the validity of the partial key field.

Another way to prevent authorities from using a lookup table of hash values is to concatenate the salts with a secret key, as shown in FIGS. In both cases of FIGS. 6 and 7, a given recipient is given a secret key and a salt, and requires the computation of a hash using the secret key and the salt to check the validity of the partial key field. In FIG. 6, the authority is given a hash and a total salt because the authority needs to compute the hash to guess all the private keys and cannot use a lookup table for the hash function. In FIG. 7, the authority has set a part of the salt (5 out of 64 bits).
6 bits), so the unknown bits in the salt must be guessed to calculate each hash. This increases the work required by the authority to decrypt the message using the hash to determine the secret key.

In another embodiment, the authority is not given any salt, so the authority cannot use the hash to determine the secret key, but can still be used to implement a partial key system. As will be appreciated by those skilled in the art, many modifications to FIGS. 5-7 are of course possible, hashing only a portion of the total secret key, with or without salt, providing the salt with the encrypted partial key. The purpose is to encrypt with a partial key that can be reconstructed by the recipient's system and checked to ensure that the encrypted partial key field is present and valid, as described above. In providing additional information.

Further, those skilled in the art can determine the amount of work required by the authority for decrypting a message using a hash in advance by using different variations of the message data structure shown in FIG. 6 and FIG. It can be understood that the control can be performed in various ways. In contrast, the amount of work required to decrypt a message with a brute force attack on the encrypted message varies with the size and content of the message.

[0061] Additional data can be included in the encryption key field. For example, the authority field may include, for example, the identity of the cryptographic algorithm used to encrypt the message and the hash function, the date of creation of the message, confirmation information about the sender, and other control information.

The method and system described above can also be used in a cryptographic system in which the entire encrypted private key is encrypted with the authority's public key and transmitted with the encrypted message. For example, the secret key field may include a hash of the secret key hashed with or without salt (all or part of the salt) and other information.
Further, as described above, the hash of the secret key combined with other information may be included in the header of the encrypted message.

Although the present invention has been described and described with reference to preferred embodiments, many variations and modifications can be made without departing from the spirit and scope of the invention, as will be apparent to those skilled in the art, and The invention derived from the scope of the present invention is not limited to the above detailed description of the methodology or configuration, and it is intended that variations and modifications are included in the scope of the present invention.

[0064]

As described above, according to the present invention, a divided work amount encryption method, system, and system for reducing, without removing, the work amount required by an authority for decrypting an encrypted message encrypted with an encrypted secret key. You can get the data structure.

[Brief description of the drawings]

FIG. 1 is a flowchart illustrating a transmission process of an encrypted message according to an embodiment of the present invention.

FIG. 2 is a flowchart illustrating a process of receiving an encrypted message according to an embodiment of the present invention.

FIG. 3 is a block diagram of a data field encrypted and transmitted according to a preferred embodiment of the present invention.

FIG. 4 is a block diagram of a data field that is encrypted and transmitted according to a preferred embodiment of the present invention.

FIG. 5 is a block diagram of a data field encrypted and transmitted according to a preferred embodiment of the present invention.

FIG. 6 is a block diagram of a data field that is encrypted and transmitted according to a preferred embodiment of the present invention.

FIG. 7 is a block diagram of a data field encrypted and transmitted according to a preferred embodiment of the present invention.

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Stephen M. Matthias Jr., United States of America, 12601-6315, New York, Pogue Kipsey, Bulk Drive 25 (72) Inventor, Raymond E. Ozzy, United States of America, 01944, Mass. Harbor Street 33

Claims (34)

[Claims] Claims: 1. A method for reducing the amount of work required for a natural person or a corporation authorized to decrypt an encrypted message that requires an encryption secret key to decrypt the message, without reducing the amount of work, the method comprising: Splitting the encryption private key into at least two partial keys,
The process of reducing the amount of work required to decrypt the encrypted message by knowing the first partial key, without reducing the amount of work required, and determining the first partial key by an authorized natural person or legal entity;
Providing the authorized natural person or legal entity with information enabling the decryption of the encrypted message using the first partial key. 2. The method according to claim 1, further comprising: encrypting a message using the encrypted private key; encrypting at least the encrypted private key using the public key of the predetermined recipient; Supplying the encrypted encrypted secret key together with the encrypted message. 3. The method according to claim 2, wherein the step of encrypting the message includes the step of generating an irregularly encrypted secret key and the step of encrypting the message using the generated irregularly encrypted secret key. The method for reducing the amount of work described in 1. 4. The method of claim 1, wherein supplying information to the authorized natural person or corporation includes transmitting the first partial key directly to the authorized natural person or corporation. 5. The process of providing information to an authorized natural or legal person comprises encrypting at least a first partial key using a public key of the authorized natural or legal person.
Providing the encrypted first partial key with the encrypted message to form an encrypted first partial key that can be used by an authorized natural or legal entity when obtaining the message. The work load reduction method described. 6. The method of claim 5, wherein encrypting at least the first partial key comprises encrypting additional information combined with the first partial key. 7. The method according to claim 6, wherein encrypting the additional information combined with the first partial key includes encrypting a random number combined with the first partial key. 8. The method of claim 1, further comprising calculating a hash of at least a portion of the encrypted private key, wherein the step of encrypting the additional information associated with the first partial key comprises combining at least the first partial key. The method of claim 6, further comprising the step of encrypting the hash. 9. The workload reduction of claim 8, wherein calculating at least a hash of at least a portion of the encrypted secret key comprises calculating a hash of at least a portion of the encrypted secret key combined with the salt. Method. 10. A method for encrypting a message using an encrypted secret key, encrypting at least an encrypted secret key combined with a salt using a public key of a predetermined recipient, Supplying the encrypted encrypted secret key and the salt together with the encrypted communication message. 11. The method of encrypting a hash combined with at least a first partial key includes the step of combining and encrypting a hash, a first partial key, and a salt.
The method for reducing the amount of work described in 1. 12. The method of claim 9, wherein encrypting the hash combined with at least the first partial key includes combining and encrypting the hash, the first partial key, and a portion of the salt. Work volume reduction method. 13. The method according to claim 6, wherein encrypting the additional information combined with the first partial key includes encrypting control information combined with the first partial key. 14. A method for cryptographically combining a first partial key encrypted with a public key of an authorized natural person or corporation with an encryption private key, and providing this cryptographic combination with an encrypted message. The method according to claim 5, further comprising: 15. using encryption hardware or software that uses an encryption key larger than a conventional size;
The process by which the government imposes one or more restrictions on imports or exports and splits the encryption private key into at least two partial keys may involve reducing the size of at least one partial key by one or more government authorities. 2. The method of claim 1, further comprising the step of maintaining the first partial key having a size equal to or smaller than the encryption key size according to the restriction after the division.
15. The method for reducing the amount of work according to any one of items 14 to 14. 16. A workload reduction method that reduces, without removing, the workload required by at least one additional authorized natural or legal person to decrypt an encrypted message, comprises:
Providing the information to one at least one additional authorized natural person or legal entity to determine the first partial key and decrypt the encrypted message using the first partial key to the at least one additional authorized natural person or legal entity. The method for reducing the amount of work according to claim 1, further comprising: 17. A method for reducing the amount of work required for at least one additional authorized natural or legal person to decrypt an encrypted message without removing it, comprising: adding at least two encrypted private keys; Splitting into partial keys, wherein the additional partial key is different than at least two partial keys, and knowing the first additional partial key reduces, without eliminating, the amount of work required to decrypt the encrypted message And at least one additional authorized natural person or legal entity, which is capable of determining the first additional partial key and decrypting the encrypted message using the first additional partial key. The method for reducing the workload according to any one of claims 1 to 14, further comprising a step of supplying to a corporation. 18. The encryption private key is divided into at least two partial keys, and knowledge of the first partial key reduces, without eliminating, the amount of work required to decrypt the encrypted message, and allows the authority to encrypt the message. In the method of supplying an encrypted secret key, which supplies a part of the encrypted secret key to the authority in order to reduce the amount of work required to decrypt the encrypted message encrypted with the secret key, without removing it, the public disclosure of the authority Encrypting at least the first partial key using the key, and if the authority wishes to obtain and decrypt the encrypted message, the authority encrypts the at least first partial key. Supplying at least a first partial key encrypted with the encrypted message so that the message can be decrypted using the secret key of the authority and the message using the first partial key can be decrypted. Secret encryption key supply Law. 19. A method for determining whether the encrypted at least first partial key is supplied with the encrypted message and is valid when a predetermined recipient of the encrypted message is received. Rejecting decryption of the encrypted message if the encrypted at least first partial key has not been supplied or is not valid with the encrypted message. . 20. Encrypting a portion of the encrypted private key so that an authorized natural person or corporation can decrypt the encrypted private key portion, and furthermore, the encrypted portion of the encrypted private key together with the encrypted message. A part of the encrypted private key is available by the process of transmitting the encrypted private key used to encrypt the message sent to the given recipient, and an authorized natural or legal person who can obtain the message. Determining whether the encrypted portion of the encrypted private key is transmitted with the encrypted message and is valid when the predetermined recipient of the encrypted message is received. And a step of refusing to decrypt the encrypted message if the encrypted portion of the encrypted private key has not been transmitted or is not valid with the encrypted message. 21. The method of claim 20, wherein some encrypted secret keys are encrypted with additional information, and wherein re-encrypting includes re-encrypting some encrypted secret keys with additional information. Method of implementing a cryptographic system. 22. A data structure of an encrypted message transmitted from one side to another computer system, wherein the encrypted message reduces the amount of work required for an authorized natural person or corporation to decrypt the encrypted message. In the sentence data structure, the first substantive encrypted data including the communication message encrypted with the encrypted private key and the partial key of the encrypted private key encrypted using the public key of the authorized natural person or corporation Including, without knowing the partial key, reducing the amount of work required for decrypting the encrypted communication message without removing it, and having the second substantial encrypted data attached to the first substantial encrypted data An encrypted message data structure characterized by the following. 23. The encrypted message data structure of claim 22, wherein the second substantial encrypted data includes a random number associated with the partial key. 24. The encrypted message data structure of claim 22, wherein the second substantive encrypted data includes a partial key that is combined with a hash of at least a portion of the encrypted private key. 25. The cipher according to claim 24, wherein the second substantively encrypted data includes a combination of a partial key, at least a part of an encrypted secret key and a hash of a salt, and all or part of a salt. Message data structure. 26. The method according to claim 26, further comprising: encrypting a third substantive encrypted data including at least an encrypted private key encrypted together with a public key of a predetermined recipient of the message and attached to the first substantive encrypted data. The encrypted communication data structure according to any one of claims 22 to 25. 27. The second substantive encrypted data includes a combination of a partial key, at least a part of an encrypted secret key and a hash of a salt, and all or part of a salt, and a third substantive encrypted data. 27. The encrypted message data structure of claim 26, wherein the encrypted data includes an encrypted secret key associated with all or some of the salt. 28. The encrypted message data structure according to claim 22, wherein the first substantial encrypted data includes a message and a cryptographic combination of an encrypted secret key and a partial key. . 29. A computer program readable means and having an encrypted secret key for decrypting the message, which is necessary for authorized natural persons or corporations to decrypt the encrypted message. A computer readable medium on which the computer can perform a method step of reducing the amount of work without removing, wherein the method step divides an encrypted secret key into at least two partial keys and obtains a cryptographic key by knowing a first partial key. Reducing the amount of work required to decrypt the encrypted message without removing it and ensuring that an authorized natural or legal person can use the first partial key to decrypt the encrypted message that the user wishes to decrypt. Supplying the information for determining the first partial key to an authorized natural person or legal entity. 30. Decrypt an encrypted message received by a partitioned workload encryption system having a computer readable program code means and encrypting the message using an encrypted secret key, and encrypting the encrypted secret key. Wherein the partial key is encrypted using the public key of the authority, and wherein the encrypted partial key is transmitted along with the encrypted message on a computer readable medium for the computer. Determining whether the encrypted partial message was received and valid, and rejecting decryption of the encrypted partial message if the encrypted partial key was not received or valid with the encrypted partial message; Decrypting the message using the encrypted private key if the encrypted partial key is received and valid with the encrypted message. Media for computer. 31. At least the hash of the encrypted private key is encrypted with the partial key, and the computer-implemented process of receiving the encrypted partial key with the encrypted message and determining whether it is valid includes at least encrypting Generating a hash of the private key, encrypting at least the encrypted secret private key and partial key using the public key of the authority, and encrypting at least the encrypted private secret key and partial key. Comparing with the encrypted partial key received with the encrypted message.
0. The computer medium according to 0. 32. A method for supplying an encrypted private key to an authorized natural person or a corporation, wherein at least a part of the encrypted private key used for encrypting a message transmitted to a predetermined recipient is provided. Or encrypting at least some of the encrypted private keys combined with at least some of the encrypted private keys and the salt hash so that the legal entity can decrypt at least some of the encrypted private keys; and Transmitting the encrypted secret key of the part together with the encrypted message. 33. When a predetermined recipient of the encrypted message receives the encrypted message, at least a part of the encrypted secret key is transmitted together with the encrypted message and it is determined whether or not the encrypted secret key is valid. 33. The cipher of claim 32, comprising the steps of: refusing to decrypt the encrypted message if at least some of the encrypted secret keys have not been transmitted or are not valid with the encrypted message. Secret key supply method. 34. The method according to claim 32, wherein the step of encrypting at least a part of the encrypted private key includes the step of encrypting the whole encrypted private key.