Hash value generating device

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 <img file="US9973336B2_D0001.tif" />) 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, 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 <img file="US9973336B2_D0002.tif" /> processing means for performing processing of five steps θ, ρ, π, χ, and <img file="US9973336B2_D0003.tif" /> included in round processing of the KECCAK algorithm, wherein the π processing unit receives input of data in units of planes and outputs data in units of sheets.

Further features of the present invention will become apparent from the following description of exemplary embodiments with reference to the attached drawings.

BRIEF DESCRIPTION OF DRAWINGS

<figref idref="DRAWINGS">FIGS. 1A, 1B, and 1C</figref> are diagrams illustrating the KECCAK algorithm.

<figref idref="DRAWINGS">FIGS. 2A, 2B, 2C, 2D, 2E</figref>, and <b>2</b>F are diagrams illustrating data structures.

<figref idref="DRAWINGS">FIGS. 3A and 3B</figref> are diagrams illustrating processing in step θ.

<figref idref="DRAWINGS">FIGS. 4A, 4B, and 4C</figref> are diagrams illustrating processing in step ρ.

<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> are diagrams illustrating processing in step π.

<figref idref="DRAWINGS">FIG. 6</figref> is a diagram illustrating processing in step χ.

<figref idref="DRAWINGS">FIG. 7</figref> is a diagram illustrating processing in step <img file="US9973336B2_D0004.tif" />.

<figref idref="DRAWINGS">FIG. 8</figref> is a diagram illustrating round constants in step <img file="US9973336B2_D0005.tif" />.

<figref idref="DRAWINGS">FIGS. 9A, 9B, and 9C</figref> are diagrams illustrating an overview of round processing R′.

<figref idref="DRAWINGS">FIGS. 10A, 10B, and 10C</figref> are diagrams illustrating processing in step ρ′.

<figref idref="DRAWINGS">FIG. 11</figref> is a diagram illustrating processing in step θ<b>1</b>.

<figref idref="DRAWINGS">FIG. 12</figref> is a diagram illustrating processing in step θ<b>2</b>.

<figref idref="DRAWINGS">FIGS. 13A, 13B, and 13C</figref> are diagrams illustrating processing in step θ<b>2</b>′.

<figref idref="DRAWINGS">FIGS. 14A, 14B, and 14C</figref> are operation timing charts.

<figref idref="DRAWINGS">FIG. 15</figref> is a diagram illustrating a schematic configuration of an implementation example when processing is performed on a lane as a unit by the KECCAK algorithm.

<figref idref="DRAWINGS">FIG. 16</figref> is a diagram illustrating a schematic configuration of an implementation example of the KECCAK algorithm according to a first exemplary embodiment.

<figref idref="DRAWINGS">FIG. 17</figref> is a diagram illustrating more detail of the configuration illustrated in <figref idref="DRAWINGS">FIG. 16</figref>.

<figref idref="DRAWINGS">FIG. 18</figref> is a diagram illustrating an implementation example of a register.

<figref idref="DRAWINGS">FIG. 19</figref> is a diagram illustrating an implementation example of a θ<b>2</b> &amp; ρ &amp; π circuit.

<figref idref="DRAWINGS">FIG. 20</figref> is a diagram illustrating an implementation example of a χ &amp; <img file="US9973336B2_D0006.tif" /> circuit.

<figref idref="DRAWINGS">FIG. 21</figref> is a diagram illustrating a schematic configuration of an implementation example of the KECCAK algorithm according to a second exemplary embodiment.

<figref idref="DRAWINGS">FIG. 22</figref> is a diagram illustrating an implementation example of a θ<b>2</b>&amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0007.tif" /> circuit.

<figref idref="DRAWINGS">FIGS. 23A and 23B</figref> are diagrams illustrating characteristics of processing in step π.

<figref idref="DRAWINGS">FIGS. 24A, 24B, 24C, 24D</figref>, and <b>24</b>E are diagrams illustrating sheet-plane unit conversion performed by the register.

<figref idref="DRAWINGS">FIG. 25</figref> is a diagram illustrating an implementation example of a π circuit.

DESCRIPTION OF EMBODIMENTS

Various exemplary embodiments, features, and aspects of the invention will be described in detail below with reference to the drawings.

As a hash value generating device according to a first 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).

<figref idref="DRAWINGS">FIG. 1A</figref> is a diagram illustrating a whole of the KECCAK algorithm. In <figref idref="DRAWINGS">FIG. 1A</figref>, message blocks <b>101</b> (m₁to m_t) are illustrated. The message blocks <b>101</b> (m₁to m_t) are generated by dividing an input message, for which a hash value is generated, into units of 1024-bit blocks.

As illustrated in <figref idref="DRAWINGS">FIG. 1A</figref>, all bits of initial values <b>102</b> and <b>103</b> are zeros in the present 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 value <b>102</b> is 1024 bits, which is the same as that of the message blocks described above, and the total length of the initial values <b>102</b> and <b>103</b> is 1600 bits. A bitwise exclusive OR (XOR) operator <b>104</b> is also illustrated. That is, the XOR operator <b>104</b> calculates 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-f <b>105</b>, which is a permutation function, receives two input data pieces and outputs two data pieces. The detail of the KECCAK-f <b>105</b> will be described below with reference to <figref idref="DRAWINGS">FIG. 1B</figref>. A cut-out section <b>106</b> cuts 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) <b>107</b> is calculation results of this algorithm.

<figref idref="DRAWINGS">FIG. 1B</figref> is a diagram illustrating an overview of the KECCAK-f <b>105</b>, which is a permutation function. Round processing R <b>201</b> is performed twenty-four times. The detail of the round processing R will be described below. Input data pieces <b>202</b> and <b>203</b> are illustrated. The length of the input data piece <b>202</b> is 1024 bits. The total length of the input data pieces <b>202</b> and <b>203</b> is 1600 bits. The two input data pieces <b>202</b> and <b>203</b> are coupled and then input to the round processing R <b>201</b>. Output data pieces <b>204</b> and <b>205</b> are illustrated. The length of the output data piece <b>204</b> is 1024 bits. The total length of the output data pieces <b>204</b> and <b>205</b> is 1600 bits.

<figref idref="DRAWINGS">FIG. 1C</figref> is a diagram illustrating an overview of the round processing R <b>201</b>. As described above, for the round processing R <b>201</b>, the lengths of the input data piece and the output data piece are both 1600 bits. In the round processing R <b>201</b>, processing of five steps (θ processing unit <b>301</b>, ρ processing unit <b>302</b>, π processing unit <b>303</b>, χ processing unit <b>304</b>, and <img file="US9973336B2_D0008.tif" /> processing unit <b>305</b>) 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.

<figref idref="DRAWINGS">FIG. 2A</figref> is a diagram illustrating a “state”, which is a data structure upon input/output of the round processing R <b>201</b>. 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 to <figref idref="DRAWINGS">FIG. 2F</figref>.

<figref idref="DRAWINGS">FIG. 2B</figref> is 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.

