Give each side a public and private key, then one side sends some random message to the other (encrypted) and the other replies back (double-encrypted using the message it just got, plus the senders public key). IF you want to both ends to authenticate each other, the first one can send a third message back to the other which is also double-encrypted.
If both sides were able to read and reply OK, authentication worked. If "garbage" came through, the "other side" is fake, or some replay attack is taking place.
Find a "big int" library for Arduino, and use "RSA" - that should easily fit in the limited space you've got - just remember to use RANDOM NUMBERS* as much as possible for what you encrypt (rsa is not secure to encrypt non-random content)
- use timers and adc measurements to make something random.