L’opération modulo (notée % dans la plupart des langages de programmation) retourne le reste d’une division entière (division euclidienne).

Exemple :

$13 = 2 × 5 + 3$ donc $12 \% 5 = 3$ (Il faut bien sûr que $3 < 5$ sinon ce n’est pas une division euclidienne)

Congruence

On dit que deux nombres $A$ et $B$ sont congrus modulo $P$ s’ils ont le même reste dans la division euclidienne par $P$. Cela se note : $A \equiv B [P]$.

Cela équivaut à dire que la différence $A - B$ est un multiple de $P$, c’est-à-dire qu’il existe un entier $k$ tel que : $A = B + k⋅P$

Exemples avec $P = 7$ :

– $12 \equiv 5 [7]$ car $12 = 5 + 1 \times 7$
– $12 \equiv 33 [7]$ car $12 = 33 + (-3) \times 7$
– $12 \equiv -2 [7]$ car $12 = -2 + 2 \times 7$

Remarque :

En programmation, le résultat du modulo est généralement compris entre 0 et P - 1 (reste positif).
Ainsi, $12 \% 7 = 5$, et $-2 \% 7 = 5$ (dans la plupart des langages).

Dans l’AES, toutes les opérations de somme se font modulo 2.

Cela signifie que les coefficients manipulés ne peuvent être que $0$ ou $1$, et l’addition se fait selon les règles suivantes :

Propriétés importantes :
– Dans $\mathbb{F}_2$, additionner et soustraire, c’est la même chose :
$a - b ≡ a + b [2]$. En effet, $-b \equiv b [2]$ car $-1 \equiv 1 [2]$.
– L’addition modulo 2 correspond à l’opérateur logique XOR (ou exclusif) des bits.
– L’ensemble $\{0 ; 1\}$ muni de l’addition modulo 2 forme un groupe abélien (nous verrons cette notion plus loin).

Dans l’AES, les octets sont représentés comme des polynômes à coefficients dans $\mathbb{F}_2$.

Par exemple, l’octet $0b11010011$ (soit $211$ en décimal) peut s’écrire : $1⋅x^7 + 1⋅x^6 + 0⋅x^5 + 1⋅x^4 + 0⋅x^3 + 0⋅x^2 + 1⋅x + 1$ soit plus simplement : $x^7 + x^6 + x^4 + x + 1$

Opérations sur ces polynômes :

– Addition : on additionne les coefficients de mêmes degrés, modulo 2.
– Multiplication : classique, mais les coefficients sont additionnés modulo 2.
– Réduction : pour rester dans des polynômes de degré inférieur à 8, on utilise un polynôme irréductible (dans AES : $x^8 + x^4 + x^3 + x + 1$).

Cette structure mathématique s’appelle un corps de Galois, noté $\mathbb{F}_{2^8}$ ou $GF(2^8)$. C’est ce qui permet de manipuler des octets tout en conservant des propriétés algébriques essentielles pour le chiffrement.

Un groupe $(G,\circ)$ est un ensemble $G$ muni d’une opération $\circ$ (appelée « loi de composition interne ») qui vérifie quatre propriétés fondamentales :

Exemples de groupes :

• $(\mathbb{Z}, +)$ : l’ensemble des entiers relatifs avec l’addition.
  • Neutre : $0$
  • Inverse de $a$ : $-a$
• $(\mathbb{F}_2, +)$ : l’ensemble $\{0,1\}$ avec l’addition modulo 2.
  • Neutre : $0$
  • Inverse : $1$ est son propre inverse car $1+1=0$

Si, en plus des quatre propriétés ci-dessus, l’opération est commutative, on dit que le groupe est abélien (en hommage au mathématicien Niels Abel) : $\forall a,b \in G, a \circ b = b \circ a$

• Exemple : $(\mathbb{Z}, +)$ est un groupe abélien.
• Contre-exemple : l’ensemble des matrices carrées inversibles avec la multiplication (non commutative).

Le corps fini $GF(2^8)$ (Galois Field) est un espace mathématique fondamental utilisé dans de nombreux algorithmes de chiffrement, notamment AES (Rijndael). Il permet de manipuler des octets comme des éléments mathématiques avec des opérations bien définies.

1. Structure générale

$GF(2^8)$ est un corps à $2^8 = 256$ éléments.
Chaque élément est représenté par un octet (8 bits) :
– 0x00, 0x01, 0x02, ..., 0xFF en héxadécimal ;
– 0b00000000, 0b00000001, 0b00000010, ..., 0b11111111 en binaire.

Chaque octet peut être vu comme :
– Un polynôme à coefficients dans $GF(2^8)$
– Un vecteur binaire de dimension 8

2. Représentation polynomiale

Un octet $b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0$ correspond au polynôme :

$b_7 x^7 + b_6 x^6 + b_5 x^5 + b_4 x^4 + b_3 x^3 + b_2 x^2 + b_1 x + b_0$

Exemple : 0x57 = 0b01010111 = 87

0x57 = 0·x⁷ + 1·x⁶ + 0·x⁵ + 1·x⁴ + 0·x³ + 1·x² + 1·x + 1
     = x⁶ + x⁴ + x² + x + 1

3. Addition

L’addition dans $GF(2^8)$ est simplement le XOR bit à bit.

$a + b = a \oplus b$

Propriétés :

• L’élément neutre est 0
• Chaque élément est son propre inverse : $a + a = 0$

Exemple :

0x57 + 0x83 = 0x57 ⊕ 0x83 = 0xD4
 01010111
⊕10000011
---------
 11010100

En polynômes :
$(x⁶ + x⁴ + x² + x + 1) + (x⁷ + x + 1) = x⁷ + x⁶ + x⁴ + x²$ en effet, dans $GF(2^8)$, l’addition est un XOR : les coefficients s’additionnent modulo 2 ($1 + 1 \equiv 0$) donc $x + x = 2x \equiv 0$ et $1 + 1 = 2 \equiv 0$

4. Multiplication

La multiplication est plus complexe : on multiplie les polynômes, puis on réduit modulo un polynôme irréductible de degré 8.

Polynôme irréductible pour AES

AES utilise le polynôme :
$m(x) = x^8 + x^4 + x^3 + x + 1 \quad (\text{0x11B})$

Le $(\text{0x11B})$ est la représentation hexadécimale du polynôme irréductible utilisé par AES :
On encode le polynôme en hexadécimal en ne considérant que les coefficients (0 ou 1) :

Soit en binaire : 0b1 0001 1011

En regroupant par 4 bits : 1 0001 1011 = 0001 0001 1011 (en ajoutant un 0 devant pour avoir un nombre de bits multiple de 4)

Soit :

0001 = 0x1 0001 = 0x1 1011 = 0xB → 0x11B
Pourquoi 9 bits ?

Le polynôme est de degré 8, donc il a 9 coefficients (de $x^8$ à $x^0$). Sa représentation binaire nécessite 9 bits, que l’on écrit en hexadécimal sur 3 chiffres :
0x11B = 0b1 0001 1011          ↑    ↑ ↑ ↑↑          x⁸  x⁴,x³,x¹,x⁰
Dans la pratique

Lors des calculs dans $GF(2^8)$, on travaille uniquement sur des octets (8 bits). Le polynôme irréductible 0x11B sert à réduire les résultats qui dépassent 8 bits :

def reduction(x):
    """Réduction modulo 0x11B pour un résultat sur 9 bits"""
    if x & 0x100:  # si le 9ème bit est 1
        x ^= 0x11B  # soustraire le polynôme (XOR)
    return x & 0xFF

Exemple :

Si un produit donne 0x1A3 (binaire : 1 1010 0011)
On réduit : 0x1A3 ^ 0x11B = 0x0B8

C’est ce mécanisme qui permet de maintenir tous les résultats dans l’intervalle $[0x00, 0xFF]$, soit $[0 ; 256]$, tout en conservant la structure de corps fini.

Algorithme de multiplication

