A storage device includes a basic memory to store a message received from an external device, a security memory to store an authentication key for authenticating the message, a controller to output a control signal, and a security engine to obtain the authentication key from the security memory with an authority to access the security memory in response to the control signal from the controller and to block an access of the controller to the security memory.