JP6972593B2 - How to operate the feedback shift register circuit and feedback shift register - Google Patents

Description

The disclosure of the present application relates to a feedback shift register circuit and a method of operating the feedback shift register.

Cryptography is roughly divided into public key cryptography and common key cryptography. The public key encryption method is a method that uses different keys for encryption and decryption, and while the key for encryption (public key) is open to the public, the key for decrypting the ciphertext (private key). ) Is confidential information only for the recipient to maintain security. On the other hand, the common key cryptosystem is a method in which the same key (secret key) is used for encryption and decryption, and by making this secret key information that is unknown to a third party other than the sender and the receiver. Keep it safe.

Symmetric-key cryptography is often used in challenge-response authentication systems. First, the certifier sends a random value called a challenge to the subject. The person to be authenticated uses the private key shared with the certifier in advance, and the received challenge is encrypted with common key cryptography as plain text. The obtained ciphertext is sent to the certifier as a response. Similarly, the certifier uses the private key shared in advance and encrypts the sent challenge as plain text with common key cryptography. Check if the obtained ciphertext matches the received response (ciphertext). Since these two ciphertexts match only when the subject holds the secret information (private key) shared in advance, the certifier can identify the subject.

On the other hand, it is said that the number of devices connected to a network and controlled by a computer is increasing year by year, and it is expected that the number of devices to be authenticated using the above-mentioned authentication system will increase accordingly. That is, since the number of persons to be authenticated who are required to be accommodated in the authentication system increases, it is indispensable to improve the processing capacity of the certifier per unit time. Here, the common key cryptographic algorithm is implemented by software or hardware, but in general, since the common key cryptographic processing has many small bit unit arithmetic processing, the implementation by hardware is better than the implementation by software. , It is known that the processing efficiency per circuit scale is high. Considering the use of hardware-implemented common key cryptography on the certifier side, efficient implementation of the cryptographic hardware is a very important issue in industry.

A linear feedback shift register or a non-linear feedback shift register is often used for cryptographic processing hardware. The linear feedback shift register is used, for example, as a stream cipher or a pseudo-random number generator. Non-linear feedback shift registers are used, for example, in the implementation of cryptographic schemes such as KATAN and Trivium. In a linear or non-linear feedback shift register (hereinafter referred to as a feedback shift register), the output value of a linear or non-linear feedback function calculated with the current state (bit pattern) of the shift register as an input is the next output value to the shift register. It is a 1-bit feedback input of the state. Combination logic circuits are used as hardware for calculating these linear or non-linear feedback functions.

In order to operate the feedback shift register at high speed, it is necessary to increase the operating clock frequency, but in general, the clock period cannot be shorter than the time required for the logical operation by the combined logic circuit. That is, the operating speed of the feedback shift register is limited by the speed of the logical operation for calculating the feedback function. Since the speed of the logical operation of the combined logic circuit depends on the operating speed of each logic element constituting the logic circuit, it is difficult to improve the logical operation speed itself.

The pseudo-random sequence generated by the linear feedback shift register is used for various purposes such as scrambling, spread spectrum, pseudo-noise generation, and error rate measurement, in addition to cryptographic applications. Therefore, it is desired to improve the operating speed of the feedback shift register not only in the encryption field but also in various fields.

Japanese Unexamined Patent Publication No. 06-07525 Japanese Unexamined Patent Publication No. 2002-352582

In view of the above, it is desired to provide a feedback shift register that can operate at high speed without being limited by the speed of the combinational logic circuit that calculates the feedback function.

Feedback shift register circuit includes a shift register, receives the register output of a plurality of bit positions of the previous SL shift register as an input, a combinational logic circuit for implementing a feedback function that generates a feedback value stored in the shift register, wherein It functions as a part of the shift register at a bit position lower than the plurality of bit positions of the shift register, and receives a 1-bit operation value which is the first intermediate result of the operation of the feedback function from the combination logic circuit. Data stored in the register sequence including a register sequence stored at the lowest bit position and a register group including an additional register for receiving and storing the second intermediate result of the operation of the feedback function from the combination logic circuit. wherein by performing a logical operation for each state transition data stored in the additional register, performs some logical operation of the combinational logic circuit while propagating data to the register series with the state transition with respect to the The feedback value is input to the most significant bit position of the register string.

According to at least one embodiment, it is possible to provide a feedback shift register that can operate at high speed without being limited by the speed of the combinatorial logic circuit that calculates the feedback function.

It is a figure which shows the structure of the round processing part of KATAN & KTANTAN when the block size which is the unit of encryption processing is 32 bits. It is a figure which shows an example of the structure of the generalized feedback shift register. It is a figure which shows an example of the general structure of the feedback shift register which can increase the operation speed. It is a figure which shows an example of the structure of the combination logic circuit which realizes the nonlinear function used in KATAN 32 and KTANTAN 32. It is a figure which shows the equivalent logic circuit of the combination logic circuit shown in FIG. It is a figure which shows typically the operation which shifts while performing a logical operation with respect to the data stored in a register string. It is a figure which shows an example of the configuration which applied the feedback shift register of FIG. 3 to KATAN 32 and KTANTAN 32. It is a figure which shows another example of the configuration which applied the feedback shift register of FIG. 3 to KATAN 32 and KTANTAN 32. It is a figure which shows still another example of the structure which applied the feedback shift register of FIG. 3 to KATAN 32 and KTANTAN 32. It is a figure which shows an example of the configuration of another cryptographic processing hardware. It is a figure which shows an example of the configuration of still another cryptographic processing hardware. It is a figure which shows an example of the hardware composition of the system which incorporated the feedback shift register of FIG.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the drawings, the same or corresponding components are referred to by the same or corresponding numbers, and the description thereof will be omitted as appropriate.