Pour multiplier $a$ et $b$ dans $GF(2^8)$ :

1. Multiplier les polynômes (produit pouvant aller jusqu’au degré 14)
2. Prendre le reste de la division euclidienne par $m(x)$

Exemple simplifié

Soit $a = 0x57$, $b = 0x83$ :

Étape 1 : Multiplication polynomiale
$a(x) \times b(x) = (x⁶ + x⁴ + x² + x + 1) \times (x⁷ + x + 1) = x^{13} + x^{11} + x^9 + x^8 + x^7 + x^7 + x^5 + x^3 + x^2 + x + x^6 + x^4 + x^2 + x + 1$

Après simplification (car $x^7 + x^7 \equiv 0$) :
$a(x) \times b(x) = x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1$

Étape 2 : Réduction modulo $m(x) = x^8 + x^4 + x^3 + x + 1$ (On utilise la division des polynômes)

$a(x) \times b(x) [m(x)] \equiv -x^7 - x^6 + x^0 [m(x)] \equiv x^7 + x^6 + x^0 [m(x)]$, soit 0b11000001 = 0xC1 = 193

Après calcul : $a \times b = 0xC1$ (résultat du calcul complet)

5. Multiplication rapide par xtime

AES utilise une multiplication optimisée par 2, notée xtime() :

xtime(x) = (x << 1) ⊕ 0x1B (si bit de poids fort = 1 sinon 0)

xtime() est une fonction qui effectue la multiplication par le polynôme x (c’est-à-dire par 2 en décimal) dans le corps fini $GF(2^8)$. C’est une opération fondamentale qui sert de brique de base pour toutes les multiplications dans AES.

5.1. Principe mathématique

Multiplier un polynôme par $x$ revient à décaler tous les bits vers la gauche :
$a(x)×x=(b_7x^7 + b_6x^6 + ... + b_0)×x = b_7x^8 + b_6x^7 + ... + b_0x$
Mais en $GF(2^8)$, on travaille modulo un polynôme irréductible de degré 8. Si le résultat dépasse le degré 7, on réduit en soustrayant XOR le polynôme irréductible.

5.2. Algorithme

def xtime(x):
    """
    Multiplication par 2 (par x) dans GF(2⁸)
    Polynôme : x⁸ + x⁴ + x³ + x + 1 (0x11B)
    """
    # Étape 1 : décaler à gauche
    result = (x << 1) & 0xFF
    # Étape 2 : si le bit perdu était 1, on réduit
    if x & 0x80:  # si le bit de poids fort est 1
        result ^= 0x11B 
    return result& 0xFF
# xtime(0x57) = 0xAE
# xtime(0x83) = 0x1D

5.3. Visualisation

– 0x80 est la représentation hexadécimale du nombre 128, qui en binaire s’écrit :
0x80 = 0b10000000.
C’est un masque qui a un seul bit à 1 : le 8ème bit (bit de poids fort).
– Le & est l’opérateur ET binaire (AND). Il compare chaque bit de x avec le bit correspondant du masque 0x80.
– Exemples
- Cas 1 : Le bit de poids fort est 1
x = 0x83 = 0b10000011    x & 0x80 = 0b10000011 & 0b10000000 = 0b10000000 = 128    # Le résultat est non nul → condition vraie    xtime(0x83) = (0x83 << 1) = 0x106 (0b100000110)    On masque sur 8 bits : 0x06    Puis on XOR avec 0x11B : 0x06 ^ 0x11B = 0x1D
Si le bit de poids fort de x est 1 : le décalage fait apparaître un 9ème bit (débordement) → on doit réduire en XORant avec 0x11B
- Cas 2 : Le bit de poids fort est 0
x = 0x57 = 0b01010111    x & 0x80 = 0b01010111 & 0b10000000 = 0b00000000 = 0 # Le résultat est nul → condition fausse    xtime(0x57) = (0x57 << 1) = 0xAE (0b10101110)
Si le bit de poids fort de x est 0 : le décalage ne provoque pas de débordement → pas de réduction

5.4. Pourquoi cette optimisation ?

xtime() est optimisée car :
– Rapide : Un seul décalage et un XOR conditionnel
– Matériel : Se fait en quelques cycles d’horloge
– Réutilisable : Sert à construire toutes les multiplications

5.5. Multiplication générale avec xtime()

On peut construire n’importe quelle multiplication en combinant des xtime() et des XOR :

def gf256_mult(a, b):
    """Multiplication utilisant xtime()"""
    result = 0
    for _ in range(8):
        if b & 1:
            result ^= a
        a = xtime(a)   # a = a × 2
        b >>= 1
    return result
gf256_mult(0x57, 0xBF)

La multiplication générale s’effectue par combinaison d’additions et de xtime.

5.6. Code Python pour la multiplication dans $GF(2^8)$

def gf256_mult(a, b):
    """Multiplication dans GF(2^8) - version explicite"""
    result = 0
    for i in range(8):
        if b & 1:
            result ^= a
        # xtime sur a
        high_bit = (a >> 7) & 1
        a = (a << 1) & 0xFF
        if high_bit:
            a ^= 0x11B
        b >>= 1
    return result
# Test
print(hex(gf256_mult(0x57, 0x83)))  # 0xc1

6. L’inverse dans $GF(2^8)$

L’inverse d’un élément $a$ dans $GF(2^8)$ est l’élément $a^{-1}$ tel que :

$a \times a^{-1} = 1 \quad \text{(dans} GF(2^8)\text{)}$

6.1. Pourquoi l’inverse est-il important ?

Dans AES, l’opération SubBytes (la seule non-linéaire) utilise l’inverse dans $GF(2^8)$ :

$\text{SubBytes}(a) = \text{Inv}(a) \times M + b$ où $M$ est une matrice affine et $b$ un vecteur constant.

L’inverse introduit une forte non-linéarité qui rend la cryptanalyse différentielle et linéaire beaucoup plus difficile.

6.2. Propriétés de l’inverse

6.3. Exemples concrets

6.4. Vérification avec Python

# Vérification de l'inverse de 0x57
a = 0x57
inv_a = 0xBF
print(hex(gf256_mult(a, inv_a)))  # 0x1

6.5. Comment calculer l’inverse ?

Plusieurs méthodes existent :

Méthode 1 : Algorithme d’Euclide étendu (dans $GF(2^8)$)

On cherche $u(x)$ et $v(x)$ tels que : $a(x) \cdot u(x) + m(x) \cdot v(x) = 1$.
Alors $u(x)$ est l’inverse de $a(x)$ modulo $m(x)$.

Exemple :
Trouver l’inverse de $a(x) = x^6 + x^4 + x^2 + x + 1 (0x57)$ avec $m(x) = x^8 + x^4 + x^3 + x + 1 (0x11B)$
Voici le développement pour trouver l’inverse de 0x57 modulo 0x11B.

1. Rappel des données

• $m(x) = x^8 + x^4 + x^3 + x + 1$ (0x11B)
• $a(x) = x^6 + x^4 + x^2 + x + 1$ (0x57)

2. Algorithme d’Euclide étendu pas à pas

Itération 1 : $\dfrac{r_{-1}}{r_0}$

• $q_1 = \mathbf{x^2 + 1}$
• $r_1 = r_{-1} \oplus (x^2+1)r_0 = \mathbf{x^4}$
• $u_1 = u_{-1} \oplus (x^2+1)u_0 = 0 \oplus (x^2+1) = \mathbf{x^2+1}$

Itération 2 : $\dfrac{r_0}{r_1}$

• $q_2 = \mathbf{x^2 + 1}$
• $r_2 = r_0 \oplus (x^2+1)x^4 = (x^6+x^4+x^2+x+1) \oplus (x^6+x^4) = \mathbf{x^2+x+1}$
• $u_2 = u_0 \oplus (x^2+1)u_1 = 1 \oplus (x^2+1)^2 = 1 \oplus (x^4+1) = \mathbf{x^4}$

Itération 3 : $\dfrac{r_1}{r_2}$

