A data storage device using a FLASH memory with replay-protected blocks. The storage space of the FLASH memory is divided into blocks and each block is further divided into pages. A controller is provided in the data storage device to couple to the FLASH memory. The controller manages at least one replay-protected memory block of the FLASH memory. The controller programs a success flag and a write count into a system block of the FLASH memory after the controller programs two pages into the at least one replay-protected memory block of the FLASH memory. The controller may perform a power restoration process based on the success flag of the system block or/and based on the amount of programmed pages of the at least one replay-protected memory block.