To facilitate mutual authentication on a network in a public key cryptosystem and mutual exchange of public keys.

Public keys are exchanged between two phases (exchange of a tentative public key and exchange of a regular public key). One to one cipher communication is established in the exchange phase of the tentative public key to prevent wiretapping. In the exchange phase of the regular public key, mutual authentication in the same timing is implemented on the basis of information which is known only by both keys, and then the regular public key is exchanged also to prevent spoofing. By the two phases (public key exchange of the total 4 times) wiretapping and spoofing are prevented, and the public keys mutually authenticated are exchanged.