• $q_3 = \mathbf{x^2 + x}$ (car $(x^2+x)(x^2+x+1) = x^4+x^3+x^2 + x^3+x^2+x = x^4+x$)
• $r_3 = x^4 \oplus (x^4+x) = \mathbf{x}$
• $u_3 = u_1 \oplus (x^2+x)u_2 = (x^2+1) \oplus (x^2+x)x^4 = (x^2+1) \oplus (x^6+x^5) = \mathbf{x^6+x^5+x^2+1}$

Itération 4 : $\dfrac{r_2}{r_3}$

• $q_4 = \mathbf{x + 1}$ (car $(x+1)x = x^2+x$)
• $r_4 = (x^2+x+1) \oplus (x^2+x) = \mathbf{1}$
• $u_4 = u_2 \oplus (x+1)u_3 = x^4 \oplus(x+1) \cdot (x^6+x^5+x^2+1) = x^4 \oplus x^7+x^6+x^3+x + x^6+x^5+x^2+1 = \mathbf{x^7 + x^4 + x^5 + x^3 + x^2 + x + 1}$

Puisque le reste $r_4$ est nul, l’inverse de $x^6 + x^4 + x^2 + x + 1$ est $u_4 = \mathbf{x^7 + x^4 + x^5 + x^3 + x^2 + x + 1}$.

Résultat

En binaire : 0b10111111
En hexadécimal : 0xBF

Version Python de l’algorithme d’Euclide étendu

def gf256_inv(a, m=0x11b):
    if a == 0: 
        return 0
    # Initialisation : u0*m + v0*a = r0 | u1*m + v1*a = r1
    r0, r1 = m, a
    v0, v1 = 0, 1 # On cherche v tel que v*a = 1 mod m
    while r1 != 0:
        # 1. Calculer le quotient complet q de r0 / r1
        # Dans GF(2), c'est une division polynomiale
        q = 0
        temp_r1 = r1
        deg_r0 = r0.bit_length() - 1
        deg_r1 = temp_r1.bit_length() - 1
        # Division longue pour trouver le quotient q
        while deg_r0 >= deg_r1:
            shift = deg_r0 - deg_r1
            q ^= (1 << shift)
            r0 ^= (temp_r1 << shift)
            deg_r0 = r0.bit_length() - 1
        # 2. Mettre à jour r et v (v correspond à u dans votre code)
        # r_suivant = r0 (qui est devenu le reste après le XOR au-dessus)
        # v_suivant = v0 ^ q*v1
        # Pour v0 ^ (q * v1), on doit faire une multiplication polynomiale GF(2)
        prod = 0
        for i in range(q.bit_length()):
            if (q >> i) & 1:
                prod ^= (v1 << i)
        v0, v1 = v1, v0 ^ prod
        r0, r1 = r1, r0
    return v0
print(f"L'inverse de 0x57 est : {hex(gf256_inv(0x57))}") # 0xbf

Méthode 2 : Exponentiation (petit théorème de Fermat)

Dans un corps fini $GF(2^8)$ :
$a^{-1} = a^{254}$ car $a^{255} = 1$ pour tout $a \neq 0$.

def gf256_inv_pow(a):
    """Inverse par exponentiation (a²⁵⁴)"""
    if a == 0:
        return 0
    result = 1
    for _ in range(254):  # a^254
        result = gf256_mult(result, a)
    return result
hex(gf256_inv_pow(0x57))
>>>'0xbf'

Méthode 3 : Table pré-calculée

La méthode la plus rapide en pratique : pré-calculer une table de 256 entrées.

def gf256_inv_table():
    """
    Prépare une table d'inverses multiplicatifs dans GF(2⁸)
    avec le polynôme x⁸ + x⁴ + x³ + x + 1 (0x11B)
    Returns:
        list: Table de 256 entrées où table[a] = a⁻¹
    """
    # Initialisation de la table
    inv_table = [0] * 256
    # Cas particulier : 0 n'a pas d'inverse (on lui donne 0 par convention)
    inv_table[0] = 0
    # Pour chaque élément non nul, calculer son inverse
    for a in range(1, 256):
        # Recherche de l'inverse par force brute
        # (une seule fois à l'initialisation)
        for b in range(1, 256):
            if gf256_mult(a, b) == 1:
                inv_table[a] = b
                break
    return inv_table
# Construction de la table
INV_TABLE = gf256_inv_table()
def gf256_inv_table_lookup(a):
    """
    Retourne l'inverse multiplicatif de a dans GF(2⁸)
    Utilise une table pré-calculée
    Args:
        a: entier entre 0 et 255
    Returns:
        int: a⁻¹ dans GF(2⁸)
    """
    return INV_TABLE[a & 0xFF]
# Affichage des premiers inverses
print("Table des inverses (début) :")
for i in range(16):
    print(f"0x{i:02X} → 0x{INV_TABLE[i]:02X}")
>>>Table des inverses (début) :
0x00 → 0x00
0x01 → 0x01
0x02 → 0x8D
0x03 → 0xF6
0x04 → 0xCB
0x05 → 0x52
0x06 → 0x7B
0x07 → 0xD1
0x08 → 0xE8
0x09 → 0x4F
0x0A → 0x29
0x0B → 0xC0
0x0C → 0xB0
0x0D → 0xE1
0x0E → 0xE5
0x0F → 0xC7

hex(gf256_inv_table_lookup(0x57))
>>>'0xbf'

6.6. Rôle dans AES

Dans AES, l’inverse est utilisé dans SubBytes :

┌─────────────┐
│   Octet a   │
└──────┬──────┘
       ▼
┌─────────────┐
│  a⁻¹ dans   │  ← inversion dans GF(2⁸)
│   GF(2⁸)    │
└──────┬──────┘
       ▼
┌─────────────┐
│ Affine      │  ← transformation affine
│   M·x + b   │
└──────┬──────┘
       ▼
┌─────────────┐
│  S-Box(a)   │
└─────────────┘

L’inversion dans $GF(2^8)$ assure que :

• La transformation est non-linéaire (aucune relation affine entre l’entrée et la sortie)
• Tout changement d’un bit en entrée modifie en moyenne 4 bits en sortie (avalanche)
• Résistance aux cryptanalyses différentielle et linéaire

7. Table récapitulative

8. Utilisation dans AES

$GF(2^8)$ est au cœur d’AES pour :

• SubBytes : inversion dans $GF(2^8)$ suivie d’une transformation affine
• MixColumns : multiplication de colonnes par un polynôme fixe dans $GF(2^8)$
• KeyExpansion : génération des sous-clés

Cette structure algébrique permet d’implémenter des opérations de chiffrement à la fois rapides en matériel et résistantes aux attaques grâce à la non-linéarité de l’inversion dans le corps.

Le dernier round ne comporte pas MixColumns pour que la structure du déchiffrement soit parfaitement symétrique et utilise exactement les mêmes transformations inverses que le chiffrement, sans avoir à gérer un cas particulier.

La raison est liée à la symétrie entre chiffrement et déchiffrement.

1. Structure du chiffrement
   • Pour les rounds 1 à 9 (sur AES-128) : SubBytes → ShiftRows → MixColumns → AddRoundKey
   • Pour le round 10 (dernier) : SubBytes → ShiftRows → AddRoundKey
2. Structure du déchiffrement
   Pour que le déchiffrement fonctionne, on applique les transformations inverses dans l’ordre inverse :
   • Pour les rounds 1 à 9 (déchiffrement) : InvShiftRows → InvSubBytes → AddRoundKey → InvMixColumns
   • Pour le dernier round du déchiffrement (qui correspond au premier round du chiffrement) : InvShiftRows → InvSubBytes → AddRoundKey
     On constate que le InvMixColumns n’est pas présent au dernier round du déchiffrement.
