Cryptographie symétrique
Cours du Master 2 MIC, Mathématiques, Informatique et application à la
Cryptologie.
Année 2021-2022
Séances le mardi en alternance avec celles de cryptographie asymétrique : TP le mardi 9h00-12h00 salle 2006 à partir du 5/10 et cours le mardi 13h00-15h00 salle 2018 à partir du 28/09/2021 toutes les deux semaines, pour le premier semestre (jusqu'au 14/12, voir plus tard pour les horaires de janvier-février). Le TP du 2/11 est déplacé le vendredi 13h30-16h30, même salle (2006).
Évaluation : 5/10*examen + 3/10 *TP +2/10*exposé
- Semaine 1 :
- Vendredi 24/09/2021, 9h30-12h30, salle 2006 : séance préliminaire
- Corps finis ; élément primitif (au sens racine primitive de l'unité), polynôme primitif (au sens polynôme minimal d'un élément primitif) ; il existe φ(pn-1)/n polynômes primitifs de degré n sur Fp.
- Fiche du premier TD (polynômes
irréductibles) ; programmation : calcul sur les polynômes
sur F2 et sur les corps finis de
caractéristique 2, recherche de polynômes irréductibles et
primitifs.
- Réaliser la petite bibliothèque sur le calcul des
polynômes de degré < 64 en caractéristique 2 décrite dans
le répertoire tp1 du dépôt gitlab
M2MIC_CrSym/public (voir les .h) et
recopiée dans vos répertoires. Chaque fonction doit être
testée. Le tout est à remettre sur gitlab dans un répertoire
tp1 dans le dépôt qui vous est attribué (voir ci-dessous).
Pour pouvoir vérifier la correction du test d'irréductibilité
et du test de primitivité, fournir un utilitaire qui compte
directement (en utilisant le test) le nombre de polynômes
irréductibles d'un degré donné (passé en entrée), de même
pour le nombre de polynômes primitifs.
Un tel programme n'a que valeur de test : vous pouvez vérifier
le calcul en utilisant la fonction d'Euler et la
fonction de Möbius (cf. feuille de TD).
Makefile obligatoire, vous pouvez vous inspirer de
l'un des deux distribués (à modifier et/ou
compléter).
Première partie (jusqu'à la fonction de dérivation) à
déposer au plus tard le 09/10/2021 (avec tests et
makefile fonctionnel) ; à terminer avant le
23/10/2021.
- Semaine 2 (28/09/2021) :
- cours 13h00-15h00 salle 2018.
-
Exemples d'utilisation de la cryptographique symétrique dans une
une session https.
- Les systèmes cryptographiques, le principe de Kerckhoffs
(Auguste Kerckhoffs, Cryptographie militaire, Journal
des sciences militaires, janvier et février 1883). La
cryptographie classique : substitutions (exemple du chiffre de
César), et permutations (ou transpositions). Attaques à texte
chiffré seul connu ; attaque à texte clair connu.
-
Chiffrements par composition de
substitutions et permutations ; confusion et
diffusion.
- Le chiffrement
de Vigenère ; la méthode de Kasiski ; indice
de coïncidence.
- Semaine 3 (5/10/2021) :
- TP 9h00-12h00 salle 2006.
-
indices de coïncidence mutuelle : définition et application au décryptage de Vigenère (voir exercices de cryptographie
classique). Exercice à rédiger et rendre au plus tard le 01/11/2021 :
une résolution par la méthode des indices de coïncidence de
d'un cryptogramme de l'exercice 11, expliquée de façon que
quelqu'un à qui la méthode n'a jamais été présentée puisse
comprendre (en particulier vous devez utiliser les binaires
distribués, mais il ne s'agit pas d'écrire un mode d'emploi).
- Le chiffrement de Vernam. Théorie de Shannon (C. E. Shannon,
"Communication Theory of Secrecy Systems") : la confidentialité
parfaite, définition, le chiffrement de Vernam à confidentialité
parfaite ; théorème de Shannon.
- Semaine 4 (12/10/2021) :
- cours 13h00-15h00 salle 2006 SG.
- Entropie, entropie conditionnelle ; clefs parasites, distance
d'unicité (résumé en feuille 3).
- Fiche du troisième TD.
-
Introduction aux chiffrements par flot : fonctionnement et utilisation ; période de la suite chiffrante ; renouvellement des clefs ; chiffrements à flots synchrones et auto synchronisants.
- Semaine 5 (19/10/2021) :
- TP 9h00-12h00 salle 2006.
- LFSR (Linear Feedback Shift Register, registre à décalage à
rétroaction linéaire) et suites récurrentes linéaires sur un corps
fini Fq : définition, écriture
matricielle ; la suite est périodique à partir d'un certain rang ;
si la matrice de la suite est inversible, elle est périodique.
-
Propriétés statistiques d'une suite de période de longueur
maximale ;
l'initialisation (0, ... ,0,1) (séquence d'impulsion)
donne toujours une période maximale, pour une relation de
récurrence donnée ;
LFSR : polynôme caractéristique ; cas où
celui-ci est irréductible ; s'il est primitif la période de la
suite est de longueur maximale qm-1
pour un LFSR de taille m dès que l'initialisation est
non nulle.
- Fiche du quatrième TD.
- Semaine 6 (26/10/2021) :
- cours 13h00-15h00 salle 2018.
- Anneau des séries formelles ; Série génératrice d'une suite
sur Fq
- une suite engendré par un LFSR de taille m sur
Fq est de période maximale
qm-1 si et seulement si le polynôme caractéristique (ou
son polynôme réciproque, le polynôme de connexion) est primitif.
- numérateur de la fraction rationnelle représentant la série génératrice de la suite décalée de n ; relation de récurrence satisfaite par ses coefficients ; mode Galois pour le fonctionnement d'un LFSR.
-
Exercices de programmation 9 de la
feuille 4 à remettre le 22/11/2021 sur github : makefile
obligatoire ; voir le fichier
attendu.txt pour des
précisions.
- Semaine 7 ( 2/11/2021) :
- TP déplacé le vendredi 5/11 13h30-16h30 salle 2006.
- Fiche du cinquième TD (algorithme de Berlekamp-Massey).
- Description sommaire de A5/1.
- Matrices de Hankel.
Complexité linéaire, profil de complexité linéaire ; propriétés du profil de complexité linéaire ; algorithme de Berlekamp-Massey.
- Semaine 8 ( 9/11/2021) :
- cours 13h00-15h00 salle 2018.
- Propriété du profil de complexité linéaire et algorithme de Berlekamp-Massey ; la complexité de l'algorithme est quadratique en la taille de l'entrée.
- Semaine 9 (16/11/2021) :
- TP 9h00-12h00.
-
Fiche du sixième TD.
-
Chiffrements à flot utilisant des LFSR ; combinaison booléenne de
LFSR ; fonction de filtrage sur le vecteur d'état ; attaques par corrélations : exemple du générateur de Geffe.
- Fonctions booléennes : forme normale algébrique ;
fonctions booléennes équilibrées, résistantes aux
corrélations à l'ordre m, m-résilientes ; compromis nécessaire entre le degré de la forme algébrique normale et la résistance aux corrélations.
- Semaine 10 (23/11/2021) :
- cours 13h00-15h00 salle 2018.
- Feuille d'exercice 6 : construction de fonctions m-résilientes de degré maximal ; transformée de Hadamard-Walsh.
- à rendre pour le 13/12/2021 : programmer
et tester l'algorithme de Berlekamp-Massey (conditions précisées
exercice 9, feuille 5)
- Semaine 11 (30/11/2021) :
- TP 9h00-12h00.
- Inégalité de Parceval traduite en termes de corrélations ; théorème de Xiao-Massey ; un autre procéde de combinaison des LFSR : description rapide de E0 (chiffrement du Bluetooth) ; attaques sur les chiffrements par flot par compromis temps-mémoire, chaînage des chiffrements, points distingués, tables arc-en-ciel, faiblesses liées au protocole etc.
- Chiffrement par bloc : brève introduction, modes opératoires et comparaison (exercice 2 de la feuille 7).
-
Fiche du septième TD
-
Source du chiffrement AES dans openssl.
- Semaine 12 (7/12/2021) :
- cours 13h00-15h00 salle 2018.
- Chiffrements par bloc, principes (confusion-diffusion,
substitution-permutation ...), modes opératoires ; conception
des chiffrements par bloc : S-box, P-box, tour ;
SPN purs (ex. AES) et schéma de Feistel (ex. DES) ; la procédure d'ordonnancement et de diversification de clefs (key schedule) du DES ;
- Semaine 13 (14/12/2021) :
- TP 9h00-12h00.
- Une propriété de la sbox de l'AES liée à l'attaque différentielle : exercice 11 de la feuille 7 ; implémentation en logiciel de l'AES ; procédure de diversification des clefs (key schedule)
- Attaque différentielle sur les chiffrements par bloc expliquée
sur un exemple de chiffrement par bloc simplifié de type SPN
(cf. article de Heys, lien indiqué en bibliographie).
- Semaine 14 (4/01/2022) 2 séances :
- cours 13h15-15h15 salle 2018
- Attaque différentielle (suite) et
attaque linéaire sur les chiffrements par bloc, piling-up
lemma ; mise en de l'attaque œuvre sur l'exemple du
chiffrement de Heys.
-
TP mercredi 5/01 9h30-12h30 salle 2004
- Fiche du huitième
TD (implémentation de l'attaque différentielle sur le chiffrement de Heys).
- Le TP sur l'analyse différentielle est à rendre pour le 01/02/2021 (vous devez trouver la clef utilisée par le binaire (linux 64 bits)
fourni dans vos répertoires git, répertoire tp5 (l'attribution des binaires de chiffrement est donnée aussi dans le répertoire tpdiff).
- Semaine 15 (11/01/2022) 2 séances :
-
cours mardi 13h15-15h15, salle 2018
-
TP mercredi 5/01 8h30-11h30 salle 2004
-
Fonctions de hachage cryptographiques, introduction :
propriétés cryptographiques, utilisation ; fonctions de
hachage cryptographiques, simples, et avec clef ; résistance à
la recherche de préimage (difficulté à inverser), d'une
seconde préimage, de collisions ; algorithme probabiliste,
modèle de l'oracle aléatoire ; attaque des anniversaire ;
"réduction" de la recherche de collision à la recherche de
l'inverse par un algorithme probabiliste.
- Semaine 16 (18/01/2022) :
-
cours 13h15-15h15 (mardi, salle 2018)
-
Les fonction de hachage md5, sha1, sha2, schéma itératif, schéma de
Merkle-Damgard : si la fonction de compression résiste aux collisions, la
fonction de hachage construite par ce schéma résiste aux collisions. Attaques par extension de longueur, attaques à préfixe choisi sur les fonctions de hachage itératives (md5, sha1).
- Semaine 17 (25/01/2022) :
-
9h-12h salle 2006
-
Authentification ; composition authentification et
confidentialité ; codes d'authentification (MAC), faux (forgery), existential/selective forgery, (ε, q)-faux ; construction
d'un MAC pour des données de longeur arbitraire à partir d'une
fonction de hashage itérative : HMAC ; construction d'un MAC (pour des données de taille fixe) à partir d'un chiffrement symétrique : CBC-MAC (données de taille arbitraire : CMAC juste mentionné).
- Semaine 18 (1/02/2022) :
- Semaine 19 (8/02/2022) :
- Soutenances exposés, 9h-12H salle 2006.
- Semaine 20 (15/02/2022) :
- Semaine 21 (22/02/2022) :
- Examen mardi 22/02, 9h00-12h00, salle 2006
Dépôt gitlab
Vous aurez accès durant l'année à un
dépôt gitlab
qui vous permet, par exemple, de sauvegarder votre travail en TP.
Les exercices, programmes à rendre sont à remettre sur ce dépôt gitlab.
Procédure :
En début d'année
à faire le plus rapidement possible !
- vous devez avoir créé au préalable votre compte pour les salles TP sur le site https://stp.math.univ-paris-diderot.fr ;
- vous devez ensuite vous connecter une première fois sur le serveur gitlab en sélectionnant l'authentification ldap ;
-
vous me communiquez ensuite par mail votre nom
d'utilisateur sur le dépôt (sujet du message : [M2MIC]...), qui est a priori votre nom d'utilsateur dans les salles TP ;
-
dans un second temps sera créé pour chacun d'entre vous un projet M2MIC_CrSym/<nom-de-login>, dont vous serez contributeur.
En cours d'année
-
Vous aurez alors à remettre votre travail sur ce projet,
dans un sous-répertoire tp{n} où {n} est le numéro du tp (tp1, tp2, ...) ; tp en minuscule ! Respectez la casse ;
-
un makefile doit être présent, qui permet de compiler tous vos
programmes. Ceux-ci doivent être accompagnés :
- d'un mode d'emploi minimal (readme) au format txt ;
-
d'un rapport : compte-rendu de comment vous avez procédé, tests et
résultats de ceux-ci... au format txt ou pdf.
- Vos programmes seront testés sous linux : vous pouvez vérifier dans les salles de TP que tout fonctionne.
L'utilisation de gitlab est obligatoire ! En particulier pas d'envoi par mail ! Évidemment vos programmes ne doivent pas être rendus sous forme compressée.
Bibliographie.
Ouvrages généralistes.
- Douglas R. Stinson Cryptographie Theory and practice,
Chapmann & Hall 1995 (première édition), 2006 (3ème édition), une
traduction française des deux premières éditions existe. Les trois
éditions sont assez différentes, la troisième édition reprend en
première partie la seconde édition.
- Alfred Menezes, Paul J. van Oorschot et Scott A. Vanstone,
Handbook of applied cryptography, CRC Press, 1997, une version
électronique est en accès libre.
- Gille Zémor, cours de Cryptographie, ed. Cassini 2000.
Références par sujet (compléments).
Langage C
Protocole SSL/TLS
- les premières spécifications de SSL (2.0, 3.0), développé par
netscape, accessibles sur le site
de la fondation mozilla.
-
TLS (version 1.3) est spécifié par la rfc8446 (site de
l'IETF) ; pour la première version 1.0, héritière directe de SSL 3,
voir la rfc2246.
Aspects historiques, théorie de Shannon.
En plus des livres de Stinson et Zémor, et du
"Handbook of applied cryptography"
Chiffrements à flot
En plus du livre de Zémor et du "Handbook of
applied cryptography"
- Andreas Klein "Stream Ciphers', Springer, 2013.
- plusieurs articles (vulgarisation, extraits d'encyclopédie, rapports de synthèse ...) sur
la page web d'Anne
Canteaut.
-
Michel Demazure "Cours d'algèbre, primalité, divisibilité,
codes", Cassini, 1997 (cours d'algèbre avec un point de vue
algorithmique, mais rien sur les LFSR et la cryptographie en général).
- Rudold Lidl et Harald Niederreiter "Introduction to finite
fields and their applications", Cambridge University press 1994,
ou "Finite Fields", Addison Wesley 1983 (chapitre "Linear recuring
Sequences" à peu près identiques dans les deux livres), point de
vue algébrique, très complet.
- Rainer A. Rueppel, "Analysis and design of Stream Ciphers", Springer-Verlag 1986 ; (étude en particulier du filtrage et de la composition des LFSR, résistance aux corrélations ....).
- La page du projet européen eSTREAM (2004-2008), analyses
et recommandations pour des chiffrements à flot de conception
récente.
- Sur A5/1, chiffrement du GSM :
-
Elad Barkan, Eli Biham, Nathan Keller, "Instant Ciphertext-Only
Cryptanalysis of GSM Encrypted Communication", 2006 (version longue d'un
papier de 2003), attaques sur A5/2, A5/1, récapitulatif des attaques existantes, "man in the middle attack", ...
- Karsten Nohl "Attacking
phone privacy" (2010), présentation rapide de l'attaque
sur le GSM, et des attaques par compromis temps-mémoire.
Fonctions booléennes.
Chiffrements par bloc.
En plus du livre de Stinson, et du "Handbook of applied cryptography",
Fonctions de hashage.
En plus du livre de Stinson, et du "Handbook of applied cryptography",
- La spécification des algorithmes de la famille SHA fips180-4 (révision d'août 2015).
- Fonctions de hachage cryptotographique avec clef : HMAC
(Keyed-Hash Message Authentication Code) fips198-1
(révision de juillet 2008).
- Le site du Cryptographic
hash project, concours organisé par le NIST pour une
nouvelle famille de fonctions de hachage cryptographiques (SHA3).
- Le standard fips202 pour les fonctions de la famille SHA3 (août 2015).
Autres
dernière modification : mardi 25 janvier 2022 13:39:47 CET