<figref idref="DRAWINGS">FIG. 2C</figref> is 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.

<figref idref="DRAWINGS">FIG. 2D</figref> is 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. <figref idref="DRAWINGS">FIG. 2F</figref> is a diagram illustrating the order of twenty-five lanes included in one state structure.

<figref idref="DRAWINGS">FIG. 2E</figref> is 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 R <b>201</b> from the input data pieces <b>202</b> and <b>203</b> that have been input to the KECCAK-f <b>105</b> will be described. First, the input data pieces <b>202</b> and <b>203</b> are coupled in this order to form a 1600-bit data block. Next, the 1600-bit data block is divided into units of sixty-four bits to form twenty-five lanes. Last, the twenty-five lanes are arranged in the order illustrated in <figref idref="DRAWINGS">FIG. 2F</figref> along the x-y plane to build one state. The thus generated state structure is input to the round processing R <b>201</b>. A method of forming the output data pieces <b>204</b> and <b>205</b> from an output data piece of the twenty-fourth round processing R <b>201</b> is similar, and thus the description thereof is not provided.

Next, five steps (steps θ, ρ, π, χ, and <img file="US9973336B2_D0009.tif" />) included in the round processing R <b>201</b> will be described. In each of the steps, the data structure of an input data piece and an output data piece is the state structure.

<figref idref="DRAWINGS">FIG. 3A</figref> is a diagram illustrating processing in the step θ (θ processing unit <b>301</b>). The step θ is processing of adding the sum of two columns to each bit, the two columns being adjacent to the bit. The θ processing unit calculates each bit of the output state 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.

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mrow><mrow><msup><mi>a</mi><mi>′</mi></msup><mo>⁡</mo><mrow><mo>[</mo><mi>x</mi><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mi>y</mi><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mi>z</mi><mo>]</mo></mrow></mrow><mo>←</mo><mrow><mrow><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>[</mo><mi>x</mi><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mi>y</mi><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mi>z</mi><mo>]</mo></mrow></mrow><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>=</mo><mn>0</mn></mrow><mn>4</mn></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mi>x</mi><mo>-</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><msup><mi>y</mi><mi>′</mi></msup><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mi>z</mi><mo>]</mo></mrow></mrow></mrow><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>=</mo><mn>0</mn></mrow><mn>4</mn></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mi>x</mi><mo>+</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><msup><mi>y</mi><mi>′</mi></msup><mo>]</mo></mrow></mrow><mo>⁡</mo><mrow><mo>[</mo><mrow><mi>z</mi><mo>-</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow></mrow></mrow></mrow></math></maths>&lt;br /&gt; In the expression, x is 0 to 4, y is 0 to 4, z is 0 to 63.

<figref idref="DRAWINGS">FIG. 3B</figref> is 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.

<figref idref="DRAWINGS">FIGS. 4A, 4B, and 4C</figref> are diagrams illustrating processing in the step ρ (ρ processing unit <b>302</b>). The step ρ is processing of shifting values of respective bits in the z axis direction. More specifically, the ρ processing unit <b>302</b> cyclically shifts values in each lane of the state in the z direction by the specified number of bits as illustrated in <figref idref="DRAWINGS">FIG. 4A</figref> and outputs the shifted values. The number of bits by which the values are shifted in each lane is previously determined as the number illustrated in <figref idref="DRAWINGS">FIG. 4B</figref>. Note that, in order to perform the ρ processing, a holding section previously holds a table listing shifting amounts as illustrated in <figref idref="DRAWINGS">FIG. 4C</figref> and the ρ processing unit <b>302</b> performs the ρ processing using the table being held.

<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> are diagrams illustrating processing in the step π (π processing unit <b>303</b>). The step π is processing of rearranging each of the respective bits in the x-y plane, that is, processing of rearranging twenty-five lanes in a single state. Note that the x-y plane may be also referred to as a “slice”. More specifically, when respective lanes in the input state are numbered as illustrated in the upper part of <figref idref="DRAWINGS">FIG. 5A</figref>, the output state is illustrated in the lower part thereof. Note that, in order to perform the π processing, the holding section previously holds a table listing rearrangement destinations as illustrated in <figref idref="DRAWINGS">FIG. 5B</figref> and the π processing unit <b>303</b> performs the π processing using the table being held.

<figref idref="DRAWINGS">FIG. 6</figref> is a diagram illustrating processing in the step χ (χ processing unit <b>304</b>). The step χ is processing of converting a bit using bits in a line in the x 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 0 and a bit at a position of +2 in the x axis direction from the bit is 1, the χ processing unit <b>304</b> inverts the value of the each corresponding bit of the output row.

<figref idref="DRAWINGS">FIG. 7</figref> is a diagram illustrating processing in the step <img file="US9973336B2_D0010.tif" /> (<img file="US9973336B2_D0011.tif" /> processing unit <b>305</b>). The step <img file="US9973336B2_D0012.tif" /> is processing of adding a round constant to each bit. <figref idref="DRAWINGS">FIG. 8</figref> is a diagram illustrating round constants used in the step <img file="US9973336B2_D0013.tif" />. In the step <img file="US9973336B2_D0014.tif" />, the <img file="US9973336B2_D0015.tif" /> processing unit <b>305</b> performs 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 <img file="US9973336B2_D0016.tif" /> processing unit <b>305</b> calculates 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 in <figref idref="DRAWINGS">FIG. 8</figref>. Then, the <img file="US9973336B2_D0017.tif" /> processing unit <b>305</b> sets 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 <img file="US9973336B2_D0018.tif" />), it can be understood that there are following limitations regarding start of the processing of the respective steps. <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0059">In the step θ, the θ processing unit <b>301</b> uses 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 unit <b>301</b> receives twenty-three lanes out of the twenty-five lanes from a preceding stage, the θ processing unit <b>301</b> can start the processing in the step θ.</li><li id="ul0002-0002" num="0060">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 unit <b>302</b> can start the processing in the step ρ.</li><li id="ul0002-0003" num="0061">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 unit <b>303</b> can start the processing in the step π.</li><li id="ul0002-0004" num="0062">In the step χ, in calculation of each lane in a state, the χ processing unit <b>304</b> uses 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 unit <b>304</b> can start the processing in the step χ.</li><li id="ul0002-0005" num="0063">The step <img file="US9973336B2_D0019.tif" /> 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 <img file="US9973336B2_D0020.tif" /> processing unit <b>305</b> can start the processing in the step <img file="US9973336B2_D0021.tif" />.</li></ul></li></ul>

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. In addition, throughput can be improved by performing the processing in units of planes or units of sheets instead of the unit of lanes in each step.

Next, round processing R′ <b>801</b> will be described. The round processing R′ <b>801</b> is processing used in the present embodiment and designed such that the result is the same as that of the round processing R <b>201</b>.

