Cryptographie et Machine Quantique

Concepts mathématiques sur les codes correcteurs d’erreurs 

Dans ce Chapitre nous proposons des concepts mathématiques sur les codes correcteurs des erreurs. Nous commençons par des motivations et un rappel. Ensuite nous passons aux codes correcteurs des erreurs, codes et distance de hamming, codes linéaires..

Motivations

La plupart des cryptosystèmes à clé publique utilisés sont basés sur des problèmes de théorie des nombres. Il est important de connaître des systèmes alternatifs efficaces en pratique (réseaux, systèmes multivariés, codes correcteurs d’erreurs, fonctions de hachage. .). Les avantages de la cryptographie basés sur les codes correcteurs d’erreurs : a priori sûre face à l’ordinateur quantique, des problèmes NP-complets bien connus, rapides et faciles à implanter. Les désavantages de la cryptographie basés sur les codes correcteurs d’erreurs : grande taille de clé publique (des centaines de milliers de bits . . .). Récemment, les systèmes basés sur les codes correcteurs d’erreurs ont été présentés avec de petites tailles de clés (aux alentours de 30 000 bits pour le chiffrement)[46] . 3.1.2 Rappel K corps fini= k corps commutatif + card k fini 1. (k, +) groupe commutatif + associative (x + y) + z = x + (y + z) + commutative x + y = y + x + admet un élément neutre ‘’ 0” : x + 0 =0 + x =x. Chaque élément x admet une symétrie (-x) : x + (-x) = (-x) + x=0 17 18 2. . associative x .(y . z) =(x . y) . z . commutative x . y = y . x. . admet un élément neutre x . 1 = 1 . x = x 3. distributive par rapport à + : x . (y + z) = xy + xz (x + y) . z = xz + yz . inversible ∀x ∈ k,x inversible :∃y ∈ k :xy = yx = 1. Figure 3.1 – Exemple Source: [47] 3.2 Les codes correcteurs Les codes correcteurs ont été introduits pour corriger les erreurs de transmission ou de lecture de données numériques, ou les erreurs survenant au cours de leur inscription sur un Support physique (bande, CD) ou encore lorsque les données subissent une altération sur le Support de stockage. Voici quelques domaines où ils sont appliques : • Transmissions spatiales • Minitel 19 • Codes-barres • Disque compact et DVD • Communications par internet. Le schéma suivant illustre la chaîne d’actions qui permet à une source de transmettre de l’information à un destinataire..

Codes et distance de Hamming

Les messages transmis sont supposés découpes en blocs (ou mots) de longueur n écrits avec l’alphabet {0,1}. Un code (binaire) est un sous-ensemble C de l’ensemble {0, 1} n de tous les mots possibles. On dit que n est la longueur de C. La distance de Hamming entre deux mots x = (x1,. . . ., xn) et y = (y1,. . . ., yn), que l’on notera d(x,y), est le nombre d’indices i tels que xi = yi. C’est bien une distance sur {0, 1} n . La distance minimal du code C’est le minimum des d(x,y) pour x et y des mots différents de C (on suppose que C a au moins 2 mots !). On la notera toujours d. Exemple . Considère C = c0, c1, c2, c3 avec c0 = (00000) ; c1 = (10110) ; c2 = (01011) ; c3 = (11101) : C’est un code de longueur 5 et de distance d = 3. Le mot c ∈ C est émis et, après d’éventuelles erreurs de transmission, le mot r ∈ {0, 1} n est reçu.On décode le mot r selon le principe du maximum de vraisemblance, c.-à-d. qu’on le décode comme un mot de C à distance minimum de r. On dit que C est t-correcteur (ou corrige t erreurs) quand toute erreur portant sur au plus t bits est corrigée correctement. On voit donc que le code C est t-correcteur si et seulement si les boules fermées (dans {0, 1} n muni de la distance de Hamming) de centres les éléments de C et de rayon t sont disjointes, ou encore si et seulement si la distance minimum d de C vérifie d ≥ 2t + 1 . Il est souvent difficile de calculer la distance minimale et plus encore de décoder un mot sans structure additionnel c’est pourquoi on préfère travailler avec des codes linéaires.

Les codes linéaires

Les codes correcteurs pour lesquels la redondance dépend linéairement de l’information peuvent être définis par une matrice génératrice G de taille k × n[47] : Figure 3.3 – Exemple Source: [47] 3.4.1 Définition Un code binaire C est linéaire si la somme de deux mots quelconques du code est encore un mot du code : w1, w2 ∈ C, w1 + w2 ∈ C Un code linéaire est donc un sous-espace vectoriel de Z/pZ. En particulier le nombre de mots du code est 2p, ou p est la dimension de C. Remarque : dans un code linéaire, le mot 0n est toujours un mot du code : En effet si x est un mot du code quelconque, alors x + x = 0n est aussi un mot du code..

Représentations matricielles

La détermination du mot de code associé à un bloc, telle que nous venons de la décrire, se ramène à un produit de matrices ; voyons comment. Un mot binaire peut être représenté par une matrice ligne dont les coefficients sont les bits de ce mot. Pour économiser les notations, nous donnerons le même nom à la matrice ligne et au mot binaire qu’elle représente. Exemple . Le mot binaire b=01001 est représenté par matrice ligne : b= (0 1 0 0 1) On appelle matrice génératrice du codage et on note G, la matrice à k lignes et n colonnes obtenue en écrivant l’un au-dessous de l’autre et dans l’ordre, les mots de code des blocs bi de la base canonique. Parce que le codage est systématique, les k bits d’information sont écrits en premier, sans en changer l’ordre, et les bits de contrôle viennent ensuite. Cette particularité fait que G apparait comme la juxtaposition de deux matrices (figure2.5) : 21 Figure 3.4 – Exemple Source: [47] à gauche Ik, la matrice identité d’ordre k, et à droite une matrice à k lignes et r colonnes, notée P, qu’on appelle la matrice de parité et qui est constituée des bits de contrôles des mots de code ϕ(bi)..

Matrice génératrice

On peut se donner un sous-espace vectoriel (et donc un code) par une base. Soit C un code linéaire. Une matrice génératrice de C est une matrice dont les lignes forment une base de C. Une matrice génératrice G est donc de taille k × n et de rang k. Si m est un vecteur ligne de F2 k ,le produit mG est un mot du code C et l’application m → mG est un isomorphisme de sur C (que l’on peut voir comme une opération de codage). Si la matrice G est de la forme (I, P), on dit que le codage est systématique. Les k premiers bits d’un mot de code portent l’information (on y recopie le vecteur de F2 k ), les n-k suivants sont de la redondance. Exemple : La matrice M =   1 0 0 0 0 1 1 0 1 0 1 1 1 0 1.