Variable-length key cryptosystem

[0001] This application is a continuing application, filed under 35 U.S.C. §111(a), of International Application PCT/JP99/05803, filed Oct. 20, 1999.

[0002] The present invention relates to a cryptosystem. For example, the present invention can be used for: encryption and decryption of communication contents that are transmitted via a computer network and require secrecy; encryption of information during storing onto a recording medium and decryption of the information during reading, wherein the information requires secrecy; and the like.

[0003] A conventional cryptosystem is generally classified into a secret key cryptosystem and a public key cryptosystem. The secret key cryptosystem is further classified into a stream cryptosystem and a block cryptosystem. Thus, a number of systems have been considered.

[0004] According to the secret key cryptosystem, only concerned parties hold both an encryption key and a decryption key as secret keys, a person sending an encrypted text encrypts a plain text with an encryption key and sends the encrypted text to a communication partner, and the communication partner decrypts the encrypted text with a decryption key to obtain the plain text. Herein, considering the strength of a cryptosystem, two points are important factors: an encryption key and a decryption key are kept secret; and a person sniffng an encrypted text during communication cannot easily learn the encrypted text to find a rule of obtaining a plain text. Regarding the former point, an encryption key and a decryption key are shared by communication parties, so that it becomes important how safely a key whose distribution is required at least once should be distributed. Regarding the latter point, various attempts have been made; for example, complexity of a rule is enhanced so that a rule will not be easily found, a hash function without any rule is used, and a key and a rule used each time are altered at random.

[0005] According to the public key cryptosystem, by utilizing difficulty in unique factorization of a value of a product of sufficiently large prime numbers and difficulty in obtaining a solution to an elliptical curve, an encryption key for encryption is made public, a person who desires to send a plain text creates an encrypted text using the key element that is made public, and only an authorized person can decrypt the encrypted text with a secret key. According to this system, security is ensured using the difficulty in obtaining a secret key from a public key, and distribution of a key, which becomes a problem according to the secret key cryptosystem, is not required. In this point, security is enhanced.

[0006] However, the public key cryptosystem requires a large amount of calculation time for encryption and decryption. Therefore, it takes a long time and a large cost to deal with a long (about 1000 or more characters) plain text, which is inconvenient for a practical use.

[0007] According to the conventionally known secret key cryptosystem, a block cryptosystem is mainly used. This system requires a long calculation time for encryption and decryption, and also requires a long time and a large cost for dealing with a long plain text, which is inconvenient for a practical use. Furthermore, although a DES cryptosystem is generally used in a conventional secret key cryptosystem, it is found that an encrypted text may be decrypted in principle, which causes a safety problem.

[0008] On the other hand, in the stream cryptosystem among the secret key cryptosystem, according to a system (Vernam cryptosystem) in which a genuine random number sequence is used as an encryption key, and a key used in the past is not used any more, it takes less time for encryption and decryption, and an encrypted text cannot be decrypted in principle. However, it is required to previously send an encryption key with the same length as that of an encrypted text to a receiver by safe means, so that a problem of distribution of a key is caused. Since it costs a lot for ensuring security for distributing a key, the Vernam cryptosystem can be used only for special communication requiring high secrecy, even if a cost for distributing a key is left out of consideration.

[0009] In view of the above-mentioned problems of a conventional encryption apparatus, it is an object of the present invention to provide a variable-length key cryptosystem with high security and a small calculation cost. As a key generation scheme of a stream cryptosystem, this system has a random number property similar to a genuine random number sequence (i.e., difficulty in decryption), allows a required key to be selected in accordance with the length of a plain text and an encrypted text, and only requires a small amount of parameters for generation of a key to be previously shared by a sender and a receiver, compared with that of an encrypted text.

[0010] In order to achieve the above-mentioned object, first, the variable-length key cryptosystem of the present invention uses a key generation scheme having only a previously given constant number or less of character strings with a particular length. When the constant number is k, such a key generation scheme is referred to as a “k-sparse language”.

[0011] The variable-length key cryptosystem of the present invention using a variable-length key generation apparatus of a one-sparse language includes: a variable-length key generation processing part for generating an encryption key with a required arbitrary length; and a data string length detection processing part for detecting a length of a character string, wherein, in the encryption of the plain text, the data string length detection part detects a length of the plain text, and the variable-length key generation processing part generates only one encryption key with a particular length, based on the detected length of the plain text, for stream encryption processing, and in the decryption of the encrypted text, the data string length detection processing part detects a length of the encrypted text, and the variable-length key generation processing part generates only one encryption key that is the same as the encryption key with a particular length used for the encryption, based on the detected length of the encrypted text, for stream decryption processing.

[0012] According to the above-mentioned configuration, in the variable-length key cryptosystem of the present invention, parameters required for generating a sparse language are only an initial string, a set of conversion rules, and a conversion rule selection function. These parameters are required to be sent to a receiver side by safe means. A data amount is small, so that distribution of a key is much easier compared with a conventional stream code. Furthermore, an encryption key is not used twice. Therefore, there is no possibility that a plain text is obtained only from an encrypted text. Furthermore, an encryption key is generated by repeating character conversion, and character conversion can be conducted in parallel. Therefore, the key can be generated in a short calculation time. Once the key is generated, encryption and decryption are conducted only by addition and subtraction, so that the encryption and decryption can be conducted at a high speed. Therefore, a large amount of data can be encrypted at a high speed.