<figref idref="DRAWINGS">FIG. 9A</figref> is a diagram illustrating an overview of the round processing R′ <b>801</b>. The round processing R′ <b>801</b> is designed such that the processing result is the same as that of the round processing R <b>201</b>. In the round processing R′ <b>801</b>, processing of six steps (performed by a θ<b>1</b> processing unit <b>802</b>, a θ<b>2</b> processing unit <b>803</b>, a ρ processing unit <b>804</b>, a π processing unit <b>805</b>, a χ processing unit <b>806</b>, and an <img file="US9973336B2_D0022.tif" /> processing unit <b>807</b>) is performed on the input data piece to generate an output data piece.

Here, the ρ processing unit <b>804</b>, the π processing unit <b>805</b>, the χ processing unit <b>806</b>, and the <img file="US9973336B2_D0023.tif" /> processing unit <b>807</b> are respectively similar to the ρ processing unit <b>302</b>, the π processing unit <b>303</b>, the χ processing unit <b>304</b>, and the <img file="US9973336B2_D0024.tif" /> processing unit <b>305</b> in the round processing R <b>201</b>. The θ<b>1</b> processing unit <b>802</b> and the θ<b>2</b> processing unit <b>803</b> are obtained by dividing the θ processing unit <b>301</b> in the round processing R <b>201</b>.

Because the ρ processing, the χ processing, and the <img file="US9973336B2_D0025.tif" /> processing in the round processing R′ <b>801</b> are similar to those in the round processing R <b>201</b>, the description thereof is not provided.

The π processing unit <b>805</b> is similar to the π processing unit <b>303</b> in the round processing R <b>201</b>. However, the π processing unit <b>805</b> does not perform the processing after holding a state data piece, but outputs a sheet data piece from a plane data piece having been input. The detail will be described below.

The θ<b>1</b> processing, and the θ<b>2</b> processing will be described below.

