1. A hash value calculation apparatus, which calculates a hash value of a message, comprising: an input unit adapted to input an extended block obtained from a message to be processed; a hash value calculation unit adapted to execute a hash value calculation of the input block and to output a hash intermediate value; a plurality of intermediate value storage units adapted to store the hash intermediate value output by said hash value calculation unit for the message to be processed; an output unit adapted to output a hash intermediate value associated with all blocks of the message to be processed as a hash value of the message; and a hash value calculation control unit adapted to control hash value calculations for a plurality of messages by switching said intermediate value storage units used to store the hash intermediate value output from said hash value calculation unit.