The secure cellphone has a tiny bit of circuitry implementing the RSA Public Key encryption system. When the user wants to make a call, the cellphone sends a public key to the cell station. In response, the station generates a large unique random number (a "challenge"), and sends it to the user's phone. The phone encrypts it using the private key, and returns the encrypted challenge to the station. The station attempts to decrypt the response using the public key sent by the phone. If decryption is successful, the station knows that the user must actually posess the private key corresponding to the public key it sent at the beginning, and is therefore authenticated. The cell station checks the public key against its list of registered users, and grants or denies access.
This requires extra circuitry in both the phones and the cell stations, but old phones and old cell stations will still work using the older insecure protocol: users and providers are motivated but not required to switch to the new system.