There is provided an authentication method which is secure against various attacks such as a KCI attack on a public network, and can reduce a required calculation amount compared to a conventional method. In this authentication method, a mutual authentication processing technique using Diffie-Hellman type key exchange is modified to compute a master secret Ks in a server by Ks=gy, where y is a random number (yε(Z/qZ)*) generated by the server. In this method, let (G,·) be a group of order q, g be a generator of that set G, and U, WεG. “·” is a binary operator on G.