According to some embodiments, there is provided a recording device. The recording device includes: a recording medium having a plurality of sectors; a first writing module configured to write, on a first sector of the plurality of sectors, a first data encrypted using a first encryption key and first encryption key information indicative of the first encryption key; and a re-encrypting module configured to: read the first data from the recording medium; decrypt the first data using the first encryption key to generate decrypted first data; encrypt the decrypted first data using a second encryption key to generate encrypted second data; and write, on the first sector, the encrypted second data and second encryption key information indicative of the second encryption key.