Cryptographie basée sur les codes

Pour les étudiants de Master

en Informatique
Par

Hervé TALE KALACHI

15 novembre 2024
 Table des matières

Résumé 3

1 Théorie des codes correcteurs 4

1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Quelques Familles de Codes Linéaires . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Codes de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.2 Codes de Reed-Solomon généralisés . . . . . . . . . . . . . . . . . . . 16
1.3.3 Codes de Goppa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.4 Codes de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.5 Codes LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4 Travaux dirigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Cryptographie basée sur les codes 23

2.1 Décodage d’un code linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.2 Décodage par tableau standard . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.3 Décodage par ensemble d’information . . . . . . . . . . . . . . . . . . . . . 25
2.2 Cryptosystèmes de McEliece et de Niederreiter . . . . . . . . . . . . . . . . . . . . 27
2.3 Exemple : Attaque structurelle sur les codes GRS . . . . . . . . . . . . . . . . . . 31

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

 Table des figures

1.1 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Certains codes linéaires en blocs [Her11] . . . . . . . . . . . . . . . . . . . . . . . 12

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

 Résumé

Ce cours est une introduction à la cryptographie basée sur les codes correcteurs d’erreurs.
Nous rassemblerons des outils et des notions de la cryptographie, de la théorie des codes et nous
poursuivrons avec la cryptographie basée sur les codes. Un état de l’art du domaine sera présenté.
Plus précisément, il s’agira de la présentation du schéma de chiffrement de McEliece et quelques
commentaires sur ses variantes. De nouvelles attaques structurelles sur certaines variantes seront
présentées et, nous finirons par une présentation de quelques orientations/pistes de recherche dans
le domaine.
Mots Clés : Cryptographie, code de correcteur d’erreurs, chiffrement à clé publique, déchiffre-
ment, attaque structurelle, attaque sur le chiffré, encodage, décodage, Cryptosystème de McElièce.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

 Chapitre Un

Théorie des codes correcteurs

Introduction

Les codes correcteurs d’erreurs ont été développés dans la deuxième moitié du vingtième siècle,
suite aux travaux de Shannon en 1949. L’objectif est alors de pouvoir établir des communications
claires (sans parasites, sans brouillage). Plutôt que d’essayer sans cesse d’améliorer physiquement
les systèmes de transmission, Shannon a l’idée d’une autre approche : Faire subir au signal un
traitement informatique après sa réception afin de détecter et de corriger les erreurs de transmis-
sion.
On s’intéresse à la transmission des messages qui sont pour chacun transmis par une succession
de signaux. Chaque message peut s’écrire au moyen d’un n − uplet (x1 , ..., xn ) où les xi , i = 1, ..., n
appartiennent à un ensemble A appelé alphabet, dont tous les éléments représentent les différents
signaux utilisés. Chaque n-uplet ainsi obtenu s’appelle un mot. L’entier n s’appelle longueur du
mot et l’ensemble des mots ainsi formés s’appelle un code.
Dans le but d’avoir un code doté de structures algébriques et combinatoires particulières,
l’alphabet A peut être choisi convenablement. C’est ainsi que nous prendrons généralement pour
alphabet un corps fini Fq ; c’est-à-dire un corps à q éléments.

1.1 Généralités
Définition 1.1. Soit Fq un corps fini à q éléments. Soient k et n deux entiers naturels tels que
0 < k ⩽ n.
i) Fkq est l’ensemble des messages de longueur k sur l’alphabet Fq .
ii) Fnq est l’ensemble des messages codés de longueur n.
iii) Un encodeur est une application injective f : Fkq −→ Fnq .
iv) L’ensemble d’images de f est appelé code. Ainsi, un code sur Fq de longueur n est un
sous-ensemble C de Fnq .
v) Les éléments du code C sont appelé mot du code C.
vi) Un décodeur une fonction f : Fnq −→ Fkq tel que f ◦ g = id.

Exemple 1.2 (Codes de Répétition). Message : x = (x1 , x2 )

Message Encodé : c = f (x) = f (x1 , x2 ) = (x1 , x1 , x1 , x2 , x2 , x2 )

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.1 Généralités 5

Mot Reçu : y = (x1 , x1 , x1 , x2 , x1 , x2 )

Décodage : y = (x1 , x1 , x1 , x2 , x1 , x2 ) −→ x = (x1 , x2 )

i)
ii) Soit C un code de longueur n sur Fq . Soient x = (x1 , ..., xn ) et y = (y1 , ..., yn ) deux mots
de C. On appelle distance de Hamming entre x et y et on note dH (x, y) ou simplement d(x, y), le
nombre de positions sur lesquelles les deux mots diffèrent :

dH (x, y) = #{i ∈ {1, ..., n} /xi ̸= yi }.

Proposition 1.3. La distance de Hamming dH est bien une distance sur C.

Preuve. Soit x = (x1 , ..., xn ), y = (y1 , ..., yn ) et z = (z1 , ..., zn ) des mots de C.
— dH (x, y) = #{i ∈ {1, ..., n} /xi ̸= yi } ⩾ O.
— Supposons qu’on a dH (x, y) = 0.
dH (x, y) = 0 ⇔ ∀i ∈ [|1; n|] , xi = yi
⇔ x=y
— Par définition de dH il est clair que dH (x, y) = dH (y, x).
— Montrons en fin que dH (x, y) ⩽ dH (x, z) + dH (z, y).
Soient A = {i ∈ {1, ..., n} /xi ̸= yi }, B = {i ∈ {1, ..., n} /xi ̸= zi } et
D = {i ∈ {1, ..., n} /zi ̸= yi }.
On a dH (x, y) = card(A), dH (x, z) = card(B) et dH (z, y) = card(D).
Soit i ∈ {1, ..., n} tel que i ∈/ B ∪ D ; alors i ∈ / B et i ∈ / D. D’où xi = zi et zi = yi ; donc
xi = yi et ainsi i ∈/ A.
On peut donc dire qu’on a A ⊂ B ∪ D ;
d’où card(A) ⩽ card(B ∪ D) ⩽ card(B) + card(D).
Ainsi dH (x, y) ⩽ dH (x, z) + dH (z, y).

Problématique.
On a transmis un mot de code c ∈ C, mais des perturbations ont eu lieu lors de cette trans-
mission et le destinataire reçoit un mot y = c + e où e est appelé vecteur d’erreurs. Le but du
destinataire est de décoder y ; c’est-à-dire trouver e à partir de y de manière à retrouver le mot de
code initial c ou directement le message (figure 1.1). Dans la suite, dire qu’un mot reçu y = c + e
contient t erreurs signifiera que dH (e, 0) = t.

Définition 1.4. La distance minimale d d’un code C est la plus petite des distances non nulles
entre les mots de C.

d = min{dH (x, y) : x, y ∈ C, x ̸= y}

Sa capacité de correction théorique t est donnée par :

t = E( d−1
2
)

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 6

Figure 1.1 – Communication

Définition 1.5. (Poids de Hamming). Le poids de Hamming d’un mot x ∈ C est simplement sa
distance au mot nul. On le notera w(x) ou wH (x).

Théorème 1.6. (Unicité du décodage). Soit C un code de capacité de correction théorique t. Soit
x ∈ Fnq un mot quelconque. Alors, il existe au plus un mot de code c ∈ C tel que dH (x, c) ⩽ t.

Preuve. Soit x ∈ Fnq .

Supposons qu’il existe deux mots c1 et c2 de C tels que dH (x, c1 ) ⩽ t et dH (x, c2 ) ⩽ t.
Alors, on a dH (x, c1 ) + dH (x, c2 ) ⩽ 2t = d − 1;
d’où dH (c1 , c2 ) ⩽ dH (x, c1 ) + dH (x, c2 ) ⩽ d − 1 < d.
d étant la distance minimale, on en déduit que c1 = c2 .

Définition 1.7. Soient x et y deux mots de C. On dit que y est une permutation de x s’il existe
une permutation σ de {1, ..., n} tel que pour tout i ∈ {1, ..., n} , yi = xσ(i) .

