A method and apparatus of transmitting data using authentication between a first device and a second device are provided. The method includes transmitting an encrypted certificate of the first device using a shared key shared by the first device and the second device, receiving authentication key generation information for generating an authentication key, which is received when it is determined that the certificate of the first device is valid and not revoked, generating a first random number and generating an authentication key based on the first random number and the authentication key generation information, and encrypting and transmitting data using the authentication key.