[0013] The variable-length key cryptosystem of the present invention that uses a k-sparse language with respect to k of 2 or more as a variable-length key generating system includes: a variable-length key generation processing part for generating an encryption key with a required arbitrary length; a data string length detection processing part for detecting a length of a character string; and a hash function for associating a character string with a hash function value, wherein, in the encryption of the plain text, the data string length detection processing part detects a length of the plain text, the variable-length key generation processing part generates a predetermined number or less of encryption keys with a particular length based on the detected length of the plain text and selects one encryption key for stream encryption processing, the hash function generates a hash value with respect to the plain text to be encrypted, and the hash value is sent together with the generated encrypted text, and in the decryption of the encrypted text, the data string length detection processing part detects a length of the encrypted text, the variable-length key generation processing part generates a plurality of number or less of encryption keys with a particular length, based on the detected length of the encrypted text, for stream decryption processing, the hash function generates a hash value with respect to each of the decrypted plain texts, and a plain text having a hash value equal to the sent hash value is selected.

[0014] According to the above-mentioned configuration, when a k-sparse language with respect to k of 2 or more is used as a variable-length key generating system, one of possible k pieces of character strings is used for encryption and decryption processing. Therefore, a hash function representing features of a plain text as a small positive integer is used, and an encrypted text obtained by using arbitrarily selected one of k pieces of character strings as a key and a hash function value are sent to a receiver. The receiver decrypts the encrypted text with respective k pieces of character strings generated based on the length of the encrypted text, and obtains a hash function value from the resultant character strings, respectively, whereby the receiver can select a plain text matched with the sent hash function value. Since the length of the hash function value is very small (about tens of bits), even if a stream code is used at distribution, which utilizes a conventionally used genuine random number value as a key, there is no problem in distribution of a key.

[0015] In order to generate a k-sparse language having the same property as that of a random number sequence, a system having an initial string, a set of conversion rules, and a conversion rule selection function is used. Herein, the initial string is a short string composed of the same characters as those of an encryption key. The conversion rule is a rule of converting one character to a character string with a length of 1 or more, and only one rule is given to each character. Some sets of such rules are provided. The conversion rule selection function is a function of selecting one set of conversion rules based on the length of a character string. In this system, one character string is converted to a character string obtained by applying a set of conversion rules, which are selected by the conversion rule selection function based on the length of the character string, to all the characters thereof, respectively. An initial string is successively converted to a character string by the above-mentioned conversion system, and a character string with the same length as or a length larger than that of a plain text is used as an encryption key. It is mathematically verified that the character string conversion system described herein generates a k-sparse language without fail. An arbitrary complicated function can be used in the conversion rule selection function, which disables decryption.

[0016] In order to further enhance the above-mentioned character string generation ability of the system, in the converted character string generation processing part, a combined initial character string generated by combining characters used for generating the encryption key with characters of kinds different from the characters used for generating the encryption key is used as the initial character string, a combined conversion rule generated by combining a character conversion rule with respect to the characters used for generating the encryption key with a character conversion rule with respect to the characters of kinds different from the characters used for generating the encryption key is used as the conversion rule, character conversion is repeated by using the combined initial character string and the combined conversion rule, and only characters used for generating the encryption key are extracted from a generated character string to generate an encryption key.

[0017] Furthermore, in the converted character string generation processing part, an initial character string of characters of kinds different from those of characters used for the encryption key is used as the initial character string, a character conversion rule with respect to characters of kinds different from those of characters used for the encryption key is used as the conversion rule, character conversion is repeated by using the initial character string and the character conversion rule, and the encryption key is generated by second character conversion of converting each character of a generated character string to characters used for the encryption key.

[0018] As described above, an encryption strength is enhanced due to the use of redundant characters. It is also mathematically verified that the above-mentioned system generates a k-sparse language without fail.

[0019] In the above-mentioned cryptosystem, when an encryption key with a length equal to that of a plain text is not generated, and when the length of a plain text has already been used, character conversion is continued to generate a converted character string with a length that has not been used for an encryption key. Then, a portion of the converted character string with a length equal to that of a plain text is adopted, and the remaining portion thereof is discarded, whereby the encryption key is generated. As described above, by allowing a sender and a receiver to record that the length of a used encryption key is spent, the same used key can be prevented from being used twice or more, and security strength can be enhanced.

[0020] The computer-readable recording medium storing a processing program for realizing processing operations of a variable-length key cryptosystem of the present invention includes: a variable-length encryption key generation processing operation of generating an encryption key with a required arbitrary length; a data string length detection processing operation of detecting a length of a character string; a stream code generation processing operation of generating a stream code by using a designated encryption key; and a stream code decryption processing operation of decrypting the stream code by using a designated encryption key, wherein, in the encryption of the plain text, the variable-length encryption key generation processing operation includes generating an encryption key with a particular length based on a legth of a plain text detected in the data string length detection processing operation, and the stream code generation processing operation includes generating a stream code by using an encryption key generated in the variable-length encryption key generation processing operation, and in the decryption of the encrypted text, the variable-length encryption key generation processing operation includes generating the same encryption key as the encryption key with a particular length used for the encryption, based on the length of the encrypted text detected in the data string length detection processing operation, and the stream code decryption processing operation includes decrypting a stream code by using the encryption key generated in the variable-length encryption key generation processing operation.

[0021] By providing the above-mentioned recording medium, the variable-length key cryptosystem of the present invention can be provided by using a computer capable of reading the recording medium.

[0033] Hereinafter, a variable-length key cryptosystem of an embodiment according to the present invention will be described with reference to the drawings.

[0034] A variable-length key cryptosystem of Embodiment 1 uses a variable-length key generating system of a one-sparse language. Herein, in a key generation scheme generating only a previously given constant number or less of pieces of character strings with a particular length, when the given constant number is k, such a key generation scheme is referred to as a k-sparse language. In Embodiment 1, if the length is specified, only one piece of encryption key with that length is generated.

[0035] FIG. 1 shows an exemplary configuration of the variable-length key cryptosystem of Embodiment 1 according to the present invention. In FIG. 1, reference numeral 100 denotes a sender system that encrypts a plain text, and 200 denotes a receiver system that decrypts an encrypted text to generate a plain text. Reference numeral 300 denotes a communication path through which a sender 1 and a receiver 2 exchange data.

