1. Motivation
L'AES standard utilise une longueur de bloc de message de 128 bits (c’est-à-dire 16 octets) et une longueur de clé de 128 bits. Les longueurs de clé de 192 et 256 bits sont également prises en charge par l'AES. Pour la combinaison 128/128 (bloc/clé), le bloc de message AES et la clé peuvent être représentés sous forme d'une matrice 4*4. Chaque cellule de la matrice représente un octet unique et 16 (4*4) cellules correspondent donc à 16 octets, ce qui équivaut à 128 bits.

De même, pour l'AES étendu, nous utilisons une matrice 4*16 (4 : taille des lignes, 16 : taille des colonnes) pour représenter les blocs de message et les clés de tour. L'AES étendu utilise certaines propriétés et fonctions de l'AES original exactement de la même manière (par exemple l'ajout de la clé de tour, le mélange des colonnes, etc.), tandis que certaines propriétés et fonctions sont spécifiques à l'AES étendu (par exemple le nombre total de tours, le décalage des lignes, etc.).

Dans les sections suivantes, les propriétés et fonctions pertinentes utilisées dans l'AES original et l'AES étendu sont expliquées en détail.

2. Modes de fonctionnement
Tous les modes de fonctionnement pris en charge par l'AES original (c’est-à-dire Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB) et Counter (CTR)) ont également été implémentés pour l'AES étendu.

3. Nombre total de tours
Pour chiffrer et déchiffrer un seul bloc, l'algorithme AES original applique ses fonctions en tout en 10 tours. Ce nombre 10 est calculé avec la formule suivante :
Nombre de tours = (taille de la clé ou du bloc en mots) + 6

Le nombre constant 6 est spécifié et fixé par les concepteurs de l'AES en fonction des attaques cryptographiques connues. Si la taille de la clé est de 256 bits, alors 14 tours (8+6) sont nécessaires.

Pour l'AES étendu, la longueur du bloc est fixée à 512 bits. Cela fait 16 mots car chaque mot fait 4 octets. Le nombre total de tours est calculé comme 22 selon la formule ci-dessus. En fait, nous avons besoin de 2 tours supplémentaires en raison de l'opération ShiftRow expliquée dans les sections suivantes. En conclusion, l'AES étendu applique 24 tours pour chiffrer et déchiffrer un seul bloc.

4. Padding
L'opération de padding est très courante pour compléter les blocs de message et les blocs de clé pour les chiffrements par bloc. Pour l'AES étendu, nous avons besoin à la fois du padding du message et du padding de la clé.

4.1. Padding du message
La longueur des messages d'entrée doit être un multiple de 512 dans l'AES étendu. Pour l'opération de padding, nous suivons le mécanisme décrit dans la RFC 1321. Dans cette méthode de padding, après le dernier bit du message original, un bit "1" est inséré puis des bits "0" sont ajoutés jusqu'à ce que le dernier bloc de message atteigne la longueur de 512. S'il ne reste pas d'espace pour ajouter des "0" supplémentaires, un nouveau bloc de 512 bits est ajouté à la fin du message.

4.2. Padding de la clé
L'AES étendu supporte des tailles de clé de 16, 32 et 64 octets. Pour initialiser le bloc de clé, un mot de passe fourni par l'utilisateur est utilisé. Si le mot de passe ne contient pas assez de caractères pour remplir le bloc de clé, les octets restants sont remplis par des zéros. Ce simple padding suffirait pour l'AES original, mais pas pour l'AES étendu. En considérant une clé de 64 octets, supposons que le mot de passe ne compose que les 10 premiers octets du bloc de clé et que les 54 octets restants sont mis à zéro. Ce bloc de clé initial est ensuite utilisé pour générer les clés de tour. Dans ce cas, il y aurait beaucoup de clés de tour ayant la valeur zéro à cause du grand nombre d'octets nuls dans le bloc de clé. Pour éviter ce problème et ne pas générer de nombreuses clés de tour nulles, nous appliquons le chiffrement AES original sur le bloc de clé rempli de zéros avec une clé fixe en mode CBC. Le résultat de ce chiffrement devient la clé paddée pour générer les clés de tour, ce qui évite le problème des nombreux zéros.

5. Génération des clés de tour
Les clés de tour sont générées à partir du bloc de clé paddé expliqué dans la section précédente. Le processus original de génération des clés de tour (voir la spécification du chiffrement par bloc Rijndael, p. 15) est légèrement modifié pour l'AES étendu et l'algorithme suivant est utilisé pour générer les clés de tour :

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. Fonctions
L'AES original utilise essentiellement 4 fonctions principales. Ce sont l'opération xor-add entre le bloc de message et la clé de tour (AddRoundKey), la recherche dans la Sbox (SboxSubstitution), le décalage des lignes (ShiftRow) et le mélange de chaque colonne dans la matrice (MixColumn).

1.1.1. AddRoundKey
Pour le processus d'ajout de clé de tour, il n'y a pas de différence entre l'AES original et l'AES étendu.

1.1.2. SboxSubstitution
Le processus de recherche dans la Sbox est également identique dans l'AES original et l'AES étendu.

1.1.3. ShiftRow
Le processus de décalage des lignes est différent dans l'AES original et l'AES étendu. L'AES original applique des décalages {0,1,2,3} pour le ShiftRow. Cela signifie que dans l'opération ShiftRow, les octets de la première ligne ne sont pas décalés. Ceux de la deuxième ligne sont décalés d'un octet vers la gauche (pour le chiffrement) ; ceux de la troisième ligne sont décalés de 2 octets vers la gauche et enfin ceux de la dernière ligne sont décalés de 3 octets vers la gauche. L'opération ShiftRow est appliquée à chaque tour de l'AES et après deux tours, la combinaison des opérations ShiftRow et MixColumn assure une diffusion totale dans la matrice ; cela signifie qu'après deux tours, chaque cellule de la matrice influence la valeur de toutes les autres cellules de la matrice.

Mais si nous appliquons les décalages {0,1,2,3} pour le ShiftRow dans l'AES étendu, cette diffusion totale est atteinte après 5 tours, au lieu de 2. Par conséquent, nous devons trouver de meilleurs décalages qui assurent la diffusion totale en moins de tours. À cette fin, nous avons écrit un programme (voir com.crypt.test.OptimumShiftRow.java dans le code source distribué) qui calcule les décalages optimaux. Le résultat a été que la diffusion totale peut être atteinte seulement après 4 tours pour l'AES étendu. Plusieurs candidats permettaient d'atteindre cette diffusion en 4 tours, et nous avons choisi les décalages {0,1,4,5} pour l'AES étendu.

1.1.4. MixColumn
La même opération MixColumn est appliquée pour l'AES original et l'AES étendu. Dans l'AES original, il y a seulement 4 colonnes, tandis que l'AES étendu en contient 16.