Vous êtes ici : FIL > Portail > Master Informatique > M1S2 > PAC

PAC : Principes et Algorithmes Cryptographiques

Le cours que certaines "agences" et dirigeants politiques des grandes puissances ne veulent pas que vous suiviez.

Responsable : Charles Bouillaguet

Volume horaire

Cette option est organisée en une séance de cours (1h30) et une séance de TD (1h30) chaque semaine, pendant 12 semaines. Les enseignement sont accompagnés d'un unique TP qui dure tout le semestre. Le SAV du TP est assuré environ une semaine sur deux.

Crédits

Valider le cours rapporte 5 ECTS.
Charles Bouillaguet
dernière modification : 13/01/2018 à 14:21:29

Objectifs

  • Donner un aperçu des principes, des raisonnements et des algorithmes utilisés en cryptographie de nos jours.
  • Comprendre quels genres de problèmes peuvent être résolus par des techniques cryptographiques (contrôle d'accès, vote, argent, anonymat, etc.).

Contenu

Généralités

  • Objectifs de la cryptographie
  • Notion de clef cryptographique
  • clef (secret fort) vs mot de passe (secret faible)

Cryptographie symétrique

  • Protocoles à base de chiffrement : DVDs, clefs de voiture, authentification en ligne
  • Fonctions de hachage cryptographiques : intégrité, stockage de mot de passe, mise en gage.
  • Notions de sécurité du chiffrement à clef secrète. Le masque jetable est inconditionnellement sûr.
  • L'AES, le système de chiffrement le plus utilisé. Pourquoi il est fait comme ça.
  • Modes opératoires de chiffrement : on peut prouver qu'ils sont sûrs.
  • Comment fabriquer une fonction de hachage cryptographique

Cryptographie asymétrique

  • Chiffrement et signature à clef publique : présentation des schémas les plus répandus
  • Identification sans mot de passe dans SSH
  • Problème des attaques par le milieu. Nécessité d'une infrastructure de distribution des clefs.

Cryptographie basée sur le problème du log discret

  • Échange de clefs Diffie-Hellman (comment générer les bons paramètres)
  • Chiffrement ElGamal, et sa sécurité sémantique (équivalence avec le problème DDH)
  • Signatures numériques : Schnorr, ElGamal
  • Génération de nombres pseudo-aléatoires de qualité certifiée (via prédicat hardcore du log discret)

Cryptographie basée sur le problème de la factorisation des entiers

  • Chiffrement et signature de Rabin (comment calculer des racines carrées modulo n)
  • Chiffrement et signature RSA
  • Signatures en blanc et application aux problèmes d'anonymat

Emploi du temps 2015

NATURE JOUR DEBUT FIN SALLE ENSEIGNANT EMAIL
Cours Vendredi 13:30 15:00 M1-27 Charles Bouillaguet charles.bouillaguet@univ-lille1.fr
TD15:1516:45M5 A6
TP 17:00 18-19h M5 A16 cf. semainier
Charles Bouillaguet
dernière modification : 13/01/2018 à 14:06:11

Le semainier est indicatif.

Fonctionnement des TP : vous avez dû recevoir un email d'invitation. Présence (quasi-)obligatoire la première séance. "Office-hours" = l'enseignant assure une permanence, répond aux questions et prodigue des conseils pour avancer dans le TP (présence facultative).

Séance Cours TD TP
1 19/01/2018 Chiffrement et protocoles à clef secrète TD 1 Séance de lancement
2 26/01/2018 Chiffrement à clef publique, signature électronique TD 2
3 02/02/2018 certificats, fonctions de hachage (partie I) TD 3 Office hours
4 09/02/2018 Notions de sécurité, One-time pad, modes opératoires à clef secrète TD 4 Office hours
5 16/02/2018 Chiffrement par blocs. L'AES TD 5
6 23/02/2018 Fonctions de hachage (sécurité, fonctionnement) TD 6 Office hours
02/03/2018 "interruption pédagogique" d'hiver
7 09/03/2018 Arithmétique et algorithmes pour les grands entiers. suite du cours Office hours
8 16/03/2018 Suite du cours précédent Office hours
23/03/2018 Relache cette semaine
9 30/03/2017 Logarithme discret. Échange de clef Diffie-Hellman. Chiffrement ElGamal. Signature ElGamal. TD 7 Office hours
10 06/04/2018 Construction de PRNG à partir de prédicats hardcore. Résiduosité quadratique. Bits hardcore du log discret. Problème [CD]DH. Sécurité sémantique de ElGamal. TD 8 Office hours
11 13/04/2018 Chiffrement et signature de Rabbin. TD 9
12 20/04/2018 Chiffrement et signature RSA TD 11 Office hours
27/04/2018 interruption pédagogique de printemps
04/05/2018 interruption pédagogique de printemps
11/05/2018 Relache cette semaine
TP : Relevé 100% en mai.
Charles Bouillaguet
dernière modification : 13/01/2018 à 14:20:30

L'évaluation s'effectue avec un TP et un examen en fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne des deux notes :

N = (EXAM + TP)/2

Pour la seconde session d'examen, la note de TP est conservée.

L'unité acquise apporte 5 ECTS.

Annales

  • 2017 : Examen et sa correction.
  • Charles Bouillaguet
    dernière modification : 13/01/2018 à 14:13:27

    Pointeurs

    Incontournable : le glossaire de la sécurité sur internet, par la Internet Engineering Task Force.

    Programmes grand public pour la crypto

    • Pretty Good Privacy (PGP) a été le premier programme largement distribué à contenir de la crypto raisonnablement forte. Aujourd'hui, il est exploité commercialement. Cependant, GNU Privacy Guard (GPG) est une version open-source. Ces programmes sont inter-opérables car plusieurs aspects de leur fonctionnement sont standardisés. Des plugins permettent d'envoyer des courriers électroniques signés et chiffrés de manière compatible.
    • OpenSSL (wikipédia) est une librairie open-source qui implémente des opérations crypto. Elle sert à implémenter les connection "sécurisées" dans les 2/3 des serveurs web du monde entier.
    • dm-crypt est un système de chiffrement de disque-dur incorporé dans les versions récentes du noyau Linux.

    Mécanismes de chiffrement à clef secrète

    Il en existe un bon paquet... Voici une petite liste pas exhaustive : AES, Blowfish, Camellia, CAST, DES, Triple-DES, IDEA, TEA (et ses variantes).

    Mécanismes de chiffrement à clef publique

    Là aussi il en existe de nombreux. Cependant les plus utilisés sont de très loin RSA (chiffrement et signature), ElGamal (chiffrement et signature). Les schémas de signature DSA et ECDSA sont des variantes de la signature ElGamal. On trouve aussi le Système de Rabin, utilisé par exemple dans les badges Vigik d'accès aux immeubles.

    Mécanisme de gestion des clefs publiques : certificats ou bien Réseau de confiance.

    Protocoles cryptographiques

    • Le chiffrement hybride combine les avantages des sytèmes symétriques et asymétriques.
    • Kerberos est un protocole (à clef secrète) qui permet à un utilisateur de s'identifier une seule fois, mais d'accéder ensuite à de multiples ressources en ligne de manière sûre.
    • Echange de clef : le Protocole de Needham-Schroeder pour l'échange de clef authentifié, qui fonctionne quand les deux utilisateurs possèdent leurs clefs publiques réciproques. Un protocole de "Password-based Authenticated Key-Exchange" (PAKE), qui permet de s'accorder sur une clef secrète alors qu'on ne possède en commun qu'un secret faible (un mot de passe). La méthode particulière qu'on voit en TD est en fait maintenant standardisé.
    • Le Protocole à 3 passes de Shamir permet d'envoyer un message chiffré alors qu'on ne possède aucune information commune à l'avance.

    Fonctions de hachage

    Il y a notamment MD4 (cassé), MD5 (cassé), SHA-0 (cassé), SHA-1 (bientôt cassé), SHA-2 (c'est-à-dire SHA-256 et SHA-512, sûrs), SHA-3 (sûr).

    Pour hacher un mot de passe en vue de la production d'une clef symétrique, on peut par exemple utiliser PBKDF2 une méthode standardisée qui repose sur l'utilisation d'une fonction de hachage.

    Arithmétique pour la cryptographie

    Logarithme discret

    Générateurs pseudo-aléatoires

    Bibliographie

    Aspects algorithmiques

    • The Art of Computer Programming (a.k.a. "la bible") de Donald Knuth. Ouvrage de référence sur une bonne partie de l'algorithmique. Le volume 1 contient la preuve du petit théorème de Fermat donnée en cours. Le volume 2 contient les algorithmes "classiques" pour effectuer les opérations arithmétiques, une étude approfondie de l'algorithme d'Euclide (la preuve de la complexité quadratique est un des exercices du livre), une discussions des algorithmes de tests de primalité, la méthode "rho" de factorisation, la méthode "p-1" (phases 1 et 2, en exercice), etc. etc. etc.
    • A Computational Introduction to Number Theory and Algebra de Victor Shoup. Disponible gratuitement en ligne. Contient presque tout ce qu'il faut savoir pour faire de la crypto : rappels sur les entiers, sur les congruences, sur les probabilités, etc. Contient la preuve des théorème sur le paradoxe des anniversaires, une preuve du théorème des nombres premiers, un chapitre sur la résiduosité quadratique. Les algorithmes de calcul du log discret sont décrits. Il est indiqué comment produire des nombres aléatoires dont la factorisation est connue (pratique pour obtenir des racines primitives modulo p), etc. etc. etc.

    Aspects cryptographiques

    Anciens documents

    Annales anciennes

    Ces documents sont largement périmés, dans la mesure où le contenu du cours a changé.

    Pointeurs

    Bibliographie (périmée)

    • En Français
      • Cryptographie : principes et mises en œuvre de Pierre Barthélemy, Robert Rolland et Pascal Véron. Hermes.
      • Cryptographie : théorie et pratique de Douglas Stinson, ITP/Vuibert.
      • Cours de cryptographie de Gilles Zemor, Cassini.
      • Histoire des codes secrets de l'Égypte des pharaons à l'ordinateur de Simon Singh, Lattès (Existe aussi au format poche), histoires et anecdotes.
    • En Anglais
      • A classical introduction to cryptography : applcations for communication security de Serge Vaudenay, Springer
      • Handbook of applied cryptography : Ouvrage de référence en anglais. Version PDF accessible ici.
      • The codebreakers de D. Kahn, Macmillan Publishing : histoires, anecdotes, mais aussi détails techniques.