JP5398353B2 - Hash value calculation device, hash value calculation method, and hash value calculation program - Google Patents

Description

  The present invention relates to a technique for efficiently calculating a hash value, for example.

  Non-Patent Document 1 describes that a random oracle cannot be strongly discriminated even if it is configured using an ideal compression function (WFILRO (Weaked Fixed Input Length Random Oracle)) whose unidirectionality is broken. There is a description of a zipper hash function that is a hash function.

  Non-Patent Document 2 discloses a double pipe hash function (double pipe pipe) that is a hash function that cannot be strongly discriminated from a random oracle even if it is configured using an ideal compression function with broken unidirectionality. (Hash function) is described.

Moses Liskov: Constructing an Ideal Hash Function from Week Ideal Compression Functions. Selected Areas in Cryptography 2006: 358-375 Stefan Lucks: A Failure-Friendly Design Principle for Hash Functions. ASIACRYPT 2005: 474-494 Mihir Bellare, Thomas Ristenpart: Multi-Property-Preserving Hash Domain Extension and the EMD Trans. ASIACRYPT 2006: 299-314 Shoichi Hirose, Je Hong Park, Aram Yun: A Simple Variant of the Merkle-Damgard Scheme with a Permutation. ASIACRYPT 2007: 113-129 Ueli Maurer, Renato Renner, and Clemens Hollenstainindifference impossibility impossibility, isl, and Nr4, N4, p4 Ralph C.I. Merkle / One Way Hash Functions and DES /, Crypto 1989, pp 428-446, LNCS 435 Springer 1990, ISBN 3-540-97317-6

Although the zipper hash function and the double pipe hash function described in Non-Patent Documents 1 and 2 are ideal compression functions with broken unidirectionality, they are hash functions that cannot be strongly distinguished from random oracles. The calculation efficiency is poor.
The present invention is, for example, a hash function that cannot be strongly distinguished from a random oracle even if it is configured using an ideal compression function with broken unidirectionality. The object is to construct a hash function that is more computationally efficient than the hash function.

The hash value calculation device according to the present invention is, for example,
i values p [1],. . . , A predetermined length input unit for inputting the value p [i],
The values p [1],. . . , Value p [i], i−1 values p [1],. . . , Value p [i−1] for each fixed value const [1],. . . , A fixed value const [i−1], and the values x [1],. . . , A fixed value adding unit that generates a value x [i−1] and stores it in the storage device;
In order from j = 1 to i−1, a value c [j−1] (value c [0] is a fixed value IV1) and a value x [j] generated by the fixed value adding unit are input. By obtaining a value c [j] that is a result of calculating the compression function h, a value c [i−1] is obtained and stored in the storage device;
A storage device that obtains a value c [i] that is a result of calculating a compression function h by using a fixed value IV2 and a value x [i] obtained by adding a value c [i-1] to a value p [i]. A compression function calculation unit stored in
And an output unit that outputs the value c [i] obtained by the compression function calculation unit.

  In the hash value calculation device according to the present invention, a fixed value is added to the input value to the compression function. This makes it possible to configure a hash function that cannot be strongly discriminated from a random oracle even when configured using an ideal compression function with broken unidirectionality. This hash function is more efficient than the zipper hash function or the double pipe hash function.

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 of a hash function realized by the hash value calculation device 10 shown in FIG. 1. The values p [1],. . . , A functional block diagram showing functions of the hash value computing device 10 according to the first embodiment to which a function of generating a value p [i] is added. 5 is a flowchart showing the operation of the hash value calculation device 10 shown in FIG. FIG. 5 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 4. FIG. 5 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 4 when performing a predetermined padding process. FIG. 5 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 4 when SHA-256 is used as a compression function. FIG. 4 is a functional block diagram showing functions of a hash value calculation device 10 according to the second embodiment. 10 is a flowchart showing the operation of the hash value calculation apparatus 10 shown in FIG. FIG. 10 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 9. The values p [1],. . . , A functional block diagram showing functions of the hash value computing device 10 according to the second embodiment to which a function of generating a value p [i] is added. 13 is a flowchart showing the operation of the hash value calculation device 10 shown in FIG. FIG. 13 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 12. FIG. 13 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 12 when a predetermined padding process is performed. FIG. 13 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 12 when a predetermined padding process is performed. FIG. 13 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 12 when SHA-256 is used as a compression function. FIG. 9 is a functional block diagram illustrating functions of a hash value computing device 10 according to a third embodiment. The flowchart which shows operation | movement of the hash value calculating apparatus 10 shown in FIG. FIG. 19 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 18. The values p [1],. . . , A functional block diagram showing functions of the hash value computing device 10 according to the third embodiment to which a function of generating a value p [i + 1] is added. The flowchart which shows operation | movement of the hash value calculating apparatus 10 shown in FIG. FIG. 22 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 21. FIG. 22 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 21 when a predetermined padding process is performed. FIG. 22 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 21 when SHA-256 is used as a compression function. FIG. 6 is a functional block diagram showing functions of a hash value computing device 10 according to a fourth embodiment. 27 is a flowchart showing the operation of the hash value calculation device 10 shown in FIG. FIG. 27 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 26. The values p [1],. . . , A functional block diagram showing functions of the hash value computing device 10 according to the second embodiment to which a function of generating a value p [i] is added. The flowchart which shows operation | movement of the hash value calculating apparatus 10 shown in FIG. FIG. 30 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 29. FIG. 30 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 29 when a predetermined padding process is performed. FIG. 30 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 29 when SHA-256 is used as a compression function. FIG. 6 is a functional block diagram showing functions of a hash value computing device 10 according to a fifth embodiment. 35 is a flowchart showing the operation of the hash value computing device 10 shown in FIG. FIG. 35 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 34. The values p [1],. . . , A functional block diagram showing functions of the hash value computing device 10 according to the fifth embodiment to which a function of generating a value p [i] is added. 38 is a flowchart showing the operation of the hash value calculation device 10 shown in FIG. FIG. 38 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37. FIG. 38 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37 when a predetermined padding process is performed. FIG. 38 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37 when a predetermined padding process is performed. FIG. 38 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37 when SHA-256 is used as a compression function. The figure which shows an example of the hardware constitutions of the hash value calculating apparatus.

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

The hash function is a function that takes an arbitrary length value as input and outputs a fixed length value.
There are the following three properties as properties to be satisfied by the hash function. Hereinafter, the hash function is H.
1. Collision resistance: It is difficult to find two values M and M ′ such that H (M) = H (M ′).
2. Second development difficulty: Second value calculation difficulty: it is difficult to find a value M ′ different from the value M for H (M) = H (M ′) for a random value M.
3. Development calculation difficulty: For a random value z, it is difficult to find a value M such that z = H (M).

The hash function is composed of a function called a compression function with a fixed input length and output length. A typical configuration of the hash function is an MD (Mercle-Damgard) structure.
The MD structure has the following configuration.
(Step 1) Apply the strength MD padding to the input M to create a value M ′ whose length is a multiple of m.
(Step 2) M ′ is changed to an m-bit value p [1],. . . , P [i].
(Step 3) Values p [1],. . . , P [i], c [j] = h (c [j−1], p [j]) is calculated. Here, c [0] is an n-bit fixed value. H is a compression function. The compression function h is a function that receives an n-bit value and an m-bit value as inputs and outputs an n-bit value.
(Step 4) Output C [i].

Encryption algorithms such as OAEP (Optical Asymmetry Encryption Padding) and PSS (Probabilistic Signature Scheme) using a hash function have been proved to be safe when using a random oracle that is an ideal function, not a hash function.
A random oracle is a list (memory) in which pairs of all input values and output values randomly selected for each input value are recorded in advance. This function is determined by subtracting.

  A cryptographic algorithm that is secure when the random oracle model is used is considered to be safe even if a secure hash function is used instead of the random oracle. Here, the secure hash function is a hash function that satisfies the above three properties.

However, in practice, a cryptographic algorithm that is secure when using a random oracle is not always secure when a secure hash function is used instead of the random oracle. That is, even if a cryptographic algorithm using a random oracle is safe, a cryptographic algorithm using a secure hash function is not always safe.
Actually, when a hash function is used instead of a random oracle for a cryptographic algorithm that is safe when using a random oracle, the hash function used is: The random oracle needs to be incapable of being strongly discriminated (see Non-Patent Document 5).
In other words, a cryptographic algorithm that has been proved to be safe when using a random oracle uses a hash function that cannot be strongly distinguished from a random oracle. That is, if a cryptographic algorithm using a random oracle is secure, a cryptographic algorithm using a hash function that cannot be strongly distinguished from a random oracle is safe.

  The hash function that cannot be strongly discriminated from the random oracle is, for example, EMD (Exploited Markle-Damgard), MDP (Mercle-Damard with Permutation), or the like.

Generally, a hash function that cannot be strongly discriminated from a random oracle like EMD or MDP is configured using a compression function (FILRO (Fixed Input Length Random Oracle)) idealized as a compression function. That is, a hash function typified by EMD or MDP cannot be so strongly discriminated from a random oracle when an idealized compression function (FILRO) is used as a compression function.
The idealized compression function (FILRO) is a compression function to which the following 1 and 2 are given.
1. (List): It has 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): For the input value (x, y), the output value z for the input is searched from the list, and the value z is output. That is, a value z satisfying f1 (x, y) = z is output.

In addition, as described in the background art, even if the configuration is made using an ideal compression function (WFILRO) whose unidirectionality is broken instead of an ideal compression function (FILRO), a random oracle And a so-called hash function that cannot be strongly discriminated (see Non-Patent Documents 1 and 2).
The ideal compression function (WFILRO) whose unidirectionality is broken is a compression function given 1-5.
1. (List): It has 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): For the input value (x, y), the output value z for the input is searched from the list, and the value z is output. That is, a value z satisfying f1 (x, y) = z is output.
3. (Oracle 1 that breaks unidirectionality): For the input value z, one pair is selected at random from all pairs of values (x, y) that satisfy f1 (x, y) = z, and the selected pair Is output.
4). (Oracle 2 that breaks unidirectionality): For input values x and z, one value is randomly selected from all values y satisfying f1 (x, y) = z, and the selected value is output. . If there is no value y satisfying f1 (x, y) = z for the input values x and z, the identification information ⊥ is output.
5. (Oracle 3 that breaks unidirectionality): For input values y and z, one value is randomly selected from all values x satisfying f1 (x, y) = z, and the selected value is output. . When there is no value x satisfying f1 (x, y) = z for the input values y and z, the identification information ⊥ is output.

The ideal compression function (WFILRO) whose unidirectionality is broken is a compression function to which the above 3-5 is given in addition to the idealized compression function (FILRO). Compared to the idealized compression function (FILRO), the ideal compression function (WFILRO) whose unidirectionality is broken is a compression function that is less secure because of the above 3-5. I can say that.
For example, when there is an attacker A, an ideal compression function (FILRO) is a state in which the attacker A can use only the above 1 and 2, and an ideal in which unidirectionality is broken. If it is a compression function (WFILRO), the attacker A can use 1-5 above. That is, compared with the idealized compression function (FILRO), the ideal compression function (WFILRO) whose unidirectionality has been broken has more functions given to the attacker A, so that the attacker A is easier. Can attack. Therefore, compared with the idealized compression function (FILRO), the ideal compression function (WFILRO) whose unidirectionality has been broken is a compression function that is less secure because the above 3-5 is given. It can be said that there is.