[0036] The sender system 100 includes a data input part 10, a data string length detection processing part 20, a variable-length key generation processing part 30, a stream code processing part 40, and a communication interface 50. A controller, a memory, and the like required for controlling the system are not shown.

[0037] The data input part 10 inputs/outputs data. In encryption, a plain text is inputted.

[0038] The data string length detection processing part 20 detects the length of a given data string. Herein, the length of a plain text is detected.

[0039] The variable-length key generation processing part 30 generates an encryption key with a required arbitrary length, using an initial character string and a conversion rule as described later. The length of an encryption key is based on the length of a detected plain text. The variable-length key generation processing part 30 includes a conversion rule holding part 31, a converted character string generation processing part 32, a used key list 33, and an encryption key converting part 34.

[0040] FIG. 2(a) shows an example of a conversion rule held by the conversion rule holding part 31. FIG. 2(a) shows a very simple example regarding three characters “A”, “a”, and “b” for convenience of description. According to the exemplary conversion rule shown in FIG. 2(a), regarding a character “A”, its length is converted from 1 to 2 (“aA”). That is, it is understood that the length of a character string to be generated becomes twice by one character conversion. The length of a character string to be generated can be adjusted by conducting conversion in multiple stages.

[0041] Needless to say, a conversion rule to be actually used can enrich the kind of characters to be used, and a more difficult conversion rule may be used. Furthermore, according to the exemplary conversion rule in FIG. 2, a character string is converted so that the length of its part becomes twice. It is also possible to set the conversion rule so that the length of a part of a character string becomes three times or more.

[0042] The converted character string generation processing part 32 generates a converted character string with a required arbitrary length from an initial character string, using a conversion rule held by the conversion rule holding part 31. In order to obtain a converted character string with a required arbitrary length, the converted character string generation processing part 32 has the following four processing stages.

[0043] In the first processing, an initial character string is converted to a converted character string reaching the length of a plain text, using the conversion rule held by the conversion rule holding part 31. For example, when the conversion rule and an initial character string A shown in FIG. 2 are used, a converted character string is generated as shown in FIG. 2(b). Every time character conversion is conducted, the length of a converted character string is increased by one character. Since the length of a plain text is detected by the data string length detection processing part 20, conversion is repeated until the length of the character string becomes that of the length of the plain text, whereby the length of a converted character string is increased. Assuming that the length of a plain text detected by the data string length detection processing part 20 is, for example, “7”, according to the first processing, a converted character string “bababaA” with a length of 7 can be generated after repeating the conversion rule six times.

[0044] In the second processing, it is checked whether or not a converted character string reaching the length of a plain text generated in the first processing has been used for the past generation of an encryption key. When the converted character string has been used, character conversion is continued until a converted character string that has not been used is obtained. Therefore, the variable-length key generation processing part 30 includes the used key list 33 so as to hold information on the length of a converted character string used in the past, and refers to the information in the second processing. In the variable-length key cryptosystem of the present invention, in order to enhance encryption strength and ensure security, an encryption key that has been used is not used any more. Even if typical electronic mail with the same length of a plain text is often sent, an encryption key to be used is varied every time, so that an encrypted text cannot be easily decrypted even in the presence of a third party sniffing communication of the encrypted text. In this example, in the case where a converted character string with a length of 7 has already been used, character conversion is continued in the second processing. For example, if a converted character string with a length of 8 in the seventh conversion of the subsequent stage has not been used, a converted character string “abababaA” with a length of 8 is outputted in the second processing.

[0045] In the third processing, in the case where the length of a converted character string that has reached the length of a plain text obtained by the time when the second processing is completed exceeds that of a plain text, the length of the converted character string is adjusted so as to be that of a plain text. The length is not necessarily increased by one character, depending upon how a conversion rule is created. Furthermore, in the second processing, a converted character string longer than a plain text may be generated, so that the length of a converted character string may not be equal to that of a plain text. Therefore, in the converted character string thus generated, a portion with a length of a plain text is adopted, and the remaining portion is discarded, whereby a converted character string with the same length as that of a plain text is obtained. In this example, in the converted character string with a length of 8 obtained by the time when the second processing is completed, a character string of 7 characters that is the leading portion corresponding to the length of 7 of a plain text is adopted, and the remaining one character string is discarded. More specifically, the converted character string obtained in the third processing becomes “abababa”.

[0046] In the fourth processing, the converted character string generated by the converted character string generation processing part 32 is converted to a character string to be used as an encryption key, by using the encryption key converting part 34. If the converted character string generated by the converted character string generation processing part 32 is a character string to be used as an encryption key, the fourth processing is not required. In this example, it is assumed that an encryption key is a binary sequence of “0” and “1”. When conversion is conducted as follows: A→“1”, a→“1”, b→“0”, an encryption key “1010101” is obtained, as shown in FIG. 2(c).

[0047] The converted character string generation processing part 32 generates a converted character string with a length of a plain text by the above-mentioned four processings. The variable-length key generation processing part 30 utilizes a converted character generated by the converted character string generation processing part 32 as an encryption key. More specifically, in the example shown in FIG. 2, “1010101” is used as an encryption key.

[0048] The stream code processing part 40 generates a stream code text from a plain text, using the encryption key generated by the variable-length key generation processing part 30. Herein, characters of an encryption key are added to the respective characters of a plain text. Since the length of the plain text is equal to that of the encryption key, the corresponding characters of the encryption key are added to the respective characters of the plain text. In the example shown in FIG. 2, a corresponding binary sequence of 7 numbers “1010101” of the encryption key is added to a plain text with a length of 7.

[0049] The communication interface 50 provides an interface for communication through a network 300, and sends a stream code text generated by the stream code processing part 40 to the receiver system 200. In order to hold the information on the length of the encryption key used for encryption processing in the used key list 33 of the receiver system 200 (described later) while synchronizing the contents, the communication interface 50 also communicates the information to the receiver system 200.