Définition 1.8. Deux codes C et C ′ sont dits équivalents par permutation s’il existe une permu-
tation σ de {1, ..., n} telle que pour tout x ∈ C ′ , il existe y ∈ C tel que x est la permutation de y
par σ.

1.2 Codes linéaires

Soit Fq le corps fini à q éléments ; n et k deux entiers naturels non nuls.

Définition 1.9. (Code linéaire). Un code linéaire de longueur n et de dimension k sur l’alphabet
Fq est un sous espace vectoriel C de Fnq de dimension k sur Fq . Dans la suite, on dira simplement
[n, k] code sur Fq ou encore code [n, k] sur Fq .

Remarque 1.10. Lorsque l’alphabet A est un anneau, un code linéaire de longueur n sur A est
un sous-module de An .

Remarque 1.11. Soit C un [n, k] code sur Fq alors, C est isomorphe à Fkq . Ainsi, le nombre de
mots de C est q k .

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 7

Propriété 1.12. Si C est un code linéaire, alors l’ensemble des distances entre les mots de C est
l’ensemble des poids de Hamming de C.

Preuve. Soient x et y deux mots de C, alors x − y ∈ C. Or dH (x, y) = w(x − y); donc toute
distance est le poids d’un mot de C. De plus w(x) = dH (x, 0) ; donc tout poids est une distance
entre deux mots de C.

Remarque 1.13. La distance minimale d’un code linéaire C est le poids minimum des mots du
code. on le note d.
d = min{w(x) : x ∈ C, x ̸= 0}
= min{w(x − y) : x, y ∈ C, x ̸= y}
= min{dH (x, y) : x, y ∈ C, x ̸= y}

Désormais, un code linéaire sur Fq de longueur n, de dimension k et de distance minimale d

sera simplement appelé code [n, k, d] ou [n, k, d] code.

Matrice génératrice

Un code linéaire est entièrement déterminé par une base du sous espace vectoriel constitué par
le code.

Définition 1.14. Soit C un code [n, k] sur Fq . On appelle matrice génératrice de C, toute matrice
k × n dont les lignes constituent une base de C.

Remarque 1.15.
(i) Si C est un code [n, k] sur Fq , toute matrice génératrice de C est une matrice k × n sur Fq
de rang k.
(ii) Inversement, toute matrice k × n sur Fq et de rang k est une matrice génératrice d’un code
[n, k] sur Fq .
(iii) Un code [n, k] possède plusieurs matrices génératrices.
(iv) Les mots de C sont tous des combinaisons linéaires des lignes d’une matrice génératrice
de C.
 
1 0 0 0 1 1 1
 
0 1 0 0 0 1 1
Exemple 1.16. G =  0 0 1 0 1 0 1

 
0 0 0 1 1 1 0
Sur F2 , G est de rang 4 ; c’est donc la matrice génératrice d’un code [7, 4] sur F2 .

Définition 1.17. Soit C un code [n, k] de matrice génératrice G.

Un ensemble d’information de C est un sous ensemble I ⊂ {1, ..., n} de k éléments tels que la
sous matrice dont les colonnes sont celles d’indices i dans G (i ∈ I) soit de rang k.

Exemple 1.18. Soit C le code [7, 4] de l’exemple précédent.

Alors I = {1; 2; 3; 4} est un ensemble d’information de C.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 8

Propriété 1.19. Soit C un code [n, k] de matrice génératrice G. Alors,

(a) C est équivalent à un code de matrice génératrice [A, B] où A est une matrice inversible
k × k et B une matrice k × (n − k).
(b) Si S est une matrice inversible k × k alors SG est une matrice génératrice de C.

Preuve.
(a) On sait que G est de rang k ; donc on peut permuter les colonnes de G de façon à obtenir
une matrice G′ = [A, B] ; ou A est une matrice inversible k×k et B une matrice k×(n−k).
La matrice G′ ainsi obtenue est bien celle d’un code C ′ équivalent par permutation à C.
(b) Considérons les applications linéaires :
Φ : Fkq −→ C Ψ : Fkq −→ Fkq
et
u 7−→ uG u 7−→ uS
k
Φ est surjective et on a dim Fq = k = dim C ; donc Φ est un isomorphisme. Ψ est un
isomorphisme (car S est inversible). Donc Φ ◦ Ψ est un isomorphisme de Fkq sur C. D’où
 
Φ ◦ Ψ(Fkq ) = C. Or Φ ◦ Ψ(Fkq ) = uSG, u ∈ Fkq ; donc C = uSG, u ∈ Fkq .
Ainsi, les lignes de SG forment une famille génératrice de C, par conséquent une base
de C (car famille génératrice de k vecteurs dans l’espace vectoriel C de dimension k). SG
est donc une matrice génératrice de C.

Définition 1.20.
— Une matrice génératrice d’un code [n, k] est dite normalisée (ou canonique) si la matrice
formée par les k premières colonnes est la matrice unité d’ordre k.
— Un code [n, k] est dit systématique s’il possède une matrice génératrice sous forme norma-
lisée.

Exemple 1.21. Le code linéaire de l’exemple précédent est un code systématique.

Propriété 1.22. Tout code linéaire est équivalent à un code systématique.

Preuve. Soit C un code [n, k].

Par la propriété 1.1.2 (a), C est équivalent à un code C ′ de matrice génératrice
G = [A, B] ; où A est une matrice inversible k × k. Soit A−1 l’inverse de A. Par la
propriété 1.1.2 .b), A−1 G = I k , A−1 B est une matrice génératrice de C ′ sous forme normalisée.
 

Donc C ′ est un code systématique.

Matrice de contrôle

Définition 1.23. Soient x = (x1 , ..., xn ) et y = (y1 , ..., yn ) deux éléments de Fnq .
Pn
— On appelle produit scalaire de x par y noté x · y la quantité x · y = xi · y i .
i=1
— x est orthogonal à y si et seulement si x · y = 0.

Définition 1.24. Soit C un code [n, k] sur Fq . On appelle orthogonal (ou dual) de C et on note
C ⊥ , le sous-espace vectoriel orthogonal à C; c’est-à-dire :

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 9

C ⊥ = y ∈ Fnq | x · y = 0, ∀x ∈ C


Propriété 1.25. Soit C un code [n, k] de matrice génératrice G.

(i) C ⊥ = y ∈ Fnq | yGt = 0 ; où Gt est la transposée de G.


(ii) C ⊥ est un code [n, n − k].

⊥
(iii) C ⊥ = C.
 
e1
.
 
  t t t
Preuve. Supposons G =   .  ; avec (e1 , ..., ek ), une base de C. G = (e1 ...ek ).

.
 

ek
n t
(i) Soit y ∈ Fq tel que yG = 0. Alors, y est orthogonal aux vecteurs e1 , ..., ek ; donc orthogonal
à toute combinaison linéaire de ces vecteurs ; c’est-à-dire à tout mot de C. Réciproquement,
si y ∈ C ⊥ , y est en particulier orthogonal aux vecteurs e1 , e2 , ..., ek ; donc yGt = 0. Ainsi,
C ⊥ = y ∈ Fnq | yGt = 0 .


(ii) Il est évident que C ⊥ est un sous-espace vectoriel de Fnq .

φ : Fnq −→ Fnq
Soit . φ est linéaire et C ⊥ = kerφ;
y 7−→ yGt
G est de rang k ; donc dim(Imφ) = k. Mais dim(ker φ) + dim(Imφ) = n ;
d’où dim(kerφ) = n − dim(Imφ) = n − k ; donc dim C ⊥ = n − k.
⊥
(iii) Il suffit de remarquer que dim((C ⊥ )⊥ ) = dim C =k et que C ⊆ C ⊥ .

Définition 1.26. On appelle matrice de contrôle (ou de parité) d’un [n, k] code C, toute matrice
génératrice de son orthogonal.

