JPH035101B2 - - Google Patents

Description

[Detailed Description of the Invention] The present invention is used in a digital transmission system to convert a message into a data series to prevent the message from being stolen by anyone other than the intended recipient, or to restore the converted data series to the original message. The present invention relates to a code converter.

The following is a well-known method for preventing messages from being intercepted in a digital transmission system. Let the encryption key be (n, e) and the decryption key (n, d). Here, n, e, and d are positive integers obtained by a certain predetermined method. On the sending side, the input data a, which is any non-negative integer less than n, is converted to the remainder of a ^e divided by n and sent, and on the receiving side, the encrypted data b is converted to the remainder of b ^d divided by n. and decrypt it. Regarding the method for determining n, e, and d, the validity of the algorithm, and confidentiality, please refer to the literature Communications of the ACM, Volume 21, No. 2, 1978.
I will not omit it as it is detailed on pages 120-126 of January 2019. Encryption and decryption are the same type of transformation, and the input x
It outputs the remainder when x ^m is divided by n (m is a positive integer). Conventionally, a code converter that outputs the remainder when x ^m is divided by n for input x requires a processing time that is 2 × [log ₂ m] times the processing time of the internal multiplier, which reduces the overall processing time. It took up a large proportion of my time. (See the above literature). [ ] represents the integer part.

An object of the present invention is to provide a code converter whose processing time is short and requires only [log ₂ m] times the processing time of a multiplier used internally, and whose scale is not so large.

The configuration and operating principle of the present invention will be explained in detail below using the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. In the figure, 101 is an input terminal, 102 is an output terminal, 103 is a data cycler that cyclically repeats a plurality of consecutive input data for a predetermined time, and 104 is the data cycler 103.
105 is the selective multiplier 104 that converts the data from the squarer 106 and the data from the squarer 106 described later into the product of both or data of either one of them.
A remainder unit 106 converts the data from the remainder unit 105 into a remainder obtained by dividing it by a predetermined positive integer n, and a square unit 106 multiplies the data from the remainder unit 105 modulo n. Here, the result of squaring the data x modulo n means x ² or the remainder when x ² is divided by n.

The operating principle of the present invention will be explained using FIG.
Let m and n be predetermined positive integers, and the result of binary expansion with m is expressed as equation (1).

m=2 ⁱ⁰ +2 ⁱ¹ +...+2 ^iK (1) where k, i ₀ , i ₁ ,..., i _K are non-negative integers and are expressed in equation (2)
Satisfy.

i ₀ ＞i ₁ ＞……＞i _K (2) Represent the timing as 0, 1, 2, …. For simplicity of explanation, selective multiplier 104 and remainder unit 10
5. It is assumed that the squarer 106 can process everything in one timing interval time, and the period of the output sequence of the data cycler 103 is assumed to be three timing interval times. Let the input data series applied to the input terminal 101 be a ₀ , a ₁ , a ₂ , . . . . Data cycler 10
3 receives a ₀ , a ₁ , a ₂ and cyclically returns a ₀ , a ₁ ,
Output a ₂ , a ₀ , a ₁ , a ₂ , ..., a ₀ , a ₂ in i ₀ cycle, then input a ₃ , c ₄ , a ₅ and cyclically output a ₃ ,
Output a ₄ , a ₅ , a ₃ , a ₄ , a ₅ , ...a ₃ , a ₄ , a ₅ for _i0 cycles. The same thing is repeated below. At this time, the output terminal 102 shows that the remainder obtained by dividing ^am ₀ , ^am ₁ , ^am ₂ , ^am ₃ , . . . by n is output. To do this, what kind of processing should data a ₀ undergo and output terminal 10?
It is enough to follow what is output in 2. The selective multiplier 104 passes the data from the data cycler 103 as is at timings 0, 1, and 2, and transmits the data at timings 3(i ₀ -i ₁ ), 3(i ₀ -i ₁ )+1, 3(
i ₀
−i ₁ )+2,…, 3(i ₀ +i _K ), 3(i ₀ −i _K )+1, 3
At (i ₀ −i _K )+2, the data from the data circulator 103 and the data from the squarer 106 are converted into a product, and at other timings, the data from the squarer 106 is passed through as is. At timing 0
a ₀ passes through the selective multiplier 104 as a ₀ , and at timing 1, a ₀ passes through the remainder unit 105 as a ₀ ,
At timing 2, a ₀ passes through the squarer 106 and becomes a ² ₀
(m ₀ dn) and is input to the selective multiplier 104. m ₀ dn means modulo n. At timing 3 (i ₀ −i ₁ ), the selective multiplier 104 combines the data a ₀ from the data circulator 103 with the squarer 106
The data from a ₀ ^2i0-i1 (modn) is the product a ₀ ^2i0-i1+1
(modn), timing 3 (i ₀ − i ₁ ) + 1
So a ₀ ^2i0-i1+1 (modn) is determined by remainder unit 105.
It is converted to the remainder when a ₀ ^2i0-i1+1 is divided by n, and at timing 3 (i ₀ - i ₁ ) + 2, the division when a ₀ ^2i0-i1+1 is divided by n is converted to a ₀ ^2i0-i1 by the squarer 106. ⁺¹⁺² (modn) and input to the selective multiplier 104. In this way, at timing 3i ₀ +1, the remainder obtained by dividing a ₀ ^2i0+2i1+ . . . ^+2iK = a ^m ₀ by n is output from the multiplier 105 to the output terminal 102. Similarly timing 3i ₀ +
2 and 3 (i ₀ +1), a ^m _{1 and} a m 1 are respectively applied to the output terminal 102.
The remainder when a ^m ₂ is divided by n is output. Since it is pipelined, the processing time is approximately i ₀ timing intervals per one input data, that is, [log ₂ m]. That is, the processing time of the multiplier is [log ₂ m], which is shorter than the conventional method.

