AES Ciphers

Helpful Notes:

• Finite Fields are a mathematical concept. They consist of a set, an addition (+) operator, and a multiplication (*) operator. However, + and * can be defined as anything, and may not be the same addition and multiplication that we are familiar with. In the case of AES, whenever you read the term "finite field," just think of a byte (8-bits, unsigned). The way that we do addition and multiplication on the field will be defined in the document.
• Review of Binary Operators: C, C++ and Java have operators (&, |, ^, <<, >>) to perform simple bitwise operations, such as a bit-wise AND, OR, XOR, left shifts and right shifts respectively. Notice that we use a single & and | instead of the double && and || that we use when doing boolean operations. For a more detailed review, click here.
• Variable Glossary: There are several variables that are used throughout the document to represent different things. Before you begin, it may be helpful to read through section 2.2 in the FIPS document. In particular, you will need to know the following variables:
  • Nb - The number of words in the block (Nb is always 4)
  • Nk - The number of words in the key (key bit-length / 32)
  • Nr - The number of rounds in the cipher algorithm
  To see the correct values for these variables using 128, 192 and 256 bit encryption, read the beginning of section 5.
  
• The State: AES is a type of block cryptography. This means that the encryption and decryption happens on an entire block at a time, rather than on a single character. In the FIPS document, the block that we are working on is called the state. When you see the word state, think of the block of bytes that you are encrypting.
• Block Orientation: The state consists of 16 bytes, and is often shown in the document as a 4x4 grid. Be aware that the bytes are ordered going down first, then moving right. For example, the byte[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} would be shown in the document as:

  1	5	9	13
  2	6	10	14
  3	7	11	15
  4	8	12	16

Requirements:

1. The AES algorithm makes use of finite field arithmetic. As such, it is important to read and understand Section 4. In particular you should implement:
   1. ffAdd() - adds two finite fields (see Section 4.1)
   2. xtime() - multiplies a finite field by x (see Section 4.2.1)
   3. ffMultiply() - uses xtime to multiply any finite field by any other finite field. (see Section 4.2.1)


2. Implement Key Expansion. Notice that the key for use with this algorithm is given as a byte[], but both cipher and invCipher require a word[] as input. The key expansion algorithm (see Section 5.2) performs this conversion. Appendix A gives excellent examples of the Key expansion algorithm. The following two functions are needed by this algorithm:
   1. subWord() - takes a four-byte input word and substitutes each byte in that word with its appropriate value from the S-Box. The S-box is provided (see Section 5.1.1)
   2. rotWord() - performs a cyclic permutation on its input word.

   Key expansion also uses the round constant word array. This array can be generated using xtime(), but is provided here for your convenience.
   Rcon[] = { 0x00000000, // Rcon[] is 1-based, so the first entry is just a place holder
   0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000, 0x1B000000, 0x36000000, 0x6C000000, 0xD8000000, 0xAB000000, 0x4D000000, 0x9A000000, 0x2F000000, 0x5E000000, 0xBC000000, 0x63000000, 0xC6000000, 0x97000000, 0x35000000, 0x6A000000, 0xD4000000, 0xB3000000, 0x7D000000, 0xFA000000, 0xEF000000, 0xC5000000, 0x91000000, 0x39000000, 0x72000000, 0xE4000000, 0xD3000000, 0xBD000000, 0x61000000, 0xC2000000, 0x9F000000, 0x25000000, 0x4A000000, 0x94000000, 0x33000000, 0x66000000, 0xCC000000, 0x83000000, 0x1D000000, 0x3A000000, 0x74000000, 0xE8000000, 0xCB000000, 0x8D000000}

3. Implement the cipher function. The cipher function is specified in Section 5.1, and an example is given in appendix B. Its implementation is quite simple once the following four transformations are created:
   1. subBytes() - This transformation substitutes each byte in the State with its corresponding value from the S-Box.
   2. shiftRows() - This transformation performs a circular shift on each row in the State (see Section 5.1.2)
   3. mixColumns() - This transformation treats each column in state as a four-term polynomial. This polynomial is multiplied (modulo another polynomial) by a fixed polynomial with coefficients (see Sections 4.3 and 5.1.3).
   4. addRoundKey() - This transformation adds a round key to the State using XOR.


4. Implement the invCipher function. This function is specified in Section 5.3. It reverses the effect of the cipher function. Its implementation is quite simple once the following three transformations are created:
   1. invSubBytes() - This transformation substitutes each byte in the State with its corresponding value from the inverse S-Box, thus reversing the effect of a subBytes() operation. The inverse SBox is not provided. You will have to generate this on your own (see Section 5.3.2)
   2. invShiftRows() - This transformation performs the inverse of shiftRows() on each row in the State (see Section 5.3.1)
   3. invMixColumns() - This transformation is the inverse of mixColumns (see Section 5.3.3).


5. The cipher and invCipher functions defined in the specification deal with a single block at a time. Write fileCipher() and invFileCipher() to encrypt and decrypt entire files. To encrypt and decrypt files, apply cipher() and invCipher() with the same key to each block size section of data in the file. The files that we will provide for this lab will be evenly divisible by the size of the block.

Passoff Requirements:
Your program must correctly encrypt/decrypt arbitrary files byte-for-byte. The TAs will use your program to encrypt a file, verify that it has been correctly encrypted, then decrypt the file and verify that it is the same as the original file.

Example:
Here are some example files to work with:

Key = hithisismysecret
plain.bin (MD5: 1dbecda2466c83240a29298c7cc30ed8)
cipher.bin (MD5: 895b0d2189fc4575eced452c59d17133)

Note: To check the md5 sum of the file you downloaded, at the Linux command follow this example:
[cs465ta@ta-14 labs]$ openssl dgst plain.bin
MD5(plain.bin)= 1dbecda2466c83240a29298c7cc30ed8
[cs465ta@ta-14 labs]$