3. Pourquoi cette asymétrie serait un problème ?
   • Si le dernier round du chiffrement contenait MixColumns, alors le déchiffrement devrait commencer par InvMixColumns. Cela fonctionnerait mathématiquement, mais créerait une incohérence structurelle :
   • Le premier round du déchiffrement devrait traiter InvMixColumns sans avoir d’AddRoundKey avant (car l’ordre serait inversé)
   • Cela compliquerait l’implémentation et romprait l’alternance régulière AddRoundKey / MixColumns
4. La règle d’or
   Pour qu’un chiffrement par blocs soit facilement réversible, on veut que la structure du déchiffrement soit identique à celle du chiffrement, mais avec :
   • Les transformations inverses
   • Les clés utilisées dans l’ordre inverse

En supprimant MixColumns au dernier round, on garantit que AddRoundKey est la dernière opération du chiffrement et la première opération du déchiffrement. Ainsi, aucune transformation de diffusion (qui mélange les octets) ne se trouve « à découvert » sans clé.

En résumé

MixColumns est absent du dernier round pour que le déchiffrement puisse s’enchaîner de manière symétrique : on termine le chiffrement par AddRoundKey (la seule opération qui dépend de la clé) et on commence le déchiffrement par AddRoundKey (avec la même clé). Ainsi, la structure reste élégante, régulière et facile à implémenter.

1. Introduction

SubBytes est la première transformation appliquée à chaque round de l’AES (après l’AddRoundKey initial).
C’est une substitution non linéaire qui agit indépendamment sur chaque octet du bloc.

Propriétés fondamentales

Remarque : Dans cette section, l’ensemble d’arrivée et de départ est le même : le corps de Galois $\mathbb{F}_{2^8}$ (ou $GF(2^8)$).

2. Fonctionnement général

SubBytes s’effectue en deux étapes distinctes :

1. Calcul de l’inverse multiplicatif dans $\mathbb{F}_{2^8}$
2. Application d’une transformation affine (sur $\mathbb{F}_2$)
   Prenons comme exemple tout au long de cette section :
   $A = \texttt{10011011}_2 = \texttt{0x9B}$

3. Étape 1 : Calcul de l’inverse multiplicatif

On remplace l’octet $A = (a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0)$ par son inverse multiplicatif dans $\mathbb{F}_{2^8}$.
Précision importante : Nous sommes dans le groupe multiplicatif de $\mathbb{F}_{2^8}$, dont l’élément neutre est $\texttt{0x01}$.
L’élément $\texttt{0x00}$ n’a pas d’inverse multiplicatif ; par convention, on pose $\texttt{0x00}^{-1} = \texttt{0x00}$.
L’inverse multiplicatif peut être calculé par l’algorithme d’Euclide étendu dans les corps finis, mais en pratique, on utilise une table pré-calculée (la S-box) car elle est fixe.

Soit $B’ = A^{-1}$.

Exemple :

$A = \texttt{0x9B} \quad \Rightarrow \quad A^{-1} = \texttt{0x88}$

Soit en binaire :
$A^{-1} = \texttt{10001000}_2$

4. Étape 2 : Transformation affine

On applique ensuite une transformation affine sur $B’$ pour obtenir $B = \text{SubBytes}(A)$.

Cette transformation est définie par :
$\boxed{ \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} b’_0 \\ b’_1 \\ b’_2 \\ b’_3 \\ b’_4 \\ b’_5 \\ b’_6 \\ b’_7 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} \pmod{2} }$

Interprétation : Il s’agit d’une multiplication matricielle (modulo 2) suivie d’une addition d’un vecteur constant (appelé *constante affine*). Cette opération est réalisée dans $\mathbb{F}_2$ (addition = XOR).

Exemple avec $B’ = \texttt{10001000}$ :

Calculons étape par étape. $B’$ en binaire : $b’_7=1$, $b’_6=0$, $b’_5=0$, $b’_4=0$, $b’_3=1$, $b’_2=0$, $b’_1=0$, $b’_0=0$.

Pour $b_0$ (première ligne) :
$b_0 = 1\cdot b’_0 + 0\cdot b’_1 + 0\cdot b’_2 + 0\cdot b’_3 + 1\cdot b’_4 + 1\cdot b’_5 + 1\cdot b’_6 + 1\cdot b’_7 + 1 \pmod{2}$
$b_0 = b’_0 + b’_4 + b’_5 + b’_6 + b’_7 + 1$
$b_0 = 0 + 1 + 0 + 0 + 1 + 1 = 1 \pmod{2}$

Après calcul complet (à faire en exercice), on obtient :
$B = \texttt{00010100}_2 = \texttt{0x14}$

5. Simplification : la S-box

Les deux étapes (inverse multiplicatif + transformation affine) sont combinées en une seule table de correspondance : la S-box (Substitution box).

La S-box est une table de $16 \times 16$ (256 entrées) qui donne directement $\text{SubBytes}(x)$ pour tout octet $x$. Elle est pré-calculée et identique pour toutes les implémentations.

**Comment lire la table** :
– Le premier chiffre hexadécimal (ligne) donne les 4 bits de poids fort.
– Le second chiffre hexadécimal (colonne) donne les 4 bits de poids faible.

Exemple avec $A = \texttt{0x9B}$ :
– Ligne 9, colonne B → on lit 0x14

On retrouve bien le résultat précédent !

6. Propriétés de la S-box

Observons quelques propriétés intéressantes :

Vérification : Compter le nombre de fois que chaque valeur apparaît dans la S-box permet de confirmer la bijectivité.

7. Inverse de SubBytes (InvSubBytes)

Pour déchiffrer, on a besoin de la transformation inverse. Elle se construit en deux étapes :

1. Inverse de la transformation affine $f^{-1}$
2. Calcul de l’inverse multiplicatif du résultat

La transformation affine inverse est donnée par :
$\boxed{ \begin{pmatrix} b’_0 \\ b’_1 \\ b’_2 \\ b’_3 \\ b’_4 \\ b’_5 \\ b’_6 \\ b’_7 \end{pmatrix} \equiv \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \end{pmatrix} \pmod{2} }$

En pratique, on utilise aussi une table pré-calculée : la InvS-box (inverse S-box), qui donne directement $\text{InvSubBytes}(x)$.

8. Récapitulatif : SubBytes en pratique

9. Pourquoi cette complexité ?

La combinaison de l’inverse multiplicatif (structure algébrique forte) et de la transformation affine (qui brise la structure algébrique) permet d’obtenir :

– Une forte non-linéarité (résistance aux attaques différentielles et linéaires)
– L’absence de points fixes ou de symétries
– Une implémentation efficace via table pré-calculée

1. Introduction

ShiftRows est la deuxième transformation de chaque round (après SubBytes). Avec MixColumns, elle constitue la couche de diffusion de l’AES.

Objectif : introduire de la confusion dans les données en modifiant l’ordre des octets au sein du bloc. La diffusion permet de répartir l’influence de chaque octet du texte clair sur un grand nombre d’octets du texte chiffré.

La transformation est simple : on applique un décalage circulaire (rotation) sur chaque ligne (row) de la matrice représentant le bloc.

2. Rappel : organisation du bloc

Rappelons que le bloc de 16 octets est organisé en matrice $4 \times 4$ colonne par colonne :

Important : Les indices $A_1$ à $A_{16}$ correspondent à l’ordre de lecture colonne par colonne. C’est essentiel pour comprendre les décalages.

3. Principe de ShiftRows

ShiftRows applique un décalage circulaire vers la gauche sur chaque ligne. Le nombre de décalages dépend du numéro de la ligne :

Remarque : Un décalage circulaire signifie que les octets qui « sortent » à gauche réapparaissent à droite.

Visualisation

Avant ShiftRows (matrice avec indices) :

Après ShiftRows :

4. Représentation sous forme de tableau d’indices

Pour implémenter ShiftRows en programmation, on peut utiliser un tableau de correspondance (permutation) qui donne, pour chaque position d’origine, sa nouvelle position.

En considérant les 16 positions indexées de 0 à 15 (dans l’ordre colonne par colonne), la permutation est :

