Methods are described for two parties to use a small shared secret (S) to mutually authenticate one another other over an insecure network. The methods are secure against off-line dictionary attack and incorporate an otherwise unauthenticated public key distribution system. One embodiment uses two computers Alice and Bob, and a Diffie-Hellman exponential key exchange in a large prime-order finite group. Both parties choose the same generator of the group (g) as a function of S. Alice chooses a random number R_A, and sends g^RA to Bob. Bob chooses a random R_B, sends g^RB to Alice. Both compute a shared key K=g^(RARB). Each party insures that K is a generator of the group, verifies that the other knows K, and then uses K as an authenticated key. Constraints are described to prevent passive and active attacks. An extension is described where Alice proves knowledge of S to Bob who knows only a one-way transformation of S. These methods establish a secure, authenticated network session using only an easily memorized password.