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é pendant 1h chaque semaine.

Crédits

Valider le cours rapporte 5 ECTS.
Charles Bouillaguet
dernière modification : 03/09/2016 à 13:47:27

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 2017

NATURE JOUR DEBUT FIN SALLE ENSEIGNANT EMAIL
Cours Jeudi 13:30 15:00 M5 A4 Charles Bouillaguet charles.bouillaguet@univ-lille1.fr
TD 15:15 16:45
SAV du TP 17:00 18:00 M5 A11
Charles Bouillaguet
dernière modification : 03/09/2016 à 12:37:13
Le semainier est indicatif. Les dates et le programme sont susceptibles de changer (notamment en fonction de la position des vacances).
Séance Cours TD TP
1 Chiffrement et protocoles à clef secrète

Nouvelle formule !

Il y a UN SEUL jeu vidéo TP pendant tout le semestre.

Chaque semaine, le SAV du TP est assuré pendant 1h.

Présence facultative : passer en cas de problème.

2 Chiffrement à clef publique, signature électronique TD 1
3 certificats, fonctions de hachage (usage) TD 2
4 Notions de sécurité, One-time pad, modes opératoires à clef secrète TD 3
5 Chiffrement par blocs. L'AES (les dessins) TD 4
"interruption pédagogique" d'hiver
6 Fonctions de hachage (sécurité, fonctionnement) TD 5
Relache cette semaine
DS #1 (et la feuille à remplir). - la correction pas TD
7 Arithmétique et algorithmes pour les grands entiers. suite du cours
8 Test et preuve de primalité. Logarithme discret. Échange de clef Diffie-Hellman. Chiffrement ElGamal. TD 6
9 Signature ElGamal. Construction de PRNG à partir de prédicats hardcore. TD 7
interruption pédagogique de printemps
interruption pédagogique de printemps
10 Résiduosité quadratique. Bits hardcore du log discret. Problème [CD]DH. Sécurité sémantique de ElGamal. >TD 8 (méthode rho)
11 Chiffrement et signature de Rabbin. TD 11
12 Chiffrement et signature RSA TD 12
DS #2 - la correction
seconde session - la correction
Charles Bouillaguet
dernière modification : 03/09/2016 à 13:46:39

L'évaluation s'effectue avec deux DS et un TP : DS1 à mi-parcours et DS2 en fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne pondérée des notes de DS et de la note de TP :

N = (DS1 + DS2 + 2*TP)/4

Le TP, qui a lieu entièrement en-ligne, est évalué automatiquement.

Pour la seconde session d'examen, les deux DS sont remplacés par le rattrapage et la note de TP est conservée.

Charles Bouillaguet
dernière modification : 03/09/2016 à 12:37:12

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

Annales

  • 2015 : DS #1 et sa correction. DS #2 et sa correction.

    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.