JP2010044251A - Hash value generator, program and hash value generation method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a hash function capable of evaluating safety.
A message blocking unit 122 divides an input message into a plurality of message blocks, and uses a round constant generated by a round constant generating unit 123 to use a first round key generating unit 124 or a second round. Using the round key generated by the key generation unit 125, the stirring unit 126 performs stirring using a block cipher for each message block. In the block cipher, specific divided data among a plurality of divided data obtained by dividing a message block is converted by the F function, and an exclusive OR with other specific divided data is calculated. In the F function, conversion including at least nonlinear conversion is performed a plurality of times.
[Selection] Figure 1

Description

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

  The hash function is a function that generates a hash value having a specific length by inputting an arbitrary length message.

  Generally, a hash function consists of a block cipher that inputs a fixed-length message block. By repeatedly performing block encryption on the input message, the message is agitated and finally output as a hash value. To do. Typical examples of the hash function include SHA-1 or SHA-2 hash family such as SHA-256 (see Non-Patent Document 1).

NIST FIPS 180-2, “Secure Hash Standard”, 2002 August 1, pp. 9-23, http://csrc.nist.gov/publications /fips/fips180-2/fips180-2.pdf

  SHA-1 described in Non-Patent Document 1 is known to have a problem in collision resistance, which is a security that the hash function should have, and the SHA-2 hash family also has a structure similar to SHA-1. For this reason, there is a possibility of causing a problem in the security that the hash function should have.

  Therefore, an object of the present invention is to provide a hash function that can be evaluated for security.

  In order to solve the above problems, the present invention generates a hash value by using a block cipher having an F function that performs nonlinear transformation a plurality of times.

  For example, according to the present invention, a message is converted into a block having a predetermined data length, specific divided data among a plurality of divided data obtained by dividing the block is converted by the F function, and other specific divided data and A hash value generation device that generates a hash value of the message using a block cipher that includes an agitation process that calculates an exclusive OR of the control, and performs a plurality of conversions including at least nonlinear conversion in the F function It is characterized by providing a part.

  As described above, according to the present invention, it is possible to provide a hash function that can be evaluated for safety.

  FIG. 1 is a schematic diagram of a hash value generation device 100 according to the first embodiment of the present invention.

  Here, in this embodiment, a 512-bit hash value is generated.

  As illustrated, the hash value generation device 100 includes a storage unit 110, a control unit 120, an input unit 130, and an output unit 140.

  The storage unit 110 includes an initial value storage area 111, a constant round value storage area 112, a key round value storage area 113, a plaintext round value storage area 114, a calculated value storage area 115, a hash value storage area 116, Is provided.

  The initial value storage area 111 stores information for specifying an initial value when generating a hash value.

  In the present embodiment, an initial value of a constant round value and an initial value of a calculated value are stored as initial values when generating a hash value.

Here, as the initial value of the constant round value, for example, a constant such as c ⁽⁻¹⁾ = 0xffffffffffffffffffffffffffffffff is stored.

The initial value of the calculated value is H ₋₁ = (H _−1.0 , H _−1.1 ,..., H _−1.7 ), and H _−1.0 = 0x0000000000000000, H _{−1. .1} = 0x0000000000000000, H- _1.2 = 0x0000000000000000, H- _1.3 = 0x0000000000000000, H- _1.4 = 0x0000000000000000, H- _1.5 = 0x0000000000000000, H- _1.6 = 0x0000000000000000, H- _1.7 = 0x0000000000000000 and other constants are stored.

  The constants used for the constant round value and the initial value of the calculated value are not limited to these. For example, a random number generated by a pseudo-random number generator or the like can be used.

  The constant round value storage area 112 stores information for specifying a constant round value for each round in each message block.

  In the present embodiment, the constant round value is generated by the round constant generation unit 123 described later.

  The key round value storage area 113 stores information for specifying a key round value for each round in each message block.

  In the present embodiment, the key round value is generated by a first round key generation unit 124 or a second round key generation unit 125 described later.

  The plaintext round value storage area 114 stores information for specifying a plaintext round value for each round in each message block.

  In the present embodiment, the plaintext round value is generated by the stirring unit 126 described later.

  The calculated value storage area 115 stores information for specifying a calculated value calculated through all rounds in each message block.

  In the present embodiment, the calculated value is generated by the overall control unit 121 described later.

  In the hash value storage area, information specifying hash values calculated through all rounds in all message blocks is stored.

  In the present embodiment, the hash value is generated by the overall control unit 121 described later.

  The control unit 120 includes an overall control unit 121, a message blocking unit 122, a round constant generation unit 123, a first round key generation unit 124, a second round key generation unit 125, and a stirring unit 126. .

  The overall control unit 121 controls the overall processing in the hash value generation device 100.

  In particular, in the present embodiment, a process for managing a message block obtained by blocking a message for calculating a hash value, a round constant generation unit 123, a first round key generation unit 124, a second round key generation unit 125, and a stirring unit The process of managing the round at 126 is performed.

  In addition, the overall control unit 121 calculates the exclusive OR of the plaintext round value calculated in the stirring unit 126 through all rounds and the message block subjected to processing in the round, Calculate the calculated value.

  Further, the overall control unit 121 calculates the exclusive OR of the plaintext round value calculated in the agitation unit 126 through all message blocks and all rounds, and the last message block, thereby calculating the hash value. calculate.

  The message blocking unit 122 divides a message for which a hash value is calculated into blocks having a predetermined bit length and performs padding.

  Here, in this embodiment, the message for which the hash value is calculated is divided into 512-bit blocks. However, the present invention is not limited to this mode.

  Further, for example, padding in the present embodiment is performed as follows.

  First, when the number of bits of a message whose hash value is calculated is divisible by 512 bits, the message blocking unit 122 generates each message block by dividing the message into 512 bits. The message block is added as the last message block.

  Then, in this last message block, the message blocking unit 122 sets “1” as the first bit, “0” up to 383 bits from the next bit of the first bit, bit length of the message as the last 128 bits, Stores information that identifies

  Next, if the number of bits of the message for which the hash value is calculated cannot be divided by 512 bits, the message blocking unit 122 generates each message block by dividing the message into 512 bits. At the same time, the information specifying “0” up to the last bit is stored in the last message block divided to 512 bits, and a message block is further added to form the last message block.

  Then, the message blocking unit 122 stores information specifying “0” up to 384 bits counted from the first bit and the bit length of the message in the last 128 bits in this last message block.

In the present embodiment, a message for calculating a hash value is M, a message that has a bit length divisible by 512 bits by padding is M ′, and the number of message blocks is k + 1 (k is 1 or more). Integer), and each message block is M ′ _i (i is an integer satisfying 0 ≦ i ≦ k).

  The round constant generation unit 123 calculates a constant round value and a round constant in each round.

In the present embodiment, the round constant generation unit 123 determines the constant round from the initial value of the constant round value stored in the initial value storage area 111 in the case of the first round, or in the case of not the first round. from the constant round value before the round stored in the value storage area 112, using a linear transformation function f _c, calculates a constant round value in each round.

For example, as shown in FIG. 2 (a schematic showing a linear transformation function _{f c} Figure), the round-constant generation unit 123, the previous round (r-1) constant round value ^{c (r-1)} (for r = 0 in the upper bits (the embodiment of the values that the initial value) was calculated by entering the function f _L constant round value is in the upper 64 bits) and lower bits (the embodiment, by replacing the lower 64 bits) Thus, the constant round value c ^(r) of the current round ( ^r) is calculated.

That is, as shown in the following equations (1) and (2), the current round is calculated from the constant round value c ^{(r−1) of} the previous round ⁽ the initial value of the constant round value when r = 0). A constant round value c ^{(r) of} is calculated.