A hash function that cannot be strongly discriminated from a random oracle even when configured using a low-security compression function is strongly discriminated from a random oracle only when configured using a high-security compression function. It can be said that the configuration of the hash function is superior to the impossible hash function from the viewpoint of security.
In other words, even when the configuration is made using an ideal compression function (WFILRO) whose unidirectionality is broken, a random oracle and a so-called hash function that cannot be strongly discriminated are more ideally compressed. Only when it is configured using a function (FILRO), it can be said that the configuration of the hash function is superior to the hash function that cannot be strongly discriminated from the random oracle from the viewpoint of security.

  In the following embodiments, similar to the zipper hash function and the double pipe hash function described in Non-Patent Documents 1 and 2, an ideal compression function (WFILRO) whose unidirectionality is broken is used. Even in this case, the hash value computing device 10 that constitutes a new hash function that cannot be strongly discriminated from a random oracle will be described. In particular, the hash value calculation device 10 that constitutes a hash function that can be calculated more efficiently than the zipper hash function and the double pipe hash function described in Non-Patent Documents 1 and 2 will be described.

In the following embodiment, among the ideal compression functions (WFILRO) whose unidirectionality is broken, 5. Even if it is configured using a compression function to which (Oracle 3 that breaks unidirectionality) is not given (hereinafter referred to as an ideal compression function whose quasi-unidirectionality is broken), it is called a random oracle. The hash value computing device 10 that constitutes a new hash function that cannot be strongly identified will be described.
The ideal compression function whose quasi-unidirectionality is broken is a compression function that is safer than the ideal compression function (WFILRO) whose unidirectionality is broken. Therefore, when configured using an ideal compression function that breaks quasi-unidirectionality, it is an ideal compression function that breaks unidirectionality rather than a random oracle and a hash function that cannot be strongly discriminated. When configured using (WFILRO)), it can be said that a hash function that cannot be strongly discriminated from a random oracle is superior as a hash function configuration from the viewpoint of security. However, even if it is configured using an ideal compression function whose quasi-unidirectionality is broken, a random oracle and a hash function that is so-called strongly discriminating is an ideal compression function (FILRO)). It can be said that it is superior from the viewpoint of security as a structure of a hash function rather than a hash function that cannot be strongly discriminated from a random oracle only when configured using it. Therefore, in the following embodiment, a new hash function that cannot be strongly discriminated from a random oracle is configured even if it is configured using an ideal compression function whose quasi-unidirectionality is broken. The hash value calculation device 10 will also be described.

First, even in the case of using the ideal compression function (WFILRO) whose unidirectionality is broken in Embodiment 1-3, three new ones that cannot be discriminated strongly from a random oracle. A hash value computing device 10 that constitutes a simple hash function will be described.
Next, in the fourth and fifth embodiments, two new hashes that are indistinguishable from a random oracle even if they are configured using an ideal compression function whose quasi-unidirectionality is broken. The hash value calculation device 10 constituting the function will be described.

  In the following embodiments, the compression function h is a compression function that outputs an n-bit value when two values, an n-bit value and an m-bit value, are input. Here, m is a predetermined natural number, and n is a natural number smaller than m.

  In the following description, the processing device includes a CPU 911, an arithmetic circuit, and the like which will be described later. The storage device is a ROM 913, a RAM 914 (memory, cache memory), a magnetic disk 920, etc., which will be described later. The input device is a keyboard 902, a communication board 915, and the like which will be described later. The output device is a RAM 914, a magnetic disk 920, a communication board 915, an LCD 901, etc., which will be described later. That is, the processing device, the storage device, the input device, and the output device are hardware. Further, as described above, the storage device includes the RAM 914 (memory, cache memory) and the like. Therefore, in the following description, storing in the storage device means temporarily storing in the RAM 914 (memory, cache memory). In some cases.

Embodiment 1 FIG.
In the first embodiment, a new hash function that cannot be strongly discriminated from a random oracle is configured even if it is configured using an ideal compression function (WFILRO) whose unidirectionality is broken. The hash value calculation device 10 will be described.

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.
FIG. 3 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 1 will be described.
The hash value calculation device 10 shown in FIG. 1 includes a predetermined length value input unit 11, a fixed value addition unit 12, a compression function calculation unit 13, and an output unit 14.

(S101: Default length input step)
The predetermined length value input unit 11 includes i values p [1],. . . , Value p [i] is input by the input device and stored in the storage device.

(S102: fixed value addition step)
The fixed value adding unit 12 receives the i values p [1],. . . , Value p [i], i−1 values p [1],. . . , Values p [i−1], n-bit fixed values const [1],. . . , A fixed value const [i−1], and an m-bit length value x [1],. . . , Value x [i−1] is generated by the processing device and stored in the storage device.
That is, the fixed value adding unit 12 adds the fixed value const [1] to the value p [1] to generate the value x [1]. The fixed value adding unit 12 adds the fixed value const [2] to the value p [2] to generate the value x [2]. Similarly, j = 3,. . . , I−1, the fixed value adding unit 12 adds the fixed value const [j] to the value p [j] to generate the value x [j].
Note that j = 1,. . . , I−1, the position where the fixed value const [j] is added to the value p [j] may be anywhere. That is, the fixed value const [j] may be added before or after the value p [j], or may be inserted between the values p [j].
Also, fixed value const [1] = fixed value const [2] =. . . = Fixed value const [i−1], or fixed value const [1] ≠ fixed value const [2] ≠. . . ≠ Fixed value const [i−1] may be used.

(S103: First compression function calculation step)
The compression function calculation unit 13 receives the fixed value IV1 having an n-bit length stored in the storage device in advance and the m-bit length value x [1] generated in (S102) as an input of the compression function h. ] = H (IV1, x [1]) is calculated by the processing device to obtain a value c [1] having an n-bit length and stored in the storage device.

(S104: Second compression function calculation step)
The compression function calculation unit 13 uses the value c [j−1] of n bits and the value x [j] of m bits in order from j = 2 to i−1 as inputs of the compression function h. ] = H (c [j−1], x [j]) is calculated by the processing device to obtain a value c [j] having an n-bit length and stored in the storage device.
That is, first, the compression function calculation unit 13 receives the value c [1] of the n-bit length calculated in (S103) and the value x [2] of the m-bit length generated in (S102) as c [2] = h (c [1], x [2]) is calculated by the processing device to obtain the value c [2].
Next, the compression function calculation unit 13 receives the calculated n-bit length value c [2] and the m-bit length value x [3] generated in (S102) as input, and c [3] = h (C [2], x [3]) is calculated by the processing device to obtain an n-bit length value c [3].
By repeating this, finally, the compression function calculation unit 13 calculates the calculated value c [i−2] of n bits and the value x [i−1] of m bits generated in (S102). As an input, c [i-1] = h (c [i-2], x [i-1]) is calculated by the processing device to obtain an n-bit long value c [i-1].

(S105: third compression function calculation step)
The compression function calculation unit 13 converts the n-bit length value c [i−1] calculated in (S104) into the n-bit length fixed value IV2 stored in advance in the storage device and the mn bit-length value p [i]. ] Is added to the compression function h, and c [i] = h (IV2, x [i]) is calculated by the processor to obtain the value c [i]. And store it in the storage device.
The position where the value c [i-1] is added to the value p [i] may be anywhere. That is, the value c [i-1] may be added before or after the value p [i], or may be inserted between the values p [i].

(S106: output step)
The output unit 14 outputs the value c [i] calculated in (S105) by the output device.

  When i = 2, that is, when only two values p [1] and p [2] are input in (S101), (S104) is not executed. That is, after the value c [1] is obtained in (S103), the fixed value IV2 and the value x [2] obtained by adding the value c [1] to the value p [2] are input as values. c [2] is obtained. Then, the value c [2] is output in (S106).

  When i = 1, that is, when only one value p [1] is input in (S101), steps (S102) to (S104) are not executed. That is, after the value p [1] is input in (S101), the fixed value IV2 and the value x [1] obtained by adding the fixed value IV1 to the value p [1] are input as the value c in (S105). [1] is obtained. The value c [1] is output in (S106).

The above is summarized as follows.
First, the hash value calculation device 10 calculates c [j] = h (c [j−1], p [j] || const [j]) in order from j = 1 to i−1. Here, c [0] is IV1.
Next, the hash value calculation apparatus 10 calculates c [i] = h (IV2, p [i] || c [i-1]).
Then, the hash value calculation device 10 outputs the value c [i].

In the above description, in (S101), the predetermined length input unit 11 determines that the i values p [1],. . . , The value p [i] is input. However, normally, the value input to the hash function is one arbitrary bit length value. In other words, in the above description, when one arbitrary bit length value is input, how the i values p [1],. . . , And the value p [i] is not described.
Next, when a value having an arbitrary bit length is input, i values p [1],. . . The hash value computing device 10 to which a function for generating the value p [i] is added will be described.

FIG. 4 shows the case where i values p [1],... With m−n bit length are input to the hash value arithmetic unit 10 shown in FIG. . . , Is a functional block diagram showing functions of the hash value computing device 10 to which a function for generating a value p [i] is added.
FIG. 5 is a flowchart showing the operation of the hash value calculation apparatus 10 shown in FIG.
FIG. 6 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 4 will be described.
The hash value calculation device 10 illustrated in FIG. 4 includes an arbitrary length value input unit 15, a padding unit 16, and a division unit 17 in addition to the functions included in the hash value calculation device 10 illustrated in FIG. 1.

(S111: arbitrary length value input step)
The arbitrary length value input unit 15 inputs an arbitrary bit length value M from the input device.

(S112: Padding step)
The padding unit 16 adds a predetermined value to the value M input in (S111) by using the padding function pad, and processes a value M ′ having a bit length i times the mn bit length. Is generated and stored in the storage device. That is, the padding unit 16 calculates M ′ = pad (M) by the processing device to obtain the value M ′.

(S113: Division step)
The dividing unit 17 divides the value M ′ generated in (S112) into i pieces by the processing device, and sets the values p [1],. . . , Value p [i] is generated and stored in the storage device. That is, the dividing unit 17 sets M ′ = p [1] ||. . . || p [i] is calculated by the processing unit and the values p [1],. . . , Value p [i] is obtained.

(S114: predetermined length input step)
The predetermined length value input unit 11 receives the values p [1],. . . , Value p [i] is input by an input device.

  The processing from (S115) to (S119) is the same as the processing from (S102) to (S106).

