Granted Patent B2

US 12,580,736 · App. 18/437,877 · Granted Mar 17, 2026

Inventor: Yusuke Naito (Tokyo, JP)

Assignee: MITSUBISHI ELECTRIC CORPORATION

H04L9/0643H04L9/0618

Abstract

Claims (103)

1 . A hash value computation device to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation device comprising

processing circuitry to:

compute a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits,

compute the hash value H from the output value S′[1] and the output value S′[2] that have been computed, compute the block cipher E using as input the input value S[2] and a value X of k bits computed from the input value M* and the input value S[1], so as to compute a value Y of n bits,

compute the block cipher E using as input the value Y and a value Z of k bits computed from the input value S[1], the input value M*, and the value Y, so as to compute a value U of n bits,

compute the value S′[1] and the value S′[2] using at least one of the value Y and the value U, and

output the ciphertext of n bits,

wherein the processing circuitry includes a processor and a memory,

the processor is configured to store intermediate values while computing in the memory, and

a required memory size in the memory for outputting the ciphertext of n bits is k+n bits.

2 . The hash value computation device according to claim 1 ,

wherein the value X is a value output by a permutation function mi using as input a bit string obtained from the input value S[1] and the input value M*,

wherein the value Z is a value obtained by concatenating an exclusive OR of a value W[1] of n bits and a value Y′ with a value W[2] of k−n bits, the value W[1] being a bit string extracted from a value W output by a permutation function π 2 using as input a bit string obtained from the input value S[1] and the input value M*, the value Y′ being a value output by a permutation function π 3 using as input the value Y, the value W[2] being a value that remains after the value W[1] is excluded from the value W,

wherein the value S′[1] is an exclusive OR of a value Z′[1] and a value U′, the value Z′[1] being a value output by a permutation function π 4 using as input a value Z [1] of n bits, which is a bit string extracted from the value Z, the value U′ being a value output by a permutation function π 5 using as input the value U, and

wherein the value S′[2] is the value U.

3 . A hash value computation device to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation device comprising

processing circuitry configured to:

compute a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits,

compute the hash value H from the output value S′[1] and the output value S′[2] that have been computed, and

divide a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits,