In the following description, the feedback shift register of the present invention will be described using the feedback shift register used in the encryption method KATAN & KTANTAN as an example. Specifically, for feedback shift register type cryptographic hardware (mounting circuit), which is a type of common key cryptography, the maximum delay time is shortened by dividing the combination circuit while maintaining the equivalence of logic. However, the processing speed is increased. As will be described later, the present invention can also be applied to circuit implementation of a linear feedback shift register used as a pseudo-random number generator.

First, the hardware configuration of KATAN & KTANTAN will be described. The encryption method KATAN & KTANTAN has been proposed as being compact and can be implemented with the smallest size encryption hardware, and is particularly lightweight among the hardware-implemented common key cryptography. In the algorithm of this encryption method, the length of the private key is 80 bits, and the block size, which is a unit of encryption processing, is any of 32 bits, 48 bits, and 64 bits. That is, a 32-bit, 48-bit, or 64-bit plaintext is used as an input, and a ciphertext having the same length as the plaintext is generated by using the input 80-bit private key.

Symmetric-key cryptographic processing generally includes round processing and key expansion processing. In the round process, the predetermined stirring process is regarded as one round, and the process of the one round is executed a plurality of times. The total number of rounds to be executed is called the number of rounds, and the number of rounds of KATAN & KTANTAN is 254. In each round, two 1-bit secret keys, which are different values for each round, are used. The 1-bit key used in each round is generated by a predetermined procedure based on the input 80-bit key. This process is the key expansion process. The only difference between KATAN and KTANTAN is that the key expansion processing configuration is different, and the round processing has the same configuration.

FIG. 1 is a diagram showing a configuration of a round processing unit when the block size, which is a unit of encryption processing, is 32 bits. KATAN and KTANTAN when the block size is 32 bits are called KATAN32 and KTANTAN32, respectively.

The round processing unit shown in FIG. 1 is implemented as a feedback shift register. The feedback shift register includes a shift register 10, a shift register 11, a combination logic circuit 12, and a combination logic circuit 13. The combinational logic circuits 12 and 13 receive the register outputs of the plurality of bit positions of the shift registers 10 and 11 in the first state as inputs, respectively. As shown by the numbers in the rectangular frame indicating each register of the shift register in FIG. 1, the shift register 10 has a length of 13 bits from bit "0" to bit "12", and the shift register 11 starts from bit "0". It is 19 bits long with bit "18".

The combined logic circuits 12 and 13 have feedback values that should be register values at predetermined bit positions (positions of bits "0" in FIG. 1) of shift registers 11 and 10, respectively, in the second state following the first state. Implement a feedback function that produces. This feedback function is a non-linear function, and in the combined logic circuit 12, two AND operation (logical product operation) logic gates 12-1 and 12-2 and four XOR operation (exclusive OR operation) logic gate 12 It is realized by -3 to 12-6. Further, in the combination logic circuit 13, it is realized by two AND operation logic gates 13-1 and 13-2 and four XOR operation logic gates 13-3 to 13-6. Although the inputs of the combination logic circuit 12 and the combination logic circuit 13 are different, the same operation is executed as a logical operation.

In addition to the input from the shift register 10, a 1-bit key Ka and a 1-bit irregular update value IR are input to the feedback function calculated by the combination logic circuit 12. Further, in the feedback function calculated by the combination logic circuit 13, a 1-bit key Kb is input in addition to the input from the shift register 10. The keys Ka and Kb are generated and supplied for each round by the above-mentioned key expansion process. The irregular update value IR is a 1-bit value that is different for each round generated by a predetermined rule.

The 32-bit plaintext is divided and stored in shift registers 10 and 11. The least significant bit of the plaintext is stored in the bit "0" of the shift register 11, and the most significant bit of the plaintext is stored in the bit "12" of the shift register 10. The shift registers 10 and 11 shift one bit per round in the direction of the arrow shown at the top or bottom of the figure. After executing 254 rounds, that is, after shifting 254 times, the 32-bit data held in 32 registers becomes a ciphertext (32 bits).

In order to normally execute the feedback operation in the feedback shift register shown in FIG. 1, the clock period of the shift operation of the shift registers 10 and 11 needs to be longer than the time required for the logical operation in the combined logic circuits 12 and 13. .. That is, the operating clock period needs to be longer than the delay time from the input to the output of the combination logic circuits 12 and 13, and high-speed encryption processing cannot be executed.

FIG. 2 is a diagram showing an example of a configuration of a generalized feedback shift register. The feedback shift register shown in FIG. 2 includes a shift register 20 and a combination logic circuit 21. The shift register 20 includes a plurality of registers connected in cascade. Each register reads the data of the register in the previous stage in response to the clock pulse, so that the data propagates in the register along with the state transition synchronized with the clock.

The combinational logic circuit 21 receives the register outputs 22 at the plurality of bit positions of the shift register 20 in the first state as inputs. The combinational logic circuit 21 realizes a feedback function that generates a feedback value that should be a register value at a predetermined bit position of the shift register 20 in the second state following the first state. The combinational logic circuit 21 supplies the generated feedback value to the shift register 20 as the feedback input 24 to the register at a predetermined bit position. The shift register 20 may be divided as in the example of KATAN 32 in FIG. 1, and there may be a plurality of feedback inputs 24 to the shift register 20.

