I think I have a solution to your problem,there is a plugin for Gaim called Gaim-Encryption,it features:

Automatically creates a public/private key pair for you upon loading the plugin.

Automatically transmits your public key to other users.

Supports 512 - 4096 bit keys.

Saves keys of known users, and warns you if their public key has changed.Embeds all encryption and keys inside HTML, so if the other user doesn't have the plugin, they will get a little message telling them about the plugin, and won't get a screen full of garbage.

Stores keys in human readable files in your .gaim directory, in case you ever need to copy/edit them by hand.

Modular and extensible. If you want to define a different type of encryption, you can use this plugin as a wrapper to take care of transporting the encrypted binary over the IM pipe.

It supports installation through:Linux on iPAQ,
Ubuntu,Debian,Gentoo,Mandriva,Fedora,CVS and Source.

Hope this works for you,
Justin.