A storage device in which file data is divided into multiple blocks for storage on a recording medium is provided. The storage device includes an additional data storing section for storing additional data to be recorded on the recording medium in association with the data to be written, a position determining section for determining recording positions on the recording medium where the blocks should be respectively written, based on the additional data, and a block writing section for writing the respective blocks on the recording positions on the recording medium determined by the recording position determining section. The additional data this defines a gap length between blocks of recorded data. During a read operation, if the gap length does not comport with the additional data, then an error is assumed.