An authentication server designed to use, as a password of a user who is to be authenticated, a one-time password deriving rule for generating a one-time password by being applied to pattern elements at specific positions in a case where a plurality of pattern elements arranged in a predetermined pattern are presented to the user as a presentation pattern, and authenticates the user on a basis of a character string for authentication in which a user ID is embedded at a predetermined embedding position within the one-time password, and which is connected to an authentication request client, the authentication server comprising: a password storage unit configured to store for each of all user IDs which have already been registered, the user ID of the user, the one-time password deriving rule of the user, and a user ID embedding position which identifies an embedding position at which the user ID is to be embedded within the one-time password in association with one another in advance for said user ID; presentation pattern determination information generation means for generating presentation pattern determination information which determines the presentation pattern using a predetermined generation rule; verification code generation means for generating a verification code in which the user ID is embedded on a basis of the user ID embedding position, in a result of applying the one-time password deriving rule associated with the user ID to the pattern elements constituting the presentation pattern determined on a basis of the presentation pattern determination information for said user ID; presentation pattern determination information transmission means for transmitting the generated presentation pattern determination information to the authentication request client of the user who is to be authenticated; authentication character string reception means for receiving a character string for authentication in which the user ID is embedded at the user ID embedding position in a one-time password which is a result of applying the one-time password deriving rule to pattern elements included in the presentation pattern determined on a basis of the presentation pattern determination information, transmitted from the authentication request client; and user authentication means for comparing the received character string for authentication with the verification code generated for each of all the user IDs and making authentication of the user ID corresponding to the verification code successful in a case where the verification code which matches the received character string for authentication exists. a password storage unit configured to store for each of all user IDs which have already been registered, the user ID of the user, the one-time password deriving rule of the user, and a user ID embedding position which identifies an embedding position at which the user ID is to be embedded within the one-time password in association with one another in advance for said user ID; presentation pattern determination information generation means for generating presentation pattern determination information which determines the presentation pattern using a predetermined generation rule; verification code generation means for generating a verification code in which the user ID is embedded on a basis of the user ID embedding position, in a result of applying the one-time password deriving rule associated with the user ID to the pattern elements constituting the presentation pattern determined on a basis of the presentation pattern determination information for said user ID; presentation pattern determination information transmission means for transmitting the generated presentation pattern determination information to the authentication request client of the user who is to be authenticated; authentication character string reception means for receiving a character string for authentication in which the user ID is embedded at the user ID embedding position in a one-time password which is a result of applying the one-time password deriving rule to pattern elements included in the presentation pattern determined on a basis of the presentation pattern determination information, transmitted from the authentication request client; and user authentication means for comparing the received character string for authentication with the verification code generated for each of all the user IDs and making authentication of the user ID corresponding to the verification code successful in a case where the verification code which matches the received character string for authentication exists.