The invention provides for installing encryption keys on a device not having any previous security credentials. An installation authority generates a security token to be used by the device for secure communications, and an installation credential for the device, and stores them in association with one another. A user of the device is provided with the installation credential, whereby the user inputs the installation credential into the device. The device utilizes the installation credential as a temporary security key, establishes a secure communication channel with the installation authority and requests provision of the security token. The installation authority provides the security token associated with the installation credential to the device over the established secure communication channel, and the device installs the security token, after which the device erases the installation credential from the device. The installation authority may also certify the security token and provide a certified token and a root verification certificate to the device.