<figref idref="DRAWINGS">FIG. 11</figref> is a diagram illustrating processing in the step θ<b>1</b>. The step θ<b>1</b> corresponds to the first half operation of the step θ. In the step, column sum calculation processing is performed. More specifically, the processing is for calculating, for each column, the sum (to be referred to as a θ intermediate 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 five sheet data pieces, the θ<b>1</b> processing unit <b>802</b> outputs 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.

<figref idref="DRAWINGS">FIG. 12</figref> is a diagram illustrating the processing in the step θ<b>2</b>. The step θ<b>2</b> corresponds to the second half operation of the step θ, and is a step of performing column sum addition processing. That is, in the step θ<b>2</b>, the θ<b>2</b> processing unit <b>803</b> adds the θ intermediate values calculated in the step θ<b>1</b> to respective bits.

From the processing contents of the above respective steps (step θ<b>1</b> and step θ<b>2</b>), it can be understood that there are following limitations regarding start of the processing of the respective steps. <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0075">The step θ<b>1</b> is calculation of the sum, and thus, the θ<b>1</b> processing unit <b>802</b> updates a θ intermediate value in the process of calculation every time when each sheet in the state is input. Therefore, when one sheet data piece of calculation results of the preceding stage is output, the θ<b>1</b> processing unit <b>802</b> can start the processing in the step θ<b>1</b>.</li><li id="ul0004-0002" num="0076">In the step θ<b>2</b>, the θ<b>2</b> processing unit <b>803</b> adds a θ intermediate value calculated in the step θ<b>1</b> in calculation of each plane in the state. Since the step θ<b>1</b> has been completed at the time of starting the step θ<b>2</b>, the θ<b>2</b> processing unit <b>803</b> can start to output the processing result of the step θ<b>2</b> when one plane data piece is output from the preceding stage (register).</li><li id="ul0004-0003" num="0077">The step ρ is calculation for each of lanes independent of each other. Therefore, when the θ<b>2</b> processing unit <b>803</b> outputs one plane data piece of calculation results of the preceding stage (step θ<b>2</b>), the ρ processing unit <b>804</b> can start the processing in the step ρ.</li><li id="ul0004-0004" num="0078">In the step π, the π processing unit <b>805</b> rearranges respective lanes in a state. However, from input of one plane, output of one sheet can be obtained. Therefore, when the ρ processing unit <b>804</b> outputs one plane data piece of the calculation results of the preceding stage (step ρ), the π processing unit <b>805</b> can start the processing in the step H.</li><li id="ul0004-0005" num="0079">In the step χ, in calculation of each lane in a state, the x processing unit <b>806</b> uses a lane at +1 in the x axis direction and a lane at +2 in the x axis direction. Therefore, the x processing unit <b>806</b> can start the processing in the step χ after receiving three sheet data pieces.</li><li id="ul0004-0006" num="0080">The step <img file="US9973336B2_D0026.tif" /> is calculation for each of lanes independent of each other. Therefore, when the χ processing unit <b>806</b> outputs one sheet data piece of calculation results of the preceding stage (step χ), the <img file="US9973336B2_D0027.tif" /> processing unit <b>807</b> can start the processing in the step <img file="US9973336B2_D0028.tif" />.</li></ul></li></ul>

Since the π processing unit <b>805</b> receives input of a plane data piece and outputs a sheet data piece in the step π, the need of holding a state data piece can be eliminated and throughput can be improved.

In addition, since the processing is performed in units of planes in the steps θ<b>2</b>, ρ and π, and in units of sheets in the steps χ and <img file="US9973336B2_D0029.tif" />, throughput can be improved.

There will be described below a configuration in which the π processing unit <b>805</b> receives input of plane data pieces and outputs sheet data pieces, and the round processing is performed in units of planes in the steps θ<b>2</b>, ρ, and π, and performed in units of sheets in the steps χ and <img file="US9973336B2_D0030.tif" />.

<figref idref="DRAWINGS">FIG. 16</figref> is a diagram illustrating a schematic configuration of an implementation example of the KECCAK algorithm according to the first exemplary embodiment. In this example, a lane structure out of an input data piece <b>1901</b> is input as a unit. However, the order of input data pieces is previously determined to be in sequential in the y direction: (x, y)=(0, 0), (0, 1), (0, 2), . . . . A register <b>1908</b> holds four lane structure data pieces that are the input data pieces <b>1901</b> and outputs a sheet structure data piece as a unit when the register <b>1908</b> receives the fifth lane structure data piece. Note that, the register <b>1908</b> may be configured to output the first sheet structure data piece when the register <b>1908</b> holds data enabling generation of at least the first sheet structure data piece. An output data piece <b>1907</b> is output in units of sheet structure data pieces when calculation is completed.

An exclusive OR (XOR) operator <b>1902</b> calculates exclusive OR of a message block and internal data each time of performing the round processing twenty-four times. A register <b>1903</b> holds the whole of the internal data. The register <b>1903</b> holds input data pieces of the sheet structure that are input and outputs output data pieces of the plane structure. A circuit <b>1904</b> is for the processing in the steps θ<b>2</b>, ρ, and π. Data input to the circuit <b>1904</b> is data of the plane structure, and data output from the circuit <b>1904</b> is data of the sheet structure. The detail will be described below. A circuit <b>1905</b> is provided for the processing in the steps χ and <img file="US9973336B2_D0031.tif" />. A circuit <b>1906</b> is provided for processing in the step θ<b>1</b>.

<figref idref="DRAWINGS">FIG. 17</figref> is a diagram illustrating the configuration of <figref idref="DRAWINGS">FIG. 16</figref> in more detail. An input data piece <b>2001</b> is the same as the input data piece <b>1901</b> in <figref idref="DRAWINGS">FIG. 16</figref>. A register <b>2009</b> holds at least the first sheet structure data piece out of the input data piece <b>2001</b> and outputs a sheet structure data piece as a unit. The register <b>2009</b> is the same as the register <b>1908</b> in <figref idref="DRAWINGS">FIG. 16</figref>. The register <b>2009</b> outputs one sheet structure data piece as a unit at every clock, and outputs sheet structure data pieces in ascending order of the x coordinate. A multiplexer <b>2002</b> outputs an input data piece as is when the multiplexer <b>2002</b> calculates exclusive OR of the input data piece and the internal state and outputs zero in other cases.

A register <b>2004</b> holds the whole of the internal data similarly to the register <b>1903</b> illustrated in <figref idref="DRAWINGS">FIG. 16</figref>. A circuit <b>2005</b> calculates in the steps θ<b>2</b>, ρ, and π (hereinafter, referred to as a θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b>). As described above, to the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b>, plane structure data pieces are input in ascending order of the y coordinate (in the order of y=0, 1, 2, 3, and 4), and the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> outputs sheet structure data pieces in ascending order of the x coordinate (in the order of x=0, 1, 2, 3, and 4).

A circuit <b>2006</b> is for the processing in the steps χ and <img file="US9973336B2_D0032.tif" /> (hereinafter, referred to as a χ &amp; <img file="US9973336B2_D0033.tif" /> circuit <b>2006</b>) and outputs one sheet structure data piece of the calculation results as a unit. A multiplexer <b>2007</b> outputs zero for initialization upon start of hash value calculation and outputs data in the process of calculation in other cases.

A circuit <b>2008</b> is for the processing in the step θ<b>1</b> (hereinafter, referred to as a θ<b>1</b> circuit <b>2008</b>) and outputs an intermediate value (θ intermediate value) of five times sixty-four bits when the circuit <b>2008</b> receives input of five sheet data pieces.

<figref idref="DRAWINGS">FIG. 18</figref> is a diagram illustrating an implementation example of the register <b>2004</b>. A combination circuit <b>2102</b> divides one sheet data piece that is an input data piece <b>2101</b> into five lane data pieces and outputs the five lane data pieces. A multiplexer <b>2103</b> alternately switches the shift direction to the vertical direction and the horizontal direction for even times of the round and odd times of the round (in <figref idref="DRAWINGS">FIG. 18</figref>, all symbols of the same shape as the multiplexer <b>2103</b> perform similarly thereto). A register <b>2104</b> is of a mesh configuration of five times five stages for storing information of one lane in one stage. The register <b>2104</b> receives input of five lane data pieces and outputs five lane data pieces (data of one sheet or one plane) at every clock. A combination circuit <b>2105</b> outputs data of five lanes (five lanes including R0, R1, R2, R3, and R4 or five lanes including R0, R5, R10, R15, and R20) having been output from the last stage of the register <b>2104</b> is output as one plane data piece. An output data piece <b>2106</b> is illustrated.

<figref idref="DRAWINGS">FIGS. 23A and 23B</figref> are diagrams illustrating characteristics of the processing in the step π.

<figref idref="DRAWINGS">FIG. 23A</figref> illustrates an example of data before the processing in the step π is performed. For ease of understanding of positions to which the respective lanes are rearranged by the π processing, sequential numbers are allocated to the respective lanes. <figref idref="DRAWINGS">FIG. 23B</figref> illustrates an example of data after the processing in the step π is performed. In this diagram, it can be seen that the bits of one plane data piece at y=0 (a data piece <b>231</b> in <figref idref="DRAWINGS">FIG. 23A</figref>) are all rearranged to positions in one sheet data piece at x=0 (a data piece <b>232</b> in <figref idref="DRAWINGS">FIG. 23B</figref>). The data pieces at y=1, 2, 3, and 4 are rearranged similarly. That is, when the processing in the step π is performed, each plane data piece at y=i (i=0, 1, 2, 3, and 4) is output as one sheet data piece at x=i.

By utilizing the characteristics of the processing in the step π as described above, the need of holding all data pieces (i.e., five plane structure data pieces) in a register for the processing in the step π is eliminated, and thus from input of one plane, one sheet output can be obtained.

<figref idref="DRAWINGS">FIGS. 24A, 24B, 24C, 24D, and 24E</figref> are diagrams illustrating sheet-plane unit conversion performed by the register <b>2004</b>. An input data piece for the register <b>2004</b> is one sheet data piece for one clock as described above. <figref idref="DRAWINGS">FIGS. 24A, 24B, and 24C</figref> are explanation diagrams of the register <b>2004</b> when a sheet data piece is input at the first clock, when the sheet data piece is input at the second clock, and when the sheet data piece is input at the fifth clock respectively. As illustrated in <figref idref="DRAWINGS">FIGS. 24A, 24B, and 24C</figref>, the register <b>2004</b> receives input of five sheet data pieces (one state data piece) over five clocks in the y direction (x direction). <figref idref="DRAWINGS">FIG. 24D</figref> is an explanation diagram of the register <b>2004</b> when the register <b>2004</b> outputs the first plane data piece after receiving input of five sheet data pieces. <figref idref="DRAWINGS">FIG. 24E</figref> is an explanation diagram of the register <b>2004</b> when the register <b>2004</b> outputs the second plane data piece. The register <b>2004</b> outputs each of five lane data pieces at every clock in the x direction (y direction) after receiving input of five sheet data pieces to provide one plane data piece. The register <b>2004</b> performs sheet-plane conversion in the above flow.

Note that, data is input to the register <b>2004</b> while switching the input direction between the x axis direction and the y axis direction alternately. For example, five plane data pieces are input in the y axis direction, and then five sheet data pieces are input in the x axis direction.

<figref idref="DRAWINGS">FIG. 19</figref> is a diagram illustrating an implementation example of the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b>. The θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> calculates output data pieces using θ intermediate values that the circuit <b>2008</b> has previously calculated for a target plane. Since the processing includes the processing in the step π, output data pieces has the sheet structure.

As described above, the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> receives input of one plane data piece at every clock as an input data piece <b>2201</b>. An input data piece <b>2202</b> is input from the θ<b>1</b> circuit <b>2008</b> and corresponds to a θ intermediate value.

The processing of an exclusive OR (XOR) operator <b>2203</b> corresponds to the operation of the step θ<b>2</b> as described above. A logic circuit (ρ circuit) <b>2204</b> performs the operation of the step ρ. A logic circuit (π circuit) <b>2205</b> performs the operation of the step π and can output one sheet from input of one plane. An output data piece <b>2206</b> is one sheet data piece that is output at every clock.

<figref idref="DRAWINGS">FIG. 25</figref> is a diagram illustrating an implementation example of the π circuit <b>2205</b>. As described above, the π circuit <b>2205</b> receives input of one plane data piece at every clock as an input data piece <b>2601</b>. A combination circuit <b>2602</b> divides one plane data piece that is the input data piece <b>2601</b> into five lane data pieces and outputs the five lane data pieces.

A combination circuit <b>2603</b> rearranges in the step π. The combination circuit <b>2603</b> rearranges five lane data pieces aligned in the x axis direction to five lane data pieces aligned in the y axis direction according to the table of <figref idref="DRAWINGS">FIG. 5B</figref> and outputs the five lane data pieces.

A combination circuit <b>2604</b> outputs five lane data pieces as one sheet data piece. An output data piece <b>2605</b> is one sheet data piece at every clock.

<figref idref="DRAWINGS">FIG. 20</figref> is a diagram illustrating an implementation example of the χ &amp; <img file="US9973336B2_D0034.tif" /> circuit <b>2006</b>. The χ &amp; <img file="US9973336B2_D0035.tif" /> circuit <b>2006</b> calculates an output data piece by using a target sheet data piece and two sheet data pieces at positions of +1 and +2 in the x axis direction from the target sheet data piece.

As described above, the χ &amp; <img file="US9973336B2_D0036.tif" /> circuit <b>2006</b> receives input of one sheet data piece at every clock as an input data piece <b>2301</b>. A multiplexer <b>2302</b> outputs the input data piece <b>2301</b> as is during the first five clocks from the start of the processing and outputs data from a register <b>2304</b> during the following two clocks.

A register <b>2303</b> having a two-stage configuration stores information of one sheet in one stage. The register <b>2304</b> having a two-stage configuration stores information of one sheet in one stage. The register <b>2304</b> stores information of sheets at x=0 and x=1.

A combination circuit <b>2305</b> is a logic circuit configured to perform the operations of the above steps χ and <img file="US9973336B2_D0037.tif" />. An output data piece <b>2306</b> of one sheet is output as a unit.

As described above, the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> is for the processing in units of planes, and the χ &amp; <img file="US9973336B2_D0038.tif" /> circuit <b>2006</b> is for the processing in units of sheets. Thus, on the path from the output of the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> to the input of the χ &amp; <img file="US9973336B2_D0039.tif" /> circuit <b>2006</b>, only a combination circuit is connected. More specifically, a latch circuit is not included on the path. Therefore, a data piece can pass through the path within one clock.

As described above, according to the first exemplary embodiment, the π processing unit <b>805</b> receives input of a plane and outputs a sheet, and processing in a round is performed using a plane and a sheet as units. Thus, the processing in the round can be pipelined.

In addition, as described above, according to the first exemplary embodiment, a unit of input processing at the start of a round is the plane, and a unit of output processing at the end of a round is the sheet. However, since plane-sheet unit conversion is performed from the input to the output of the register <b>2004</b>, the unit of input processing can be units of planes at the start of a next round.

Note that, an input unit to the θ<b>1</b> circuit <b>2008</b> is the sheet structure in the first exemplary embodiment, but the input unit may be the plane structure. In that case, after receiving five plane data pieces, the θ<b>1</b> circuit <b>2008</b> outputs θ intermediate values of five times sixty-four bits. However, when the input unit to the θ<b>1</b> circuit <b>2008</b> is the sheet structure, the θ<b>1</b> circuit <b>2008</b> can sequentially calculate a θ intermediate value at every input, which is an advantageous effect.

<figref idref="DRAWINGS">FIG. 14A</figref> is an operation timing chart of the respective modules of the implementation example according to the first exemplary embodiment. The θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> and the χ &amp; <img file="US9973336B2_D0040.tif" /> circuit <b>2006</b> are configured for pipeline processing. Since the θ<b>1</b> circuit <b>2008</b> can calculate a θ intermediate value from input of five sheet data pieces, it takes five clocks. Two clocks after the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> outputs one sheet data piece, the χ &amp; <img file="US9973336B2_D0041.tif" /> circuit <b>2006</b> can output one sheet data piece. That is, the χ &amp; <img file="US9973336B2_D0042.tif" /> circuit <b>2006</b> can start the processing upon receiving three sheet data pieces. Thus, the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> and the χ &amp; <img file="US9973336B2_D0043.tif" /> circuit <b>2006</b> can operate in parallel. In addition, it takes seven 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 specifications will be described for comparison with the implementation example of the above first exemplary embodiment.

<figref idref="DRAWINGS">FIG. 15</figref> is 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 <img file="US9973336B2_D0044.tif" />) is similar to that described above, and thus the description thereof is not provided.