As in the case of the above-mentioned example of FIG. 1, in order to normally execute the feedback operation in the feedback shift register shown in FIG. 1, the clock cycle of the shift operation of the shift register 20 is a logical operation in the combined logic circuit 21. It needs to be longer than the time it takes. That is, the operating clock period needs to be longer than the delay time from the input to the output of the combinational logic circuit 21, and high-speed encryption processing cannot be executed.

FIG. 3 is a diagram showing an example of a general configuration of a feedback shift register capable of increasing the operating speed. In addition, in FIG. 3 and other similar figures, the boundary between each circuit block shown in each box and the other circuit block basically indicates a functional boundary, and the separation of physical positions, It does not always correspond to the separation of electrical signals and the separation of control logic. Each circuit block may be one hardware module that is physically separated from the other blocks to some extent, or represents one function in the hardware module that is physically integrated with the other blocks. It may be a module.

The feedback shift register of FIG. 3 includes a shift register 30, a first combination logic circuit 31-1, a second combination logic circuit 31-2, and an additional register 32. The shift register 30 includes a register sequence 30-1 which is a first shift register portion and a second shift register portion 30-2.

The shift register 30 includes a plurality of registers connected in cascade. The second shift register portion 30-2 is a normal shift register. Each register of the second shift register portion 30-2 reads the data of the register in the previous stage in response to the clock pulse, so that the data propagates in the register with the state transition synchronized with the clock. The register sequence 30-1 also includes a plurality of registers connected in cascade, but the logic gate of the second combinational logic circuit 31-2 is interposed between the registers. Each register in the register row 30-1 reads the calculation result of the logic gate for the data of the register in the previous stage in response to the clock pulse, so that the data is calculated along with the state transition synchronized with the clock and propagates through the register row. To go.

The first combination logic circuit 31-1 and the second combination logic circuit 31-2 show the logic operation circuit corresponding to the combination logic circuit 21 of FIG. 2 divided into two for convenience of explanation. .. When a logic operation with two or more stages is realized by a plurality of logic gates in a certain combination logic circuit, this combination logic circuit is used as a logic gate of a logic circuit part on the front stage side and a logic gate of a logic circuit part on the rear stage side. It can be divided arbitrarily. In this case, the first combination logic circuit 31-1 corresponds to the logic circuit portion on the front stage side, and the second combination logic circuit 31-2 corresponds to the logic circuit portion on the rear stage side.

The first combinational logic circuit 31-1 receives the register output 33 at the plurality of bit positions of the shift register 30 in the first state as an input. The first combination logic circuit 31-1 and the second combination logic circuit 31-2 set a feedback value that should be a register value at a predetermined bit position of the shift register 30 in the second state following the first state. Realize the feedback function to be generated. The shift register 30 may be divided as in the example of KATAN 32 in FIG. 1, and there may be a plurality of feedback inputs 36 to the shift register 30.

The feedback shift register included in FIG. 3 is provided with a register group including a register sequence 30-1 and an additional register 32 that function as a part of the shift register 30. The operation value input 35 to the additional register 32 is one or more operation values (intermediate result of the operation of the feedback function) generated by the first combination logic circuit 31-1. The calculated value supplied by the calculated value input 35 is stored in at least one register of the additional register 32. One calculated value (intermediate result of the operation of the feedback function) generated by the first combination logic circuit 31-1 may be supplied to the register sequence 30-1 as the calculated value input 36. The calculated value input 36 may be supplied from the second combinational logic circuit 31-2 instead of being supplied from the first combinational logic circuit 31-1.

The operation intermediate result supplied as the operation value input 36 is stored in one register of the register column 30-1. The bit position of this register may be a predetermined bit position in which the feedback value for the second state described above is stored, or may be another bit position.

The second combination logic circuit 31-2 performs a logical operation between the register storage value of the additional register 32 and the register storage value of the register column 30-1, and if necessary, the additional register 32 register storage values are used with each other. Perform logical operations. The second combinational logic circuit 31-2 may store the operation result in the additional register 32 or the register column 30-1. The operation result storage process is executed along with the state transition synchronized with the clock. The exchange of register values and calculation results between the second combination logic circuit 31-2 and the additional register 32 is shown as input / output 37 in FIG.

Focusing on register column 30-1, the register value stored in a certain register of register column 30-1 is logically operated with one or more register values stored in one or more registers of the additional register 32. , The result of the logical operation is stored in the register at the next stage. In FIG. 3, the operation of transferring the data of the register of the register column 30-1 to the adjacent register while performing a logical operation with the state transition is shown as a data transition and shifts 38-1 to 38-N. For example, the data stored in the register at the position of the bit "0" (least significant bit) of the register string 30-1 undergoes N data transitions and shifts by N state transitions, and the bit "N" (the first). It is stored in the register at the position (N bit). At this time, one logical operation in each state transition may be an operation by one logic gate, an operation by a plurality of logic gates, a one-stage logic operation, or a multi-stage logic. It may be an operation. By configuring the circuit configuration in which the data transition and shift operations are performed in the register sequence 30-1, the register sequence 30-1 can function as a part of the shift register 30.