Définition 1.27. (Syndrome). Soit H une matrice de contrôle d’un code linéaire C. On appelle
syndrome de x ∈ Fnq l’élément s = H · xt ; xt étant la transposée de x.

Proposition 1.28. Soit H une matrice de contrôle d’un code linéaire C.

(x ∈ C) si et seulement si (H · xt = 0)

Preuve. H étant une matrice de contrôle de C, H est par définition une matrice génératrice
⊥
de C ⊥ . Mais nous avons vu à la propriété précédente que C ⊥ = C; donc x ∈ C si et seulement si
⊥
x ∈ C ⊥ ; c’est-à-dire xH t = 0 et H · xt = 0.

Proposition 1.29. Soit C un code [n, k] de matrice génératrice G ;

H une matrice (n − k) × n de rang n − k.
H est une matrice de contrôle de C si et seulement si H · Gt = 0.

Preuve. Soit H une matrice de contrôle de C.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 10

   
e1 e1 H t
.  . 
   
  t
  t
Supposons G =   .  ; alors, G · H =  .  = 0 ; car ei H = 0 pour i = 1, ..., k.
  
.  . 
   

ek ek H t
Donc H · Gt = (G · H t )t = 0.
Réciproquement, supposons que H · Gt = 0; il va de soi que G · H t = 0. Donc pour tout i ∈
{1, ..., k} , ei H t = 0; d’où x·H t = 0 et H ·xt = 0 pour tout x ∈ C. Soit C ′ = x · H, x ∈ Fn−k

q
(dim C ′ = n − k; car H est de rang n − k). On a alors C ⊆ (C ′ )⊥ et dim C = k = dim(C ′ )⊥ ; donc
⊥
C = (C ′ )⊥ ; d’où C ′ = (C ′ )⊥ = C ⊥ . Ainsi, H est une matrice de contrôle de C.
 
1 0 0 1 0
Exemple 1.30. Sur F2 , considérer le code C de matrice génératrice G = 0 1 0 1 1 et la
 

0 0 1 0 1
!
1 1 0 1 0
matrice H = . On a H · Gt = 0; donc H est une matrice de contrôle de C.
0 1 1 0 1

Proposition 1.31. Si H est une matrice de parité d’un code C de longueur n, on a :

C a pour distance minimale d si et seulement si tout système de d−1 colonnes de H est linéairement
indépendant.

Preuve. x ∈ C ⇐⇒ H · xt = 0
Donc C possède un mot de poids w si et seulement si on peut trouver w colonnes de H
linéairement dépendantes. Ainsi, C est de distance minimale d si et seulement si tout système de
d − 1 colonnes de H est linéairement indépendant.

Théorème 1.32. (Borne de singleton). Soit C un code linéaire [n, k, d] sur Fq . Alors C vérifie
l’inégalité de Singleton :

d⩽n−k+1

Preuve. Soit H = (U1 , U2 , ..., Un ) une matrice de contrôle de C ; avec Ui ∈ Fqn−k pour i =
1, ..., n. Supposons d − 1 > n − k.
H étant de rang n − k, les vecteurs U1 , U2 , ..., Ud−1 sont liés ; ce qui contredit le fait que d soit
la distance minimale.

Remarque 1.33. Ce théorème nous permet d’avoir une idée sur la valeur de la distance minimale
d’un code [n, k, d]. Plus d se rapproche de n − k + 1, plus le code est optimal ; c’est-à-dire peut
corriger un plus grand nombre d’erreurs.

Définition 1.34. (Maximum Distance Séparable). Soit C un code [n, k, d]. Le code C est dit
maximum distance séparable (MDS) s’il atteint la borne de Singleton ; c’est-à-dire si :

d=n−k+1

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.2 Codes linéaires 11

Proposition 1.35. Si C est un [n, k, d] code MDS de matrice de contrôle H, alors tout système
de n − k colonnes de H est linéairement indépendant.

Preuve. Si C est MDS, alors d − 1 = n − k. Donc tout système de n − k colonnes de H est

linéairement indépendant.

Proposition 1.36. C est un [n, k, d] code MDS si et seulement si C ⊥ est un [n, n − k, d′ ] code
MDS.

Preuve. Soit G la matrice génératrice de C et H sa matrice de contrôle. Comme C est MDS,

tout système de n − k colonnes de H est libre. Soit x ∈ C ⊥ un mot non nul. Supposons que
w(x) < k + 1. Alors x possède au moins n − k composantes nulles. Ainsi, les n − k colonnes de H
de mêmes indices que les composantes nulles de x sont liées ; ce qui est absurde. Donc w(x) ⩾ k+1,
c’est-à-dire d′ ⩾ k + 1; et par la borne de singleton, on a d′ = k + 1. L’équivalence vient du fait
que (C ⊥ )⊥ = C.

Corollaire 1.37. Soit C un code [n, k, d] de matrice génératrice G. Alors, C est MDS si et seule-
ment si tout système de k colonnes de G est libre.

L’optimalité d’un code est un paramètre important de son efficacité en terme de décodage,
mais ce n’est pas le seul. Une distance minimale élevée garantit que le code permet théoriquement
de corriger beaucoup d’erreurs mais pas que cette correction est algorithmiquement possible. La
vitesse des algorithmes de décodage est une autre qualité fondamentale du code.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 12

1.3 Quelques Familles de Codes Linéaires

Figure 1.2 – Certains codes linéaires en blocs [Her11]

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 13

1.3.1 Codes de Reed-Solomon

Encodage

Définition 1.38. Soit k et n deux entiers tels que 1 ⩽ k ⩽ n ; a = (a1 , ..., an ) tel que ai ∈ Fq et
les ai deux à deux distincts avec n < q.
On appelle code de Reed-Solomon de longueur n et de dimension k l’ensemble :

RSk (a) = {(f (a1 ), ..., f (an )) / f ∈ Fq [X] , deg(f ) < k}

a est appelé le support de RSk (a).

Proposition 1.39. .
(i) RSk (a) est un code lineaire de longueure n et de dimension k.
(ii) Une matrice génératrice de RSk (a) est :
 
1 1 . . . . 1
 
 a1 a2 . . . . an 
 
 a2 a22 . . . . a2n 
 1 
G= . . . 
 
 
 . . . 
 
 . . . 
 
k−1 k−1
a1 a2 . . . . ak−1
n

(iii) RSk (a) est un code MDS.

Preuve. Soit c = (c1 , ...., cn ) ∈ RSk (a). Alors, il existe f ∈ Fq [X] tel que ci = f (ai ).
Supposons f (X) = m0 + m1 X + .... + mk−1 X k−1 ; mi ∈ Fq .
On a :

c = (f (a1 ), f (a2 )..., f (an ))

= (m0 + m1 a1 + .... + mk−1 a1k−1 , m0 + a1 a2 + .... + mk−1 ak−1 k−1
2 , ...., a0 + m1 an + .... + mk−1 an )
 
1 1 . . . . 1
 
 a1 a2 . . . . a n 
 
 a2 a 2
. . . . a 2 
 1 2 n 
= (m0 , m1 , ...., mk−1 )  . . . 
 
 
 . . . 
 
 . . . 
 
ak−1
1 ak−1
2 . . . . ak−1 n
= (m0 , m1 , ...., mk−1 )G

Ainsi, les lignes de la matrice G génèrent RSk (a). D’après le déterminant de Vandermonde,
les lignes de G sont linéairement indépendantes. Ainsi RSk (a) est un code linéaire de longueur n,
de dimension k, et de matrice génératrice G.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 14

Comme deg(f ) < k, f a au plus k − 1 racines ; d’où n − wH (c) ⩽ k − 1 (où wH (c) est le poids
de Hamming de c). Ceci étant vrai pour tout c ∈ RSk (a), on a donc d ⩾ n − k + 1. Mais la borne
de singleton nous donne déjà d ⩽ n − k + 1; donc d = n − k + 1.

Décodage

Plusieurs algorithmes polynomiaux permettent de décoder efficacement n−k2