[0050] Next, decryption processing in the receiver system 200 will be described.

[0051] The receiver system 200 includes a data input part 10, a data string length detection processing part 20, a variable-length key generation processing part 30, a stream code processing part 40, and a communication interface 50. A controller, a memory, and the like required for controlling the system are not shown.

[0052] The data input part 10 inputs/outputs data. In the receiver system 200, the data input part 10 receives an encrypted text from the communication interface 50.

[0053] The data string length detection processing part 20 detects the length of a given character string, in the same way as the data string length detection processing part 20 in the sender system 100. In the receiver system 200, the data string length detection processing part 20 detects the length of the received encrypted text.

[0054] The variable-length key generation processing part 30 is the same as the variable-length key generation processing part 30 in the sender system 100, and generates a key (i.e., which is the same as an encryption key) with a required arbitrary length used for decryption, using an initial character string and a conversion rule. In the receiver system 200, the length of the encryption key is based on the length of an encrypted text. The variable-length key generation processing part 30 of the receiver system 200 similarly includes a conversion rule holding part 31, a converted character string generation processing part 32, a used key list 33, and an encryption key converting part 34. Herein, it is assumed that the conversion rule held by the conversion rule holding part 31 is the same as that held by the conversion rule holding part 31 of the sender system 100, and is previously distributed to the sender system 100 and the receiver system 200 by a safe method. Furthermore, it is assumed that an initial character string to be used is the same as that used by the sender system 100, and is previously distributed to the sender system 100 and the receiver system 200 by a safe method. For example, a public key cryptosystem or the like can be used for the distribution.

[0055] Herein, the conversion rule held by the conversion rule holding part 31 is the same as that shown in FIG. 2. In the same way as in the case of the sender system 100, regarding a part of characters, a character string with a length of 1 is converted to a character string with a length of 2. Every time character conversion is conducted, the length of a generated character string is increased by one character. The length of a character string to be generated can be adjusted by conducting the conversion in multiple stages.

[0056] The converted character string generation processing part 32 generates a converted character string with a length of an encrypted text from an initial character string, using the conversion rule held by the conversion rule holding part 31. In order to obtain a converted character string with a length of an encrypted text, the converted character string generation processing part 32 has the following four processing stages.

[0057] In the first processing, an initial character string is converted to a converted character string until it reaches the length of an encrypted text, using the conversion rule held by the conversion rule holding part 31. If the conversion rule and the initial character string A shown in FIG. 2(a) are used, a converted character string is similarly generated as shown in FIG. 2(b). Since the length of an encrypted text is detected by the data string length detection processing part 20, conversion is repeated until the length of the character string becomes that of the encrypted text, whereby the length of a converted character string is increased. Herein, since the length of the encrypted text is “7”, according to the first processing, the conversion rule is repeated six times to generate a converted character string with a length of 7.

[0058] In the second processing, it is checked whether or not a converted character string reaching the length of an encrypted text generated in the first processing has been used for the past generation of an encryption key. When the converted character string has been used, character conversion is continued until a converted character string that has not been used is obtained. Therefore, the variable-length key generation processing part 30 includes the used key list 33, which holds information on the length of a converted character string used in the past, in synchronization with the used key list 33 of the sender system 100 with respect to of the history information contents, and refers to the information in the second processing. Herein, the information in the used key list 33 is synchronized with the information contents of the used key list 33 of the sender system 100, and the past use of the converted character string with a length of 7 is stored in the used key list 33. Therefore, it is determined that the character string cannot be used. In the second processing, character conversion is continued. Regarding a converted character string with a length of 8 in the subsequent stage, information on the use thereof is not held in the used key list 33, and the converted character string with a length of 8 is outputted from the second processing.

[0059] In the third processing, in the case where the length of a converted character string that has reached the length of an encrypted text obtained by the second processing exceeds the length of an encrypted text, the length of the converted character string is adjusted so as to be the length of the encrypted text. In the generated converted character string, a portion having a length of the encrypted text is adopted, and the remaining portion of the encrypted text is discarded, whereby a converted character string having the same length as that of the encrypted text is obtained. In the example shown in FIG. 2, in the converted character string with a length of 8 obtained by the time the second processing is completed, a character string of 7 characters that is the leading portion corresponding to the length of 7 of an encrypted text is adopted, and the remaining one character string is discarded. More specifically, the converted character string obtained in the third processing becomes “abababa”.

[0060] In the fourth processing, the converted character string generated by the converted character string generation processing part 32 is converted to a character string to be used as an encryption key, by using the encryption key converting part 34. If the converted character string generated by the converted character string generation processing part 32 is a character string to be used as an encryption key, the fourth processing is not required. In this example, it is assumed that an encryption key is a binary sequence of “0” and “1”. When conversion is conducted as follows: A→“1”, a→“1”, b→“0”, an encryption key “1010101” is obtained, as shown in FIG. 2(c).

[0061] The converted character string generation processing part 32 generates a converted character string with a length of an encrypted text by the above-mentioned four processings. The variable-length key generation processing part 30 utilizes a converted character generated by the converted character string generation processing part 32 as an encryption key. More specifically, in the same way as in the sender system 100, an encryption key “1010101” is also generated in the receiver system 200.

[0062] As described above, the same encryption key as that used in the sender system 100 is also obtained in the receiver system 200.

[0063] The stream code processing part 40 decrypts a stream code text to a plain text, using the encryption key generated by the variable-length key generation processing part 30. Herein, the characters of the encryption key are subtracted from the respective characters of the stream code text. Since the length of the encrypted text is the same as that of the encryption key, the characters of the encryption key corresponding to the respective characters of the encrypted text are subtracted. In this example, 7 characters “1010101” of the encryption key corresponding to the respective characters of the encrypted text with a length of 7 are respectively subtracted to obtain a plain text.

