Provided are a method of generating a message authentication code and an authentication device and an authentication request device using the method. The method includes generating a second secret key by encrypting seed data, a first secret key, and first auxiliary data using an encryption algorithm; and encrypting the seed data, the second secret key, and second auxiliary data using the encryption algorithm, wherein the encryption algorithm receives data of a preset base number of bits and encrypts the received data, and the number of bits of the second auxiliary data varies according to a difference between the number of bits of the first secret key and the number of bits of the second secret key.