The KECCAK-f receives one lane data piece (data having a length of sixty-four bits) from an input data piece <b>1801</b> at every clock. The KECCAK-f receives lane data pieces in one state data piece in the order illustrated in <figref idref="DRAWINGS">FIG. 2F</figref>.

An Exclusive OR processing unit <b>1802</b> is an operator that calculates exclusive OR of a message block and an internal data piece every time when the round processing is performed twenty-four times.

A register <b>1803</b> holds the whole of the internal data expressed as a state data piece. A processing block (π circuit) <b>1804</b> performs 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) <b>1805</b> performs the step θ, and a processing block (ρ circuit) <b>1806</b> performs the step ρ.

A processing block (χ circuit) <b>1807</b> performs the step χ, and a processing block (<img file="US9973336B2_D0045.tif" /> circuit) <b>1808</b> performs the step <img file="US9973336B2_D0046.tif" />. A multiplexer <b>1809</b> outputs data having been input from the processing block <b>1806</b> in the first half of round processing and outputs data from the processing block <b>1808</b> in the second half thereof. The KECCAK-f outputs an output data piece <b>1810</b> of one lane when calculation is completed.

<figref idref="DRAWINGS">FIG. 14B</figref> is an operation 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 θ circuit <b>1805</b> and the p circuit <b>1806</b> and a pair of the χ circuit <b>1807</b> and the <img file="US9973336B2_D0047.tif" /> circuit <b>1808</b> operate 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 of <figref idref="DRAWINGS">FIG. 14A</figref> and FIG. <b>14</b>C, 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. <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0120">The two processing circuits: the θ<b>2</b> &amp; ρ &amp; π circuit <b>2005</b> and the χ &amp; <img file="US9973336B2_D0048.tif" /> circuit <b>2006</b> operate in parallel, and thus utilization efficiency of the circuits can be improved.</li><li id="ul0006-0002" num="0121">One-time round processing can be performed within a smaller number of clocks (less time).</li></ul></li></ul>

As a hash value generating device according to a second 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 values. The KECCAK algorithm and the data structures are similar to those of the first exemplary embodiment, and thus, points different from the first exemplary embodiment will be described.

Round processing R′ <b>901</b> will be described. The round processing R′ <b>901</b> is processing used in the present embodiment and designed such that the result is the same as that of the round processing R <b>201</b>. However, processing contents of the round processing R′ <b>901</b> are different from the specifications of the KECCAK algorithm.

