Abstract: A mutual authentication scheme and key exchange based on public key encryption is presented for mobile communication system. This scheme can realize mutual authentication and generate a session key confirmed by both sides of communication. The generation of session key has no third party involved. Besides, non-repudiation of data sent by both sides is provided with digital signature. By performance analysis, this scheme has a simple structure and high efficiency.