A time required for actually starting encrypted communication after a trigger of an encrypted communication is shortened. When a key exchanging process is to be applied in order to exchange key information upon encrypting a communication performed between a communication terminal 11 and a gateway device 25, a network relay device 15 relays the key information, contents of the key exchanging process are divided into a former-half process and a later-half process, and the network relay device 15 executes the former-half process substitute for the communication terminal 11 to establish “IKE SA”. Then, information obtained as the result of the former-half process is transferred from the network relay device 15 to the communication terminal 11. Then, the later-half process of the key exchange process is executed between the communication terminal 11 and the gateway device 25, the communication terminal 11 and the gateway device 25 share common key information with each other to establish “IPsec SA”, and an encrypted communication is performed by using this key information.