To generate and verify signature data using a known signature algorithm whose safety is ensured from the viewpoint of calculation quantity and ensuring the authenticity thereof over a long time period. A message to be signed is transmitted, a padding-data item is added to the message, and a signature-data item of the message with the padding-data item added thereto is generated by using a hash function and a public-key cryptosystem. The addition step and the generation step are performed a predetermined number of times by using the signature-data item, as the padding-data item, and the signature-data items generated the predetermined number of times and the padding-data items added the predetermined number of times are externally transmitted with the message.