Paper 2004/033

New Approaches to Password Authenticated Key Exchange based on RSA

Muxiang Zhang


We investigate efficient protocols for password-authenticated key exchange based on the RSA public-key cryptosystem. To date, most of the published protocols for password-authenticated key exchange were based on Diffie-Hellman key exchange. It appears inappropriate to design password-authenticated key exchange protocols using RSA and other public-key cryptographic techniques. In fact, many of the proposed protocols for password-authenticated key exchange based on RSA have been shown to be insecure; the only one that remains secure is the SNAPI protocol. Unfortunately, the SNAPI protocol has to use a prime public exponent $e$ larger than the RSA modulus $n$. In this paper, we present a new password-authenticated key exchange protocol, called {\em PEKEP}, which allows using both large and small prime numbers as RSA public exponents. Based on number-theoretic techniques, we show that the new protocol is secure against the $e$-{\em residue attack}, a special type of off-line dictionary attack against RSA-based password-authenticated key exchange protocols. We also provide a formal security analysis of PEKEP under the RSA assumption and the random oracle model. On the basis of PEKEP, we present a computationally-efficient key exchange protocol to mitigate the burden on communication entities.

Available format(s)
Publication info
Published elsewhere. An extended abstract will appear in ASAICRYPT 2004 proceedings.
Password authenticationOff-line dictionary attackPublic-key cryptography
Contact author(s)
muxiang zhang @ verizon com
2004-08-18: revised
2004-02-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muxiang Zhang},
      title = {New Approaches to Password Authenticated Key Exchange based on {RSA}},
      howpublished = {Cryptology ePrint Archive, Paper 2004/033},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.