A verification data generating apparatus generates data that can be stored in a terminal device without sustaining unauthorized operations and has assured continuity in the order of being output. In the apparatus, a verification data holding element holds a verification data. A data generation element generates a data body at a predetermined timing. Whenever the data body is generated, a verification value generation element generates a new verification value based on the verification value held in the verification value holding element and the data body newly generated. The verification value held in the verification value holding element is then updated with the new verification value. A data storage element stores the data bodies generated by the data generating element in order. On receiving a verification data outputting request, a verification data outputting element generates a signature value based on the verification value held in the verification value holding element and outputs verification data generated by concatenating the signature value with the data body stored in the data storing element.