Provided is a storage device which partitions data from a host into multiple partitioned data and distributes, encrypts and stores them together with a parity to and in multiple memory mediums. This storage device executes processing of restoring the partitioned data or the parity stored in a memory medium to be subject to encryption re-key based on decrypted data of the partitioned data or the parity stored in each memory medium other than the memory medium to be subject to encryption re-key among the multiple memory mediums, storing the restored partitioned data or the parity in a backup memory medium while encrypting the restored partitioned data or the parity with a new encryption key, and thereafter interchanging the backup memory medium and the memory medium to be subject to encryption re-key so that the backup memory medium will be a memory medium configuring the parity group and the memory medium to be subject to encryption re-key will be the backup memory medium.