WO2009142190A1

WO2009142190A1 - Coding or decoding circuit structure with error detecting capability

Info

Publication number: WO2009142190A1
Application number: PCT/JP2009/059167
Authority: WO
Inventors: 証佐藤; 健菅原; 尚文本間; 孝文青木
Original assignee: 独立行政法人産業技術総合研究所
Priority date: 2008-05-19
Filing date: 2009-05-19
Publication date: 2009-11-26
Also published as: JP2009278576A; JP5164154B2

Abstract

Provided are a coding circuit and a decoding circuit that reliably detect errors in operation mode, and reduce penalties to the circuit scale and operational speed. When a coding process is executed at one stage, the coding circuit and decoding circuit execute a decoding process, at a preceding stage, as verification of the coding process in a directly previous cycle in parallel. Decoded data is compared with data to be coded in the previous cycle to check if they match. In the next cycle, data coded earlier at the stage is decoded, and is checked against data before the coding to check if they match. A coding process is performed on the previously coded data at the next stage while new data is input to be subjected to a coding process at the preceding stage in parallel.

Description

Circuit configuration for encoding or decoding processing with error detection function

The present invention relates to a circuit configuration for encoding / decoding processing, and relates to a novel circuit configuration having error detection capability.

With the advancement of VLSI high-speed and high-integration technology, the performance of information equipment and the rapid spread of broadband networks have led to the exchange of large amounts of data not only in business but in every aspect of daily life. ing. Data compression techniques are used to expand the data bandwidth and reduce the storage device capacity, and the reliability of information and the safety of communications are ensured by error detection / correction codes and encryption techniques. Data compression technology is widely used for digital contents such as audio images, but such data often does not become a big problem even if some errors occur, and its confidentiality is low. On the other hand, programs that are downloaded from the server and used, monetary information, privacy information, etc. may cause serious damage if they cause errors or content leaks.

The error detection / correction code is mainly used for the purpose of detecting / correcting an error occurring on a communication channel or a recording medium, or requesting retransmission at a transmission destination. Therefore, when an error occurs in the encoding or decoding apparatus itself, data that cannot be corrected is generated, and the error cannot be detected. Although encryption technology can ensure the security of transmitted or recorded data, it cannot cope with data loss due to a failure of an encryption device or an attack using the data. Therefore, a technique for ensuring the reliability of the device itself for encoding / decoding data is required.

FIG. 1 is a diagram for explaining a conventional method for detecting an error generated in a circuit during an encoding process. As for error detection during the decoding process, the encoding and decoding processes in the figure may be replaced with each other. In the method described with reference to FIG. 1 (a), input data is encoded by the left-side pass, and then a parity equal to or smaller than the bit width of the output is generated. At the same time, the expected value circuit directly generates parity and detects the occurrence of an error depending on whether the two parities match. The expected value circuit is smaller than that for generating parity after encoding, but since it is a comparison based on parity, not all occurrences of errors can be detected.

The method described with reference to FIG. 1B is a method in which two same encoding circuits are prepared, the same operation is simultaneously performed in both, and the results are compared. Of course, the cost of the circuit is doubled. In the method described with reference to FIG. 1C, encoding and decoding processing are supported by separate circuit blocks. Simultaneously with storing the input data in the register 2, the encoded data is stored in the register 1. In the next cycle, new input data can be encoded. In parallel with this, the data in the register 1 is decoded and compared with the data stored in the register 2 to detect an error. However, the encoding and decoding processing circuits often share arithmetic components, and in this case, they cannot be applied. Even if they are independent, it is impossible to perform encoding and decoding on different data at the same time. For example, when performing bidirectional communication of data, since encoding and decoding processing cannot be performed simultaneously, the cost of the circuit is eventually doubled.

The method described with reference to FIG. 1D is a method in which the same processing is repeated twice in one encoding circuit and the results are compared. First, input data is encoded and the result is stored in the register 1. In the next cycle, the same data is encoded again, and it is detected whether the result matches the data stored in the register 1. Although this method can detect a temporary error due to power supply noise or the like, it has a drawback that it cannot be detected when the same error always occurs due to a defect in a transistor or wiring. In addition, since the same encoding process is repeated twice, the operation speed is reduced to ½.

The method described with reference to FIG. 1 (e) is a method in which encoding and decoding processing are performed by the same circuit block. Simultaneously with storing the input data in the register 2, first, the encoded data is held in the register 1. In the next cycle, the data in register 1 is decoded and compared with the data stored in register 2. Since only one data can be processed in two cycles, the throughput is halved as compared to the case of FIG. However, although the same calculation block is used, since different processes such as encoding and decoding processes are performed and it is confirmed that the original data can be restored, detection is not possible due to a circuit defect as shown in FIG. Possible errors are unlikely to occur.

The method described with reference to FIG. 1 (f) is an implementation in which the encoding circuit in the case of FIG. The result is compared twice before and after the two registers. Pipelining improves operating frequency and improves speed penalty due to error detection. However, as in the case of FIG. 1D, the problem that an error cannot be detected when there is a circuit defect has not been solved.

As described above, the conventional error detection method at the time of circuit operation has a defect that there is a problem in the error detection rate, the circuit scale is doubled, or the operation speed is halved. .

