Théorie des codes - Compression, Cryptage, Correction

Théorie des codes

Table des matières

Préambule Introduction 1 Théorie des codes 1.1 De Jules César à la télécopie 1.1.1 La source : de l'image à la suite de pixels 1.1.2 La compression du message 1.1.3 La détection d'erreurs 1.1.4 Le chiffrement 1.1.5 Le décodage L'attaque et le déchiffrement La décompression et les pertes 1.1.6 Les défauts de ce code 1.1.7 Ordres de grandeur et bornes de complexité des algorithmes Taille des nombres La vitesse des ordinateurs Taille et âge de l'univers Complexité des algorithmes 1.2 Codage par flot et probabilités 1.2.1 Vernam et le chiffrement à clef jetable (one-time-pad) 1.2.2 Un peu de probabilités Évènements et mesure de probabilité Probabilités conditionnelles et formule de Bayes 1.2.3 Entropie Source d'information Entropie d'une source Entropies conjointe et conditionnelle Extension d'une source 1.2.4 Stéganographie et tatouage numérique 1.2.5 Chiffrement parfait 1.2.6 Chiffrement parfait en pratique et principes de Kerckhoffs 1.3 Codage par blocs, algèbre et arithmétique 1.3.1 Blocs et modes de chaînage, du CBC au CTR 1.3.2 Structures algébriques des mots de codes Groupes Anneaux Corps Espaces vectoriels et algèbre linéaire 1.3.3 Codage bijectif d'un bloc Inverse modulaire : algorithme d'Euclide L'indicatrice d'Euler et le théorème de Fermat L'exponentiation modulaire et le logarithme discret Fonctions à sens unique 1.3.4 Construction des corps premiers et corps finis Tests de primalité et génération de nombres premiers Arithmétique des polynômes L'anneau V [X]/P et les corps finis Polynômes irréductibles Constructions des corps finis 1.3.5 Implémentations des corps finis Opérations sur les polynômes Utilisation des générateurs Racines primitives 1.3.6 Courbes sur des corps finis Modèle de Weierstraß Le groupe des points d'une courbe elliptique 1.3.7 Générateurs pseudo-aléatoires Les générateurs congruentiels Les registres à décalage linéaire Générateurs cryptographiquement sûrs Quelques tests statistiques 1.4 Décoder, déchiffrer, attaquer 1.4.1 Décoder sans ambiguïté Propriété du préfixe L'arbre de Huffman Représentation des codes instantanés Théorème de McMillan 1.4.2 Les codes non injectifs L'empreinte de vérification Les fonctions de hachage Transformations avec perte Transformée de Fourier et transformée discrète Algorithme de la Transformée de Fourier discrète (DFT) DFT et racines n-ièmes de l'unité dans un corps fini Produit rapide de polynômes par la DFT Partage de secret 1.4.3 Cryptanalyse Attaque des générateurs congruentiels linéaires Algorithme de Berlekamp-Massey pour la synthèse de registres à décalage linéaire Le paradoxe des anniversaires Attaque de Yuval sur les fonctions de hachage Factorisation des nombres composés Nombres premiers robustes Résolution du logarithme discret 2 Théorie de l'information et compression 107 2.1 Théorie de l'information 2.1.1 Longueur moyenne d'un code 2.1.2 L'entropie comme mesure de la quantité d'information 2.1.3 Théorème de Shannon 2.2 Codage statistique 2.2.1 Algorithme de Huffman L'algorithme de Huffman est optimal 2.2.2 Codage arithmétique Arithmétique flottante Arithmétique entière En pratique 2.2.3 Codes adaptatifs Algorithme de Huffman dynamique -- pack Compression dynamique Décompression dynamique Codage arithmétique adaptatif 2.3 Heuristiques de réduction d'entropie 2.3.1 Run-Length Encoding (RLE) Le code du fax (suite et fin) 2.3.2 Move-to-Front 2.3.3 Transformation de Burrows-Wheeler (BWT) 2.4 Codes compresseurs usuels 2.4.1 Algorithme de Lempel-Ziv et variantes gzip 2.4.2 Comparaison des algorithmes de compression 2.4.3 Formats GIF et PNG pour la compression d'images 2.5 La compression avec perte 2.5.1 Dégradation de l'information 2.5.2 Transformation des informations audiovisuelles 2.5.3 Le format JPEG DCT-JPEG Tatouage numérique d'images JPEG JPSEC 2.5.4 Le format MPEG 3 Cryptologie 3.1 Principes généraux et terminologie 3.1.1 Terminologie 3.1.2 À quoi sert la cryptographie ? 3.1.3 Les grands types de menaces Cryptanalyse et attaques sur un chiffrement 3.2 Système cryptographique à clef secrète 3.2.1 Principe du chiffrement à clef secrète 3.2.2 Classes de chiffrements symétriques Les chiffrements symétriques par flot Les chiffrements symétriques par blocs Chiffrement inconditionnellement sûr 3.2.3 Le système Data Encryption Standard (DES) Présentation exhaustive du système DES Diversification de la clef dans DES Avantages et applications de DES Cryptanalyse de DES 3.2.4 Le standard AES (Rijndael) Principe de l'algorithme La diversification de la clef dans AES Sécurité de AES 3.3 Système cryptographique à clef publique 3.3.1 Motivations et principes généraux 3.3.2 Chiffrement Rivest-Shamir-Adleman (RSA) Efficacité et robustesse de RSA Attaques sur RSA 3.3.3 Chiffrement non-déterministe et OAEP 3.3.4 Chiffrement El Gamal 3.3.5 Codes homomorphes 3.4 Authentification, intégrité, non-répudiation 3.4.1 Fonctions de hachage cryptographiques MD5 SHA-1 et SHA-256 Whirlpool Keccak (SHA-3) État des lieux sur la résistance aux collisions Performance des principales fonctions de hachage 3.4.2 La signature électronique Contrôle d'intégrité par les fonctions de hachage Codes d'authentification ou MAC Les signatures numériques La signature RSA Le Standard de Signature Digitale (DSS) 3.4.3 Preuve à divulgation nulle de connaissance 3.5 Protocoles usuels de gestion de clefs 3.5.1 Génération de bits cryptographiquement sûre 3.5.2 Protocole d'échange de clef secrète de Diffie-Hellman et attaque Man-in-the-middle 3.5.3 Kerberos : un distributeur de clefs secrètes Présentation générale du protocole Kerberos Détail des messages Kerberos Les faiblesses de Kerberos 3.5.4 Authentification à clef publique 3.5.5 Infrastructures à clefs publiques : PKIX Principe général Les éléments de l'infrastructure Les certificats électroniques Le modèle PKIX Défauts des Public Key Infrastructure (PKI) 3.5.6 Architecture pair à pair par toile de confiance : le modèle hybride PGP 3.5.7 Un utilitaire de sécurisation de canal, SSH Authentification du serveur Établissement d?une connexion sécurisée Authentification du client i.e. de l'utilisateur Sécurité, intégrité et compression 3.5.8 Utilisation de la cryptographie dans les applications mobiles et les réseaux sociaux 3.5.9 Projets de standardisation et recommandations 4 Détection et correction d'erreurs 227 4.1 Principe de la détection et de la correction d'erreurs 4.1.1 Codage par blocs 4.1.2 Un exemple simple de détection par parité 4.1.3 Correction par parité longitudinale et transversale 4.1.4 Schéma de codage et probabilité d'erreur 4.1.5 Deuxième théorème de Shannon Rendement d'un code et efficacité Capacité de canal Transmission sans erreur sur un canal de capacité fixée 4.2 Détection d'erreurs par parité - codes CRC 4.2.1 Contrôle de parité sur les entiers : ISBN, EAN, LUHN Code-barres EAN Code ISBN Clé RIB Carte bancaire : LUHN-10 4.2.2 Codes de Redondance Cyclique (CRC) Codage CRC Décodage CRC Nombre d'erreurs de bit détectées Exemples de codes CRC 4.3 Distance d'un code 4.3.1 Code correcteur et distance de Hamming 4.3.2 Codes équivalents, étendus et raccourcis Codes équivalents Code étendu Code poinçonné Code raccourci 4.3.3 Code parfait 4.3.4 Codes de Hamming binaires 4.4 Codes linéaires et codes cycliques 4.4.1 Codes linéaires et redondance minimale 4.4.2 Codage et décodage des codes linéaires Codage par multiplication matrice-vecteur Décodage par multiplication matrice-vecteur 4.4.3 Codes LDPC Matrice de contrôle creuse Encodage Low Density Parity Check (LDPC) Représentation par graphes de Tanner Décodage itératif Applications pratiques des codes LDPC 4.4.4 Codes cycliques Caractérisation : polynôme générateur Opération de codage Détection d'erreurs et opération de décodage 4.4.5 Codes BCH Codes d'interpolation et décodage de Berlekamp-Welch Distance garantie Construction des polynômes générateurs BCH Codes BCH optimaux : codes de Reed-Solomon Décodage rapide des codes de Reed-Solomon Le protocole PAR-2 Code-barres bidimensionnel QR 4.5 Paquets d'erreurs et entrelacement 4.5.1 Paquets d'erreurs 4.5.2 Entrelacement 4.5.3 Entrelacement avec retard et table d'entrelacement 4.5.4 Code entrelacé croisé et code CIRC Application : code CIRC 4.6 Codes convolutifs et turbo-codes 4.6.1 Le codage par convolution 4.6.2 Le décodage par plus court chemin Le diagramme d'état Le treillis de codage L'algorithme de Viterbi Codes systématiques, rendement et poinçonnage Codes convolutifs récursifs 4.6.3 Les turbo-codes Composition parallèle Décodage turbo Turbo-codes en blocs et turbo-codes hybrides Performances et applications des turbo-codes Compression, cryptage, correction : en guise de conclusion Solutions des exercices Solutions des exercices proposés au chapitre 1 Solutions des exercices proposés au chapitre 2 Solutions des exercices proposés au chapitre 3 Solutions des exercices proposés au chapitre 4 Solution de l'exercice du casino Liste des figures, tables, algorithmes et acronymes utilisés Liste des figures Liste des tables Liste des algorithmes Liste des acronymes Bibliographie Index

© 2010 Sébastien Varrette. Template design by Arcsin

Valid XHTML 1.1 Valid CSS!