Ou plus simplement, en termes de correspondance des indices $A_1$ à $A_{16}$ (en partant de 1) :

Avant → Après :

$$ [A_1, A_2, A_3, A_4, A_5, A_6, A_7, A_8, A_9, A_{10}, A_{11}, A_{12}, A_{13}, A_{14}, A_{15}, A_{16}] $$

$$ \Downarrow $$

$$ [A_1, A_6, A_{11}, A_{16}, A_5, A_{10}, A_{15}, A_4, A_9, A_{14}, A_3, A_8, A_{13}, A_2, A_7, A_{12}] $$

Exemple : $A_2$ (ligne 1, col 0) se déplace en position 1 (ligne 1, col 1) après décalage.

5. Exemple concret

Prenons un bloc d’exemple avec des valeurs simples pour visualiser le décalage :

Bloc initial (en hexadécimal, indices pour repérage) :

Après ShiftRows :

6. Réversibilité

ShiftRows est facilement réversible : il suffit d’appliquer un décalage circulaire vers la droite sur chaque ligne.

Vérification : Si on reprend l’exemple précédent et qu’on applique le décalage inverse, on retrouve bien la matrice d’origine.

En termes de tableau de correspondance inverse :

7. Pourquoi ce décalage ?

Le choix des décalages (0, 1, 2, 3) n’est pas anodin :

– Ligne 0 inchangée : permet de préserver une partie de la structure pour le déchiffrement.
– Décalages croissants : assurent qu’après plusieurs rounds, chaque octet de la colonne a été distribué dans toutes les colonnes.

Cette diffusion, combinée avec MixColumns, garantit qu’après quelques rounds, chaque octet du texte chiffré dépend de tous les octets du texte clair.

8. Implémentation simple

def shift_rows(bloc):
    """
    Applique ShiftRows sur un bloc de 16 octets (liste d'entiers)
    Le bloc est organisé en 4 lignes de 4 octets (ordre colonne par colonne)
    """
    # Transformer la liste plate en matrice 4x4 (colonne par colonne)
    matrice = [[0]*4 for _ in range(4)]
    for ligne in range(4):
        for col in range(4):
            matrice[ligne][col] = bloc[ligne + 4*col]
    
    # Appliquer les décalages
    decalages = [0, 1, 2, 3]
    nouvelle_matrice = [[0]*4 for _ in range(4)]
    
    for ligne in range(4):
        for col in range(4):
            # Décalage circulaire vers la gauche
            nouvelle_col = (col - decalages[ligne]) % 4
            nouvelle_matrice[ligne][col] = matrice[ligne][nouvelle_col]
    
    # Reconstruire la liste plate
    resultat = [0]*16
    for ligne in range(4):
        for col in range(4):
            resultat[ligne + 4*col] = nouvelle_matrice[ligne][col]
    
    return resultat

# Version simplifiée avec permutation directe
def shift_rows_permutation(bloc):
    """Version utilisant la permutation directe"""
    permutation = [0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11]
    return [bloc[p] for p in permutation]

# Test
bloc_test = list(range(1, 17))
print("Avant :", bloc_test)
print("Après :", shift_rows_permutation(bloc_test))

9. Récapitulatif

Pour aller plus loin

1. Visualisation interactive  : Afficher la matrice avant/après côte à côte.
2. Exercice : Appliquer ShiftRows à un bloc concret (par exemple en reprenant les valeurs hexadécimales d’un vrai bloc AES) et vérifier le résultat avec une implémentation de référence.
3. Question de réflexion :
   > Pourquoi est-il important que la ligne 0 ne soit pas décalée ? Que se passerait-il si toutes les lignes étaient décalées du même nombre ?

1. Introduction

MixColumns est la troisième transformation de chaque round (après ShiftRows). Avec ShiftRows, elle constitue la couche de diffusion de l’AES.

Objectif : faire en sorte que chaque octet de la colonne de sortie dépende de tous les octets de la colonne d’entrée. Cela permet de propager rapidement l’influence de chaque bit à travers tout le bloc.

Contrairement à ShiftRows qui est une simple permutation, MixColumns est une transformation algébrique qui mélange réellement les bits entre eux.

2. Organisation des données

Rappelons l’organisation du bloc en matrice $4 \times 4$ (ordre colonne par colonne) :

MixColumns agit indépendamment sur chaque colonne. Pour une colonne donnée, on note $A_i$ les quatre octets de la colonne d’entrée, et $C_i$ les quatre octets de la colonne de sortie.

3. Principe de la transformation

MixColumns applique une multiplication matricielle dans $\mathbb{F}_{2^8}$ (le corps de Galois) entre une matrice fixe $S$ et chaque colonne du bloc.

Pour une colonne d’indice $i$ (avec $i \in \{0, 1, 2, 3\}$) :

$$ \begin{pmatrix} C_{i} \\ C_{i+4} \\ C_{i+8} \\ C_{i+12} \end{pmatrix} = \begin{pmatrix} \text{0x02} & \text{0x03} & \text{0x01} & \text{0x01} \\ \text{0x01} & \text{0x02} & \text{0x03} & \text{0x01} \\ \text{0x01} & \text{0x01} & \text{0x02} & \text{0x03} \\ \text{0x03} & \text{0x01} & \text{0x01} & \text{0x02} \end{pmatrix} \cdot \begin{pmatrix} A_{i} \\ A_{i+4} \\ A_{i+8} \\ A_{i+12} \end{pmatrix} $$

Remarque importante : Les coefficients de la matrice sont des éléments de $\mathbb{F}_{2^8}$. Ils sont représentés en hexadécimal :

• $\text{0x01} = 00000001_2$ (élément neutre)
• $\text{0x02} = 00000010_2$
• $\text{0x03} = 00000011_2$

4. Détail des opérations dans $\mathbb{F}_{2^8}$

Multiplication par 0x01

C’est l’élément neutre : $\text{0x01} \cdot X = X$

Multiplication par 0x02

Dans $\mathbb{F}_{2^8}$, multiplier par $\text{0x02}$ équivaut à :

1. Décaler tous les bits de l’octet d’un cran vers la gauche (multiplication polynomiale par $x$)
2. Si le bit de poids fort (bit 7) était à 1 avant le décalage, on réduit en effectuant un XOR avec $\text{0x1B}$ (le polynôme irréductible $x^8 + x^4 + x^3 + x + 1$)

En Python, cela donne :

def mul_by_02(octet):
    if octet & 0x80:  # bit de poids fort = 1
        return ((octet << 1) ^ 0x1B) & 0xFF
    else:
        return (octet << 1) & 0xFF

Multiplication par 0x03

On utilise la propriété : $\text{0x03} = \text{0x02} \oplus \text{0x01}$ (car $3 = 2 + 1$ dans $\mathbb{F}_{2^8}$)

Ainsi :

$$\text{0x03} \cdot X = (\text{0x02} \cdot X) \oplus X$$

5. Développement des équations

Pour une colonne donnée, les quatre octets de sortie s’écrivent :

$$ \begin{cases} C_i = (\text{0x02} \cdot A_i) \oplus (\text{0x03} \cdot A_{i+4}) \oplus A_{i+8} \oplus A_{i+12} \\ C_{i+4} = A_i \oplus (\text{0x02} \cdot A_{i+4}) \oplus (\text{0x03} \cdot A_{i+8}) \oplus A_{i+12} \\ C_{i+8} = A_i \oplus A_{i+4} \oplus (\text{0x02} \cdot A_{i+8}) \oplus (\text{0x03} \cdot A_{i+12}) \\ C_{i+12} = (\text{0x03} \cdot A_i) \oplus A_{i+4} \oplus A_{i+8} \oplus (\text{0x02} \cdot A_{i+12}) \end{cases} $$

où $\oplus$ désigne l’opération XOR (addition dans $\mathbb{F}_{2^8}$).

6. Exemple concret

Prenons une colonne d’exemple (première colonne, $i=0$) :

Calculs préliminaires :

