The easiest way is probably a hybrid of telephone/modem, doing normal calls in "analog" voice mode and secure calls in digital modem-to-modem connection. The digital layer may be done best over IP protocol, assigning IP addresses to the phones and making them talk over TCP and UDP over the direct dialup. (We cannot reliably use GPRS, as the quality of service is not assured, so we have to use direct dialup. But we can implement "real" IP later, when the available technology reaches that stage.)IIRC, PGPfone (http://www.pgpi.org/products/pgpfone/) did something similar, with a "verbal handshake" protocol that relied on you being able to recognise the remote party's voice over the phone while speaking a list of words.... always seemed both unreliable and odd in something with "PGP" in the name, but....
Once we have the phones talking over IP with each other, we can proceed with the handshake. I'd suggest using OpenSSL for this purpose, as it offers all we need for certificates and secure transfer of the key. Then use UDP for the voice itself, using eg. stripped-down SpeakFreely as the engine. So during the call, two connections will be open over the IP channel: the command one (SSL-wrapped TCP, for key and protocol handshake, ensuring the identity of the caller, etc.), and the data one (a bidirectional UDP stream). As the command connection should be silent for most of the time, a 14k4 modem should offer us enough bandwidth for 9k6 GSM codec, even with the UDP/IP overhead.Raw data streams would be fine over a point to point modem link - but I can see an advantage to compartmentalization - you can break your secure phone problem down into two distinct subproblems
a) establishing a secure IP VPN between two nodes
b) optimizing VoIP for low bandwidth links
I would add a third - a modem protocol based on something like CSMA/CD to allow conference calls to be used as carrier media for secure conversations, but that is too hairy for me :)
Something like OpenVPN (http://openvpn.sourceforge.net/) seems ideal for the secure VPN part of the problem, but requires an underlying IP network.... the VoIP part of the problem has a embarrassment of riches; H323 used to come as standard with windows, in the form of Netmeeting (complete with videoconferencing and whiteboarding) and SIP is now part of Windows XP (a not-particuarly-well-documented) "feature" of windows messager. There are many, many more, and Asterix (sadly not particularly well known, and unix only) is a complete, open source PBX which is conventional telephony, SIP and H323 aware.
OpenVPN is of course built on SSL, and can use either X509 certificates or a preshared key for authentication. Sadly, there is no convenient way to use DNS-SEC key records for OpenVPN.
