When manufacturing, distributing, or selling mobile phones, each phone is associated with an asymmetric cryptographic key pair, comprising a public key and a private key. The private key is stored on the phone, and the public key is stored in a public key repository. When connecting to a cellular network, a phone provides its device ID to the network. The cellular network queries the public key repository to determine the public key of the phone and authenticates the phone using the phone's public key. The cellular network also provides a digital identity certificate to the phone, allowing the phone to authenticate the cellular network using a public key infrastructure (PKI).