Here's a way we did it using two keys, one 'private' and one 'public'.
1. Encrypt the data using the private key.
2. Embed the bytes for the private key inside the encrypted data.
3. Encrypt the modified data again using the public key.
4. Send the resulting data.
5. Decrypt the data using the public key.
6. Extract the private key out of the decrypted data.
7. Decrypt the modified data again using the private key.
If someone 'intercepts' the data during transmission, the chances of them
successfully decrypting it are practically nil.
Both the sending and receiving executables need to know the public key, but
this is not an issue because of the 'double' encryption.
The private key is hidden in the data and therefore does not need to be
stored anywhere else. In fact, it can be different for every transmission.
The only other things that both executables need to know is where the
private key is 'hidden' and how long it is.
If someone were to 'reverse engineer' either executable, it would still be
possible for them to work out how to decrypt the data, but they will not
find the public key stored in the executables as a constant because it is
not there.
To make it even harder you could use an obfuscator on the executables.
Remember, that if someone really really really wants to crack your
encryption they will. What you are doing is reducing the risk of someone
doing so to an acceptable level.