In this way, the second combination logic circuit 31-2 logically operates the data stored in the additional register 32 with respect to the data stored in the register column 30-1 for each state transition. As a result, the second combination logic circuit 31-2 sequentially executes a part of the logical operation (operation of the feedback function) of the combination logic circuit while propagating data to the register sequence 30-1 with the state transition. As a result, the feedback value is generated in the state immediately before the state after the transition from the second state to the N state (N: natural number), and N times after (N steps) from the predetermined bit position described above. This generated feedback value is input to the register at the bit position.

In the above operation, the logical operation of the feedback function by the combined logic circuit is divided into a plurality of logical operation parts, and the logical operation part is executed while propagating the data to the register sequence 30-1 in synchronization with the clock. That is, instead of executing all the logical operations of the feedback function in one clock cycle as shown in FIG. 2, the data is propagated to the register sequence 30-1 over one or more clock cycles. Execute one or more divided logical operation parts. With this configuration, one operation of the part of the first combination logic circuit 31-1 and one or more operations of the part of the second combination logic circuit 31-2 are executed over a plurality of clock periods. However, the amount of calculation in one clock cycle, that is, the delay time can be reduced. Therefore, in the configuration of FIG. 3, the clock period can be shortened as compared with the configuration of FIG. 2, and the operating speed of the feedback shift register can be improved.

For example, in cryptographic processing such as KATAN and KTANTAN, the plaintext stored in the shift register shifts in the shift register as it is in the initial round. When this is applied to the configuration of FIG. 3, the plaintext stored in the shift register 30 including the part stored in the register column 30-1 is sequentially the value as it is without being changed by the logical operation. It is required to shift. For example, the least significant bit of plaintext stored in the position of the rightmost bit "0" of the shift register 30 is required to be shifted to the leftmost bit position of the shift register 30 with the same value.

In the configuration of FIG. 3, by setting an appropriate value as an initial value in the additional register 32, the register sequence 30-1 can function as a normal shift register. That is, for example, when the operation executed at the time of data transition and shift is XOR, the data shift operation is realized by setting the corresponding register value of the additional register 32 to 0. Further, for example, when the operation executed at the time of data transition and shift is AND, the data shift operation is realized by setting the corresponding register value of the additional register 32 to 1.

Alternatively, in the input portion of each register in the register sequence 30-1, a selector may be provided in which either the output from the register in the previous stage or the output of the logic gate of the second combination logic circuit 31-2 can be selected. .. By controlling the selection of each selector according to the number of state transitions from the initial state, when a data shift is required, the register output of the previous stage is selected, and the data transition and subsequent logical operations are accompanied. If a shift is required, select the output of the logic gate.

An example in which the configuration of FIG. 3 is applied to the feedback shift registers of KATAN 32 and KTANTAN 32 of FIG. 1 will be described below.

FIG. 4 is a diagram showing an example of a configuration of a combinational logic circuit that realizes a nonlinear function used in KATAN 32 and KTANTAN 32. As described above, for example, the combined logic circuit 12 includes two AND logic gates 12-1 and 12-2 and four XOR logic gates 12-3 to 12-6.

FIG. 5 is a diagram showing an equivalent logic circuit of the combination logic circuit shown in FIG. Since the XOR operation satisfies the coupling law, the combination logic circuit shown in FIG. 5 can be obtained as a circuit equivalent to the combination logic circuit shown in FIG. 4 by appropriately changing the order of the XOR operations.

The combined logic circuit that realizes the nonlinear feedback function shown in FIG. 5 includes two AND logic gates 40-1 and 40-2 and four XOR logic gates 40-3 to 40-6. For convenience of the following description, this combinational logic circuit is divided into three. The logic circuit part of the XOR logic gates 40-4 and 40-5 obtained by the three divisions is the logic circuit 41, and the logic circuit part of the AND logic gates 40-1 and 40-2 and the XOR logic gate 40-3 is the logic circuit 42. , The logic circuit portion of the XOR logic gate 40-6 is referred to as a logic circuit 43.

By dividing the feedback function in this way, the logic circuits 41 and 42 in the previous stage are assigned to the first combination logic circuit 31-1 in FIG. 3, and the logic circuit 43 in the second stage is assigned to the second combination logic circuit 31-2. Can be assigned. This makes it possible to implement KATAN 32 and KTANTAN 32 using the configuration shown in FIG.

In addition, in order to apply the configuration shown in FIG. 3 to the feedback shift registers of KATAN 32 and KTANTAN 32 shown in FIG. 1, it is not necessary to convert the combination logic circuit shown in FIG. 4 to the equivalent circuit shown in FIG. The combinational logic circuit shown in FIG. 4 may be divided into a front stage and a rear stage as they are, and each may be assigned to the first and second combinational logic circuits 31-1 and 31-2.

FIG. 6 is a diagram schematically showing an operation of shifting while performing a logical operation on the data stored in the register sequence. In FIG. 6, the register at the position of the least significant bit "0" of the shift register 11 and the two registers at the position of the next bit "1" function as the register sequence 51 that executes the data transition and shift operations. Synchronized with the first pulse of the clock signal, the operation result of 1 bit output by the logic circuit 42 shown in FIG. 5 is stored in the register at the position of bit "0", and 1 bit output by the logic circuit 41. The calculation result of is stored in the additional register 52. Only the operations of these logic circuits 41 and 42 are executed in parallel in the original clock period (that is, the first period immediately before the first pulse).

