Maybe this is a good service for a key server to perform.
Yeah, but that kind of assumes connectivity to the net. It's rather inconvenient for a pair of phones who only have dialup modems connected to each other to do this on every call.
What if you prepare RSA key pairs in advance in your computer's (phone's) spare time, then use one per conversation (at least for the initializing)? You would encode your public key with the session
You could probably use temporary RSA key-pairs for each call, but RSA key generation is notoriously slow. A lot slower than a Diffie-Hellman key exchange.
Am I wrong, or is Diffie-Helman only useful when you *don't* have a way of verifying who each other are?
Eh? No, as I've been saying, you can produce a very strong hybrid in which both Diffie-Hellman and RSA each play an important part. Diffie-Hellman generates the session keys, while RSA signs them. Phil