The encryption circuit conforming to the above error detection method is summarized in Non-Patent Document 1. Patent Documents 1 and 2 disclose a method of mounting an encryption circuit, but this is a circuit configuration in which an error error detection / correction circuit is added to a data register, not an arithmetic unit.

JP 2007-174024 A JP 2007-325219 A

In the background as described above, the present invention develops a new method for reliably detecting errors during the operation of the encoding / decoding processing circuit and minimizing the penalty for circuit scale and operation speed. It was made.

The present invention has a circuit configuration in which encoding and decoding processes are performed by pipeline processing, and each pipeline stage is not only a partial encoding process that is a part of the encoding process, but also a partial process thereof. The circuit configuration includes a partial encoding / decoding block for executing a partial decoding process which is an inverse process, and an encoding circuit and a decoding circuit are configured. Hereinafter, the partial encoding and partial decoding processes may be simply referred to as encoding and decoding, respectively, within a range that does not cause confusion.

In the embodiment of the encoding circuit of the present invention, when the encoding process is executed in a certain stage, the decoding process as the verification of the encoding process in the immediately preceding cycle is performed in parallel in the preceding stage. Executed. The decoded data is compared with the data to be encoded in the immediately preceding cycle to check whether they match. In the next cycle, in the same stage where the previous encoding process was performed, the previously encoded data is decoded and it is checked whether or not it matches the data before the encoding. In parallel, the encoding process proceeds on the previously encoded data at the next stage (output from the circuit if there is no next stage), and a new stage is added to the previous stage. Data is input and an encoding process is performed.

In the embodiment of the decoding circuit of the present invention, the order and roles of the encoding and decoding processes in the above encoding circuit are reversed.

That is, the encoding / decoding circuit according to the present invention is configured as a pipeline processing circuit including a plurality of encoding / decoding blocks, and each encoding / decoding block performs encoding processing and decoding processing for each cycle. Switch. Therefore, as a whole, not only data processing proceeds in each cycle, but also verification of processing in the previous cycle is performed at the same time. When operating as an encoding circuit, decoding processing is performed for verification, and when operating as a decoding circuit, encoding is performed for verification.

According to the present invention, the encoding and decoding processes are divided and pipeline processing is performed, and verification processing is also performed in parallel with the progress of processing, so that error detection can be performed during the processing. This ability is particularly effective in defending against attacks that intentionally generate errors and steal information, such as failure use analysis attacks on common key cryptography, and immediately stops processing when an error is detected. It can be used for such purposes.

In the present invention, although encoding and decoding processes are performed in the same circuit block, it is confirmed that the original data can be restored by performing different processes such as encoding and decoding processes. The possibility of undetectable errors is very low. From these facts, it can be said that the error detection function according to the present invention is very powerful and highly reliable.

On the other hand, in the circuit configuration according to the present invention, since the processing of each encoding / decoding block is switched between encoding and decoding every cycle, data can be input only once every two cycles. However, the operation frequency can be improved by dividing the operation block into a plurality of blocks and performing pipeline processing. For this reason, the decrease in processing performance is limited. In terms of the circuit scale, the circuit scale does not increase so much because the operation block that was originally one is only divided into a plurality of blocks. The additional circuit may also be a pipeline processing register and selector, and an error detection comparator.

For this reason, according to the present invention, it is possible to minimize adverse effects on the circuit scale and the operation speed while providing the circuit with a powerful and highly reliable error detection function.

Also, the circuit configuration disclosed here is not dependent on the encoding / decoding calculation method, and can be widely applied to various methods.

The embodiment of the present invention includes the following encoding circuit. This circuit is an encoding circuit that performs encoding processing by pipeline processing of a plurality of stages including at least stage X and stage Y that is the next stage of stage X,
Each of the plurality of stages includes a partial encoding / partial decoding block capable of executing a partial encoding process that is a part of the encoding process and a partial decoding process that is an inverse process of the partial process,
In a cycle
In the stage Y, the data partially encoded in the stage X in the cycle immediately before the certain cycle is partially encoded,
In the stage X, the data partially encoded in the stage X in the previous cycle is partially decoded,
The previously stored data before partial encoding at the stage X in the previous cycle is compared with the partially decoded data;
In the next cycle of the certain cycle,
In the stage Y, the data partially encoded in the stage Y in the certain cycle is partially decoded,
The pre-stored data before partial encoding at the stage Y in the certain cycle is compared with the data partially decoded at the stage Y,
In stage X, another data is partially encoded
An encoding circuit configured as a circuit.

The embodiment of the present invention includes the following decoding circuit. This circuit is a decoding circuit that performs decoding processing by pipeline processing of a plurality of stages including at least stage X and stage Y that is the next stage of stage X,
Each of the plurality of stages includes a partial encoding / partial decoding block capable of executing a partial decoding process that is a part of the decoding process and a partial encoding process that is a reverse process of the part,
In a cycle
In the stage Y, the data partially decoded in the stage X in the cycle immediately before the certain cycle is partially decoded,
In the stage X, the data partially decoded in the stage X in the previous cycle is partially encoded,
The previously stored data before partial decoding at the stage X in the previous cycle is compared with the partially encoded data;
In the next cycle of the certain cycle,
In the stage Y, the data partially decoded in the stage Y in the certain cycle is partially encoded,
The pre-stored data before partial decoding at the stage Y in the certain cycle is compared with the data partially encoded at the stage Y,
In stage X, another data is partially decoded
A decoding circuit configured as a circuit.

