Public key cryptography seems like the wrong choice for phones, because it's relatively computationally intensive, and you'd want a phone to use the cheapest hardware imaginable. However, there is an alternative that would work.
You can use a symmetric cipher (AES is the current standard), and exchange keys via Diffie-Hellman key exchange, which is a method of securely generating a shared private cipher key over a public channel.
As I understand it, the primary advantage of public key cryptography is that it makes encryption and decryption asymmetric processes - i.e. everyone can encrypt something using your public key, but only you can decrypt it, because only you know your private key. In the phone case, the asymmetry would actually be annoying, because both parties want to send encrypted messages to each other, so you'd have to deal with two key pairs for each phone conversation.
That's how most encryption protocols work now, by exchanging symmetric encryption keys at the start. There are protocols to do this, PGPfone was written in the 90s.
You can use a symmetric cipher (AES is the current standard), and exchange keys via Diffie-Hellman key exchange, which is a method of securely generating a shared private cipher key over a public channel.
As I understand it, the primary advantage of public key cryptography is that it makes encryption and decryption asymmetric processes - i.e. everyone can encrypt something using your public key, but only you can decrypt it, because only you know your private key. In the phone case, the asymmetry would actually be annoying, because both parties want to send encrypted messages to each other, so you'd have to deal with two key pairs for each phone conversation.
See http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exch... and http://en.wikipedia.org/wiki/Advanced_Encryption_Standard .