Master INPG-UJF Cryptologie,
Sécurité et Codage de l'information
502a - Chiffrement : théorie de l'information et applications
Enseignant:
Jean-Louis.Roch@imag.fr
Planning des séances: 2006/2007
Document : notes de cours : entropie,
classes de complexité, hachage
- Mercredi 20 Septembre 2006 - 14h-16h Salle 14
Chap. 1/ Chiffrement et théorie de l'Information
- Théorie de l'Information: quantité
d'information et entropie
- Théorème de Shanon : chiffrement absolu et
borne inférieure sur la taille de la clef privée
- Extension au cas d'un groupe.
- Corollaire: le chiffre de Vernam implémente un
chiffrement parfait
- Références:
- Lundi 25 Septembre 2006 - 9h45-12h45 Salle 14
Chap. 2/ Chiffrement et théorie de la complexité (1)
- Diffie-Hellman: fonction à sens unique et fonction
chausse-trappe.
Exemples: Controle de parite dans GF_2[x], Logarithme discret, RSA
- Problèmes "infaisables" et complexité
Problèmes de décision et langages. Prédicats
à sens unique et chausse-trappe.
- Lien avec certificat polynomial. Classes P et NP.
- Exercice: LOG, PLOG et El Gamal
- Références:
- Lundi 2 Octobre 2006 - 9h45-12h45 Salle 14
Chap. 2/ Chiffrement et théorie de la complexité (2)
- Exemple: Merkle-Hellman (Sac à dos)
- Technique de Réduction
- Exemple: réduction de la factorisation à RSA
(déterministe)
Chap 3 / Fonctions de hachage
- Hachage et collisions.
- Hachage uniforme - Famille universelle de fonctions de hachage
- Hachage et sécurité: résistance aux
collisions
- Exemple: hachage par logarithme discret : Chaum-van Heijst -
Pfitzmann
feuille d'exercice: fonction
de hachage prouvée par réduction [ corrigé ]
- Lundi 9 Octobre 2006 - 9h45-12h45 Salle 14
Chap 3 Fin fonction de hachage. - Hachage compressif
- Hachage compressif - méthode de Merkle
- Exemples de fonctions de hachage: MD5 et SHA
- Applications: MDC, MAC, HMAC
- Remarques: modes de chiffrement ECB, CBC OFB et CFB
Chap. 4/ Complexité probabiliste et Chiffrement (1)
- Algorithmes Atlantic City, Monte Carlo et Las Vegas
- Exemple: Miller Rabin
- Classes de complexité probabilistes: BPP / RPP / ZPP
- Chiffrement probabilisite (Polynomial time secure)
Feuille d'exercice:
résidu quadratique et protocole d'identification probabiliste de
Shamir [ corrigé
]
- Lundi 16 Octobre 2006 - 9h45-12h45 Salle 14
Chap. 4/ Chiffrement probabiliste (Polynomial time secure) (2)
Chap. 5/ Génération de suites aléatoires
- Généralités sur les
générateurs pseudo-aléatoires:
- générateur sans biais et sans
collision:
construction de Vazirani
- complexité de Kolmogorov
- Générateurx linéaires classiques
- Sécurité des générateurs
aléatoires
- Prédicat à sens unique : définition
- Test du bit suivant
- Générateur générique de
Blum-Micali
- Construction d'un générateur à partir
d'une fonction à sens unique:
- Log-discret (Blum-Micali)
- Résidu quadratique mod n
- RSA
- Familles de fonctions pseudo-aléatoires
- Lundi 23 Octobre 2006 - 9h45-12h45 Salle 14
- Complements de cours
- Examen (1h)
Bibliographie:
- Théorie des codes: Compression, cryptographie et codes
correcteurs. Cours et exercices corrigés. JG Dumas, JL Roch, E
Tannier, S Varrette. A paraître chez Dunod
- Cryptographie
à clef
publique. Jean-Guillaume Dumas, Franck Leprevost, Jean-Louis Roch,
Valentin
Savin, and Sébastien Varrette. In T. Ebrahimi,
F. Leprevost, and
B. Warusfeld, editors, La
sécurité
Multimédia, pages 103--187. Hermes, 2006.
- Applied
Digital Information Theory I et
Applied Digital Information Theory II, James Massey.
- Cryptographie : Théorie et
Pratique . Douglas Stinson International Thomson
Publishing France, 1996
<>- Applied Cryptography :
Protocoles, Algorithms and Source code in C - 2nd edition -
Bruce Schneier -
1996.http://www.counterpane.com/crypto-gram.html
URL pour se tenir au courant des actualités en
sécurité: