Patent ID: 8108682

Claim:
A hash value generator for compressing a message having an arbitrary length and thereby generating a digest of the message, comprising: a message padding unit for receiving as an input thereto a message M having an arbitrary length, executing padding processing for the message M, the message M being divided into message blocks each having a fixed length, and sequentially outputting a fixed-length message block M[i] according to a clock i, a register for storing therein an intermediate value of conversion processing, an initializer unit for setting an initial value to the register, a compression unit for conducting a conversion according to the clock i by use of the value stored in the register and the message block M[i] output from the message padding unit and thereby producing as an output therefrom a conversion result having a length of the register, a register control unit for updating, according to the clock i, the value of the register by use of the output from the data compression unit, and a final processing unit for producing as an output therefrom a fixed-length bit string by use of the value stored in the register, wherein: the compression unit comprises: a linear compression unit for producing as an output therefrom a conversion result having a length of the register by use of the message block M[i] and the value stored in the register; and a nonlinear permutation unit for outputting a conversion result having a length of the register by use of the output from the linear compression unit, the linear compression unit executes the following processing: T<−C *( X[ 1] XOR X[ 2] XOR . . . XOR X[w] ), Y[j]<−L[j] ( M[i ]) XOR T XOR X[j], Y<−Y[ 1]∥ Y[ 2]∥ . . . ∥ Y[w ]; and the value stored in the register is divided into message block length units, the values of which are X[1], X[2], . . . , X[w], where: A<−B indicates that B substitutes for A; A∥B indicates a concatenation of A and B, A XOR B indicates an exclusive OR between A and B for each bit, A*B is multiplication between A and B in a finite field, C is a non-zero constant, L[j]( ) indicates an output from the mutually different linear permutation unit, M[i] indicates an i-th message block outputted from the message padding unit, X is a value stored in the register, and Y is an output from the linear compression unit.