Soutenance mémoire
Généralités sur la cryptographie et les codes correcteurs d’erreurs
Généralités sur la cryptographie
Définitions
La cryptographie vient du grec kryptos qui veut dire caché et de graphien qui signifie écrire. La cryptographie est donc un ensemble des techniques permettant de protéger une communication au moyen d’un code graphique secret. Elle est l’étude des méthodes d’envoi de messages codés de telle sorte que seul le destinataire puisse le décoder. Le message qu’on veut envoyer est appelé le texte clair et le message codé, ou encrypté, est également appelé cryptogramme. Le processus de conversion d’un texte clair en message codé s’appelle chiffrement, ou codage. Et le processus inverse est appelé déchiffrement, ou décodage. Pour effectuer un codage, on suit une méthode précise appelée système cryptographique, ou cryptosystème. Un codage se fait donc à l’aide d’un cryptosystème, et celui-ci nécessite très souvent l’utilisation d’une clé.
La cryptanalyse est l’étude des méthodes qui permettent de découvrir le sens d’un message codé, sans connaître le message original. Il y a plusieurs situations possibles. On peut vouloir simplement trouver le sens du message codé, sans chercher la clé de codage. Mais, en général on voudra d’abord trouver quel est le système de codage, puis la clé de codage utilisée. Lorsqu’on a trouvé tous les éléments de la méthode utilisée pour coder les messages, on dit qu’on a cassé, ou brisé, le système cryptographique en question. Plus un système est « difficile » à briser, plus il est qualifié de « sûr ». La cryptologie est l’ensemble formé de la cryptographie et de la cryptanalyse. Elle fait partie d’un ensemble de théories et techniques liées à la transmission de l’information (théorie des ondes électromagnétiques, théorie du signal, théorie de l’information, …).
Principe de Kerckhoff
Dans son article La cryptographie militaire [7], Auguste Kerckhoff fustige le manque de précaution lors de l’utilisation des techniques cryptographiques dans les armées. Cependant, la partie la plus connue de cet article est de Desiderata de la cryptographie militaire, où il énonce six conditions pour avoir un système cryptographique fiable et utilisable par les armées. De ces six points, le plus important est le second: «il faut qu’il (le système cryptographique) n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi ». Autrement dit, tout système cryptographique devrait avoir sa fiabilité du fait de la difficulté de trouver sa clé, et non du secret de l’algorithme. De plus, en rendant les algorithmes publics, les cryptanalystes du monde entier peuvent essayer de le casser ou l’améliorer.
Enjeux de la cryptographie
Dès que plusieurs entités sont impliquées dans un échange de messages sécurisés, des règles doivent déterminer l’ensemble des opérations cryptographiques à réaliser, leur séquence, afin de sécuriser la communication. Ainsi, lorsque l’on parle de ‘‘sécuriser un échange’’, on souhaite prêter attention aux trois services suivants:
La confidentialité: seulement le destinataire autorisé doit être capable d’extraire le contenu du message de son état crypté. Par ailleurs, l’obtention de l’information à propos du contenu du message ne doit pas être possible.
L’intégrité: Par analyse de l’intégrité le destinataire peut déterminer si le message a été modifié pendant la transmission.
L’authentification: le destinataire doit avoir la capacité d’identifier le destinataire du message, aussi bien que de savoir si c’est l’auteur présumé qui a en effet envoyé le message.
Notion de chiffrement
Dans la cryptographie moderne, toute sécurité est basée sur la clé (ou les clés), et non dans les détails des algorithmes. Cela signifie qu’un algorithme peut être publié et analysé, mais la clé doit être protégée [8]. Ainsi, dans les systèmes cryptographiques utilisant des clés, il faut bien distinguer les deux types existants: le chiffrement symétrique et le chiffrement asymétrique.
Chiffrement symétrique
Le chiffrement symétrique (aussi appelé chiffrement à clé privée, ou à clé secrète) se base sur l’utilisation d’une clé qui doit rester secrète et qui ne doit être connue que par les personnes devant crypter et décrypter les messages. La sécurité de la méthode de chiffrement réside donc dans la difficulté à trouver cette clé.
Les algorithmes de chiffrement symétriques sont très rapides en termes de calcul. Cependant, leur principal inconvénient est le problème de la distribution de la clé entre l’expéditeur et le destinataire.
On peut distinguer deux types de chiffrements symétriques :
• Le chiffrement par flux qui se fait bit à bit sans attendre la réception entière de données. Le RC4 (Rivest Cipher 4) est l’algorithme le plus connu pour ce type de chiffrement.
• Le chiffrement par bloc qui consiste à diviser les données en blocs de taille généralement fixe (entre 64 et 128 bits). Les blocs sont ensuite chiffrés les uns après les autres. Les algorithmes les plus répandus de ce type de chiffrement sont : le DES (Data Encryption Standard) et l’AES (Advanced Encryption Standard) qui est actuellement l’algorithme le plus utilisé et le plus sûr.
Codes correcteurs d’erreurs
Théorie des codes
En 1948, dans son article intitulé ‘‘A mathematical theory of communication’’, Claude Shannon posa les bases de ce que l’on appelle aujourd’hui la théorie de l’information [12]. La théorie de l’information décrit les aspects les plus fondamentaux des systèmes de communication, essentiellement à l’aide de la théorie des probabilités. Elle étudie les moyens de transmettre un message depuis une source (voix, signal numérique, onde électromagnétique, …) jusqu’à un destinataire et via un canal de transmission (liaison radio, ligne téléphonique, …).
Cependant, lorsqu’une information est transmise à travers un canal, celui-ci génère des erreurs ou des effacements. Le canal est alors bruité. Ce problème sera résolu en 1950, lorsque Richard W. Hamming, dans son article ‘‘Error detecting and error correcting codes’’ introduisit la théorie des codes [13]. Hamming proposa ainsi les premiers codes correcteurs d’erreurs. Ces derniers sont un outil qui permet d’assurer la transmission fiable d’informations à travers un canal. L’idée étant de rajouter de la redondance au message transmis, de sorte que cet excèdent d’information aide à retrouver le message initial. Une grande famille des codes correcteurs d’erreurs est constituée des codes par blocs. Pour ces codes, l’information est d’abord coupée en blocs de taille constante et chaque bloc est transmis indépendamment des autres, avec une redondance qui lui est propre. La plus grande sous-famille de ces codes rassemble ce que l’on appelle les codes linéaires.
Canal binaire symétrique
La modélisation des canaux est un enjeu majeur pour la théorie de l’information afin de comprendre les propriétés du bruit qu’ils vont produire et de l’estimer. En effet, le choix de l’algorithme de décodage et le bon fonctionnement de celui-ci dépendent du modèle du canal utilisé. Dans notre manuscrit, nous allons considérer le modèle du canal binaire symétrique. C’est un canal binaire caractérisé par la probabilité d’erreur ? qu’au cours de la transmission un bit (0 ou 1) soit modifié en son opposé. Ces modifications se produisent indépendamment sur chacun des bits transmis.
|
Table des matières
Introduction Générale
Chapitre 1 Généralités sur la cryptographie et les codes correcteurs d’erreurs
1.1. Généralités sur la cryptographie
1.1.1. Définitions
1.1.2. Principe de Kerckhoff
1.1.3. Enjeux de la cryptographie
1.1.4. Notion de chiffrement
1.1.4.1. Chiffrement symétrique
1.1.4.2. Chiffrement asymétrique
1.1.5. Fonction de hachage
1.2. Codes correcteurs d’erreurs
1.2.1. Théorie des codes
1.2.2. Canal binaire symétrique
1.2.3. Codes linéaires
1.2.3.1. Définition et exemple
1.2.3.2. Matrice génératrice
1.2.3.3. Code dual
1.2.3.4. Matrice de contrôle de parité
1.2.3.5. Fonction syndrome
1.2.4. Quelques exemples de codes linéaires
1.2.4.1. Code de Hamming
1.2.4.2. Codes de Goppa classique
1.2.4.3. Codes cycliques
a. Définition
b. Représentation polynomiale
c. Matrice circulante et quasi-circulante
d. Codes quasi-cycliques
1.2.4.4. Autres codes
Chapitre 2 Cryptosystème de McEliece et codes QC-MDPC
2.1. Le cryptosystème de McEliece
2.1.1. Génération de clés
2.1.2. Chiffrement
2.1.3. Déchiffrement
2.1.4. Exemple
2.1.5. Avantages et inconvénient du cryptosystème de McEliece
2.1.6. Problème difficile en théorie des codes
2.1.7. Sécurité du cryptosystème de McEliece
2.2. Les Codes quasi-cycliques MDPC
2.2.1. Etat de l’art
2.2.2. Définitions
2.2.3. Les codes ??-???? pour le schéma de McEliece
2.2.3.1. Génération des clés
2.2.3.2. Chiffrement
2.2.3.3. Déchiffrement
2.2.4. Décodage
2.2.5. Sécurité
2.2.6. Taille de la clé
Chapitre 3 Attaques sur les codes QC-MDPC
3.1. Attaque de Guo-Johannson-Stankovski
3.1.1. Spectre de distance
3.1.2. Description de l’attaque
3.1.3. Reconstruction de la Clé secrète
3.2. Attaque temporelle
Chapitre 4 Analyse des algorithmes de décodage des codes QC-MDPC
4.1. Optimisation de l’algorithme Bit-flipping
4.2. Les variantes de l’algorithme Bit-flipping
4.2.1. La variante Black-Gray
4.2.2. La variante Back-flipping
4.3. Notre proposition
4.4. Simulations et résultats
4.4.1. Choix des paramètres de simulations
4.4.2. Simulations avec 11 itérations
4.4.3. Simulations avec 7 itérations
4.4.4. Simulations avec 5 itérations
Conclusion Générale