[0064] Finally, the processing flow of the variable-length key cryptosystem will be described with reference to a flow chart. If the processing operations described in the flow chart are used, the method for executing the variable-length encryption processing of the present invention will be understood. FIG. 3 shows processing operations in the sender system 100, and FIG. 4 shows processing operations in the receiver system 200.

[0065] As shown in FIG. 3, in the sender system 100, input processing of a plain text from the data input part 10 (Operation 301), detection processing of a length of a plain text by the data string length detection processing part 20 (Operation 302), first processing by the variable-length key generation processing part 30 (Operation 303), second processing (Operation 304), character conversion continuation processing in the case where a converted character string has been used (Operation 305), third processing in the case where a converted character string has not been used (Operation 306), fourth processing (Operation 307), and stream encryption processing (Operation 308) by the stream code processing part 40 are conducted.

[0066] Similarly, as shown in FIG. 4, in the receiver system 200, input processing of an encrypted text from the data input part 10 through the communication interface 50 (Operation 401), detection processing of a length of an encrypted text by the data string length detection processing part 20 (Operation 402), first processing by the variable-length key generation processing part 30 (Operation 403), second processing (Operation 404), character conversion continuation processing in the case where a converted character string has been used (Operation 405), third processing in the case where a converted character string has not been used (Operation 406), fourth processing (Operation 407), and stream decryption processing by the stream code processing part 40 (Operation 408) are conducted.

[0067] Because of the encryption processing by the sender system 100 and the decryption processing by the receiver system 200, an encryption key can be generated based on the length of a plain text and the length of an encrypted text without distributing the encryption key in a stream cryptosystem, whereby high security can be realized. Parameters required for generating a sparse language are only an initial string and a set of conversion rules. The encryption key is not used twice, so that there is no possibility that a plain text is obtained only from an encrypted text. Furthermore, an encryption key is generated by repeating character conversion, and character conversion can be conducted in parallel. Therefore, the key can be generated in a short calculation time. Once the key is generated, encryption and decryption are conducted only by addition and subtraction, so that the encryption and decryption can be conducted at a high speed. Therefore, a large amount of data can be encrypted at a high speed.

[0068] A variable-length key cryptosystem of Embodiment 2 uses a variable-length key generating system of a k (k is an integer of 2 or more)-sparse language. Compared with Embodiment 1, in the variable-length key cryptosystem of Embodiment 2, a plurality of sets of conversion rules are prepared, one set of conversion rule is dynamically selected for character conversion, and a hash function is used as information for identifying which set of conversion rule has been used. In Embodiment 2, for convenience of description, a variable-length key generating system of a 2-sparse language will be described.

[0069] FIG. 5 shows an exemplary configuration of the variable-length key cryptosystem of Embodiment 2 according to the present invention. In FIG. 5, reference numeral 100a denotes a sender system that encrypts a plain text, and 200a denotes a receiver system that decrypts an encrypted text to generate a plain text. Reference numeral 300 denotes a communication path through which a sender 1 and a receiver 2 exchange data.

[0070] The sender system 100a includes a data input part 10, a data string length detection processing part 20, a variable-length key generation processing part 30a, a stream code processing part 40, and a communication interface 50. A controller, a memory, and the like required for controlling the system are not shown.

[0071] The data input part 10, the data string length detection processing part 20, the stream code processing part 40, and the communication interface 50 are the same as constituent elements denoted with the same reference numerals in the sender system 100 described in Embodiment 1. Therefore, the description thereof will be omitted here.

[0072] The variable-length key generation processing part 30a generates an encryption key with a required arbitrary length, using an initial character string and a conversion rule as described later. The length of an encryption key is based on the length of a detected plain text in the same way as in Embodiment 1. The variable-length key generation processing part 30a of Embodiment 2 includes a conversion rule selection function processing part 35 and a hash function processing part 36, as well as a conversion rule holding part 31a, a converted character string generation processing part 32a, a used key list 33, and an encryption key converting part 34.

[0073] The conversion rule holding part 31a holds conversion rules. In Embodiment 2, as shown in FIG. 6, the conversion rule holding part 31a holds a plurality of sets of conversion rules. In the example shown in FIG. 6, for convenience of description, each set is assumed to be a simple conversion rule for three characters, and only two sets: Conversion rule 1 and Conversion rule 2 are shown. Needless to say, a conversion rule to be actually used can enrich the number of characters to be used, and a larger number of sets can be held. According to the exemplary conversion rule in FIG. 6, a character string is converted so that the length of its part is converted from one to two. However, in the same way as in Embodiment 1, it is also possible to set the conversion rule so that the length of a part of a character string becomes three times or more.

[0074] The conversion rule selection function processing part 35 dynamically selects one set of conversion rule from a plurality of sets of conversion rules held by the conversion rule holding part 31a. Various conversion rule selection functions can be assumed. Herein, the following function is used: in the case where the length of a plain text is a prime number, “1” (i.e., Conversion rule 1) is selected, and in the case where the length of a plain text is not a prime number, “2” (i.e., Conversion rule 2) is selected. According to this function, since the characteristics in distribution of prime numbers are not clarified in principle so far, it is impossible to understand the tendency of how Conversion rule 1 or Conversion rule 2 is selected. Even in Embodiment 2, when it is assumed that the length of a plain text is 7,7 is a prime number, so that Conversion rule 1 is selected based on the conversion rule selection function.

[0075] The variable-length key generation processing part 30a generates a converted character string in accordance with the length of a plain text by the converted character string generation processing part 32a, using the selected Conversion rule 1 and an initial character string, in the same way as in Embodiment 1. In Embodiment 2, the converted character string generation processing part 32a conducts the first to fourth processings described in Embodiment 1. In this example, the selected Conversion rule 1 is the same as that shown in FIG. 2(a) described in Embodiment 1, so that a character string to be generated also becomes the same as that shown in FIG. 2(b). Herein, it is assumed that a converted character “abababa” is generated. It is also assumed that the variable-length key generation processing part 30a uses “1010101” as an encryption key.