Here, in Expressions (1) and (2), t _H and t _L are constant round values c ^(r−1) (initial values of constant round values when r = 0 ⁾ , respectively, and function f _These are the upper and lower bits of the value calculated by inputting to _L.

The function f _L uses a linear feedback shift register (LFSR).

  In general, the LFSR is determined by a polynomial. Here, a polynomial g (x) for determining the LFSR is defined as the following equation (3).

  However, g (x) is a polynomial defined in the finite field GF (2).

Incidentally, the pseudo-code for the function f _L is expressed by the following (4).

Here, “<< X” indicates a left shift of X bits, “>> Y” indicates a right shift of Y bits, “^” indicates an exclusive OR for each bit, and “&” "Represents a logical product for each bit, and" | "represents a logical sum for each bit. Further, h is upper bits of the constant round value ^{c (r-1) (upper} 64 bits), l is the lower-order bits of the constant round value ^{c (r-1) (low-order} 64 bits).

Then, the round constant generation unit 123 sets the lower 64 bits of the constant round value c ^{(r) in} the calculated round (r) as the round constant C ^(r) in the r-th round, or the first round key generation unit 124 or Output to the second round key generation unit 125.

An example of C ^(r) in the case of R = 96 is given below.

C ⁽⁰⁾ = 0x9916b42b1075d3c4, C ⁽¹⁾ = 0xef660b4c6b97a9a1, C ⁽²⁾ = 0x645ad0ac41d74f11, C ⁽³⁾ = 0xdb7166e541d48abf, C ⁽⁴⁾ = 0x81f2b60293356a19, 0 ⁽ e ^{) (7) = 0x5ac3fe60d882617f, C (} 8) = 0xd670690748b71e50, C (9) = 0x0de6b2578d83a9c6, C (10) = 0x495850aeb6b42f1c, C (11) = 0x379ac95e360ea718, C (12) = 0x4388096e355a904b, C (13) = 0xa81b9a1fa3d8e607, C ( ^{14) = 0x1eb9d10b41021771, C (15} ) = 0xa06e687e8f63981c, C (16) = 0x7ae7442d04085dc5, C (17) = 0x81b9a1fa3d8e6070, C (18) = 0x8d745b60ffab5b2e, C (19) = 0x7096388f8ddbfba6, C (20) = 0x43a1d2e4854f16df, C (21 ^{) = 0xd2c1168da307b8c4, C (22)} = 0x686e0046fab67746, C (23) = 0x5b9dae851876b54c, C (24) = 0xc7514acf0553f123, C ^{25) = 0x7eef4ea7f5b2836d, C (26} ) = 0x7bac60e8fac5e8b7, C (27) = 0xeb24ce2c42a25be8, C (28) = 0x8858c877049d8ee6, C (29) = 0xbc0acc029ee139fd, C (30) = 0x216321dc12763b99, C (31) = 0xf02b300a7b84e7f4, C (32 ^{) = 0x858c877049d8ee65, C (33)} = 0xa6458bfd0199b3ea, C (34) = 0x6042a2a65c81c3f2, C (35) = 0xef6690937d84b5cf, C (36) = 0x91937e2ae66f5995, C (37) = 0xdb7309991998fb06, C (38) = 0x303d47cce25f1c32, C (39) ^{= 0x7d55d2d7f20bba44, C (40) =} 0xc0f51f33897c70c8, C (41) = 0x93be008b27a4c52a, C (42) = 0x134d887db199957d, C (43) = 0x4ef8022c9e9314a8, C (44) = 0x4d3621f6c66655f4, C (45) = 0x5d09436695c67e9b, C (46) = 0x244173688df1018c, C ⁽⁴⁷⁾ = 0x12cc464eb893d657, C ⁽⁴⁸⁾ = 0xe77572c54c267c57, C ⁽⁴⁹⁾ = 0 ^{x3d41a65d99ad233a, C (50) = 0x8d4c3fa6a4f1a700} , C (51) = 0xf506997666b48ce9, C (52) = 0x3530fe9a93c69c01, C (53) = 0xb2f32e0d75581f9f, C (54) = 0xa2b3450d34f80a62, C (55) = 0xbdbc0752ae82041a, C (56) = 0xfcbdab53a80253ee ^{, C (57) = 0x8080a22dc1ea6a0e,} C (58) = 0xe26f59fd346119e5, C (59) = 0x020288b707a9a839, C (60) = 0xef542c203e0e4baf, C (61) = 0x7e7a9dbb6544da82, C (62) = 0xadc944336c5178e0, C (63) = 0x9f033d397a994632, ^{C (64) = 0xc155afaacaa799e6, C} (65) = 0x0a7c4b82918762ae, C (66) = 0x15cf4a18bef631c4, C (67) = 0x29f12e0a461d8ab8, C (68) = 0x573d2862fbd8c710, C (69) = 0xa7c4b82918762ae0, C (70) = 0x3a1dea5f00e9307a, C ⁽⁷¹⁾ = 0xe9625fc31a3ad1e7, C ⁽⁷²⁾ = 0x9e07161b7846bb8e, C ⁽⁷³⁾ = 0xb5108bbffc8311c 1, C ⁽⁷⁴⁾ = 0x781c586de11aee39, C ⁽⁷⁵⁾ = 0xd4422efff20c4704, C ⁽⁷⁶⁾ = 0x86982a636be194de, C ⁽⁷⁷⁾ = 0x41914f4c5c594a4d, C ^{(78 )} = 0x1a60a98daf865378, C ^{(80) , C (81) = 0x92282f25efd44260,} C (82) = 0x7fc8654717ecde1d, C (83) = 0x48a0bc97bf510980, C (84) = 0x99c8dec8b039544f, C (85) = 0x321b06ed692c705d, C (86) = 0x67237b22c0e5513c, C (87) = 0xc86c1bb5a4b1c174, ^{C (88) = 0xfa64a75fec1f68ca, C} (89) = 0x31299a6506af538d, C (90) = 0x8f7bd6ab5ff78f13, C (91) = 0xb2d6d6f3615f3452, C (92) = 0x4b9fe5ca043c462a, C (93) = 0xbd2be4aafe9eab2f, C (94) = 0x3ee6639b84994ef5, C ⁽⁹⁵⁾ = 0xf4af92abfa7aacbc.

  The first round key generation unit 124 performs processing for calculating a key round value and a round key in each round.

For example, the calculation of the key round value by the first round key generation unit 124 is performed using the first key round value conversion function f _k shown in FIG. 3 (schematic diagram of the first key round value conversion function f _k ).

As shown in the figure, the first key round value conversion function f _k is stored in the calculated value storage area 115 when the key round value k ^{(r−1) of the} ( ^r−1) -th round (where r = 0 ^). Calculated values or the initial values of the calculated values stored in the initial value storage area 111) are divided into eight divided data (here, 64 bits each) k ₀ ^(r−1) and k ₁ ^{(r -1)} , k ₂ ^(r-1) , k ₃ ^(r-1) , k ₄ ^(r-1) , k ₅ ^(r-1) , k ₆ ^(r-1) , k ₇ ^{(r-1) )} , K ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ ^(r) , k ₆ ^(r) , k ₇ ⁽ converted to ^r), by connecting the converted these values is a function of generating a key round value k ^(r) of the r rounds.

Specifically, in the first key round value conversion function f _k , first, the first round key generation unit 124 stores the key round value of the (r−1) -th round stored in the key round value storage area 113 (however, In the case of r = 0, the calculated value stored in the calculated value storage area 115 or the initial value of the calculated value stored in the initial value storage area 111) is expressed as k ₀ ^(r−1) , k _{1. ^{(r-1), k 2}} (r-1), k 3 (r-1), k 4 (r-1), k 5 (r-1), k 6 (r-1), k 7 (r ^-1) is divided into 8 equal parts.

Next, the first round key generation unit 124 includes k ₀ ^(r−1) , k ₁ ^(r−1) , k ₂ ^(r−1) , k _{3 in} the key round values of the ^(r−1) -th round. ^(R−1) and k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , and k ₅ ^(r) in the r-th round key round values, respectively.

Next, the first round key generation unit 124 uses the exclusive logic of the round constant C ^(r) generated by the round constant generation unit 123 and k ₄ ^(r−1) of the round keys of the ^(r−1) -th round. A value a obtained by concatenating the sum value a _H and the value a _L of k ₅ ^(r−1) of the round keys of the ^{(r−1) -th} round is input to the function F _k that is an F function. Value b _H (b _H = F _k (k ₄ ^(r−1) XOR C ^(r) , k ₅ ^(r−1) ) _H ) and lower bits A value b _L (here, lower 64 bits) b _L (b _L = F _k (k ₄ ^(r−1) XOR C ^(r) , k ₅ ^(r−1) ) _L ) is calculated.

Then, the first round key generation unit 124 calculates an exclusive OR of the value b _H and k ₆ ^(r−1) of the key round values of the ^(r−1) -th round, and calculates the calculated value. The key round value of the r-th round is k ₀ ^(r) .

The first round key generation unit 124 calculates an exclusive OR of the value b _L and k ₇ ^(r−1) of the key round values of the ^(r−1) -th round, and calculates the calculated value. The key round value of the r-th round is k ₁ ^(r) .

Next, the first round key generation unit 124 converts the key round values k ₄ ^(r−1) and k ₅ ^(r−1) of the key round values of the ^(r−1) -th round to the key round values k of the r-th round, respectively. ₆ ^(r) and k ₇ ^(r) .

The first round key generation unit 124 then calculates k ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ calculated as described above. ^(R) , k ₆ ^(r) , and k ₇ ^(r) are concatenated and stored in the key round value storage area 113 as the key round value of the r-th round, replaced with the key round value of the (r-1) -th round.

Further, the first round key generation unit 124 outputs k ₃ ^(r) in the key round value of the r-th round to the stirring unit 126 as the round key K ^(r) of the r-th round.

Next, the function F _K that is the F function used in the first round key generation unit 124 will be described.

The function F _K is a function that performs a combined transformation of the nonlinear transformation γ _K and the linear transformation λ _k as shown in the following equation (5).

The linear transformation λ _k is a composite transformation of byte substitution π _K and matrix transformation θ _K.

Here, describing the input to the function F _K X, the output from the function F _K as Y.

  In the present embodiment, X and Y are 128-bit data.

First, in the non-linear transformation γ _K , the value X is divided into sub-data (s ₀ , s ₁ ,..., S ₁₅ ) every 8 bits, and each sub-data is divided into the following formula (6) As shown in FIG. 5, nonlinear conversion is performed using the replacement table S-box. Here, it is assumed that the converted sub data is s ′ ₀ , s ′ ₁ ,..., S ′ ₁₅ .

  The replacement table Sbox is represented by, for example, (7) below.

Next, in the matrix transformation θ _K , the sub-data (s ′ ₀ , s ′ ₁ ,..., S ′ ₁₅ ) after the transformation by the nonlinear transformation γ _K is converted into an 8 × 2 matrix, and the following As shown in equation (10), conversion is performed by multiplication with the conversion matrix A. Here, the converted sub-data is s ″ ₀ , s ″ ₁ ,..., S ″ _15. Multiplication is multiplication on the finite field GF (2 ⁸ ) .The finite field GF (2 ^ 8) satisfies the following equations (8) and (9).

  Here, the transformation matrix A is included in an input column and an output column when a column is an input column and a column of values after the transformation by the transformation matrix A is performed on the input column is an output column. Any transformation matrix may be used as long as the number of terms whose value is not “0” is nine or more.

