Cryptographie: théorie et applications (IFT6180)

Automne 2016

Professeur: Louis Salvail

LITQ, DIRO, Université de Montréal, Montréal, Québec



Plan/Description

Le plan du cours IFT6180 est accessible ici:

Horaire

Les cours ont lieu les lundis et mardis comme indiqué ici: Le premier cours aura lieu le mardi 6 septembre 2016.


Devoirs

  • Devoir 1: A remettre le mardi 26 septembre 2016, 9:30. Les numéros entre parenthèses sont pour la plus récente version du livre(le livre bleu).
    • Résolvez les exercices suivants du livre:
      1. 2.5
      2. 2.6 a) et 2.6 b)
      3. 2.10
      4. 2.13 a) et 2.13 b)
      5. 3.2
      6. 3.4
  • Devoir 2: - A remettre le mardi 11 octobre 2016, 14:30. Les numeros sont ceux du livre bleu (et non pas ceux du livre vert).
    • Résolvez les exercices suivants:
      1. 3.5
      2. 3.6
      3. 3.10
      4. 3.14
      5. 3.29
  • Devoir 3: A remettre le mardi 1er novembre 2016, 14:30.
    • Résolvez les exercices suivants:
      1. 4.7
      2. 4.8
      3. 4.9
      4. 5.5 faites seulement le cas k=1.
  • Devoir 4: A remettre le mardi 29 novembre 2016, 14:30PM.
    • Résolvez les exercices du livre suivants:
      1. 9.1
      2. 10.1
      3. 10.2
      4. 11.4
  • Devoir 5: A remettre avant le 13 décembre 2016, 12:30PM. Les numeros entre parentheses sont pour la nouvelle version du livre; le livre bleu.
    • Résolvez les exercices suivants:
      1. 11.8
      2. 12.8
      3. 12.9 (a) et (b)
      4. Question bonus: 12.9 (c)

    Notes

    Voici les sujets traités à mesure que le semestre progresse:

    • Semaine 1: Correspond à la première moitié de l'introduction du livre. Nous avons vu quelques chiffres historiques et avons discuté de la façon de les attaquer (les cryptanalyser).
    • Semaine 2: Les transparents au sujet de la machine ENIGMA ont été préparés par Alain Tapp. Ils sont disponibles ici. Nous avons terminé l'introduction. Nous avons vu le chapitre 2 au sujet du chiffrement parfaitement sûr et débuté le Chapitre 3 jusqu'à la section 3.2.1 exclusivement.
    • Semaine 3: Nous avons défini la sécurité calculatoire des chiffres contre l'espionnage (unique) comme l'indistinguabilité des chiffrements de n'importe quelle paire de messages clairs. Nous avons discuté de son équivalence à la notion de sécurité sémantique. Nous avons introduit la notion de générateur pseudo-aléatoire cryptographique (GPA). Nous avons montré ensuite comment utiliser un GPA pour construire un chiffre sûr contre l'espionnage. Nous avons finalement discuté de la sécurité contre l'espionnage multiple avant de montrer qu'elle nécessite une chiffrement non-déterministe à partir de la clé et du message clair. Ceci correspond aux sections 3.2.1 à 3.4.1 inclusivement.
    • Semaine 4: Nous avons défini la sécurité CPA pour les chiffres. Nous avons introduit les fonctions pseudo-aléatoires. Nous avons construit un chiffre CPA sûr à partir de fonctions pseudo-aléatoires. Nous avons vu comment chiffrer des messages de taille arbitraire à partir de chiffre CPA-sûr pour des messages de taille fixe. Nous avons vu comment créer un chiffre CPA sûr pour des messages de longueur arbitraire à partir de fonctions pseudo-aléatoires en utilisant les modes d'utilisation CBC, OFB et CTR.
    • Semaine 5: Nous avons montré que le mode CTR est bien CPA-sûr. Nous avons ensuite regardé comment définir la sécurité CCA. Nous avons vu comment authentifier des messages de longueur variable étant donné une façon d'authentifier des messages de longueur fixe. CBC-MAC et ses variantes.
    • Semaine 6: La transformée de Merkle-Damgaard. Les fonctions résistantes aux collisions et l'authentification de messages (i.e. HMAC et NMAC). La construction d'un chiffre CCA-sûr.
    • Semaine 7: La construction de chiffres par bloc: permutations pseudo-aléatoires fortes. Les réseaux de substitutions et permutations et les réseaux de Festel. DES et AES. Voici les diapos sur DES et AES.
    • Semaine 8: Théorie des nombres et hypothèses cryptographiques I. Nous avons l'arithmétique modulaire l'algorithme d'Euclide et sa version étendue. Nous avons introduit la théorie des groupes dans Z*N pour un groupe additif et dans les groupes cycliques pour des groupes multiplicatifs. Nous avons également discuté la génération de nombres premiers, l'algorithme de Miller-Rabin, aléatoires pour produire des nombres difficiles à factoriser.
    • Semaine 9: Nous avons déterminé des groupes cycliques pour lesquels le log discret est supposé difficile à résoudre. Finalement, nous avons discuté de deux variantes du problème des logs discrets: Le Diffie-Hellman calculatoire (CDH) et le Diffie-Hellman décisionnel (DDH). DLOG est au moins aussi difficile que CDH qui est au moins aussi difficile que DDH. Nous avons exhibé des groupes cycliques pour lesquels le problème DDH est supposé difficile (basé sur les nombres premiers de Sophie Germain). Nous avons construit une fonction à sens unique à partir de la difficulté de factoriser et une fonction résistante aux collisions à partir du problème DLP.
    • Semaine 10: Gestion de clés et la révolution à clé publique. Toutes les sections du Chapitre 10 et les premières du chapitre 11. La distribution de clé de Diffie-Hellman a été prouvée sûre sous l'hypothèse DDH. Nous avons ensuite montré que les chiffres à clé publique sûrs contre l'espionnage sont également sûr contre les attaques CPA. Nous avons vu qu'un chiffre à clé publique sûr contre l'espionnage est sûr contre le chiffrement multiple (une version un peu plus simple que celle du livre au Théorème 11.6).
    • Semaine 11: Nous avons continué le chapitre 11: Sections 11.2.3 jusqu'à la fin. Nous avons vu la sécurité des systèmes hybrides. Les chiffrements RSA et El Gammal.
    • Semaine 12: Les signatures numériques, construction de signatures. Le paradigme hache-et-signe et les signatures RSA. Construction de signatures numériques à partir de fonctions à sens unique (et résistantes aux collisions), la construction de Lamport. Visite rapide des infrastructures à clé publique. Introduction au modèle de l'oracle aléatoire.

    Liens utiles

    Examen Final (Matière)

    Choisissez un sujet parmi les suivants. Vous aurez sans doute à lire plus d'un papier pour comprendre le sujet. Certains sujets ont plus d'une références dans la liste qui suit. La présentation devra durer au plus 25 minutes avec 5 minutes de discussion. Sélectionnez une sous-liste qui vous intéresse et allez lire les résumés sur l'internet. Donnez-moi vos 3 choix en ordre descendant de préférence. Faites vos choix le plus rapidement possible.....
    1. S. Rudich, The use of interaction in public cryptosysytems. In Advances in Cryptology:CRYPTO'91, Lecture Notes in Computer Science, Springer, pp. 242-251, 1991.
    2. R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. Proceedings of the 21st ACM Symposium on the Theory of Computing, 1989.
    3. R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Advances in Cryptology: CRYPTO'98, Lecture Notes in Computer Science, 1998.
    4. M. Naor et M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the 20th annual ACM symposium on Theory of computing, STOC'90, Vol. 369, ACM Press, pp. 427-437, 1990.
    5. P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology: EUROCRYPT'99. Lecture Notes in Computer Science, Springer, pp. 223-238. 1999.
    6. U. Maurer, Torwards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms, Advances in Cryptology:CRYPTO'94, Lecture Notes in Computer Science, Vol.839, Springer, pp.271-281, 1994 et U. Maurer et S. Wolf, The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms, SIAM Journal on Computing, Vol. 28, Num. 5, Society for Industrial and Applied Mathematics, p.1689, 1999.
    7. D. R. Simon, Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions?, Advances in Cryptology: EUROCRYPT'98, Lecture Notes in Computer Science, Springer, pp.334~345, 1998.
    8. J. Vandewalle, R. Govaerts et B. Preneel, Hash functions based on block ciphers: a synthetic approach, Advances in Cryptology: CRYPTO'93, Douglas R. Stinson, editor, Lecture Notes in Computer Science, vol. 773, Springer, pp. 368--378, 1994.
    9. D. Boneh et M. Franklin (2001). Identity-based encryption from the Weil pairing, Advances in Cryptology:CRYPTO'01, Lecture Notes in Computer Science, Springer, pp. 213-229, 2001.
    10. M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, vol. 17, no 2, pp. 373--386, April 1988.
    11. M. Naor and O. Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited, Journal of Cryptology, Springer, vol. 12, 1999.
    12. U. Maurer, Y. A. Oswald, K. Pietrzak et J. Sjoedin Luby-Rackoff Ciphers from Weak Round Functions?, Advances in Cryptology:EUROCRYPT'06, Lecture Notes in Computer Science, Springer, pp. 391-408, 2006.
    13. S. Goldwasser, S. Micali, R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, Society for Industrial and Applied Mathematics, 1988.
    14. M. Bellare, S. Miner, A forward-secure digital signature scheme, Lecture Notes in Comptuer Science, Crypto 99, Springer-Verlag, 1999.
    15. L. Blum, M. Blum et M. Shub. A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, vol.15, pp. 364-383,1986 et P. Junod, Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator, 1999.
    16. C. Rackoff et D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Crypto 91, Lecture Notes in Computer Science, Springer, 576, pp. 433-444, 1992.
    17. U. Maurer, Secret key agreement by public discussion from common information, IEEE Transactions on Information Theory, 1993.
    18. E. Biham, A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993 et E. Biham et A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology, CRYPTO '90. Springer-Verlag. 2-21 et E. Biham et A. Shamir, Differential Cryptanalysis of the Full 16-Round DES, CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991.

Horaire de l'examen

L'examen pour l'automne 2016 aura lieu mardi le 13 décembre 14:30-17:30 au local A.A.1409.

Mise-à-jour

Date de la dernière mise à jour est: 08/12/2016.