Вы хотите использовать HMAC.
Как правило, вы отправляете 2 соли клиенту. Вы храните в своей базе данных
md5(salt + pwd)
вы отправляете уникальную salt2 и db salt конечному пользователю, который возвращает
md5(salt2 + md5(salt + pwd))
и затем вы сравниваете с той же операцией на стороне сервера.
Пока вы меняете отправленную соль и не принимаете старую, она примерно так же безопасна, как и без SSL. Вы определенно не хотите пытаться использовать AES или RSA что-нибудь подобное.
Если вам не нравится md5, используйте любой другой алгоритм хеширования по вашему выбору.