IN420 – Algorithmique pour la cryptographie

Informations pratiques

Chargé de cours: Luca De Feo http://defeo.lu

Chargée de TD: Christina Boura http://christina-boura.info/

Cours magistral: Lundi 15h15 - 16h45, amphi H

TD: Mardi 13h30 - 16h45, salle G101

Cours

Cours 1 (20/01/2013): Types de données en Java.
Cours 2 (27/01/2013): Codage ASCII, UTF-16.
Cours 3 (03/02/2013): UTF-8, Codage de Huffman, Codes instantanés, Compression.
Cours 4 (10/02/2013): Chiffrement par substituion.
Cours 5 (17/02/2013): Notions de sécurité, Chiffrement par transposition.
Cours 6 (03/03/2013): Chiffrement par flot, LFSR.
Cours 7 (10/03/2013): Codes correcteurs d’erreurs.
Cours 8 (17/03/2013): Codes de Hamming.
Cours 9 (31/03/2013): Forme systématique, Décodage syndrome
Cours 10 (07/04/2013): Cryptographie asymétrique, Arithmétique modulaire.
Cours 11 (14/04/2013): Algorithme d’Euclide étendu et Inversion modulaire.
Cours 12 (28/04/2013): RSA.

TDs

TD 1 (28/01/2013): Traitement de texte en Java via le terminal.
TD 2 (04/02/2013): Coder et décoder en UTF-8 et UTF-16.
TD 3 (11/02/2013): Coder et décoder en UTF-8 et UTF-16.
TD 4 (18/02/2013): Construction du code de Huffman.
TD 5 (04/03/2013): Algèbre linéaire et chiffre de Hill.
TD 6 (11/03/2013): Bit twiddling et LFSR.
TD 7 (18/03/2013): Codes linéaires.
TD 8 (25/03/2013): Codes linéaires.
TD 9 (01/04/2013): Codes linéaires.
TD 10 (08/04/2013): Arithmétique modulaire.
TD 11 (15/04/2013): Torus Wars.
TD 12 (29/04/2013): Révision examen.

Devoirs maison

DM 1 (à rendre le 09/03/2014): Compression LZ78 et son challenge.
DM 2 (à rendre le 07/04/2014): Chiffre VIC, avec son challenge.
DM 3 (à rendre le 07/05/2014): Méthode p – 1, avec son challenge.

Anciens devoirs

Codage et décodage avec Huffman et son challenge.
Cryptanalyse de Vigenère et son challenge.
Pas de bébé et pas de géant et son challenge.
Décodage par syndrome, avec son challenge.
Test de Miller-Rabin, avec son challenge.

Bibliographie essentielle.

Travaillez ces chapitres, et vous validerez le cours sans problèmes.

Codage source : J.-C. Chappelier. Introduction à la Théorie de l’Information et ses applications. Chapitre 2.
Cryptographie symétrique : D. Stinson. Cryptographie – Théorie et pratique. Chapitre 1. P. Vigoureux. Comprendre les codes secrets. Chapitre 2.
Codes correcteurs d’erreurs: B. Martin. Codage, cryptologie et applications. Chapitres 3-5. Ou J.-C. Chappelier. Introduction à la Théorie de l’Information et ses applications. Sections 6.1, 6.2.
Cryptographie asymétrique: J. A. Buchmann. Introduction à la cryptographie. Chapitre 8.
Arithmétique modulaire: J. Vélu. Méthodes Mathématiques pour l’Informatique. Chapitres 15-16, vous pouvez sauter la section 16.2.

Vous pouvez retrouver ces références à la BU (voir ci-dessous). Le cours de J.-C. chappelier est ici : http://icwww.epfl.ch/~chappeli/it/courseFR/index.php?shownav=yes. Allez aussi voir cette page.

Liens et pages utiles

Entrées-Sorties en Java.
Endianness.
Les APIs Java: http://docs.oracle.com/javase/6/docs/api/
La machine virtuelle Linux du département d’info, avec un environnement configuré pour ce cours.

Sujets d’examen

Le partiel 2014.
Le partiel 2013 session de rattrapage, avec solution.
Le partiel 2013 avec solution.
Le partiel 2012 session de rattrapage, avec solution.
Le partiel 2012 avec solution.

Bibliographie

Pour se rafraîchir la mémoire sur java

J. Brondeau. Introduction à la programmation en Java.: Côte BU: 005.13jav BRO. Un peu daté, mais toujours d’actualité. Couvre bien les aspects de Java en tant que langage orienté aux objets. Le chapitre 8 traite en détail les flux d’entrée/sortie.

Ces références concernent la cryptographie, les codes et les algorithmes.