An example of the padding method in (S112) will be described.
FIG. 7 is a structural diagram of a hash function realized by the hash value calculation apparatus 10 shown in FIG. 4 when performing the padding process described below.
In (S112), the padding unit 16 adds “1 || 0... 0 || M> to the value M input in (S111), i times the length of mn bits. A bit length value M ′ is generated by the processing unit, where <M> is a 64-bit representation of the bit length | M |
That is, the padding unit 16 generates a bit string that is “1” at the beginning, a plurality of “0” thereafter, and finally <M>, and is added to the value M to generate the value M ′.
In the above description, it has been described that padding is performed so that the bit length is i times the mn bit length. However, instead of predetermining the value of i, the value of i may be determined in accordance with the input arbitrary bit length value M. For example, in the case of the above padding method, padding is performed so that the bit length is a multiple of mn bit length with the minimum number of zeros, and the bit length of the value M ′ obtained as a result of padding is mn The value of i may be several times the bit length.

  The padding method may be any method, for example, a method of adding all “0” s or a method of adding all “1” s. However, as described above, the difficulty of collision can be increased by generating the value M ′ by padding.

Next, an example in which SHA-256 (Secure Hash Algorithm-256) is used as the compression function of the hash value computing device 10 shown in FIG. 4 will be described. Note that the compression function of SHA-256 is called SHA256. SHA256 is a function that outputs a 256-bit value when two values, a 256-bit value and a 512-bit value, are input.
FIG. 8 is a structural diagram of a hash function realized by the hash value calculation device 10 shown in FIG. 4 when SHA-256 is used as the compression function.

In (S111), the arbitrary length value input unit 15 inputs a value M having an arbitrary bit length.
In (S112), the padding unit 16 adds a predetermined value to the value M input in (S111) by using the padding function pad, and is i times the 256 (= 512-256) bit length. A bit length value M ′ is generated.
In (S113), the dividing unit 17 divides the value M ′ generated in (S112) into i pieces and divides the values p [1],. . . , Value p [i].
In (S114), the predetermined length input unit 11 determines the i values p [1],. . . , Input the value p [i].
In (S115), the fixed value adding unit 12 receives the 256 values i values p [1],. . . , Value p [i], i−1 values p [1],. . . , Value p [i−1], a fixed value const [1],. . . , A fixed value const [i−1] is added, and a value x [1],. . . , Value x [i−1].
In (S116), the compression function calculation unit 13 uses the 256-bit fixed value IV1 and the 512-bit length value x [1] generated in (S115) as the input of the compression function h, and c [1] = h (IV1, x [1]) is calculated to obtain a 256-bit long value c [1].
In (S117), the compression function calculation unit 13 inputs the value c [j-1] of 256 bit length and the value x [j] of 512 bit length in order of the compression function h from j = 2 to i-1. C [j] = h (c [j−1], x [j]) is calculated to obtain a 256-bit long value c [j].
In (S118), the compression function calculation unit 13 adds a 256-bit fixed value IV2 and a 512-bit value obtained by adding a 256-bit length value c [i-1] to a 256-bit length value p [i]. With x [i] as the input of the compression function h, c [i] = h (IV2, x [i]) is calculated to obtain the value c [i].
In (S119), the output unit 14 outputs the value c [i] calculated in (S118).

  The hash function configured by the hash value computing device 10 according to the first embodiment is indistinguishable from a random oracle even if the compression function h is an ideal compression function whose unidirectionality is broken. A hash function that satisfies

  Note that it is not always necessary to calculate according to the above-described processing order. If stream processing is possible, calculation may be performed by stream processing. Stream processing is a method of performing processing in the order of arrival from the input first bit, and is a type of parallel processing.

  In the above description, the compression function calculation unit 13 calculates the compression function h by a processing device for a predetermined input value, and obtains the result of calculating the compression function h. However, the compression function calculation unit 13 calculates the compression function h by inputting the input value to the compression function calculation device provided outside the hash value calculation device 10 and causing the compression function calculation device to calculate the compression function h. Results may be obtained.

  In addition, the compression function calculation unit 13 receives the values c [1],. . . , C [i], the compression function h used for calculating the value c [i] may be the same compression function h or different compression functions h.

That is, the hash value calculation apparatus 10 according to the first embodiment is summarized as follows.
The hash value arithmetic unit 10 is configured to input i mn bit input values p [1],. . . , P [i], the n-bit fixed value IV1, the first message p [1], and the n-bit fixed value const [1] are input to the compression function arithmetic unit, and the output c [1] is obtained. Next, the n-bit value c [1], the second message p [2], and the n-bit fixed value const [2] are input to the compression function arithmetic unit, and the output c [2] is obtained. This process is similarly performed up to the (i-1) th message, and the output value c [i-1] is obtained. An initial value IV2, an i-th message p [i], and an n-bit value c [i-1] are input to the compression function arithmetic unit, and an output c [i] is obtained. Then, c [i] is output.

  In addition, the hash value calculation device 10 uses an arbitrary padding processing device that receives an arbitrary length value from an arbitrary length value M and outputs a value that is a multiple of mn in length, using m-n bits. A message M ′ that is a multiple of is generated. Then, M ′ is converted into i mn bit values p [1],. . . , P [i].

  Further, the hash value computing device 10 changes the padding processing device to M || 1 || 0. . . 0 || <M>. However, <M> represents the bit length of M in 64 bits.

  Further, the hash value calculation device 10 is characterized in that a compression function calculation device of SHA-256 is used as the compression function calculation device.

Embodiment 2. FIG.
In the second embodiment, even when the hash function is different from that of the first embodiment and is configured using an ideal compression function (WFILRO) whose unidirectionality is broken, it is called a random oracle. The hash value computing device 10 that constitutes a new hash function that cannot be strongly identified will be described.

FIG. 9 is a functional block diagram illustrating functions of the hash value computing device 10 according to the second embodiment.
FIG. 10 is a flowchart showing the operation of the hash value calculation apparatus 10 shown in FIG.
FIG. 11 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 9 will be described.
The hash value calculation device 10 illustrated in FIG. 9 includes a predetermined length value input unit 11, a fixed value addition unit 12, a compression function calculation unit 13, an output unit 14, and an exclusive OR calculation unit 18.

(S201: Default length input step)
The predetermined length value input unit 11 includes i values p [1],. . . , Value p [i] is input by the input device and stored in the storage device.

(S202: Exclusive OR calculation step)
The exclusive OR calculation unit 18 calculates the values p [1],. . . , P [i] and an m-s bit length fixed value y stored in advance in the storage device as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing device to obtain a value sum of m-s bit length and stored in the storage device.

(S203: Fixed value addition step)
The fixed value adding unit 12 receives the i values p [1],. . . , Values p [i], s bit length fixed values const [1],. . . , A fixed value const [i], and an m-bit length value x [1],. . . , Value x [i] is generated by the processing device and stored in the storage device.
That is, the fixed value adding unit 12 adds the fixed value const [1] to the value p [1] to generate the value x [1]. The fixed value adding unit 12 adds the fixed value const [2] to the value p [2] to generate the value x [2]. Similarly, j = 3,. . . , I, the fixed value adding unit 12 adds the fixed value const [j] to the value p [j] to generate the value x [j].
Note that j = 1,. . . , I−1, the position where the fixed value const [j] is added to the value p [j] may be anywhere. That is, the fixed value const [j] may be added before or after the value p [j], or may be inserted between the values p [j].
Further, the fixed value const [1] ≠ fixed value const [2] ≠. . . ≠ Fixed value const [i]. For example, j = 1,. . . , I, the fixed value const [j] is a value <j> in which j is expressed by s bits.

(S204: First compression function calculation step)
The compression function calculation unit 13 receives the fixed value IV1 of n-bit length stored in the storage device in advance and the m-bit length value x [1] generated in (S203) as an input of the compression function h, c [1] = H (IV1, x [1]) is calculated by the processing device to obtain an n-bit length value c [1] and stored in the storage device.

(S205: Second compression function calculation step)
The compression function calculation unit 13 sequentially inputs the value c [j−1] having an n-bit length and the value x [j] having an m-bit length from j = 2 to i, and inputs c [j] = h (c [j−1], x [j]) is calculated by the processing device to obtain a value c [j] having an n-bit length and stored in the storage device.
That is, first, the compression function calculation unit 13 receives the value c [1] having the n-bit length calculated in (S204) and the value x [2] having the m-bit length generated in (S203) as c [2] = h (c [1], x [2]) is calculated by the processing device to obtain an n-bit length value c [2].
Next, the compression function calculation unit 13 receives the calculated n-bit length value c [2] and the m-bit length value x [3] generated in (S203) as c [3] = h. (C [2], x [3]) is calculated by the processing device to obtain an n-bit length value c [3].
By repeating this, the compression function calculation unit 13 finally inputs the calculated n-bit length value c [i−1] and the m-bit length value x [i] generated in (S203). C [i] = h (c [i−1], x [i]) is calculated by the processing device to obtain an n-bit length value c [i].

(S206: third compression function calculation step)
The compression function calculation unit 13 adds the fixed value const [i + 1] having the s bit length to the value c [i] having the n bit length calculated in (S205) and the value sum having the m-s bit length calculated in (S202). C [i + 1] = h (c [i], x [i + 1]) is calculated by the processing device using the m-bit length value x [i + 1] to which is added as an input to the compression function h, and the n-bit length value is calculated. c [i + 1] is obtained and stored in the storage device.
Note that the fixed value const [i + 1] ≠ fixed value const [1] ≠. . . ≠ Fixed value const [i]. For example, the fixed value const [i + 1] is a value <i + 1> in which i + 1 is expressed by s bits.
Further, the position where the fixed value const [i + 1] is added to the value sum may be anywhere. That is, the fixed value const [i + 1] may be added before or after the value sum, or may be inserted between the values sum.

