WO2013175599A1

WO2013175599A1 - Hash value calculation device, hash value calculation method, and hash value calculation program

Info

Publication number: WO2013175599A1
Application number: PCT/JP2012/063259
Authority: WO
Inventors: 祐介内藤
Original assignee: 三菱電機株式会社
Priority date: 2012-05-24
Filing date: 2012-05-24
Publication date: 2013-11-28

Abstract

The purpose of the present invention is to maintain sufficient stability and configure efficient functions. s[1] of r' bit is calculated by using A[1] and having IV1 of r' bit and m[1] as inputs; and t[1] is calculated by using a replacement function (P) and having s[1] and c' bit IV2 as inputs. Using t[1] as x[1], x[1] is divided into z[1] of r'' bit and y[1] of c'' bit, and x[2] is calculated by using the replacement function (P) and having z[1] and y[1] as inputs. From k=2 to i', z'[k] is calculated by using B[k] and having y[k] of c'' bit among x[k] and y[k-1] as inputs, and x[k+1] is calculated by using the replacement function (P) and having z[k] of r'' bit for the remainder of x[k] and y[k] as inputs. z[1] , z[k] for all k, and z'[k] are associated and become the hash values.

Description

Hash value calculation device, hash value calculation method, and hash value calculation program

This invention relates to a technique for calculating a highly secure hash value, for example.

Hash function is a function that takes an arbitrary length value as input and outputs a fixed length hash value.

Non-Patent Document 1-5 describes a hash function using a replacement function that satisfies the properties of a pseudo-random oracle. The hash functions of Non-Patent Documents 1-4 can freely change the hash length. The hash function of Non-Patent Document 5 cannot change the hash length freely.
Here, in order for the hash function in Non-Patent Documents 1-5 to satisfy the properties of a pseudo-random oracle, the replacement function to be used needs to be an idealized replacement function.

The hash function described in Non-Patent Documents 1-4 is a replacement function in which the replacement function to be used is idealized. When the input / output length is b bits and the message size is r bits, the pseudo-random oracle property is obtained. And the safety level is O (2 ^{(br) / 2} ).
However, this hash function is not computationally efficient when a long hash value is required.

The hash function described in Non-Patent Document 5 is an idealized replacement function. When the input / output length is b bits and the message size is b / 2 bits, the pseudo-random oracle property is obtained. Satisfaction and safety level is O (2 ^{b / 6} ).
However, a calculation method when a long hash value is required has not been proposed. However, a long hash value can be obtained by combining this hash function and the method of Non-Patent Document 6. However, in this case, the efficiency is deteriorated.
In addition, this hash function has a fixed message size of b / 2 bits and is less secure than the hash functions described in Non-Patent Documents 1-4.

An object of the present invention is, for example, to construct a function that can be as secure as the system of Non-Patent Documents 1-4 and is more efficient than the system of Non-Patent Documents 1-4. To do.

