Sommaire
Introduction
1 Théorie des codes
1.1 De Jules César `a la télécopie
1.1.1 La source : de l’image `a 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 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 Le code de Vernam
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 Chiffrement parfait
1.2.5 Mise en pratique du chiffrement parfait ?
1.3 Codage par
blocs, algèbre et arithmétique
1.3.1 Blocs et modes de chainage
Le mode ECB : Electronic Code
Book
Le mode CBC : Cipher Bloc
Chaining
Le mode CFB : Cipher FeedBack
Le mode OFB : Output FeedBack
Le mode CTR : Counter-mode
encryption
1.3.2 Structures algébriques des mots de codes
Groupes
Anneaux
Corps
Espaces vectoriels
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 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 ambiguité
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
des
codes 7
Transformations avec perte
Transformée de Fourier et transformée
discrète
Algorithme de la DFT
DFT et racines ni`emes
de
l’unit´e dans un corps fini
Produit rapide de polynômes
par la DFT
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´es
Nombres premiers robustes
Résolution du logarithme discret
2 Théorie de l’information et compression
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 RLE – Run Length Encoding
Le code du fax (suite et fin)
2.3.2 Move-to-Front
2.3.3 BWT : Transformation de Burrows-Wheeler
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
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.2 Attaques sur les systèmes cryptographiques
3.2.1 Principes de Kirchhoff
3.2.2 Les grands types de menaces
Attaques passives/actives
Cryptanalyse et attaques sur un
chiffrement
3.3 Système cryptographique a clef secrète
3.3.1 Principe du chiffrement `a clef secrète
3.3.2 Classes de chiffrements symétriques
Les chiffrement symétriques par flot
Les chiffrements symétriques par
blocs
Chiffrement inconditionnellement sûr
3.3.3 Le système DES (Data Encryptions Standard)
Présentation exhaustive du système
DES
Diversification de la clef dans DES
Avantages et applications de DES
Cryptanalyse de DES
3.3.4 Le nouveau standard AES (Rijndael)
Principe de l’algorithme
La diversification de la clef dans
AES
Sécurité de AES
3.4 Système cryptographique `a clef publique
3.4.1 Motivations et principes généraux
3.4.2 Chiffrement RSA
Efficacité et robustesse de RSA
Attaques sur RSA
3.4.3 Chiffrement El Gamal
3.5 Authentification, Intégrité, Non-répudiation
3.5.1 Fonctions de hachage cryptographiques
MD5
SHA-1
SHA-256
Whirlpool
état des lieux sur la résistance aux
collisions
3.5.2 La signature électronique
Contrôle d’intégrité par les
fonctions de hachage
Codes d’authentification, ou MAC
Les signatures électroniques
Signature RSA
Standard DSS - Digital
Signature Standard
3.6 Protocoles usuels de gestion de clefs
3.6.1 Génération de bits crypto graphiquement sûre
3.6.2 Protocole d’´echange de clef secrète de
Diffie-Hellman et
attaque Man-in-the-middle
3.6.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.6.4 Authentification `a clef publique
3.6.5 Infrastructures `a clefs publiques : PGP et PKI X
Principe général
Les éléments de l’infrastructure
Les certificats électroniques
Le modèle PKIX
Architectures non hiérarchiques, PGP
Défauts des PKI
3.6.6 Un utilitaire de sécurisation de canal, SSH
SSH, un protocole hybride
Authentification du serveur
établissement d’une connexion
s´ecuris´ee
Authentification du client
Sécurité, intégrité et compression
Différences majeures entre SSH-1 et
SSH-2
3.6.7 Projets de standardisation et recommandations
4 Détection et correction d’erreurs
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´e 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 barre 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¸conné
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 cycliques
Caractérisation : polynôme générateur
Opération de codage
Détection d’erreur et opération de décodage
4.4.4 Codes BCH
Distance garantie
Construction des polynômes générateurs
BCH
Codes BCH optimaux : codes de
Reed-Solomon
Décodage des codes de Reed-Solomon
4.5 Paquets d’erreurs et entrelacement
4.5.1 Paquets d’erreur
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’´etat
Le treillis de codage
L’algorithme de Viterbi
Codes systématiques, rendement et
poin connage
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
Bibliographie
Liste des figures,
tableaux et algorithmes
Liste des figures
Liste des tableaux
Liste des algorithmes
Pages : 353
Forme : PDF
Taille : 3 Mo
