Cryptographie: théorie et applications (IFT6180)

Automne 2017

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 5 septembre 2017.


Devoirs

  • Devoir 1: A remettre le mardi 26 septembre, 14:30. Les numéros entre parenthèses sont pour la plus récente version du livre(le livre bleu) ceux qui ne le sont pas sont pour la version verte du livre (la premiè version). Résolvez les exercices suivants du livre:
    1. 2.7 et 2.8 (2.5)
    2. 2.9 et 2.10 (2.13 (a) et (b))
    3. 2.11 (2.1)
  • Devoir 2:
  • A remettre le mardi 10 octobre 2017, 14:30. Les numeros entres parenthèses sont ceux du livre bleu et les numéros correspondants du livre vert sont donnés sans parenthèses. Résolvez les exercices suivants:
    1. 3.3 (3.2)
    2. 3.4(3.3)
    3. 3.5(3.4)
    4. 3.6 (b) (3.6 (a))
    5. (3.10) Déterminer, pour F une FPA qui préserve les longueurs, si les constructions suivantes pour F' sont des FPA et expliquez pourquoi:
      • F'_k(x):= F_k(0||x)|| F_k(1||x)
      • F'_k(x):= F_k(0||x)|| F_k(x||1)
    6. 3.16 (3.20).
  • Devoir 3: A remettre le mardi 31 octobre 2017, 14:30. Résolvez les exercices suivants:
    1. 3.21 (3.29)
    2. En supposons l'existence de fonctions pseudo-aléatoires, montrez qu'il existe des chiffres qui admettent des chiffrements indistiguables contre l'espionnage multiple mais qui ne sont pas CPA-sûr. Votre chiffre n'a pas à être naturelle. Vous devez utiliser le fait que la sécurité CPA tient contre des requêtes adaptatives faites par l'adversaire.
    3. Montrez que CBC-MAC de base (pour des messages de taille fixe) n'est pas sûr lorsqu'il est utilisé pour authentifier des messages de tailles différentes.
    4. Montrez comment modifier la transformation de Merkle-Damgaard à partir d'une fonction de hachage résistante aux collisions hs:{0,1}l+1->{0,1}l et prouvez le résistance aux collisions de la fonction obtenue.
  • Devoir 4:
  • A remettre le mardi 28 novembre 2017, 14:30PM. Résolvez les exercices suivants du livre bleu:
    1. (8.20)
    2. (9.1)
    3. La réponse à cette question peut être trouvée à la sect. 4.1.2 de ce document.
    4. (10.1)
    5. (10.4)
    6. (11.4)
  • Devoir 5:
  • A remettre avant le 17 décembre 2017 par courrier électronique. Les numeros sont ceux du livre bleu. Résolvez les exercices suivants:
    1. (11.7)
    2. (12.8) (a), (b), (c)
    3. (12.9) (a), (b), (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. Nous avons débuté le Chapitre 3 jusqu'à la section 3.2.1 inclusivement.
  • Semaine 3: Voici un document où il est montré que la sécurité sémantique et la sécurité sous forme d'exprérience d'indistinguabité sont équivalentes. Nous avons terminé la semaine en introduisant la génération pseudo-aléatoire. 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.
  • Semaine 4: 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. Nous avons montré que le mode CTR est bien CPA-sûr.
  • Semaine 5: Nous avons défini les chiffres CCA-sûrs. Nous avons discuté du fait que les chiffres que nous avons vus jusqu'à maintenant ne sont pas CCA-sûrs. Nous avons introduit les codes d'authentification de message (CAM). Nous avons montré comment les construires pour des messages de longueur fixe à partir de fonctions pseudo-aléatoires. Nous avons montré comment convertir un CAM pour des messages de longueur fixe en CAM pour les messages de longueur arbitraire. Certaines de ces constructions (i.e. les plus efficaces) peuvent être obtenues à partir du mode d'opération CBC pour les chiffres par bloc, c'est le mode CBC-MAC.
  • Semaine 6: Les fonctions résistantes aux collisions. La transformation de Merkle-Damgaard. et l'authentification de messages à partir de fonctions résistantes aux collisions(i.e. HMAC et NMAC). La construction d'un chiffre CCA-sûr à clé privée et sa preuve de sécurité. La construction de chiffres par bloc: permutations pseudo-aléatoires fortes. Les réseaux de substitutions et permutations et les réseaux de Festel.
  • 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. Nous avons ensuite débuté l'étude des éléments de la théorie des nombres pour la cryptographie à clé publique (jusqu'à la section 7.2.2 en l'excluant).
  • 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 les concepts de base de la théorie des groupes. Nous avons introduit le groupe Z*N sur lequel RSA est basé lorsque N est le produit de deux grands nombres premiers. Nous avons également discuté la génération de nombres premiers, l'algorithme de Miller-Rabin, aléatoires pour produire des nombres difficiles à factoriser. Nous avons introduit les groupes cycliques pour lesquels nous avons défini le problème du calcul des logs discrets.
  • 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 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 en utilisant un argument hybride.
  • 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. Nous avons prouvé que lorsque DDH est difficile alors El Gammal est CPA-sûr. Nous avons débuté notre étude des protocoles de signature numérique. Nous avons vu le paradigme hache-et-signe et montré qu'il permet de transformer un schéma de signature pour les messages de longueur fixe en un schéma de signature pour les messages de longueur arbitraire.
  • Semaine 12: Nous avons vu comment construire des signatures numériques à partir de fonctions à sens unique (et résistantes aux collisions), la construction de Lamport. Visite rapide des infrastructures à clé publique. Vous trouverez ici une description de la réduction et de la preuve de sécurité sous forme graphique.

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. Voici la liste des articles:
  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 2017 aura lieu les 11 décembre de 10:30 à 12:00 au Z-255 et le 12 décembre de 15:00 à 17:30 au Z-200. Il s'agit d'une présentation sur un sujet choisi par chaque étudiant.

Mise-à-jour

Date de la dernière mise à jour: 11/12/2017.