1. Motivation
Der Standard-AES verwendet eine Blocklänge von 128 Bit (d.h. 16 Byte) und eine Schlüssellänge von 128 Bit. Es werden auch Schlüssellängen von 192 und 256 Bit vom AES unterstützt. Für die Kombination von 128/128 (Block/Schlüssel) kann der AES-Nachrichtsblock und der Schlüssel als eine 4*4 Matrix realisiert werden. Jede Zelle der Matrix stellt ein einzelnes Byte dar, und 16 (4*4) Zellen entsprechen 16 Byte, was 128 Bit entspricht.

Für den erweiterten AES verwenden wir eine 4*16 Matrix (4: Zeilengröße, 16: Spaltengröße) zur Darstellung der Nachrichtenblöcke und Rundenschlüssel. Der erweiterte AES verwendet einige Eigenschaften und Funktionen des ursprünglichen AES exakt (z.B. das Hinzufügen des Rundenschlüssels, Spaltenmischung usw.), während einige Eigenschaften und Funktionen spezifisch für den erweiterten AES sind (z.B. die Gesamtzahl der Runden, Zeilenverschiebung usw.).

In den folgenden Abschnitten werden die relevanten Eigenschaften und Funktionen des ursprünglichen AES und des erweiterten AES detailliert erklärt.

2. Betriebsarten
Alle von AES unterstützten Betriebsarten (d.h. Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB) und Counter (CTR)) wurden auch für den erweiterten AES implementiert.

3. Gesamtzahl der Runden
Zum Verschlüsseln und Entschlüsseln eines einzelnen Blocks wendet der ursprüngliche AES-Algorithmus seine Funktionen insgesamt in 10 Runden an. Diese Zahl 10 wird mit der folgenden Formel berechnet:
Rundenzahl = (Schlüsselgröße oder Blockgröße in Wörtern) + 6

Die Konstante 6 wird von den AES-Designern gemäß den bekannten Kryptographie-Angriffen festgelegt. Wenn die Schlüsselgröße 256 Bit beträgt, sind 14 Runden (8+6) erforderlich.

Für den erweiterten AES ist die Blocklänge auf 512 Bit festgelegt. Das ergibt 16 Wörter, da jedes Wort 4 Byte ist. Die Gesamtzahl der Runden wird gemäß der obigen Formel auf 22 berechnet. Tatsächlich benötigen wir aufgrund der ShiftRow-Operation, wie in den nächsten Abschnitten erklärt, 2 weitere Runden. Daher wendet der erweiterte AES insgesamt 24 Runden zum Verschlüsseln und Entschlüsseln eines einzelnen Blocks an.

4. Padding
Die Padding-Operation ist sehr verbreitet, um Nachrichtenblöcke und Schlüsselblöcke für Blockchiffren aufzufüllen. Für den erweiterten AES benötigen wir sowohl Nachrichten- als auch Schlüssel-Padding.

4.1. Nachrichten-Padding
Die Länge der Eingabemeldungen sollte im erweiterten AES ein Vielfaches von 512 sein. Für die Padding-Operation folgt die Methode dem Padding-Mechanismus, der in RFC 1321 beschrieben ist. Bei dieser Padding-Methode wird nach dem ursprünglichen letzten Nachrichtenbit ein Bit „1“ eingefügt, und dann werden „0“-Bits angehängt, bis der letzte Nachrichtenblock eine Länge von 512 hat. Wenn kein Platz mehr für zusätzliches Padding „0“-Bits bleibt, wird ein neuer 512-Bit-Block am Ende der Nachricht hinzugefügt.

