Patent ID: 8589688

Claim:
A message authentication device comprising: an input unit which inputs a message; a padding unit which pads the message, sets its length always to a multiple of a block length, and outputs the message as a padded message; a binary tree hash unit which compresses the padded message, by dividing the padded message into a plural number of blocks in the block length, inputting each of the blocks to each of leaves of a binary tree then outputting a hash value of the block length in the root of the binary tree, wherein the binary tree includes repetitions of keyed hash functions, wherein each of the keyed hash functions obtains a first result which is a result of an exclusive-or function of a first block which is one of the blocks and a key which is the key of one of different keys in accordance with the depth of the binary tree based on a block cipher, obtains a second result which is a result of a substituted first result by a keyed or unkeyed one block substitution based on parts of the block cipher, and outputs the hash value which is a result of an exclusive—or function of the second result and a second block which is another block of the blocks; an adjustment value added encryption unit which encrypts the hash values so as to set a tag; and an output unit which couples and outputs the tag and the message.