Non-Repudiation in data sending and receiving is essential in the secure communication. In recent years, this kind of cryptographic protocols has been mainly implemented by the intervention of the trusted third party in transmission and encryption of data, thus the dependability and security of the trusted third party become a bottleneck in these secure systems. In this paper, a fair non-repudiation cryptographic protocol (NCP) for both sender and receiver is proposed. It is a more efficient and secure protocol, which solves the bottleneck problem of trusted third party. And its formal analysis is presented using the belief logic. Finally its applications to E-mail communication are discussed.