• $\text{0x02} \cdot A_0$ : $0x9B = 0x9B$ (bit 7 = 1) → décalage + XOR 0x1B
• $0x9B << 1 = 0x136$ → $0x36$ après masque
• $0x36 \oplus 0x1B = 0x2D$
• Donc $\text{0x02} \cdot 0x9B = 0x2D$

• $\text{0x03} \cdot A_4 = (\text{0x02} \cdot 0x88) \oplus 0x88$
• $\text{0x02} \cdot 0x88$ : $0x88$ (bit 7=1) → décalage + XOR 0x1B
• $0x88 << 1 = 0x110 → 0x10$
• $0x10 \oplus 0x1B = 0x0B$
• $0x0B \oplus 0x88 = 0x83$

• $\text{0x02} \cdot A_8 : 0x14$ (bit 7=0) → simple décalage
• $0x14 << 1 = 0x28$

• $\text{0x02} \cdot A_{12} : 0x2A$ (bit 7=0) → simple décalage
• $0x2A << 1 = 0x54$

• $\text{0x03} \cdot A_8 = (\text{0x02} \cdot 0x14) \oplus 0x14 = 0x28 \oplus 0x14 = 0x3C$
• $\text{0x03} \cdot A_{12} = (\text{0x02} \cdot 0x2A) \oplus 0x2A = 0x54 \oplus 0x2A = 0x7E$

Calcul des octets de sortie :

• $C_0 = 0x2D \oplus 0x83 \oplus 0x14 \oplus 0x2A$
• $0x2D \oplus 0x83 = 0xAE$
• $0xAE \oplus 0x14 = 0xBA$
• $0xBA \oplus 0x2A = 0x90$

• $C_4 = 0x9B \oplus 0x0B \oplus 0x3C \oplus 0x2A$
• $0x9B \oplus 0x0B = 0x90$
• $0x90 \oplus 0x3C = 0xAC$
• $0xAC \oplus 0x2A = 0x86$

• $C_8 = 0x9B \oplus 0x88 \oplus 0x28 \oplus 0x7E$
• $0x9B \oplus 0x88 = 0x13$
• $0x13 \oplus 0x28 = 0x3B$
• $0x3B \oplus 0x7E = 0x45$

• $C_{12} = 0x7E \oplus 0x88 \oplus 0x14 \oplus 0x54$
• $0x7E \oplus 0x88 = 0xF6$
• $0xF6 \oplus 0x14 = 0xE2$
• $0xE2 \oplus 0x54 = 0xB6$

La colonne de sortie est donc : $[0x90, 0x86, 0x45, 0xB6]$

7. Réversibilité : InvMixColumns

MixColumns est une transformation linéaire et bijective. Pour déchiffrer, on applique la matrice inverse $S’$ :

$$ \begin{pmatrix} A_{i} \\ A_{i+4} \\ A_{i+8} \\ A_{i+12} \end{pmatrix} = \begin{pmatrix} \text{0x0E} & \text{0x0B} & \text{0x0D} & \text{0x09} \\ \text{0x09} & \text{0x0E} & \text{0x0B} & \text{0x0D} \\ \text{0x0D} & \text{0x09} & \text{0x0E} & \text{0x0B} \\ \text{0x0B} & \text{0x0D} & \text{0x09} & \text{0x0E} \end{pmatrix} \cdot \begin{pmatrix} C_{i} \\ C_{i+4} \\ C_{i+8} \\ C_{i+12} \end{pmatrix} $$

Vérification  : En reprenant l’exemple précédent, on devrait retrouver $[0x9B, 0x88, 0x14, 0x2A]$.

8. Implémentation Python

def mul_by_02(octet):
    """Multiplication par 0x02 dans GF(2^8)"""
    if octet & 0x80:
        return ((octet << 1) ^ 0x1B) & 0xFF
    return (octet << 1) & 0xFF

def mul_by_03(octet):
    """Multiplication par 0x03 dans GF(2^8)"""
    return mul_by_02(octet) ^ octet

def mix_columns(bloc):
    """
    Applique MixColumns sur un bloc de 16 octets
    Le bloc est organisé en 4 lignes (ordre colonne par colonne)
    """
    resultat = [0] * 16
    
    for col in range(4):  # Pour chaque colonne
        i = col  # indice de base pour la colonne
        
        a0 = bloc[i + 0]   # ligne 0
        a1 = bloc[i + 4]   # ligne 1
        a2 = bloc[i + 8]   # ligne 2
        a3 = bloc[i + 12]  # ligne 3
        
        # Calcul des 4 octets de sortie
        resultat[i + 0] = mul_by_02(a0) ^ mul_by_03(a1) ^ a2 ^ a3
        resultat[i + 4] = a0 ^ mul_by_02(a1) ^ mul_by_03(a2) ^ a3
        resultat[i + 8] = a0 ^ a1 ^ mul_by_02(a2) ^ mul_by_03(a3)
        resultat[i + 12] = mul_by_03(a0) ^ a1 ^ a2 ^ mul_by_02(a3)
    
    return resultat

# Version avec la matrice inverse pour le déchiffrement
def inv_mix_columns(bloc):
    """InvMixColumns - déchiffrement"""
    resultat = [0] * 16
    
    for col in range(4):
        i = col
        
        c0 = bloc[i + 0]
        c1 = bloc[i + 4]
        c2 = bloc[i + 8]
        c3 = bloc[i + 12]
        
        # Multiplication par les coefficients de la matrice inverse
        # 0x0E, 0x0B, 0x0D, 0x09
        resultat[i + 0] = mul_by_0e(c0) ^ mul_by_0b(c1) ^ mul_by_0d(c2) ^ mul_by_09(c3)
        resultat[i + 4] = mul_by_09(c0) ^ mul_by_0e(c1) ^ mul_by_0b(c2) ^ mul_by_0d(c3)
        resultat[i + 8] = mul_by_0d(c0) ^ mul_by_09(c1) ^ mul_by_0e(c2) ^ mul_by_0b(c3)
        resultat[i + 12] = mul_by_0b(c0) ^ mul_by_0d(c1) ^ mul_by_09(c2) ^ mul_by_0e(c3)
    
    return resultat

Note : Les fonctions mul_by_09, mul_by_0b, mul_by_0d, mul_by_0e peuvent être implémentées par combinaisons de multiplications par 0x02 (par exemple, $0x09 = 0x02 \cdot 0x02 \cdot 0x02 \oplus 0x01$).

9. Récapitulatif

10. Pourquoi cette matrice ?

Le choix de cette matrice particulière (appelée matrice de MDS - Maximum Distance Separable) garantit une diffusion optimale : après une seule application de MixColumns, la moindre modification d’un octet d’entrée affecte tous les octets de sortie de la colonne.

Pour aller plus loin

1. Cellule interactive : Visualiser l’effet de MixColumns sur une colonne.
2. Exercice : Vérifier que la multiplication par 0x03 correspond bien à $(\text{0x02} \cdot X) \oplus X$.
3. Vérification expérimentale : Appliquer MixColumns puis InvMixColumns et vérifier qu’on retrouve le bloc original.
4. Question de réflexion : Pourquoi la matrice inverse contient-elle des coefficients plus grands (0x0E, 0x0B, 0x0D, 0x09) ? Quelle est leur signification dans $\mathbb{F}_{2^8}$ ?

1. Introduction

AddRoundKey est la quatrième et dernière transformation de chaque round. C’est la seule opération de l’AES qui fait intervenir directement la clé de chiffrement.

Fondamental : C’est véritablement la seule transformation qui « chiffre » les données. Les autres (SubBytes, ShiftRows, MixColumns) ne font que mélanger et substituer les octets, mais sans la clé, elles sont parfaitement réversibles. La sécurité de l’AES repose donc sur la clé et sur sa gestion.

2. Principe

AddRoundKey réalise une addition (XOR) entre :

• Le bloc de données courant (état)
• La RoundKey courante (clé dérivée pour ce round)

