A storage device includes: a memory cell array including a plurality of memory cells connected to a plurality of word lines and a plurality of bit lines; a physical unclonable function (PUF) circuit configured to output PUF data based on a voltage difference between two memory cells from among the plurality of memory cells, the two memory cells being connected to a word line from among the plurality of word lines and two bit lines from among the plurality of bit lines, and to which a same data are programmed; and a memory controller configured to receive the PUF data from the PUF circuit, and program the PUF data or an inverted value of the PUF data to one of the two memory cells based on a value of the PUF data.