<figref idref="DRAWINGS">FIG. 9B</figref> is a diagram illustrating an overview of the round processing R′ <b>901</b>. The round processing R′ <b>901</b> is designed such that the processing result is the same as that of the round processing R <b>201</b>. In the round processing R′ <b>901</b>, processing of six steps is performed (by a θ<b>1</b> processing unit <b>902</b>, a π processing unit <b>903</b>, a θ<b>2</b>′ processing unit <b>904</b>, a ρ′ processing unit <b>905</b>, a χ processing unit <b>906</b>, and an <img file="US9973336B2_D0049.tif" /> processing unit <b>907</b>) on an input data piece to generate an output data piece.

Note that, the π processing unit <b>903</b>, the χ processing unit <b>906</b>, and the <img file="US9973336B2_D0050.tif" /> processing unit <b>907</b> performs processing similar to those performed by the π processing unit <b>303</b>, the χ processing unit <b>304</b>, and the <img file="US9973336B2_D0051.tif" /> processing unit <b>305</b> of the round processing R <b>201</b>. The ρ′ processing unit <b>905</b> performs processing of shifting values of respective bits in the z axis direction similarly to the ρ processing unit <b>302</b> of the round processing R <b>201</b>, but the number of bits by which the values are shifted is different. The θ<b>1</b> processing unit <b>902</b> and the θ<b>2</b>′ processing unit <b>904</b> are obtained by dividing the θ processing unit <b>301</b> in the round processing R <b>201</b>.

Since the χ processing and the <img file="US9973336B2_D0052.tif" /> processing in the round processing R′ <b>901</b> are similar to those in the round processing R <b>201</b>, the description thereof is not provided.

The π processing unit <b>903</b> is similar to the π processing unit <b>303</b> in the round processing R <b>201</b>. However, the π processing unit <b>903</b> does not perform the processing after a state data piece is held, but receives a plane data piece and then outputs a sheet data piece. The detail is similar to the first exemplary embodiment.

The θ<b>1</b> processing of the round processing R′ <b>901</b> is similar to the θ<b>1</b> processing of the round processing R′ <b>801</b>, and thus the description thereof is not provided. The ρ′ processing and the θ<b>2</b>′ processing will be described below.

<figref idref="DRAWINGS">FIG. 10A</figref> is a diagram illustrating processing in the step ρ′ (ρ′ processing unit <b>905</b>). In the step ρ′, the ρ′ processing unit <b>905</b> performs 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 in <figref idref="DRAWINGS">FIG. 10B</figref>. Note that, in order to perform the ρ′ processing, a holding section previously holds a table listing shifting amounts as illustrated in <figref idref="DRAWINGS">FIG. 10C</figref> and the ρ′ processing unit <b>905</b> performs 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′ <b>901</b> and that of the round processing R <b>201</b> are the same, first, there will be described that the processing result of the round processing R <b>201</b> and the processing result of round processing R″ <b>911</b> are the same.

<figref idref="DRAWINGS">FIG. 9C</figref> is a diagram of the round processing R″ <b>911</b>. In the round processing R″ <b>911</b>, processing of five steps is performed (by a θ processing unit <b>912</b>, a π processing unit <b>913</b>, a ρ′ processing unit <b>915</b>, a χ processing unit <b>916</b>, and an <img file="US9973336B2_D0053.tif" /> processing unit <b>917</b>) on the input data piece to generate an output data piece. Here, the θ processing unit <b>912</b>, the π processing unit <b>913</b>, the χ processing unit <b>916</b>, and the <img file="US9973336B2_D0054.tif" /> processing unit <b>917</b> are respectively similar to the θ processing unit <b>301</b>, the π processing unit <b>303</b>, the χ processing unit <b>304</b>, and the <img file="US9973336B2_D0055.tif" /> processing unit <b>305</b> of the round processing R <b>201</b>. The ρ′ processing unit <b>915</b> is similar to the ρ′ processing unit <b>905</b> of the round processing R′ <b>901</b>.

When the round processing R <b>201</b> is compared with the round processing R″ <b>911</b>, they are different in a point that the π processing unit <b>913</b> and the ρ′ processing unit <b>915</b> perform the processing in this order in the round processing R″ <b>911</b> while the ρ processing unit <b>302</b> and the π processing unit <b>303</b> perform the processing in this order in the round processing R <b>201</b>.

Here, in the step ρ of the round processing R <b>201</b>, the ρ processing unit <b>302</b> shifts values in the z axis direction according to rules determined for respective lanes, and the n processing unit <b>303</b> rearranges the respective lanes. On the other hand, in the round processing R″ <b>911</b>, the π processing unit <b>913</b> rearranges the respective lanes (processing in the step π), and thereafter the ρ′ processing unit <b>915</b> shifts 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″ <b>911</b>, the step π is performed before the step ρ′, but the shifting amount by which values are shifted in the z axis direction by the ρ′ processing unit <b>915</b> is changed in consideration of the processing in the step π, whereby the processing result of the round processing R″ <b>911</b> becomes the same as that of the round processing R <b>201</b>.

<figref idref="DRAWINGS">FIG. 10C</figref> is a table listing shifting amounts for respective lanes used in the step ρ′.

A method of generating the table illustrated in <figref idref="DRAWINGS">FIG. 10C</figref> will be specifically described. First, the round processing R <b>201</b> will be considered. In the round processing R <b>201</b>, the ρ processing unit <b>302</b> and the π processing unit <b>303</b> perform the processing in this order. The numbers in <figref idref="DRAWINGS">FIG. 4B</figref> are 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 using <figref idref="DRAWINGS">FIGS. 5A and 5B</figref>. It can be seen that the n processing unit <b>303</b> moves the lane at the position of x=0 and y=4 to the position of x=4, y=2.

Next, the round processing R″ <b>911</b> will be considered. In the round processing R″ <b>911</b>, the π processing unit <b>913</b> and the ρ′ processing unit <b>915</b> perform the processing in this order. Since the π processing is performed before the ρ′ processing, a lane for which the ρ′ processing unit <b>915</b> should 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 in <figref idref="DRAWINGS">FIG. 10B</figref> is eighteen. Shifting amounts of the other lanes can be similarly obtained to be the other numbers in <figref idref="DRAWINGS">FIG. 10B</figref>.

That is, the table listing the shifting amounts for the respective lanes used in the step ρ′ illustrated in <figref idref="DRAWINGS">FIG. 10C</figref> is 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″ <b>911</b> is the same as that of the round processing R′ <b>901</b>.

Note that, the π processing unit <b>903</b>, the ρ′ processing unit <b>905</b>, the χ processing unit <b>906</b>, and the <img file="US9973336B2_D0056.tif" /> processing unit <b>907</b> respectively perform the processing similarly to the π processing unit <b>913</b>, the ρ′ processing unit <b>915</b>, the χ processing unit <b>916</b>, and the <img file="US9973336B2_D0057.tif" /> processing unit <b>917</b> of the round processing R″ <b>911</b>. The θ<b>1</b> processing unit <b>902</b> and the θ<b>2</b>′ processing unit <b>904</b> are obtained by dividing the θ processing unit <b>912</b>.