(S207: Fourth compression function calculation step)
The compression function calculation unit 13 adds an n-bit length fixed value IV2 stored in the storage device in advance and the n-bit length value c [i + 1] calculated in (S206) to an mn bit length fixed value const [i + 2]. The value x [i + 2] to which is added is used as the input of the compression function h, and c [i + 2] = h (IV2, x [i + 2]) is calculated by the processing device to obtain the value c [i + 2] having an n-bit length. Store in the storage device.
The position where the fixed value const [i + 2] is added to the value c [i + 1] may be anywhere. That is, the fixed value const [i + 2] may be added before or after the value c [i + 1], or may be inserted between the values c [i + 1].
Further, for example, the fixed value const [i + 2] may be two values: a fixed value const having an m−ns−bit length and a value <i + 2> in which i + 2 is expressed by s bits. When the fixed value const [i + 2] is the fixed value const and <i + 2>, the fixed value const and <i + 2> may be added to the value c [i + 1] in any way. For example, x [i + 2] = <i + 2> || const || [c [i + 1] may be set.

(S208: Output step)
The output unit 14 outputs the value c [i + 2] calculated in (S207) from the output device.

  When i = 1, that is, when only one value p [1] is input in (S201), (S205) is not executed. That is, after obtaining the value c [1] in (S204), the value c [1] in (S206) and the value x [2] obtained by adding the fixed value const [2] to the value sum are input. c [2] is obtained. Then, the process proceeds to (S207).

The above is summarized as follows.
First, the hash value computing device 10 is sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing unit.
Further, the hash value calculation device 10 calculates c [j] = h (c [j−1], p [j] || <j>) in order from j = 1 to i. Here, c [0] is IV1.
Next, the hash value calculation device 10 calculates c [i + 1] = h (c [i], sum || <i + 1>).
Next, the hash value calculation device 10 calculates c [i + 2] = h (IV, c [i + 1] || const || i + 2>).
Then, the hash value calculation device 10 outputs the value c [i + 2].

In the above description, in (S201), the predetermined length value input unit 11 determines that the i values p [1],. . . , The value p [i] is input. However, normally, the value input to the hash function is one arbitrary bit length value. In other words, in the above description, when one arbitrary bit length value is input, how the i values p [1],. . . , And the value p [i] is not described.
Next, when an arbitrary bit length value is input, i values p [1],. . . The hash value computing device 10 to which a function for generating the value p [i] is added will be described.

FIG. 12 shows i values p [1],... Of m−s bit length when an arbitrary bit length value is input to the hash value calculation apparatus 10 shown in FIG. . . , Is a functional block diagram showing functions of the hash value computing device 10 to which a function for generating a value p [i] is added.
FIG. 13 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 14 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 12 will be described.
The hash value calculation device 10 illustrated in FIG. 12 includes an arbitrary length value input unit 15, a padding unit 16, and a division unit 17 in addition to the functions included in the hash value calculation device 10 illustrated in FIG. 9.

(S211: Arbitrary length value input step)
The arbitrary length value input unit 15 inputs an arbitrary bit length value M from the input device.

(S212: Padding step)
The padding unit 16 adds a predetermined value to the value M input in (S211) using the padding function pad, and processes the value M ′ having a bit length i times the m-s bit length. Is generated and stored in the storage device. That is, the padding unit 16 calculates M ′ = pad (M) by the processing device to obtain the value M ′.

(S213: Division step)
The dividing unit 17 divides the value M ′ generated in (S212) into i pieces by the processing device, and sets the values p [1],. . . , Value p [i] is generated and stored in the storage device. That is, the dividing unit 17 sets M ′ = p [1] ||. . . || p [i] is calculated by the processing unit and the values p [1],. . . , Value p [i] is obtained.

(S214: predetermined length value input step)
The predetermined length value input unit 11 receives the values p [1],. . . , Value p [i] is input by an input device.

  The processing from (S215) to (S221) is the same as the processing from (S202) to (S208).

An example of the padding method in (S212) will be described.
FIG. 15 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 12 when the padding process described below is performed.
In (S212), the padding unit 16 performs "1 || 0 ... 0 || for the value M input in (S211), similarly to the padding method in (S112) described in the first embodiment. A value M ′ having a bit length i times the m-s bit length is generated by the processing device by adding <M>, where <M> is a 64-bit representation of the bit length | M | is there.
Thus, the difficulty of collision can be increased by generating the value M ′ by padding.

FIG. 16 is a structural diagram of a hash function realized by the hash value calculation apparatus 10 shown in FIG. 12 when performing the padding process described below.
In (S212), the padding unit 16 adds “1 || 0... 0 to the value M input in (S211), and a value M having a bit length i times the m-s bit length. 'Is generated by the processing device.
Thus, even if padding generates the value M ′, the collision difficulty can be increased.

  As in the first embodiment, the value of i may not be determined in advance, but the value of i may be determined according to the input arbitrary bit length value M.

Next, an example in which SHA-256 is used as the compression function of the hash value computing device 10 shown in FIG. Note that the compression function of SHA-256 is called SHA256. SHA256 is a function that outputs a 256-bit value when two values, a 256-bit value and a 512-bit value, are input.
FIG. 17 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 12 when SHA-256 is used as the compression function.
In the following description, the value s is assumed to be 56.

In (S211), the arbitrary length value input unit 15 inputs a value M having an arbitrary bit length.
In (S212), the padding unit 16 adds a predetermined value to the value M input in (S211) using the padding function pad, and is i times the length of 456 (= 512-56) bits. A bit length value M ′ is generated.
In (S213), the dividing unit 17 divides the value M ′ generated in (S212) into i pieces and 456-bit length values p [1],. . . , Value p [i].
In (S214), the predetermined length value input unit 11 receives the 456-bit length values p [1],. . . , Input the value p [i].
In (S215), the exclusive OR calculation unit 18 determines the values p [1],. . . , P [i] and a fixed value y of 456 bits as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated to obtain a value sum of 456 bits.
In (S216), the fixed value adding unit 12 receives the values p [1],. . . , Value p [i], a fixed value const [1],. . . , A fixed value const [i] is added to the value x [1],. . . , Value x [i].
In (S217), the compression function calculation unit 13 uses the 256-bit fixed value IV1 and the 512-bit length value x [1] generated in (S216) as the input of the compression function h, and c [1] = h (IV1, x [1]) is calculated to obtain a 256-bit long value c [1].
In (S218), the compression function calculation unit 13 sequentially inputs a value c [j−1] of 256 bits and a value x [j] of 512 bits in length from j = 2 to i as inputs of the compression function h. c [j] = h (c [j−1], x [j]) is calculated to obtain a 256-bit long value c [j].
In (S219), the compression function calculation unit 13 adds a 56-bit length fixed value const to the 256-bit length value c [i] calculated in (S218) and the 456-bit length value sum calculated in (S215). Using a 512-bit length value x [i + 1] with [i + 1] added as an input to the compression function h, c [i + 1] = h (c [i], x [i + 1]) is calculated and a 256-bit length value is obtained. c [i + 1] is obtained.
In (S220), the compression function calculation unit 13 adds a 256-bit fixed value IV2 and a 256-bit fixed value const [i + 2] to the 256-bit long value c [i + 1] calculated in (S215). Using the value x [i + 2] as an input to the compression function h, c [i + 2] = h (IV2, x [i + 2]) is calculated to obtain a 256-bit long value c [i + 2].
In (S221), the output unit 14 outputs the value c [i + 2] calculated in (S220).

  The hash function configured by the hash value computing device 10 according to the second embodiment is indistinguishable from a random oracle even if the compression function h is an ideal compression function whose unidirectionality is broken. A hash function that satisfies

  Note that, as in the first embodiment, the calculation is not necessarily performed according to the above-described processing order. When the stream processing can be performed, the calculation may be performed by the stream processing.

Similarly to the first embodiment, the compression function calculation unit 13 inputs an input value to a compression function calculation device provided outside the hash value calculation device 10 and causes the compression function calculation device to calculate the compression function h. Thus, the result of calculating the compression function h may be obtained.
Similarly, the exclusive OR calculator 18 inputs an input value to an exclusive OR calculator provided outside the hash value calculator 10 and performs an exclusive OR operation on the exclusive OR calculator. By calculating, an exclusive OR operation result may be obtained.

  In addition, the compression function calculation unit 13 receives the values c [1],. . . , C [i + 2] may be the same compression function h or different compression functions h.

That is, the hash value calculation device 10 according to the second embodiment is summarized as follows.
The hash value arithmetic unit 10 is configured to input i m-s bit input values p [1],. . . , P [i], the n-bit fixed value IV1, the first message p [1], and the s-bit representation value of 1 are input to the compression function arithmetic unit, and the output c [1] is obtained. Next, the n-bit value c [1], the second message p [2], and the s-bit representation value of 2 are input to the compression function arithmetic unit, and the output c [2] is obtained. This process is similarly performed up to the i-th message, and the output value c [i] is obtained. The compression function arithmetic unit receives an n-bit value c [i], sum = p [1] xor. . . xor p [i] xor y, an s-bit representation value of i + 1 is input, and its output c [i + 1] is obtained. An initial value IV2, an n-bit value c [i-1], an mn-s-bit fixed value const, and an s-bit representation value of i + 2 are input to the compression function arithmetic unit, and an output c [i + 2] is obtained. Then, c [i + 2] is output. Here, y is a fixed value of m−s bits.

  Further, the hash value computing device 10 is a multiple of m-s bits using an arbitrary padding processing device that receives an arbitrary length value from an arbitrary length value M and outputs an m-s bit value. A message M ′ is generated. Using a split processor, M 'is replaced with i ms bit values p [1],. . . , P [i].

  Further, the hash value computing device 10 changes the padding processing device to M || 1 || 0. . . 0 || <M> and s = 56. However, <M> represents the bit length of M in 64 bits.

  Further, the hash value calculation device 10 changes the padding processing device to M || 1 || 0. . . 0 and s = 56.

  Further, the hash value calculation device 10 is characterized by using a SHA-256 compression function calculation device as the compression function calculation device.

Embodiment 3 FIG.
In the third embodiment, even if the hash function is different from those in the first and second embodiments and is configured using an ideal compression function (WFILRO) whose unidirectionality is broken, the random oracle The hash value calculation device 10 that constitutes a new hash function that cannot be strongly discriminated will be described.

FIG. 18 is a functional block diagram illustrating functions of the hash value computing device 10 according to the third embodiment.
FIG. 19 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 20 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 18 will be described.
The hash value calculation device 10 illustrated in FIG. 18 includes a predetermined length value input unit 11, a fixed value addition unit 12, a compression function calculation unit 13, an output unit 14, and an exclusive OR calculation unit 18.

(S301: Default length input step)
The predetermined length value input unit 11 includes i values p [1],. . . , Value p [i] and one value p [i + 1] having a length of m−n bits are input by the input device and stored in the storage device.

(S302: Exclusive OR calculation step)
The exclusive OR calculator 18 calculates the i-values p [1],. . . , P [i] and an m-s bit length fixed value y stored in advance in the storage device as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing device to obtain a value sum of m-s bit length and stored in the storage device.

(S303: fixed value addition step)
The fixed value adding unit 12 receives the i values p [1],. . . , Values p [i], s bit length fixed values const [1],. . . , A fixed value const [i], and an m-bit length value x [1],. . . , Value x [i] is generated by the processing device and stored in the storage device.
That is, the fixed value adding unit 12 adds the fixed value const [1] to the value p [1] to generate the value x [1]. The fixed value adding unit 12 adds the fixed value const [2] to the value p [2] to generate the value x [2]. Similarly, j = 3,. . . , I, the fixed value adding unit 12 adds the fixed value const [j] to the value p [j] to generate the value x [j].
Note that j = 1,. . . , I−1, the position where the fixed value const [j] is added to the value p [j] may be anywhere. That is, the fixed value const [j] may be added before or after the value p [j], or may be inserted between the values p [j].
Further, the fixed value const [1] ≠ fixed value const [2] ≠. . . ≠ Fixed value const [i]. For example, j = 1,. . . , I, the fixed value const [j] is a value <j> in which j is expressed by s bits.

(S304: First compression function calculation step)
The compression function calculation unit 13 uses the n-bit fixed value IV1 stored in the storage device in advance and the m-bit length value x [1] generated in (S303) as the input of the compression function h. = H (IV1, x [1]) is calculated by the processing device to obtain an n-bit length value c [1] and stored in the storage device.

(S305: second compression function calculation step)
The compression function calculation unit 13 sequentially inputs the value c [j−1] having an n-bit length and the value x [j] having an m-bit length from j = 2 to i, and inputs c [j] = h (c [j−1], x [j]) is calculated by the processing device to obtain a value c [j] having an n-bit length and stored in the storage device.
That is, first, the compression function calculation unit 13 receives the value c [1] of n-bit length calculated in (S304) and the value x [2] of m-bit length generated in (S303) as c [2] = h (c [1], x [2]) is calculated by the processing device to obtain an n-bit length value c [2].
Next, the compression function calculation unit 13 receives the calculated n-bit length value c [2] and the m-bit length value x [3] generated in (S303) as c [3] = h. (C [2], x [3]) is calculated by the processing device to obtain an n-bit length value c [3].
By repeating this, finally, the compression function calculation unit 13 inputs the calculated n-bit length value c [i−1] and the m-bit length value x [i] generated in (S303). C [i] = h (c [i−1], x [i]) is calculated by the processing device to obtain an n-bit length value c [i].

(S306: third compression function calculation step)
The compression function calculation unit 13 adds the fixed value const [i + 1] of the s bit length to the value c [i] of the n bit length calculated in (S305) and the value sum of the m−s bit length calculated in (S302). C [i + 1] = h (c [i], x [i + 1]) is calculated by the processing device using the m-bit length value x [i + 1] to which is added as an input to the compression function h, and the n-bit length value is calculated. c [i + 1] is obtained and stored in the storage device.
Note that the fixed value const [i + 1] ≠ fixed value const [1] ≠. . . ≠ Fixed value const [i]. For example, the fixed value const [i + 1] is a value <i + 1> in which i + 1 is expressed by s bits.
Further, the position where the fixed value const [i + 1] is added to the value sum may be anywhere. That is, the fixed value const [i + 1] may be added before or after the value sum, or may be inserted between the values sum.

(S307: Fourth compression function calculation step)
The compression function calculation unit 13 inputs the m-n bit length input in (S301) to the fixed value IV2 of n bit length stored in the storage device in advance and the value c [i + 1] of n bit length calculated in (S306). C [i + 2] = h (IV2, x [i + 2]) is calculated by the processing device using the value x [i + 2] to which the value p [i + 1] is added as the input of the compression function h, and the value c of n-bit length is calculated. [I + 2] is obtained and stored in the storage device.
The position where the value p [i + 1] is added to the value c [i + 1] may be anywhere. That is, the value p [i + 1] may be added before or after the value c [i + 1], or may be inserted between the values c [i + 1].

(S308: Output step)
The output unit 14 outputs the value c [i + 2] calculated in (S307) from the output device.

  When i = 1, that is, when only two values p [1] (value p [i]) and value p [2] (value p [i + 1]) are input in (S301). , (S305) are not executed. That is, after obtaining the value c [1] in (S304), the value c [1] in (S306) and the value x [2] obtained by adding the fixed value const [2] to the value sum are input. c [2] is obtained. Then, the process proceeds to (S307).

The above is summarized as follows.
First, the hash value computing device 10 is sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing unit.
Further, the hash value calculation device 10 calculates c [j] = h (c [j−1], p [j] || <j>) in order from j = 1 to i. Here, c [0] is IV1.
Next, the hash value calculation device 10 calculates c [i + 1] = h (c [i], sum || <i + 1>).
Next, the hash value calculation device 10 calculates c [i + 2] = h (IV, c [i + 1] || p [i + 1]).
Then, the hash value calculation device 10 outputs the value c [i + 2].

In the above description, in (S301), the predetermined length value input unit 11 determines that the i values p [1],. . . , Value p [i] and one value p [i + 1] having an mn bit length are input. However, normally, the value input to the hash function is one arbitrary bit length value. In other words, in the above description, when one arbitrary bit length value is input, how the i values p [1],. . . , Value p [i] and whether to generate one value p [i + 1] having a length of m−n bits are not described.
Next, when an arbitrary bit length value is input, i values p [1],. . . , A value p [i] and a hash value computing device 10 to which a function for generating one value p [i + 1] having an mn bit length is added will be described.

FIG. 21 shows i values p [1],... Of m-s bit length when an arbitrary bit length value is input to the hash value calculation apparatus 10 shown in FIG. . . , Value p [i] and a function for generating one value p [i + 1] having a length of m−n bits.
FIG. 22 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 23 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 21 will be described.
The hash value calculation device 10 illustrated in FIG. 21 includes an arbitrary length value input unit 15, a padding unit 16, and a division unit 17 in addition to the functions included in the hash value calculation device 10 illustrated in FIG. 18.

(S311: Arbitrary length input step)
The arbitrary length value input unit 15 inputs an arbitrary bit length value M from the input device.

(S312: Padding step)
The padding unit 16 adds a predetermined value to the value M input in (S311) using the padding function pad ((ms) × i + (mn)) and has a bit length value. M ′ is generated by the processing device and stored in the storage device. That is, the padding unit 16 calculates M ′ = pad (M) by the processing device to obtain the value M ′.

(S313: Division step)
The dividing unit 17 divides the value M ′ generated in (S312) into i + 1 pieces by the processing device, and sets the values p [1],. . . , Value p [i] and one value p [i + 1] having an mn bit length are generated and stored in the storage device. That is, the dividing unit 17 sets M ′ = p [1] ||. . . || p [i] || p [i + 1] is calculated by the processing unit and the values p [1],. . . , Value p [i] and value p [i + 1].

(S314: Default length input step)
The predetermined length value input unit 11 receives the values p [1],. . . , Value p [i] and value p [i + 1] are input by the input device.

  The processing from (S315) to (S321) is the same as the processing from (S302) to (S308).

An example of the padding method in (S312) will be described.
FIG. 24 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 21 when the padding process described below is performed.
In (S312), the padding unit 16 performs "1 || 0 ... 0 || for the value M input in (S311), similarly to the padding method in (S112) described in the first embodiment. A value M ′ having a bit length i times the m-s bit length is generated by the processing device by adding <M>, where <M> is a 64-bit representation of the bit length | M | is there.
Thus, the difficulty of collision can be increased by generating the value M ′ by padding.

  As in the first embodiment, the value of i may not be determined in advance, but the value of i may be determined according to the input arbitrary bit length value M. In this case, the value M ′ may be generated so that the bit length | M ′ | of the value M ′ is “| M ′ | mod m−s = mn”.

Next, an example in which SHA-256 is used as the compression function of the hash value computing device 10 shown in FIG. Note that the compression function of SHA-256 is called SHA256. SHA256 is a function that outputs a 256-bit value when two values, a 256-bit value and a 512-bit value, are input.
FIG. 25 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 12 when SHA-256 is used as the compression function.
In the following description, the value s is assumed to be 56.

In (S311), the arbitrary length value input unit 15 inputs a value M having an arbitrary bit length.
In (S312), the padding unit 16 adds a predetermined value to the value M input in (S311) using the padding function pad ((512-56) × i + (512-256)). ) Generate a bit length value M ′.
In (S313), the dividing unit 17 converts the value M ′ generated in (S312) into i 456-bit length values p [1],. . . , Value p [i] and one 256-bit length value p [i + 1].
In (S314), the predetermined length input unit 11 determines the i 456-bit length values p [1],. . . , Value p [i] and one 256-bit length value p [i + 1].
In (S315), the exclusive OR calculator 18 determines the values p [1],. . . , P [i] and a fixed value y of 456 bits as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated to obtain a value sum of 456 bits.
In (S316), the fixed value adding unit 12 receives the 456-bit value p [1],. . . , Value p [i], a fixed value const [1],. . . , A fixed value const [i] is added to the value x [1],. . . , Value x [i].
In (S317), the compression function calculation unit 13 uses the 256-bit length fixed value IV1 and the 512-bit length value x [1] generated in (S316) as the input of the compression function h, and c [1] = h (IV1, x [1]) is calculated to obtain a 256-bit long value c [1].
In (S <b> 318), the compression function calculation unit 13 uses a 256-bit length value c [j−1] and a 512-bit length value x [j] as inputs to the compression function h in order from j = 2 to i. c [j] = h (c [j−1], x [j]) is calculated to obtain a 256-bit long value c [j].
In (S319), the compression function calculation unit 13 adds the 56-bit length fixed value const to the 256-bit length value c [i] calculated in (S318) and the 456-bit length value sum calculated in (S315). Using a 512-bit length value x [i + 1] with [i + 1] added as an input to the compression function h, c [i + 1] = h (c [i], x [i + 1]) is calculated and a 256-bit length value is obtained. c [i + 1] is obtained.
In (S320), the compression function calculation unit 13 adds the 256-bit length value input in (S314) to the 256-bit length fixed value IV2 and the 256-bit length value c [i + 1] calculated in (S315). c [i + 2] = h (IV2, x [i + 2]) is calculated using the value x [i + 2] to which p [i + 1] is added as an input to the compression function h to obtain a 256-bit long value c [i + 2]. .
In (S321), the output unit 14 outputs the value c [i + 2] calculated in (S320).

  The hash function configured by the hash value computing device 10 according to the third embodiment is indistinguishable from a random oracle even if the compression function h is an ideal compression function whose unidirectionality is broken. A hash function that satisfies

  Note that, as in the first embodiment, the calculation is not necessarily performed according to the above-described processing order. When the stream processing can be performed, the calculation may be performed by the stream processing.

