JPH01277280A - Encoding and decoding method - Google Patents

Abstract

PURPOSE:To suppress the increase of the amount of data even when information is encoded by comparing and outputting the numeric value expression of inputted information with a numeric value supplied in advance. CONSTITUTION:When the numeric value expression of the inputted information is less than the numeric value supplied in advance, output obtained by applying an encoding method on the information is set as an intermediate result, and when it is not less than the numeric value supplied in advance, the output obtained by applying conversion decided in advance on the inputted information is set as the intermediate result. The output obtained by applying code conversion decided in advance on the intermediate result is set as a new intermediate result. And when the new intermediate result is less than the numeric value supplied in advance, the output at the time of applying the encoding method on the intermediate result is outputted as a code, and when an obtained intermediate result is not less than the numeric value supplied in advance, the output at the time of applying the conversion decided in advance on the new intermediate result is outputted as the code. In such a way, it is possible to prevent the amount of data from being increased even when the information is encoded.

Description

[Detailed Description of the Invention] (Industrial Application Field) The present invention is designed to prevent unauthorized persons from illegally viewing data in communications and computers. The present invention relates to an encoding method for encoding data into an indecipherable code, and a decoding method for restoring the original data from the code.

(Prior Art) The R8A method is a typical method known and used as an encoding method for converting information into a code and a decoding method for restoring the original information from the code. R8A method is 1
It was proposed by Rivest, Shamir, and Eidelman in 1978, and is called the R8A method by the initials of the proposers (R, L, RLVEST, A, Sham).
ir and L, Addlemans ”AMet
hod for ObtaInlng Digital
Signatures andPublic-key
Cryptosyste+ms+”Coa
t, ACM, Vol.

2 violet, No, 2. pp, 120-12G, 1978
). Regarding the R8A method, a simple explanation can be found, for example, in Chapter 10 of a book written by Miyashiro, Genshin, and Jibun under the title "Theory of Information and Codes" and published by Goupa Shoten in 1988. There is.

For convenience, the following explanation will only explain the case where information is encoded into a code to prevent unauthorized persons from viewing the information, and the R8A method will be used as an example of the encoding method and decoding method. I will only explain. In addition, below, the operation of converting information into a code is called encoding.
The operation of restoring the original information from the code is also called decryption. In the encoding method and decoding method in the R8A method, first, a numerical value e is prepared for the encoding layer and a numerical value d is prepared for the decoding layer. Also, prepare a numerical value n as a common key used for encoding and decoding.

It is assumed that these numerical values e and ds n are integers and are predetermined. Note that the method of determining these values is not directly related to the present invention, so the explanation will be left to the aforementioned book.

To encode using the R8A method, first obtain a numerical representation P of information. Since information is usually expressed as a 0.1 pit series,
By dividing a bit string of information into finite lengths, a numerical representation can be automatically obtained. Therefore, in the following, we will not distinguish between information and the numerical representation of information unless there is confusion. Then, the following calculation is performed on the information P to obtain the code C.

C=P sod n That is, the remainder when information P is raised to the power of e and divided by n is defined as code C. To restore the original information P from cipher C, cipher C
The book states that the following calculations should be performed for .

P''Cmad n That is, the information P is restored by calculating the remainder when the code C is raised to the d power and divided by n.

Note that the R8A law is not only intended to encode information in a code that prevents unauthorized persons from viewing it, but also to allow the person who sent the information to later deny that he or she sent the information and commit fraud. For example, the above-mentioned document describes that it is also used for the purpose of preventing unauthorized persons from disseminating false information by pretending to be authorized persons.

(Problems to be Solved by the Invention) In the conventional method, it was necessary to make the information P smaller than the common IIn. This is because the remainder when divided by the common lin is calculated in the encoding process, so that it becomes impossible to distinguish between information whose numerical expression is P and information whose numerical expression is P+n. Moreover, since binary systems are used in communications and computers, the input information is usually divided so that the information P to be encoded is one bit shorter than the bit length of the common key n.