Pour chaque octet de l’état, on effectue :

$$\text{État}_{\text{sortie}} = \text{État}_{\text{entrée}} \oplus \text{RoundKey}$$

Rappel : Dans $\mathbb{F}_{2^8}$, l’addition est l’opération XOR. L’élément neutre est $\text{0x00}$.

3. Détail de l’opération

Prenons un exemple sur un seul octet (un mot du bloc) :

En binaire :

RoundKey : 11101100
Mot      : 10011011
XOR      : 01110111

Soit en hexadécimal :
– 0xEC ⊕ 0x9B = 0x77

4. Visualisation sur le bloc complet

Sur l’ensemble du bloc de 16 octets (matrice $4 \times 4$), AddRoundKey s’applique octet par octet :

État_entrée          RoundKey             État_sortie
┌──────────────┐     ┌──────────────┐    ┌──────────────┐
│ a00 a01 a02 a03       │     │ k00 k01 k02 k03       │    │    b00 b01 b02 b03    │
│ a10 a11 a12 a13       │ ⊕ │ k10 k11 k12 k13       │ = │   b10 b11 b12 b13    │
│ a20 a21 a22 a23       │     │ k20 k21 k22 k23       │    │    b20 b21 b22 b23    │
│ a30 a31 a32 a33       │     │ k30 k31 k32 k33       │    │    b30 b31 b32 b33    │
└──────────────┘     └──────────────┘    └──────────────┘

avec :

$$b_{ij} = a_{ij} \oplus k_{ij}$$

5. Réversibilité

AddRoundKey est parfaitement réversible grâce aux propriétés de l’opération XOR.

Propriétés utilisées

1. Associativité : $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
2. Élément neutre : $a \oplus 0 = a$
3. Auto-inverse : $a \oplus a = 0$

Démonstration

Soit $M_i$ le mot courant, $K_i$ la RoundKey, et $C_i$ le résultat du chiffrement :

$$C_i = M_i \oplus K_i$$

Pour déchiffrer, on applique à nouveau la même RoundKey :

$$C_i \oplus K_i = (M_i \oplus K_i) \oplus K_i$$

Par associativité :

$$= M_i \oplus (K_i \oplus K_i)$$

Or $K_i \oplus K_i = 0$ (élément neutre), donc :

$$= M_i \oplus 0 = M_i$$

On retrouve bien le message original.

6. Schéma de la compensation

Chiffrement :          Déchiffrement :
                        
M_i                    C_i
  │                      │
  ⊕ K_i                  ⊕ K_i
  ↓                      ↓
C_i                     M_i

Exemple numérique avec l’octet précédent :

7. Rôle dans l’algorithme

AddRoundKey est appliquée :

• Au début : AddRoundKey initial (avec la clé principale)
  – **À la fin de chaque round** (sauf le dernier ?) : En réalité, dans la structure standard, AddRoundKey est appliquée à la fin de **chaque round**, y compris le dernier.

Rappel de l’ordre pour un round complet (sauf le premier et le dernier qui sont particuliers) :
1. SubBytes
2. ShiftRows
3. MixColumns (sauf au dernier round)
4. AddRoundKey

Important  : Le dernier round ne contient pas MixColumns, mais contient bien AddRoundKey.

8. Gestion des RoundKeys

Les RoundKeys sont dérivées de la clé principale via un processus appelé Key Expansion (ou routine d’expansion).

Pour AES-128 (clé de 128 bits) :

• Clé initiale : 128 bits = 4 mots de 32 bits
• 10 rounds → besoin de 11 RoundKeys (une initiale + une par round)
• Soit $11 \times 4 = 44$ mots de 32 bits

La Key Expansion sera détaillée dans la section suivante.

9. Implémentation Python

def add_round_key(etat, round_key):
    """
    Applique AddRoundKey sur l'état (liste de 16 octets)
    round_key est une liste de 16 octets
    """
    return [etat[i] ^ round_key[i] for i in range(16)]

# Exemple avec un seul octet
mot = 0x9B
round_key = 0xEC
resultat = mot ^ round_key
print(f"0x{mot:02X} ⊕ 0x{round_key:02X} = 0x{resultat:02X}")

# Exemple sur un bloc complet (simplifié)
etat = [0x9B, 0x88, 0x14, 0x2A] * 4  # bloc exemple
rk = [0xEC] * 16  # round_key factice
nouvel_etat = add_round_key(etat, rk)

10. Récapitulatif

11. Pourquoi AddRoundKey est cruciale

Sans AddRoundKey, l’AES ne serait qu’une permutation fixe des données (SubBytes, ShiftRows, MixColumns), parfaitement connue et donc totalement vulnérable. C’est l’ajout de la clé qui rend l’algorithme sûr.

La sécurité repose sur :

• La longueur de la clé (128, 192 ou 256 bits)
• La non-linéarité de SubBytes
• La diffusion de ShiftRows et MixColumns
• La complexité de la Key Expansion

12. Question de réflexion

Pourquoi l’opération XOR est-elle particulièrement adaptée pour ce type de chiffrement ? Quelles propriétés mathématiques la rendent indispensable ?

Éléments de réponse :

• Elle est rapide (une seule instruction processeur)
• Elle est parfaitement réversible
• Elle préserve l’entropie (pas de perte d’information)
• Elle est associative et commutative, ce qui simplifie l’implémentation

Pour aller plus loin

1. Cellule interactive : Visualiser l’effet de AddRoundKey sur un bloc.
2. Exercice : Vérifier que add_round_key(etat, rk) appliqué deux fois redonne l’état initial.
3. Mini-projet : Implémenter une version simplifiée de l’AES en combinant toutes les transformations vues jusqu’ici.

1. Introduction

Le Key Schedule (ou routine d’expansion de clé) est le processus qui génère l’ensemble des RoundKeys à partir de la clé principale.

Pourquoi ? Utiliser directement la même clé à chaque round serait dangereux : cela créerait des corrélations entre les rounds et faciliterait certaines attaques cryptanalytiques. L’expansion permet de :

• Disposer d’une clé différente par round
• Introduire de la non-linéarité dans la génération des clés
• Rendre l’attaque par related-key plus difficile

2. Généralités

Remarque : La clé initiale est utilisée comme première RoundKey (avant le premier round). On génère ensuite $N_r$ RoundKeys supplémentaires, où $N_r$ est le nombre de rounds.

3. Organisation des clés

Une clé de 128 bits est constituée de 16 octets. Pour faciliter le traitement, on les regroupe par mots de 4 octets (32 bits).

Soit une clé $K$ de 128 bits :

$$ K \iff b_0 b_1 \ldots b_{126} b_{127} \quad (b_i \in \{0,1\}) $$

On organise en octets $V_i$ (8 bits) :

$$ K \iff V_0 V_1 \ldots V_{14} V_{15} $$

Puis en mots $W_i$ (32 bits = 4 octets) :

$$ K \iff W_0 W_1 W_2 W_3 $$

avec :

• $W_0 = (V_0, V_1, V_2, V_3)$
• $W_1 = (V_4, V_5, V_6, V_7)$
• $W_2 = (V_8, V_9, V_{10}, V_{11})$
• $W_3 = (V_{12}, V_{13}, V_{14}, V_{15})$

4. Principe général de l’expansion

Pour AES-128, on doit générer $11 \times 4 = 44$ mots $W_0$ à $W_{43}$.

La relation de récurrence est :

$$ W_i = \begin{cases} W_{i-4} \oplus g(W_{i-1}) & \text{si } i \equiv 0 \pmod{4} \\ W_{i-4} \oplus W_{i-1} & \text{sinon} \end{cases} $$

Interprétation : Tous les 4 mots, on applique la fonction non linéaire $g()$ au mot précédent avant de l’ajouter.

5. La fonction $g()$

La fonction $g()$ s’applique sur un mot de 4 octets (32 bits) et se décompose en trois étapes :

Étape 1 : Rotation (RotWord)