F. Bavaud, J.-C. Chappelier, J. Kohlas. Introduction à la Théorie de l’Information et ses applications.: Cours EPFL. version 2.4FR. http://icwww.epfl.ch/~chappeli/it/courseFR/index.php?shownav=yes.
P. Vigoureux. Comprendre les codes secrets.: Ellipses, Paris, 2010. ISBN: 978–2–7298–5368–6. Côte BU: 005.82 VIG. Ouvrage d’introduction à la cryptographie. Très simple à lire.
D. Stinson. Cryptographie – Théorie et pratique.: 2e édition. Vuibert, Paris, 2003. ISBN: 2-7117-4800-6. Côte BU: 005.82 STI. Ouvrage d’introduction à la cryptographie, d’un niveau tout à fait adapté à la licence. Une bonne partie du cours se base sur ce livre.
B. Martin. Codage, cryptologie et applications.: Presse polytechniques et universitaires romandes. ISBN: 2-88074-569-1. Côte BU: 005.82 MAR. Autre ouvrage d’introduction couvrant une bonne partie du cours. Les leçons sur les codes correcteurs suivent de près de ce livre.
Cryptographie & codes secrets.: Éditions POLE, 2006. Hors-Série Tangente 26. ISSN: 09870806. Côte BU: 008.82 CRY. Ouvrage de divulgation non-technique, recouvrant une partie du cours. Surtout les chapitres introductifs sur la cryptographie classique sont assez riches pour être utilisés comme matériel d’étude à la place du Stinson (qui est moins verbeux, mais plus technique).
J. A. Buchmann. Introduction à la cryptographie.: 2e édition. Dunod, 2006. ISBN 2-10-049622-0. Côte BU: 005.82 BUC. Texte d’introduction à la cryptographie pour mathématiciens, avec exercices. Les deux premier chapitres font un panorama complet des algorithmes qu’on utilisera pour la Cryptographie asymétrique.
D. Barsky. Notes de cours de Cryptographie.: http://www.math.univ-paris13.fr/~barsky/enseignement/cours-crypto-070206.pdf. Très bon poly couvrant quasiment toutes les notions de cryptologie abordés en cours, et plus.

Ces références concernent les algorithmes et les mathématiques. On indique les chapitres importants pour le cours.

J. Vélu. Méthodes Mathématiques pour l’Informatique.: 4e édition. Dunod, 2005. ISBN 2-10-049149-0. Côte BU: 004.01 VEL. Chapitres 15 (division, pgcd et nombres premiers) et 16 (entiers modulaires), annexes B (algèbre linéaire) et C (calcul matriciel).
J. Vélu, G. Avérous, I. Gil, F. Santi. Mathématiques pour l’Informatique.: Dunod 2008. ISBN 978-10-052052-7. Côte BU: 004.01 MAT. Livre d’exercices qui complète la référence précédente.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, X. Cazin Introduction à l’algorithmique.: Dunod 1994. ISBN 2-10-001933-3. Côte BU: 005.1 COR. Chapitres 28 (algèbre linéaire et calcul matriciel), 31 (arithmétique des entiers) et 34 (NP-complétude). Texte archi-classique, à lire absolument.
T. Brugère, A. Mollard. Mathématiques à l’usage des informaticiens.: Ellipses, 2003. ISBN 2-7298-1399-3. Côte BU: 004.01. Chapitres 8 (calcul matriciel et algèbre linéaire), 10 (arithmétique des entiers) et 11 (cryptographie). Ce livre se place à un niveau plus élevé que celui de Vélu.

Ouvrages de divulgation et autres.

D. Kahn. The Codebreakers. The Comprehensive History of Secret Communication from Ancient Times to the Internet.: Second edition. Scribner, 1996. ISBN: 978–0684831305. Côte BU 005.82 KAH. Ouvrage de divulgation classique sur la cryptographie classique (i.e. jusqu’à la fin de la deuxième guerre). Absolument pas un manuel de cours, mais une lecture passionnante pour le mordu de crypto. Malheureusement le livre n’a jamais été complètement traduit en français, à ma connaissance.
N. Stephenson. Cryptonomicon.: Avon, 2002. ISBN: 978-0060512804. Des explosions, du sang, du sexe et des octets. Tous les éléments classiques d’un blockbuster américain, savamment mélangés avec l’histoire de la deuxième guerre, des débuts d’Internet, de Alan Turing et de sa bande de codebreakers à Bletchley Park. Cryptonomicon est un roman de fiction (1168 pages) parsemé de clins d’œil aux experts de crypto et sécurité. Il risque plutôt de vous faire perdre des précieuses heures de travail que de vous faire valider le cours, mais puisque il a déjà suscité plus d’une vocation, je n’hésite pas à le conseiller.
S. Vaudenay. La fracture cryptographique.: Presses polytechniques et universitaires romandes, 2011. ISBN: 978-2-88074-830-2. Côte BU: 005.82 VAU. Ouvrage non-technique dressant le paysage de techniques cryptographiques modernes. Il contient très peu de maths, très peu de formules et beaucoup d’études de cas. Son contenu est presque complètement disjoint de celui du cours, mais l’étudiant passionné qui souhaite s’orienter vers une spécialisation en sécurité y trouvera des nombreuses informations et pistes de réflexion.