Furthermore, in normal communications and computers, information is managed by dividing it into lengths that are powers of 2, such as 1024 bits, so even if the bit length is increased by 1 bit, in the previous example
024 bits are also expanded. For this reason, when encoding is performed using the conventional method, there is a problem in that the efficiency of information transmission and storage is greatly degraded.

An object of the present invention is to provide an encoding method and a decoding method that solve the above problems.

(Means for Solving the Problems) The encoding method according to the present invention performs a predetermined operation on input information, outputs the remainder when the result of the operation is divided by a predetermined numerical value, and In an encoding method that outputs a code corresponding to input information, if the numerical representation of the input information is smaller than the predetermined numerical value, the output obtained by applying the encoding method to the input information is a first step of setting an output obtained by performing a predetermined transformation on the input information as an intermediate result if the numerical representation of the input information is not smaller than the predetermined value; a second step in which a predetermined code conversion is performed on the intermediate result of the first step and an output obtained as a new intermediate result;
If the intermediate result of the step is smaller than the predetermined value, the output when the encoding method is applied to the intermediate result of the second step is output as a code, and the intermediate result obtained in the second step is is not smaller than the predetermined value, a third step of outputting the output obtained by performing a predetermined transformation on the intermediate result obtained in the second step as a code. do.

For the above conversion and code conversion, input and output are 1
Any one-to-one correspondence is possible, but for the reasons described later, it is effective to output the input information as is, and for code conversion, it is effective to output the input information as is. Conversion that adds or subtracts a predetermined value or conversion that inverts the most significant bit of an input code is effective.

Furthermore, the decoding method according to the present invention performs a predetermined operation on an input code, and outputs the remainder when the operation result is divided by a predetermined numerical value, thereby providing information corresponding to the input code. In a decoding method that restores and outputs a If the numerical representation of the input code is not smaller than the predetermined numerical value, a first step of performing a predetermined inverse transformation on the input code and obtaining an output as an intermediate result; a second step in which an output obtained by performing a predetermined inverse code conversion on the intermediate result is set as a new intermediate result; For example, in the second step, the output when the decoding method is applied to the intermediate result obtained in the Tsubu is output as information, and the intermediate result obtained in the second step is smaller than the pre-given value. If not, the second
The method is characterized in that it includes a third step of performing a predetermined inverse transformation on the intermediate result obtained in the step and outputting the output as information.

Any inverse transformation and inverse code transformation can be used as long as the input and output correspond one-to-one, but for the reasons explained later, the inverse transformation can output the input code as is. Inverse code conversion is effective, and inverse code conversion involves adding or subtracting the input code and a predetermined value. Inverse conversion or inverse conversion that inverts the most significant bit of the input code is effective.

(Operation) The principle of the present invention is shown below. The bit length of cipher C is information P
To encode so that it is no longer than the bit length of
Common i! It is necessary to have a one-to-one correspondence between all information whose bit length is not longer than n and the cipher. If there is not a one-to-one correspondence, different information will be encoded in the same code, making it impossible to correctly restore the original information. In the conventional R3A method,
We.

If den is chosen well, there will be a one-to-one correspondence between information and codes that take a value smaller than the common mn. This is explained in detail in the book mentioned above. Therefore, the cipher C
In order to prevent the bit length of information P from becoming longer than the bit length of information P, information having a common value of 1jln or more and a code may be made to correspond one-to-one through a predetermined conversion. When encoding information P, if the information P is common! If it is smaller than In, it is encoded using a conventional encoding method and output, and if the information P is greater than or equal to the common key, it is sufficient to convert the information P into its transformation family and output it. Note that for convenience of explanation, the above encoding method will be referred to as a bit length preserving encoding method. To restore the original information P from the cipher C obtained by this encoding method, if the cipher C is smaller than the common IIn, it is restored and output using the conventional encoding method, and if the cipher C is smaller than the common an
If the above is the case, it is sufficient to perform the inverse of the above-mentioned transformation, that is, inverse transformation, on the cipher C and output it. Note that for convenience of explanation, the above decoding method will be referred to as a bit length preserving decoding method.