The present invention is useful for general and business electronic information devices that handle digital data, and is particularly useful for information devices related to digital contents, encryption technology, and information security. Therefore, the embodiment of the present invention not only includes an encoding circuit, a decoding circuit, and a semiconductor chip including these circuits, but also an electronic device including these circuits, for example, a personal computer, a communication device, a digital TV recorder. IC cards and network devices are also included. In addition, an encoding circuit and a decoding circuit that embody the technical idea disclosed in this specification can be implemented not only as non-reconfigurable hardware, but also as a reconfigurable programmable logic device such as an FPGA. The embodiment of the present invention can be implemented, and includes a program for expressing the technical idea disclosed in the present specification on a programmable logic device.

Some examples of preferred implementations of the invention are defined in the appended claims. Also, in the following description of the embodiments, examples of some preferred embodiments are described. However, the embodied form of the present invention is not limited to the form appearing in the claims and the description of the embodiments, and various variations can be made without departing from the scope of the present invention. Please note. In addition, it is stated that the technical scope of the present invention includes all new and useful features and combinations thereof that appear explicitly or implicitly in the claims, specification, and drawings.

It is a figure for demonstrating the system of the conventional error detection circuit. It is a figure for demonstrating the important part of the circuit structure of the encoding circuit 200 demonstrated as 1st Example. FIG. 6 is a diagram for explaining a processing flow of an encoding circuit 200. It is a figure for demonstrating the principal part of the circuit structure of the encoding / decoding circuit 400 demonstrated as 2nd Example. It is a figure for demonstrating a mode when the encoding / decoding circuit 400 operate | moves as a decoding circuit. FIG. 10 is a diagram for explaining a modification of the encoding / decoding circuit 400. It is a figure for demonstrating the example of the encryption / decryption circuit of AES which does not have an error detection function. It is a figure for demonstrating the encryption / decryption circuit of AES introduced as 3rd Example of this invention. It is a figure for demonstrating operation | movement of the AES circuit of FIG. It is a figure for comparing the performance of the AES circuit of FIG. 7 and FIG.

Hereinafter, in order to help understanding of the present invention, embodiments of the present invention will be described with reference to the accompanying drawings. As described above, the present invention relates to a circuit configuration having an error detection capability for encoding / decoding operations. In this circuit configuration, pipeline processing is used. Therefore, first, an example of the simplest embodiment in which pipeline processing consists of only two stages will be described.

FIG. 2 is a diagram for explaining an important part of the circuit configuration of the encoding circuit 200 according to the embodiment to be described. The encoding circuit 200 includes two partial encoding / partial decoding blocks 202 and 204, and performs encoding operation by pipeline processing using these two blocks. The first partial encoding / partial decoding block 202 is in charge of the calculation of the first half of the entire encoding process by the encoding circuit 200, and the second partial encoding / partial decoding block 204 is the entire encoding process. Responsible for the second half of the calculation. Also, the partial encoding / partial decoding blocks 202 and 204 are configured to be able to perform partial decoding operations that are inverse operations of the respective partial encoding operations. In this case, the first half of the entire decoding operation is the inverse operation of the latter half of the encoding operation, and the latter half of the entire decoding operation is the inverse operation of the first half of the encoding operation. Therefore, the first partial encoding / partial decoding block 202 processes the latter half of the decoding operation, and the second partial encoding / partial decoding block 204 processes the first half of the decoding operation. As described in the background art section, since the encoding circuit and the decoding circuit often share a calculation component and are combined into one processing circuit, the partial encoding / decoding blocks 202 and 204 As described above, it is possible for those skilled in the art to easily configure both processing of partial encoding and partial decoding with a single processing circuit.

The encoding circuit 200 stores a register 206 for the partial encoding / partial decoding blocks 202 and 204 to store the result of the arithmetic processing, and a copy of input data to the partial encoding / partial decoding blocks 202 and 204. A register 208 is provided. Therefore, the

registers

206 and 208 are shared by the partial encoding / partial decoding blocks 202 and 204. The encoding circuit 200 is provided with a comparator 210. The comparator 210 is also shared by the partial encoding / partial decoding blocks 202 and 204 and is used for comparing the result of the arithmetic processing with the data stored in the register 208. In order to share the

registers

206 and 208 and the comparator 210, three

selectors

212a, 212b, and 212c are provided.

Next, the processing flow of the encoding circuit 200 will be described in detail with reference to the calculation cycles (a) to (d) and the equations shown in FIG. In the following description, when encoding is performed in the partial encoding / partial decoding block 202, the function is expressed as ENC _pre (), and the function when decoding is performed as DEC _post (). Similarly, for the partial encoding / decoding block 204, a function when encoding is expressed as ENC _post () and a function when decoding is performed as DEC _pre ().

In the first calculation cycle (a), the first half of the encoding process is performed on the input data D0 by the partial encoding / decoding block 202, and an intermediate result E0 _pre is obtained as in the following equation.

E0 _pre = ENC _pre (D0)

The result of the operation is prepared to be stored in the register 206 in the next cycle (b). The input data D0 is also prepared to be stored in the register 208 in the next cycle (b).

In the next cycle (b), no new data is input, but the operation result E0 _pre in the previous cycle is stored in the register 206, and the input data D0 in the previous cycle is stored in the register 208. Then, the encoding / decoding block 204 performs the latter half of the encoding process E0 _pre stored in the register 206, and the encoding result E0 is obtained as follows.

