An authentication system performs user authentication between a client and a server using a one-time password. Each of the client and the server generates random authentication data. The generated random authentication data is exchanged between the client and the server. In this way, authentication based on a complete random authentication data not using specific one-time password generation logic can be provided. Furthermore, by applying the method for authentication and the method for updating a one-time password according to the present invention, spoofing can be detected even when a password is stolen. As a result, unauthorized access can be prevented.