# US 2024/0187215 A1 · Hash value computation device, hash value computation method, and computer readable medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0187215 A1
- Document ID: US20240187215A1
- Status: Published application
- Kind: A1
- Application number: 18/437,877
- Filed: 2024-02-09
- Published: 2024-06-06
- Earliest claimed: 2021-10-01
- Assignees: Mitsubishi Electric Corporation
- Applicants: Mitsubishi Electric Corporation
- Inventors: Yusuke NAITO
- Web page: https://patentgrep.com/patent/US20240187215A1

## CPC

- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A hash value computation device (10) computes 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. A function computation unit (22) computes 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 unit (23) computes the hash value H from the output value S′[1] and the output value S′[2].

## Claims

### Claim 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 cyphertext 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, and
compute the value S′[1] and the value S′[2] using at least one of the value Y and the value U.

### Claim 2 (depends on 1)

The hash value computation device according to claim 1,
wherein the value X is a value output by a permutation function π1 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.

### Claim 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 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, and
computes the hash value H from a value S[1, m] and a value S[2, m].

### Claim 4 (depends on 3)

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].

### Claim 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 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], and
computes the hash value H from the value S[1, m] and the value [2, m].

### Claim 6 (depends on 5)

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.

### Claim 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; and
computing the value S′[1] and the value S′[2] using at least one of the value Y and the value U.

### Claim 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; and
computing the hash value H from a value S[1, m] and a value S[2, m].

### Claim 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]; and
computing the hash value H from the value S[1, m] and the value [2, m].

### Claim 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, and
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.

### Claim 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; 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,
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, and
wherein the hash value computation process computes the hash value H from a value S[1, m] and a value S[2, m].

### Claim 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,
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], and
wherein the hash value computation process computes the hash value H from the value S[1, m] and the value [2, m].