Décalage circulaire vers la gauche d’un octet :

$$g_1(W) = \text{RotWord}(W) = (W_1, W_2, W_3, W_0)$$

Exemple avec $W = (V_{12}, V_{13}, V_{14}, V_{15})$ :

$$g_1(W) = (V_{13}, V_{14}, V_{15}, V_{12})$$

Étape 2 : Substitution (SubWord)

Application de la S-box (SubBytes) à chaque octet du mot :

$$g_2(W) = (\text{SubBytes}(V_{13}), \text{SubBytes}(V_{14}), \text{SubBytes}(V_{15}), \text{SubBytes}(V_{12}))$$

Étape 3 : Ajout de la constante de round (Rcon)

On ajoute (XOR) une constante de round uniquement au premier octet du mot :

$$g_3(W) = (V_{13}’ \oplus \text{Rcon}[j], V_{14}’, V_{15}’, V_{12}’)$$

où $\text{Rcon}[j]$ (Round Constant) est un octet dépendant du round $j$.

6. Les constantes de round (Rcon)

Les constantes $\text{Rcon}[j]$ sont définies dans $\mathbb{F}_{2^8}$ comme des puissances de $x$ (polynôme $x^1$) :

$$\text{Rcon}[j] = x^{j-1} \pmod{P}$$

où $P = x^8 + x^4 + x^3 + x + 1$ est le polynôme irréductible de l’AES.

Remarque : À partir de $j=9$, on dépasse $x^8$ et on réduit par le polynôme irréductible.

7. Schéma complet pour AES-128

Clé initiale (128 bits) = W₀ W₁ W₂ W₃
           │
           ↓
┌──────────────────────────────────────────────────────────┐
│ Pour j = 1 à 10 (rounds)                                 │
│                                                          │
│   ┌─────────────────────────────────────────────────┐   │
│   │ temp = g(W₄ⱼ₋₁)  avec g = RotWord → SubWord → XOR Rcon │
│   └─────────────────────────────────────────────────┘   │
│                         │                                │
│   W₄ⱼ   = W₄ⱼ₋₄ ⊕ temp                                   │
│   W₄ⱼ₊₁ = W₄ⱼ₋₃ ⊕ W₄ⱼ                                   │
│   W₄ⱼ₊₂ = W₄ⱼ₋₂ ⊕ W₄ⱼ₊₁                                 │
│   W₄ⱼ₊₃ = W₄ⱼ₋₁ ⊕ W₄ⱼ₊₂                                 │
│                                                          │
└──────────────────────────────────────────────────────────┘

Visualisation :

Round 0 (clé initiale) : [W₀] [W₁] [W₂] [W₃]
                           │    │    │    │
Round 1 : [W₄] ← g(W₃)     │    │    │    │
          [W₅] ← W₄ ⊕ W₁   ↓    ↓    ↓    ↓
          [W₆] ← W₅ ⊕ W₂
          [W₇] ← W₆ ⊕ W₃

Round 2 : [W₈]  ← g(W₇) ⊕ W₄
          [W₉]  ← W₈ ⊕ W₅
          [W₁₀] ← W₉ ⊕ W₆
          [W₁₁] ← W₁₀ ⊕ W₇

... et ainsi de suite jusqu'à W₄₃

8. Exemple concret (simplifié)

Prenons un exemple simplifié avec des valeurs fictives pour illustrer.

Soit la clé initiale (128 bits) découpée en 4 mots :

Pour le premier round $(j = 1)$ :

1. $temp = g(W₃)$ :
   • RotWord : (0xCF, 0x4F, 0x3C, 0x09)
   • SubWord : appliquer S-box à chaque octet
   • $Rcon[1] = 0x01$
   • $temp = (S(0xCF) ⊕ 0x01, S(0x4F), S(0x3C), S(0x09))$
2. $W₄ = W₀ ⊕ temp$
3. $W₅ = W₄ ⊕ W₁$
4. $W₆ = W₅ ⊕ W₂$
5. $W₇ = W₆ ⊕ W₃$

9. Cas particulier : clé de 192 bits

Pour AES-192, on part de 6 mots initiaux (192 bits = 6 × 32 bits). La récurrence devient :

$$ W_i = \begin{cases} W_{i-6} \oplus g(W_{i-1}) & \text{si } i \equiv 0 \pmod{6} \\ W_{i-6} \oplus W_{i-1} & \text{sinon} \end{cases} $$

On génère $13 \times 4 = 52$ mots (W₀ à W₅₁).

Particularité : La dernière itération ne nécessite que 4 mots supplémentaires (au lieu de 6).

10. Cas particulier : clé de 256 bits

Pour AES-256, on part de 8 mots initiaux (256 bits = 8 × 32 bits). La récurrence est :

$$ W_i = \begin{cases} W_{i-8} \oplus g(W_{i-1}) & \text{si } i \equiv 0 \pmod{8} \\ W_{i-8} \oplus W_{i-1} & \text{si } i \equiv 4 \pmod{8} \\ W_{i-8} \oplus W_{i-1} & \text{sinon} \end{cases} $$

Particularité : Tous les 4 mots (lorsque $i \equiv 4 \pmod{8}$), on applique également la S-box avant l’addition (sans rotation ni Rcon).

On génère $15 \times 4 = 60$ mots (W₀ à W₅₉).

11. Récapitulatif par taille de clé

12. Implémentation Python (AES-128)

def sub_word(mot):
    """Applique SubBytes sur un mot de 4 octets"""
    return [sbox[octet] for octet in mot]

def rot_word(mot):
    """Rotation circulaire vers la gauche d'un octet"""
    return mot[1:] + [mot[0]]

def rcon(j):
    """Retourne la constante de round pour le round j (1-indexé)"""
    rcon_table = [
        0x01, 0x02, 0x04, 0x08, 0x10,
        0x20, 0x40, 0x80, 0x1B, 0x36
    ]
    return rcon_table[j-1]

def key_expansion_128(cle_initiale):
    """
    Expansion de clé pour AES-128
    cle_initiale : liste de 16 octets
    Retourne une liste de 44 mots (4 octets chacun)
    """
    # Initialisation : 4 premiers mots
    mots = []
    for i in range(4):
        mots.append(cle_initiale[4*i:4*(i+1)])
    
    # Génération des 40 mots suivants
    for i in range(4, 44):
        temp = mots[i-1].copy()
        
        if i % 4 == 0:
            # Application de g() tous les 4 mots
            temp = rot_word(temp)
            temp = sub_word(temp)
            temp[0] ^= rcon(i // 4)
        
        # Ajout du mot i-4
        nouveau = [mots[i-4][j] ^ temp[j] for j in range(4)]
        mots.append(nouveau)
    
    return mots

def key_expansion_192(cle_initiale):
    """Expansion de clé pour AES-192 (similaire, avec modulo 6)"""
    # À implémenter
    pass

def key_expansion_256(cle_initiale):
    """Expansion de clé pour AES-256 (avec cas particulier i%8 == 4)"""
    # À implémenter
    pass

13. Réversibilité et déchiffrement

Pour le déchiffrement, on a besoin des RoundKeys dans l’ordre inverse (de la dernière à la première).

Deux approches possibles :

1. Précalcul : Générer toutes les RoundKeys au début du déchiffrement et les stocker.
2. Génération inversée : Calculer les clés à partir de la dernière (plus complexe, rarement utilisée).

En pratique, on précalcule toutes les RoundKeys à l’initialisation.

14. Pourquoi ne pas utiliser une seule grande clé ?

15. Récapitulatif final

Pour aller plus loin

1. Cellule interactive : Afficher l’évolution des mots lors de l’expansion.
2. Exercice : Implémenter la Key Expansion pour AES-128 et vérifier avec des vecteurs de test connus.
3. Visualisation : Représenter graphiquement les dépendances entre les mots.
4. Question de réflexion :
   Pourquoi utilise-t-on des constantes de round (Rcon) et pourquoi changent-elles à chaque round ?