E0 = ENC _post (E0 _pre )

Result E0 is prepared to be stored in register 206 in the next cycle. The input data E0 _pre to the partial encoding / decoding block 204 is also prepared to be stored in the register 208 in the next cycle.

At the same time as the processing by the partial encoding / partial decoding block 204, the partial encoding / partial decoding block 202 performs the latter half of the decoding on the E0 _pre stored in the register 206, and if the circuit is operating correctly, Obtain D0 as follows.

D0 = DEC _post (E0 _pre ) = DEC _post (ENC _pre (D0))

The comparator 210 compares the data D0 decoded by the partial encoding / partial decoding block 202 with D0 held in the register 208. If the comparison results match, no error exists, and if they do not match, an error exists and verification is possible.

To make sure, ENC _pre () → ENC _post () is the order of encoding functions executed in two cycles, and DEC _pre () → DEC _post () is used for decoding, so ENC _pre ( ) → ENC _post () → DEC _pre () → DEC _post () to return to the original data. Accordingly, the sets of ENC _pre () and DEC _post () and ENC _post () and DEC _pre () are respectively inverse functions.

In the next cycle (c), the result E0 is stored in the register 206, and the input data E0 _pre to the partial encoding / partial decoding block 204 in the previous cycle is stored in the register 208. Then, the encoding result E0 is output from the register 206. At the same time, the partial encoding / partial decoding block 204 performs the first half of the decoding on the value E0 held in the register 206 as follows, and the comparator 210 determines whether or not the value E0 matches the value E0 _pre held in the register 208. Checked.

E0 _pre = DEC _pre (E0) = DEC _pre (ENC _post (E0 _pre ))

Also, new data D1 is input simultaneously with these processes, and the intermediate result E0pre is calculated by the next encoding process by the partial encoding / partial decoding block 20.

E1 _pre = ENC _pre (D1)

E1 _pre and D1 are prepared to be stored in

registers

206 and 208, respectively, in the next cycle.

In the next cycle (d), as in the cycle (b) described above, the latter half of the encoding process and the decoding process as the verification process are performed on the intermediate result E1 _pre of the register 206 as follows. The same process is repeated each time there is a correct data input.

E1 = ENC _post (E1 _pre )

D1 = DEC _post (E1 _pre )

The encoding circuit 200 performs encoding and decoding in the same circuit block, but performs different processing such as encoding and decoding, and confirms that the original data can be restored, so it cannot be detected due to a circuit defect. The possibility of a serious error is very low. In addition, since it is confirmed that encoding and decoding are performed to return to the original data, it can be said that this is an error detection method with higher reliability than a parity check with an error that cannot be detected.

On the other hand, since the encoding circuit 200 can input data only once every two cycles, twice the number of cycles is required as compared with the case where error detection is not performed. However, since the operation frequency is approximately doubled by dividing the calculation block into two, the degradation of the processing performance is limited. The additional circuit may be only a pipeline processing register and selector and an error detection comparator. There are two operation blocks, but since only one was originally divided, there is no need to add a new operation unit as in the case of duplication in the method of FIG. The increase in scale is also very limited.

That is, the circuit configuration exemplified in the encoding circuit 200 makes it possible to reliably detect an error during the operation of the encoding / decoding circuit and to reduce the penalty for the circuit scale and the operation speed. Furthermore, since the circuit configuration described here is not a configuration depending on the encoding calculation method, it also has a feature that the application range is wide.

As understood from the above description, in the embodiment of the present invention related to the encoding process, the encoding process is divided into a plurality of stages, and in each cycle, the partial operation of the encoding and the cycle one cycle before A decoding operation as a verification process of the encoded partial operation is performed simultaneously. In the example using the encoding circuit 200, the operation processing is divided into two for simplicity, or when pipeline processing is possible, the number of divisions is increased to 3, 4, 5,. It is possible to improve further than in the case of division. As the number of divisions is increased, the delay time of the processing unit is shortened. However, since there is a fixed delay time in other parts, the operating frequency does not gradually improve. On the other hand, since additional circuits such as pipeline registers and comparators increase, it is necessary to select the number of divisions according to the characteristics of the encoding process while looking at the balance between processing capability and circuit scale.

In the above description using FIG. 2 and FIG. 3, the circuit 200 has been described as an encoding circuit. However, the circuit 200 operates as a decoding circuit only by changing the order of use of the partial encoding / decoding blocks 202 and 204. Can be made. That is, it is possible to realize a decoding circuit having a circuit configuration in which verification is performed by performing encoding processing in parallel as reverse processing to decoding processing of the previous stage while performing decoding processing of a certain stage. Many of the embodiments of the present invention can operate as both an encoding circuit and a decoding circuit. Therefore, an embodiment in which the number of divisions is four will be described with reference to the decoding process in detail.

FIG. 4A is a diagram for explaining the main part of the circuit configuration of the encoding / decoding circuit 400 described as the second embodiment. As shown in the figure, the encoding / decoding circuit 400 is configured to perform pipeline processing of encoding operations and decoding operations in four

stages

