A storage device is provided. The storage device includes a boot ROM stores a plurality of public keys and a boot ROM image, an OTP memory identifies a first public key among the plurality of public keys, a first memory including a first area the stores the plurality of public keys and a flash boot image different from the boot ROM image, and a second area that stores a first boot signature corresponding to the flash boot image, a second memory including a first firmware image including a first firmware signature, and a memory controller that receives a second firmware image including a second firmware signature and a second boot signature, receives a second public key among the plurality of public keys and the flash boot image based on the second firmware image being received, and write the second boot signature in the second area of the first memory.