erreurs dans un
code de Reed-Solomon. Celui de Berlekamp-Massey est le plus connu, mais nous allons expliciter
ici l’algorithme de Berlekamp-Welch.
On suppose que l’on a reçu un mot y = c + e où e est une erreur de poids w et c un mot de
code, évaluation d’un polynôme Pc de degré < k.
On appelle polynôme localisateur de e le polynôme unitaire Le (de degré minimal), qui
s’annule en tous les éléments du support où e est non nul. Le degré de Le est donc inférieur ou
égal à w. Puisque e n’est pas connu, ce polynôme est aussi inconnu et on a :

∀i ∈ [|1; n|] yi × Le (ai ) = (Pc (ai ) + ei ) × Le (ai ) = Pc (ai ) × Le (ai ). (1-1)

Le polynôme Pc de degré < k est, lui aussi, inconnu (c’est ce que l’on cherche à trouver), et
on linéarise le système en introduisant le polynôme N = Pc × Le qui est donc de degré au plus
k − 1 + w. On obtient alors le système linéaire suivant :

∀i ∈ [|1; n|] c′i × Le (ai ) = N (ai ). (1-2)

Il est composé de n équations en k + 2w inconnues (w inconnues pour Le qui est unitaire de

degré au plus w et k + w pour N ). De plus, toute solution du système 1-1 donne aussi une solution
pour ce système. Il suffit donc qu’il y ait un nombre fini de solutions à 1-2 pour pouvoir retrouver
une solution. Ce sera le cas si n ⩾ k + 2w et donc si w ⩽ n−k 2
. On peut donc facilement corriger
d−1 n−k
jusqu’à t = 2 = 2 erreurs.
Exemple 1.40. Sur F5 = {0, 1, 2, 3, 4} , considérer le [4, 2, 3] code R2 (L) avec
L = (1, 2, 4, 3). Soit f (x) = 3x + 2. Le mot associé à f est c = (0, 3, 4, 1). Supposons que le mot c
soit transmis et que le récepteur reçoit y = c + e, avec e = (0, 0, 1, 0) ; on a y = (0, 3, 0, 1). Nous
allons décoder y. On a :
∀i ∈ [|1; 4|] yi ×Le (ai ) = N (ai ). De plus deg(N ) = 2 et deg(Le ) = 1; d’où N (x) = ax2 +bx+c
et Le (x) = x + d. On a alors le système suivant :



 a+b+c=0

 4a + 2b + c = 3(2 + d)
.


 a + 4b + c = 0

 4a + 3b + c = 3 + d



 a+b+c=0

 4a + 2b + c − 3d = 1
D’où .


 a + 4b + c = 0
 4a + 3b + c − d = 3


Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 15

Ce qui nous permet d’obtenir après résolution a = 3, b = 0, c = 2 et d = 1.

Donc N (x) = 3x2 + 2 = f (x)(x + 1). Par une division Euclidienne, on a f (x) = 3x + 2.

# On peut utiliser SageMath pour resoudre les systemes lineairs AX = Y .

A = Matrix ( GF (5) , [[1 ,1 ,1 ,0] ,[4 ,2 ,1 , -3] ,[1 ,4 ,1 ,0] ,[4 ,3 ,1 , -1]])
Y = vector ([0 ,1 ,0 ,3])
X = A . solve_right ( Y )
print ( ’X = ’ ,X )
"""
X = (3 , 0 , 2 , 1)
"""
# Les codes de Reed Solomon sont implementes dans SageMath .
F = GF (5)
Fx . <x > = F [] # Espace des polynomes
n , k =4 , 2 # Paremetres du codes
a = [ F (1) , F (2) , F (4) , F (3)] # Support
C = codes . Gen e ra li ze d Re ed So l om on Co d e (a , k ) # Code de Reed Salomon .
E = C . encoder ( " EvaluationPolynomial " )
G = C . generator_matrix () # Matrice generatrice
p = 2+3* x # Polynome representatif du message m =(2 ,3).
c = E . encode ( p ) # Encodeage du message .
e = vector (F , [0 , 0 , 1 , 0]) # L ’ erreur
y = c + e # Mot recu
D = codes . decoders . GRSB erle kampWel chDe code r ( C ) # Algorithme de decodage
v = D . decode_to_code ( y ) # Decodage du mot recu .
print ( ’ Support : ␣ a = ’ ,a )
print ( ’ Matrice ␣ generatice : ␣ G = ’)
print ( G )
print ( ’ Encodeage ␣ du ␣ message : ␣ c = ’ ,c )
print ( ’ Mot ␣ recu : ␣ y = ’ ,y )
print ( ’ Decodage ␣ du ␣ mot ␣ recu : ␣ v = ’ ,v )
"""
Support : a = [1 , 2 , 4 , 3]
Matrice generatice : G =
[1 1 1 1]
[1 2 4 3]
Encodeage du message : c = (0 , 3 , 4 , 1)
Mot recu : y = (0 , 3 , 0 , 1)
Decodage du mot recu : v = (0 , 3 , 4 , 1)
"""

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 16

1.3.2 Codes de Reed-Solomon généralisés

Soit a = (a1 , ..., an ), où les ai sont des éléments distincts de Fq , et soit b = (b1 , ..., bn ) où les bi
sont des éléments non-nuls (mais non nécessairement distincts) de Fq .

Définition 1.41. Le code de Reed-Solomon Généralisé sur Fq , de longueur n et de dimension k,