[0076] The hash function processing part 36 calculates a hash function based on a converted character string generated by the converted character string generation processing part 32a to obtain a hash value. In order to enhance the strength of security, a hash function, of which rule is unlikely to be found out, is preferably used, and the hash function is preferably a genuine random number sequence. In this example, it is assumed that a hash value H1 is calculated with respect to an encryption key “1010101”.

[0077] The stream code processing part 40 generates a stream code text from a plain text, using the encryption key generated by the variable-length key generation processing part 30a, in the same way as in Embodiment 1. Herein, 7 characters “1010101” of the corresponding encryption key are added to the respective characters of a plain text of 7 characters.

[0078] The communication interface 50 provides an interface for communication through a network 300. In Embodiment 2, the communication interface 50 sends the stream code text generated by the stream code processing part 40 and the hash function value H1 to the receiver system 200a. The information on the length of the encryption key used for encryption processing is also communicated to the receiver system 200a so as to be in synchronization with the contents of the used key list 33.

[0079] Next, decryption processing in the receiver system 200a will be described.

[0080] The receiver system 200a includes a data input part 10, a data string length detection processing part 20, a variable-length key generation processing part 30a, a stream code processing part 40, and a communication interface 50. A controller, a memory, and the like required for controlling the system are not shown.

[0081] The data input part 10, the data string length detection processing part 20, the stream code processing part 40, and the communication interface 50 are the same as constituent elements denoted with the same reference numerals in the receiver system 200 described in Embodiment 1. Therefore, the description thereof will be omitted here.

[0082] The encrypted text and the hash value are received from the data input part 10 through the communication interface 50. In this example, the hash value is H1.

[0083] The variable-length key generation processing part 30a generates a key (i.e., which is the same as an encryption key) with a required arbitrary length used for decryption, using an initial character string and a conversion rule. In the present embodiment, there are a plurality of sets of conversion rules, so that it is required to determine which encryption key generated by using which set of conversion rule is correct.

[0084] The variable-length key generation processing part 30a includes a hash function processing part 36, as well as a conversion rule holding part 31a, a converted character string generation processing part 32a, a used key list 33, and an encryption key converting part 34. Herein, it is assumed that each of a plurality of sets of conversion rules held by the conversion rule holding part 31a is the same as each of a plurality of sets of conversion rules held by the conversion rule holding part 31a of the sender system 100a. It is also assumed that a hash function held by the hash function processing part 36 is the same as that held by the hash function processing part 36 of the sender system 100a, and these are previously distributed to the sender system 100a and the receiver system 200a by a safe method. Furthermore, it is assumed that an initial character string to be used is the same as that used by the sender system 100a, and is previously distributed to the sender system 100a and the receiver system 200a by a safe method.

[0085] The converted character string generation processing part 32a generates a converted character string with a length of an encrypted text from an initial character string, using each of sets of conversion rules held by the conversion rule holding part 31a. More specifically, in this example, an encryption key 1 is generated by using Conversion rule 1 and an initial character string shown in FIG. 6, and an encryption key 2 is generated by using Conversion rule 2 and an initial character string. An encryption key is generated by using the first to third processings described in Embodiment 1. It is assumed that a first converted character string “abababa” and a first encryption key “1010101” are generated by Conversion rule 1 and an initial character string, and a second converted character string “bababab” and “0101010” are generated by Conversion rule 2 and an initial character string.

[0086] The variable-length key generation processing part 230a obtains a hash value from each encryption key generated by the hash function processing part 236. In this example, it is assumed that a hash value H1 is generated from the first encryption key “1010101”, and a hash value H2 is generated from a second encryption key “0101010”. The variable-length key generation processing part 30a compares the generated hash value with that sent from the sender system 100a, and determines an encryption key with a correct hash value to be a correct encryption key. In this example, the encryption key 1 “1010101” that has the same hash value H1 is determined as a correct encryption key.

[0087] The stream code processing part 40 decrypts a stream code text to a plain text, using the encryption key generated by the variable-length key generation processing part 30a. In this example, 7 characters “1010101” of the encryption key 1 are subtracted from an encrypted text with a length of 7 to obtain a plain text.

[0088] Because of the encryption processing by the sender system 100a and the decryption processing by the receiver system 200a, an encryption key can be generated based on the length of a plain text and the length of an encrypted text, without distributing an encryption key of a stream cryptosystem. Furthermore, encryption is conducted by dynamically selecting one set of conversion rule from a plurality of sets of conversion rules, so that high security can be realized. Since an encryption key is not used twice, there is no possibility that a plain text is obtained only from an encrypted text. Furthermore, a plurality of encryption keys can be generated in parallel in decryption, and encryption keys can be generated in a shorter period of time. Encryption and decryption are conducted only by addition and subtraction, so that encryption and decryption can be conducted at a high speed. Therefore, encryption of a large amount of data can be conducted at a high speed.

[0089] The variable-length key cryptosystem of Embodiment 3 has a plurality of conversion rules, and switches a conversion rule to be used in each stage of character conversion by a conversion rule selection function. As a conversion rule selection function, a function of switching a conversion rule in accordance with the length of a converted character in each stage of character conversion is adopted. In Embodiment 3, an example of switching a conversion rule depending upon whether or not the length of a converted character is a prime number will be described. As an example, variable-length key generation processing of a one-sparse language will be described.

[0090] The configuration itself of the variable-length key cryptosystem of Embodiment 3 may be similar to that of Embodiment 2, and is shown in FIG. 5. In the example of Embodiment 3, as a conversion rule selection function, it is determined whether or not the length of a character string is a prime number in each stage of character conversion, whereby a conversion rule is switched. In the case where the length of a converted character string is a prime number, Conversion rule 1 is used, and in the case where the length of a converted character string is not a prime number, Conversion rule 2 is used.