Similarly to the first embodiment, the compression function calculation unit 13 inputs an input value to a compression function calculation device provided outside the hash value calculation device 10 and causes the compression function calculation device to calculate the compression function h. Thus, the result of calculating the compression function h may be obtained.
Similarly, the exclusive OR calculator 18 inputs an input value to an exclusive OR calculator provided outside the hash value calculator 10 and performs an exclusive OR operation on the exclusive OR calculator. By calculating, an exclusive OR operation result may be obtained.

  In addition, the compression function calculation unit 13 receives the values c [1],. . . , C [i + 2] may be the same compression function h or different compression functions h.

That is, the hash value calculation device 10 according to the third embodiment is summarized as follows.
The hash value arithmetic unit 10 applies n m-s bit input values m [1],..., M [i] and mn bit input m [i + 1] to the compression function arithmetic unit n. The bit fixed value IV1, the first message m [1], and the s bit representation value of 1 are input, and the output c [1] is obtained. Next, the n-bit value c [1], the second message m [2], and the s-bit representation value of 2 are input to the compression function arithmetic unit, and the output c [2] is obtained. This process is similarly performed up to the i-th message, and the output value c [i] is obtained. An n-bit value c [i], sum = m [1] xor... Xor m [i] xor y, i + 1 s-bit representation values are input to the compression function arithmetic unit, and an output c [i + 1] is obtained. An initial value IV2, an m-n bit message m [i + 1], and an n-bit value c [i-1] are input to the compression function arithmetic unit, and an output c [i + 2] is obtained. Then, c [i + 2] is output. Here, y is a fixed value of m−s bits.

  In addition, the hash value calculation device 10 receives an arbitrary length value from the arbitrary length value M, and generates a message M ′ using an arbitrary padding processing device. However, it is set so that | M ′ | mod m−s = mn. M ′ is divided into i m-s bit values m [1],..., M [i] and m−n bit values m [i] using a division processing apparatus.

  Further, the hash value computing device 10 is characterized in that the padding processing device is M || 1 || 0 ... 0 || <M> and s = 56. However, <M> represents the bit length of M in 64 bits.

  Further, the hash value calculation device 10 is characterized in that a compression function calculation device of SHA-256 is used as the compression function calculation device.