When the round processing R″ <b>911</b> is compared with the round processing R′ <b>901</b>, they are different in a point that the θ processing unit <b>912</b> and the π processing unit <b>913</b> perform the processing in this order in the round processing R″ <b>911</b> while the θ<b>1</b> processing unit <b>902</b>, the π processing unit <b>903</b>, and the θ<b>2</b>′ processing unit <b>904</b> perform the processing in this order in the round processing R′ <b>901</b>.

Here, in the round processing R″ <b>911</b>, 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′ <b>901</b>, the θ<b>1</b> processing unit <b>902</b> calculates the sum of two columns that are adjacent to each bit (processing in the step θ<b>1</b>). Then, the π processing unit <b>913</b> rearranges the respective lanes (processing in the step π), and the θ<b>2</b>′ processing unit <b>904</b> adds the sum of the columns to a bit in consideration of the rearrangement of the respective lanes (processing in the step θ<b>2</b>′).

<figref idref="DRAWINGS">FIG. 13A</figref> is a diagram illustrating processing in the step θ<b>2</b>′. The step θ<b>2</b>′ corresponds to the operation of the second half of the step θ and is a step of performing column sum addition processing. That is, the step θ<b>2</b>′ is a step of adding θ intermediate values calculated in the step θ<b>1</b> to the respective bits.

However, it should be noted that the step π has been already performed before the step θ<b>2</b>′. More specifically, in the step θ of the round processing R″ <b>911</b> (i.e., the step θ of the round processing R <b>201</b>), 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 θ<b>2</b>′ of the round processing R′ <b>901</b>, 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 in <figref idref="DRAWINGS">FIG. 13B</figref>. Note that, a holding section previously holds a table in <figref idref="DRAWINGS">FIG. 13C</figref> providing x coordinates of θ intermediate values used for calculation of respective bits in the θ<b>2</b>′ processing, and the θ<b>2</b>′ processing unit <b>904</b> performs the θ<b>2</b>′ processing using the table being held.

A method of generating the table illustrated in <figref idref="DRAWINGS">FIG. 13C</figref> will be specifically described. First, the round processing R″ <b>911</b> will 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 using <figref idref="DRAWINGS">FIGS. 5A and 5B</figref>. It can be seen that the π processing unit <b>913</b> moves the bit at the position of x=0, y=4 to the position of x=4, y=2.

Next, the round processing R′ <b>901</b> will be considered. Since the π processing unit <b>903</b> has already performed the step π when the θ<b>2</b>′ processing unit <b>904</b> performs the step θ<b>2</b>′, 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 θ<b>2</b>′ is x=0. Therefore, a number at the position of x=4, y=2 out of the numbers provided in <figref idref="DRAWINGS">FIG. 13B</figref> becomes zero. The x coordinates of θ intermediate values for other bits can be similarly obtained to be the other numbers in <figref idref="DRAWINGS">FIG. 13B</figref>.

That is, the table in <figref idref="DRAWINGS">FIG. 13C</figref> providing the x coordinates of θ intermediate values when the θ<b>2</b>′ processing unit <b>904</b> performs the step θ<b>2</b>′ is a table determined in consideration of the rearrangement processing of the π processing.

As described above, the processing result of the round processing R <b>201</b> and that of the round processing R″ <b>911</b> are the same. In addition, the processing result of the round processing R″ <b>911</b> and the processing result of the round processing R′ <b>901</b> are the same. Therefore, the processing result of the round processing R′ <b>901</b> and the processing result of the round processing R <b>201</b> are the same.

From the processing contents of the above respective steps (steps θ<b>1</b>, θ<b>2</b>′, and ρ′), it can be understood that there are following limitations regarding start of the processing of the respective steps. <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0149">In the step θ<b>1</b>, the θ<b>1</b> processing unit <b>902</b> calculates the sum, and thus, the θ<b>1</b> processing unit <b>902</b> updates a θ intermediate value in the process of calculation every time when each plane in the state is input. Therefore, when one plane data piece of calculation results of the preceding stage is output, the θ<b>1</b> processing unit <b>902</b> can start the processing in the step θ<b>1</b>.</li><li id="ul0008-0002" num="0150">In the step θ<b>2</b>′, the θ<b>2</b>′ processing unit <b>904</b> adds a θ intermediate value calculated in the step θ<b>1</b> in calculation of each plane in the state. Since the step θ<b>1</b> has been completed at the time of starting the step θ<b>2</b>′, the θ<b>2</b>′ processing unit <b>904</b> can start to output the processing result of the step θ<b>2</b>′ when one plane data piece of calculation results of the preceding stage (step π) is output.</li><li id="ul0008-0003" num="0151">The step ρ′ is calculation for each of lanes independent of each other. Therefore, when the θ<b>2</b>′ processing unit <b>904</b> outputs one plane data piece of calculation results of the preceding stage (step θ<b>2</b>′), the ρ′ processing unit <b>905</b> can start the processing in the step ρ′.</li></ul></li></ul>

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

In addition, the processing contents of the steps n, χ, and <img file="US9973336B2_D0058.tif" /> of the second exemplary embodiment are the same as those described in the first exemplary embodiment. Thus, it can be understood that there are following limitations regarding start of the processing of the respective steps. <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0154">In the step π, respective lanes in a state are rearranged. However, the π processing unit <b>903</b> can output one sheet data piece from input of one plane data piece. Therefore, when the preceding stage (step θ<b>1</b>) outputs one plane of calculation results, the π processing unit <b>903</b> can start the processing in the step π.</li><li id="ul0010-0002" num="0155">In the step χ, in calculation of each lane in a state, the x processing unit <b>906</b> uses a lane at +1 and a lane at +2 in the x axis direction. Therefore, when the ρ′ processing unit <b>905</b> outputs one plane data piece of calculation results of the preceding stage (step ρ′), the χ processing unit <b>906</b> can start the processing in the step χ.</li><li id="ul0010-0003" num="0156">The step <img file="US9973336B2_D0059.tif" /> is calculation for each of lanes independent of each other. Therefore, when one plane data piece of calculation results of the preceding stage (step χ) is output, the <img file="US9973336B2_D0060.tif" /> processing unit <b>907</b> can start the processing in the step <img file="US9973336B2_D0061.tif" />.</li></ul></li></ul>

Since a plane data piece is input and a sheet data piece is output in the step π, the need of holding a state data piece can be eliminated and throughput can be improved.

In addition, the π processing unit <b>903</b> performs processing in units of planes, and the round processing R′ <b>901</b> is used instead of the round processing R <b>201</b>. Therefore, throughput can be improved. Hereinafter, a configuration in which plane data pieces are input to the step π and sheet data pieces are output therefrom, and the round processing is performed in units of planes will be described.

