I second [Richie Frame's observation][1] that AES is an excellent choice. I'd use AES-128 in [CTR][2] mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes).
Update: SPECK, considered in the [other answer][3], is worth consideration if compactness or speed per encryption for narrow block size are the choice criteria. But I believe it is not competitive with AES in term for cycles/byte on a Z80 (as asked in the question); in particular, SPECK's rotation by 3 bits and large number of rounds are going to be show stoppers.
AES is near ideal for lowly 8-bit CPU because
- It has a natural implementation with as the only data transformations: XOR between octets, and lookup of two 256-octet tables. Contrary to many modern ciphers, no word rotation is needed, which is extremely desirable in the context, in which that would be slow even when using assembly.
- With an implementation (still natural) separating derivation of round subkeys from encryption itself, speed for large data will be hard to beat, thanks to the carefully crafted structure of AES.
- Typical C compilers can generate fair code, and optimization is relatively easy.
- With the precaution of locating the two 256-octet tables on page boundaries, a natural implementation on a CPU without data cache (such as the Z80) will typically exhibits no data timing dependency (but I have seen small caches, e.g. 16-octet, in the read path of Flash memory).
As illustration, here is reference code:
// ezAES: Public domain AES-128 encryption.
// C99-conformant. Well suited to 8-bit CPUs.
// CAUTION: vulnerable to fault attacks and side-channels, including
// Differential Power Analysis, and possibly data cache timing attack.
// Data types
typedef unsigned char octet_t; // 8-bit octet
typedef octet_t ezAESblk_t[16]; // AES data block
typedef octet_t ezAESkey_t[16]; // key for AES-128
typedef octet_t ezAESsks_t[11*16]; // subkeys for AES-128
// Sbox for encryption, FIPS-197 figure 7
static const octet_t ezAESs[256] = {
0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
};
// Tabulation of (x<<1)^((x>>7)*0x1B)
static const octet_t ezAESt[256] = {
0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5
};
// Round constants
static const octet_t ezAESr[10] = {
0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36
};
// encrypt one block
void ezAESenc
(
ezAESblk_t oC, // ciphertext output
const ezAESblk_t iP, // plaintext input
const ezAESsks_t iS // round subkeys
) {
ezAESblk_t vB; // current state of the block
ezAESblk_t vT; // temporary
octet_t vn;
// first AddRoundKey
vn = 16;
do {
--vn;
vB[vn] = iP[vn] ^ iS[vn];
} while( vn!=0 );
// round loop, started 10 times; exits with break in the middle of the last round
for( ; ; ) {
// ShiftRows and SubBytes, performed 10 times
vT[ 0] = ezAESs[vB[ 0]]; vT[ 1] = ezAESs[vB[ 5]]; vT[ 2] = ezAESs[vB[10]]; vT[ 3] = ezAESs[vB[15]];
vT[ 4] = ezAESs[vB[ 4]]; vT[ 5] = ezAESs[vB[ 9]]; vT[ 6] = ezAESs[vB[14]]; vT[ 7] = ezAESs[vB[ 3]];
vT[ 8] = ezAESs[vB[ 8]]; vT[ 9] = ezAESs[vB[13]]; vT[10] = ezAESs[vB[ 2]]; vT[11] = ezAESs[vB[ 7]];
vT[12] = ezAESs[vB[12]]; vT[13] = ezAESs[vB[ 1]]; vT[14] = ezAESs[vB[ 6]]; vT[15] = ezAESs[vB[11]];
if ( (vn += 16)==10*16 )
break;
// MixColumns and AddRoundKey, performed 9 times
#define EZAESMA(x) \
vB[x+2] = vT[x+0]^vT[x+1]; /* 1 1 0 0 */ \
vB[x+3] = vT[x+2]^vT[x+3]; /* 0 0 1 1 */ \
vB[x+0] = ezAESt[vB[x+2]]^vT[x+1]^vB[x+3] /* 2 3 1 1 */ ^iS[x+0+vn]; \
vB[x+2] ^= ezAESt[vB[x+3]]^vT[x+3] /* 1 1 2 3 */ ^iS[x+2+vn]; \
vB[x+3] = vT[x+1]^vT[x+2]; /* 0 1 1 0 */ \
vT[x+3] ^= vT[x+0]; /* 1 0 0 1 */ \
vB[x+1] = ezAESt[vB[x+3]]^vT[x+2]^vT[x+3] /* 1 2 3 1 */ ^iS[x+1+vn]; \
vB[x+3] ^= ezAESt[vT[x+3]]^vT[x+0] /* 3 1 1 2 */ ^iS[x+3+vn];
EZAESMA( 0)
EZAESMA( 4)
EZAESMA( 8)
EZAESMA(12)
#undef EZAESMA
// here the content of vT is immaterial
}
// last AddRoundKey
vn = 16;
do {
--vn;
oC[vn] = vT[vn] ^ iS[10*16+vn];
} while( vn!=0 );
}
// prepare round subkeys
void ezAESkey (
ezAESsks_t oS, // round subkeys output
const ezAESkey_t iK // key input
) {
octet_t vj, vk;
// first subkey is the key
vj = 16;
do {
--vj;
oS[vj] = iK[vj];
}
while ( vj!=0 );
// for each 4-octet word of each 10 other subkeys
vk = 0;
do {
if( (vj&15)==0 ) {
oS[16+vj] = ezAESs[oS[13+vj]]^oS[ vj]^ezAESr[vk++];
oS[17+vj] = ezAESs[oS[14+vj]]^oS[1+vj];
oS[18+vj] = ezAESs[oS[15+vj]]^oS[2+vj];
oS[19+vj] = ezAESs[oS[12+vj]]^oS[3+vj];
}
else {
oS[16+vj] = oS[12+vj]^oS[ vj];
oS[17+vj] = oS[13+vj]^oS[1+vj];
oS[18+vj] = oS[14+vj]^oS[2+vj];
oS[19+vj] = oS[15+vj]^oS[3+vj];
}
} while( ( vj += 4)!=10*16 );
}
// Minimal test and demo. Returns 0 for OK, 1 for error.
int ezAESchk(void) {
// test values from FIPS-197 appendix C.1
const ezAESkey_t key = {
0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
};
const ezAESblk_t plaintext = {
0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
};
const ezAESblk_t ciphertext = {
0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
};
ezAESsks_t subkeys;
ezAESblk_t result;
octet_t j, r;
// derive the round subkeys
ezAESkey( subkeys, key );
// encrypt
ezAESenc( result, plaintext, subkeys );
// compare result and known-good ciphertext
for( j = r = 0; j<16; ++j)
r |= result[j] ^ ciphertext[j];
return r!=0; // 0 for OK, 1 for error
};
[1]: https://crypto.stackexchange.com/q/55885/555#comment123701_55885
[2]: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Counter_(CTR)
[3]: https://crypto.stackexchange.com/a/55906/555