noté GRSk (a, b), est l’ensemble :
GRSk (a, b) = {((b1 f (a1 ), ..., bn f (an )) / f ∈ Fq [X] , deg(f ) < k}

Proposition 1.42. .
(i) GRSk (a, b) est un code linéaire de longueur n, de dimension k.
(ii) Une matrice génératrice de GRSk (a, b) est
 
b1 b2 . . . . bn
 
 b 1 a1 b 2 a2 . . . . b n an 
 
 b 1 a2 b2 a22 . . . . bn a2n 
 1 
G =  . . . 
 
 
 . . . 
 
 . . . 
 
k−1
b 1 a1 b2 ak−1
2 . . . . bn ak−1
n

  
1 1 . . . . 1 b1 0
  
 a1 a2 . . . . an   b2 
  
 a2 a22 . . . . 2 
an   
 1 
=  . . . 
  

  
 . . .   
  
 . . . 
  

k−1 k−1
a1 a2 . . . . ak−1
n 0 bn

(iii) GRSk (a, b) est MDS.

(iv) L’orthogonal de GRSk (a, b) est GRSn−k (a, w), c’est-à-dire, GRSk (a, b)⊥ = GRSn−k (a, w),
où les composantes de w = (w1 , ..., wn ) sont :
1
wi = bi F ′ (ai )
(1 ⩽ i ⩽ n),
n
Q
avec F (x) = (x − ai ).
i=1

Remarque 1.43. Le principe du décodage des codes de Reed-Solomon généralisés est le même que
celui des codes de Reed-Solomon. En effet, si le mot reçut est y = mG′ + e (avec G′ = GS ; où
G est une matrice génératrice de RSk (a) et S une matrice diagonale inversible n × n . On calcule
alors yS −1 = (mG′ + e)S −1 = mG + eS −1 . Retrouver m revient alors à décoder un mot du code
de Reed-Solomon RSk (a).

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 17

# Les codes de Reed Solomon generalise sont implementes dans SageMath .

F = GF (5)
Fx . <x > = F [] # Espace des polynomes
n , k =4 , 2 # Paremetres du codes
a = [ F (1) , F (2) , F (4) , F (3)] # Support pour evaluation
b =[ F (1) , F (1) , F (2) , F (3)] # Support pour multiplication
C = codes . Gen e ra li ze d Re ed So l om on Co d e (a ,k , b ) # Code de Reed Salomon generalise .
E = C . encoder ( " EvaluationPolynomial " )
G = C . generator_matrix () # Matrice generatrice
Cd = C . dual_code () # Code dual du code C
H = Cd . generator_matrix () # Matrice de controle
v = Cd . evaluation_points () # Support pour evaluation de dual
w = Cd . column_multipliers () # Support pour multiplication de dual
p = 2+3* x # Polynome representatif du message m =(2 ,3).
c = E . encode ( p ) # Encodeage du message .
e = vector (F , [0 , 0 , 1 , 0]) # L ’ erreur
y = c + e # Mot recu
D = codes . decoders . GRSB erle kampWel chDe code r ( C ) # Algorithme de decodage
z = D . decode_to_code ( y ) # Decodage du mot recu .
print ( ’ Matrice ␣ generatice : ␣ G = ’)
print ( G )
print ( ’ Matrice ␣ controle : ␣ H = ’)
print ( H )
print ( ’ Support ␣ pour ␣ evaluation ␣ du ␣ dual ␣ : ␣ v = ’ ,v )
print ( ’ Support ␣ pour ␣ multiplication ␣ du ␣ dual ␣ w = ’ ,w )
print ( ’ Encodeage ␣ du ␣ message : ␣ c = ’ ,c )
print ( ’ Mot ␣ recu : ␣ y = ’ ,y )
print ( ’ Decodage ␣ du ␣ mot ␣ recu : ␣ z = ’ ,z )

"""
Matrice generatice : G =
[1 1 2 3]
[1 2 3 4]
Matrice controle : H =
[4 3 3 4]
[4 1 2 2]
Support pour evaluation du dual : v = (1 , 2 , 4 , 3)
Support pour multiplication du dual w = (4 , 3 , 3 , 4)
Encodeage du message : c = (0 , 3 , 3 , 3)
Mot recu : y = (0 , 3 , 4 , 3)
Decodage du mot recu : z = (0 , 3 , 3 , 3)
"""

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 18

1.3.3 Codes de Goppa

Soit a = (a1 , ..., an ), où les ai sont des éléments distincts de Fqm . Soit g un polynôme de Fqm [X]
de degré r tel que g(ai ) ̸= 0 pour tout i ∈ {1, . . . , n}.

Définition 1.44. Le code de Goppa de support a et de polynôme de Goppa g est le code noté
Γ(a, g) et défini par :
( n
)
X ci
Γ(a, g) = (c1 , . . . , cn ) ∈ Fnq : ≡ 0 mod g(X) .
i=1
X − ai

Proposition 1.45. .
(i) Γ(a, g) est un code alternant c’est-à-dit que Γ(a, g) est un sous-code sur un sous-corps Fq d’un
code de Reed Salomon généralisé sur Fqm . Plus précisement,

Γ(a, g) = Fnq ∩ GRSr (a, b)⊥

où b = (b1 , ..., bn ) est défini par bi = 1/g(ai ) pour tout i ∈ {1, . . . , n}.
(ii) Γ(a, g) est un code Fq -linéaire de longueur n de dimension k ⩾ n − m(n − r) et de distance
minimal d ⩾ r + 1.
(iii) Quand q = 2 et g n’a pas de racine multiple, alors Γ(a, g)=Γ(a, g) la distance minimal
d ⩾ 2r + 1.

Un algorithme pour décoder les codes Goppa est l’algorithme de Patterson ; ; ; ;

# Les code de Goppa sont inmplemente dans Sagemath
q =2
m =3
r =2
F . <s >= GF ( q ^ m )
R . <x > = F []
g = x ^2 + x +1
a =[0 ,1 , s , s ^2 , s ^3 , s ^4 , s ^5 , s ^6]
C = codes . GoppaCode (g , a )
n = C . length ()
k = C . dimension ()
d = C . minimum_distance ()
G = C . generator_matrix ()
H = C . parity_check_matrix ()
print ( ’C = ’ ,C )
print ( ’ Support ␣ a = ’ , a )
print ( ’ Polynome ␣ de ␣ Goppa : ␣ g = ’ ,g )
print ( ’ Longueur : ␣ n = ’ ,n )
print ( ’ Dimension : ␣ k = ’ ,k )
print ( ’ Distance ␣ minimal : ␣ d = ’ ,d )

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 19

print ( ’ Matrice ␣ generatice : ␣ G = ’)

print ( G )
print ( ’ Matrice ␣ de ␣ controle : H = ’)
print ( H )
"""
C = [8 , 2] Goppa code over GF (2)
Support a = [0 , 1 , s , s ^2 , s + 1 , s ^2 + s , s ^2 + s + 1 , s ^2 + 1]
Polynome de Goppa : g = x ^2 + x + 1
Longueur : n = 8
Dimension : k = 2
Distance minimal : d = 5
Matrice generatice : G =
[1 1 0 0 1 0 1 1]
[0 0 1 1 1 1 1 1]
Matrice de controle : H =
[1 1 0 0 0 0 0 0]
[0 0 0 1 0 1 1 1]
[0 0 1 1 1 0 0 1]
[0 1 1 1 1 1 1 1]
[0 0 1 0 1 1 0 1]
[0 0 0 1 1 1 1 0]
"""

1.3.4 Codes de Hamming

Encodage

Pour définir les codes de Hamming, nous utilisons l’espace projectif. Rappelons que la relation
binaire ∼ sur Fmq \{(0, . . . , 0)} définie par x ∼ y ⇐⇒ existe λ ∈ Fq \{0}, x = λy est une relation
d’équivalence. L’ensemble quotient de Fm q \{(0, . . . , 0)} par la relation d’équivalence ∼ est appelé
l’espace projectif associé à Fq que nous notons P (Fm
m
q ). Ainsi un système complet de représentatif
de P (Fm m
q ) un ensemble maximal d’éléments de Fq dont aucun élément n’est multiple d’un autre .

Définition 1.46. Les codes de Hamming C(m, q) sur le corps fini Fq sont les codes linéaires
pour lesquels une matrice de contrôle est formée par les colonnes représentant les différents points
de l’espace projectif P (Fm
q ), c’est-à-dire que les colonnes de la matrice de contrôle de C(m, q) sont
formées à partir des vecteurs de Fm q qui sont deux à deux linéairement indépendants.

Exemple 1.47. .
1. Un ensemble de représentants des points projectifs de P (F23 ), est (1, 0), (0, 1), (1, 1), (1, 2).
Par conséquent, une matrice de contrôle du code de Hamming pour m = 2 et q = 3 est
!
1 0 1 1
H= .
0 1 1 2

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.3 Quelques Familles de Codes Linéaires 20

2. Dans le cas binaire, un système complet de représentations des points projectifs de P (Fm 2 )
m
est l’ensemble F2 \{(0, . . . , 0)}. Par conséquent, la matrice de contrôle du code de Hamming
pour m = 3 et q = 2 est
 
0 0 0 1 1 1 1
H =  0 1 1 0 0 1 1 .
 

1 0 1 0 1 0 1

Proposition 1.48. .
q m −1 q m −1
(i) Le code de Hamming C(m, q) est un code linéaire de longueur q−1
de dimension q−1
−m
et distance minimale 3.
(ii) Le code de Hamming est un code parfait.

Preuve._ _ _ _ _

Décodage

Soit C un code de Hamming de longueur n et H sa matrice de contrôle.

Soit hj le j-ème vecteur colonne de H, pour j ∈ {1, . . . , n}.
Puisque la distance minimale de C est de 3, alors C peut détecter et corriger une erreur.
Soit y un mot reçu de C tel que le nombre d’erreurs survenues lors de la transmission soit de
1.
Soit e = (ej )1⩽j⩽n le vecteur d’erreur et j0 la position dans le vecteur d’erreur e où l’erreur
s’est produite, que c’est-à-dire ej = 0 si j ̸= j0 . Alors, Hy T = HeT = ej0 hj0 .
Ainsi pour décoder y :
1) On calcule h = Hy T ;
2) On recherche une colonne hj0 de H et un scalaire λ tel que h = λhj0 . On obtient alors la
position j0 où l’erreur s’est produite ainsi que la valeur λ de l’erreur.
3) On calcule le mot transmis qui est c = y − e, où e est l’erreur définie par e = (ej )1⩽j⩽n avec
ej0 = λ et ej = 0 si j ̸= j0 .

