Patent ID: 8001384

Claim:
An authentication system, comprising: a proving device for storing held information; and a verification device connected to the proving device so as to communicate with the proving device, the verification device verifying that the held information is the same as comparative information; wherein the verification device comprises: a first storage section for storing verification information, and storing first random information; an authentication information generation factor generation section for generating an authentication information generation factor by using the first random information stored in the first storage section; a first transmitting section for transmitting the authentication information generation factor generated by the authentication information generation factor generation section to the proving device; a first receiving section for receiving authentication information transmitted by the proving device; and a decision section for deciding whether a predetermined relationship is established between the authentication information received by the first receiving section and the verification information and the first random information which are stored in the first storage section; the proving device comprises: a second storage section for storing the held information; a second receiving section for receiving the authentication information generation factor transmitted by the first transmitting section; an authentication information generation section for generating the authentication information by using the authentication information generation factor received by the second receiving section and the held information stored in the second storage section; and a second transmitting section for transmitting the authentication information generated by the authentication information generation section to the verification device; wherein the verification information is a result C(s′) of modular exponentiation whose modulus is a constant N, base is a value g smaller than N, and exponent is the comparative information s′; the authentication information generation factor is a result R of modular exponentiation whose modulus is a constant N, base is the value g, and exponent is the first random information r; the authentication information is a result R(s) of modular exponentiation whose modulus is N, base is the authentication information generation factor R, and exponent is the held information s; and the decision section decides whether or not a result of modular exponentiation whose modulus is N, base is the verification information C(s′), and exponent is the first random information is equal to the authentication information R(s).