Next, in the byte substitution π _K , as shown in the following equation (11), the sub-data (s ″ ₀ , s ″ ₁ ,..., S ″ ₁₅ ) converted by the matrix transformation θ _K performing replacement of half of the data. in addition, the sub-converted data _{y 0,} y 1, · · _·, and _{y 15.}

Then, the sub-data (y ₀ , y ₁ ,..., Y ₁₅ ) calculated as described above are connected as shown in the equation (12) to obtain the output Y of the function F _K.

In more functions F _K, as compared to the function F _R described later, for performing an output in one of the processing for one input, requires less amount of calculation, it is possible to light implementation.

  Returning to FIG. 1, the second round key generation unit 125 performs a process of calculating a key round value and a round key in each round.

For example, the calculation of the key round value by the second round key generation unit 125 is performed using the second key round value conversion function f ′ _K shown in FIG. 4 (schematic diagram of the second key round value conversion function f ′ _K ). Is called.

As shown in the figure, the second key round value conversion function f ′ _K is stored in the calculated value storage area 115 when the key round value k ^{(r−1) of the} ( ^r−1) -th round (r = 0 ^). Calculated values or the initial values of the calculated values stored in the initial value storage area 111) are divided into eight divided data (here, 64 bits each ⁾ , k ₀ ^(r−1) , k ₁ ^{( _{r-1), k 2 (}} r-1), k 3 (r-1), k 4 (r-1), k 5 (r-1), k 6 (r-1), k 7 (r- ¹⁾ , k ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ ^(r) , k ₆ ^(r) , k _{7, respectively.} It is a function that generates a key round value k ^(r) for the r-th round by converting these values into ^(r) and concatenating these converted values.

Specifically, in the second key round value conversion function f ′ _K , first, the second round key generation unit 125 first sets the (r−1) th key round value stored in the key round value storage area 113 (however, , R = 0, the calculated values stored in the calculated value storage area 115 are changed to k ₀ ^(r−1) , k ₁ ^(r−1) , k ₂ ^(r−1) , k ₃ ^{( _{r-1), k 4 (}} r-1), k 5 (r-1), k 6 (r-1), 8 aliquoted into ^{k 7 (r-1).}

Next, the second round key generation unit 125 includes k ₀ ^(r−1) and k ₁ ^{(r−1) out} of the key round values of the ^(r−1) -th round (calculated values when r = 0 ^). , K ₂ ^(r−1) and k ₃ ^(r−1) are respectively represented by k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ ^{( r)}

Next, the second round key generation unit 125 includes the round constant C ^(r) generated by the round constant generation unit 123 and the key round value of the (r−1 ⁾ -th round (calculated value when r = 0). of _k ^{4 (r-1)} and a value a _'H is exclusive of, _k ⁵ of the key round value of the r-1 round (calculated value in the case of r = 0) ^{(r-1 )} value a at a is the function F upper bits of the output value inputted to the _R (where F function 'and _L, value a linked a', the value b _{'H (b'} of the upper 64 bits) _H = F _R (k ₄ ^(r−1) XOR C ^(r) , k ₅ ^(r−1) ) _H ) and the value b ′ _L (b _L = F _R ( _{^{k 4 (r-1) XOR}} C (r), k 5 and _{^{(r-1)) L)}} , is calculated.

Then, the second round key generation unit 125 calculates the value b ′ _H and k ₆ ^(r−1) of the key round values of the ^(r−1) -th round (calculated values when r = 0 ⁾ . An exclusive OR is calculated, and the calculated value is set as the key round value k ₀ ^(r) of the r-th round.

In addition, the second round key generation unit 125 calculates the value b ′ _L and k ₇ ^(r−1) of the key round values of the ^(r−1) -th round (calculated values when r = 0 ⁾ . An exclusive OR is calculated, and the calculated value is set as the key round value k ₁ ^(r) of the r-th round.

Next, the second round key generation unit 125 includes k ₄ ^(r−1) and k ₅ ^{(r−1) out} of the key round values of the ^(r−1) -th round (calculated values when r = 0 ^). Are the r-th key round values k ₆ ^(r) and k ₇ ^(r) , respectively.

Then, the second round key generation unit 125 calculates k ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ calculated as described above. ^(R) , k ₆ ^(r) , and k ₇ ^(r) are concatenated and stored in the key round value storage area 113 as the key round value of the r-th round, replaced with the key round value of the (r-1) -th round.

Further, the second round key generation unit 125 outputs k ₃ ^(r) in the r-th round key round value to the agitation unit 126 as the ^r-th round key K ^(r) .

Next, functions described F _R is F function used in the second round-key generation unit 125.

The function F _R is a function that performs the synthesis transformation of the nonlinear transformation γ _R , the byte replacement π _R, and the matrix transformation θ _R four times (four stages), as shown in the following equation (13).

Here, describing the input to the function F _R X, the output from the function F _R as Y. In the present embodiment, X and Y are 128-bit data.

First, the nonlinear transformation gamma _R, the sub-data for each 8-bit value X by dividing _{(s 0, s 1, ···} , s 15) in the sub-data of the divided each of the following formula (14) As shown in FIG. 5, nonlinear conversion is performed using the replacement table S-box. Here, it is assumed that the converted sub data is s ′ ₀ , s ′ ₁ ,..., S ′ ₁₅ .

  For example, the replacement table Sbox may be the one shown in (7) above.

Next, in the byte replacement π _R , as shown in the equation (15), the sub-data (s ′ ₀ , s ′ ₁ ,..., S ′ ₁₅ ) converted by the nonlinear conversion γ _R is stored in 4 rows and 4 columns. As a matrix, the data is exchanged so that the data of each row included in each column is arranged in a different column. Note that equation (15) is an example, and other replacement methods can be adopted as long as the data in each row included in each column is arranged in a different column.

Further, the sub-data of the converted _{s "0, s" 1,} ···, and _{s "15.}

Next, in the matrix transformation θ _R , as shown in the following equation (16), the sub-data (s ″ ₀ , s ″ ₁ ,..., S ″ ₁₅ ) after the transformation with the byte replacement π _R described above. Is performed by performing multiplication on a finite field GF (2 ⁸ ) of a matrix of 4 rows and 4 columns and a transformation matrix B. Here, the transformed sub-data is represented by y ₀ , Let y ₁ ,..., y ₁₅ .

  Here, the transformation matrix B is included in an input column and an output column when a column is an input column and a column of values after the transformation by the transformation matrix B is performed on the input column is an output column. Any transformation matrix may be used as long as the number of terms whose values are not “0” is five or more.

Then, the sub data (y ₀ , y ₁ ,..., Y ₁₅ ) calculated in this way is converted into sub data (s ₀ , s ₁ ,..., S, as shown in the equation (17). ₁₅ ), the sub-data (y ₀ , y ₁ ,..., Y ₁₅ calculated by performing the transformation by the nonlinear transformation γ _R , byte substitution π _R and matrix transformation θ _R three times (four times in total). ) (17) by concatenating as type, the output Y of the function _{F R.}

In more functions F _R, as compared with the function F _K described above, for performing the output in four processing for one input, it is possible to enhance the safety. In addition, about the frequency | count of this 4 times, it can change suitably.

  Returning to FIG. 1, the stirring unit 126 performs a process of calculating a plaintext round value in each round.

For example, calculation of plaintext round value by stirring section 126 is performed using the plaintext round value transformation function f _R shown in FIG. 5 (a schematic diagram of plaintext round value transformation function f _R).

As shown in the figure, the plaintext round value conversion function f _R is the plaintext round value x ^{(r−1) of the} ( ^r−1) -th round (however, when r = 0, the message blocked by the message blocking unit 122) The block M ′ _i ) is divided into 8 (here, 64 bits each), which is divided data x ₀ ^(r−1) , x ₁ ^(r−1) , x ₂ ^(r−1) , x ₃ ^{(r− 1)} , x ₄ ^(r-1) , x ₅ ^(r-1) , x ₆ ^(r-1) , x ₇ ^(r-1) , respectively, x ₀ ^(r) , x ₁ ^(r) , By converting x ₂ ^(r) , x ₃ ^(r) , x ₄ ^(r) , x ₅ ^(r) , x ₆ ^(r) , x ₇ ^(r) and concatenating these converted values, This is a function that generates a plaintext round value x ^(r) of the r-th round.

Specifically, in the plaintext round value conversion function f _R , first, the agitation unit 126 performs the r−1 round plaintext round value stored in the plaintext round value storage area 114 (provided that r = 0). , The message block M ′ _i ) blocked by the message blocking unit 122 is converted into x ₀ ^(r−1) , x ₁ ^(r−1) , x ₂ ^(r−1) , x ₃ ^(r−1). , X ₄ ^(r-1) , x ₅ ^(r-1) , x ₆ ^(r-1) , and x ₇ ^(r-1) .

Next, the agitation unit 126 includes x ₀ ^(r−1) , x ₁ ^(r−1) , of the plaintext round values of the r−1-th round (in the case of r = 0, the message block M ′ _i ⁾ , x ₂ ^(r-1) and x ₃ ^(r-1) are respectively expressed as x ₂ ^(r) , x ₃ ^(r) , x ₄ ^(r) and x ₅ ^{(r )} in the plaintext round value of the r-th round. ⁾

Next, the agitation unit 126 generates the round key K ^(r) generated by the first round key generation unit 124 or the second round key generation unit 125 and the plaintext round value of the (r−1 ⁾ -th round (when r = 0). , The value p _H which is the exclusive OR of x ₄ ^{(r−1) in} the message block M ′ _i ) and the plaintext round value of the r−1-th round (if r = 0, the message block M ′ x ₅ of the _{i) (the} value p _L of ^r-1), the upper bits of the output value of the value p which is connected to the input to the function F _R is F function (here, the upper 64 bits) the value ^{_{q H (q H = F R}} (x 4 (r-1) XOR K (r), x 5 (r-1)) H), ( in this case, the lower 64 bits) lower bit value _{q L} of ^{_{(q L = F R (x}} 4 (r-1) XOR K (r), x 5 (r-1)) L), to calculate the The

Then, the agitation unit 126 exclusively uses the value q _H and x ₆ ^{(r−1) in} the plaintext round value of the (r−1) -th round (in the case of r = 0, the message block M ′ _i ). The logical sum is calculated, and the calculated value is set to x ₀ ^(r) of the ^r-th plaintext round key.

Further, the stirring section 126, the value _{q L,} (in the case of r = 0, the message block M _'i) the plaintext round value of r-1 rounds and _x ^{7 (r-1)} of the exclusive of The logical sum is calculated, and the calculated value is set to x ₁ ^(r) of the plaintext round value of the r-th round.

Next, the stirring unit 126 calculates x ₄ ^(r−1) and x ₅ ^(r−1) in the plaintext round value of the (r−1) -th round (in the case of r = 0, the message block M ′ _i ). , Respectively, are the plaintext round values x ₆ ^(r) and x ₇ ^{(r) of} the r-th round.

Then, the stirring section 126 _x ⁰ is calculated as described above ^{_{(r), x 1 (r}} ), x 2 (r), x 3 (r), x 4 (r), x 5 (r), x ₆ ^(r) and x ₇ ^(r) are concatenated and stored in the plaintext round value storage area 114 as a plaintext round value of the r-th round, replacing the key round value of the (r-1) -th round.

Since elements are the F function used in the stirring section 126 function F _R, which is similar to that shown in the above (13), the description thereof is omitted.

  The input unit 130 receives input of information.

  The output unit 140 outputs information.

  The hash value generation device 100 described above is, for example, an external storage such as a CPU (Central Processing Unit) 901, a memory 902, and an HDD (Hard Disk Drive) as shown in FIG. 6 (schematic diagram of the computer 900). A device 903, a reading device 905 for reading / writing information from / to a portable storage medium 904 such as a compact disk read only memory (CD-ROM) or a digital versatile disk read only memory (DVD-ROM), a keyboard and a mouse It can be realized by a general computer 900 including an input device 906 such as a display, an output device 907 such as a display, and a communication device 908 such as a NIC (Network Interface Card) for connecting to a communication network.

  For example, the storage unit 110 can be realized by the CPU 901 using the memory 902 or the external storage device 903, and the control unit 120 loads a predetermined program stored in the external storage device 903 into the memory 902. The input unit 130 can be realized by the CPU 901 using the input device 906, and the output unit 140 can be realized by the CPU 901 using the output device 907. .

  The predetermined program is downloaded from the storage medium 904 via the reading device 905 or from the network via the communication device 908 to the external storage device 903, and then loaded onto the memory 902 and executed by the CPU 901. You may do it. Alternatively, the program may be directly loaded on the memory 902 from the storage medium 904 via the reading device 905 or from the network via the communication device 908 and executed by the CPU 901.

  Next, with reference to FIG. 7 (schematic diagram showing hash value calculation processing), an outline of processing in which the hash value generation device 100 calculates hash values will be described.

  First, the hash value generation device 100 receives an input of a message M for generating a hash value via the input unit 130, and the overall control unit 121 of the hash value generation device 100 inputs the message M to the message blocking unit 122. To do.

Then, the message blocking unit 122 pads the message M and divides it into 512-bit message blocks (M ′ ₀ ,..., M ′ _k ; k is an integer of 1 or more).

Next, the overall control unit 121 sets the first message among the initial value H _{−1 of the} calculated value stored in the initial value storage area 111 and the message block M _i ′ blocked by the message blocking unit 122. By inputting the block M ′ ₀ to the first block cipher f _E , the plaintext round value h ₀ is calculated.

Here, processing using the first block cipher f _E, as described later, the round-constant generation unit 123, is performed in the first round-key generation unit 124 and the stirring section 126.

Then, the overall control unit 121 obtains a calculated value by calculating an exclusive OR of the calculated plaintext round value h ₀ and the message block M ′ _0, and calculates the calculated value and the next message block By inputting M ′ ₁ into the first block cipher f _E , the plaintext round value h ₁ is calculated. Note that the calculated value is stored in the calculated value storage area 115.

By repeating such processing up to the message block M ′ _k−1 immediately before the last message block M ′ _k , the plaintext round value h _k−1 is calculated.

Then, the overall control unit 121 determines the calculated value calculated by exclusive OR of the plaintext round value h _k−1 and the message block M ′ _k−1 and the last message block M ′ _k . By inputting to the two-block cipher f ′ _E , the plaintext round value h _k is calculated.

Here, the process using the second block cipher f ′ _E is performed by the round constant generation unit 123, the second round key generation unit 125, and the agitation unit 126, as described later.

Then, the overall control unit 121 calculates a hash value H _k by exclusive OR of the plaintext round value h _k and the last message block M ′ _k .

Such a hash value H _k is stored in the hash value storage area 116.

Note that the hash value calculation processing (method) in the present invention is not limited to the processing (method) shown in FIG. 7, and at least one of the first block cipher f _E and the second block cipher f ′ _E. Anything can be used as long as one of them is used.

Figure 8 is a schematic diagram showing the process in the first block cipher f _E.

First, the round-constant generation unit 123 acquires the initial value of the constant round value stored in the initial value storage area 111, by performing the processing using the linear transformation function f _c as shown in FIG. 2, calculating a constant round value ^{c (0)} in the round r = 0, to calculate the lower 64 bits of the constant round value ^{c (0),} as ^{C (0)} round constant in the round r = 0.

Then, the round constant generation unit 123 stores the calculated constant round value c ⁽⁰⁾ in the constant round value storage area 112, and outputs the round constant C ⁽⁰⁾ to the first round key generation unit 124.

Next, when the message block M ′ _i input to the first block cipher f _E is the message block M ′ ₀ , the first round key generation unit 124 calculates the calculated value stored in the initial value storage area 111. On the other hand, if the message block M ′ _i input to the first block cipher f _E is not the message block M ′ ₀ , the previous message block stored in the calculated value storage area 115 is acquired. The key round value k ⁽⁰⁾ at r = 0 is calculated by obtaining the calculated value at M ′ _i and performing the process using the first key round value conversion function f _K as shown in FIG. Moreover, to calculate the _k ^{3 (0)} of the key round value ^{k (0),} as a round key ^K rounds r = ^{0 (0).}

Then, the first round key generation unit 124 stores the key round value k ⁽⁰⁾ in the key round value storage area 113 and outputs the round key K ⁽⁰⁾ to the stirring unit 126.

Next, the agitation unit 126 obtains the message block M ′ _i input to the first block cipher f _E and performs a process using the plaintext round value conversion function f _R as shown in FIG. The plaintext round value x ⁽⁰⁾ at r = 0 is calculated and stored in the plaintext round value storage area 114.

  This is the end of the zeroth round process.

Then, the round-constant generation unit 123 obtains a constant round value stored in the constant round value storage area 112 c ^(0), performs a process using the linear transformation function f _c as shown in FIG. 2 it allows to calculate the constant round value ^{c (1)} in the round r = 1, calculates the lower 64 bits of the constant round value ^{c (1),} as the round constant ^{C (1)} in the round r = 1.

Then, the round constant generation unit 123 replaces the calculated constant round value c ⁽¹⁾ with the constant round value c ⁽⁰⁾ (so-called overwriting), and stores the round constant C in the constant round value storage area 112. ⁽¹⁾ is output to the first round key generation unit 124.

Next, the first round key generation unit 124 acquires the key round value k ⁽⁰⁾ stored in the key round value storage area 113, and the first key round value conversion function f _K as shown in FIG. Is used to calculate a key round value k ⁽¹⁾ in round r = 1, and k ₃ ⁽¹⁾ in key round value k ⁽¹⁾ is calculated as a round of round r = 1. Calculated as key K ⁽¹⁾ .

Then, the first round key generation unit 124 replaces the calculated key round value k ⁽¹⁾ with the key round value k ⁽⁰⁾ (so-called overwriting), stores it in the key round value storage area 113, and stores the round The key K ⁽¹⁾ is output to the stirring unit 126.

Then, the stirring section 126 is performed by obtaining the plain text round value x stored in the plaintext round value storage area 114 ^(0), the process using the plaintext round value transformation function f _R as shown in FIG. 5 Thus, the plaintext round value x ⁽¹⁾ in round r = 1 is calculated, and the calculated plaintext round value x ⁽¹⁾ is replaced with the plaintext round value x ⁽⁰⁾ (so-called overwriting) to obtain the plaintext round value. Store in the storage area 114.

  This completes the first round of processing.

Then, the same processing as in the first round described above, the predetermined rounds (here, the 31 round) By repeating until the process ends in the first block cipher f _E.

FIG. 9 is a schematic diagram showing processing in the second block cipher f ′ _E.

First, the round-constant generation unit 123 acquires the initial value of the constant round value stored in the initial value storage area 111, by performing the processing using the linear transformation function f _c as shown in FIG. 2, calculating a constant round value ^{c (0)} in the round r = 0, to calculate the lower 64 bits of the constant round value ^{c (0),} as ^{C (0)} round constant in the round r = 0.

Then, the round constant generation unit 123 stores the calculated constant round value c ⁽⁰⁾ in the constant round value storage area 112, and outputs the round constant C ⁽⁰⁾ to the second round key generation unit 125.

Next, the second round key generation unit 125 acquires the calculated value in the previous message block M ′ _k−1 stored in the calculated value storage area 115, and converts the second key round value as shown in FIG. by performing the processing using the function f _'K, and calculates the key round value ^{k (0)} in the r = 0, also, _k ³ of the key round value ^{k (0)} to ^(0), the round r = Calculated as ⁰ round key K ⁽⁰⁾ .

Then, the second round key generation unit 125 stores the key round value k ⁽⁰⁾ in the key round value storage area 113 and outputs the round key K ⁽⁰⁾ to the stirring unit 126.

Next, the agitation unit 126 obtains the message block M ′ _k input to the second block cipher f ′ _E and performs processing using the plaintext round value conversion function f _R as shown in FIG. , R = 0 plaintext round value x ⁽⁰⁾ is calculated and stored in the plaintext round value storage area 114.

  This is the end of the zeroth round process.

Then, the round-constant generation unit 123 obtains a constant round value stored in the constant round value storage area 112 c ^(0), performs a process using the linear transformation function f _c as shown in FIG. 2 it allows to calculate the constant round value ^{c (1)} in the round r = 1, calculates the lower 64 bits of the constant round value ^{c (1),} as the round constant ^{C (1)} in the round r = 1.

Then, the round constant generation unit 123 replaces the calculated constant round value c ⁽¹⁾ with the constant round value c ⁽⁰⁾ (so-called overwriting), and stores the round constant C in the constant round value storage area 112. ⁽¹⁾ is output to the second round key generation unit 125.

Next, the second round key generation unit 125 acquires the key round value k ⁽⁰⁾ stored in the key round value storage area 113, and the second key round value conversion function f ′ as shown in FIG. by performing the processing using the _K, and calculates the key round value ^{k (1)} in the round r = 1, also the _k ^{3 (1)} of the key round value ^{k (1),} round r = 1 Calculated as round key K ⁽¹⁾ .

Then, the second round key generation unit 125 replaces the calculated key round value k ⁽¹⁾ with the key round value k ⁽⁰⁾ (so-called overwriting) and stores it in the key round value storage area 113, The key K ⁽¹⁾ is output to the stirring unit 126.

Then, the stirring section 126 is performed by obtaining the plain text round value x stored in the plaintext round value storage area 114 ^(0), the process using the plaintext round value transformation function f _R as shown in FIG. 5 Thus, the plaintext round value x ⁽¹⁾ in round r = 1 is calculated, and the calculated plaintext round value x ⁽¹⁾ is replaced with the plaintext round value x ⁽⁰⁾ (so-called overwriting) to obtain the plaintext round value. Store in the storage area 114.

  This completes the first round of processing.

By repeating the same process as the process in the first round described above until a predetermined round (here, the 31st round), the process in the second block cipher f ′ _E is completed.

  FIG. 10 is a flowchart showing hash value generation processing in the hash value generation device 100.

  First, the hash value generation device 100 acquires a message M that is a source for generating a hash value via the input unit 130 (S10).

Next, the message blocking unit 122 generates k + 1 message blocks M ′ _i by dividing the message acquired via the input / output unit 130 into a predetermined data length (S11). In this embodiment, the message is divided into 512-bit data lengths.

  Next, the overall control unit 121 resets the information stored in the constant round value storage area 112, the key round value storage area 113, the plaintext round value storage area 114, the calculated value storage area 115, and the hash value storage area 116. Perform (S12). Specifically, all bit values are set to “0”.

  Next, the overall control unit 121 initializes the value of the message counter i, which is a message block counter (S13). Here, “0” is substituted for the value of the message counter i.

  Next, the overall control unit 121 determines whether or not the value of the message counter i is i = k (S14).

  If i = k is not satisfied in step S14 (No in step S14), the process proceeds to step S15. If i = k is satisfied (Yes in step S14), the process proceeds to step S21.

  In step S15, the overall control unit 121 assigns an initial value “0” to the round counter r, which is a round counter.

  Next, the overall control unit 121 determines whether the value of the round counter r has a relationship of r = (ROUND NUM) +1 with respect to a predetermined first round number (here, ROUND NUM = 31). Is determined (S16). If it is determined in step S16 that r = (ROUND NUM) +1, the process proceeds to step S19. If r = (ROUND NUM) +1 is not satisfied, the process proceeds to step S17.

In step S17, the round constant generation unit 123, the first round-key generation unit 124 and the stirring section 126, using the first block cipher f _E, calculated constant round value, the key round value and the plaintext round value, constant round Information stored in the value storage area 112, the key round value storage area 113, and the plaintext round value storage area 114 is updated.

  Next, the overall control unit 121 increments the value of the round counter r by “1”, returns to step S16, and repeats the process.

In step S19, the overall control unit 121 calculates a calculated value by calculating an exclusive OR of the plaintext round value stored in the plaintext round value storage area 114 and the message block M ′ _i. The information stored in the calculated value storage area 115 is updated with the calculated value.

  The overall control unit 121 increments the value of the message counter i by “1” (S20), returns to step S14, and repeats the process.

  On the other hand, if i = k in step S14 (Yes in step S14), in step S21, the overall control unit 121 assigns an initial value “0” to the round counter r, which is a round counter. .

  Next, the overall control unit 121 determines whether or not the value of the round counter r has a relationship of r = (ROUND NUM) +1 with respect to a predetermined second round number (here, ROUND NUM = 31). Is determined (S22).

  In step S22, if r = (ROUND NUM) +1 (Yes in step S22), the process proceeds to step S25. If r = (ROUND NUM) +1 is not satisfied (in step S22). No), it proceeds to step S23.

In step S23, the round constant generation unit 123, the second round key generation unit 125, and the stirring unit 126 calculate the constant round value, the key round value, and the plaintext round value using the second block cipher f ′ _E , Information stored in the round value storage area 112, the key round value storage area 113, and the plaintext round value storage area 114 is updated.

  Next, the overall control unit 121 increments the value of the round counter r by “1” (S24), returns to step S22, and repeats the process.

Further, in step S25, the overall control unit 121 calculates a plaintext round value stored in the plaintext round value storage area 114, a hash value by calculating the message block M _'k, the exclusive OR of The information stored in the hash value storage area 116 is updated.

  As described above, in the present embodiment, since a 512-bit block cipher is used, it is possible to provide a hash function that guarantees theoretical security and mounting security.

  FIG. 11 is a schematic diagram of a hash value generation device 200 according to the second embodiment of the present invention.

  Here, in this embodiment, a 256-bit hash value is generated.

  As illustrated, the hash value generation device 200 includes a storage unit 210, a control unit 220, an input unit 130, and an output unit 140. Compared to the first embodiment, the storage unit 210 and the control unit Since the portion 220 is different, matters related to these different points will be described below.

  The storage unit 210 includes an initial value storage area 211, a constant round value storage area 112, a key round value storage area 113, a plaintext round value storage area 114, a calculated value storage area 115, a hash value storage area 116, Since the information stored in the initial value storage area 211 is different from that of the first embodiment, items related to the different points will be described below.

  The initial value storage area 211 stores information for specifying an initial value when generating a hash value.

  In the present embodiment, an initial value of a constant round value and an initial value of a calculated value are stored as initial values when generating a hash value.

Here, as the initial value of the constant round value, for example, a constant such as c ⁽⁻¹⁾ = 0xffffffffffffffff is stored.

The initial value of the calculated value is H ₋₁ = (H _−1.0 , H _−1.1 ,..., H _−1.7 ), and H _−1.0 = 0x00000000, H _{−1. .1} = 0x00000000, H- _1.2 = 0x00000000, H- _1.3 = 0x00000000, H- _1.4 = 0x00000000, H- _1.5 = 0x00000000, H- _1.6 = 0x00000000, H- _1.7 = 0x00000000 is stored.

  The constants used for the constant round value and the initial value of the calculated value are not limited to these. For example, a random number generated by a pseudo-random number generator or the like can be used.

  The control unit 220 includes an overall control unit 221, a message blocking unit 222, a round constant generation unit 223, a first round key generation unit 224, a second round key generation unit 225, and a stirring unit 226. .

  The overall control unit 221 controls the overall processing in the hash value generation device 200.

  In particular, in the present embodiment, a process for managing a message block obtained by blocking a message for calculating a hash value, a round constant generation unit 223, a first round key generation unit 224, a second round key generation unit 225, and a stirring unit A process for managing the round at 226 is performed.

  Further, the overall control unit 221 calculates the exclusive OR of the plaintext round value calculated in the stirring unit 226 through all rounds and the message block that is the target of processing in the round, Calculate the calculated value.

  Furthermore, the overall control unit 221 calculates the exclusive OR of the plaintext round value calculated by the agitation unit 226 through all message blocks and all rounds, and the last message block, thereby calculating the hash value. calculate.

  The message blocking unit 222 divides a message for which a hash value is to be calculated into blocks having a predetermined bit length and performs padding.

  Here, in the present embodiment, a message for which a hash value is calculated is divided into blocks each having 256 bits, but the present invention is not limited to such a mode.

  For example, padding in the present embodiment is performed as follows.

  First, when the number of bits of a message whose hash value is to be calculated is divisible by 256 bits, the message blocking unit 222 generates each message block by dividing the message into 256 bits. The message block is added as the last message block.

  Then, in this last message block, the message blocking unit 222 sets “1” as the first bit, “0” up to 191 bits from the next bit after the first bit, bit length of the message as the last 64 bits, Stores information that identifies

  Next, when the number of bits of the message whose hash value is to be calculated is not divisible by 256 bits, the message blocking unit 222 generates each message block by dividing the message into 256 bits. At the same time, information specifying “0” up to the last bit is stored in the last message block thus divided to 256 bits, and a message block is further added to form the last message block.

  Then, the message blocking unit 122 stores information specifying “0” up to 192 bits counted from the first bit and the bit length of the message in the last 64 bits in the last message block.

In the present embodiment, a message for calculating a hash value is M, a message having a bit length divisible by 256 bits by padding is M ′, and the number of message blocks is k + 1 (k is 1 or more). Integer), and each message block is M ′ _i (i is an integer satisfying 0 ≦ i ≦ k).

  The round constant generation unit 223 calculates a constant round value and a round constant in each round.

Also in the present embodiment, the round constant generation unit 223, in the case of the first round, from the initial value of the constant round value stored in the initial value storage area 211, or if it is not the first round, from the constant round value in the previous round, which is stored in the constant round value storage area 212, using a linear transformation function f _c, calculates a constant round value in each round.

For example, as shown in FIG. 2, the round constant generation unit 223 uses the constant round value c ^(r−1) of the previous round (r−1) ⁽ the initial value of the constant round value when r = 0) as a function. The constant round value of the current round (r) is obtained by switching the upper bits (upper 32 bits in the present embodiment) and lower bits (lower 32 bits in the present embodiment) of the value calculated by inputting to f _L c ^(r) is calculated.

That is, as shown in the above equations (1) and (2), the current round is calculated from the constant round value c ^{(r−1) of} the previous round ⁽ the initial value of the constant round value when r = 0). A constant round value c ^{(r) of} is calculated.

The function f _L uses a linear feedback shift register (LFSR).

  Generally, the LFSR is determined by a polynomial. Here, a polynomial g (x) for determining the LFSR is defined as the following equation (18).

  However, g (x) is a polynomial defined in the finite field GF (2).

Incidentally, the pseudo-code for the function _{f L} is expressed by the following (19).

Here, “<< X” indicates a left shift of X bits, “>> Y” indicates a right shift of Y bits, “^” indicates an exclusive OR, and “&” “|” Indicates a logical product, and “|” indicates a logical sum. Further, h is upper bits of the constant round value ^{c (r-1) (upper} 32 bits), l is the lower-order bits of the constant round value ^{c (r-1) (low-order} 32 bits).

Then, the round constant generation unit 223 sets the lower 32 bits of the constant round value c ^{(r) in} the calculated round (r) as the round constant C ^(r) in the r-th round, or the first round key generation unit 224 or The data is output to the second round key generation unit 225.

An example of C ^(r) in the case of R = 96 is given below.

C ⁽⁰⁾ = 0x3b29b693, C ⁽¹⁾ = 0x90a58f8a, C ⁽²⁾ = 0x472ae357, C ⁽³⁾ = 0x42963e28, C ⁽⁴⁾ = 0xd87dc430, C ⁽⁵⁾ = 0x650288d7, C ⁽⁶⁾ = 0x0ead60b6, C ^{(7) = 0xfb50532a, C (} 8) = 0x9139bbc3, C (9) = 0x299705c5, C (10) = 0xef6ad616, C (11) = 0xa65c1715, C (12) = 0x797d1135, C (13) = 0x32fc654e, C ( ^{14) = 0x21220db8, C (15} ) = 0x607dac22, C (16) = 0x848836e0, C (17) = 0x4520f9e5, C (18) = 0xb9ace29a, C (19) = 0xd055aef9, C (20) = 0x4d3fb373, C (21 ^{) = 0x8580f288, C (22)} = 0x5ba4bdbb, C (23) = 0xbd8ff33a, C (24) = 0xaa44bf81, C (25) = 0x5db3f5f3, C (26) = 0xa912fe04, C (27) = 0xb2199ea1, C (28) = 0x0fc7c10b, C ⁽²⁹⁾ = 0xc8667a84, C ⁽³⁰⁾ = 0x3f1f042d, C ^{( 31) = 0xe54fa37c, C (32} ) = 0x57f029af, C (33) = 0x51e8c49c, C (34) = 0x309ad6ca, C (35) = 0x28f96206, C (36) = 0x69e76232, C (37) = 0xa3e58818, C (38 ⁾ = 0x634bc1a5, C ⁽³⁹⁾ = 0x241a197a, C ⁽⁴⁰⁾ = 0x49f94ff8, C ⁽⁴¹⁾ = 0x3be45cf2, C ⁽⁴²⁾ = 0xe333768c, C ⁽⁴³⁾ = 0x441d4ad3, C ⁽⁴⁴⁾ = 0x481b935c, C ^{(45) = 0x7f2f5b3a, C (46) =} 0x4f343d06, C (47) = 0x93e71c9e, C (48) = 0x538a846f, C (49) = 0xe4104b62, C (50) = 0x8afc58d1, C (51) = 0xff1b5dff, C (52) = 0x807d5a5f, C ⁽⁵³⁾ = 0x38bb3e91, C ⁽⁵⁴⁾ = 0xaa795066, C ⁽⁵⁵⁾ = 0xe2ecfa45, C ⁽⁵⁶⁾ = 0xa9e54199, C ⁽⁵⁷⁾ = 0x4f65a079, C ⁽⁵⁸⁾ = 0x0c193f7e, 0 ⁽⁵⁹⁾ , C ⁽⁶⁰⁾ = 0x9be8c4e3, C ⁽⁶¹⁾ = 0x21d56b4d, C ⁽⁶²⁾ = 0xc42f2a96, C ⁽⁶³⁾ = 0x8755ad35, C ⁽⁶⁴⁾ = 0xd46ae335, C ⁽⁶⁵⁾ = 0xb6da8dcf, C ⁽⁶⁶⁾ = 0x957dc5b9, C ⁽⁶⁷⁾ = 0x70e60e27, C ⁽⁶⁸⁾ 0x55f716e4, C ⁽⁶⁹⁾ = 0x074e71f0, C ⁽⁷⁰⁾ = 0x38862be6, C ⁽⁷¹⁾ = 0xb6b5feda, C ⁽⁷²⁾ = 0xe218af99, C ⁽⁷³⁾ = 0xdad7fb69, C ⁽⁷⁴⁾ = 0x4cb4f709, x ⁽ 040 ⁾ 0 ⁽⁷⁵⁾ C ⁽⁷⁶⁾ = 0x5d89ac52, C ⁽⁷⁷⁾ = 0xbb9a4e52, C ⁽⁷⁸⁾ = 0xb2f0f825, C ⁽⁷⁹⁾ = 0x45e50053, C ⁽⁸⁰⁾ = 0xcbc3e094, C ⁽⁸¹⁾ = 0xd3424821, C ⁽⁸²⁾ = 0x4055 C ⁽⁸³⁾ = 0x225350f2, C ⁽⁸⁴⁾ = 0x6e0db8ea, C ⁽⁸⁵⁾ = 0x22c17ad2, C ⁽⁸⁶⁾ = 0x7ce0aac4, C ⁽⁸⁷⁾ = 0x2089d252, C ⁽⁸⁸⁾ = 0x3754e27c, C ⁽⁸⁹⁾ = 0x29ab7052, C ⁽⁹⁰⁾ = 0xdd5389f0, C ⁽⁹¹⁾ = 0xa6adc 149, C ⁽⁹²⁾ = 0xb1986ead, C ⁽⁹³⁾ = 0x313b3c3f, C ⁽⁹⁴⁾ = 0xc661bab4, C ⁽⁹⁵⁾ = 0xc4ecf0fd.

  The first round key generation unit 224 performs processing for calculating a key round value and a round key in each round.

For example, the calculation of the key round value by the first round key generation unit 224 is performed using the first key round value conversion function f _K shown in FIG.

As shown in FIG. 3, the first key round value conversion function f _K is the key round value k ^{(r−1) of the} ( ^r−1) -th round (however, when r = 0, it is stored in the calculated value storage area 115). Calculated value or the initial value of the calculated value stored in the initial value storage area 211) is divided into eight pieces (in this embodiment, 32 bits each), k ₀ ^(r−1). , K ₁ ^(r-1) , k ₂ ^(r-1) , k ₃ ^(r-1) , k ₄ ^(r-1) , k ₅ ^(r-1) , k ₆ ^(r-1) , k ₇ ^(r-1) is replaced with k ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ ^(r) , k ₆ ^{(r, respectively. )} , K ₇ ^(r), and these converted values are concatenated to generate the r-th round key round value k ^(r) .

Note that the processing using the first key round value conversion function f _K is the same as that of the first embodiment except that the number of bits is different, and thus detailed description thereof is omitted.

Next, the function F _K that is the F function used in the first round key generation unit 224 will be described.

The function F _K in the present embodiment is also a function that performs a combined transformation of the nonlinear transformation γ _K and the linear transformation λ _k as shown in the above equation (5), and the linear transformation λ _k is a byte substitution π. _K and matrix transformation θ _K.

Here, describing the input to the function F _K X, the output from the function F _K as Y.

  In the present embodiment, X and Y are 64-bit data.

First, in the non-linear transformation γ _K , the value X is divided into sub-data (s ₀ , s ₁ ,..., S ₇ ) every 8 bits, and each sub-data is divided into the following equation (20) As shown in FIG. 5, nonlinear conversion is performed using the replacement table Sbox. Here, it is assumed that the converted sub data is s ′ ₀ , s ′ ₁ ,..., S ′ ₇ .

  The replacement table Sbox is represented by (7) above, for example.

Next, in the matrix transformation θ _K , the sub-data (s ′ ₀ , s ′ ₁ ,..., S ′ ₇ ) after the transformation by the nonlinear transformation γ _K is converted into a 4 × 2 matrix and the following As shown in equation (21), the transformation is performed by multiplying the transformation matrix A on the finite field GF (2 ⁸ ). Here, the sub-data of the converted _{s "0, s" 1,} ···, and s _"7.

  Here, the transformation matrix A is included in an input column and an output column when a column is an input column and a column of values after the transformation by the transformation matrix A is performed on the input column is an output column. Any transformation matrix may be used as long as the number of terms whose values are not “0” is five or more.

Next, in the byte replacement π _K , as shown in the following equation (22), among the sub data (s ″ ₀ , s ″ ₁ ,..., S ″ ₇ ) converted by the matrix conversion θ _K performing replacement of half of the data. in addition, the sub-converted data _{y 0,} y 1, · · ·, and _{y 7.}

Then, the sub-data (y ₀ , y ₁ ,..., Y ₇ ) calculated as described above are connected as shown in the equation (23) to obtain the output Y of the function F _K.

In more functions F _K, as compared to the function F _R described later, for performing an output in one of the processing for one input, requires less amount of calculation, it is possible to light implementation.

  Returning to FIG. 11, the second round key generation unit 225 performs a process of calculating a key round value and a round key in each round.

For example, the calculation of the key round value by the second round key generation unit 225 is performed using a second key round value conversion function f ′ _K as shown in FIG.

As shown in FIG. 4, the second key round value conversion function f ′ _K is the key round value k ^{(r−1) of the} ( ^r−1) -th round (however, if r = 0, the calculated value storage area 115 stores K ₀ ^(r−1), which is divided data obtained by dividing the stored calculated value or the initial value of the calculated value stored in the initial value storage area 111 into eight (in this embodiment, 32 bits each ^). , K ₁ ^(r-1) , k ₂ ^(r-1) , k ₃ ^(r-1) , k ₄ ^(r-1) , k ₅ ^(r-1) , k ₆ ^(r-1) , k ₇ ^(r-1) is replaced with k ₀ ^(r) , k ₁ ^(r) , k ₂ ^(r) , k ₃ ^(r) , k ₄ ^(r) , k ₅ ^(r) , k ₆ ^{(r, respectively. )} , K ₇ ^(r), and these converted values are concatenated to generate the r-th round key round value k ^(r) .

Note that the processing using the second key round value conversion function f ′ _K is the same as in the first embodiment except that the number of bits is different, and thus detailed description thereof is omitted.

Next, functions described F _R is F function used in the second round-key generation unit 225.

The function F _R is a function that performs the composite transformation of the nonlinear transformation γ _R , the byte replacement π _R, and the matrix transformation θ _R four times (for four stages) as shown in the above equation (13).

Here, describing the input to the function F _R X, the output from the function F _R as Y.

  In the present embodiment, X and Y are 64-bit data.

First, in the non-linear transformation γ _R , the value X is divided into 8-bit sub data (s ₀ , s ₁ ,..., S ₇ ), and each sub data divided is expressed by the following equation (24): As shown in FIG. 5, nonlinear conversion is performed using the replacement table S-box. Here, it is assumed that the converted sub data is s ′ ₀ , s ′ ₁ ,..., S ′ ₁₅ .

  In addition, what is necessary is just to use what is shown by said (7), for example as replacement table S-box.

Next, in byte replacement π _R , as shown in the following equation (25), two rows of sub-data (s ′ ₀ , s ′ ₁ ,..., S ′ ₇ ) converted by nonlinear conversion γ _R are stored in two rows. As a four-column matrix, the data is exchanged so that the data in each row included in each column is arranged in a different column. Equation (25) is an example, and other replacement methods can be adopted as long as the data of each row included in each column is arranged in a different column.

Further, the sub-data of the converted _{s "0, s" 1,} ···, and s _"7.

Next, in the matrix transformation θ _R , as shown in the following equation (26), the sub-data (s ″ ₀ , s ″ ₁ ,..., S ″ ₇ ) after the transformation with the byte replacement π _R described above. Is converted by performing multiplication on a finite field GF (2 ⁸ ) of a matrix of 2 rows and 4 columns and a conversion matrix B. Here, the converted sub-data is expressed as y ₀ , Let y ₁ ,..., y ₇ .

  Here, the transformation matrix B is included in an input column and an output column when a column is an input column and a column of values after the transformation by the transformation matrix B is performed on the input column is an output column. Any conversion matrix may be used as long as the number of terms whose values are not “0” is three or more.

Then, the sub data (y ₀ , y ₁ ,..., Y ₇ ) calculated in this way is converted into sub data (s ₀ , s ₁ ,. ₇ ), the sub-data (y ₀ , y ₁ ,..., Y ₇ calculated by performing the transformation by the nonlinear transformation γ _R , the byte substitution π _R and the matrix transformation θ _R three times (total four times). ) (27) by concatenating as type, the output Y of the function _{F R.}

In more functions F _R, as compared with the function F _K described above, for performing the output in four processing for one input, it is possible to enhance the safety. Note that the number of these four times can be changed as appropriate.

  Returning to FIG. 11, the stirring unit 226 performs a process of calculating a plaintext round value in each round.

For example, calculation of plaintext round value by stirring section 226 is performed using the plaintext round value transformation function f _R as shown in FIG.

As shown in FIG. 5, the plaintext round value conversion function f _R is converted into a plaintext round value x ^{(r−1) of the} ( ^r−1) -th round (however, when r = 0, it is blocked by the message blocking unit 222). The message block M ′ _i ) is divided into eight (in this embodiment, 32 bits each), which is divided data x ₀ ^(r−1) , x ₁ ^(r−1) , x ₂ ^(r−1) , x ^{_{3 (r-1), x}} 4 (r-1), x 5 (r-1), x 6 (r-1), x 7 a ^{(r-1), _{respectively, x 0 (r), x}} 1 ^(R) , x ₂ ^(r) , x ₃ ^(r) , x ₄ ^(r) , x ₅ ^(r) , x ₆ ^(r) , x ₇ ^(r), and these converted values are concatenated By doing so, it is a function that generates the plaintext round value x ^(r) of the r-th round.

Regarding process using plaintext round value transformation function f _R is the number of bits are different only because it is similar to the first embodiment, the detailed description thereof is omitted.

Further, since the function F _R is F function used in the stirring section 226 is similar to the function F _R is F function used in the second round-key generation unit 225, a description thereof will not be given.

  The hash value calculation process in this embodiment can also be performed in the same manner as in FIG.

  First, the hash value generation device 200 receives an input of a message M for generating a hash value via the input unit 130, and the overall control unit 221 of the hash value generation device 200 inputs the message M to the message blocking unit 222. To do.

Then, the message blocking unit 222 pads the message M and divides it into 256-bit message blocks (M ′ ₀ ,..., M ′ _k ; k is an integer of 1 or more).

Next, the overall control unit 221 determines the first message among the initial value H _{−1 of the} calculated value stored in the initial value storage area 211 and the message block M _i ′ blocked by the message blocking unit 222. By inputting the block M ′ ₀ to the first block cipher f _E , the plaintext round value h ₀ is calculated.

Here, the processing using the first block cipher f _E is performed by the round constant generation unit 223, the first round key generation unit 224, and the stirring unit 226.

Then, the overall control unit 221 calculates an exclusive OR of the calculated plaintext round value h ₀ and the message block M ′ ₀ to obtain a calculated value, and calculates the calculated value and the next message block By inputting M ′ ₁ into the block cipher f _E , the plaintext round value h ₁ is calculated. Note that the calculated value is stored in the calculated value storage area 115.

By repeating such processing up to the message block M ′ _k−1 immediately before the last message block M ′ _k , the plaintext round value h _k−1 is calculated.

Then, the overall control unit 221 determines the calculated value calculated by exclusive OR of the plaintext round value h _k−1 and the message block M ′ _k−1 and the last message block M ′ _k . By inputting to the two-block cipher f ′ _E , the plaintext round value h _k is calculated.

Here, processing using the second block cipher f ′ _E is performed by the round constant generation unit 223, the second round key generation unit 225, and the stirring unit 226.

Then, the overall control unit 221 calculates a hash value H _k by exclusive OR of the plaintext round value h _k and the last message block M ′ _k .

Such a hash value H _k is stored in the hash value storage area 216.

Here, the processing in the first block cipher f _E and the processing in the second block cipher f ′ _E are the same as the processing in FIG. 8 and FIG. .

  As described above, according to the present embodiment, a 256-bit hash value can be calculated.

  Here, the following equation (28) using the minimum number of active S-boxes is used as an index of resistance to the differential attack linear attack.

In this regard, in the F function of AES (Advanced Encryption Standard) type, when the two stages of active S-box number is B, the active S-box number of four stages becomes ^{B 2.} In this way, such a technique for improving safety by stacking four S-boxes is called WTS (Wide Trail Strategy).

On the other hand, for example, in the Feistel structure as shown in FIG. 5, there is a process of adding the output of the F function to X ₆ ^(r−1) and X ₇ ^(r−1). WTS that increases the number of function stages cannot be adopted.

In this regard, in the present invention, in the function F _R that is an F function used in the plaintext round value conversion function f _R , the composite conversion of the second nonlinear conversion γ _R , the byte replacement π _R, and the matrix conversion θ _R is performed. Safety is ensured by performing it four times (four steps).

For example, in the hash value generation device 100 that generates a 512-bit hash value in the first embodiment of the present invention, since the minimum number of active S-boxes for two stages is “B = 5”, there is one F function. The minimum number of active S-boxes per hit is “B ² = 25”.

  Since there are at least five F functions active in 12 stages, the minimum value of the number of active S-boxes is “5 × 25 = 125”.

  Accordingly, since the maximum differential propagation probability is “125 × 6 (= 750)> 512”, it can be seen that the formula (28) is satisfied and the system is resistant to differential attacks.

Further, in the hash value generation device 200 that generates a 256-bit hash value in the second embodiment of the present invention, since the minimum number of active S-boxes for two stages is “B = 3”, there is one F function. The minimum number of active S-boxes per hit is “B ² = 9”.

  Since there are at least five F functions active in 12 stages, the minimum value of the number of active S-boxes is “5 × 9 = 45”.

  Therefore, since the maximum differential propagation probability is “45 × 6 (= 270)> 256”, it is understood that the formula (28) is satisfied and the system is resistant to differential attacks.

  The WTS is described in detail in the following document 2.

Reference 2: J. Daemen and V. Rijmen, Springer, 2002, February, “The Design of Rijndael”, pp. 123-147
In the first embodiment and the second embodiment described above, 512-bit and 256-bit hash values are calculated, respectively, but the present invention is not limited to this mode. It is also possible to calculate a hash value having another bit length such as 224 bits or 384 bits by appropriately changing the bit length.

  Furthermore, in the embodiment described above, the hash value generation devices 100 and 200 can be realized by the computer 900 as shown in FIG. 6, but the present invention is not limited to such an aspect. Alternatively, it can be realized in a small-scale device such as a mobile phone terminal, a non-contact type IC card, and a product tag provided with a non-working memory.

  Further, the hash value generation apparatuses 100 and 200 described above may not be realized by a computer executing a program. For example, it may be executed in hardware by an integrated logic IC such as ASIC (Application Specific Integrated Circuit) or FPGA (Field Programmable Gate Array), or may be software by a computer such as DSP (Digital Signal Processor). May be executed automatically.

In the embodiment described above, the use of the plain round value transformation function f _R as shown in FIG. 5, is not limited to such a mode, as long as the function is used F _R as F function Anything may be used. For example, it is also possible to use plain round value transformation function f _R as shown in FIG. 12 (a schematic diagram showing a plain round value transformation function f _R variant).

In the plaintext round value conversion function f _R shown in FIG. 12, x ₄ ^(r ) of the round key K ^(r) and the plaintext round value of the (r−1 ⁾ -th round (message block M ′ _{i in} the case of r = 0). an exclusive OR is a value _{p H} ^-1), the case of the plaintext round value of r-1 rounds (r = 0, _x ⁵ value of ^(r-1) of the message block M _'i) The value q _H (q _H = F _R (x ₄ ^(r ₄ )) of the higher-order bits (here, the higher-order 64 bits) of the output value input to the function F _R which is the F function is the value p obtained by concatenating p _{L ^{-1) XOR K (r),}} x 5 and _{^{(r-1)) H)}} , the lower bits (here, the value _q L of the lower 64 ^{_{bits) (q L = F R (}} x 4 (r-1) XOR K ^{_(r), x 5} and _{^{(r-1)) L)}} , is calculated.

Then, an exclusive OR of the values _{p H} and a value _{q H,} (in the case of r = 0, the message block M _'i) the plaintext round value of r-1 rounds _x ⁶ of the ^(r-1) , And the calculated value is x ₀ ^(r) of the ^r-th plaintext round key.

Further, the exclusive OR of the values _{p L} and the value _{q L,} (in the case of r = 0, the message block M _'i) the plaintext round value of r-1 rounds _x ⁷ of the ^(r-1) , And the calculated value is defined as x ₁ ^(r) of the plaintext round value of the r-th round.

By using the plaintext round value transformation function f _R as shown in FIG. 12, by feed forward the input to the output of the F function, it is possible to break the substitution of F function parts.

Further, instead of the plain round value transformation function f _R as shown in FIG. 5, for example, plaintext round value transformation function f _R as shown in FIG. 13 (a schematic diagram showing a plain round value transformation function f _R variant) It is also possible to use it.

In the plaintext round value conversion function f _R shown in FIG. 13, x ₄ ^(the message block M ′ _{i in} the case of r = 0 ⁾ and the round key K ₀ ^(r) and the plaintext round value of the (r−1 ⁾ -th round. a value p _H which is an exclusive OR of ^r−1) , a round key K ₁ ^(r) and a plaintext round value of the (r−1 ⁾ -th round (if r = 0, message block M ′ _i ) x 5 and a value p _L is exclusive of ^_(r-1), the upper bits of the output value of the value p which is connected to the input to the function F _R is F function (in this case, the upper 64 bits) Q _H (q _H = F _R (x ₄ ^(r−1) XOR K ₀ ^(r) , x ₅ ^(r−1) XOR K ₁ ^(r) ) _H ) and lower bits (here, lower the value _q L of 64 ^{_{bits) (q L = F R (}} x 4 (r-1) XOR K (r), x 5 (r- ⁾ XOR K ₁ and _{^(r)) L),} is calculated.

Here, the round key K ₀ ^(r) uses k ₂ ^(r) in the key round value of the r-th round, and the round key K ₁ ^(r) is k in the key round value of the r-th round. ₃ ^(r) is used.

By using the plaintext round value transformation function f _R as shown in FIG. 13, it is possible to round keys to a size more than twice.

1 is a schematic diagram of a hash value generation device according to a first embodiment. Schematic diagram of a linear transformation function f _c. Schematic view of a first key round value conversion function f _K. Schematic view of a second key round value transformation function f _'K. Schematic diagram of plaintext round value transformation function f _R. Schematic diagram of a computer. Schematic which shows the calculation process of a hash value. Schematic diagram showing the process in the first block cipher f _E. Schematic diagram showing the process of the second block cipher f _'E. The flowchart which shows the production | generation process of the hash value in a hash value production | generation apparatus. The schematic diagram of the hash value generation device which is a second embodiment. Schematic diagram showing a plain round value transformation function f _R modification. Schematic diagram showing a plain round value transformation function f _R modification.

Explanation of symbols

100, 200 Hash value generator 110, 210 Storage unit 111, 211 Initial value storage area 112 Constant round value storage area 113 Key round value storage area 114 Plain text round value storage area 115 Calculated value storage area 116 Hash value storage area 120, 220 Control units 121, 221 Overall control unit 122, 222 Message blocking unit 123, 223 Round constant generation unit 124, 224 First round key generation unit 125, 225 Second round key generation unit 126, 226 Agitation unit

Claims (17)

The message is changed to a block having a predetermined data length, specific divided data among a plurality of divided data obtained by dividing the block is converted by the F function, and exclusive OR with other specific divided data is performed. A hash value generation device that generates a hash value of the message using a block cipher including a stirring process to calculate,
In the F function, including a control unit that performs conversion including at least nonlinear conversion a plurality of times,
A hash value generator characterized by the above. The hash value generation device according to claim 1,
The F function is a combination of non-linear transformation, byte replacement, and matrix transformation that is performed multiple times;
A hash value generator characterized by the above. The hash value generation device according to claim 2,
The plurality of times is four times;
A hash value generator characterized by the above. The hash value generation device according to claim 2,
The nonlinear conversion is to perform conversion by extracting data after conversion corresponding to the data before conversion from a predetermined replacement table;
A hash value generator characterized by the above. The hash value generation device according to claim 2,
The byte replacement is to perform conversion in which each item included in an arbitrary column is arranged in a different column in a matrix having data before conversion as items,
A hash value generator characterized by the above. The hash value generation device according to claim 4,
The matrix conversion is performed by multiplying a matrix having data before conversion as an item by multiplying the conversion matrix by each item included in an arbitrary column of the matrix and a column corresponding to the arbitrary column in the matrix after multiplication. The number of items included in the item and the number of items that are not zero in the item is greater than or equal to a predetermined number,
A hash value generator characterized by the above. The hash value generation device according to claim 6,
In the case of generating a 512-bit hash value, the number is 5.
A hash value generator characterized by the above. The hash value generation device according to claim 6,
In the case of generating a 256-bit hash value, the number is 3.
A hash value generator characterized by the above. The computer sets the message to a block having a predetermined data length, converts the specific divided data among a plurality of divided data obtained by dividing the block by the F function, and is exclusive with other specific divided data. A program that functions as a hash value generation device that generates a hash value of the message using a block cipher including agitation processing for calculating a logical sum,
Causing the computer to function as a control unit that performs conversion including at least nonlinear conversion a plurality of times in the F function;
A program characterized by The program according to claim 9, wherein
The F function is a combination of non-linear transformation, byte replacement, and matrix transformation that is performed multiple times;
A program characterized by The program according to claim 10,
The plurality of times is four times;
A program characterized by The program according to claim 10,
The nonlinear conversion is to perform conversion by extracting data after conversion corresponding to the data before conversion from a predetermined replacement table;
A program characterized by The program according to claim 10,
The byte replacement is to perform conversion in which each item included in an arbitrary column is arranged in a different column in a matrix having data before conversion as items,
A program characterized by A program according to claim 12,
The matrix conversion is performed by multiplying a matrix having data before conversion as an item by multiplying the conversion matrix by each item included in an arbitrary column of the matrix and a column corresponding to the arbitrary column in the matrix after multiplication. The number of items included in the item and the number of items that are not zero in the item is greater than or equal to a predetermined number,
A program characterized by The program according to claim 14, wherein
In the case of generating a 512-bit hash value, the number is 5.
A program characterized by The program according to claim 14, wherein
In the case of generating a 256-bit hash value, the number is 3.
A program characterized by The message is converted into a block having a predetermined data length, specific divided data among a plurality of divided data obtained by dividing the block is converted by the F function, and exclusive OR with other specific divided data is performed. A hash value generation method performed by a hash value generation device that generates a hash value of the message using a block cipher including a stirring process to calculate,
The control unit of the hash value generation device includes a process of performing a transformation including at least a nonlinear transformation a plurality of times in the F function;
A hash value generation method characterized by

Images