However, in the bit length preserving encoding method, although the bit length is not expanded, if the numerical representation P of input information is equal to or larger than the common Iin, the information is simply converted and output as is. Therefore, in applications where confidentiality is required, the following should be done.

First, let's make inputs and outputs correspond one-to-one, so that they are common! In
If the above number is input, code conversion is determined in advance so as to output a value smaller than the common 11n. Then, by applying this code conversion to the cipher obtained by performing bit length preserving encoding and applying bit length preserving encoding again, all information will be encoded. To restore the original information from the information encoded using the above encoding method, bit length preserving decoding is first performed on the cipher. Then, the obtained data is subjected to code conversion opposite to the code conversion described above, that is, inverse Hood conversion, and bit length preserving decoding is executed again. In this way, the original information can be restored.

Although the above explanation was limited to the R8A method, the present invention generally applies when a predetermined operation is performed on input data and the result of the operation is divided by a predetermined numerical value. It is clear that the present invention is applicable to encoding and decoding methods that output the remainder of . This is because the present invention has common l! among the properties of the R8A method! This is because only the property that there is a one-to-one correspondence between information having a value smaller than n and a code is used, and this property also holds true for general encoding and decoding methods as described above.

Additionally, in the above explanation, we limited the explanation to the case where unauthorized persons are prevented from viewing the information, but the person who transmitted the information later denies that he or she transmitted the information. It can also be applied to the purpose of preventing fraud or preventing unauthorized persons from disseminating false information by pretending to be authorized persons. It is clear, for example, from the above-mentioned documents, that the above-mentioned encoding and encryption can be combined to be applied to the latter purpose.

(Example) Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a functional block diagram of an encoding device constructed based on the encoding method of the present invention. In the figure, information input from an input terminal 101 is supplied to a comparator 102, an encoding circuit 103, and a converter 104. The comparator 102 compares the input numerical value, that is, information, with the common key n, and if the input numerical value is smaller than the common key n, outputs l, otherwise outputs 0. The encoding circuit 103 performs conventional encoding on the input and outputs the result. converter 1
04 performs a predetermined one-to-one conversion on the input numerical value or information. The switch 105 selects the output of the encoding circuit 103 if the output of the comparator 102 is 1, and selects the output of the converter if the output is 0, and supplies the selected output to the code converter 106. The code converter 106 performs predetermined code conversion on the input and outputs the result.

The output of the code converter 106 is supplied to a comparator 107, an encoding circuit 108, and a converter 109. comparator 107,
The relationship between the encoding circuit 108, the converter 109, and the switch 110 is as follows: the comparator 102, the encoding circuit 103, and the converter 104.
The relationship is similar to that between the switch 105 and the switch 105, but the common key, encoding key, and conversion used in the former do not necessarily need to be the same as those used in the latter. The output of the switch 110 is supplied to an output terminal 111, and is output from the output terminal 111 as a code.

FIG. 2 is a functional block diagram of a decoding device configured to restore original information from the cipher output by the encoding device of FIG. 1 based on the decoding method of the present invention. In the figure, a code input from an input terminal 201 is supplied to a comparator 202, a decryption circuit 203, and an inverse converter 204. The comparator 202 has the input numerical value, ie, the code, and the common l! Compare n, and if the input value is smaller than the common lIn, output 1, otherwise output 0. The decoding circuit 203 performs conventional decoding on the input and outputs the result. The inverse converter 204 performs the inverse conversion of the input numerical value, that is, the code, to the converter 109 in FIG. The switch 205 selects the output of the decoding circuit 203 if the output of the comparator 202 is 1, and selects the output of the inverse converter if the output is 0, and supplies the selected output to the inverse code converter 206.

The inverse code converter 206 performs code conversion on the input in a manner opposite to that of the code converter 106 in FIG. 1, and outputs the result. The output of the inverse code converter 206 is sent to a comparator 207,
The signal is supplied to a decoding circuit 208 and an inverse converter 209. The relationship between the comparator 207, the decoding circuit 208, the inverse converter 209, and the switch 210 is as follows: the comparator 202, the decoding circuit 203,
The relationship is similar to that between the inverse converter 204 and the switch 205.

