N The product of two safe primes p and q (p = 2j+1, q = 2k+1, j, k, p, q all prime) All arithmetic is done modulo N. g A generator of the group G((p-1)(q-1)/2) mod N s User's salt u Username P Cleartext Password H() One-way hash function ^ (Modular) Exponentiation Ws,Ys Secret values Wp,Yp Public values Xs Salted and hashed password Xp Password verifierThe host stores passwords using the following formula:

Xs = s * H(P) (s is chosen randomly) Xp = g ^ Xs (computes password verifier)The host then keeps {u, s, Xp} in its password database. The authentication protocol itself goes as follows:

User -> Host: u, Wp = g ^ Ws (identifies self, Ws = random number) Host: Yp = g ^ Ys (Ys = random number) Host -> User: s, Z = Xp + Yp (sends salt, adds verifier to residue) User: Xs = s * H(P) (user enters password) User: Yp = Z - (g ^ Xs) (recovers Yp from message) User: S = Yp ^ (2*Ws + Xs) (computes session key) User: K = H(S) Host: S = (Wp^2 * Xp) ^ Ys (computes session key) Host: K = H(S)Now the two parties have a shared, strong session key K. To complete authentication, they need to prove to each other that their keys match. One possible way:

User -> Host: H(Z, K) (hash with host's value) Host -> User: H(Wp, K) (hash with user's value)The two parties also employ the following safeguards:

- The user will abort if he receives Z == 0 (mod N).
- The host will abort if it detects that Wp == 0 (mod N).
- The user must show his proof of K first. If the server detects that the user's proof is incorrect, it must abort without showing its own proof of K.

Back