Embodiment 4 FIG.
In the fourth embodiment, even if it is configured using an ideal compression function whose quasi-unidirectionality has been broken, a hash value calculation that constitutes a new hash function that cannot be strongly discriminated from a random oracle. The apparatus 10 will be described.

FIG. 26 is a functional block diagram illustrating functions of the hash value computing device 10 according to the fourth embodiment.
FIG. 27 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 28 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 26 will be described.
The hash value calculation device 10 illustrated in FIG. 26 includes a predetermined length value input unit 11, a fixed value addition unit 12, a compression function calculation unit 13, an output unit 14, and a replacement function calculation unit 19.

(S401: Default length input step)
The predetermined length value input unit 11 includes i values p [1],. . . , Value p [i] is input by the input device and stored in the storage device.

(S402: Fixed value addition step)
The fixed value adding unit 12 receives the i values p [1],. . . , Values p [i], n-bit fixed values const [1],. . . , A fixed value const [i], and an m-bit length value x [1],. . . , Value x [i] is generated by the processing device and stored in the storage device.
That is, the fixed value adding unit 12 adds the fixed value const [1] to the value p [1] to generate the value x [1]. The fixed value adding unit 12 adds the fixed value const [2] to the value p [2] to generate the value x [2]. Similarly, j = 3,. . . , I, the fixed value adding unit 12 adds the fixed value const [j] to the value p [j] to generate the value x [j].
Note that j = 1,. . . , I, the position where the fixed value const [j] is added to the value p [j] may be anywhere. That is, the fixed value const [j] may be added before or after the value p [j], or may be inserted between the values p [j].
Also, fixed value const [1] = fixed value const [2] =. . . = Fixed value const [i], or fixed value const [1] ≠ fixed value const [2] ≠. . . ≠ Fixed value const [i] may be used.

(S403: First compression function calculation step)
The compression function calculation unit 13 uses the n-bit length fixed value IV1 stored in the storage device in advance and the m-bit length value x [1] generated in (S402) as an input of the compression function h, c [1] = H (IV1, x [1]) is calculated by the processing device to obtain an n-bit length value c [1] and stored in the storage device.

(S404: Second compression function calculation step)
The compression function calculation unit 13 uses the value c [j−1] of n bits and the value x [j] of m bits in order from j = 2 to i−1 as inputs of the compression function h. ] = H (c [j−1], x [j]) is calculated by the processing device to obtain a value c [j] having an n-bit length and stored in the storage device.
That is, first, the compression function calculation unit 13 receives the n-bit length value c [1] calculated in (S403) and the m-bit length value x [2] generated in (S402) as c [2] = h (c [1], x [2]) is calculated by the processing device to obtain an n-bit length value c [2].
Next, the compression function calculation unit 13 receives the calculated n-bit length value c [2] and the m-bit length value x [3] generated in (S402) as input, and c [3] = h (C [2], x [3]) is calculated by the processing device to obtain an n-bit length value c [3].
By repeating this, finally, the compression function calculation unit 13 calculates the calculated n-bit length value c [i−2] and the m-bit length value x [i−1] generated in (S402). As an input, c [i-1] = h (c [i-2], x [i-1]) is calculated by the processing device to obtain an n-bit long value c [i-1].

(S405: Substitution function calculation step)
The replacement function calculation unit 19 uses the value c [i−1] of n bits calculated in (S404) as an input of the replacement function π, and c ′ [i−1] = π (c [i−1]) Is calculated by the processing device to obtain a value c ′ [i−1] having an n-bit length and stored in the storage device.
The replacement function π is a replacement function that replaces a value a ′ different from the value a when an arbitrary value a is input, and the input value a is output as it is when the value a is input. It is a replacement function without That is, the replacement function π is a replacement function that does not have a fixed point such that π (a) = a.

(S406: third compression function calculation step)
The compression function calculation unit 13 uses the n-bit length value c ′ [i−1] calculated in (S405) and the m-bit length value x [i] generated in (S402) for the compression function h. As an input, c [i] = h (c ′ [i−1], x [i]) is calculated by the processing device to obtain an n-bit length value c [i] and stored in the storage device.

(S407: output step)
The output unit 14 outputs the value c [i] calculated in (S406) by the output device.

  When i = 2, that is, when only two values p [1] and p [2] are input in (S401), (S404) is not executed. That is, after obtaining the value c [1] in (S403), the value c [1] is input in (S405) to obtain the value c '[1]. In (S406), the value c '[1] and the value x [2] are input to obtain the value c [2].

  When i = 1, that is, when only one value p [1] is input in (S401), (S403) and (S404) are not executed. That is, after the value x [1] is generated in (S402), the fixed value IV1 is input in (S405) to obtain the value IV1 '. In step S406, the value IV1 'and the value x [1] are input to obtain the value c [1].

The above is summarized as follows.
First, the hash value calculation device 10 calculates c [j] = h (c [j−1], p [j] || const [j]) in order from j = 1 to i−1. Here, c [0] is IV1.
Next, the hash value calculation device 10 calculates c [i] = h (π (c [i−1]), p [i] || const [i]).
Then, the hash value calculation device 10 outputs the value c [i].

In the above description, in (S401), the default length value input unit 11 determines that i values p [1],. . . , The value p [i] is input. However, normally, the value input to the hash function is one arbitrary bit length value. In other words, in the above description, when one arbitrary bit length value is input, how the i values p [1],. . . , And the value p [i] is not described.
Next, when a value having an arbitrary bit length is input, i values p [1],. . . The hash value computing device 10 to which a function for generating the value p [i] is added will be described.

29 shows a case where i values p [1],... With m−n bit length are inputted to the hash value computing device 10 shown in FIG. . . , Is a functional block diagram showing functions of the hash value computing device 10 to which a function for generating a value p [i] is added.
FIG. 30 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 31 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 29 will be described.
The hash value calculation device 10 illustrated in FIG. 29 includes an arbitrary length value input unit 15, a padding unit 16, and a division unit 17, in addition to the functions of the hash value calculation device 10 illustrated in FIG.

(S411: Arbitrary length value input step)
The arbitrary length value input unit 15 inputs an arbitrary bit length value M from the input device.

(S412: Padding step)
The padding unit 16 adds a predetermined value to the value M input in (S411) using the padding function pad, and processes the value M ′ having a bit length i times the mn bit length. Is generated and stored in the storage device. That is, the padding unit 16 calculates M ′ = pad (M) by the processing device to obtain the value M ′.

(S413: division step)
The dividing unit 17 divides the value M ′ generated in (S412) into i pieces by the processing device, and the values p [1],. . . , Value p [i] is generated and stored in the storage device. That is, the dividing unit 17 sets M ′ = p [1] ||. . . || p [i] is calculated by the processing unit and the values p [1],. . . , Value p [i] is obtained.

(S414: Default length input step)
The predetermined length value input unit 11 receives the values p [1],. . . , Value p [i] is input by an input device.

  The processing from (S415) to (S420) is the same as the processing from (S402) to (S407).

An example of the padding method in (S412) will be described.
FIG. 32 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 29 when performing a predetermined padding process described below.
In (S412), the padding unit 16 adds “1 || 0... 0 || <M> to the value M input in (S411), i times the mn bit length. A bit length value M ′ is generated by the processing unit, where <M> is a 64-bit representation of the bit length | M |
Thus, the difficulty of collision can be increased by generating the value M ′ by padding.

  As in the first embodiment, the value of i may not be determined in advance, but the value of i may be determined according to the input arbitrary bit length value M.

Next, an example in which SHA-256 is used as the compression function of the hash value computing device 10 shown in FIG. 32 will be described. Note that the compression function of SHA-256 is called SHA256. SHA256 is a function that outputs a 256-bit value when two values, a 256-bit value and a 512-bit value, are input.
FIG. 33 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 29 when SHA-256 is used as the compression function.

In (S411), the arbitrary length value input unit 15 inputs a value M having an arbitrary bit length.
In (S412), the padding unit 16 adds a predetermined value to the value M input in (S411) using the padding function pad, and is i times the 256 (= 512-256) bit length. A bit length value M ′ is generated.
In (S413), the dividing unit 17 divides the value M ′ generated in (S412) into i pieces and divides the values p [1],. . . , Value p [i].
In (S414), the predetermined length value input unit 11 performs the 256-bit length values p [1],. . . , Input the value p [i].
In (S415), the fixed value adding unit 12 receives the 256-bit length values p [1],. . . , Value p [i], a fixed value const [1],. . . , A fixed value const [i] is added to the value x [1],. . . , Value x [i].
In (S416), the compression function calculation unit 13 uses the fixed value IV1 of 256 bits and the value x [1] of 512 bits generated in (S415) as the input of the compression function h, and c [1] = h (IV1, x [1]) is calculated to obtain a 256-bit long value c [1].
In (S417), the compression function calculation unit 13 inputs the value c [j-1] having a 256-bit length and the value x [j] having a 512-bit length to the compression function h in order from j = 2 to i-1. C [j] = h (c [j−1], x [j]) is calculated to obtain a 256-bit long value c [j].
In (S418), the permutation function calculation unit 19 uses the value c [i−1] of 256 bits calculated in (S417) as an input of the permutation function π, and c ′ [i−1] = π (c [ i-1]) to obtain a 256-bit long value c ′ [i−1].
In (S419), the compression function calculation unit 13 calculates the 256-bit length value c ′ [i−1] calculated in (S418) and the 512-bit length value x [i] generated in (S415). As the input of the compression function h, c [i] = h (c ′ [i−1], x [i]) is calculated to obtain a 256-bit long value c [i].
In (S420), the output unit 14 outputs the value c [i] calculated in (S419).

  The hash function configured by the hash value calculation device 10 according to the fourth embodiment cannot be strongly distinguished from a random oracle even if the compression function h is an ideal compression function whose quasi-unidirectionality is broken. It becomes a hash function that satisfies the characteristics.

  Note that, as in the first embodiment, the calculation is not necessarily performed according to the above-described processing order. When the stream processing can be performed, the calculation may be performed by the stream processing.

Similarly to the first embodiment, the compression function calculation unit 13 inputs an input value to a compression function calculation device provided outside the hash value calculation device 10 and causes the compression function calculation device to calculate the compression function h. Thus, the result of calculating the compression function h may be obtained.
Similarly, the replacement function calculation unit 19 inputs the input value to the replacement function calculation device provided outside the hash value calculation device 10 and causes the replacement function calculation device to calculate the replacement function π, thereby performing the replacement function calculation. You may obtain the result of having calculated.

  In addition, the compression function calculation unit 13 receives the values c [1],. . . , C [i], the compression function h used for calculating the value c [i] may be the same compression function h or different compression functions h.

