Cryptology ePrint Archive: Report 2004/033

New Approaches to Password Authenticated Key Exchange based on RSA

Muxiang Zhang

Abstract: 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.

Category / Keywords: Password authentication, Off-line dictionary attack, Public-key cryptography

Publication Info: An extended abstract will appear in ASAICRYPT 2004 proceedings.

Date: received 5 Feb 2004, last revised 18 Aug 2004

Contact author: muxiang zhang at verizon com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040818:172304 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]