Примените
цифровую подпись.
Создаете пару ключей. Открытый (публичный) ключ в приложении, закрытый (секретный) на сервере.
Любое сообщение шифруете открытым ключом, отправляете, если получилось открыть секретным - все хорошо.
Но стоит понимать, что злоумышленники могут "добыть" этот ключ из вашего приложения, и подделать сообщения.
Если этот риск неприемлем, можно генерировать сеансовые ключи непосредственно при создании соединения, как в
SSL, что сильно усложнит атаку. В браузерах такая штука давно работает.
Для всего этого существуют готовые реализации, только подключить, и вперед!