UPD: нижнюю часть не читал, не заметил про то, чтобы ключей не было.
Гугли шифр вернама - поточный шифр одноразовый.
~~~~~~~
Используй RSA.
Шифруй массив с запросом перед отправкой открытым ключем сервера, кодируй в base64 и посылай закодированную аброкадабру, на сервере полученный base64 декодируй и расшифровывай своим закрытым ключем.
Гугли что такое ассиметричное шифрование и как юзать RSA ( сырую имплементацию, или крипто-фреймворки ) в C#, и как его юзать в том языке на котором сервер.