[0091] The conversion rule holding part 31a holds two conversion rules: Conversion rule 1 and Conversion rule 2, as shown in FIG. 7(a). According to the conversion rule selection function of the conversion rule selection function processing part 35, in the case where the length of a character string is a prime number, Conversion rule 1 is used in each process of character conversion, and in the case where the length is not a prime number, Conversion rule 2 is used.

[0092] In the first processing, the variable-length key generation processing part 30a generates a character string by starting from A and switching a conversion rule depending upon whether or not the length of a character string is a prime number in each stage of character conversion, as shown in FIG. 7(b). In this example, assuming that the length of a plain text is 7, a conversion rule to be used is switched based on the length of a converted character string generated from an initial character string A, whereby a converted character string “babaabA” with a length of 7 is obtained, as shown in FIG. 7(b). The second to fourth processings are the same as those in Embodiment 2, so that the detailed description thereof will be omitted here. In this example, the information in the used key list 33 is referred to, whereby it is detected that a converted character string with a length of 7 has been used. Then, a converted character string “ababbaaA” with a length of 8 is converted to “10100111” to generate an encryption key with upper 7 bits of “1010011”, and a stream code is generated based on this encryption key.

[0093] In the variable-length key generation processing part of the receiver system, a converted character string “babaabA” with a length of 7 is generated based on the length of 7 of an encrypted text. The information in the used key list is referred to, whereby it is detected that the converted character string with a length of 7 has been used. Then, a converted character string “ababbaaA” with a length of 8 is converted to “10100111” to generate an encryption key with upper 7 bits of “1010011”. A stream code is decrypted based on this encryption key to obtain a plain text.

[0094] In the same way as in Embodiment 3, the variable-length key cryptosystem of Embodiment 4 has a plurality of conversion rules and switches a conversion rule to be used in each stage of character conversion by a conversion rule selection function. As the conversion rule selection function, a function of switching a conversion rule in accordance with the length of a converted character in each stage of character conversion is adopted. In Embodiment 4, an example of switching a conversion rule based on the result of a residue number operation of a length of a converted character will be shown. As an example, variable-length key generation processing of a one-sparse language will be described.

[0095] The configuration of the variable-length key cryptosystem of Embodiment 4 is as shown in FIG. 5, in the same way as in Embodiment 2. In the example of Embodiment 4, a residue number operation is used as a conversion rule selection function.

[0096] The conversion rule holding part 31a holds four conversion rules (Conversion rule 1 to Conversion rule 4) as shown in FIG. 8(a). According to the conversion rule selection function of the conversion rule selection function processing part 35, assuming that x is a length of a character string, a conversion rule of the number of the result of the residue number operation of 3^xmod5 is used. More specifically, character conversion is conducted; every time the length of a character string is changed; a residue number operation of the length is conducted; and character conversion in the subsequent stage is conducted using a rule of the number of an obtained numerical value.

[0097] In the first processing, the variable-length key generation processing part 30a starts from an initial character string ABCD, conducts a residue number operation of the length of a character string in each stage of character conversion, and switches a conversion rule based on the result, thereby generating a character string, as shown in FIG. 8(b). In the first character conversion, the length of an initial character string ABCD is 4, Conversion rule 1 is adopted from 3^xmod5=1, and “aABCD” is obtained. Then, the length of the converted character string is 5, so that 3^xmod5=3 is obtained, and Conversion rule 3 is adopted to obtain “bABcCD”. Conversion thus proceeds, whereby “aABbCdD” with a length of 7 is obtained. The second to fourth processings are the same as those in Embodiment 2. Therefore, the description thereof will be omitted here. In this example, the information in the used key list 33 is referred to, whereby it is detected that a converted character string with a length of 7 has been used. Then, a converted character string “bAbBaCcD” with a length of 8 is generated, and converted to numerical values in accordance with the correspondence between the characters and the numerical values shown in FIG. 8(b), whereby a numerical value string “00011011” is generated. Upper 7 bits are extracted to obtain an encryption key “0001101”. A stream code is generated based on the encryption key.

[0098] In the variable-length key generation processing part of the receiver system, a converted character string “aABbCdD” with a length of 7 is generated based on the length of 7 of an encrypted text. In this example, the information in the used key list 33 is referred to, whereby it is detected that the converted character string with a length of 7 has been used. Then, a converted character string “bAbBaCcD” with a length of 8 is generated, a numerical value string “00011011” is generated, upper 7 bits are extracted, and finally, an encryption key of “0001101” is generated. A stream code is decrypted based on the encryption key to obtain a plain text.

[0099] In the variable-length key cryptosystem of Embodiment 5, a combined initial character string of characters used for generating an encryption key and dummy characters different from the characters used for generating an encryption key is used as an initial character string, and a combined conversion rule of a character conversion rule with respect to characters used for generating an encryption key and a character conversion rule with respect to dummy characters different from the characters used for generating an encryption key is used as a conversion rule. Character conversion is repeated using the combined initial character string and the combined conversion rule, and only characters to be used for generating an encryption key are extracted from the generated character string, whereby an encryption key is generated. As an example, a one-sparse language will be described.

[0100] FIG. 9 shows a configuration of the variable-length key cryptosystem of Embodiment 5. In FIG. 9, reference numeral 100b denotes a sender system that encrypts a plain text, and 200b denotes a receiver system that decrypts an encrypted text to generate a plain text. Reference numeral 300 denotes a communication path through which a sender 1 and a receiver 2 exchange data.

[0101] The sender system 100b includes a data input part 10, a data string length detection processing part 20, a variable-length key generation processing part 30b, a stream code processing part 40, and a communication interface 50. A controller, a memory, and the like required for controlling a system are not shown.

[0102] The data input part 10, the data string length detection processing part 20, the stream code processing part 40, and the communication interface 50 are the same as elements denoted with the same reference numerals in the sender system 100 described in Embodiment 1. Therefore, the description thereof will be omitted here.

