Signature CFS avec Codes de Goppa
Introduction
Le schéma de signature CFS (Courtois, Finiasz, Sendrier) repose sur les codes correcteurs
d'erreurs, en particulier les codes de Goppa, pour garantir la sécurité. Ce document décrit le
processus en détail, avec des formules et des exemples.
1. Choix du Code de Goppa
Un code de Goppa est défini sur un corps fini GF(2^m) par :
- Un polynôme de Goppa g(x),
- Une séquence L = {α₁, α₂, ..., αₙ} d'éléments distincts dans GF(2^m).
Le code est noté [n, k, d], où n est la longueur, k la dimension, et d la distance minimale.
2. Génération des Clés
a. Clé privée
La clé privée comprend :
1. Le polynôme de Goppa g(x),
2. La séquence L,
3. Une permutation aléatoire P,
4. Une matrice de transformation S (non singulière).
b. Clé publique
La clé publique est calculée en obfusquant la matrice génératrice G :
G_pub = S · G · P,
où :
- G est la matrice génératrice du code de Goppa,
- S et P masquent la structure de G.
3. Signature d’un Message
Pour signer un message M :
1. Encodage : M est transformé en un vecteur de poids faible e par un hachage.
2. Décodage : On utilise un algorithme efficace pour trouver un mot code proche de e.
3. Transformation inverse : La signature est obtenue par l'inverse des transformations :
e' = S⁻¹ · e · P⁻¹.
4. Vérification
Le vérificateur utilise la clé publique G_pub pour vérifier si le vecteur signé est un mot code
valide correspondant au message M.
Exemple Illustratif
Supposons un code de Goppa défini sur GF(2³) avec :
- Polynôme g(x) = x³ + x + 1,
- Séquence L = {α₁, α₂, ..., α₆} dans GF(2³),
- n = 6, k = 3, d = 3.
La matrice génératrice G est donnée par :
G = [1 0 1 1 0 0;
0 1 1 0 1 0;
0 0 1 1 1 1].
Après application de S et P, on obtient :
G_pub = S · G · P.