<figref idref="DRAWINGS">FIG. 21</figref> is a diagram illustrating a configuration of an implementation example of the KECCAK algorithm according to the second exemplary embodiment. Here, the order of input data pieces <b>2401</b> is previously determined to be sequential in the x direction: (x, y)=(0, 0), (1, 0), (2, 0), . . . . A register <b>2409</b> holds four lane structure data pieces that are the input data pieces <b>2401</b> and outputs a plane structure data piece as a unit when the register <b>2409</b> receives the fifth lane structure data piece. Note that, the register <b>2409</b> may be configured to output the first plane structure data piece when the register <b>2409</b> holds data enabling generation of at least the first plane structure data piece. When calculation is completed, an output data piece <b>2410</b> is output in units of the sheet structures.

A multiplexer <b>2402</b> outputs an input data piece as is when the multiplexer <b>2402</b> calculates exclusive OR of the input data piece and the internal state and outputs zero in other cases.

A circuit <b>2404</b> calculates in the step π (hereinafter, referred to as a π circuit <b>2404</b>). The π circuit <b>2404</b> receives input of a plane structure data piece and outputs a sheet structure data piece similarly to the π circuit <b>2205</b> illustrated in <figref idref="DRAWINGS">FIG. 19</figref>. More specifically, plane structure data pieces are input in ascending order of the y coordinate (in the order of y=0, 1, 2, 3, and 4), and outputs sheet structure data pieces in ascending order of the x coordinate (in the order of x=0, 1, 2, 3, and 4).

A register <b>2405</b> holds the whole of the internal data. Since the register <b>2405</b> is similar to the register <b>2004</b> of the first exemplary embodiment, the description thereof is not provided.

A circuit <b>2406</b> performs calculation in the steps θ<b>2</b>′, p′, χ, and <img file="US9973336B2_D0062.tif" /> (hereinafter, referred to as a θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0063.tif" /> circuit <b>2406</b>) and outputs one plane structure data piece of the calculation results as a unit. A multiplexer <b>2407</b> outputs zero upon start of calculation of a hash value for initialization and outputs data in the process of calculation in other cases.

A circuit <b>2408</b> is for the processing in the step θ<b>1</b> (hereinafter, referred to as a θ<b>1</b> circuit <b>2408</b>) and outputs an intermediate value (θ intermediate value) of five times sixty-four bits when the circuit <b>2408</b> receives five plane data pieces.

<figref idref="DRAWINGS">FIG. 22</figref> is a diagram illustrating an implementation example of the θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0064.tif" /> circuit <b>2406</b>. The θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0065.tif" /> circuit <b>2406</b> calculates output data pieces using θ intermediate values that the circuit <b>2408</b> has previously calculated for a target plane.

The θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0066.tif" /> circuit <b>2406</b> receives input of one plane data piece at every clock as an input data piece <b>2501</b>. An input data piece <b>2502</b> is input from the θ<b>1</b> circuit <b>2408</b>, and corresponds to θ intermediate values.

The processing by an exclusive OR (XOR) operator <b>2503</b> corresponds to the operation of the step θ<b>2</b>′ described above. A combination circuit <b>2504</b> is a logic circuit configured to actually perform the operations of the above steps ρ′, χ, and <img file="US9973336B2_D0067.tif" /> and to outputs one plane data piece at every clock. An output data piece <b>2505</b> is one plane data piece that is output at every clock.

As described above, the π circuit <b>2404</b> performs processing in units of planes and outputs a sheet structure data piece, the register <b>2405</b> converts the sheet structure data piece to a plane structure, and the θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0068.tif" /> circuit <b>2406</b> performs processing in units of planes. On the path from the output of the θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0069.tif" /> circuit <b>2406</b> and to the input of the π circuit <b>2404</b>, only a combination circuit is connected. More specifically, a latch circuit is not included on the path. Therefore, a data piece can pass through the path within one clock.

Note that, an input unit to the θ<b>1</b> circuit <b>2408</b> is the plane structure in the second exemplary embodiment, but the input unit may be the sheet structure. In that case, after receiving input of five sheet data pieces, the θ<b>1</b> circuit <b>2408</b> outputs θ intermediate values of five times sixty-four bits.

<figref idref="DRAWINGS">FIG. 14B</figref> is an operation timing chart of the respective modules of the implementation example according to the second exemplary embodiment. The output from the θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0070.tif" /> circuit <b>2406</b> to the π circuit <b>2404</b> is configured for pipeline processing. The processing of each of the all steps in the round processing can be started when one plane data piece is input. That is, all steps in the round processing can be performed in parallel. In addition, it takes five 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 specifications will be described for comparison with the implementation example of the above second exemplary embodiment. The implementation example in which processing is performed on a lane data piece as a unit by the algorithm according to the specifications is similar to the contents described in the first exemplary embodiment, and thus the description thereof is not provided.

<figref idref="DRAWINGS">FIG. 14C</figref> is an operation timing chart of the respective modules of the implementation example in which processing is performed on a lane data piece as a unit according to specifications.

As can be seen from comparison of <figref idref="DRAWINGS">FIG. 14B</figref> and <figref idref="DRAWINGS">FIG. 14C</figref>, throughput of the processing can be improved by using the configuration of the implementation example according to the second exemplary embodiment.

More specifically, the followings can be said. <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0000"><ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0175">The two processing circuits: the π circuit <b>2404</b> and the θ<b>2</b>′ &amp; ρ′ &amp; χ &amp; <img file="US9973336B2_D0071.tif" /> circuit <b>2406</b> operate in parallel, and thus utilization efficiency of the circuits can be improved.</li><li id="ul0012-0002" num="0176">One-time round processing can be performed within a smaller number of clocks (less time).</li></ul></li></ul>

As described above in the present embodiment, the conversion of processing unit during the θ<b>1</b> processing can reduce time for holding data.

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

Embodiments of the present invention can also be realized by a computer of a system or apparatus that reads out and executes computer executable instructions recorded on a storage medium (e.g., non-transitory computer-readable storage medium) to perform the functions of one or more of the above-described embodiment (s) of the present invention, and by a method performed by the computer of the system or apparatus by, for example, reading out and executing the computer executable instructions from the storage medium to perform the functions of one or more of the above-described embodiment(s). The computer may comprise one or more of a central processing unit (CPU), micro processing unit (MPU), or other circuitry, and may include a network of separate computers or separate computer processors. The computer executable instructions may be provided to the computer, for example, from a network or the storage medium. The storage medium may include, for example, one or more of a hard disk, a random-access memory (RAM), a read only memory (ROM), a storage of distributed computing systems, an optical disk (such as a compact disc (CD), digital versatile disc (DVD), or Blu-ray Disc (BD)™), a flash memory device, a memory card, and the like.

While the present invention has been described with reference to exemplary embodiments, it is to be understood that the invention is not limited to the disclosed exemplary embodiments. The scope of the following claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.

This application claims the benefit of Japanese Patent Applications No. 2013-045574 filed Mar. 7, 2013 and No. 2014-017413 filed Jan. 31, 2014, which are hereby incorporated by reference herein in their entirety.