Ensimag Rubrique Formation 2022

Codes: cryptographie, compression, correction d'erreurs - 4MMCRY

  • Volumes horaires

    • CM 16.5
    • TD 16.5

    Crédits ECTS

    Crédits ECTS 2.5

Objectif(s)

L'objectif du cours est de former aux fondements informatiques et mathématiques pour fournir des garanties sur la confidentialité, l'intégrité et l'authentification des communications numériques. Ce cours présente la théorie des codes, ses fondements mathématiques et ses applications en cryptographie, compression et codes correcteurs. Il permet d’acquérir les fondements nécessaires pour la mise en oeuvre et l’exploitation des protocoles de codage.

Contact Jean-Louis ROCH

Contenu(s)

1. Codage binaire de l’Information – Entropie.
2. Le groupe Zn* ; fonction d’Euler et théorème chinois des restes. Polynômes et corps finis. Corps de Galois.
3. Cryptographie symétrique – chiffrement parfait de Vernam sur un groupe. AES, crypt
4. Cryptographie asymétrique. Diffie-Hellman, El Gamal. RSA : sécurité et attaques.
5. Mode de chaînage. Générateur aléatoire sûr. Hachage. Signature électronique. DSA
6. Compression sans perte. Arbres de Huffman ; Lempel-Ziv zlip / zip
7. Codes correcteurs d’erreurs ; distance d’un code. Codes détecteurs d’erreurs. CRC
8. Codes linéaires et codes de Reed-Solomon. Décodage unique et par liste.
9. Codes cycliques BCH et codes raccourcis.



Prérequis

Connaissances de base en : probabilités (Cours de Probabilités Appliquées 1) ; Algorithmique et analyse de coût
(Algorithmique 1 et 2) ; bases en algèbre linéaire (résolution de systèmes par élimination de Gauss), arithmétique
entière et polynomiale (primalité, pgcd).

Contrôle des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique : NON
Durée : 3h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents manuscrits et phtocopies autorisés
Documents interdits (ex : livres, tous documents) : livres interdits
Matériel (ex : calculatrices):

  • matériel autorisé, préciser : aucun
  • matériel interdit, préciser : tout calculateur électronique (ordinateur, calculette, téléphone, ...)
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : écrit si > 6 étudiants; oral si <=6 étudiants.
Salle spécifique : pour oral de rattrapage: 2 (petites) salles côte à côte, une où l'étudiant passe l'oral, l'autre où l'étudiant prépare.
Durée : écrit 2h ; si oral: 30' préparation + 30' oral par étudiant
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents manuscrits et photocopies
Documents interdits (ex : livres, tous documents) : livres (sauf si oral)
Matériel (ex : calculatrices):

  • matériel autorisé, préciser : aucun si écrit; mais ordinateur autorisé si oral.
  • matériel interdit, préciser : tous si écrit; mais ordinateur autorisé si oral.

Commentaires :



1 examen écrit de 3 heures (documents autorisés) (E).
N1=E1
N2=E2

Informations complémentaires

Cursus ingénieur->Filière MMIS->Semestre 4
Cursus ingénieur->Filière ISI->Semestre 4
Cursus ingénieur->Filière ISSC->Semestre 4
Cursus ingénieur->Filière SLE->Semestre 4

Bibliographie

S. Arora, B. Barak, Computaional complexity: a modern approach, 2009
JG Dumas, JL Roch, E Tannier, S Varrette, Théorie des Codes, Dunod Sc.iences Sup., 2ème édition, 2009.
James Massey. Applied Digital Information Theory (vol I et II) ETZH. University.