Initiation à la cryptographie

Couverture
Page de titre
Introduction
1 Les nombres premiers
1.1 Nombres premiers
1.2 Crible d'Ératosthène
1.3 Facteurs premiers
1.4 Complexité, liste des nombres premiers, spirale d'Ulam
1.4.1 Notion de complexité algorithmique
1.4.2 Liste des nombres premiers
1.4.3 La spirale d'Ulam
1.5 Décomposition en facteurs premiers
1.6 Exercices
2 Éléments d'arithmétique
2.1 Congruences dans Z
2.1.1 Introduction
2.1.2 Congruence
2.1.3 Ensemble quotient Z/nZ
2.1.4 Structure algébrique de Z/nZ
2.1.5 Groupe, anneau et corps
2.1.6 Relation d'équivalence
2.2 Cryptographie: César, Vigénère, permutation (Programmation)
2.2.1 Système de cryptographie de César
2.2.2 Système cryptographique de Vigenère
2.2.3 Permutations alphabétiques
2.3 Divisibilité dans Z
2.3.1 Idéal des multiples de a : (a)
2.3.2 Divisibilité et idéaux de Z
2.3.3 PPCM
2.3.4 PGCD
2.3.5 Le Théorème de Gauss
2.4 PGCD, PPCM et Maple (Programmation)
2.5 Retour aux nombres premiers
2.6 Exercices
2.7 Éléments inversibles de Z/nZ
2.7.1 Indicateur d'Euler
2.7.2 Petit Théorème de Fermat
2.8 Applications et pratique
2.8.1 Cryptographie et algèbre linéaire
2.8.2 Calcul de a^x mod n et le théorème de Fermat
2.8.3 Test de non primalité
2.8.4 Calcul de a^x « à la main ». Notion de cycle
3 L'algorithme d'Euclide étendu
3.1 Présentation de l'algorithme
3.2 Euclide étendu, inverse de a dans Z/nZ (Programmation)
3.2.1 Euclide étendu
3.2.2 Inverse de a dans Z/nZ
3.3 Exercices
4 Le logarithme discret
4.1 Racine primitive
4.2 Critère de primalité de Lehmer
4.3 Racine primitive, grands nombres premiers (Programmation)
4.3.1 Recherche de racine primitive
4.3.2 Recherche de grands nombres premiers
5 Cryptosystèmes
5.1 Exemples de cryptosystèmes classiques
5.1.1 Trois exemples
5.1.2 N-gramme substitution
5.1.3 Permutation d'ordre d
5.1.4 Playfair Cipher
5.1.5 Transformation linéaire
5.1.6 La machine Enigma
5.2 Casser un cryptosystème
5.3 Différents niveaux d'attaque
5.4 Masque jetable, Vernam (One time pad)
5.5 Cryptographie quantique
5.6 La Cryptographie militaire (1883), Kerckhoffs
5.7 Communication Theory of Secrecy Systems, Shannon
5.8 Convertir du texte en nombre (Programmation)
6 Fonctions à sens unique
6.1 Fonctions à sens unique
G.2 Sac à dos, Protocole DH, ..., chiffre de Rabin
6.2.1 Partage de clés : protocole DH
6.2.2 Un cryptosystème sans clé
6.2.3 Un cryptosytème à clé publique
6.2.4 Algorithme du sac à dos
6.2.5 Le chiffre de Rabin
6.3 Implémentation avec Maple (Programmation)
6.3.1 Le sac à dos
6.3.2 Partage de clés
6.3.3 Cryptosystème sans clé
6.4 Le théorème chinois et le chiffre de Rabin (Théorie et programmation)
6.4.1 Le théorème du reste chinois
6.4.2 Le chiffre de Rabin
7 Le RSA
7.1 Le système RSA
7.2 RSA et Maple (Programmation)
8 Le DES
8.1 L'algorithme LUCIFER : notion de ronde
8.2 Le DES
8.3 IDEA
8.4 Modes de chiffrement par bloc. Mode ECB, CBC, CFB, OFB
8.5 Ou exclusif et addition modulo 2 (Programmation)
8.6 Addition modulo 2 16
9 Identification, Authentification, Signature
9.1 Protocole
9.2 Identification
9.3 Protocole ZK : Zero knowledge
9.4 Le démon de Quisquater et Guillou
9.5 Protocole de Fiat-Shamir
9.6 Authentification
9.7 Fonction de hachage
9.8 Signature
10 Advanced Encryption Standard (AES)
10.1 Introduction
10.2 Les corps finis (Théorie)
10.2.1 Construction de GF(2⁸)
10.2.2 L'anneau GF(2⁸)[x]/(x⁴+1)
10.3 AES
10.3.1 Les rondes
10.3.2 La génération des clés de rondes (Key Expansion)
10.3.3 Déchiffrement
10.4 Maple et le corps de Galois GF(2⁸) (Programmation)
10.5 Implémentation de l'AES (Programmation)
10.5.1 Le corps de Galois GF(2⁸)
10.5.2 Les routines
10.5.3 Key Expansion
10.5.4 Le chiffrement
11 Courbes elliptiques
11.1 Introduction
11.2 Courbes elliptiques sur Z/pZ (p premier)
11.3 Courbes elliptiques sur Z/nZ (n composé)
11.4 Application à la cryptographie
11.5 Application à la décomposition des grands nombres
11.6 Courbes elliptiques et Maple (Programmation)
11.6.1 Courbes elliptiques sur R
11.6.2 Le formulaire : « addition des points »
11.6.3 Racine carrée dans Z/pZ
11.6.4 Courbes elliptiques sur Z/pZ (p premier)
11.6.5 Addition des points des courbes elliptiques sur Z/pZ
11.6.6 Multiples d'un point
11.6.7 Courbe symétrique par rapport à l'axe Ox
11.6.8 Courbes sur Z/nZ (n composé)
11.6.9 Addition des points. Multiples d'un point
12 Exemples d'applications de la cryptographie
12.1 L'argent n'a pas d'odeur
12.2 Organiser une partie de poker sur internet
12.3 Tiers de confiance et distribution de clés
12.4 HTTPS
12.5 Carte bancaire
12.6 PGP
12.7 Voter via internet
12.8 Le WIFI
12.9 Conclusion
13 La cryptographie à travers l'Histoire
13.1 L'Antiquité
L'âge artisanal
Système à transposition
Système à substitution
Chiffre de César
Kama-sutra (Ve siècle)
XIIIe siècle, Roger Bacon
Système de Vigénère (1586)
Chiffre poly-alphabétique
Grand chiffre de Louis XIII et Louix XIV (1626)
Le chiffre du livre
Invention du télégraphe
1883 Principes de Kerckhoffs
Masque jetable (one time pad) (Vernam 1917)
13.2 La mécanisation
Enigma (1918) (et autres systèmes à rotors)
Shannon
L'âge industriel et informatique
Cryptographie publique et libre ou secrète et tolérée ?
13.3 Systèmes symétriques
Lucifer (1970) et le DES (1976)
IDEA (1992)
AES (2000)
13.4 Systèmes à clé publique (asymétriques)
Échange de clés (Diffie et Hellman 1976)
Sac à dos (Hellmann 1978)
RSA (Rivest, Shamir, Adleman 1978)
Courbes elliptiques (Miller et Koblitz 1985)
PGP (P. Zimmermann 1991)
13.5 Mars 2000 : la signature numérique a valeur légale en France
Où en est-on en 2012 ?
Bibliographie
Index