[0103] The variable-length key generation processing part 30b includes a dummy character removal processing part 37, as well as a conversion rule holding part 31b, a converted character string generation processing part 32b, a used key list 33, an encryption key converting part 34, a conversion rule selection function processing part 35, and a hash function processing part 36.

[0104] Herein, the dummy character removal processing part 37 removes dummy characters from a converted character string generated by the converted character string generation processing part 32b to extract only characters involved in generating an encryption key.

[0105] In Embodiment 5, an initial character string includes dummy characters that are not used in generating an encryption key. Herein, as an example, “ABCD” used in Embodiment 4 is used as an initial character string, and “B” and “b” are assumed to be dummy characters that are not used in generating an encryption key. Furthermore, in Embodiment 5, a plurality of sets of conversion rules are used, which also includes a conversion rule regarding dummy characters. As an example, in the same way as in Embodiment 4, the conversion rule holding part 31b holds four conversion rules (Conversion rule 1 to Conversion rule 4) as shown in FIG. 10(a). In these conversion rules, “B” and “b” are assumed to be dummy characters that are not used in generating an encryption key.

[0106] It is assumed that the conversion rule selection function of the conversion rule selection function processing part 35 uses a conversion rule of the number of the result obtained by a residue number operation of 3^xmod5 (where x is the length of a character string), in the same way as in Embodiment 4.

[0107] In the same way as in Embodiment 4, in the first processing, the variable-length key generation processing part 30b generates a character string by starting from “ABCD”, conducting a residue number operation of the length of a character string in each stage of character conversion, and switching a conversion rule shown in FIG. 10(a) in accordance with the result of the residue number operation, as shown in FIG. 10(b).

[0108] In Embodiment 5, the following fifth processing is conducted prior to the second processing described in Embodiment 2. In the fifth processing, the dummy character removal processing part 37 removes dummy characters from a converted character string generated by the converted character string generation processing part 32b to extract only characters that are used in generating an encryption key. If the length of the converted character string does not reach the length of a plain text, the first processing is continued to conduct character conversion, and the character conversion is repeated until the length of the converted character string composed of only the characters that are used in generating an encryption key reaches the length of a plain text. In this example, assuming that the length of a plain text is 7, in the case where the length of a converted character string by the first processing is 7 (i.e., “aABbCdD”) as shown in FIG. 10(b), the length becomes 5 (i.e., “aACdD”) by removing the dummy characters in the fifth processing. Therefore, the first processing is continued. The converted character string “bAbBaCcD” with a length of 8 becomes “AaCcD” with a length of 5 by removing the dummy characters in the fifth processing, so that the first processing is further continued. When the converted character string “cdAcBbcCdD” with a length of 10 is obtained, the converted character string “cAccCdD” with a length of 7 is obtained after removal of the dummy characters. Therefore, “cAccCdD” is obtained in the fifth processing.

[0109] The second to fourth processings are the same as those in Embodiment 2. In this example, it is assumed that the converted character string with a length of 7 has not been used in the used key list 33. Finally, “cAccCdD” is converted to binary numbers constituting an encryption key to obtain an encryption key “1011001”. A stream code is generated by using the encryption key.

[0110] In the variable-length key generation processing part of the receiver system 200b, conversion is started from an initial character string “ABCD” based on the length of 7 of an encryption key, the first to fifth processings are conducted, and an encryption key “1011001” is obtained from “cAccCdD”. A stream code is decrypted with the encryption key to obtain a plain text.

[0111] The variable-length key cryptosystem of the present invention can be configured with various computers by recording a program describing processing operations for realizing the above-mentioned configuration on a computer-readable recording medium. Examples of a recording medium storing a program containing processing operations for realizing a variable-length key cryptosystem of the present invention include a recording medium 400 in a recording apparatus on a network and a recording medium 405 such as a hard disk and a RAM of a computer, as well as a portable recording medium 401 such as a CD-ROM 402 and a flexible disk 403. In execution of the program, the program is loaded onto a computer 404, and executed on a main memory.

[0112] It is understood that, according to the variable-length key cryptosystem of the present invention, various modifications and alterations can be made in the above-mentioned method and apparatus without departing from the above-mentioned concept of the present invention. Therefore, it should be noted that the present invention is not limited to the above-mentioned embodiments.

[0113] Because of the above-mentioned configuration, the present invention has the following effects.

[0114] In the variable-length key cryptosystem of the present invention, since an encryption key and a decryption key are selected depending upon the length of a plain text and an encrypted text, the trouble of distributing a key is saved.

[0115] Parameters of secret that should be shared by an encryption apparatus and a decryption apparatus are an initial string, sets of conversion rules, and a conversion rule selection function, and a genuine random number sequence for encrypting a hash function value, for constituting a variable-length key generation processing part. These parameters can be represented in a small information amount. Therefore, they can be sent safely and easily, for example, by using a public key cryptosystem.

[0116] In the encryption system of the present invention, a key is not used twice. Therefore, there is no possibility that a plain text is obtained only from an encrypted text. It is also impossible to predict a variable-length key generation processing part from a key that is obtained arbitrarily, because there is an infinite number of sets of parameters constituting the variable-length key generation processing part. Therefore, the safety of the cryptosystem is very high.

[0117] A key is generated in the variable-length key generation processing part by repeating character conversion and a conversion rule selection function. A key can be generated at a high speed if the conversion rule selection function is set so that calculation is easy.

[0118] Once a key is generated, encryption can be conducted only by addition, and decryption can be conducted only by subtraction. Therefore, encryption and decryption can be conducted at a high speed. In the case where a plain text, an encrypted text, and a key are composed of 0 and 1, encryption and decryption are conducted by XOR operation, and can be conducted at a higher speed.

[0119] An encryption apparatus and a decryption apparatus include the same constituent element (e.g., a variable-length key generation processing part). Therefore, it is actually easy to configure these apparatuses.