An authentication system that can show having an authentic computer program, can certify the authenticity of itself, and can verify the certification. The authentication system is composed of a terminal (requesting device) and a card (verifying device). The card stores secret information to be used by the terminal, and an update program for the terminal. The card verifies authenticity of the terminal using information obtained from the terminal. When it judges that the terminal is authentic, the card outputs the secret information to the terminal. When it judges that the terminal is not authentic, the card outputs the update program. With this structure, the terminal is forced to update the program when it attempts to use the secret information.