410, 420, 430, and 440. Each stage includes partial encoding / decoding blocks (412, 422, 432, 442), and is in charge of different stages of encoding / decoding processing. The block 412 is responsible for the first stage of the encoding process and the fourth stage of the decoding process, the block 422 is responsible for the second stage of the encoding process and the third stage of the decoding process, and the block 432 is the third stage of the encoding process. The stage and the second stage of the decoding process are in charge, and the block 442 is in charge of the fourth stage of the encoding process and the first stage of the decoding process. The encoding process and the decoding process performed in each of the partial encoding / decoding blocks 412 to 442 have an inverse function relationship. As illustrated in FIG. 4B, when the input data is processed in the order of

blocks

412, 422, 432, and 442, the encoding / decoding circuit 400 operates as an encoding circuit, and the input data is processed into

blocks

442 and 432. , 422, 412 operate as a decoding circuit.

Each encoding / decoding block holds the first register (413, 423, 433, 443) for holding the data processed in the block and the previous cycle data for error detection. A second register (414, 424, 434, 444) is provided. In addition, a comparator that determines whether the data held in the second register (414, 424, 434, 444) and the data restored by performing the inverse process are the same for each encoding / decoding block. Provided (415, 425, 435, 445). In addition, the encoding / decoding circuit 400 is provided with selectors (411, 421, 431, 441) for controlling data input for the respective encoding / decoding blocks (412, 422, 432, 442). .

Whether the encoding / decoding circuit 400 operates as an encoding circuit or a decoding circuit, each encoding / decoding block (412, 422, 432, 442) is Switching between encoding processing and decoding processing. In a cycle in which a certain encoding / decoding block performs encoding processing, adjacent blocks perform decoding processing. When the encoding / decoding circuit 400 operates as an encoding circuit, the decoding process is performed for error detection. Conversely, when the encoding / decoding circuit 400 operates as a decoding circuit, the encoding process is performed for error detection.

The data partially processed in each stage is held in the first register (413, 423, 433, 443), passed to the right stage if it is encoded in the next cycle, and passed to the left stage if it is decoded. You can continue. At the same time, reverse processing for error detection is performed at the same stage, and the data of the previous cycle held in the second register (414, 424, 434, 444) matches the data after reverse processing. It is checked by a comparator (415, 425, 435, 445).

FIG. 5 is a diagram depicting a state where the encoding / decoding circuit 400 operates as a decoding circuit. The upper (a) shows the operation in a certain cycle, and the lower (b) shows the operation in the next cycle of (a). The state of the operation of the encoding / decoding circuit 400 in the next cycle of (b) returns to (a). Data to be decoded is input from the upper right of the figure, and decoded data is output at the lower left.

As shown in FIG. 5, at each stage, decoding and verification (error detection) by encoding are performed alternately. For example, the partial encoding / partial decoding block 442 performs decoding processing in the cycle (a), but performs encoding processing as verification of the decoding processing in the cycle (b). Similar relationships can be seen for any of the partial encoding / decoding blocks 412, 422, 432, 442.

Also, in a stage adjacent to the stage where decoding is performed, encoding is performed in parallel in order to verify the result of decoding one cycle before. For example, looking at the partial encoding / partial decoding block 432 and the partial encoding / partial decoding block 442 in (b), the partial encoding / partial decoding block 432 executes the second stage decoding operation. In the partial encoding / partial decoding block 442, a fourth-stage encoding process as an inverse operation of the first-stage decoding operation is executed for error detection. The same relationship can be seen in the partial encoding / partial decoding blocks 422 and 432 in (a) and the partial encoding / partial decoding blocks 412 and 422 in (b).

In FIG. 5, hatched components and broken-line buses indicate portions where processing is not performed, and it can be understood that half of the registers and comparators are not used in each cycle. This indicates that the register and the comparator can be shared in two stages. Next, the encoding / decoding circuit 600 described with reference to FIG. 6 is an embodiment that utilizes this fact and halves the register and the comparator in the encoding / decoding circuit 400. In the encoding circuit 200 described with reference to FIG. 2, only two registers (206, 208) and one comparator (210) are provided for the two partial encoding / decoding blocks 202, 204. It was not provided for the same reason.

An encoding / decoding circuit 600 depicted in FIG. 6 is a modification of the encoding / decoding circuit 400, and is characterized in that adjacent encoding / decoding blocks share a register and a comparator. Is. As can be seen by comparing FIG. 6 and FIG. 4, the

registers

413 and 423 depicted in FIG. 4 are replaced with one register 613 in FIG. 6, and the

registers

414 and 424 in FIG. 614. Also, the

comparators

415 and 425 depicted in FIG. 4 are replaced with one comparator 615 in FIG. The same applies to the relationship between the

registers

433 and 443 in FIG. 4 and the register 633 in FIG. 6, the

registers

434 and 444 in FIG. 4 and the register 634 in FIG. 6, the comparatively 435 and 445 in FIG. .

The encoder / decoder circuit 600 has

selectors

616, 617, 626, and 627 added to the encoder / decoder circuit 400 in order to share registers and comparators. Since the device can be shared in two stages, the overall circuit scale can be smaller than that of the encoding / decoding circuit 400.

