Hash value generating device that performs round processing of a hash algorithm

A hash value generating device for generating a hash value based on the KECCAK algorithm includes a θ processing unit, a ρ processing unit, a π processing unit, a χ processing unit, and an ι processing unit for performing processing of five steps θ, ρ, π, χ, and ι, included in round processing of the KECCAK algorithm. The θ processing unit includes a θ1 processing unit for performing column sum calculation processing and a θ2 processing unit for performing column sum addition processing. In the round processing, the π processing unit performs processing before the θ2 processing unit and the ρ processing unit performs processing, and the ρ processing unit performs processing on a lane after rearrangement processing by the π processing unit.

TECHNICAL FIELD

The present invention relates to technique for generating a hash value.

BACKGROUND ART

A hash value, which is calculated by using a cryptographic hash algorithm, is utilized for checking data alteration. It has been already verified that Secure Hash Algorithm 1 (SHA-1), which is a cryptographic hash algorithm (cryptographic hash), is not capable of securing safety. It has been pointed out that SHA-2 family (SHA-224, SHA-256, SHA-384, and SHA-512) may lack security. Therefore, National Institute of Standards and Technology (NIST) asked the public to come up with a new algorithm to establish a next-generation cryptographic hash algorithm (SHA-3). Then, the KECCAK algorithm (“The KECCAK reference”, Version 3.0, Jan. 14, 2011, (http://keccak.noekeon.org/Keccak-reference-3.0.pdf)) was assigned as the SHA-3 in December 2012.

The SHA-3 outputs a cryptographic hash value of a fixed length from an input message (data) of any length. In the KECCAK algorithm, a permutation function is used, and in the permutation function, round processing of five sequential steps (θ, ρ, π, χ, and ι) is repeated twenty-four times. The round processing is performed on data called a “state” data piece having a length of 1600 bits.

A lot of results of preceding processing has to be once stored in a memory for the θ processing and the π processing out of the five steps of the round processing. Therefore, when the round processing is performed in the order of the steps θ, ρ, π, χ, and ι, a lot of results of preceding processing has to be once stored in a memory twice within one-time round processing, and thus speedup has been difficult.

SUMMARY OF INVENTION

The present invention is directed to a technique to improve throughput for generating hash values.

According to an aspect of the present invention, a hash value generating device for generating a hash value based on KECCAK algorithm includes a θ processing means, a ρ processing means, a π processing means, a χ processing means, and an ι processing means for performing processing of five steps θ, ρ, π, χ, and ι included in round processing of the KECCAK algorithm, the θ processing means includes a θ1processing means for performing column sum calculation processing and a θ2processing means for performing column sum addition processing, in the round processing, the π processing means performs processing before the θ2processing means and the ρ processing means perform processing, and the ρ processing means performs processing on a lane on which rearrangement processing has been performed by the π processing means.

DESCRIPTION OF EMBODIMENTS

As a hash value generating device according to an exemplary embodiment of the present invention, a device configured to generate a hash value of SHA-3 (KECCAK algorithm) will be hereinafter described as an example. In the description below, a specific data length or a specific bit value may be provided, but the present invention is not limited to the specific length or value.

First, the KECCAK algorithm will be described. Note that, specifications in more detail can be found in “The KECCAK reference”, Version 3.0, Jan. 14, 2011, (http://keccak.noekeon.org/Keccak-reference-3.0.pdf).

FIG. 1Ais a diagram illustrating a whole of the KECCAK algorithm. InFIG. 1A, message blocks101(m1to mt) are illustrated. The message blocks101(m1to mt) are generated by dividing an input message, for which a hash value is generated, into units of 1024-bit blocks.

As illustrated inFIG. 1A, all bits of initial values102and103are zeros in the present exemplary embodiment. Here, an example where all bits of initial values are zeros is described as an example, but the present invention is not limited to this example. The length of the initial value102is 1024 bits, which is the same as that of the message blocks described above, and the total length of the initial values102and103is 1600 bits. A bitwise exclusive OR (XOR) operator104is also illustrated. That is, the XOR operator104calculates exclusive OR for each bit of the two 1024-bit input data pieces and outputs the results as a 1024-bit data piece.

A KECCAK-f105, which is a permutation function, receives two input data pieces and outputs two data pieces. The detail of the KECCAK-f105will be described below with reference toFIG. 1B. A cut-out section106cuts out a necessary size from the 1024-bit input data pieces, and outputs the cut out data. A cryptographic hash value (i.e., hash value)107is calculation results of this algorithm.

FIG. 1Bis a diagram illustrating an overview of the KECCAK-f105, which is a permutation function. Round processing R201is performed twenty-four times. The detail of the round processing R will be described below. Input data pieces202and203are illustrated. The length of the input data piece202is 1024 bits. The total length of the input data pieces202and203is 1600 bits. The two input data pieces202and203are coupled and then input to the round processing R201. Output data pieces204and205are illustrated. The length of the output data piece204is 1024 bits. The total length of the output data pieces204and205is 1600 bits.

FIG. 1Cis a diagram illustrating an overview of the round processing R201. As described above, for the round processing R201, the lengths of the input data piece and the output data piece are both 1600 bits. In the round processing R201, processing of five steps (θ processing unit301, p processing unit302, π processing unit303, χ processing unit304, and ι processing unit305) to be described below is sequentially performed on the input data piece to generate the output data piece.

Data structures used in the round processing of the KECCAK algorithm and the above five steps will be described in detail below.

FIG. 2Ais a diagram illustrating a “state”, which is a data structure upon input/output of the round processing R201. As described above, both of the input data piece and the output data piece have 1600-bit length. Each of these 1600-bit data pieces is expressed as a rectangular parallelepiped having a width (x axis direction) of five bits, a height (y axis direction) of five bits, and a depth (z axis direction) of sixty-four bits in three-dimensional arrangement. The rectangular parallelepiped data structure is called a “state”. A 1600-bit data piece is allocated to the state structure expressed as a rectangular parallelepiped in the order of the z axis direction, the x axis direction, and the y axis direction. The detail will be described below with reference toFIG. 2F.

FIG. 2Bis a diagram illustrating a data structure “plane”. The plane structure is expressed as a planar structure that is parallel to the x-z plane and that has a width of five bits, a height of one bit, and a depth of sixty-four bits. That is, the above “state” structure can be considered as five plane structures that are stacked in the y axis direction.

FIG. 2Cis a diagram illustrating a data structure “sheet”. The sheet structure is expressed as a planar structure that is parallel to the y-z plane and that has a width of one bit, a height of five bits, and a depth of sixty-four bits. That is, the above “state” structure can be considered as five sheet structures arranged horizontally in line in the x axis direction.

FIG. 2Dis a diagram illustrating a data structure “lane”. The lane structure is expressed as a linear structure that is parallel to the z axis and that has a width of one bit, a height of one bit, and a depth of sixty-four bits. That is, the above “state” structure can be considered as twenty-five lane structures gathered along the x-y plane.FIG. 2Fis a diagram illustrating the order of twenty-five lanes included in one state structure.

FIG. 2Eis a diagram illustrating a data structure “column”. The column structure is expressed as a linear structure that is parallel to the y axis and that has a width of one bit, a height of five bits, and a depth of one bit. That is, the above “sheet” structure can be considered as sixty-four column structures arranged in line in the z axis direction.

In the first exemplary embodiment, a case where the input data piece is 1600 bits are described, but the present invention is not limited to the case. In addition, an example where data of the state structure is handled as a rectangular parallelepiped data structure having a width (x axis direction) of five bits, a height (y axis direction) of five bits, and a depth (z axis direction) of sixty-four bits will be described, but the present invention is not limited thereto. For example, an input data piece may have 800 bits, and the state structure data may be handled as a rectangular parallelepiped data structure having a width of five bits, a height of five bits, and a depth of thirty-two bits.

Further, the plane structure, the sheet structure, the lane structure, and the column structure can be modified according to the respective numbers of bits in the width (x axis direction), in the height (y axis direction), and in the depth (z axis direction) of the state structure. More specifically, when the state structure data has m bits in the x axis direction, n bits in the y axis direction, and s bits in the z axis direction, the plane structure is a planar structure having m bits in the x axis direction, one bit in the y axis direction, and s bits in the z axis direction. The sheet structure is a planar structure having one bit in the x axis direction, n bits in the y axis direction, and s bits in the z axis direction. The lane structure is a linear structure having one bit in the x axis direction, one bit in the y axis direction, and s bits in the z axis direction. The column structure is a linear structure having one bit in the x axis direction, n bits in the y axis direction, and one bit in the z axis direction.

Next, a method of forming an input data piece for the first round processing R201from the input data pieces202and203that have been input to the KECCAK-f105will be described. First, the input data pieces202and203are coupled in this order to form a 1600-bit data block. Next, the 1600-bit data block is divided into units of sixty-four bit block to form twenty-five lanes. Last, the twenty-five lanes are arranged in the order illustrated inFIG. 2Falong the x-y plane to build one state. The thus generated state structure is input to the round processing R201. A method of forming the output data pieces204and205from an output data piece of the twenty-fourth round processing R201is similar, and thus the description thereof is not provided.

Next, five steps (steps θ, ρ, π, χ, and ι) included in the round processing R201will be described. In each of the steps, the data structure of an input data piece and an output data piece is the state structure.

FIG. 3Ais a diagram illustrating processing in the step θ(θ processing unit301). The step θ is processing of adding the sum of two columns to each bit, the two columns being adjacent to the bit. More specifically, the θ processing unit calculates each bit of the output state as follows. That is, the each bit is calculated as the sum of three values obtained from the input state: “a value of a bit at the same position”; “the sum of bits of a column at a position of −1 in the x axis direction”; and “the sum of bits of a column at a position of +1 in the x axis direction and −1 in the z axis direction”. Here, the sum means the sum on GF(2), and the result will be the same as that of the exclusive OR operation. The processing can be expressed by the following expression.

a′⁡[x]⁡[y]⁡[z]←a⁡[x]⁡[y]⁡[z]+∑y′=04⁢a⁡[x-1]⁡[y′]⁡[z]+∑y′=04⁢a⁡[x+1]⁡[y′]⁡[z-1]
In the expression, x is 0 to 4, y is 0 to 4, z is 0 to 63.

FIG. 3Bis a diagram illustrating processing in the step θ upon calculation of a bit in an end part (x=0, for example). In order to calculate a bit at x=0, “a column at a position of −1 in the x axis direction” corresponds to a column opposite in the state, that is, “the column at a position of x=4”. As described above, a coordinate beyond the state is regarded as a position that is opposite in the state. That is, coordinate values are cyclically shifted in the same state. This rule is similarly applied to x coordinate, y coordinate, and z coordinate and to four other steps.

FIGS. 4A, 4B, and 4Care diagrams illustrating processing in the step ρ (ρ processing unit302). The step ρ is processing of shifting values of respective bits in the z axis direction. More specifically, the ρ processing unit302cyclically shifts values in each lane of the state in the z direction by the specified number of bits as illustrated inFIG. 4Aand outputs the shifted values. The number of bits by which the values are shifted in each lane is previously determined as the number illustrated inFIG. 4B. Note that, in order to perform the ρ processing, a holding section previously holds a table listing shifting amounts as illustrated inFIG. 4Cand the ρ processing unit302performs the ρ processing using the table being held.

FIGS. 5A and 5Bare diagrams illustrating processing in the step π (π processing unit303). The step π is processing of rearranging each of the respective bits in the x-y plane (also referred to as a “slice”), that is, processing of rearranging twenty-five lanes in a single state. More specifically, when respective lanes in the input state are numbered as illustrated in the upper part ofFIG. 5A, the output state is illustrated in the lower part thereof. Note that, in order to perform the n processing, the holding section previously holds a table listing rearrangement destinations as illustrated inFIG. 5Band the π processing unit303performs the π processing using the table being held.

FIG. 6is a diagram illustrating processing in the step χ (χ processing unit304). The step χ is processing of converting a bit using bits in a line in the χ axis direction (also referred to as a “row”), and each bit in the output row is derived based on three bits in the same input row. More specifically, setting is made such that when a bit at a position of +1 in the x axis direction from each bit of the input row is zero and a bit at a position of +2 in the x axis direction from the bit is one, the χ processing unit304inverts the value of the each corresponding bit of the output row.

FIG. 7is a diagram illustrating processing in the step ι (ι processing unit305). The step ι is processing of adding a round constant to each bit.FIG. 8is a diagram illustrating round constants used in the step ι. In the step ι, the ι processing unit305performs exclusive OR (XOR) on a bit line of a lane at x=y=0 with a round constant (64-bit value) predetermined for each round. More specifically, the L processing unit305calculates bitwise exclusive OR of a 64-bit value of a lane at x=y=0 (when a bit at z=63 is MSB and a bit at z=0 is LSB) and a round constant illustrated inFIG. 8. Then, the ι processing unit305sets the result as a bit line of a lane at x=y=0 in the output state.

From the processing contents of the above respective steps (steps θ, ρ, π, χ, and ι), it can be understood that there are following limitations regarding start of the processing of the respective steps.In the step θ, the θ processing unit301uses a sheet data piece at −1 and a sheet data piece at +1 in the x axis direction to calculate each lane in the state. Therefore, when the first three sheets are completed, that is, when the θ processing unit301receives twenty-three lanes out of the twenty-five lanes from a preceding stage, the θ processing unit301can start the processing in the step θ.The step ρ is calculation for each of lanes independent of each other. Therefore, when one lane of calculation results of the preceding stage (step θ) is output, the ρ processing unit302can start the processing in the step ρ.In the step π, respective lanes in a state are rearranged. Therefore, when one whole state of calculation results of the preceding stage (step ρ) is output, that is, when twenty-five lanes are output, the π processing unit303can start the processing in the step π.In the step χ, in calculation of each lane in a state, the χ processing unit304uses a lane at +1 in the x axis direction and a lane at +2 in the x axis direction. Therefore, upon receiving three lane data pieces, the χ processing unit304can start the processing in the step χ.The step ι is calculation for each of lanes independent of each other. Therefore, when one lane of calculation results of the preceding stage (step χ) is output, the ι processing unit305can start the processing in the step ι.

In other words, in the steps θ, π, and χ, start of processing has to wait until the steps at the respective preceding stages output calculation results of twenty-three lanes, twenty-five lanes, and three lanes respectively. As described above, particularly the processing of the two steps θ and π can be started when a long time has passed after the start of processing of their preceding stages.

This means that throughput can be improved when the starting time of the step θ or the step π can be hastened. However, the operation order of the specifications of the KECCAK algorithm does not allow improvement of throughput. Thus, the operation order has to be different from that of the KECCAK algorithm in order to improve throughput.

Next, round processing R′901will be described. The round processing R′901is processing used in the present exemplary embodiment and designed such that the result is the same as that of the round processing R201. However, processing contents of the round processing R′901are different from the specifications of the KECCAK algorithm.

FIG. 9Ais a diagram illustrating an overview of the round processing R′901. The round processing R′901is designed such that the processing result is the same as that of the round processing R201. In the round processing R′901, processing of six steps is performed (by a θ1processing unit902, a π processing unit903, a θ2processing unit904, a ρ′ processing unit905, a χ processing unit906, and an ι processing unit907) on an input data piece to generate an output data piece.

Note that, the π processing unit903, the χ processing unit906, and the ι processing unit907performs processing similar to those performed by the π processing unit303, the x processing unit304, and the ι processing unit305of the round processing R201. The ρ′ processing unit905performs processing of shifting values of respective bits in the z axis direction similarly to the ρ processing unit302of the round processing R201, but the number of bits by which the values are shifted is different. The θ1processing unit902and the θ2processing unit904are obtained by dividing the θ processing unit301in the round processing R201.

Since the π processing, the χ processing, and the ι processing in the round processing R′901are similar to those in the round processing R201, the description thereof is not provided. The ρ′ processing, the θ1processing, and the θ2processing will be described below.

FIG. 10Ais a diagram illustrating processing in the step ρ′ (ρ′ processing unit905). In the step ρ′, the ρ′ processing unit905performs processing of cyclically shifting a value of each bit in the z axis direction similarly to the step ρ. However, the number of bits by which the values are cyclically shifted in each lane is different from that of the step ρ, and is illustrated inFIG. 10B. Note that, in order to perform the ρ′ processing, a holding section previously holds a table listing shifting amounts as illustrated inFIG. 10Cand the ρ′ processing unit905performs the ρ′ processing using the table being held. This table is determined in consideration of the π processing. The detail will be described below.

In order to describe that the processing result of the round processing R′901and that of the round processing R201are the same, first, there will be described that the processing result of the round processing R201and the processing result of round processing R″911are the same.

FIG. 9Bis a diagram of the round processing R″911. In the round processing R″911, processing of five steps is performed (by a θ processing unit912, a π processing unit913, a ρ′ processing unit915, a χ processing unit916, and an ι processing unit917) on the input data piece to generate an output data piece. Here, the θ processing unit912, the π processing unit913, the χ processing unit916, and the ι processing unit917are respectively similar to the θ processing unit301, the π processing unit303, the χ processing unit304, and the ι processing unit305of the round processing R201. The ρ′ processing unit915is similar to the ρ′ processing unit905of the round processing R′901.

When the round processing R201is compared with the round processing R″911, they are different in a point that the π processing unit913and the ρ′ processing unit915perform the processing in this order in the round processing R″911while the ρ processing unit302and the π processing unit303perform the processing in this order in the round processing R201.

Here, in the step ρ of the round processing R201, the ρ processing unit302shifts values in the z axis direction according to rules determined for respective lanes, and the n processing unit303rearranges the respective lanes. On the other hand, in the round processing R″911, the π processing unit913rearranges the respective lanes (processing in the step π), and thereafter the ρ′ processing unit915shifts values in the z axis direction according to rules determined for the respective lanes in consideration of the rearrangement processing (processing in the step ρ′). More specifically, in the round processing R″911, the step π is performed before the step ρ′, but the shifting amount by which values are shifted in the z axis direction by the ρ′ processing unit915is changed in consideration of the processing in the step π, whereby the processing result of the round processing R″911becomes the same as that of the round processing R201.

FIG. 10Cis a table listing shifting amounts for respective lanes used in the step ρ′.

A method of generating the table illustrated inFIG. 10Cwill be specifically described. First, the round processing R201will be considered. In the round processing R201, the ρ processing unit302and the π processing unit303perform the processing in this order. The numbers inFIG. 4Bare shifting amounts in the step ρ. For example, the shifting amount for a lane at the position of x=0 and y=4 is eighteen bits. Next, the lane rearrangement by the π processing is confirmed usingFIGS. 5A and 5B. It can be seen that the π processing unit303moves the lane at the position of x=0 and y=4 to the position of x=4, y=2.

Next, the round processing R″911will be considered. In the round processing R″911, the π processing unit913and the ρ′ processing unit915perform the processing in this order. Since the π processing is performed before the ρ′ processing, a lane for which the ρ′ processing unit915should shift values by eighteen bits is a lane at the position of x=4, y=2. Therefore, the number at the position of x=4, y=2 inFIG. 10Bis eighteen. Shifting amounts of the other lanes can be similarly obtained to be the other numbers inFIG. 10B.

That is, the table listing the shifting amounts for the respective lanes used in the step ρ′ illustrated inFIG. 10Cis a table determined in consideration of the rearrangement processing of the π processing.

Next, there will be described that the processing result of the round processing R″911is the same as that of the round processing R′901.

Note that, the π processing unit903, the ρ′ processing unit905, the χ processing unit906, and the ι processing unit907respectively perform the processing similarly to the π processing unit913, the ρ′ processing unit915, the χ processing unit916, and the ι processing unit917of the round processing R″911. The θ1processing unit902and the θ2processing unit904are obtained by dividing the θ processing unit912.

When the round processing R″911is compared with the round processing R′901, they are different in a point that the θ processing unit912and the π processing unit913perform the processing in this order in the round processing R″911while the θ1processing unit902, the π processing unit903, and the θ2processing unit904perform the processing in this order in the round processing R′901.

Here, in the round processing R″911, the step θ is a step of adding the sum of two columns to each bit, the two columns being adjacent to the bit, and the step π is a step of rearranging the respective lanes. On the other hand, in the round processing R′901, the θ1processing unit902calculates the sum of two columns that are adjacent to each bit (the step θ1). Then, the π processing unit903rearranges the respective lanes (the step π), and the θ2processing unit904adds the sum of the columns to a bit in consideration of the rearrangement of the respective lanes (the step θ2).

FIG. 11is a diagram illustrating processing in the step θ1. The step θ1corresponds to the operation of the first half of the step θ and is a step of performing column sum calculation processing. More specifically, the processing is for calculating, for each column, the sum (to be referred to as θ mean value) of two values: “the sum of bits in a column at a position of −1 in the x axis direction” and “the sum of bits in a column at a position of +1 in the x axis direction and −1 in the z axis direction”. After receiving twenty-five lane data pieces, the θ1processing unit902outputs a θ intermediate value of one bit for each column that totals up to θ intermediate values of five times sixty-four bits. A structure for all of the θ intermediate values will be expressed as a planar structure that is parallel to the x-z plane and that has a width of five bits, a height of one bit, and a depth of sixty-four bits.

FIG. 12Ais a diagram illustrating processing in the step θ2. The step θ2corresponds to the operation of the second half of the step θ and is a step of performing column sum addition processing. That is, the step θ2is a step of adding e intermediate values calculated in the step θ1to the respective bits.

However, it should be noted that the step π has been already performed before the step θ2. More specifically, in the step θ of the round processing R″911(i.e., the step θ of the round processing R201), an x coordinate of each bit and an x coordinate of a θ intermediate value used for calculation of the bit is the same. However, in the step θ2of the round processing R′901, an x coordinate of each bit and an x coordinate of a θ intermediate value used for calculation of the bit is different and the x coordinate is determined in consideration of the rearrangement of the respective lanes in the step π. The x coordinates of θ intermediate values used for calculation of respective bits are illustrated inFIG. 12B. Note that, a holding section previously holds a table inFIG. 12Cproviding x coordinates of θ intermediate values used for calculation of respective bits in the θ2processing, and the θ2processing unit904performs the θ2processing using the table being held.

A method of generating the table illustrated inFIG. 12Cwill be specifically described. First, the round processing R″911will be considered. The x coordinates of θ intermediate values needed to calculate respective bits in the step θ are the same as the x coordinates of the respective bits. For example, a bit at the position of x=0, y=4 is calculated using a θ intermediate value at the position of x=0 in the step θ. Next, the lane rearrangement in the step π is confirmed usingFIGS. 5A and 5B. It can be seen that the π processing unit913moves the bit at the position of x=0, y=4 to the position of x=4, y=2.

Next, the round processing R′901will be considered. Since the π processing unit903has already performed the step n when the θ2processing unit904performs the step θ2, it can be seen that an x coordinate of a θ intermediate value needed for calculation of a bit at the position of x=4, y=2 in the step θ2is x=0. Therefore, a number at the position of x=4, y=2 out of the numbers provided inFIG. 12Bbecomes zero. The x coordinates of θ intermediate values for other bits can be similarly obtained to be the other numbers inFIG. 12B.

That is, the table inFIG. 12Cproviding the x coordinates of θ intermediate values when the θ2processing unit904performs the step θ2is a table determined in consideration of the rearrangement processing of the π processing.

As described above, the processing result of the round processing R201and that of the round processing R″911are the same. In addition, the processing result of the round processing R″911and the processing result of the round processing R′901are the same. Therefore, the processing result of the round processing R′901and the processing result of the round processing R201are the same.

From the processing contents of the above respective steps (steps θ1, θ2, and ρ′), it can be understood that there are following limitations regarding start of the processing of the respective steps.In the step θ1, the θ1processing unit902calculates the sum, and thus, the θ1processing unit902updates a θ intermediate value in the process of calculation every time when each lane in the state is input. Therefore, when the preceding stage outputs calculation results of one lane data piece, the θ1processing unit902can start the processing in the step θ1.In the step θ2, the θ2processing unit904adds a θ intermediate value calculated in the step θ1in calculation of each lane in the state. Since the step θ1has been completed at the time of starting the step θ2, the θ2processing unit904can start to output the processing result of the step θ2when the preceding stage (step π) outputs calculation results of one lane data piece.The step ρ′ is calculation for each of lanes independent of each other. Therefore, when the θ2processing unit904outputs calculation results of the preceding stage (step θ2) of one lane data piece, the ρ′ processing unit905can start the processing in the step ρ′.

That is, in the steps θ1, θ2, and ρ′, processing can be started when one lane data piece out of calculation results of a step of the preceding stage is output.

In addition, from the processing contents of the steps π, χ, and ι, there are following limitations regarding start of the processing of the respective steps.In the step π, respective lanes in a state are rearranged. Therefore, when the preceding stage (step θ1) outputs one whole state, that is, twenty-five lanes of calculation results of, the π processing unit903can start the processing in the step π.In the step χ, in calculation of each lane in a state, the χ processing unit906uses a lane at +1 and a lane at +2 in the x axis direction. Therefore, upon receiving the third lane data piece, the χ processing unit906can start the processing in the step χ.The step ι is calculation for each of lanes independent of each other. Therefore, when one lane of calculation results of the preceding stage (step χ) is output, the ι processing unit907can start the processing in the step ι.

In other words, in the step π, start of processing has to wait until the step of the preceding stage outputs twenty-five data pieces of calculation results. However, in the steps χ and ι, processing can be started when the steps of the preceding stages output three lane data pieces and one lane data piece out of calculation results respectively.

That is, in the steps excluding the step π, the processing can be started without waiting a long time after the start of processing of their preceding stages.

Thus, throughput can be improved by using the round processing R′901instead of the round processing R201. Hereinafter, a configuration of the round processing R′901will be described.

FIG. 13is a diagram illustrating a schematic configuration of an implementation example of the KECCAK algorithm according to the first exemplary embodiment. In FIG.13, an input data piece2101is illustrated. Here, a lane data piece out of an input data piece2101is input as a unit. An exclusive OR (XOR) operator2102calculates exclusive OR of a message block and internal data each time of performing the round processing twenty-four times. A register2103holds the whole of the internal data expressed as a state data piece.

A circuit (θ1circuit)2104performs processing in the step θ1. In the present exemplary embodiment, the circuit2104adds columns each time a lane is input and outputs θ intermediate values of five times sixty-four bits after receiving input of twenty-five lanes as a result.

A circuit (π circuit)2105performs processing in the step π. The π circuit2105performs the processing after the register2103holds twenty-five lanes, that is, one state. The data width upon input and output is 1600 bits.

A circuit (θ2circuit)2106performs processing in the step θ2. A circuit (ρ′ circuit)2107performs processing in the step ρ′. A circuit (χ circuit)2108performs processing in the step χ. A circuit (ι circuit)2109performs processing in the step ι. The θ2circuit2106, the ρ′ circuit2107, and the ι circuit2109respectively perform the processing in units of lanes, and thus perform the processing every time when a lane is input. The χ circuit2108performs the processing when three lanes are input, but the χ circuit2108performs every time when a lane is input from the fourth lane.

FIG. 14Ais an output timing chart of the respective modules of the implementation example according to the first exemplary embodiment.FIG. 14Aillustrates an output timing chart when the round processing R′901is performed twice. It takes on average twenty-eight clocks for one-time round processing.

Hereinafter, an implementation example in which processing is performed on a lane data piece as a unit by the algorithm according to the specifications will be described for comparison with the implementation example of the above first exemplary embodiment.

FIG. 15is a diagram illustrating a schematic configuration of the implementation example when processing is performed on a lane as a unit by the KECCAK algorithm according to specifications. The processing of the five steps (θ, ρ, π, χ, and ι) is similar to that described above, and thus the description thereof is not provided.

The KECCAK-f105receives one lane data piece (data having a length of sixty-four bits) from an input data piece1801at every clock. The KECCAK-f105receives lane data pieces in one state data piece in the order illustrated inFIG. 2F.

An Exclusive OR processing unit1802is an operator that calculates exclusive OR of a message block and an internal data piece upon each time of performing the round processing twenty-four times.

A register1803holds the whole of the internal data expressed as a state data piece. A processing block (π circuit)1804performs the step π. However, as described above, the processing in the step π can be performed only after the processing in the step ρ is completed. A processing block (θ circuit)1805performs the step θ, and a processing block (ρ circuit)1806performs the step ρ.

A processing block (χ circuit)1807performs the step χ, and a processing block (ι circuit)1808performs the step ι. A multiplexer1809outputs data having been input from the processing block1806in the first half of round processing and outputs data from the processing block1808in the second half thereof. The KECCAK-f outputs an output data piece1810of one lane when calculation is completed.

FIG. 14Bis an output timing chart of the respective modules when processing is performed on a lane as a unit by the algorithm according to specifications. A pair of the θ circuit1805and the ρ circuit1806and a pair of the χ circuit1807and the ι circuit1808operate in different time-periods and do not operate at the same time. It takes fifty-one clocks for one-time round processing.

As can be seen from comparison ofFIG. 14AandFIG. 14B, throughput of the processing can be improved by using the configuration of the implementation example according to the first exemplary embodiment.

More specifically, the followings can be said.All processing circuits other than the π circuit2404operate in parallel, and thus utilization efficiency of the circuits can be improved.One-time round processing can be performed within a smaller number of clocks (less time).

As described above, the π processing is performed before the θ2processing and the ρ processing are performed, and data is held for the π processing during the θ1processing is performed. Thus, time for holding data similarly to the conventional technique is reduced. Incidentally,FIG. 13illustrates an example in which the ρ processing performed after the θ2processing, but similar effect can be obtained even when the ρ processing is performed before the θ2processing is performed. When the ρ processing is performed before the θ2processing, bits to be added in the θ2processing should be determined in consideration of the fact that the ρ processing has been performed.

According to the exemplary embodiments described above, a technique capable of improving throughput for generating hash values can be provided.

This application claims the benefit of Japanese Patent Applications No. 2013-032036 filed Feb. 21, 2013 and No. 2014-017414 filed Jan. 31, 2014, which are hereby incorporated by reference herein in their entirety.