The operation result stored in the register of bit "0" is an intermediate result, not the original final feedback value. Therefore, in the second cycle immediately after the first pulse, the logic circuit 43 executes an XOR operation on the intermediate result and the intermediate result stored in the additional register 52, so that the feedback value which is the final calculation result is obtained. calculate. The calculated feedback value is stored in the register of bit "1" in synchronization with the second pulse following the first pulse. By performing data transition and shift between the two registers of the register column 51 in this way, the final feedback value is calculated from the intermediate result, and the feedback value is stored in the register at the final stage of the register column 51. Will be done.

Combination of feedback functions In the conventional configuration that does not divide the logic circuit, the original feedback value is stored in the register of bit "0" in the first pulse. This feedback value is stored in the register of bit "1" in synchronization with the second pulse following the first pulse. Therefore, the positions where the feedback values of interest are stored are the same in the same clock period between the conventional configuration without logical division and the logical division configuration shown in FIG. In this way, it is possible to ensure the equivalence of logic between the case of logical division and the case of no logical division.

FIG. 7 is a diagram showing an example of a configuration in which the feedback shift register of FIG. 3 is applied to KATAN 32 and KTANTAN 32. The feedback shift registers shown in FIG. 7 include a shift register 10, a shift register 11, a plurality of logic gates 40-1 to 40-6 that realize a non-linear feedback function, and a plurality of logic gates 50-1 to that realize a non-linear feedback function. Includes 50-6. The plurality of logic gates 40-1 to 40-6 correspond to the combination logic circuit 12 of FIG. 1, and the plurality of logic gates 50-1 to 50-6 correspond to the combination logic circuit 13 of FIG. Each of the combinational logic circuits that realizes the nonlinear feedback function in FIG. 7 has the configuration of the equivalent circuit shown in FIG.

The configuration and operation of the round processing unit of KATAN 32 and KTANTAN 32 shown in FIG. 7 are the same as the configuration and operation of the round processing unit shown in FIG. 1 except for the portion in which the combinational logic circuit is divided. In the following, the configuration and operation that will be different from FIG. 1 by dividing the combinational logic circuit will be described.

The combinatorial logic circuit, which is a collection of the plurality of logic gates 40-1 to 40-6, receives the register outputs of the plurality of bit positions of the shift register 10 in the first state as inputs. This combinational logic circuit further sets a feedback value that should be a register value at a predetermined bit position (bit "0" position) of the shift register 11 in the second state following the first state. Realize the feedback function generated in the state. However, since the combinational circuit is divided in the configuration of FIG. 7, the feedback value is generated for the first time in the second state following the first state, as described below.

The round processing unit shown in FIG. 7 is provided with a register group including a register sequence 51 and an additional register 52 that function as a part of the shift register 11. The data stored at the bit "0" position of the register sequence 51 is an intermediate result generated by the logic circuit 42 shown in FIG. The data stored in the additional register 52 is an intermediate result generated by the logic circuit 41 shown in FIG. The logic gate 40-6 that executes the XOR operation performs a logical operation (XOR operation) on the data stored in the additional register 52 with respect to the data stored at the position of the bit "0" in the register column 51 for each state transition. .. As a result, a part of the logical operation of the combined logic circuit (XOR operation by the logic gate 40-6) is executed while propagating the data to the register sequence 51 along with the state transition, and the state after the transition from the second state to the first state. The feedback value is generated in the state immediately before (that is, the second state). This generated feedback value is the bit position (bit "1" position) one bit after the predetermined bit position (bit "0" position) at the timing of transition from the second state to the third state. Is input to the register of.

The data transition and shift operations in the register sequence 51 described above are the same as the operations described in detail with reference to FIG. By performing data transition and shift between the two registers of the register column 51 in this way, the final feedback value is calculated from the intermediate result, and the feedback value is stored in the register at the final stage of the register column 51. Will be done. On the shift register 10 side, a register group including a register sequence 53 that functions as a part of the shift register 10 and an additional register 54 is provided. As a result, the same operation as that on the shift register 11 side is executed on the shift register 10 side. In the configuration shown in FIG. 7 for executing such an operation, the calculation amount of the feedback function in one clock cycle, that is, the delay time can be reduced, so that the clock cycle is shortened as compared with the configuration of FIG. Therefore, the operating speed of the feedback shift register can be improved.

FIG. 8 is a diagram showing another example of the configuration in which the feedback shift register of FIG. 3 is applied to KATAN 32 and KTANTAN 32. The feedback shift registers shown in FIG. 8 include a shift register 10, a shift register 11, a plurality of logic gates 40-1 to 40-4, 40-5A, and 40-6A, and a plurality of logic gates 50-1 to 50-4. , 50-5A, and 50-6A. The plurality of logic gates 40-1 to 40-4, 40-5A, and 40-6A correspond to the combination logic circuit 12 of FIG. 1, and the plurality of logic gates 50-1 to 50-4, 50-5A, and 50. -6A corresponds to the combination logic circuit 13 of FIG.

For example, among the plurality of logic gates 40-1 to 40-4, 40-5A, and 40-6A, the logic gates 40-1 to 40-4 correspond to the logic gates having the same reference number in FIG. 7, respectively. For the logic gates 40-5A and 40-6A that perform the XOR operation, the calculation target (calculation input) is different from the XOR logic gates 40-5 and 40-6 in FIG. 7 by using the associative law of the XOR operation. ing. However, the plurality of logic gates 40-1 to 40-4, 40-5A, and 40-6A as a whole have a logic circuit configuration for calculating the feedback function of the combination logic circuit 12 of FIG. This also applies to the plurality of logic gates 50-1 to 50-4, 50-5A, and 50-6A.