The hash value calculation device according to the present invention is:
a default length value input unit for inputting a value m [1] of r ′ bit length (r ′ is an integer of 1 or more);
The function A [1] is calculated by using the fixed value IV1 of r ′ bit length and the value m [1] as input to obtain the value s [1] of r ′ bit length, and the obtained values s [1] and c A leading function calculation unit for calculating a replacement function by inputting a fixed value IV2 of 'bit length (c' is an integer equal to or greater than 1) 'to obtain (r' + c ') bit length value t [1];
With value t [1] as value x [1], value z [1] from value x [1] to r ″ bit length (r ″ is an integer of 1 or more) and value x [1] to value z The value y [1] of c ″ bit length excluding [1] (c ″ is an integer equal to or greater than 1 and r ′ + c ′ = r ″ + c ″) is cut out and the value z [1 ] And the value y [1] as inputs to calculate a replacement function (r ″ + c ″) to obtain a bit length value x [2], and from k = 2 to i ′ (i ′ is 1 or more) The value z [k] of r ″ bit length is extracted from the value x [k] in order up to an integer), and the value c [bit length y [k] of the value x [k] minus the value z [k] is extracted. The function B [k] is calculated by inputting the value y [k−1] and the value y [k−1] to obtain the value c′-bit length z ′ [k], and the value z [k] and the value y [k] are input. An output function calculation unit for calculating a replacement function to obtain a value x [k + 1] of (r ″ + c ″) bit length;
A hash value calculation unit that calculates a hash value Z by combining the value z [1], the value z [k] from k = 2 to i ′, and the value z ′ [k]. .

The hash value calculation device according to the present invention satisfies the properties of the pseudo-random oracle and has the same security as the methods of Non-Patent Documents 1-4 if the replacement function to be used is an idealized replacement function. Can be configured more efficiently than the methods disclosed in Non-Patent Documents 1-4.

FIG. 3 is a functional block diagram illustrating functions of the hash value calculation device 10 according to the first embodiment. 3 is a flowchart showing the operation of the hash value calculation apparatus 10 shown in FIG. FIG. 3 is a structural diagram (1) of a hash function realized by the hash value computing device 10 shown in FIG. 1. FIG. 2 is a structural diagram (2) of a hash function realized by the hash value computing device 10 shown in FIG. 1.

Embodiment 1 FIG.
First, the concept of security of the hash function will be described.

A hash function that satisfies the characteristics of a random oracle is an idealized hash function.
The hash function H satisfying the characteristics of the random oracle is a hash function to which the following 1 and 2 are given.
1. (List): A list in which pairs of all input values and output values randomly selected for each input value are recorded.
2. (Oracle that outputs a value in the forward direction): Oracle that outputs the value z by searching the output value z for the input value x from the list for the input value x. That is, it is an oracle that outputs a value z such that H (x) = z.

A hash function that satisfies the properties of a random oracle satisfies the following three properties: “(1) collision difficulty”, “(2) second original image calculation difficulty”, and “(3) original image calculation difficulty”.
Definitions of the properties (1) to (3) are as follows. In the following definition, “H” indicates a hash function. “M” and “M ′ (≠ M)” indicate input values of the hash function H. “H (x)” indicates an output (hash value) of the hash function H to which x is input.

(1) A hash function that satisfies the collision difficulty is a hash function in which it is difficult to find two input values M and M ′ that satisfy “H (M) = H (M ′)”. That is, the collision difficulty is a property that it is difficult to obtain a plurality of input values having the same hash value.
(2) A hash function satisfying the second original image calculation difficulty is to find an input value M ′ satisfying “H (M) = H (M ′)” when a random input value M is given. It is a difficult hash function. That is, the second original image calculation difficulty is a property that it is difficult to obtain a second input value having the same hash value as the first input value.
(3) A hash function satisfying the original image calculation difficulty is a hash function in which it is difficult to find M satisfying “z = H (M)” when a random value z is given. That is, the original image calculation difficulty is a property that it is difficult to obtain an input value corresponding to a hash value.

(1) to (3) The properties are as follows: (1) A hash function that satisfies the collision difficulty (2) satisfies the second original image calculation difficulty, and (2) a hash function that satisfies the second original image calculation difficulty There is a relationship that (3) the original image calculation difficulty is satisfied.
In addition, (3) a hash function (hash function that does not satisfy the original image calculation difficulty) whose original image calculation difficulty is broken has (1) collision difficulty and (2) second original image calculation difficulty. There is a relationship of not satisfying. That is, a hash function whose original image calculation difficulty has been broken is a function that does not satisfy the properties (1) to (3) that should be satisfied by a secure hash function, and is generally unusable because of its low security.

Standard public key cryptography, RSA-OAEP (RSA-Optical Encryption Padding), which is a digital signature algorithm, RSA-KEM (RSA-Key Encapsulation Mechanism), RSA-PSS (RSA-Probabilistic Science), etc. It is safe to assume that the hash function satisfies random oracle properties.
However, it is known that it is difficult to realize a hash function that satisfies the characteristics of a random oracle. Therefore, when implementing these public key cryptography and digital signature algorithms, hash functions such as SHA-256 (Secure Hash Algorithm-256) are used instead of hash functions satisfying the characteristics of random oracle.

When the above-described public key cryptography and electronic signature algorithm are implemented using a hash function that does not satisfy the characteristics of a random oracle, the security is not necessarily guaranteed. However, there is a concept of pseudo-random oracle as a concept for guaranteeing the safety.
Here, an internal function used in the hash function is P, and a hash function configured using P is H [P]. The fact that H [P] satisfies the property of pseudo-random oracle means that there exists a simulator S that simulates P such that any discriminator cannot distinguish H [P] from a hash function that satisfies the property of random oracle. It is.

If H [P] satisfies the properties of pseudo-random oracle, H [P] satisfies the properties of (1) collision difficulty, (2) second original image calculation difficulty, and (3) original image calculation difficulty. . A cryptographic algorithm that is secure when using a hash function that satisfies the characteristics of a random oracle is guaranteed to be secure even when H [P] is used.

The replacement function (P, Pinv) is a set of a forward calculation function P and a backward calculation function Pinv. The forward calculation function P and the backward calculation function Pinv take a predetermined d-bit value as input and output a d-bit value.
The idealized replacement function is a replacement function when one replacement function is selected at random from a set of all replacement functions.

It is known that it is difficult to realize an idealized replacement function. Therefore, when realizing a hash function that satisfies the properties of a pseudo-random oracle, such as the hash function described in Non-Patent Document 1-5, instead of an idealized replacement function, addition, shift, multiplication, table reference, etc. It is conceivable to use a permutation function realized using.
In this case, since the idealized replacement function is not used, the obtained hash function does not become a hash function that satisfies the properties of the pseudo-random oracle. However, since it has been proved that the pseudo-random oracle properties are satisfied when an idealized replacement function is used, it is recognized that there is a certain degree of safety.

In the following description, a hash function using a replacement function will be described in the same manner as the hash function described in Non-Patent Documents 1-5. Similar to the hash functions described in Non-Patent Documents 1-5, the hash function described below satisfies the property of a pseudo-random oracle when the replacement function to be used is an idealized replacement function.
However, the hash function described below satisfies the same safety as the hash function described in Non-Patent Document 1-4, and calculates a hash value longer than the hash function described in Non-Patent Document 1-4 at high speed. Is possible.

FIG. 1 is a functional block diagram illustrating functions of the hash value calculation device 10 according to the first embodiment.
FIG. 2 is a flowchart showing the operation of the hash value calculation apparatus 10 shown in FIG.
3 and 4 are structural diagrams of a hash function realized by the hash value calculation device 10 shown in FIG. FIG. 4 shows the continuation of the processing of FIG.

The function and operation of the hash value calculation apparatus 10 shown in FIG. 1 will be described with reference to FIGS.
The hash value calculation device 10 shown in FIG. 1 includes an arbitrary length value input unit 11, a padding unit 12, a division unit 13, a predetermined length value input unit 14, a function calculation unit 15, and a hash value calculation unit 16. The function calculation unit 15 includes a head function calculation unit 151, a subsequent function calculation unit 152, and an output function calculation unit 153.

Note that the function calculation unit 15 performs the functions A [1],. . . , A [i] and functions B [2],. . . , B [i ′] and the function P.
The function A [1] is a function that receives two r′-bit length values (r ′ is an integer of 1 or more) and outputs an r′-bit length value. The function A [1] is, for example, a function that calculates x + y and truncates the bits after the r ′ + 1th bit and outputs an exclusive OR of x and y, where x and y are r′-bit length values. Is a function that calculates and outputs.
Functions A [2],. . . , A [i] is a function that inputs two r-bit length values (r is an integer of 1 or more) and outputs an r-bit length value. Functions A [2],. . . , A [i], for example, if x and y are r-bit length values, calculate x + y and round off the output from the (r + 1) th bit and calculate the exclusive OR of x and y. Function to output.
Functions B [2],. . . , B [i ′] is a function that inputs two c ″ bit length values (c ″ is an integer of 1 or more) and outputs two c ″ bit length values. Functions B [2],. . . , B [i ′] is, for example, a function that calculates x + y and truncates the bits after c ″ +1 bits and outputs them when x and y are c ″ -bit length values, and exclusive of x and y This function calculates and outputs a logical OR.
The function P is a forward calculation function in the above-described replacement function, and receives a d-bit length value and outputs a d-bit length value. In the following description, c, c ′, and r ″ are integers of 1 or more, and d = r + c = r ′ + c ′ = r ″ + c ″.

(S1: Arbitrary length input step)
The arbitrary length value input unit 11 inputs an arbitrary bit length value M by an input device.

(S2: Padding step)
The padding unit 12 uses the padding function pad to generate the value M * of r ′ + (i−1) r bit length for the value M input in (S1) by the processing device. Note that i is an integer of 1 or more. However, the padding unit 12 generates the value M * so that the last r bits are not all zero.
For example, the padding unit 12 adds 1 after the value M, and then adds 0 to the required number of bits to obtain a value M * of r ′ + (i−1) r bit length. That is, M * = M || 1 || 0,. . . , 0. When all the last r bits are 0 by this method, at least one bit of the last r bits may be set to 1.

(S3: Division step)
The dividing unit 13 cuts r ′ + (i−1) r-bit length value M * generated in (S2) by r′-bit from the head and sets the value to m [1]. Further, the dividing unit 13 divides the remaining (i−1) r-bit length values into i−1 pieces for each r bits in order from the top, and values m [2],. . . , M [i−1].

(S4: Default length input step)
The predetermined length value input unit 14 receives the r ′ bit length value m [1] generated by the dividing unit 13 and the i−1 values m [2],. . . , And the value m [i].

(S5: Function calculation step)
The function calculation step includes three steps from (S51) to (S53).
(S51: First function calculation step)
The head function calculation unit 151 calculates the function A [1] with the processing device as input using the fixed value IV1 of r ′ bit length and the value m [1] of r ′ bit length, and the value s of r ′ bit length. [1] is obtained. Then, the head function calculation unit 151 calculates the replacement function P by using the obtained value s [1] and the fixed value IV2 of c ′ bit length as input by the processing device, and (r ′ + c ′) a bit length value. t [1] is obtained.

(S52: Subsequent function calculation step)
The subsequent function calculation unit 152 executes the following processing in order from j = 2 to i.
The subsequent function calculation unit 152 divides the value t [j−1] into the leading r-bit length value u [j] and the remaining c-bit length value v [j] by the processing device. Next, the succeeding function calculation unit 152 calculates the function A [j] by using the r-bit length value u [j] and the r-bit length value m [j] as inputs by the processing device, and calculates the r-bit length. The value s [j] is obtained. Then, the subsequent function calculation unit 152 calculates the replacement function P by using the value s [j] of the r-bit length and the value v [j] of the c-bit length as input, and (r + c) the value of the bit length. t [j] is obtained.

(S53: Output function calculation step)
The output function calculation unit 153 sets the value t [i] as the value x [1].
The output function calculation unit 153 divides the value x [1] into the leading r ″ bit length value z [1] and the remaining c ″ bit length value y [1] by the processing device. Next, the output function calculation unit 153 calculates the replacement function P by using the value z [1] and the value y [1] as inputs, and (r ″ + c ″) the bit length value x [. 2].
Subsequently, the output function calculation unit 153 executes the following processing in order from k = 2 to i ′ (i ′ is an integer of 1 or more).
The output function calculation unit 153 divides the value x [k] into the first r ″ bit length value z [k] and the remaining c ″ bit length value y [k] by the processing device. Next, the output function calculation unit 153 calculates the function B [k] by using the c ″ bit length value y [k] and the c ″ bit length value y [k−1] as inputs by the processing device. Then, a c ″ bit length value z ′ [k] is obtained. Then, the output function calculation unit 153 calculates the replacement function P using the value z [k] and the value y [k] as inputs, and (r ″ + c ″) the bit length value x [k + 1]. Ask for.

(S6: Hash value calculation step)
The hash value calculation unit 16 combines the value z [1] calculated in S53, the value z [k] from k = 2 to i ′, and the value z ′ [k] using a combination function by the processing device. To calculate the hash value Z.

In the above description, in S52, the value t [j-1] is divided into the leading r-bit length value u [j] and the remaining c-bit length value v [j]. However, the value u [j] need not be the first r bits of the value t [j-1], but may be an r-bit value extracted from the value t [j-1]. The value v [j] may be a value consisting of the remaining c bits obtained by removing the value u [j] from the value t [j-1].
Similarly, in the above description, in S53, the value x [k] is divided into the leading r ″ bit length value z [k] and the remaining c ″ bit length value y [k]. However, the value z [k] need not be the first r ″ bits of the value x [k], but may be a value of r ″ bits extracted from the value x [k]. The value y [k] may be a value composed of the remaining c ″ bits obtained by removing the value z [k] from the value x [k].

Also, the number of repetitions i ′ of the process in S53 is determined by the number of bits necessary as a hash value. That is, the process of S53 may be repeated until the total number of bits of the value z [k] and the value z ′ [k] reaches the number of bits necessary as the hash value.

In the above description, the case where i is 2 or more has been described. However, when i is 1, S52 is not executed, and the value t [1] is set to the value x [1] in S53.

The hash value calculation device 10 described above is configured by, for example, a circuit or software. In the case of a circuit, the processing device in the above description is, for example, an arithmetic circuit, and the storage device is, for example, a register. When configured by software, the processing device in the above description is, for example, a CPU (Central Processing Unit), and the storage device is, for example, a RAM (Random Access Memory). The input device in the above description is, for example, a keyboard or a communication board, and the output device is a display device such as an LCD (Liquid Crystal Display), a communication board, or a storage device such as a register or RAM. Of course, it is not limited to these.
When the hash value calculation device 10 is configured by a circuit, the above-described “˜unit” may be read as “˜circuit”. Further, the above-described “˜part” may be read as “˜processing”, “˜apparatus”, “˜apparatus”, “˜means”, “˜procedure”, and “˜function”. That is, what is described as “˜unit” may be realized by firmware stored in a ROM (Read Only Memory). Alternatively, it may be realized only by software, only hardware such as an element, a device, a board, and wiring, or a combination of software and hardware, or further a combination of firmware.

As described above, the hash value calculation apparatus 10 according to the first embodiment processes an r-bit length message in the subsequent process (S52), whereas an r′-bit length message is processed in the head process (S51). To process. For this reason, it is possible to lengthen the message that can be processed in the head process.
Further, the hash value calculation device 10 according to the first embodiment calculates a hash value using all the output values of the replacement function in the output process (S53).
Therefore, the hash value calculation device 10 according to Embodiment 1 can calculate a hash value at high speed.

In addition, by setting c ′ and c ″ to be c / 2 or more, the hash value calculation apparatus 10 according to Embodiment 1 can simulate the pseudo-bit replacement function if the replacement function to be used is an idealized b-bit input / output replacement function. It is possible to construct a hash function that satisfies the characteristics of a random oracle and has a security level of O (2 ^{(br) / 2} ) = O ( ^{2c / 2} ).
The reason why c ′ and c ″ are set to c / 2 or more is that there are two attack methods that break the properties of the pseudo-random oracle, one with a calculation amount of 2 ^{c ′} and one with a calculation amount of 2 ^{c ″.} . By setting c ′ to c / 2 or more and c ″ to c / 2 or more, the amount of calculation by these attack methods becomes 2 ^{c / 2} and the level of safety becomes O (2 ^{c / 2} ).

10 hash value calculation device, 11 arbitrary length value input unit, 12 padding unit, 13 division unit, 14 default length value input unit, 15 function calculation unit, 151 head function calculation unit, 152 subsequent function calculation unit, 153 output function calculation unit 16 Hash value calculator.

Claims

a default length value input unit for inputting a value m [1] of r ′ bit length (r ′ is an integer of 1 or more);
The function A [1] is calculated by using the fixed value IV1 of r ′ bit length and the value m [1] as input to obtain the value s [1] of r ′ bit length, and the obtained values s [1] and c A leading function calculation unit for calculating a replacement function by inputting a fixed value IV2 of 'bit length (c' is an integer equal to or greater than 1) 'to obtain (r' + c ') bit length value t [1];
With value t [1] as value x [1], value z [1] from value x [1] to r ″ bit length (r ″ is an integer of 1 or more) and value x [1] to value z The value y [1] of c ″ bit length excluding [1] (c ″ is an integer equal to or greater than 1 and r ′ + c ′ = r ″ + c ″) is cut out and the value z [1 ] And the value y [1] as inputs to calculate a replacement function (r ″ + c ″) to obtain a bit length value x [2], and from k = 2 to i ′ (i ′ is 1 or more) The value z [k] of r ″ bit length is extracted from the value x [k] in order up to an integer), and the value c [bit length y [k] of the value x [k] minus the value z [k] is extracted. The function B [k] is calculated by inputting the value y [k−1] and the value y [k−1] to obtain the value c′-bit length z ′ [k], and the value z [k] and the value y [k] are input. An output function calculation unit for calculating a replacement function to obtain a value x [k + 1] of (r ″ + c ″) bit length;
A hash value calculation unit that calculates a hash value Z by combining the value z [1], the value z [k] from k = 2 to i ′, and the value z ′ [k]. Hash value arithmetic unit.
The predetermined length value input unit further includes (i−1) (i is an integer of 2 or more) r bit length (r is an integer of 1 or more) values m [2],. . . , Enter the value m [i],
The hash value calculation device further includes:
In order from j = 2 to i, a value u [j] of r-bit length is extracted from the value t [j−1], and the function A [j] is calculated by using the value u [j] and the value m [j] as inputs. Then, an r-bit length value s [j] is obtained, and the obtained value s [j] and the value t [j−1] minus the value u [j] (c is an integer of 1 or more) , R + c = r ′ + c ′ = r ″ + c ″) as input and a substitution function is calculated to obtain a (r + c) bit length value t [j]. ,
The output function calculation unit is configured to output the values m [2],. . . , M [i] is input, the value t [i] is set to the value x [1].
The hash value calculation device further includes:
An arbitrary length value input unit for inputting an arbitrary bit length value M;
A padding unit that adds a predetermined value to the value M input by the arbitrary length value input unit to generate a value M ′ of (r ′ + (i−1) × r) bit length;
The value M ′ generated by the padding unit is divided into a value m [1], a value m [2],. . . , A dividing unit that generates a value m [i],
The predetermined length value input unit includes a value m [1] generated by the dividing unit, a value m [2],. . . , The value m [i] is input.
The functions A [1],. . . , A [i] and the functions B [1],. . . , [I ′] is either a function that calculates the sum of two input values, truncates unnecessary bits and outputs, or a function that calculates and outputs an exclusive OR of two input values The hash value calculation device according to claim 2, wherein the hash value calculation device is provided.
The hash value calculation unit calculates a hash value Z by sequentially combining a value z [1], a value z [k] from k = 2 to i ′, and a value z ′ [k]. The hash value computing device according to any one of claims 1 to 4.
3. The hash calculation apparatus according to claim 2, wherein the c ′ and the c ″ are integers equal to or greater than c / 2.
The input device inputs a value m [1] of r ′ bit length (r ′ is an integer of 1 or more),
The processing device calculates the function A [1] by using the fixed value IV1 of r ′ bit length and the value m [1] as inputs to obtain the value s [1] of r ′ bit length, and the obtained value s [ 1] and a fixed value IV2 of c ′ bit length (c ′ is an integer equal to or greater than 1) as inputs, calculate a replacement function to obtain a value t [1] of (r ′ + c ′) bit length,
The processing device sets the value t [1] as the value x [1], the value z [1] from the value x [1] to r ″ bit length (r ″ is an integer of 1 or more), and the value x [1 ], The value y [1] of c ″ bit length (c ″ is an integer equal to or greater than 1 and r ′ + c ′ = r ″ + c ″) obtained by removing the value z [1], The permutation function is calculated with the value z [1] and the value y [1] as inputs to obtain the value ([r ″ + c ″) bit length value x [2], and from k = 2 to i ′ (i ′ Is an integer greater than or equal to 1), in order, the value z [k] of r ″ bit length is extracted from the value x [k], and the value of c ″ bit length is obtained by removing the value z [k] from the value x [k]. The function B [k] is calculated by taking y [k] and the value y [k−1] as inputs to obtain a c ″ -bit length value z ′ [k], and the value z [k] and the value y [k] ] As an input to calculate a replacement function (r ″ + c ″) to obtain a bit length value x [k + 1],
A hash value calculation, wherein the processing device calculates a hash value Z by combining a value z [1], a value z [k] from k = 2 to i ′, and a value z ′ [k]. Method.
a predetermined length value input process for inputting a value m [1] of r ′ bit length (r ′ is an integer of 1 or more);
The function A [1] is calculated by using the fixed value IV1 of r ′ bit length and the value m [1] as input to obtain the value s [1] of r ′ bit length, and the obtained values s [1] and c A head function calculation process for calculating a replacement function by inputting a fixed value IV2 of 'bit length (c' is an integer of 1 or more) and obtaining (r '+ c') bit length value t [1];
With value t [1] as value x [1], value z [1] from value x [1] to r ″ bit length (r ″ is an integer of 1 or more) and value x [1] to value z The value y [1] of c ″ bit length excluding [1] (c ″ is an integer equal to or greater than 1 and r ′ + c ′ = r ″ + c ″) is cut out and the value z [1 ] And the value y [1] as inputs to calculate a replacement function (r ″ + c ″) to obtain a bit length value x [2], and from k = 2 to i ′ (i ′ is 1 or more) The value z [k] of r ″ bit length is extracted from the value x [k] in order up to an integer), and the value c [bit length y [k] of the value x [k] minus the value z [k] is extracted. The function B [k] is calculated by inputting the value y [k−1] and the value y [k−1] to obtain the value c′-bit length z ′ [k], and the value z [k] and the value y [k] are input. An output function calculation process for calculating a replacement function to obtain a value x [k + 1] of (r ″ + c ″) bit length;
Causing the computer to execute a value z [1], a hash value calculation process for calculating the hash value Z by combining the value z [k] and the value z ′ [k] from k = 2 to i ′. A hash value calculation program.