However, the comparator 207, decoding circuit 208, and inverse conversion circuit 2
The common key, decryption silver, and inverse transformation used in 09 are the comparator 102, encoding circuit 103, and converter 1 in FIG. 1, respectively.
It has the following relationship with that used in 04. That is, the common key is the same for the former and the latter, the decryption key of the former corresponds to the encoding key of the latter, and the inverse transformation of the former is the inverse of the transformation of the latter. The output of the switch 210 is supplied to an output terminal 211, and is output from the output terminal 211 as restored information.

Note that the above comparators 102, 107, 202.207,
The switches 105, 110, 205, and 210 are constructed by connecting a plurality of standard logic integrated circuits. In addition, the above-mentioned encoding circuits 103 and 108 and decoding circuit 203
．． 208 can be configured with a signal processor such as μP077230 developed by NEC Corporation for signal processing and commercially available. Regarding this, please refer to ``On exponentiation modular calculation using signal processors'' in the Proceedings of the 1986 IEICE Information and Systems Division National Conference.
It is described in a paper titled "Lecture number 15)" and a paper titled "Realization of R8A cryptosystem using signal processor" (Lecture number A-298) in the Proceedings of the 1986 Institute of Electronics, Information and Communication Engineers Spring National Conference. ing.

The converters 104 and 109 described above can be constructed using, for example, a read-only memory, but by reading the contents of the memory, it is possible for a person who attempts to illegally view the data to know how the conversion is performed. Therefore, performing complex transformations in transformers 104 and 109 is not very effective in maintaining confidentiality. Therefore, considering the complexity of the device, it is more effective to output the data as is without conversion. In addition, when the conversion of the converters 104 and 109 outputs the input as it is, the inverse converter 20
The inverse transformation of 4.209 also outputs the input as is.

Although the above-mentioned hood converter 108 can be configured using a read-only memory, for example, the converter 104
．． For the same reason as No. 109, it is more effective not to perform complicated processing. A value not smaller than the common an, the common l!
Convert to a number smaller than n, and input and output are 1:1
The following is a simple code conversion that corresponds to .

FIG. 3 is a block diagram showing an embodiment of a circuit including a code converter 106 of an encoding apparatus constructed based on the encoding method of the present invention.

In FIG. 3, a plurality of NOT circuits 306 connect terminals 301
Commonly supplied to! Adder 303 inverts all bits of
The result is output from the output terminal 305.

Note that the carry input of the adder 303 is 1 from the terminal 304.
is supplied. With the above configuration, the common key n is subtracted from the input code, and the result is output.

FIG. 4 is an embodiment of a circuit that embodies the inverse Hood converter 206 of a decoding device constructed based on the decoding method of the present invention, and is a block diagram corresponding to the code converter of FIG. 3. It is a diagram. In FIG. 4, an adder 403 adds a common Inn supplied to a terminal 401 and a code supplied to an input terminal 402, and sends the result to an output terminal 4.
Output from 05. Note that O is supplied from a terminal 404 to the carry input of the adder 403.

FIG. 5 is a block diagram showing a second embodiment of a circuit that embodies the code converter 106 of the encoding device constructed based on the encoding method of the present invention. In FIG. 5, a NOT circuit 502 inverts the most significant bit of a code input from an input terminal 501 and sends the result to an output terminal 503.
Output from. Further, the lower bits of the code inputted from the input terminal 501 are outputted from the output terminal 503 as they are. Note that when the code converter is configured as described above, the corresponding inverse code converter has the same configuration as the code converter described above.