Exemple 1.49. Soit le code de Hamming sur F3 dont une matrice de contrôle est
!
1 0 1 1
H= .
0 1 1 2

On suppose que le mot reçu est y = (0, 0, 1, 1) et qu’il y eut une seule erreur lors de la
transmission. Pour décoder y :  
! 0  ! !
1 0 1 1  0  2 1
1) On calcule h = Hy T =  = =2 = 2h1 ;
0 1 1 2   1 
 0 0
1
2) Comme h = 2h1 alors l’erreur s’est produite à la première position et sa valeur est 2.
3) Le mot transmis est donc c = y − e = (0, 0, 1, 1) − (2, 0, 0, 0) = (1, 0, 1, 1).

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.4 Travaux dirigés 21

# Les codes de Hamming sont implementes dans SageMath .

C = codes . HammingCode ( GF (3) , 2) # Code de Hamming pour q =3 et m =2.
H = C . parity_check_matrix () # Matric de controle .
y = vector ( GF (3) , (0 , 0 , 1 , 1)) # Mot recu .
c = C . decode_to_code (y , " Syndrome " ) # Decodage du mot recu .
print ( ’ la ␣ matrice ␣ de ␣ controle ␣ est ␣ H = ’)
print ( H )
print ( ’ le ␣ mot ␣ transmis ␣ est ␣ c = ’)
print ( c )
"""
la matrice de controle est H =
[1 0 1 1]
[0 1 1 2]
le mot transmis est c =
(1 , 0 , 1 , 1)
"""

1.3.5 Codes LDPC

___

1.4 Travaux dirigés

Exercise 1
1. Let C be a linaer code with a parity check matrix H and the minimum distance d.

(a) Show that if r columns of H are linearly dependent, then d ⩽ r.

(b) Show that if every r columns of H are linearly independent, then r < d.

2. Let C be a linear code over F3 with a parity check matrix ;

!
1 2 1 0
1 1 0 1

(a) Find the minimum distance of C.

(b) Find a generator matrix of C.
 
(c) A received word from the code C is y = 2 0 0 2 . Assuming that the number of
errors which occurred during transmission is less than or equal to the error correction
capacity. Find the transmitted codeword and the transmitted message.

Exercise 2 (Cyclic Codes)

Let C be a linear code over Fq of length n.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

1.4 Travaux dirigés 22

C is a cyclic code if for every (c1 , . . . , cn−1 , cn ) in C, the word (cn , c1 , . . . , cn−1 ) is in C.
Let (X n − 1) be the ideal of Fq [X] generated by X n − 1 and Fq [X] / (X n − 1) the quotient
ring.
Let the map Ψ : Fnq −→ Fq [X] / (X n − 1) defined by Ψ ((c1 , c2 , . . . , cn )) = c1 + c2 X + · · · +
cn X n−1 .
If c = (c1 , c2 , . . . , cn ) is in Fnq , then Ψ ((c1 , c2 , . . . , cn )) is denoted by c (X), that is,
c (X) = c1 + c2 X + · · · + cn X n−1 .
1. Prove that C is a cyclic code if and only if Ψ (C) is an ideal of Fq [X] / (X n − 1).
2. Prove that if C is a cyclic code then the ideal Ψ (C) is generated by the unique monic
polynomial g (X). This polynomial is called the generator polynomial of C.
3. Give the dimension and a generator matrix of a cyclic code.
4. Show that if C is a cyclic code then the dual C ⊥ is also a cyclic code and specify the generator
polynomial of C ⊥ .
5. Let C = {(x1 , x2 , −x1 − x2 ) , x1 ∈ Fq , x2 ∈ Fq }.

(a) Show that C is a cyclic code.

(b) Give a generator matrix and the generator polynomial of C and C ⊥ .

Exercise 3 (Decodage des code de Goppa)

___

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

 Chapitre Deux

Cryptographie basée sur les codes

Outre la factorisation entière, un autre problème aussi utilisé en cryptographie est le décodage
d’un code correcteur aléatoire.
Nous avons vu au chapitre précédent que le décodage d’un code aléatoire (c’est-à-dire un code
dont on ne connaît pas la structure) est un problème algorithmique difficile. Pour mettre au point
un système cryptographique, il faut un problème algorithmique difficile. McEliece a présenté en
1978, dans [McE78], l’idée d’utiliser le décodage comme problème difficile sous-jacent à un système
cryptographique. Quelque années plus tard, en 1986, Niederreiter proposa, apparemment sans
connaître les travaux de McEliece, un autre cryptosystème à base de codes.

2.1 Décodage d’un code linéaire

Ce qui nous intéresse ici, c’est la possibilité ou non de mettre en place des algorithmes de
décodage d’un code linéaire, et la complexité de tels algorithmes. Nous allons étudier ceci dans
les paragraphes qui suivent. On considère ici C, un code [n, k, d] sur Fq (connu par sa matrice
génératrice), un mot y ∈ Fnq , et un entier t.

2.1.1 Formalisation
Voici les formalisations classiques des problèmes de décodage les plus courants :
— Décodage au maximum de vraisemblance (C, y)
Il s’agit de trouver un mot c ∈ C vérifiant d(c, y) = d(C, y), C’est-à-dire le mot de code le plus
proche au sens de Hamming de y. En d’autres termes, c’est le mot qui a été probablement envoyé
par l’expéditeur.
— Décodage borné (C, y, t)
Il s’agit de trouver, s’il existe, un mot c ∈ C vérifiant d(c, y) ⩽ t.
— Décodage en liste (C, y, t)
Il s’agit de trouver l’ensemble des mots c ∈ C vérifiant d(c, y) ⩽ t. Cela revient à établir un
ensemble de candidats réalistes pour le mot envoyé.

Remarquons que le problème de décodage borné est plus simple que chacun des deux autres.
Mais si t ⩽ d−1
2
, alors décodage borné (C, y, t) et décodage en liste (C, y, t) sont équivalents. On

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.1 Décodage d’un code linéaire 24

ne s’intéresse donc au décodage en liste que pour des distances excédant la capacité de correction.
Nous allons maintenant étudier deux algorithmes permettant de résoudre de façon générale le
problème de décodage d’un code linéaire.

2.1.2 Décodage par tableau standard

Soit H une matrice de parité du code C. Si on a y = c + e avec c ∈ C, alors le syndrome de y
est donné par :

Hy T = HcT + HeT = HeT .

Par conséquent, si c est une solution du problème de décodage borné, on peut calculer c à
l’aide d’un mot de poids faible de même syndrome que y.
Algorithme : Décodage par tableau standard
— Input : G, y = (y1 , ..., yn ), t
— Output : x ∈ C tel que d(x, y) ⩽ t
— Pré-calculs : Calculer une matrice de parité H associée à la matrice génératrice G. Pour
chaque mot e ∈ Fnq de poids inférieur ou égal à t, calculer HeT et l’ajouter à la liste des
syndromes S.
— Décodage : Calculer Hy T , et rechercher dans la liste S un mot e admettant le même
syndrome.
Si e existe, renvoyer c = y − e.
Sinon, renvoyer ”pas de solution”
Applications.
 
1 0 0 0 1 1 1
 
0 1 0 0 0 1 1
Soit C le code [7, 4, 3] de Hamming binaire, de matrice génératrice G = 
0 0 1 0 1 0 1 ;

 
0 0 0 1 1 1 0
y = (1111101) le mot à décoder
 ; t = 1. 
1 0 1 1 1 0 0
— Pré-calculs : H = 1 1 0 1 0 1 0 est une matrice de contrôle de C.
 

1 1 1 0 0 0 1
— Liste des syndromes :
Mots de poids ⩽ 1 Syndromes
 
  0
0 0 0 0 0 0 0 0
 

0
 
  1
1 0 0 0 0 0 0 1
 

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.1 Décodage d’un code linéaire 25

 
  0