wherein the processing circuitry sets a value S[1, 0] as a fixed value IV[1] and sets a value S[2, 0] as a fixed value IV[2], and computes the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value [1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m in ascending order,

computes the hash value H from a value S[1, m] and a value S[2, m], and

wherein the processing circuitry includes a processor and a memory,

the processor is configured to store intermediate values while computing in the memory, and

a required memory size in the memory for outputting the ciphertext of n bits is k+n bits.

4 . The hash value computation device according to claim 3 ,

wherein the processing circuitry generates a value W′ of k bits by adding k-2n bits to a value obtained by interchanging first n bits and remaining n bits of the computed hash value H, where k≥2n,

computes the output value S′[1] as a value H′[1] and the output value S′[2] as a value H′[2] by the function CF using a value V[1] of k−n bits as the input value M*, a value V[2] as the input value S[1], and a fixed value IV[3] as the input value S[2], the value V[1] being a bit string extracted from a value V output by a permutation function π 6 using as input the generated value W′, the value V[2] being a bit string that remains after the value V[1] is excluded from the value V, and

computes a hash value H′ from the value H′[1] and the value H′[2].

5 . A hash value computation device to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation device comprising

processing circuitry configured to:

compute a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits,

compute the hash value H from the output value S′[1] and the output value S′[2] that have been computed, and

divide a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits,

wherein the processing circuitry sets a value S[1, 0] as a fixed value IV[1] and sets a value S[2, 0] as a fixed value IV[2], and computes the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value S[1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m−1 in ascending order,

computes the output value S′[1] as a value S[1, m] and the output value S′[2] as a value S[2, m] by the function CF using a value M[m] as the input value M*, an exclusive OR of a value S[1, m-1] and a non-zero fixed value Const [1] as the input value S[1], and an exclusive OR of a value S[2, m-1] and a non-zero fixed value Const [2] as the input value S[2],

computes the hash value H from the value S[1, m] and the value [2, m], and

output the ciphertext of n bits,

wherein the processing circuitry includes a processor and a memory,

the processor is configured to store intermediate values while computing in the memory, and

a required memory size in the memory for outputting the ciphertext of n bits is k+n bits.

6 . The hash value computation device according to claim 5 ,

wherein the processing circuitry uses a different value as each of the fixed value Const [1] and the fixed value Const [2] in each case of a case where the value M is a multiple of k−n bits and a case where the value M is not a multiple of k−n bits.

7 . A hash value computation method for computing a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation method comprising:

computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits;

computing the hash value H from the output value S′[1] and the output value S′[2];

computing the block cipher E using as input the input value S[2] and a value X of k bits computed from the input value M* and the input value S[1], so as to compute a value Y of n bits;

computing the block cipher E using as input the value Y and a value Z of k bits computed from the input value S[1], the input value M*, and the value Y, so as to compute a value U of n bits;

computing the value S′[1] and the value S′[2] using at least one of the value Y and the value U; and

outputting the ciphertext of n bits,

wherein the hash value computation method is performed by processing circuitry including a processor and a memory,

the processor stores intermediate values while computing in the memory, and

a required memory size in the memory for the hash value computation method is k+n bits.

8 . A hash value computation method for computing a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation method comprising:

computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits;

computing the hash value H from the output value S′[1] and the output value S′[2];

dividing a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits;

setting a value S[1, 0] as a fixed value IV[1] and setting a value S[2, 0] as a fixed value IV[2], and computing the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value [1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m in ascending order;

computing the hash value H from a value S[1, m] and a value S[2, m]; and

outputting the ciphertext of n bits,

wherein the hash value computation method is performed by processing circuitry including a processor and a memory,

the processor stores intermediate values while computing in the memory, and

a required memory size in the memory for the hash value computation method is k+n bits.

9 . A hash value computation method for computing a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation method comprising:

computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits;

computing the hash value H from the output value S′[1] and the output value S′[2];

dividing a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits;

setting a value S[1, 0] as a fixed value IV[1] and setting a value S[2, 0] as a fixed value IV[2], and computing the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value S[1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m−1 in ascending order;

computing the output value S′[1] as a value S[1, m] and the output value S′[2] as a value S[2, m] by the function CF using a value M[m] as the input value M*, an exclusive OR of a value S[1, m-1] and a non-zero fixed value Const [1] as the input value S[1], and an exclusive OR of a value S[2, m-1] and a non-zero fixed value Const [2] as the input value S[2];

computing the hash value H from the value S[1, m] and the value [2, m]; and

outputting the ciphertext of n bits,

wherein the hash value computation method is performed by processing circuitry including a processor and a memory,

the processor stores intermediate values while computing in the memory, and

a required memory size in the memory for the hash value computation method is k+n bits.

10 . A non-transitory computer readable medium storing a hash value computation program to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation program causing a computer to function as a hash value computation device to perform:

a function computation process of computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits; and

a hash value computation process of computing the hash value H from the output value S′[1] and the output value S′[2] computed by the function computation process,

wherein the function computation process performs

a first cryptographic computation process of computing the block cipher E using as input the input value S[2] and a value X of k bits computed from the input value M* and the input value S[1], so as to compute a value Y of n bits,

a second cryptographic computation process of computing the block cipher E using as input the value Y and a value Z of k bits computed from the input value S[1], the input value M*, and the value Y, so as to compute a value U of n bits,

an output computation process of computing the value S′[1] and the value S′[2] using at least one of the value Y and the value U, and

outputting the ciphertext of n bits,

wherein the hash value computation program causes a processor of the of the hash value computation device to store intermediate values while computing in a memory of the hash value computation device, and

a required memory size in the memory for outputting the ciphertext is k+n bits.

11 . A non-transitory computer readable medium storing a hash value computation program to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation program causing a computer to function as a hash value computation device to perform:

a function computation process of computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits;

a hash value computation process of computing the hash value H from the output value S′[1] and the output value S′[2] computed by the function computation process;

a division process of dividing a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits; and

outputting the ciphertext of n bits,

wherein the function computation process sets a value S[1, 0] as a fixed value IV[1] and sets a value S[2, 0] as a fixed value IV[2], and computes the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value [1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m in ascending order,

wherein the hash value computation process computes the hash value H from a value S[1, m] and a value S[2, m],

wherein the hash value computation program causes a processor of the hash value computation device to store intermediate values while computing in a memory of the hash value computation device, and

a required memory size in the memory for outputting the ciphertext is k+n bits.

12 . A non-transitory computer readable medium storing a hash value computation program to compute a hash value H of 2n bits using a block cipher E that takes as input a key K of k bits and a plaintext block P of n bits, which is a smaller number of bits than k bits, and outputs a ciphertext of n bits, the hash value computation program causing a computer to function as a hash value computation device to perform:

a function computation process of computing a function CF that processes the block cipher E a plurality of times sequentially on an input value M* of k−n bits, an input value S[1] of n bits, and an input value S[2] of n bits so as to compute an output value S′[1] of n bits and an output value S′[2] of n bits;

a hash value computation process of computing the hash value H from the output value S′[1] and the output value S′[2] computed by the function computation process; and

a division process of dividing a value M′ at every k−n bits to generate a value M[1], . . . , a value M[m], the value M′ being a value obtained by padding a value M for which a hash value is computed so as to make the value M a multiple of k−n bits when the value M is not a multiple of k−n bits; and

outputting the ciphertext of n bits,

wherein the function computation process sets a value S[1, 0] as a fixed value IV[1] and sets a value S[2, 0] as a fixed value IV[2], and computes the output value S′[1] as a value S[1, i] and the output value S′[2] as a value S[2, i] by the function CF using a value M[i] as the input value M*, a value S[1, i-1] as the input value S[1], and a value S[2, i-1] as the input value S[2], for each integer i of i=1, . . . , m−1 in ascending order, and

computes the output value S′[1] as a value S[1, m] and the output value S′[2] as a value S[2, m] by the function CF using a value M[m] as the input value M*, an exclusive OR of a value S[1, m-1] and a non-zero fixed value Const [1] as the input value S[1], and an exclusive OR of a value S[2, m-1] and a non-zero fixed value Const [2] as the input value S[2],

wherein the hash value computation process computes the hash value H from the value S[1, m] and the value [2, m],

wherein the hash value computation program causes a processor of the hash value computation device to store intermediate values while computing in a memory of the hash value computation device, and

a required memory size in the memory for outputting the ciphertext is k+n bits.

Assignments (1)

Continuity (2)

References Cited (25)