FIG. 6 is a block diagram showing a third embodiment of a circuit embodying the code converter 106 of an encoding device constructed based on the encoding method of the present invention. In FIG. 6, in the read-only memory 602, the number of address bits is L, and the number of data bits stored in each address is also L, and predetermined data is written in each address. The upper L bits of the code input from the input terminal 601 are stored in a read-only memory 602.
is supplied as an address signal, and the corresponding data is output from the output terminal 603. In addition, the input terminal 601
The lower bits of the food input from are output as they are. Note that when the code converter is configured as described above, the corresponding inverse converter has the same configuration as the code converter described above. However, data is written in advance in the read-only memory of the reverse code converter so as to perform code conversion in the opposite direction to that in the read-only memory 602 of the code converter.

FIG. 7 is a functional block diagram of a second encoding device constructed based on the encoding method of the present invention. In the figure, information input from an input terminal 701 is supplied to a switch 712. The switch 712 first selects information and supplies it to the comparator 702, the encoding circuit 703, and the converter 704. The comparator 702 compares the input numerical value and the common tsn, and outputs 1 if the input numerical value is smaller than the common Inn, otherwise outputs 0. The encoding circuit 703 performs conventional encoding on the input and outputs the result. The converter 704 performs a predetermined one-to-one conversion on the input numerical value. The switch 705 selects if the comparator 7
If the output of 02 is 1, the output of the encoding circuit 703 is selected; if it is 0, the output of the converter 704 is selected and supplied to the code converter 706. Hood converter 706 performs predetermined code conversion on the input and supplies the result to switch 712 . Switcher 712 then selects the output of code converter 706. Then, the above operations performed on the information are performed on the output of the code converter 706, and finally the output of the switch 705 is transferred to the output terminal 711.
is output as a cipher. Switching of switch 712 is controlled by a control signal supplied to input terminal 713. In addition, in the encoding device of FIG. 7, it is possible to repeat the above operation performed on information more than twice by repeatedly supplying the output of the switch 705 to the code converter 706 again. It is. It is also possible to use different common keys and encoding keys in each iteration.

