A key data recording device includes a key data recording medium section which stores key data of the encrypted data; and a reading/writing section which reads and writes the key data from and into the key data recording medium section, which sections are contained in a cartridge casing accommodatable in a library unit. When the cartridge casing is irregularly ejected from the library unit, the key data recorded in the key data recording medium section is deleted. This configuration can enhance the confidentiality of encrypted data because the key data is not leaked even when the recording medium in which key data of the encrypted data is recorded is carried away.