[Application example to AES]
Next, as a specific embodiment of the present invention, an example applied to an international standard encryption AES (Advanced Encryption Standard) circuit is shown. The cipher has a characteristic that if even one bit of original data is different, it is converted into completely different data. For this reason, when an arithmetic error occurs, it results in a very serious problem that data cannot be restored at all. Since cryptography is also used for money-related applications such as IC cards, it is necessary to cope with malfunctions caused by unauthorized application of noise to power supplies and clocks by malicious users trying to steal secret information. There is. For this reason, the encryption circuit is required to have particularly high reliability among the encoding / decoding circuits, and a high-performance error detection mechanism is indispensable.

FIG. 7 is a schematic diagram of an example of an AES encryption / decryption circuit that uses a 128-bit secret key and does not have an error detection function. In order to perform encryption and decryption by repeating a conversion called a round function 10 times for 128-bit data, normally, only one round function block is prepared as in the data conversion unit on the left side of this figure, A loop architecture that uses it 10 times in one encryption (or decryption) is used. The round function is mainly composed of four parts, and is expressed as ShiftRows, SubBytes, MixColumns, and AddRoundKey in the case of encryption. Decoding is performed by processing that is an inverse function of these, and is represented as InvShiftRows, InvSubBytes, InvMixColumns, and AddRoundKey, respectively. (In the figure, MixColumns and InvMixColumns are represented as MixCol. And InvMixCol., Respectively.) The functions corresponding to encryption and decryption share a circuit. Even if the same input data is converted by the same function, completely different data is output by changing the secret key. The secret key is input 10 times to the round function while being simply converted by the right key scheduler.

In FIG. 7, a data register 712 is used to hold the processing result of each loop in order to perform loop processing. Processing of ShiftRows and its inverse function InvShiftRows is performed at block 714, and processing of SubBytes and its inverse function InvSubByte is performed at block 716. MixColumns and its inverse function InvMixColumns are processed in block 718 and AddRoundKey is processed in block 720.

FIG. 8 shows a circuit configuration in which the two-part configuration described with reference to FIG. 2 is applied to the AES circuit of FIG. The round function is divided into 2 blocks that combine ShiftRows / InvShiftRows and SubBytes / InvSubByte, and MixColumns / InvMixColumns and AddRoundKey. That is, when FIG. 2 is compared with FIG. 8, the partial encoding / partial decoding block 202 in FIG. 2 corresponds to the ShiftRows / InvShiftRows block 714 and SubBytes / InvSubByte block 716 in FIG. The decryption block 204 corresponds to the MixColumns / InvMixColumns block 718 and the AddRoundKey blocks 820 and 821 in FIG. 2 corresponds to the register 712 in FIG. 8, and the register 208 in FIG. 2 corresponds to the register 812 in FIG. 2 corresponds to the comparator 210 in FIG. Further, in the AES circuit of FIG. 8,

selectors

824 and 826 corresponding to the

selectors

212b and 212c of FIG. 2 are provided in order to make the AES circuit of FIG. 7 into two stages.

In the configuration of FIG. 2, encoding was performed once in two cycles. On the other hand, the circuit of FIG. 7 performs encryption (encoding) in 10 cycles, and FIG. 8 performs error detection by performing inverse transformation for each round function of each cycle, so that encryption is performed once in 20 cycles. Will do. However, if one round function conversion is considered as one encoding, it is basically equivalent to FIG. The coincidence signal 1 in FIG. 8 outputs an error check result of half round function processing for each cycle.

In the architecture of FIG. 8, the XOR gate is not shared by changing the order of the AddRoundKey block and the InvMixColumns block. Therefore, in FIG. 7, there is one AddRoundKey block (720), whereas in FIG. 8, there are two (820, 821). In the architecture of FIG. 7, the round function block that is a critical path can be shortened by sharing the XOR gate, but instead, the MixColumns block is required in the key scheduler unit. On the other hand, in the implementation of the proposed method that divides the round function into two, the balance between the circuit scale and the operation speed is better when the MixColumns block of the key scheduler unit is omitted without sharing the XOR. By the way, when the delay time of the round function block is shortened by the division, the key scheduler unit becomes a critical path. Therefore, a register is also inserted in the key scheduler unit so that one round is processed with two clocks.

Even if the round function is operating correctly, an error may occur in the processing of the key scheduler unit, or the 10-round repetitive processing may be terminated once by a failure of the control counter. To prevent this, the key generated on-the-fly when the last round of processing is completed is checked with the comparator 830 for a match between the decryption key register for encryption and the encryption key register for decryption. is doing. Even if the attacker can skip the value of the counter, it is impossible to correctly skip up to 128 bits of the key scheduler whose value is unknown.

Referring to FIG. 9, an operation example at the time of encryption of the AES circuit having the configuration shown in FIG. 8 will be described. When the head of the arrow is painted black, it indicates that there is a processing flow, and when it is outlined, there is no processing flow. The initial key K0 for encryption is input to the encryption key register 732, converted into an initial key for decryption (= final key for encryption) K10 by the right key scheduler unit, and already set in the decryption key register 734. It shall be.

