Есть несколько способов достичь своей цели.
Один из способов сделать это - использовать некоторую форму протокола обмена ключами / соглашениями, например, обмен ключами в стиле Диффи-Хеллмана (см. http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange).. Поскольку вы находитесь в среде J2ME, вы, вероятно, захотите использовать недавнюю реализацию с использованием эллиптических кривых, поскольку они более щадящие к вашим аппаратным требованиям.
Другим способом достижения вашей цели было бы внедрение защищенного протокола передачи ключей с использованием сертификатов открытых ключей, но я бы не рекомендовал изобретать собственный протокол безопасности, вместо этого используйте SSL / TLS, который был специально разработан для этих случаев.
В зависимости от ваших требований вам потребуется использовать SSL в аутентификации на сервере («односторонний SSL») или во взаимно аутентифицированной форме («двусторонний SSL»). Обратитесь к документации вашего веб-сервера относительно правильной настройки SSL.
После настройки сервера достаточно создать симметричный ключ шифрования на клиенте, как это делается в данный момент, а затем отправить ключ шифрования на сервер с помощью вновь настроенного соединения TLS.
Преимущество решения Диффи-Хеллмана состоит в том, что оно не обязательно включает сертификаты, но для его безопасного использования вам потребуется реализовать некоторую форму функции получения ключа (см. http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf), которая опять-таки не Поэтому я бы порекомендовал использовать второй подход, даже если это потребует дополнительных затрат на настройку.