In the method and system of establishing a trusted relationship, first a virtual private network is established between a key device and at least one locking device. Thereafter, in order to establish a trusted relationship the key device sends a message encrypted with its private cryptographic key to at least one locking device. The message comprises the certificate of the trusted key device and the certificate of some other device, with which the locking device that received the message shall establish a new trusted relationship. By using the established trusted relationship either a trusted relationship between the locking device and a new key device or a trusted relationship between two or more locking devices is established, whereby a virtual private network can be established between the locking devices.