0 1 0 0 0 0 0 1
 

1
 
  1
0 0 1 0 0 0 0 0
 

1
 
  1
0 0 0 1 0 0 0 1
 

0
 
  1
0 0 0 0 1 0 0 0
 

0
 
  0
0 0 0 0 0 1 0 1
 

0
 
  0
0 0 0 0 0 0 1 0
 

1
— Décodage :  
1
 
1
    
1 0 1 1 1 0 0 1
 0
T
Hy = 1 1 0 1 0 1 0 1 = 1 .
     
 
1 1 1 0 0 0 1 1
 0
0
 
1
 
Le mot de poids faible de même syndrome que y est e = 0 0 0 0 0 1 0 ; le mot
 
de code cherché est alors c = y − e = 1 1 1 1 1 1 1 .

Cet algorithme doit cependant calculer et manipuler une liste S contenant les syndromes de
tous les mots de poids de Hamming inférieur ou égal à t. Pour une valeur w fixée, w ⩽ t Il existe
t
Cnw (q − 1)w mots d’un tel poids ; soit au total Cnw (q − 1)w mots de poids inférieur ou égal à
P
w=1
t. La complexité de l’algorithme est donc exponentielle en t. On peut améliorer la complexité du
décodage, en utilisant un algorithme de décodage par ensemble d’information.

2.1.3 Décodage par ensemble d’information

Un ensemble d’information est un paramètre très important ; il indique que les positions des
mots d’un code prises par paquet de k n’ont pas toutes la même importance. k positions tirées
aléatoirement ne forment pas toujours un ensemble d’information.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.1 Décodage d’un code linéaire 26

Dans la suite, I désignera un ensemble d’information du [n, k] code C, L = {1, 2, ..., n} et J le

complémentaire de I dans L.
Pour toute matrice G et tout sous ensemble d’information I de L, on note
G = (GI | GJ ) où GI est la sous matrice de G constituée des colonnes étiquetées par les éléments
de I. Pour tout vecteur x ∈ Fnq , on notera x = (xI | xJ ) où xI (respectivement xJ ) désigne les
positions du mot x étiquetées par les éléments de I (respectivement de J).
Soit C un code [n, k] de matrice génératrice G et de capacité de correction théorique t ;

soit y = mG + e, m ∈ Fkq .
On a y = (y I | y J ) = m (GI | GJ ) + (eI | eJ ) ;
d’où eI = y I − mGI et eJ = y J − mGJ .

Ainsi, si l’ensemble d’information ne contient pas de position d’erreur (c’est-à-dire eI = 0), on

a:

y I = mGI et eJ = y J − mGJ .

Comme GI est inversible par définition, le système s’écrit :

m = y I GI−1 et eJ = y J − y I G−1
I GJ

Ainsi, le vecteur e = (eI | eJ ) = (0 | y J − y I G−1

I GJ ) est la solution cherchée du problème de
décodage borné par t du code C.
Le Principe des algorithmes de décodage par ensemble d’information se présente comme suit :
Algorithme : Décodage par ensemble d’information.
— Input : G, y = (y1 , ..., yn ) à distance au plus t du code C.
— Output : x ∈ C et e tel que y = x + e.
— Décodage :
1. Tirer aléatoirement un ensemble d’information I du code de matrice génératrice G.
2. Calculer R = G−1 I GJ .
3. Calculer eJ = y J − y I R.
Si w(eJ ) ⩽ t, retourner e = (0 | eJ ) et x = y − e
Sinon, recommencer la procédure avec un nouveau I.

Applications.
 
Considérons le code C de l’application précédente et y = 1 1 0 0 0 1 0 le mot à décoder.
On a encore t = 1.  
1 1 1
 
0 1 1
— Pour I = {1, 2, 3, 4} , on a GI = I 4 et GJ =  .
 1 0 1

1 1 0
−1 −1
GI = I 4 ; R = GI GJ = I 4 GJ = GJ ;

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.2 Cryptosystèmes de McEliece et de Niederreiter 27

 
1 1 1
 
0 1 1
  
yI R = 1 1 0 0  1
= 1 0 0 ;
 0 1
1 1 0
     
eJ = y J − y I R = 0 1 0 − 1 0 0 = 1 1 0 et on a w(eJ ) = 2 > t.
   
1 0 0 1 0 1 1
   
0 1 0 0 0 1 1
— Pour I = {1, 2, 3, 5} , on a GI = 0 0 1 1 et GJ = 0 0
  .
   1
0 0 0 1 1 1 0
    
1 0 0 1 0 1 1 1 0 1
    
0 1 0 0 0 1 1 0 1 1
G−1 −1
I = GI ; R = GI GJ = 
  = 
0 0 1 1 0 0 1 1 1 1
  

0 0 0 1 1 1 0 1 1 0
 
1 0 1
  
0 1 1  
yI R = 1 1 0 0  
= 1 1 0

1 1 1
1 1 0
     
eJ = y J − y I R = 0 1 0 − 1 1 0 = 1 0 0
 
On a w(eJ ) = 1 ⩽ t ; donc e = 0 0 0 1 0 0 0 .
 
D’où x = y − e = 1 1 0 1 0 1 0 .

Remarque 2.1. La probabilité P pour que k éléments de L tirés aléatoirement n’étiquettent aucune
des t positions du vecteur d’erreur est égale à :
k
Cn−t
P = Cnk

3
La complexité moyenne de l’algorithme vaut O( kP ) multiplications dans Fq . Et si on prend par
exemple n=1024, k=512 et t=50, l’algorithme décrit en moyenne 253 itérations tandis que celui du
décodage par tableau standard décrit en moyenne 2283 itérations. La complexité des algorithmes
de décodage par ensemble d’information est donc nettement mieux ; mais toujours exponentielle.
Mais si le décodage d’un code linéaire donné avait toujours une complexité exponentielle, on
ne pourrait pas utiliser efficacement les codes pour faire de la correction d’erreurs. Heureusement,
pour certaines familles de codes comme les codes de Reed-Solomon, la structure du code nous
permet de développer des algorithmes de décodage encore plus rapides.

2.2 Cryptosystèmes de McEliece et de Niederreiter

Les cryptosystèmes de McEliece et de Niederreiter fondent respectivement leurs sécurités sur
les deux problèmes suivants de la théorie des codes :

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.2 Cryptosystèmes de McEliece et de Niederreiter 28

Problème 2.2. (Décodage borné par t)

Étant donnés :
— Un code linéaire aléatoire de longueur n, de dimension k, donné par une matrice génératrice
G,
— un mot y de longueur n,
trouver s’il existe un couple de mots (x, e) tel que y = xG + e. Où e est un mot de poids t.

Problème 2.3. (recherche d’un mot de poids t connaissant son syndrome) Étant donnés :
— Un code linéaire aléatoire de longueur n, de dimension k, donné par une matrice de parité
H,
— Un mot s de longueur n − k,
trouver s’il existe un mot x de longueur n et de poids t tel que :

y = xH T

Dans cette section, nous allons commencer par décrire les instances les plus générales des
systèmes de McEliece et de Niederreiter.

Cryptosystème de McEliece

Soit G une famille de codes linéaires de longueur n sur Fq et de dimension k, pour lesquels on
dispose d’un algorithme polynômial permettant de résoudre le problème du décodage borné par
t. La famille G sera appelée par la suite espace des clés du cryptosystème. Le cryptosystème de
McEliece [McE78] se présente comme suit :

Génération des clés :

— On se donne G ∈ Mk×n (Fq ), matrice génératrice d’un code C ∈ G,
— On génère S, une matrice inversible k × k sur Fq , et P , une matrice de permutation n × n.
— On calcule Gpub = SGP , matrice k × n à coefficients dans Fq .
La clé publique est le couple (Gpub , t).
La clé secrète est la décomposition (S, G, P ).

Chiffrement : Pour chiffrer le message m ∈ Fkq , on génère aléatoirement un vecteur e ∈ Fnq de