That is, the hash value calculation device 10 according to the fourth embodiment is summarized as follows.
The hash value arithmetic unit 10 is configured to input i m-s bit input values p [1],. . . , P [i], the n-bit fixed value IV1, the first message p [1], and the n-bit fixed value const [1] are input to the compression function arithmetic unit, and the output c [1] is obtained. Next, the n-bit value c [1], the second message p [2], and the n-bit fixed value const [2] are input to the compression function arithmetic unit, and the output c [2] is obtained. This process is similarly performed up to the (i-1) th message, and the output value c [i-1] is obtained. c = π (c [i−1]) is calculated by using an arbitrary permutation function π on n bits having no fixed point. An n-bit value c, an i-th message p [i], and an n-bit fixed value const [i] are input to the compression function arithmetic unit, and an output c [i] is obtained. Then, c [i] is output.

  In addition, the hash value calculation device 10 uses an arbitrary padding processing device that receives an arbitrary length value from an arbitrary length value M and outputs an mn bit value, and is a multiple of mn bits. A message M ′ is generated. Using a split processor, M 'is converted into i mn bit values p [1],. . . , P [i].

  Further, the hash value computing device 10 changes the padding processing device to M || 1 || 0. . . 0 || <M>. However, <M> represents the bit length of M in 64 bits.

  Further, the hash value calculation device 10 is characterized in that a compression function calculation device of SHA-256 is used as the compression function calculation device.

Embodiment 5 FIG.
In the fifth embodiment, even when the hash function is different from that of the fourth embodiment and is configured using an ideal compression function whose quasi-unidirectionality has been broken, random oracles and so-called strong discrimination failures are not used. The hash value calculation device 10 that constitutes a new hash function that is possible will be described.

FIG. 34 is a functional block diagram illustrating functions of the hash value computing device 10 according to the fifth embodiment.
FIG. 35 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 36 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value calculation device 10 shown in FIG. 34 will be described.
The hash value calculation device 10 shown in FIG. 34 includes a predetermined length value input unit 11, a fixed value addition unit 12, a compression function calculation unit 13, an output unit 14, an exclusive OR calculation unit 18, and a substitution function calculation unit 19.

(S501: Default length input step)
The predetermined length value input unit 11 includes i values p [1],. . . , Value p [i] is input by the input device and stored in the storage device.

(S502: exclusive OR calculation step)
The exclusive OR calculator 18 calculates the value p [1],... Of the m-s bit length input in (S501). . . , P [i] and an m-s bit length fixed value y stored in advance in the storage device as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing device to obtain a value sum of m-s bit length and stored in the storage device.

(S503: fixed value addition step)
The fixed value adding unit 12 receives the m-s bit length values p [1],. . . , Values p [i], s bit length fixed values const [1],. . . , A fixed value const [i], and an m-bit length value x [1],. . . , Value x [i] is generated by the processing device and stored in the storage device.
That is, the fixed value adding unit 12 adds the fixed value const [1] to the value p [1] to generate the value x [1]. The fixed value adding unit 12 adds the fixed value const [2] to the value p [2] to generate the value x [2]. Similarly, j = 3,. . . , I, the fixed value adding unit 12 adds the fixed value const [j] to the value p [j] to generate the value x [j].
Note that j = 1,. . . , I−1, the position where the fixed value const [j] is added to the value p [j] may be anywhere. That is, the fixed value const [j] may be added before or after the value p [j], or may be inserted between the values p [j].
Further, the fixed value const [1] ≠ fixed value const [2] ≠. . . ≠ Fixed value const [i]. For example, j = 1,. . . , I, the fixed value const [j] is a value <j> in which j is expressed by s bits.

(S504: First compression function calculation step)
The compression function calculator 13 uses the n-bit fixed value IV1 stored in the storage device in advance and the m-bit length value x [1] generated in (S503) as an input of the compression function h, and c [1] = H (IV1, x [1]) is calculated by the processing device to obtain an n-bit length value c [1] and stored in the storage device.

(S505: Second compression function calculation step)
The compression function calculation unit 13 sequentially inputs the value c [j−1] having an n-bit length and the value x [j] having an m-bit length from j = 2 to i, and inputs c [j] = h (c [j−1], x [j]) is calculated by the processing device to obtain a value c [j] having an n-bit length and stored in the storage device.
That is, first, the compression function calculation unit 13 receives the value c [1] of the n-bit length calculated in (S504) and the value x [2] of the m-bit length generated in (S503) as c [2] = h (c [1], x [2]) is calculated by the processing device to obtain an n-bit length value c [2].
Next, the compression function calculation unit 13 receives the calculated n-bit length value c [2] and the m-bit length value x [3] generated in (S503) as input, and c [3] = h (C [2], x [3]) is calculated by the processing device to obtain an n-bit length value c [3].
By repeating this, finally, the compression function calculation unit 13 inputs the calculated n-bit length value c [i−1] and the m-bit length value x [i] generated in (S503). C [i] = h (c [i−1], x [i]) is calculated by the processing device to obtain an n-bit length value c [i].

(S506: Substitution function calculation step)
The replacement function calculation unit 19 uses the processing device to calculate c ′ [i] = π (c [i]) using the n-bit length value c [i] calculated in (S505) as an input of the replacement function π. N-bit length value c ′ [i] is obtained and stored in the storage device.
The replacement function π is a replacement function that replaces a value a ′ different from the value a when an arbitrary value a is input, and the input value a is output as it is when the value a is input. It is a replacement function without That is, the replacement function π is a replacement function that does not have a fixed point such that π (a) = a.

(S507: third compression function calculation step)
The compression function calculation unit 13 adds the value c ′ [i] of the n-bit length calculated in (S506) and the value sum of the m-s bit length calculated in (S502) to a fixed value const [ c [i + 1] = h (c ′ [i], x [i + 1]) is calculated by the processing device using m [i + 1] with x [i + 1] added with i + 1] as an input to the compression function h, and nbit length The value c [i + 1] is obtained and stored in the storage device.
Note that the fixed value const [i + 1] ≠ fixed value const [1] ≠. . . ≠ Fixed value const [i]. For example, the fixed value const [i + 1] is a value <i + 1> in which i + 1 is expressed by s bits.
Further, the position where the fixed value const [i + 1] is added to the value sum may be anywhere. That is, the fixed value const [i + 1] may be added before or after the value sum, or may be inserted between the values sum.

(S508: Output step)
The output unit 14 outputs the value c [i + 1] calculated in (S507) from the output device.

  When i = 1, that is, when only one value p [1] is input in (S501), (S505) is not executed. That is, after obtaining the value c [1] in (S504), the value c [1] is input in (S506) to obtain the value c '[1]. In step S507, the value c '[1] and the value x [2] obtained by adding the fixed value const [i + 1] to the value sum are input to obtain the value c [2].

The above is summarized as follows.
First, the hash value computing device 10 is sum = p [1] xor,. . . , Xor p [i] xor y is calculated by the processing unit.
Further, the hash value calculation device 10 calculates c [j] = h (c [j−1], p [j] || <j>) in order from j = 1 to i. Here, c [0] is IV1.
Next, the hash value calculation device 10 calculates c [i + 1] = h (π (c [i]), sum || <i + 1>).
Then, the hash value calculation device 10 outputs the value c [i + 1].

In the above description, in (S501), the predetermined length value input unit 11 determines that the i values p [1],. . . , The value p [i] is input. However, normally, the value input to the hash function is one arbitrary bit length value. In other words, in the above description, when one arbitrary bit length value is input, how the i values p [1],. . . , And the value p [i] is not described.
Next, when an arbitrary bit length value is input, i values p [1],. . . The hash value computing device 10 to which a function for generating the value p [i] is added will be described.

FIG. 37 illustrates the case where i values p [1],... With m−s bit length are input to the hash value computing device 10 illustrated in FIG. . . , Is a functional block diagram showing functions of the hash value computing device 10 to which a function for generating a value p [i] is added.
FIG. 38 is a flowchart showing the operation of the hash value computing device 10 shown in FIG.
FIG. 39 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG.

The function and operation of the hash value computing device 10 shown in FIG. 37 will be described.
The hash value calculation device 10 illustrated in FIG. 37 includes an arbitrary length value input unit 15, a padding unit 16, and a division unit 17 in addition to the functions provided in the hash value calculation device 10 illustrated in FIG.

(S511: Arbitrary length value input step)
The arbitrary length value input unit 15 inputs an arbitrary bit length value M from the input device.

(S512: Padding step)
The padding unit 16 adds a predetermined value to the value M input in (S511) using the padding function pad, and processes the value M ′ having a bit length i times the m-s bit length. Is generated and stored in the storage device. That is, the padding unit 16 calculates M ′ = pad (M) by the processing device to obtain the value M ′.

(S513: Division step)
The dividing unit 17 divides the value M ′ generated in (S512) into i pieces by the processing device, and sets the values p [1],. . . , Value p [i] is generated and stored in the storage device. That is, the dividing unit 17 sets M ′ = p [1] ||. . . || p [i] is calculated by the processing unit and the values p [1],. . . , Value p [i] is obtained.

(S514: Default length input step)
The predetermined length value input unit 11 receives the values p [1],. . . , Value p [i] is input by an input device.

  The processing from (S515) to (S521) is the same as the processing from (S502) to (S508).

An example of the padding method in (S512) will be described.
FIG. 40 is a structural diagram of a hash function realized by the hash value calculation apparatus 10 shown in FIG. 37 when the padding process described below is performed.
In (S512), the padding unit 16 performs "1 || 0 ... 0 || for the value M input in (S511), similarly to the padding method in (S112) described in the first embodiment. A value M ′ having a bit length i times the m-s bit length is generated by the processing device by adding <M>, where <M> is a 64-bit representation of the bit length | M | is there.
Thus, the difficulty of collision can be increased by generating the value M ′ by padding.

FIG. 41 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37 when the padding process described below is performed.
In (S512), the padding unit 16 adds “1 || 0... 0 to the value M input in (S511), and a value M having a bit length i times the m-s bit length. 'Is generated by the processing device.
Thus, even if padding generates the value M ′, the collision difficulty can be increased.

  As in the first embodiment, the value of i may not be determined in advance, but the value of i may be determined according to the input arbitrary bit length value M.

Next, an example in which SHA-256 is used as the compression function of the hash value computing device 10 shown in FIG. Note that the compression function of SHA-256 is called SHA256. SHA256 is a function that outputs a 256-bit value when two values, a 256-bit value and a 512-bit value, are input.
FIG. 42 is a structural diagram of a hash function realized by the hash value computing device 10 shown in FIG. 37 when SHA-256 is used as the compression function.
In the following description, the value s is assumed to be 56.