FIG. 2 is a block diagram illustrating one embodiment of a selective multiplier. In the figure, 201 and 202 are input terminals, 203 is an output terminal, 204 is a multiplier, and 205
is a rotary switch. The multiplier 204 multiplies the data from the input terminals 201 and 202, and the rotary switch 205 selects and outputs one of the data from the two input terminals 201 and 202 and the multiplier 204 according to a timing signal.

In this embodiment, the rotary switch can be replaced with a selector.

FIG. 3 is a block diagram showing one embodiment of the data cycler. Data input from the input terminal 301 is put into the shift register 303. If the contents of the shift register 303 are set as a ₀ , a ₁ , a ₂ in order of oldest contents, the commutator 304 sequentially reads a ₀ , a ₁ , a ₂ , a ₀ , a ₁ , a ₂ , . . . from each output of the shift register 303. is output to the output terminal 302.

In this embodiment, the commutator can be replaced with a rotary switch or a selector.

In the present invention, it is assumed that the selective multiplier, remainder unit, and squarer have the same processing time, but even if they are different, the period of the output sequence of the data cycler may be changed appropriately, and the squarer converts the data x into x ² It is also possible to use a circuit that not only converts x 2 to the remainder of x ² divided by n, but these conversions are included in the present invention.

As explained in detail above, if the device of _the present invention is used, _{a m} ⁰ _,
Since the series of remainders obtained by dividing each of a ^m ₁ , a ^m ₂ , ... by n can be easily calculated in a short time, the drawbacks of the conventional technology are eliminated, and it is effective when applied to private communications in digital transmission systems. Extremely large.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing the configuration of the present invention, FIG. 2 is a diagram showing an embodiment of a selective multiplier, and FIG. 3 is a diagram showing an embodiment of a data cycler. In the figure, 101,
201, 202, 301 are input terminals, 102, 2
03, 302 are output terminals, 103 is a data cycler, 104 is a selective multiplier, 105 is a remainder unit, 1
06 is a squarer, 204 is a multiplier, 205 is a rotary switch, 303 is a shift register, 30
4 each indicates a commutator.

Claims (1)

[Claims] 1. Input data examples a _{1 ,} a ₂ ... of arbitrary non-negative integers less than a predetermined first positive integer n are raised to powers a ₁ , a ₂ , ... by a predetermined second positive integer m. A code converter that outputs the remainder after dividing each by n includes a data cycler that cyclically repeats a plurality of consecutive input data for a certain predetermined time, and a data cycler that cyclically repeats a plurality of consecutive input data for a predetermined time, and a data cycler that outputs the remainder after dividing each by n. a selective multiplier that converts data into the product of both or data of either one; a remainder unit that converts the data from the selective multiplier into a remainder when divided by n; and a remainder unit that converts the data from the remainder unit by multiplying n. 1. A code converter comprising a squarer for converting data into squared data as , and outputting data from the remainder unit in the final cycle of the data circulator.