Corps fini = corps de Galois

"Un corps est un ensemble de numéros où on peut add. sous. mult. et
div."

En crypto souvent on s'intéresse à des ensembles finis.
En AES : 256 éléments

Théorème : FF exist seulement s'il y a p^m elt, p nombre premier >= 2, m entier positif
- Il y a un FF avec 11 éléments : GF(11)
- Il y a un FF avec 81 éléments : GF(81) = GF(3^4)
- Il y a un FF avec 256 éléments : GF(256) = GF(2^8)
- Il n'y a pas de FF avec 12 éléments car 12 = 3 × 2^2


                  GF(p^m)
                   /   \
                  /     \
                 /       \
       m = 1    /         \    m > 1
               /           \
              /             \
             /               \
            /                 \
         GF(p)             GF(p^m)
     Prime Field          Ext. Field
                    En crypto on s'intéresse
                          aux GF(2^m)

Arithmétique dans les corps premiers finis
==========================================
Les éléments de GF(p) sont les entiers dans l'ensemble {0,1,…,p-1}

Add. sous. mult. :
------------------

Soit a,b \in GF(p) = {0,1,…,p-1}
  a + b ≡ c mod p
  a - d ≡ d mod p
  a × b ≡ e mod p

À noter que toutes les cds sont satisfaites avec ces calculs
Ex : c = a + b \in GF(p)

Division : inversion :
----------------------

a \in GF(p) alors l'inverse doit satisfaire a × a^{-1} ≡ 1 mod p
On utilise l'algorithme d'euclide étendu

Corps étendu : GF(2^m)
======================

Les éléments du GF(2^m) sont des polynomes

a_{m-1} X^{m-1} + … + a_1 X + a_0 = A(X) \in GF(2^m)
a_i \in GF(2) = {0,1}

Ex : GF(2^3) = GF(8)
A(X) = a_2 * X^2 + a_1 * X + a_0 = (a2, a1, a0)
                                    0   0   0
                                    0   0   1
                                    0   1   0
                                    0   1   1
                                    1   0   0
                                    1   0   1
                                    1   1   0
                                    1   1   1

Gf(2^3) = {0,1,X,X+1,X^2,X^2+1,X^2+X,X^2+X+1}

Question : comment peut-on calculer en utilisant ces éléments

Add. & sous. dans GF(2^m) :
---------------------------

On va utilise add./sous. régulière des polynomes t.q. les coeff sont
dans GF(2) :

C(X) = A(X) + B(X) = \sum_{i=0}^{m-1} c_i X^i
    t.q. c_i ≡ a_i + b_i mod 2

C'(X) = A(X) - B(X) = \sum_{i=0}^{m-1} c'_i X^i
    t.q. c_i ≡ a_i - b_i mod 2
             ≡ a_i + b_i mod 2

C(X) = C'(X)

Exemple dans GF(2^3) :
----------------------

A(X) = X^2 + X + 1
B(X) = X^2 +     1

A + B = (1+1)X^2 + X + (1+1)
      = X

Mult. dans GF(2^m) :
--------------------

Intuitions : faire mult. dans polynômes régulière

Exemple dans GF(2^3) :

A × B = (X^2 + X + 1)(X^2 + 1)
      = X^4 + X^3 + X^2 + X^2 + X + 1
      = X^4 + X^3 + X + 1
      = C'(X) \not\in GF(2^3) => problème

Solution :

Réduire C'(X) modulo un polynôme qui "se comporte comme un nombre
premier". On l'appelle polynôme irréductible i.e. on ne peut pas le
factoriser.

Un polynôme irréductible de GF(2^3) :
P(X) = X^3 + X + 1

Dans AES, c'est un polynôme fixe, spécifié dans la norme :
P(X) = X^8 + X^4 + X^3 + X + 1

  X^4 + X^3 + X + 1 │ X^3 + X + 1
+                   ├─────────────
  X^4 + X^2 + X     │ X + 1
 ────────────────── │
  X^3 + X^2 + 1     │
+                   │
  X^3 + X + 1       │
 ────────────────── │
  X^2 + X           │

A×B mod P(X) = X^2 + X

Inversion dans GF(2^m)
----------------------

L'inverse A^{-1}(X) de A(X) \in GF(2^m) doit satisfaire :
A(X) × A^{-1}(X) ≡ 1 mod P(X)