Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cryptographie 2013 Pascal Boyer (LAGA) Universit´ e Paris 13 janvier-f´ evrier

Cryptographie 2013 Pascal Boyer (LAGA) Universit´ e Paris 13 janvier-f´ evrier 2013 Vous trouverez sur http://www.math.univ-paris13.fr/ boyer/enseignement/images.html un polycopi´ e de cours ainsi que des liens vers les trois tds. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 1 / 278 Cryptographie 2013 Pascal Boyer (LAGA) Universit´ e Paris 13 janvier-f´ evrier 2013 Vous trouverez sur http://www.math.univ-paris13.fr/ boyer/enseignement/images.html un polycopi´ e de cours ainsi que des liens vers les trois tds. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 1 / 278 1 G´ en´ eralit´ es Historique Pr´ esentation axiomatique 2 Exemples simples Codes de permutation Codes de substitution Cryptanalyse Codes polyalphab´ etiques Code de VIC 3 Codes modernes Chiﬀrement en chaˆ ınes Codes ` a conﬁdentialit´ e parfaite Registres ` a d´ ecalages Applications aux GSM et WIFI DES et AES 4 Codes ` a clefs publiques RSA El Gamal Menezes-Vanstone 5 Fonctions de Hachage Probl´ ematique Description de SHA-1 Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 2 / 278 6 Protocoles Signature et datation Certiﬁcats MAC ´ Echange de clefs Mots de passe Preuve sans transfert de connaissance Transfert inconscient Partage de secret Carte bleue SSL et TLS PGP 7 Rappels math´ ematiques Th´ eorie de la complexit´ e Division euclidienne Congruences Corps ﬁnis Petit th´ eor` eme de Fermat and c Sur les nombres premiers M´ ethode de factorisation Polynˆ omes Courbes elliptiques Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 3 / 278 G´ en´ eralit´ es Historique Historique La cryptographie ou science du secret est un art tr` es ancien qui se d´ eveloppe parall` element ` a la st´ eganographie. Scytale Sparte vers -450 AJC, (principe des codes de permutation) Code de Jules C´ esar vers -50 AJC, (principe des codes de substitution, n = n + 3) cryptanalys´ e par les arabes (9e), am´ elior´ e (ajout de blancs, mauvaise orthographe, et qui a coˆ ut´ e la vie ` a Marie Stuart (ﬁn 16e) Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 4 / 278 G´ en´ eralit´ es Historique Historique La cryptographie ou science du secret est un art tr` es ancien qui se d´ eveloppe parall` element ` a la st´ eganographie. Scytale Sparte vers -450 AJC, (principe des codes de permutation) Code de Jules C´ esar vers -50 AJC, (principe des codes de substitution, n = n + 3) cryptanalys´ e par les arabes (9e), am´ elior´ e (ajout de blancs, mauvaise orthographe, et qui a coˆ ut´ e la vie ` a Marie Stuart (ﬁn 16e) Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 4 / 278 G´ en´ eralit´ es Historique Historique La cryptographie ou science du secret est un art tr` es ancien qui se d´ eveloppe parall` element ` a la st´ eganographie. Scytale Sparte vers -450 AJC, (principe des codes de permutation) Code de Jules C´ esar vers -50 AJC, (principe des codes de substitution, n = n + 3) cryptanalys´ e par les arabes (9e), am´ elior´ e (ajout de blancs, mauvaise orthographe, et qui a coˆ ut´ e la vie ` a Marie Stuart (ﬁn 16e) Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 4 / 278 G´ en´ eralit´ es Historique Historique Code de Vigen` ere 1586 Premier chiﬀre polyalphab´ etique, invuln´ erable ` a l’analyse statistique avec un nombre immense de clef, il resta n´ eglig´ e pendant deux si` ecles lui pr´ ef´ erant des chiﬀres de substitution homophonique: l’exemple le plus remarquable est le grand chiﬀre de Louis XIV (17e) d´ echiﬀr´ e seulement ` a la ﬁn du 19e. Codes ` a r´ epertoires Tr` es anciens, utilis´ es intensivement jusqu’au d´ ebut du 20-i` eme si` ecle. Enigma: d´ ebut XXe Utilis´ ee par l’arm´ ee allemande durant la seconde guerre mondiale, d´ ecrypt´ ee par les polonais grˆ ace a une r´ ep´ etition r´ ecurrence, puis par Alan Turing via la recherche de mots probables. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 5 / 278 G´ en´ eralit´ es Historique Historique Code de Vigen` ere 1586 Premier chiﬀre polyalphab´ etique, invuln´ erable ` a l’analyse statistique avec un nombre immense de clef, il resta n´ eglig´ e pendant deux si` ecles lui pr´ ef´ erant des chiﬀres de substitution homophonique: l’exemple le plus remarquable est le grand chiﬀre de Louis XIV (17e) d´ echiﬀr´ e seulement ` a la ﬁn du 19e. Codes ` a r´ epertoires Tr` es anciens, utilis´ es intensivement jusqu’au d´ ebut du 20-i` eme si` ecle. Enigma: d´ ebut XXe Utilis´ ee par l’arm´ ee allemande durant la seconde guerre mondiale, d´ ecrypt´ ee par les polonais grˆ ace a une r´ ep´ etition r´ ecurrence, puis par Alan Turing via la recherche de mots probables. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 5 / 278 G´ en´ eralit´ es Historique Historique Code de Vigen` ere 1586 Premier chiﬀre polyalphab´ etique, invuln´ erable ` a l’analyse statistique avec un nombre immense de clef, il resta n´ eglig´ e pendant deux si` ecles lui pr´ ef´ erant des chiﬀres de substitution homophonique: l’exemple le plus remarquable est le grand chiﬀre de Louis XIV (17e) d´ echiﬀr´ e seulement ` a la ﬁn du 19e. Codes ` a r´ epertoires Tr` es anciens, utilis´ es intensivement jusqu’au d´ ebut du 20-i` eme si` ecle. Enigma: d´ ebut XXe Utilis´ ee par l’arm´ ee allemande durant la seconde guerre mondiale, d´ ecrypt´ ee par les polonais grˆ ace a une r´ ep´ etition r´ ecurrence, puis par Alan Turing via la recherche de mots probables. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 5 / 278 G´ en´ eralit´ es Historique Principe de Kerckhoﬀs Jusqu’au milieu du XXe si` ecle, la s´ ecurit´ e d’un chiﬀre reposait sur le secret de son fonctionnement. Le probl` eme est que d` es que ce secret est ´ event´ e, cf. par exemple le chiﬀre de VIC, il faut changer enti` erement le cryptosyst` eme ce qui est complexe et couteux. Principe de Kerckhoﬀs La s´ ecurit´ e d’un cryptosyst` eme ne repose pas sur le secret du cryptosyst` eme mais seulement sur la clef du cryptosyst` eme qui est un param` etre facile ` a transmettre secr` etement et ` a changer, de taille r´ eduite (actuellement de 64 ` a 2048 bits). Loin d’aﬀaiblir la s´ ecurit´ e du chiﬀre, la diﬀusion du fonctionnement d’un cryptosyst` eme analys´ e par le plus grand nombre, permet, en l’´ eprouvant, de valider sa s´ ecurit´ e ou ` a d´ efaut, renseigne sur l’urgence d’en changer. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 6 / 278 G´ en´ eralit´ es Historique Principe de Kerckhoﬀs Jusqu’au milieu du XXe si` ecle, la s´ ecurit´ e d’un chiﬀre reposait sur le secret de son fonctionnement. Le probl` eme est que d` es que ce secret est ´ event´ e, cf. par exemple le chiﬀre de VIC, il faut changer enti` erement le cryptosyst` eme ce qui est complexe et couteux. Principe de Kerckhoﬀs La s´ ecurit´ e d’un cryptosyst` eme ne repose pas sur le secret du cryptosyst` eme mais seulement sur la clef du cryptosyst` eme qui est un param` etre facile ` a transmettre secr` etement et ` a changer, de taille r´ eduite (actuellement de 64 ` a 2048 bits). Loin d’aﬀaiblir la s´ ecurit´ e du chiﬀre, la diﬀusion du fonctionnement d’un cryptosyst` eme analys´ e par le plus grand nombre, permet, en l’´ eprouvant, de valider sa s´ ecurit´ e ou ` a d´ efaut, renseigne sur l’urgence d’en changer. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 6 / 278 G´ en´ eralit´ es Historique Principe de Kerckhoﬀs Jusqu’au milieu du XXe si` ecle, la s´ ecurit´ e d’un chiﬀre reposait sur le secret de son fonctionnement. Le probl` eme est que d` es que ce secret est ´ event´ e, cf. par exemple le chiﬀre de VIC, il faut changer enti` erement le cryptosyst` eme ce qui est complexe et couteux. Principe de Kerckhoﬀs La s´ ecurit´ e d’un cryptosyst` eme ne repose pas sur le secret du cryptosyst` eme mais seulement sur la clef du cryptosyst` eme qui est un param` etre facile ` a transmettre secr` etement et ` a changer, de taille r´ eduite (actuellement de 64 ` a 2048 bits). Loin d’aﬀaiblir la s´ ecurit´ e du chiﬀre, la diﬀusion du fonctionnement d’un cryptosyst` eme analys´ e par le plus grand nombre, permet, en l’´ eprouvant, de valider sa s´ ecurit´ e ou ` a d´ efaut, renseigne sur l’urgence d’en changer. Pascal Boyer (Universit´ e Paris 13) Cryptographie 2013 janvier-f´ evrier 2013 6 / 278 G´ en´ eralit´ es Historique Codes modernes On peut distinguer deux grandes familles de codes classiques: Codes ` a uploads/Litterature/ cours-crypto2013-pdf.pdf