The configuration and operation of the round processing unit of KATAN 32 and KTANTAN 32 shown in FIG. 8 are the same as the configuration and operation of the round processing unit shown in FIG. 7, except for the method of dividing the combinational logic circuit. In the following, a configuration and an operation different from those in FIG. 7 due to the difference in the method of dividing the combinational logic circuit will be described.

The round processing unit shown in FIG. 8 is provided with a register group including a register sequence 61 that functions as a part of the shift register 11 and additional registers 62-1 to 62-6. The data stored at the bit "0" position of the register column 61 is an intermediate result generated by the logic gate 40-2. The data stored in the additional registers 62-1 to 62-3 are the intermediate result generated by the logic gate 40-1, the intermediate result generated by the logic gate 40-4, and the 1-bit key Ka, respectively.

The XOR operation for the four bit values stored in the register of bit "0" of the register column 61 and the additional registers 62-1 to 62-3 is performed on the three two-input XOR logic gates 40-3, 40-5A, and 40-5A. It is executed sequentially by 40-6A. In this sequentially executed operation, the register at the position of bit "1" and the register at the position of bit "2" of the register column 61, and the registers of the additional registers 62-4 to 62-6 are the above-mentioned four bit values. It is used as a plurality of buffer registers for the operation to obtain the XOR of. The output of the XOR logic gate 40-6A in the final stage of the three 2-input XOR logic gates 40-3, 40-5A, and 40-6A is the predetermined bit position (bit "0") as the final feedback value. It is input to the register at the bit position (position of bit "3") three after "position".

On the shift register 10 side, a register group including a register sequence 63 that functions as a part of the shift register 10 and additional registers 64-1 to 64-6 is provided. As a result, the same operation as that on the shift register 11 side is executed on the shift register 10 side. In the configuration shown in FIG. 8 for executing such an operation, the calculation amount of the feedback function in one clock cycle, that is, the delay time can be reduced, so that the clock cycle is shortened as compared with the configuration of FIG. Therefore, the operating speed of the feedback shift register can be improved. Further, since the logical operation of the feedback function is divided into smaller parts as compared with the configuration of FIG. 7, the clock period is shortened and the operation speed of the feedback shift register is improved as compared with the configuration of FIG. Can be done.

FIG. 9 is a diagram showing still another example of the configuration in which the feedback shift register of FIG. 3 is applied to KATAN 32 and KTANTAN 32. The feedback shift registers shown in FIG. 9 include a shift register 10, a shift register 11, a plurality of logic gates 40-1, 40-2, 40-8, and 40-9, and a plurality of logic gates 50-1, 50-2. , 50-8, and 50-9. Multiple Logics A plurality of logic gates 40-1, 40-2, 40-8, and 40-9 correspond to the combination logic circuit 12 of FIG. 1, and a plurality of logic gates 50-1, 50-2, 50-8. , And 50-9 correspond to the combination logic circuit 13 of FIG.

For example, of the plurality of logic gates 40-1, 40-2, 40-8, and 40-9, the logic gates 40-1 and 40-2 correspond to the logic gates having the same reference number in FIG. 7, respectively. In the configuration of FIG. 9, in addition to the logic gates 40-1 and 40-2, the three-input XOR logic gates 40-8 and 40-9 are used to realize the logical operation of the feedback function. The plurality of logic gates 40-1, 40-2, 40-8, and 40-9 as a whole have a logic circuit configuration for calculating the feedback function of the combination logic circuit 12 of FIG. This also applies to the plurality of logic gates 50-1, 50-2, 50-8, and 50-9.

The configuration and operation of the round processing unit of KATAN 32 and KTANTAN 32 shown in FIG. 9 are the same as the configuration and operation of the round processing unit shown in FIG. 7, except for the method of dividing the combinational logic circuit. In the following, a configuration and an operation different from those in FIG. 7 due to the difference in the method of dividing the combinational logic circuit will be described.

The round processing unit shown in FIG. 9 is provided with a register group including a register sequence 71 that functions as a part of the shift register 11 and additional registers 72-1 and 72-2. The data stored at the bit "0" position of the register column 71 is an intermediate result generated by the logic gate 40-2. The data stored in the additional registers 72-1 and 72-2 are the intermediate result generated by the logic gate 40-1 and the intermediate result generated by the logic gate 40-8, respectively. In the configuration shown in FIG. 9, the delay time of the 3-input XOR logic gate is the same as that of other logic gates (2-input AND logic gate), or at least 2 input XOR logic gates are used. It is assumed that the delay time is shorter than the delay time of the configuration connected in tandem.

The three-input XOR logic gate 40-9 has the output of the register at a predetermined bit position (bit "0" position) of the shift register 11, the output of the additional register 72-1, and the output of the additional register 72-2. Find the XOR of the three outputs of. The output of the 3-input XOR logic gate 40-9 is input as a feedback value to the register at the bit position (bit "1" position) next to the predetermined bit position (bit "0" position).

On the shift register 10 side, a register group including a register sequence 73 that functions as a part of the shift register 10 and additional registers 74-1 and 74-2 is provided. As a result, the same operation as that on the shift register 11 side is executed on the shift register 10 side. In the configuration shown in FIG. 9 for executing such an operation, the calculation amount of the feedback function in one clock cycle, that is, the delay time can be reduced, so that the clock cycle is shortened as compared with the configuration of FIG. Therefore, the operating speed of the feedback shift register can be improved. Further, since the logical operation of the feedback function is divided into smaller parts as compared with the configuration of FIG. 7, the clock period is shortened and the operation speed of the feedback shift register is improved as compared with the configuration of FIG. Can be done.