First, in (a), the input plaintext and the encryption initial key K0 are XORed and written as D0 in the data register 712, and the data that has passed through the paths of the ShiftRrows block 714 and the SubBytes block 716 in the first half of the encryption process. Is fed back as D1X. At the same time, the data D0 is passed to the comparison register 812. In the key scheduler, the first round key K1 is generated from the initial key K0 on the fly. In (b), decryption is performed in the path used for encryption in (a) for verification, and the data D1X written in the data register 712 is inversely converted by the InvShirtRows block 714 and InvSubBytes block 716, and then compared. The comparator 828 compares the value D 0 held in the comparison register 812. On the other hand, the same data D1X is converted to D1 by the MixColumns block 718 and the AddroundKey block 820 (XOR with the round key K1) in another path. In (c), the value D1 of the data register 712 is converted to D2X in the same path as in (a), and at the same time, in the right path, D1X in the InvMixColumns block 718 and AddroundKey block 821 (XOR with the round key K1). And the value of the comparison register 812 is compared. Similarly, encryption and verification are repeated until the ninth round.

In (d), processing of the InvShiftrows block and InvSubBytes block is performed for error detection, and XOR processing with the key K10 of the final tenth round, which is the final processing of encryption, is performed. As shown in FIG. 3, since the MixColumns block is not processed in the final round, the processing block is bypassed. Since it is the final round, it is checked that 10 rounds have been processed properly by comparing K10 of the round key register generated on-the-fly with K10 of the encryption key register 732 by pre-calculation. Although the ciphertext D10 can be output here, the ciphertext D10 is output after it is finally confirmed that the process returns to D10X in (e). Since the next plaintext is not input until this final check is completed, the number of clocks required for encryption of one block is 20 clocks (= 10 rounds × 2 clocks) plus one clock of (e), which is 21 clocks. Become.

The table of FIG. 10 shows the results of designing the circuits of FIG. 7 and FIG. 8 and evaluating the circuit scale and operation speed by logic synthesis using a 90 nm CMOS standard cell library. In the circuit of FIG. 8, the cycle number is 21 because the design is such that one cycle interval is inserted to enter the next data after the encryption is completed as described above. In addition to the two types that minimize the circuit scale (gate) and the maximum operation speed (throughput), the optimization at the time of logic synthesis is also implemented to maximize the circuit efficiency that is the throughput per unit gate. It was. The circuit scale and operation speed vary greatly depending on the conditions of logic synthesis. The smaller the size, the slower the speed, and the higher the speed, the larger the circuit scale. difficult. Therefore, circuit efficiency is optimal as an index for simple comparison. As can be seen from the table of FIG. 10, in both the circuit scale optimization and the operation speed optimization, no error detection and the circuit efficiency of the present invention are equivalent. Even in an implementation in which the balance between the scale and the speed is optimum, the present invention is 145.51 kbps / gate, which is 85.5% of 169.48 kbps / gate without error detection. That is, it can be seen that the AES circuit to which the present invention is applied is an excellent technique capable of reliably detecting an error with an overhead of only about 15% at the maximum.

The embodiments of the present invention have been described above. However, these embodiments are not intended to limit the scope of the present invention, but are intended to contribute to a deep understanding of the present invention. The present invention can take various embodiments other than the embodiments described in the present specification without departing from the scope of the idea. The embodiments described in the claims are preferred embodiments of the present invention, but the embodiments of the present invention are not limited thereto, and can be felt by those skilled in the art from the application documents and common general knowledge of the present application. Includes all configurations.

200 Encoding Circuit 200

Encoding Circuit

202, 204 Partial Encoding /

Partial Decoding Block

206, 208 Register 208 Register 210 Comparator 212a-212c Selector 400 Encoding /

Decoding Circuit

410, 420, 430, 440

Stages

411, 421, 431 , 441

Selector

412, 422, 432, 442 Partial encoding /

decoding block

413, 423, 433, 443

Register

414, 424, 434, 444

Register

415, 425, 435, 445 Comparator 600 Encoding / decoding circuit 613 Register 614 Register 615

Comparator

616, 617, 626, 627 Selector 633 Register 634 Register 635 Comparator

Claims