4.2. Schlüssel-Padding
Der erweiterte AES unterstützt Schlüssellängen von 16, 32 und 64 Byte. Zur Initialisierung des Schlüsselblocks wird ein vom Benutzer angegebenes Passwort verwendet. Wenn das Passwort nicht genug Zeichen enthält, um den Schlüsselblock zu füllen, werden die verbleibenden Bytes im Schlüsselblock mit Nullen aufgefüllt. Tatsächlich wäre dieses einfache Padding für den ursprünglichen AES ausreichend, jedoch nicht für den erweiterten AES. Bei einer Schlüssellänge von 64 Byte, nehmen wir an, dass das Passwort nur aus den ersten 10 Byte des Schlüsselblocks besteht und die verbleibenden 54 Byte mit Null belegt sind. Andererseits wird dieser anfängliche Schlüsselblock zur Erzeugung der Rundenschlüssel verwendet. In diesem Fall würden viele Rundenschlüssel mit dem Wert Null existieren, da der Schlüsselblock viele Null-Bytes enthält. Um dieses Problem zu vermeiden und nicht viele Rundenschlüssel mit dem Wert Null zu erzeugen, wenden wir die ursprüngliche AES-Verschlüsselung auf den mit Nullen aufgefüllten Schlüsselblock mit einem festen Schlüssel im CBC-Modus an. Das Verschlüsselungsergebnis wird zum aufgefüllten Schlüssel, um die Rundenschlüssel zu generieren, und wir verhindern das Problem der vielen Null-Werte.

5. Rundenschlüssel-Generierung
Die Rundenschlüssel werden aus dem aufgefüllten Schlüsselblock generiert, der im vorherigen Abschnitt „Schlüssel-Padding“ erklärt wurde. Der ursprüngliche Rundenschlüssel-Generierungsprozess (siehe Rijndael Block Cipher Specification, S. 15) ist für den erweiterten AES leicht modifiziert, und der folgende Algorithmus wird zur Generierung der Rundenschlüssel verwendet:

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. Funktionen
Der ursprüngliche AES verwendet grundsätzlich 4 Hauptfunktionen. Diese sind die XOR-Addition zwischen dem Nachrichtenblock und dem Rundenschlüssel (AddRoundKey), Sbox-Lookups (SboxSubstitution), Zeilenverschiebung (ShiftRow) und das Mischen jeder Spalte in der Matrix (MixColumn).

1.1.1. AddRoundKey
Für den Rundenschlüsselhinzufügungsprozess gibt es keinen Unterschied zwischen dem ursprünglichen und dem erweiterten AES.

1.1.2. SboxSubstitution
Der Sbox-Lookup-Prozess ist sowohl im ursprünglichen als auch im erweiterten AES identisch.

1.1.3. ShiftRow
Der Zeilenverschiebungsprozess unterscheidet sich im ursprünglichen und erweiterten AES. Der ursprüngliche AES verwendet {0,1,2,3} Offsets für die Zeilenverschiebung. Das bedeutet, dass in der ShiftRow-Operation die Bytes in der ersten Zeile nicht verschoben werden. Die Bytes in der zweiten Zeile werden um 1 Byte nach links verschoben (für die Verschlüsselung); die Bytes in der dritten Zeile werden um 2 Bytes nach links verschoben, und schließlich werden die Bytes in der letzten Zeile um 3 Bytes nach links verschoben. Die ShiftRow-Operation wird in jeder Runde des AES angewendet, und nach zwei Runden führen die Kombination von ShiftRow und MixColumn zu einer vollständigen Diffusion in der Matrix; das bedeutet, dass nach zwei Runden jede Zelle der Matrix den Wert aller anderen Zellen beeinflusst.

Wenn wir jedoch die {0,1,2,3} Offsets für die Zeilenverschiebung im erweiterten AES anwenden, wird diese vollständige Diffusion erst nach 5 Runden erreicht, anstatt nach 2 Runden. Daher müssen wir bessere Verschiebungs-Offsets finden, die die vollständige Diffusion in wenigen Runden bieten. Zu diesem Zweck haben wir ein Programm geschrieben (siehe com.crypt.test.OptimumShiftRow.java im verteilten Quellcode), das die optimalen Verschiebungs-Offsets berechnet hat. Das Ergebnis war, dass die vollständige Diffusion nur nach 4 Runden im erweiterten AES erreicht werden kann. Es gab viele Kandidaten, die die vollständige Diffusion in 4 Runden erreichen, und wir haben die {0,1,4,5} Offsets für den erweiterten AES gewählt.

1.1.4. MixColumn Die gleiche MixColumn-Operation wird sowohl im ursprünglichen als auch im erweiterten AES angewendet. Im ursprünglichen AES gibt es nur 4 Spalten, während der erweiterte AES 16 Spalten enthält.