FIG. 8 is a functional block diagram of a second decoding device constructed based on the decoding method of the present invention. In the figure, a code input from an input terminal 801 is supplied to a switch 812. The switch 812 first selects a code and supplies it to the comparator 802, the decryption circuit 803, and the inverse converter 804. Comparator 802 compares the input numerical value with the common fin, and outputs 1 if the input numerical value is smaller than the common key n, otherwise outputs 0. The decoding circuit 803 performs conventional decoding on the input and outputs the result. The inverse transformer 804 performs a predetermined one-to-one transformation on the input numerical value. The switch 805 selects if the comparator 80
If the output of 2 is 1, the output of the decoding circuit 803 is selected, and if it is 0, the output of the inverse converter 804 is selected and supplied to the inverse code converter 806. Inverse code converter 806 performs predetermined inverse code conversion on the input and supplies the result to switch 812 . Switcher 812 then selects the output of inverse code converter 806. Then, the above operations performed on the code are performed on the output of the inverse code converter 806, and finally the output of the switch 805 is outputted from the output terminal 811 as restored information. Switching of switch 812 is controlled by a control signal supplied to input terminal 813. Note that in the decoding device shown in FIG. 8, it is possible to repeat the above operation performed on the cipher more than twice by repeatedly supplying the output of the switch 805 to the code converter 706. be. However, the number of repetitions is made equal to the number of repetitions in the corresponding encoding device of FIG. Furthermore, in the decryption device of FIG. 8, it is possible to use a different common key and decryption layer in each iteration. However, in the corresponding encoding device of FIG. 7, the common key and encoding key are n (1) +
n■w ””e n(M) and e (IL e (2
Used in the order 1,...* e (M) and encoded! 1 e m * e■.

..., each decoding layer corresponding to e(N) is d(1
).

If d■,...,d(M), then the order of the common key and the decryption layer used in the decryption device is n(M),...

Let n■, n(1) and d(M), -, d■, d(1).

(Effects of the Invention) As described above, according to the present invention, even when information is encoded, the amount of encoded information does not increase, thereby reducing the cost for transmitting or storing information.

[Brief explanation of the drawing]

FIG. 1 is a functional block diagram showing an encoding device configured based on the encoding method of the present invention, FIG. 2 is a functional block diagram showing a decoding device configured based on the decoding method of the present invention, FIG. 3 is a block diagram showing an embodiment of a circuit including a code converter of an encoding device constructed based on the encoding method of the present invention, and FIG. This is an example of a circuit that specifically implements an inverse code converter in a decoding device constructed using the above-mentioned method, and is a block diagram showing a circuit corresponding to the food converter shown in FIG. 3. FIG. FIG. 6 is a block diagram showing the second and second embodiments of the code converter of the encoding device constructed based on the encoding method of the present invention. FIG. 3 is a block diagram showing a third embodiment of a circuit embodying a converter. FIG. 7 is a functional block diagram of a second encoding device configured based on the encoding method of the present invention, and FIG. 8 is a functional block diagram of a second decoding device configured based on the decoding method of the present invention. It is a functional block diagram. In the figure, 102.107, 202.207... comparator, 103
, 108... encoding circuit, 104, 109... converter, 105, 110.205, 210... switching device,
10B...Code converter, 203, 208...Decoding circuit, 204.209...Inverse converter, 20B...
Reverse code converter.

Claims (10)

[Claims] (1) An encoding method that performs a predetermined operation on input information, outputs the remainder when the operation result is divided by a predetermined value, and outputs a code corresponding to the input information. If the numerical representation of the input information is smaller than the predetermined value, the output obtained by applying the encoding method to the input information is set as an intermediate result, and the numerical representation of the input information is smaller than the predetermined value. If the value is not smaller than the given value, the first step is to perform a predetermined transformation on the input information and use the output obtained as the intermediate result; a second step of converting the output obtained by code conversion into a new intermediate result; output as a code, and if the intermediate result obtained in the second step is not smaller than the predetermined value, apply a predetermined conversion to the intermediate result obtained in the second step. An encoding method comprising: a third step of outputting the output as a code. (2) Perform a predetermined operation on the input code, output the remainder when the operation result is divided by a predetermined value, and restore and output the information corresponding to the input code. In the decoding method, if the numerical representation of the input code is smaller than the pre-given value, the output obtained by applying the decoding method to the input code is used as an intermediate result, and the numerical representation of the input code is is not smaller than the predetermined value, a first step in which the input code is subjected to a predetermined inverse transformation and the output obtained is an intermediate result; and for the intermediate result of the first step; a second step in which the output obtained by performing a predetermined inverse code conversion is used as a new intermediate result; and if the intermediate result obtained in the second step is smaller than the predetermined value, the second step The output when the decoding method is applied to the intermediate result obtained in step 2 is output as information, and if the intermediate result obtained in the second step is not smaller than the predetermined value, then in the second step A decoding method characterized by comprising: a third step of outputting as information an output when a predetermined inverse transformation is performed on the obtained intermediate result. (3) The encoding method according to claim 1, wherein the predetermined transformation is a transformation that outputs input information as it is. (4) The decoding method according to claim 2, wherein the predetermined inverse transformation is a transformation that outputs the input code as it is. (5) The encoding method according to claim 1 or 3, wherein the predetermined code conversion is a conversion that adds or subtracts an input code and a predetermined numerical value. (6) The decoding method according to claim 2 or 4, wherein the predetermined inverse code conversion is a conversion that adds or subtracts an input code and a predetermined numerical value. (7) Claim 1 or 3, wherein the predetermined code conversion is a conversion that inverts the most significant bit of the input code.
Encoding method described. (8) The decoding method according to claim 2 or 4, wherein the predetermined inverse code conversion is a conversion that inverts the most significant bit of the input code. (9) In the encoding method according to claim 1, the steps from step 2 to step 3 are executed multiple times using the output of step 3 as an intermediate result, and the intermediate result of the last executed step 3 is output as a code. encoding method. (10) In the decoding method of claim 2, the steps from step 2 to step 3 are executed multiple times using the output of step 3 as an intermediate result, and the intermediate result of the last executed step 3 is decoded. Decoding method to output as information.