1. Мотивация
Стандартный AES использует длину блока сообщения 128 бит (то есть 16 байт) и ключ длиной 128 бит. Также поддерживаются ключи длиной 192 и 256 бит. При комбинации 128/128 (Блок/Ключ) блок сообщения и ключ AES могут быть представлены в виде матрицы 4×4. Каждая ячейка матрицы представляет один байт, и всего 16 (4×4) ячеек составляют 16 байт, что эквивалентно 128 битам.

Аналогично, в расширенном AES используется матрица 4×16 (4 — количество строк, 16 — количество столбцов) для представления блоков сообщений и раундовых ключей. Расширенный AES использует некоторые свойства и функции оригинального AES (например, добавление раундового ключа, смешивание столбцов и т. д.), в то время как другие свойства и функции характерны только для расширенного AES (например, общее число раундов, сдвиг строк и т. д.).

В следующих разделах подробно объясняются соответствующие свойства и функции, используемые в оригинальном и расширенном AES.

2. Режимы работы
Все режимы работы, поддерживаемые оригинальным AES (т. е. Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB) и Counter (CTR)), также реализованы для расширенного AES.

3. Общее количество раундов
Для шифрования и дешифрования одного блока оригинальный алгоритм AES применяет свои функции в течение 10 раундов. Это число рассчитывается по следующей формуле:
Количество раундов = (размер ключа или блока в словах) + 6

Постоянное число 6 задано и зафиксировано разработчиками AES в соответствии с известными криптоанализами. Если размер ключа составляет 256 бит, то необходимо 14 раундов (8+6).

В расширенном AES длина блока зафиксирована на уровне 512 бит, что составляет 16 слов, поскольку каждое слово — это 4 байта. Общее количество раундов рассчитывается как 22 по приведённой выше формуле. На практике требуются ещё 2 дополнительных раунда из-за операции ShiftRow, как объяснено в следующих разделах. В результате расширенный AES применяет 24 раунда для шифрования и дешифрования одного блока.

4. Дополнение (Padding)
Операция дополнения широко используется для выравнивания блоков сообщений и ключей в блочных шифрах. В расширенном AES необходимо дополнять как сообщение, так и ключ.

4.1. Дополнение сообщения
Длина входного сообщения в расширенном AES должна быть кратной 512. Для дополнения используется механизм, описанный в RFC 1321. В этой методике после последнего бита исходного сообщения добавляется бит “1”, а затем добавляются биты “0” до тех пор, пока последний блок сообщения не достигнет длины 512 бит. Если для дополнительных нулей не хватает места, то к сообщению добавляется новый 512-битный блок.

4.2. Дополнение ключа
Расширенный AES поддерживает ключи длиной 16, 32 и 64 байта. Для инициализации блока ключа используется пароль, заданный пользователем. Если пароль содержит недостаточно символов для заполнения блока ключа, оставшиеся байты заполняются нулями. Хотя такое простое дополнение может быть достаточным для оригинального AES, для расширенного AES этого недостаточно. Например, при размере ключа 64 байта, если пароль содержит только первые 10 байт, а остальные 54 заполнены нулями, то при генерации раундовых ключей многие из них будут равны нулю, что неприемлемо. Чтобы предотвратить эту проблему, мы применяем оригинальное шифрование AES к дополненному нулями блоку ключа с использованием фиксированного ключа в режиме CBC. Результат шифрования используется как дополненный ключ для генерации раундовых ключей, что предотвращает проблему «много нулей».

5. Генерация раундовых ключей
Раундовые ключи генерируются из дополненного блока ключа, как описано в предыдущем разделе “Дополнение ключа”. Процесс генерации ключей, описанный в спецификации Rijndael (стр. 15), немного изменён для расширенного AES, и используется следующий алгоритм:

KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)])
{
  for(i = 0; i < Nk; i++)
    W[i] = (key[4*i],key[4*i+1],key[4*i+2],key[4*i+3]);

  for(i = Nk; i < Nb * (Nr + 1); i++)
  {
    temp = W[i - 1];
    if (i % Nk == 0 || (I % Nk==4 && Nk>6))
      temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
    else if ((i % Nk == 8 || i % Nk == 12) && Nk>6)
      temp = SubByte(temp);
    W[i] = W[i - Nk] ^ temp;
  }
}

6. Функции
Оригинальный AES использует 4 основные функции. Это операция xor между блоком сообщения и раундовым ключом (AddRoundKey), замена байтов по Sbox (SboxSubstitution), сдвиг строк (ShiftRow) и смешивание каждого столбца матрицы (MixColumn).

1.1.1. AddRoundKey
В процессе добавления раундового ключа нет различий между оригинальным и расширенным AES.

1.1.2. SboxSubstitution
Процесс подстановки через Sbox также идентичен в оригинальном и расширенном AES.

1.1.3. ShiftRow
Процесс сдвига строк различается в оригинальном и расширенном AES. В оригинальном AES используются смещения {0,1,2,3}. Это означает, что байты первой строки не сдвигаются, байты второй строки сдвигаются влево на 1 байт, третьей строки — на 2 байта, а четвёртой — на 3 байта. Операция ShiftRow применяется в каждом раунде AES, и после двух раундов в сочетании с MixColumn обеспечивается полное рассеяние по матрице, то есть каждая ячейка влияет на все остальные.

Но если использовать смещения {0,1,2,3} в расширенном AES, полное рассеяние достигается только после 5 раундов вместо 2. Поэтому необходимо найти более эффективные смещения, обеспечивающие полное рассеяние за меньшее количество раундов. Для этого была написана программа (см. com.crypt.test.OptimumShiftRow.java в исходном коде), которая вычислила оптимальные смещения. В результате оказалось, что полное рассеяние достигается за 4 раунда. Было много кандидатов, обеспечивающих это, и мы выбрали смещения {0,1,4,5} для расширенного AES.

1.1.4. MixColumn Операция MixColumn одинакова в оригинальном и расширенном AES. В оригинальном AES — 4 столбца, а в расширенном — 16 столбцов.