The example of applying the configuration of the feedback shift register of FIG. 3, that is, the configuration of dividing the combinational logic circuit for calculating the feedback function to improve the operating speed, to the KATAN 32 and the KTANTAN 32 has been described above. The configuration of the feedback shift register of FIG. 3 can be applied to the configuration of any feedback shift register as long as the register for inputting the original feedback value in the shift register is not used as the input of the combination logic circuit. When the register that inputs the original feedback value in the shift register is used as the input of the combination logic circuit, it is necessary to complete the operation of all the feedback functions within one clock cycle, so the configuration of FIG. 3 is used. That is difficult.

The configuration of FIG. 3 is also applicable to KATAN48 and KTANTAN48 and KATAN64 and KTANTAN64. The configuration of the feedback registers of KATAN48 and KTANTAN48 and KATAN64 and KTANTAN64 is different only in the length of the shift register and the position of the input bit to the combination logic circuit from those of KATAN32 and KTANTAN32. The configuration of the combinational logic circuit is the same for KATAN48 and KTANTAN48, KATAN64 and KTANTAN64, and KATAN32 and KTANTAN32. The first bit (lowest bit) used as an input to the combinatorial logic circuit is the sixth in KATAN48 and KTANTAN48 and the ninth in KATAN64 and KTANTAN64. Therefore, any of the divisional forms of the combinational logic circuits shown in FIGS. 7 to 9 can be applied to KATAN48 and KTANTAN48 and KATAN64 and KTANTAN64.

FIG. 10 is a diagram showing an example of the configuration of another cryptographic processing hardware. The cryptographic processing hardware shown in FIG. 10 implements the stream cipher method Grain. Grain's hardware includes a non-linear feedback shift register 81 and a linear feedback shift register 82.

In FIG. 10, g (x) is the non-linear feedback function of the non-linear feedback shift register 81, and f (x) is the linear feedback function of the linear feedback shift register 82. In the configuration of this cryptographic processing hardware, the least significant bit of the input to the non-linear feedback function g (x) of the non-linear feedback shift register 81 is the 17th bit. The least significant bit of the input to the linear feedback function f (x) of the linear feedback shift register 82 is the 18th bit. Therefore, by dividing the nonlinear feedback function g (x) and the XOR gate 83 as division targets and dividing the linear feedback function f (x) as division targets, the configuration of the feedback shift register in FIG. 3 is shown in FIG. It can be applied to the indicated Grain cryptographic hardware. More specifically, an additional register may be provided, and the data transition and shift operations may be executed in the register strings at the heads of the non-linear feedback shift register 81 and the linear feedback shift register 82 while using the additional register.

FIG. 11 is a diagram showing an example of the configuration of still another cryptographic processing hardware. The cryptographic processing hardware shown in FIG. 10 implements the stream cipher Trivium. Trivium hardware includes shift registers 91-93, logic gates 101-104, logic gates 111-114, and logic gates 121-124.

The logic gates 101 to 104, the logic gates 111 to 114, and the logic gates 121 to 124 are configured to perform logically the same operation although the inputs are different. Taking the logic gates 101 to 104 as an example, the logic gate 101 calculates the AND of _{s 286} and s _287. The logic gate 102 calculates the XOR of _{s 243} and s _288. The logic gate 103 calculates the XOR between the output of the logic gate 101 and s _69. The logic gate 104 calculates the XOR between the output of the logic gate 102 and the output of the logic gate 103. The output of the logic gate 104 is input to the _{s 1.} In order to apply the configuration of FIG. 3 to the configuration of FIG. 11, the logical operation by the logical gates 101 to 104 is divided and an additional register is provided, and the register sequence of the head portion of the shift register 91 is used while using the additional register. The data transition and shift operations may be executed in. The same applies to the logical operations by the logical gates 111 to 114 and the logical operations by the logical gates 121 to 124.

FIG. 12 is a diagram showing an example of a hardware configuration of a system incorporating the feedback shift register of FIG. The system shown in FIG. 12 includes CPU 201, ROM 202, RAM 203, cryptographic processing hardware 204, and random number generation hardware 205.

The ROM 202 stores data and programs used for the basic operation of the CPU 201. The CPU 201 executes a desired process by executing a program stored in the RAM 203. The RAM 203 functions as a workspace when the processing of the CPU 201 is executed, and also functions as a storage area for storing data used for the processing executed by the CPU 201 and data generated by the processing. The cryptographic processing hardware 204 and the random number generation hardware 205 have a built-in feedback shift register used for the cryptographic processing and the random number generation processing, and the configuration shown in FIG. 3 is adopted in the feedback shift register.

The encryption processing hardware 204 operates under the control of the CPU 201, and may execute encryption processing, decryption processing, and the like. The cryptographic processing hardware 204 may be used, for example, in a challenge-response authentication system using common key cryptography. In this case, the system of FIG. 12, which functions as an certifier, sends a random value called a challenge to the authenticated person. The system also uses cryptographic hardware 204 to encrypt the challenge with a common private key. The authenticated person encrypts the received challenge with a common private key, and sends the obtained ciphertext as a response to the system. On the system side, it is confirmed whether or not the ciphertext generated by itself and the ciphertext of the response received from the authenticated person match. Based on the ciphertext match or mismatch, the system can authenticate the subject.