In (S511), the arbitrary length value input unit 15 inputs a value M having an arbitrary bit length.
In (S512), the padding unit 16 adds a predetermined value to the value M input in (S511) by using the padding function pad, i times the 456 (= 512-56) bit length. A bit length value M ′ is generated.
In (S513), the dividing unit 17 divides the value M ′ generated in (S512) into i pieces and 456-bit length values p [1],. . . , Value p [i].
In (S514), the predetermined length value input unit 11 receives the 456-bit length values p [1],. . . , Input the value p [i].
In (S515), the exclusive OR calculation unit 18 uses the 456-bit length values p [1],. . . , P [i] and a fixed value y of 456 bits as inputs of the exclusive OR operation, sum = p [1] xor,. . . , Xor p [i] xor y is calculated to obtain a value sum of 456 bits.
In (S516), the fixed value adding unit 12 receives the values p [1],. . . , Value p [i], a fixed value const [1],. . . , A fixed value const [i] is added to the value x [1],. . . , Value x [i].
In (S517), the compression function calculation unit 13 uses the fixed value IV1 of 256 bits and the value x [1] of 512 bits generated in (S516) as the input of the compression function h, and c [1] = h (IV1, x [1]) is calculated to obtain a 256-bit long value c [1].
In (S518), the compression function calculation unit 13 sequentially inputs a value c [j−1] of 256 bits and a value x [j] of 512 bits in length from j = 2 to i as inputs of the compression function h. c [j] = h (c [j−1], x [j]) is calculated to obtain a 256-bit long value c [j].
In (S519), the permutation function calculation unit 19 takes c ′ [i] = π (c [i]) as the input of the permutation function π using the 256-bit length value c [i] calculated in (S518). Calculate to obtain a value c ′ [i] that is 256 bits long.
In (S520), the compression function calculation unit 13 fixes the 56-bit length to the 256-bit length value c ′ [i] calculated in (S519) and the 456-bit length value sum calculated in (S515). Using a 512-bit length x [i + 1] to which the value const [i + 1] is added as an input to the compression function h, c [i + 1] = h (c ′ [i], x [i + 1]) is calculated to obtain a 256-bit length. The value c [i + 1] is obtained.
In (S521), the output unit 14 outputs the value c [i + 1] calculated in (S520).

  The hash function configured by the hash value computing device 10 according to the fifth embodiment cannot be strongly distinguished from a random oracle even if the compression function h is an ideal compression function whose quasi-unidirectionality is broken. It becomes a hash function that satisfies the characteristics.

  Note that, as in the first embodiment, the calculation is not necessarily performed according to the above-described processing order. When the stream processing can be performed, the calculation may be performed by the stream processing.

Similarly to the first embodiment, the compression function calculation unit 13 inputs an input value to a compression function calculation device provided outside the hash value calculation device 10 and causes the compression function calculation device to calculate the compression function h. Thus, the result of calculating the compression function h may be obtained.
Similarly, the exclusive OR calculator 18 inputs an input value to an exclusive OR calculator provided outside the hash value calculator 10 and performs an exclusive OR operation on the exclusive OR calculator. By calculating, an exclusive OR operation result may be obtained. Similarly, the substitution function calculation unit 19 calculates a substitution function calculation by inputting an input value to a substitution function calculation device provided outside the hash value calculation device 10 and causing the substitution function calculation device to calculate a substitution function π. Results may be obtained.

  In addition, the compression function calculation unit 13 receives the values c [1],. . . , C [i + 1] may be the same compression function h or different compression functions h.

That is, the hash value calculation apparatus 10 according to the fifth embodiment is summarized as follows.
The hash value arithmetic unit 10 is configured to input i m-s bit input values p [1],. . . , P [i], the n-bit fixed value IV1, the first message p [1], and the s-bit representation value of 1 are input to the compression function arithmetic unit, and the output c [1] is obtained. Next, the n-bit value c [1], the second message p [2], and the s-bit representation value of 2 are input to the compression function arithmetic unit, and the output c [2] is obtained. This process is similarly performed up to the i-th message, and the output value c [i] is obtained. c = π (c [i]) is calculated by using an arbitrary permutation function π on n bits having no fixed point. The compression function arithmetic unit receives an n-bit value c, sum = p [1] xor. . . xor p [i] xor y, an s-bit representation value of i + 1 is input, and its output c [i + 1] is obtained. c [i + 1] is output. Here, y is a fixed value of m−s bits.

  Further, the hash value computing device 10 is a multiple of m-s bits using an arbitrary padding processing device that receives an arbitrary length value from an arbitrary length value M and outputs an m-s bit value. A message M ′ is generated. Using a split processor, M 'is replaced with i ms bit values p [1],. . . , P [i].

  Further, the hash value computing device 10 changes the padding processing device to M || 1 || 0. . . 0 || <M> and s = 56. However, <M> represents the bit length of M in 64 bits.

  Further, the hash value calculation device 10 changes the padding processing device to M || 1 || 0. . . 0 and s = 56.

  Further, the hash value calculation device 10 is characterized by using a SHA-256 compression function calculation device as the compression function calculation device.

  In other words, the hash value calculation apparatus 10 according to the above embodiments includes an EMD structure, an MDP structure, an operation for inputting a fixed value to the compression function, an operation for inputting a compression function number to the compression function, and an exclusive logical value of the message. A hash function is constructed using an operation that uses as a compression function input. As a result, an efficient hash function that satisfies the random oracle and the strong indistinguishability is constructed from the compression function with broken unidirectionality or the compression function with broken quasi-unidirectionality.

  The hash value calculation device 10 according to the above embodiment is a device for calculating a hash value used in a cryptographic processing device or the like that performs cryptographic processing (including signature processing).

Next, the hardware configuration of the hash value calculation device 10 in the embodiment will be described.
FIG. 43 is a diagram illustrating an example of a hardware configuration of the hash value calculation device 10.
As shown in FIG. 43, the hash value calculation apparatus 10 includes a CPU 911 (also referred to as a central processing unit, a central processing unit, a processing unit, an arithmetic unit, an arithmetic circuit, a microprocessor, a microcomputer, and a processor) that executes a program. I have. The CPU 911 is connected to the ROM 913, the RAM 914, the LCD 901 (Liquid Crystal Display), the keyboard 902 (K / B), the communication board 915, and the magnetic disk device 920 via the bus 912, and controls these hardware devices. Instead of the magnetic disk device 920 (fixed disk device), a storage device such as an optical disk device or a memory card read / write device may be used. The magnetic disk device 920 is connected via a predetermined fixed disk interface.

  The ROM 913 and the magnetic disk device 920 are examples of a nonvolatile memory. The RAM 914 is an example of a volatile memory. The ROM 913, the RAM 914, and the magnetic disk device 920 are examples of storage devices. The keyboard 902 and the communication board 915 are examples of input devices. The communication board 915 is an example of a communication device (network interface). Furthermore, the LCD 901 is an example of a display device.

  An operating system 921 (OS), a window system 922, a program group 923, and a file group 924 are stored in the magnetic disk device 920 or the ROM 913. The programs in the program group 923 are executed by the CPU 911, the operating system 921, and the window system 922.

In the program group 923, in the above description, “predetermined length value input unit 11”, “fixed value addition unit 12”, “compression function calculation unit 13”, “output unit 14”, “arbitrary length value input unit 15”, Stored are software, programs, and other programs that execute the functions described as “padding unit 16”, “dividing unit 17”, “exclusive OR calculator 18”, “replacement function calculator 19”, and the like. The program is read and executed by the CPU 911.
In the file group 924, information such as fixed values, intermediate calculation results, data, signal values, variable values, and parameters in the above description are stored as items of “file” and “database”. The “file” and “database” are stored in a recording medium such as a disk or a memory. Information, data, signal values, variable values, and parameters stored in a storage medium such as a disk or memory are read out to the main memory or cache memory by the CPU 911 via a read / write circuit, and extracted, searched, referenced, compared, and calculated. Used for the operation of the CPU 911 such as calculation / processing / output / printing / display. Information, data, signal values, variable values, and parameters are temporarily stored in the main memory, cache memory, and buffer memory during the operation of the CPU 911 for extraction, search, reference, comparison, calculation, calculation, processing, output, printing, and display. Is remembered.

In the above description, the arrows in the flowchart mainly indicate input / output of data and signals, and the data and signal values are recorded in a memory of the RAM 914, other recording media such as an optical disk, and an IC chip. Data and signals are transmitted online by a bus 912, signal lines, cables, other transmission media, and radio waves.
In addition, what is described as “to part” in the above description may be “to circuit”, “to device”, “to device”, “to means”, and “to function”. It may be “step”, “˜procedure”, “˜processing”. In addition, what is described as “˜device” may be “˜circuit”, “˜device”, “˜device”, “˜means”, “˜function”, and “˜step”, “ ~ Procedure "," ~ process ". Furthermore, what is described as “to process” may be “to step”. That is, what is described as “˜unit” may be realized by firmware stored in the ROM 913. Alternatively, it may be implemented only by software, or only by hardware such as elements, devices, substrates, and wirings, by a combination of software and hardware, or by a combination of firmware. Firmware and software are stored in a recording medium such as ROM 913 as a program. The program is read by the CPU 911 and executed by the CPU 911. That is, the program causes a computer or the like to function as the “˜unit” described above. Alternatively, the computer or the like is caused to execute the procedures and methods of “to part” described above.

  DESCRIPTION OF SYMBOLS 10 Hash value arithmetic unit, 11 Default length value input part, 12 Fixed value addition part, 13 Compression function calculation part, 14 Output part, 15 Arbitrary length value input part, 16 Padding part, 17 Dividing part, 18 Exclusive OR calculation Part, 19 substitution function calculation part.

Claims (2)

I values p [1],. . . , Value p [i], for a predetermined natural number m and a natural number n smaller than the natural number m, the value p [1],. . . , A predetermined length input unit for inputting the value p [i],
The mn bit length values p [1],. . . , Value p [i], i−1 values p [1],. . . , Values p [i−1], n-bit fixed values const [1],. . . , A fixed value const [i−1], and an m-bit length value x [1],. . . , A fixed value adding unit that generates a value x [i−1] and stores it in the storage device;
In order from j = 1 to i−1, an n-bit value c [j−1] (value c [0] is an n-bit fixed value IV1) and m bits generated by the fixed value adding unit By inputting the length value x [j] and obtaining the n-bit length value c [j] which is the result of calculating the compression function h, the n-bit length value c [i-1] is obtained and stored. Memorize in the device,
a fixed value IV2 of n bit length, m-n to the value p [i] of the bit length of an n-bit length value c [i-1] by adding the m-bit length of the value x [i] as input, compression A compression function calculation unit that obtains an n-bit length value c [i], which is a result of calculating the function h, and stores it in a storage device;
A hash value calculation device comprising: an output unit that outputs a value c [i] obtained by the compression function calculation unit. The hash value calculation device further includes:
An arbitrary length value input unit for inputting an arbitrary bit length value M;
A padding unit for adding a predetermined value to the value M input by the arbitrary length value input unit to generate a value M ′ having a bit length i times mn bit length and storing the value M ′ in a storage device;
The value M ′ generated by the padding unit is divided into values p [1],. . . , A dividing unit that generates a value p [i] and stores it in a storage device,
The predetermined length value input unit includes the values p [1],. . . , The hash value calculation device according to claim 1, characterized in that the input values p [i].

Images