poids de Hamming au plus t. Le chiffré est alors le vecteur c = mGpub + e.

Déchiffrement : Le vecteur cP −1 est à distance au plus t du code C. Notre algorithme de

décodage permet donc de retrouver le vecteur mSG ∈ C. On en déduit m par inversion matricielle.

Cryptosystème de Niederreiter

Soit G une famille de codes linéaires de longueur n sur Fq et de dimension k, pour lesquels on
dispose d’un algorithme polynômial permettant de résoudre le problème 2.3. Le fonctionnement
du cryptosystème de Niederreiter [Nie86] se présente comme suit :

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.2 Cryptosystèmes de McEliece et de Niederreiter 29

Génération des clés :

— On se donne H ∈ M(n−k)×n (Fq ), matrice de parité d’un code C ∈ G.
— On génère S, une matrice inversible (n−k)×(n−k) sur Fq , et P , une matrice de permutation
n × n.
— On calcule H pub = SHP , matrice (n − k) × n à coefficients dans Fq .
La clé publique est le couple (H pub , t).
La clé secrète est la décomposition (S, H, P ).

Chiffrement : L’ensemble des messages est ici l’ensemble des mots de longueur n et de poids
de Hamming au plus t. Pour un message m dans cet ensemble, le chiffré est le vecteur c tel que
cT = H pub mT .

Déchiffrement : On a cT = SHP mT ;
On calcule S −1 cT = HP mT = H(P mT )
P mT est la transposée d’un mot de longueur n et de poids au plus t dont on connaît le
syndrome ; le receveur retrouve P mT en appliquant l’algorithme polynomial qui résout le problème
3.0.2. Il retrouve alors m en appliquant la permutation P −1 .

Sécurité des cryptosystèmes

Comme on peut le voir, les systèmes de McEliece et de Niederreiter fondent leur sécurité sur
les problèmes 2.2 et 2.3 respectivement. Bien que ces problèmes soient de formulations distinctes,
ils sont équivalents :

Proposition 2.4.
— Il existe un algorithme qui, à partir de la résolution du problème 2.2 pour un code C, permet
de résoudre le problème 2.3 pour C.
— Réciproquement, il existe un algorithme qui, à partir de la résolution du problème 2.3 pour
un code C, permet de résoudre le problème 2.2 pour C .

Preuve. La preuve se décompose en deux étapes.

1. Supposons que l’on sait résoudre le problème du décodage borné par t d’un code C de
longueur n et de dimension k, de matrice génératrice G, c’est-à-dire pour tout mot y à
distance au plus t du code C, on retrouve le couple (x, e) tel que y = xG + e, où e est de
poids au plus t.
Soit H une matrice de parité du code C, et soit y un mot tel que :
y = xH T ,
où x est de longueur n et de poids t.
Supposons sans nuire à la généralité que la forme systématique de H est :
H syst = (I n−k | R);

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.2 Cryptosystèmes de McEliece et de Niederreiter 30

c’est-à-dire qu’il existe une matrice S inversible de taille (n − k) × (n − k) telle que :

H = SH syst c.-à-d. S −1 H = H syst .
Si tel n’est pas le cas, on peut toujours s’y ramener par des permutations adéquates sur les
colonnes.
Soit y ′ = (y · (S T )−1 , 0, ..., 0).
| {z }
k fois
y est un mot de longueur n ; calculons y ′ · H T :
′

y ′ · H T = (y · (S −1 )T , 0, ..., 0) · H T
| {z }
k fois

Supposons S −1 = (Sij )n−k,n−k n−k,n

i=1,j=1 et H = (hij )i=1,j=1 .

La peme composante de y · (S T )−1 est donnée par :

n−k
P
βp = yl Spl (p = 1, ..., n − k).
l=1

Ainsi, la j eme (j = 1, ..., n − k) composante de y ′ · H T est :

n−k
P n−k
P n−k
P
βp hjp = yl Spl hjp
p=1 p=1 l=1
P n−k
n−k P
= yl ( Spl hjp ).
l=1 p=1

n−k
Spl hjp est la composante αjl de la matrice H I S −1 = I n−k (car S −1 H I = I n−k );
P
Mais
p=1
avec I = {1, 2, ..., n − k}.
(
0 si j ̸= l,
Donc, αjl =
1 si j = l.
n−k
P n−k
P n−k P
D’où, βp hjp = yl ( Spl hjp )
p=1 l=1 p=1
= yj .
Ainsi, y ′ · H T = y = xH T .
Les mots y ′ et x ont le même syndrome ; c’est-à-dire qu’il existe un mot c ∈ C tel que
y ′ = c + x.
On passe ainsi du problème de la recherche d’un mot de poids t connaissant son syndrome,
au problème du décodage borné par t de C.
2. Supposons que l’on sait résoudre le problème 2.3 ; c’est-à-dire pour tout mot y tel que
y = xH T , on sait retrouver le mot x.
Soit y un mot tel que :

y = xG + e

En calculant le produit de y à droite par la matrice H T du code C, on a :

yH T = xGH T + eH T = eH T ; où e est de poids t.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

2.3 Exemple : Attaque structurelle sur les codes GRS 31

Comme on sait résoudre le problème de la recherche d’un mot de poids borné par t connais-
sant son syndrome, on sait retrouver e.

Un cryptanalyste n’a que deux possibilités d’attaquer le système :

(i) Soit il tente directement de déchiffrer c dans le code C (attaque sur le chiffré ou attaque
par décodage),
(ii) Soit il essaye de mettre au point son propre algorithme de décodage en essayant par
exemple de retrouver une décomposition valide de la clé Gpub = S ′ G′ P ′ , ou H pub = S ′ H ′ P ′
(attaque sur la clé ou attaque structurelle).

Par la proposition précédente, toute attaque par (ii) réussie sur un cryptosystème de McEliece
de code public C se traduit par une attaque de même nature sur le cryptosystème de Niederreiter
utilisant le même code public et réciproquement. C’est pour cela qu’on se limite généralement à
l’étude de l’un des deux cryptosystèmes lorsqu’on parle de sécurité.
Dans le cas d’un système de McEliece par exemple, l’attaquant connaît Gpub sans connaître sa
décomposition, et connaît le chiffré c. Son but étant de trouver une décomposition c = mGpub +e,
La sécurité du système repose sur deux suppositions :
1. Premièrement, que le code C est difficile à décoder au rayon t ; ce qui est le cas par exemple si
ce code ne peut pas être algorithmiquement distingué d’un code aléatoire, et si les paramètres
du code sont suffisamment grands pour neutraliser les algorithmes de décodage par ensemble
d’information.
2. Deuxièmement, qu’il est difficile de retrouver les matrices S, G, P à partir de Gpub .
La résistance du système dépend donc intrinsèquement de la famille G dans laquelle est choisie
G. Le choix de cette famille est le point délicat dans la conception du cryptosystème. En effet, on
veut utiliser une famille de codes que l’on sait décoder (et si possible rapidement), ce qui impose
que ces codes soient structurés. D’un autre côté, des codes trop structurés prêtent le flanc à des
attaques tirant parti de cette structure. Il faut donc atteindre un compromis.

2.3 Exemple : Attaque structurelle sur les codes GRS

Dans cette section, nous allons montrer comment la structure d’un code peut mener à une
attaque efficace lorsque celui-ci est utilisé dans un cryptosystème. Nous nous intéressons particu-
lièrement aux codes GRS étudiés au chapitre 1.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.

 Bibliographie

[Her11] Vincent Herbert. Des codes correcteurs pour sécuriser l’information numérique. PhD
thesis, Université Pierre et Marie Curie-Paris VI, 2011.
[McE78] Robert J. McEliece. A Public-Key System Based on Algebraic Coding Theory, pages
114–116. Jet Propulsion Lab, 1978. DSN Progress Report 44.
[Nie86] Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems
of Control and Information Theory, 15(2) :159–166, 1986.

Cours Crypto Adv HERVE TALE KALACHI ©ENSPY@2024.