The random number generation hardware 205 may operate under the control of the CPU 201 to generate a pseudo-random number sequence. The feedback shift register used for pseudo-random number generation in the random number generation hardware 205 may be, for example, a linear feedback shift register. For example, in the above-mentioned challenge-response authentication system, it is necessary for the system side, which is the certifier, to generate a challenge having a random value. The system of FIG. 12 may use random number generation hardware 205 to generate random values to be used as challenges.

Although the present invention has been described above based on the examples, the present invention is not limited to the above examples, and various modifications can be made within the scope of the claims.

For example, in the example of the feedback shift register shown in FIG. 3, the register sequence 30-1 shows a configuration that is a part of the shift register 30, but the present invention is not limited to this configuration. For example, a register array may be provided separately from the shift register 30, and data transitions and shifts may be performed in this register array while performing a partial logical operation of the feedback function together with a state transition synchronized with the clock. The circuit may be configured such that the feedback value generated in this way is input to the register at the bit position N after the predetermined bit position (the bit position where the feedback value is input in the configuration of FIG. 2). At this time, a selector may be provided in the input portion of the register so that the register output in the previous stage of the shift register and the output of the above register sequence can be selected.

Even with such a configuration, the register sequence can function as a part of the shift register 30 in the sense that it can function as a shift register depending on the corresponding register value of the additional register 32. Register sequence. That is, even such a configuration is included in the range intended by the present invention.

10 Shift register 11 Shift register 12 Combination logic circuit 13 Combination logic circuit 20 Shift register 21 Combination logic circuit 30 Shift register 31-1 First combination logic circuit 31-2 Second combination logic circuit 31-2
32 additional registers

Claims (11)

Shift register and
Receive register output of a plurality of bit positions of the previous SL shift register as an input, a combinational logic circuit for implementing a feedback function that generates a feedback value stored in the shift register,
The 1-bit operation value, which functions as a part of the shift register at a bit position lower than the plurality of bit positions of the shift register and is the first intermediate result of the operation of the feedback function, is obtained from the combination logic circuit. A register group including a register sequence stored at the lowest receiving bit position and an additional register for receiving and storing the second intermediate result of the operation of the feedback function from the combination logic circuit is stored in the register sequence. By logically performing a logical operation on the data stored in the additional register for each state transition, a part of the logical operation of the combined logic circuit is executed while propagating the data to the register sequence along with the state transition. A feedback shift register circuit that inputs the feedback value to the most significant bit position of the register sequence. The feedback shift register circuit according to claim 1, wherein the register in the register sequence is a part of the shift register. The feedback shift register circuit according to claim 1 or 2, wherein the feedback function is a feedback function of the KATAN cipher. The combination logic circuit includes a logic gate for obtaining an exclusive logical sum of the output of the register at the lowest bit position of the register sequence and the output of the additional register, and the output of the logic gate is the feedback value of the register sequence. The feedback shift register circuit according to claim 3, which is input to the register at the bit position next to the lowest bit position of. The combination logic circuit has an output of a register at the lowest bit position of the register sequence, an output of a first register which is one of the additional registers, and a second register which is the other of the additional registers. The output of the three-input logic gate includes a three-input logic gate for obtaining an exclusive logic sum of the three outputs with the output of the above, and the output of the three-input logic gate is input to the register at the bit position next to the lowest bit position of the register string as the feedback value. The feedback shift register circuit according to claim 3. The combination logic circuit has an output of a register at the lowest bit position of the register sequence, an output of a first register which is one of the additional registers, and an output of a second register which is one of the additional registers. And three 2-input exclusive logic sum gates for finding the exclusive logic sum of the four outputs with the output of the third register, which is one of the additional registers, and the register at the lowest bit position of the register sequence. The register at the bit position after one and the register at the bit position after two, and the fourth to sixth registers which are the additional registers are for the operation of obtaining the exclusive logic sum of the four outputs. It is used as a plurality of buffer registers, and the output of the exclusive logic sum gate at the final stage of the three two-input exclusive logic sum gates is the bit position three after the lowest bit position of the register sequence as the feedback value. The feedback shift register circuit according to claim 3, which is input to the register of. The feedback shift register circuit according to claim 3, wherein the shift register is a shift register used for cryptographic calculation of any one of KATAN32, KTANTAN32, KATAN48, KTANTAN48, KATAN64, and KTANTAN64. The feedback shift register circuit according to claim 1, wherein the feedback function is a linear feedback function, and the shift register is a shift register used for pseudo-random number generation. Receive register output of a plurality of bit positions of the shift register as input, the feedback shift register using a combination logic circuit for realizing the feedback function that generates a feedback value stored in the shift register,
A 1-bit operation value which functions as a part of the shift register at a bit position lower than the plurality of bit positions of the shift register and is the first intermediate result of the operation of the feedback function is obtained from the combination logic circuit. For the data stored in the register string stored in the lowest receiving bit position, the data stored in the additional register that receives and stores the second intermediate result of the operation of the feedback function from the combination logic circuit is stored for each state transition. By performing a logic operation on the above, a part of the logic operation of the combination logic circuit is executed while propagating data to the register sequence according to the state transition.
A method of operating a feedback shift register including each step of inputting the feedback value at the most significant bit position of the register sequence. The operation method of the feedback shift register according to claim 9, wherein the register in the register sequence is a part of the shift register. The operation method of the feedback shift register according to claim 9 or 10, wherein the feedback function is a feedback function of the KATAN cipher.

Images