Symmetric encryption algorithm for embedded system

Question

Looking for recommendations and some reference code for encrypting byte array in C. The problem is that I have to fit into 1KByte memory along with other routines and MCU is only 8MHz. So the size and speed is the key. I've checked Rijndael but it has huge tables for my MCU. Basically I am going to encrypt intel hex format on PC, probably only data area, then decrypt in MCU.

Using dynamic memory allocation routines is not desirable.

My google search brings me all to C# implementations, using libraries.

UPDATE:

decryption side constraints:

RAM: 512 byte
MAX code size: 512-1024 words
CPU: 8 bit, 8MHz

Answer 1

A very simple encryption algorithm that I saw being used in the embedded world is XXTEA

Answer 2

All the tables in Rijndael are defined as simplish operations in GF2. As such, I'd be tempted to say it's possible to write eg. 128-bit AES in 1k.

See also: https://electronics.stackexchange.com/questions/13275/smallest-aes-implementation-for-microcontrollers

But any chosen algorithm is a minor factor in security eg. if the key is distributed with the binary. In that case, the simplest mechanism to unveil the original binary is to run the code through emulator and store the memory.