An encoding circuit that performs encoding processing by pipeline processing of a plurality of stages, including at least stage X and stage Y that is the next stage of stage X,
Each of the plurality of stages includes a partial encoding / partial decoding block capable of executing a partial encoding process that is a part of the encoding process and a partial decoding process that is an inverse process of the partial process,
In a cycle
In the stage Y, the data partially encoded in the stage X in the cycle immediately before the certain cycle is partially encoded,
In the stage X, the data partially encoded in the stage X in the previous cycle is partially decoded,
The previously stored data before partial encoding at the stage X in the previous cycle is compared with the partially decoded data;
In the next cycle of the certain cycle,
In the stage Y, the data partially encoded in the stage Y in the certain cycle is partially decoded,
The pre-stored data before partial encoding at the stage Y in the certain cycle is compared with the data partially decoded at the stage Y,
An encoding circuit configured as a circuit in which another data is partially encoded in the stage X;
A decoding circuit that performs decoding processing by pipeline processing of a plurality of stages, including at least stage X and stage Y that is the next stage of stage X,
Each of the plurality of stages includes a partial encoding / partial decoding block capable of executing a partial decoding process that is a part of the decoding process and a partial encoding process that is a reverse process of the part,
In a cycle
In the stage Y, the data partially decoded in the stage X in the cycle immediately before the certain cycle is partially decoded,
In the stage X, the data partially decoded in the stage X in the previous cycle is partially encoded,
The previously stored data before partial decoding at the stage X in the previous cycle is compared with the partially encoded data;
In the next cycle of the certain cycle,
In the stage Y, the data partially decoded in the stage Y in the certain cycle is partially encoded,
The pre-stored data before partial decoding at the stage Y in the certain cycle is compared with the data partially encoded at the stage Y,
A decoding circuit configured as a circuit in which another data is partially decoded in the stage X.
The stage X includes a partial encryption / partial decryption block capable of executing a partial encryption process that is a part of a randomizing function that is repeatedly executed in encryption and a partial decryption process that is an inverse function of the part, 2. The stage Y includes a partial encryption / partial decryption processing block capable of executing a partial encryption process that is the remainder of the randomizing function and a partial decryption process that is an inverse function of the remainder. The encoding circuit described in 1.
The stage X includes a partial decryption / partial encryption block capable of executing a partial decryption process that is a part of a randomizing function that is repeatedly executed in decryption and a partial encryption process that is an inverse function of the part, The stage Y includes a partial decryption / encryption processing block capable of executing a partial decryption process that is the remainder of the randomizing function and a partial encryption process that is an inverse function of the remainder. Decoding circuit.
(A) An encoding circuit that performs encoding processing by pipeline processing of N stages (N is an integer of 2 or more),
(B) Each stage includes a partial encoding / partial decoding block capable of executing a partial encoding process that is a part of the encoding process and a partial decoding process that is an inverse process of the partial process.
(C) For each of the partial encoding / partial decoding blocks, a first register that is a register for storing a result of partial encoding processing of the partial encoding / partial decoding block, and the partial encoding / partial A second register, which is a register for storing a copy of the input data to the decoding block, and a comparator are allocated;
(D) In a cycle in which partial encoding processing by the i-th (2 ≦ i ≦ N) partial encoding / partial decoding block is performed,
(D-1) Using the data stored in the first register relating to the i−1th partial encoding / partial decoding block as input data, the partial encoding process by the i th partial encoding / partial decoding block is performed. Executed,
(D-2) The data subjected to the partial coding process is prepared to be stored in the first register related to the i-th partial coding / partial decoding block in the next cycle of the cycle,
(D-3) The input data is prepared to be stored in the second register related to the i-th partial coding / decoding block in the next cycle,
(D-4) For the data stored in the first register relating to the i−1th partial coding / partial decoding block, partial decoding processing by the i−1th partial coding / partial decoding block is performed. Executed,
(D-5) The comparison process between the data subjected to the partial decoding process and the data stored in the second register regarding the i−1th partial encoding / partial decoding block is the i−1th Executed by the comparator with respect to the partial encoding / decoding block of
(E) In the next cycle,
(E-1) A store process for the first and second registers related to the i-th partial coding / decoding block is executed,
(E-2) A partial decoding process by the i-th partial coding / partial decoding block is executed on the data stored in the first register relating to the i-th partial coding / partial decoding block,
(E-3) The comparison process between the data subjected to the partial decoding process in (e-2) and the data stored in the second register relating to the i-th partial coding / partial decoding block includes: executed by the comparator for the i th partial encoding / decoding block;
(E-4) An encoding circuit configured as a circuit that executes partial encoding processing on the other data by the i-1th partial encoding / decoding block.
(A) A decoding circuit that performs decoding processing by pipeline processing of N stages (N is an integer of 2 or more),
(B) Each stage includes a partial encoding / decoding block that can execute a partial decoding process that is a part of the decoding process and a partial encoding process that is a reverse process of the partial process,
(C) For each of the partial coding / partial decoding blocks, a first register that is a register for storing a result of partial decoding processing of the partial coding / partial decoding block, and the partial coding / partial decoding A second register, which is a register for storing a copy of input data to the block, and a comparator are allocated;
(D) In a cycle in which partial decoding processing by the i-th (2 ≦ i ≦ N) partial encoding / partial decoding block is performed,
(D-1) The partial decoding process by the i-th partial encoding / partial decoding block is executed using the data stored in the first register relating to the i-1th partial encoding / partial decoding block as input data. And
(D-2) The data subjected to the partial decoding process is prepared to be stored in the first register related to the i-th partial coding / decoding block in a cycle subsequent to the cycle,
(D-3) The input data is prepared to be stored in the second register related to the i-th partial coding / decoding block in the next cycle,
(D-4) For the data stored in the first register relating to the i−1th partial coding / partial decoding block, partial coding processing by the i−1th partial coding / partial decoding block is performed. Executed,
(D-5) The comparison process between the data subjected to the partial encoding process and the data stored in the second register relating to the i−1th partial encoding / decoding block is the i−1 Executed by the comparator for the th partial encoding / decoding block;
(E) In the next cycle,
(E-1) A store process for the first and second registers related to the i-th partial coding / decoding block is executed,
(E-2) For the data stored in the first register relating to the i-th partial coding / partial decoding block, a partial coding process by the i-th partial coding / partial decoding block is executed,
(E-3) A process of comparing the data subjected to the partial encoding process in (e-2) and the data stored in the second register relating to the i-th partial encoding / decoding block, Executed by the comparator for the i th partial encoding / decoding block;
(E-4) A decoding circuit configured as a circuit for executing partial decoding processing on the other data by the i-1th partial encoding / decoding block.
The encoding circuit according to claim 5, wherein at least one of the first register, the second register, and the comparator is configured as a circuit shared by the two partial encoding / decoding blocks.
The decoding circuit according to claim 6, wherein at least one of the first register, the second register, and the comparator is configured as a circuit shared by the two partial encoding / partial decoding blocks.