Cryptographie: théorie et applications (IFT6180)

Hiver 2019

Professeur: Louis Salvail

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



Plan/Description

Le plan du cours est accessible ici: À noter qu'il est un peu différent de la description du cours donnée ici.

Horaire

Les cours ont lieu les lundis (11:30-13:30) et mercredis (12:30-14:30) comme indiqué ici: Les locaux sont indiqués sur le plan de cours. Le premier cours aura lieu le lundi 7 janvier 2019.


Devoirs

Les numéros seuls sont les numéros du livre vert (1ere édition). Les numéros entre les parenthèses sont pour le livre bleu (2ième édition). Une copie du livre est disponible à la bibliothèque (je crois que les deux éditions y sont, mais je ne suis pas certain) The exercises indicated by numbers alone are from the 1st edition of the book (the green book). The exercices between parenthesis are from the 2nd edition of the book(the blue book). You solve either the numbers from the first edition or the second edition according the book you have. You can find the book at the library.
  • Devoir 1: A remettre le lundi 28 janvier, 11:30 sous forme papier. To be handed in Monday, January 28th, 11:30. You are responsible to give me your your solved exercises before the deadline. Résolvez les exercices suivants du livre (Solve the following):
    1. 2.7 et 2.8 (2.5)
    2. 2.9 et 2.10 (2.13 (a) et/and (b))
    3. 2.11 (**2.11**)
  • Devoir 2: A remettre le mercredi 13 février 2019, 12:30. Je ne donne que les numéros de la seconde édition (livre bleu). Résolvez les exercices suivants. To be handed in on Wednesday, Feb. 13th,12:30. Only the numbers for the second edition are given below.
    1. (3.5)
    2. (3.6 (a), (b), (c))
    3. (3.10 (a), (b))
    4. (3.12)
    5. (3.14)
    6. (3.19)
  • Devoir 3: À remettre le lundi 11 mars 2019, 11:30. To be handed in on Monday March 11th, 2019, 11:30. Résolvez les exercices suivants (solve the following):
    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ûrs. 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.

      Assuming the existence of a PRF, show the existence of secret-kety encryption schemes secure against multiple eavesdroppings but CPA insecure. Your scheme does not have to be natural. You should use the fact that CPA security holds against adaptative encryption requests made by the adversary.

    3. J'ai montré en classe que les chiffres qui admettent des chiffrements indistinguables contre les attaques CPA admettent également des multi-chiffrements indistinguables contre les attaques CPA. La preuve utilisait un argument hybride. Je vous demande de montrer un énoncé plus fort: Les chiffres qui admettent des chiffrements indistinguables contre les attaques CPA admettent également des multi-chiffrements indistinguables contre les attaques CPA adaptatives (selon l'expérience LR-CPA dans le livre). Il vous faudra raffiner l'argument hybride légèrement pour y parvenir.

      I have shown in class that all ciphers having indistinguishable encryptions under chosen plaintext attacks have also indinguishable multiple encryptions under chosen plaintext attacks (the non-adaptative version). The proof was using a hybrid argument. I ask you to show a stronger statement: All ciphers having indistinguishable encryptions under chosen plaintext attacks have also indinguishable multiple encryptions under adaptative chosen plaintext attacks (captured by the LR-CPA experiment). You will have to refine slightly the hybrid argument I gave you to get the result.

    4. 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.

      Show that CBC-MAC for messages of fixed length is insecure for messages of arbitrary length.

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

      Show how to adapt the Merkle-Damgaard transform in the case of a fixed-length collision resistant hashing function hs:{0,1}l+1->{0,1}l and prove the collision resistance of the resulting function.

    6. (4.7 (a), (b), (c))
    7. (4.8)
    8. (4.14 (a), (b))
    9. (4.15)
  • Devoir 4:
  • A remettre le mercredi 3 avril 2019, 12:30PM. To be handed in on Wednesday April 3rd, 2019, 12:30. Résolvez les exercices suivants du livre bleu/ Solve the following exercices in the blue book:
    1. (8.20)
    2. (10.1)
    3. (11.4)
    4. (11.16)
  • Devoir 5:
  • A remettre avant le 7 mai 2019 par courrier électronique. Les numeros sont ceux du livre bleu. To be handed in before May 7th, 2019 by email. Résolvez les exercices suivants du livre bleu/ Solve the following exercices in the blue book:
    1. (12.2)
    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 à l'introduction du livre (chapitre 1). J'ai commencé par présenter quelques chiffres historiques et avons discuté de la façon de les attaquer (les cryptanalyser). Les diapos que j'ai présentées ont été préparées par Alain Tapp. Elles sont disponibles ici. Nous avons ensuite traité des principes fondamentaux de la cryptographie moderne.

    We discussed the introduction (chapter 1) of the book. We have seen some historical ciphers together with their cryptanalysis. We have quickly discussed the Enigma machine. We then look at the basic principles of modern cryptography. The slides of the first course are available here.

  • Semaine 2: Nous avons traité du chapitre 2 et de la première partie du chapitre 3. Nous avons montré un chiffre parfait (le masque jetable) et les limites des chiffres parfaits. Nous avons considéré plusieurs définitions de sécurité équivalentes pour les chiffres parfaits. Nous avons ensuite introduit des définitions de sécurité calculatoires pour les chiffres à clé secrète. Nous avons discuté de deux approches dans ce contexte: l'approche conrète et l'approche asymptotique. La cryptrographie moderne utilise essentiellement toujours l'approche asymptotique pour exprimer la sécurité des schémas. Le document suivant montre l'équivalence entre la définition d'indistinguabilité et la définition de sécurité sémantique, deux définitions de l'approche asymptotique.

    We covered chapter 2 and the first part of chapter 3. We defined the security of perfectly secure ciphers in several equivalent ways. We introduced the one-time-pad and showed that it is perfectly secure. We showed the limits of perfectly secure ciphers. We review two ways of considering the security of private key ciphers in the computational setting: the concrete approach and the asymptotic approach. Modern cryptography almost always expresses security with the asymptotic approach. We consider two definitions (indistinguishability and semantic security) for the computational security of private key encryption schemes in the asymptotic setting. This document shows the equivalence of these two definitions.

  • Semaine 3: Nous avons traité des sections 3.3, 3.4 et 3.5 de la seconde édition. Nous avons introduit les générateurs pseudo-aléatoires standards, à longueur variable et avec vecteurs d'initialisation. Nous avons donné un chiffre sûr contre l'espionnage pour les messages de longueur fixe à partir de générateur pseudo-aléatoire standard. Nous avons montré comment mettre au point un chiffre pour les messsages de longueur variable à partir d'un générateur pseudo-aléatoire de longueur variable. Les générateurs pseudo-aléatoires avec vecteur d'inialisation sont utiles pour obtenir un chiffre de flux asynchrone sûr contre l'espionnage. Nous avons 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. Nous avons introduit la sécurité CPA et énoncé (seulement) que la sécurité CPA offre automatiquement la sécurité contres les attaques CPA multiples et même contre les attaques CPA multiples adaptatives.

    We have discussed sections 3.3,3.4, and 3.5 of the second edition of the book. We have introduced pseudo-random generators (standard PRG), variable length pseudo-random generators, and initialisation vector pseudo-random generators. We have shown how to define a cipher for messages of fixed length offering security against (single) eavesdropping from a PRG. We have shown how to allow secure encryption of variable length messages against eavesdropping from a variable length PRG. Ciphers like that are called stream ciphers. We have seen how to devise am asyncrhone stream cipher from an initialisation vector PRG. We have discussed security against multiple eaveadropping and showed that it requires probabilistic encryption. Finally, we have introduced the CPA security for ciphers and their generalisations to multiple messages CPA and multiple messages adaptative CPA. We have mentionned (but not proved) that all these variants of CPA security are equivalent.

  • Semaine 4: Nous avons traité des sections 3.5 et 3.6 de la seconde édition du livre. Nous avons prouvé qu'un chiffre CPA-sûr est également sûr contre les attaques CPA contre les chiffrements multiples en utilisant un argument hybride. La preuve peut être modifiée légèrement pour montrer qu'un chiffre CPA-sûr est sûr contre les attaques CPA multiples adaptatives. Nous avons introduit les fonctions pseudo-aléatoires (FPA) et donné une construction (sans preuve) à partir d'un GPA. Nous avons montré comment construire, à partir d'une FPA, un chiffre pour des messages de taille fixe qui soit CPA-sûr. Nous avons vu comment chiffrer plus efficacement des messages de taille arbitraire à partir de chiffres CPA-sûrs. Nous appelons mode de chiffrement ces façons de procéder. Nous avons montré les grandes lignes de la preuve que le mode CTR est CPA-sûr si le chiffre utilisé l'est également. Nous avons introduits les modes de chiffrement EBC, CBC et OFB. Les modes CTR et OFB convertissent un chiffre CPA-sûr pour les messages de taille fixe en chiffre de flux. Le mode CTR est complètement parallélisable (le chiffrement et le déchiffrement).

    We have discussed sections 3.5 and 3.6 of the second edition of the book. We have shown that a CPA secure encryption scheme is also secure against CPA-mult attacks using an hybrid argument. The proof can be slightly modified to show that CPA secure encryption schemes are also secure against LR-CPA-mult attacks. We have introduced pseudo-random functions (PRF) and showed how to construct a CPA secure encryption schheme from any of them. We have indicated how to construct a PRF from a PRG. Finally, we have discussed encryption modes allowing to encrypt messages of arbitrarily length efficiently given a pseudo-random function. We have shown that the CTR mode is CPA secure in this case. Modes EBC, CBC and OFB have been quickly discussed. The CTR and OFB modes allow to convert a pseudo-random function into a stream cipher with CPA security. The CTR mode is completely parallelizable (i.e. encryption and decryption).

  • Semaine 5: Nous avons terminé le chapitre 3 et débuter le chapitre 4 (3.7, 4.1, 4.2, 4.3 et 4.4) de la seconde édition. Nous avons montré que le mode de chiffrement CTR est CPA-sûr lorsqu'utilisé avec une fonction pseudo-aléatoire. Nous avons défini les chiffres CCA-sûrs et montré qu'aucun chiffre développé jusqu'à maintenant n'est CCA-sûr. Nous avons introduit les codes d'authentification de message (CAM) pour assurer l'intégrité des messages transmis. 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. CBC-MAC remplace le vecteur d'initialisation aléatoire pas le 0-vecteur pour le mode de chiffrement CBC. L'emprunte est composé seulement du résultat de la dernière évaluation de la fonction pseudo-aléatoire.

    We finished chapter 3 and discussed sections 4.1, 4.2, 4.3, and 4.4 of the second edition. We have shown that the encryption mode CTR is CPA-secure when used with a pseudo-random function. We have defined CCA-secure encryption schemes. We have shown that none of the encryption scheme we have seen so far is CCA-secure. We have introduced messae authentication codes (MAC) to enforce the integrity of message transmissions. We have shown how to construct a secure MAC for fixed length messages from any pseudo-random function. We have seen how to construct a secure CAM for messages of arbitrary length (almost arbitrary) given a secure CAM for fixed length messages. Other way to achieve this more efficiently is by using CBC-MAC. That is using the CBC encryption mode to authenticate messages where the initialisation vector is the all zero vector and where only the last application of the pseudo-random function is returned as the authentication tag.

  • Semaine 6: Nous avons traité des fonctions résistantes aux collisions et à certaines de leurs applications pour ganrantir l'intégrité des messages. Nous avons vu un outil indispensable en cryptographie moderne, la transformation de Merkle-Damgaard. Elle permet de convertir des fonctions résistantes aux collisions pour des messages de longueur fixe en fonctions résistantes aux collisions pour des messages de taille arbitraire. Une tempête de neige nous a forcé à remettre les constructions de CAM à partir de fonctions résistantes aux collisions à la semaine prochaine.

    We have introduced collision resistant hashing functions and and some of their applications to ensure message integrity (building MACs from them). We habe seen a very important tool in modern cryptography, the Merkle-Damgaard transform, which allows to transform collision resitant hashing functions for fixed-length input messages into collision resistant hasing functions for arbitrary-length input messages. A snow storm forced use to postpone to next week the standard techniques used to obtain secure MACs from collission-resistant hashing function.

  • Semaine 7: Nous avons vu comment utiliser la transformation de Merkle Damgaard pour construire des CAMs. Il s'agit des standards NMAC et HMAC. Le CAM NMAC est sûr si la fonction résistante aux collisions pour les messages de taille fixe hs utilisée avec une clé secrète k et le message m, hsk(m):= hs(k,m), est un CAM sûr pour les messages de taille fixe. NMAC utilise deux clés secrètes pour authentifier un message. HMAC utilise qu'une seule clé secrète, mais n'est sûr que si G(k):= hs(k+OPAD) || hs(k+IPAD) est un GPA. Nous avons vu comment transformer un chiffre CPA-sûr en un chiffre CCA-sûr à l'aide d'un CAM avec emprunte unique pour chaque message une fois la clé secrète fixée. Nous avons débuté notre discussion des méthodes mondernes pour la mise au point de chiffre par bloc (permutations pseudo-aléatoires fortes). Nous avons vu le paradigme de confusion et diffusion de Shannon. Il s'agit des fonctions obtenues en substituant des petits blocs de bits avant de les permuter et de recommencer pour un certain nombre de ronde. Les substitutions (S-boxes) et les permutations doivent permettre l'effet d'avalanche des erreurs au travers tout le bloc de données.

    We have seen how to use the Merkle-Damgaard transform to construct a secure MAC. These are the NMAC and HMAC standards. NMAC is secure if the collision intractable function hs used with secret key k and message m as hsk(m):= hs(k,m) is a secure MAC for fixed length messages. NMAC uses 2 secret keys to authenticate messages. HMAC uses only one key but is secure only if G(k):= hs(k+OPAD) || hs(k+IPAD) is a PRG. We have seen how to transform a CPA secure cipher into a CCA secure cipher using a secure MAC having unique tag for each message given a fixed the secret key. We have started our discussion about the modern methods allowing the set up of block ciphers (strong pseudo random permutations). We have have seen Shannon's confusion and diffusion paradigm. These are the pseudo-random permutations obtained by applying substitutions upon small parts of the block, then a permutation upon all positions before repeting this process for a certain number of rounds. The substitutions (S-boxes), permutations, and the number of round must ensure the commpletion of the avalanche effect of the differences over the whole block.

  • Semaine 8: Nous avons vu les deux principales méthodes pour la mise au point des chiffres par bloc, qui doivent se comporter comme des permutations pseudo-aléatoires fortes. Il s'agit du paradigme de confusion-diffusion de Shannon et les réseaux de Festel. Nous avons vu qu'un petit nombre de ronde permet des attaques dévastatrices contre ces constructions. La clé privée peut être retrouvée après l'interception de paires message clair-cryptogramme en beaucoup moins d'étapes que la fouille exhaustive des clés. Nous avons ensuite vu que DES est une réseau de Feistel tandis que son remplaçant, AES, est un réseau de confusion diffusion. Nous avons également vu rapidement comment le chiffre par flot RC4 est construit. Voici quelques diapos à leur sujet. Nous avons terminé la semaine en traitant de certains aspects de la théorie des nombres et de la théorie des groupes qui seront pertinents pour notre étude de la cryptographie à clé publique. Quelques théorèmes que nous n'avons pas montré en classe sont montrés sur ces diapos (théorème fondamentale de l'arithmétique, les nombres premiers sont infinis, etc...).

    We have seen the two main methods to set up block ciphers behaving like strong pseudo-random permutations. These are the Shannon's confusion-diffusion paradigm and Festel networks. We showed that these methods require enough rounds to complete the avalanche effects. Otherwise, devastating attacks can be mounted to recover the private key from plaintext-ciphertext pairs much faster than key space exhaustive search. We then lokked at modern block ciphers, DES and AES together with streamcipher RC4. DES is a Feistel network while AES satisfies the confusion-diffusion paradigm. These slides show DES, AES et RC4. We then started discussing a few number theory and group theory results that will be relevant to our study of public key cryptography. A few theorems that I did not prove in class can be seen here (i.e. fundamental theorem of arithmetics, infinity of prime numbers, etc...).

  • Semaine 9: Nous avons mentionné brièvement l'algorithme d'Euclide et sa version étendue. Nous avons introduit les concepts de base de la théorie des groupes. Nous avons défini le groupe Z*N dans lequel l'arithmétique RSA se déroule pour N le produit de deux grands nombres premiers aléatoires. Nous avons défini le problème RSA et fait l'hypothèse qu'il est difficile à résoudre. Nous avons également discuté la génération de nombres premiers, l'algorithme de Miller-Rabin. Nous avons introduit les groupes cycliques pour lesquels nous avons défini le problème du calcul du log discret (DLOG). Nous avons discuté des groupes cycliques pour lesquels le log discret est supposé difficile à réoudre. Nous avons introduit 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. Finalement, nous avons construit une fonction à sens unique à partir de la difficulté de factoriser et une fonction résistante aux collisions à partir du problème DLOG.

    We mentioned Euclid's algorithm and its extended version (allowing to find efficiently the inverse of elements in modular groups). We have introduced the group Z*N in which the RSA arithmetic is performed, when N is the product of two large random primes. We have defined the RSSA problem and made the hypothesis that it is difficult to resolve for the composite number generator GenModulus. We discussed quickly how to generate random primes using the Rabin-Miller algorithm. We have defined cyclic groups and the discrete log problem (DLOG). We have identified a cyclic group for which DLOG is believed to be difficult. We have introduced two variant of the DLOG problem, the computational Diffie-Hellman problem (CDH) and the decisional Diffie-Hellman problam (DDH) problems. DLOG is at least as difficult as CDH, which is at least as difficult aas DDH. Finally, we have constructed a one-way function from the difficulty of factoring numbers produced by GenModulus and a collision resistant function from the difficulty of solving DLOG.

  • Semaine 10: Nous avons abordé les problèmes de gestion gestion de clés dans une architecture ouverte et la révolution à clé publique qui permet de résoudre (en partie) ces problèmes. Nous avons revu les propositions faites par Diffie et Hellman en 1976 dans leur papier New Directions in Cryptography. Nous avons vu le protocole de distribution de clé de Diffie et Hellman. Nous l'avons ensuite prouvé sûr sous l'hypothèse DDH. Nous avons ensuite montré que les chiffres à clé publique sûrs contre l'espionnage sont également sûrs contre les attaques CPA. Nous avons montré qu'un chiffre à clé publique sûr contre l'espionnage est sûr contre le chiffrement multiple en utilisant un argument hybride du même type que celui vu en devoir et en classe lorsque nous discutions des chiffres à clé privée.

    We have discussed the problem of key management in open architecture and the public-key revolution allowing to resolve most of the problem. We have also discussed the proposals given in the paper responsible for the public key revolution: New direction in Cryptogreaphy by Diffie and Hellman (1976). We then review the one proposal of Diffie and Hellman, the Diffie-Hellman key exchange protocol. We have shown that the Diffie-Hellman key exchange is secure given that DDH is hard. Then, we have shown that public key encryption schemes that are secure against eavesdropping are also CPA-secure. In addition to that, we have shown that a secure public-key encryption scheme against eavesdropping is also secure againt multiple eavesdropping (and is therefore multiple CPA-secure). The proof of this fact uses an hybrid argument similar to the one we have seen when we discussed private key encryption and also in the 2nd assignment.

  • Semaine 11: Nous avons montré comment construire un chiffre à clé publique hybride qui utilise un chiffre à clé privée pour le chiffrement et un chiffre à clé publique pour chiffrer une nouvelle clé privée à chaque transmission. Nous avons montré que si les deux chiffres sont sûrs contre l'espionnage alors le chiffre à clé publique résultant est sûr contre les attaques CPA. Il est également plus efficace (en général) que les chiffres à clés publiques pour chiffrer de longs messages. C'est de cette façon que le chiffrement SSL (ou TLS) fonctionne. Nous avons discuté de RSA et des faiblesses de la version décrite habituellement dans les livres d'introduction. Nous avons ensuite vu quelques façons de bourrer les messages pour rendre le chiffrement probabiliste. Le bourrage simple qui consiste à concaténer une chaîne aléatoire (un nonce) au message peut seulement être montré sûr, lorsque le problème RSA est difficile pour GenRSA, si la longueur du message est au plus logarithmique dans le facteur de sécurité, ce qui est très inefficace. Nous avons ensuite vu deux standards pour le bourrages: PKCS #1 v1.5 et OAEP. PKCS est un bourrage simple qui permet de chiffrer des messages de taille arbitrairement petite. Il est conjecturé CPA sûr mais n'est pas CCA sûr. Sa sécurité n'est que de 64 bits, ce qui est trop peu aujourd'hui. OAEP est le standard utilisé (qui devrait être utilisé) dans la pratique. Il est construit à partir d'un GPA est d'une fonction de hachage résistante aux collisions. Lorsque ces compostantes sont modélisées par des primitives idéales (à l'aide d'un oracle aléatoire), RSA+OAEP est CCA sûr. Nous avons ensuite vu comment construire un chiffre à clé publique CPA-sûr sur des groupes cycliques pour lesquels DDH est difficile. Il s'agit du chiffre de El Gamal. Aucune schméma que nous avons vu n'offre le sécurité CCA.

    We have shown how to construct a public key hybrid encryption scheme using a private key cipher for the encryption of the message and a public key cipher to encrypt a new session key for the private key cipher. We have shown the resulting hybrid cipher is a CPA secure public key encryption scheme when the public and private key ciphers used are secure against eavesdropping. The resulting hybrid encryption scheme is much more efficient than the public key cipher alone. This is how SSL (TLS) encrypts messages during a session. We have discussed some weaknesses of textbook RSA. In order to have a secure RSA implementation, some good padding is needed (in particular to have probabilistic encryption). The simplest form of padding (concatenating the message with a random nonce) can only be shown CPA secure when the RSA problem is hard for GenRSA when messages are of (at most) logarithmic length in the security parameter. This is very inefficient. We discussed two standard paddin schemes: PKCS #1 v1.5 and OAEP. PKCS is a variant of the simple padding allowing to encrypt arbitrary length messages (but shorter than the security parameter). It is conjectured CPA secure but is not CCA secure. OAEP is the current padding standard. It is implemented from a PRA and a collision resistant hashing function. When these two primitives are modelled ideally by a random oracle then RSA+OAEP is CCA secure. Finally, we have seen how to construct a CPA secure public key cipher on cyclic groups for which the DDH problem is hard. This public key cipher is called El Gamal. No public key encryption scheme that we have seen is CCA secure.

  • Semaine 12: Nous avons débuté notre étude des protocoles de signature numérique. Après avoir discuté des différences avec les schémas d'authentification, nous avons formellement défini les schémas de signature numérique et leur sécurité. Nous avons vu le paradigme hache-et-signe et montré qu'il permet de transformer un schéma de signature pour des messages de longueur fixe en un schéma de signature pour les messages de longueur arbitraire. Nous avons considéré les faiblesses des signatures RSA canoniques et discuté de la difficulté de monter ces attaques lorsque RSA est utilisé en hache-et-signe. Nous avons introduit les signatures numériques à usage unique et montré comment en construire sous la seule hypothèse que des familles de fonctions à sens unique existent. Nous en avons fait la preuve, qui est assez simple. Nous avons ensuite promu le schéma de signature pour qu'ils puissent signer autant de messages que désirés en permettant à l'algorithme de signature de conserver un état. Cette construction de signature à état demande l'existence de fonctions de hachage résistantes aux collisions pour pouvoir signer des paires de clés publiques. Ce résultat est celui de Lamport publié en 1979, mais il montrait la sécurité des signatures à état sous la seule hypothèse que les fonctions à sens unique existent. La résistance aux collisions est une hypothèse possiblement plus forte que l'existence de fonctions à sens unique. Nous avons décrit, dans ses grandes lignes, l'idée derrière la preuve de sécurité. Les diapos suivantes discutent du schéma de Lamport et de sa preuve de sécurité comme signature à état.

    We started our study of digital signature schemes. After having discussed the differences between digital signatures and authentication codes, we formally defined signature schemes and their security. We have seen the hash-and-sign paradigm as a way to convert a signature scheme for messages of fixed length into one for messages of arbitrary lenght. We have seen some weaknesses of canonical RSA for signatures. We saw that the attacks described seem difficult to carry out when the hash-and-sign paradigm is used with canonical RSA. We have introduced a weaker version of signature schemes: one-time signatures. We have seen how to construct them from any one-way function family and we have shown its security. Then, we have prmoted the 1-time signature scheme to a many-time signature scheme by allowing the signing algorithm to keep a state. These are called state signatures. We have shown how to build them from the existence of collision intractable hasing functions. This result is due to Lamport in 1979 but he showed it only assuming the existence of one-way functions. Collision resistance is likely to be a stronger assumption than the existence of one-way functions. We have discussed rhoughly the ideas behind the security proof of the state signature scheme. The slides here discuss Lamport's state signature scheme and its proof of security (roughly).

  • Semaine 13: Nous avons montré comment éliminer l'état des signatures è état de Lamport pour obtenir un schéma de signature sûr contre les attaques à messages choisis en autant que les fonctions de hachage résistantes aux collisions existent. Il s'agit d'utiliser une PRF pour la génération de l'état en demandant la génération de seulement trois clés. Ce résultat de Rompel est formulé d'une façon enbcore plus forte dans l'article original (1990), seule l'existence de fonctions à sens unique est nécessaire (et suffisante) pour montrer la sécurité du schéma. Ce résultat est surprenant, car il montre que les signatures sont plus faciles à obtenir que le chiffrement à clé publique dans un monde relativisé. Nous avons ensuite traité du modèle de l'oracle aléatoire pour obtenir des preuves de sécurité là où les techniques standards échoues. Il s'agit de modéliser les fonctions de hachage par des oracles aléatoires pour montrer la sécurité de schémas cryptographiques. Cepdendant, la sécurité obtenue tient seulement pour des fonctions de hachages qui peuvent être évaluées qu'en appelant un oracle, ce qui n'est pas le cas pour n'importe quelle réalisation d'une fonction de hachage cryptographique dans le modèle standard. Le résultat n'est pas une preuve qui s'applique dans la pratique, seulement une preuve conceptuelle qui indique que le schéma n'a pas de faiblesses autres que la fonction de hachage utilisée. Nous avons montré que dans le modèle de l'oracle aléatoire, une variante de RSA peut être montré CPA sûr sous l'hypothèse que le problème RSA est difficile pour GenRSA. Il s'agit d'une variante de RSA, RSAH, construite comme le chiffre de ElGamal. RSAH utilise une fonction de hachage appliquée à une valeur aléatoire chiffrée avec RSA de façon directe pour générer un masque jetable. RSAH est moins efficace que OAEP appliqué à RSA. Une autre variante de RSA(que nous n'avons pas vue) peut être montrée CCA-sûre dans le même modèle en utilisant un chiffre clé privé qui soit CCA sûr. Finalement, nous avons montré que le paradigme hache-et-signe appliqué à RSA dans le modèle de l'oracle aléatoire, appelé RSA-FDH, est un schéma de signature sûr contre les attaques à messages choisis en autant que le problème RSA soit difficile pour GenRSA.

    We have shown how to get rid of the state of Lamport's stateful digital signature scheme(1979) based on the existence of collision resistant hashing functions. The idea is to use a PRF with 3 keys to generate the state on the fly without having to store it. This result form Rompel has been stated in a stronger way in the original paper: only the existence of one-way frunctions is required (1990). This is a surprising result because it tells us that digital signatures are "easier" to construct than public key encryption schemes in a relativized world. Then, we have introduced the random oracle model (ROM) as a model allowing to show the security of cryptographic schemes by idealizing the use of cryptographic hashing functions. It allows to have a weak proof of security for schemes that we are otherwise unable to show secure in the standard model. In the ROM collision-resistamt hashing functions are viewed and interacted with through oracle calls. As a result, a security proof in the ROM is not a security proof in the standard model. They require hashing functions that cannot be evaluated efficiently in the standard model and cannot be analyzed by any means to learn relevant things about it. No implementation in the standard model can provide such an idealized hashing function. A security proof in the ROM only shows that a cryptogeraphic scheme does not have inherent weaknesses, only the instantiation of the ROM by an actual hashing function can prevent the scheme from being secure. We have shown that a viarant of RSA similar to the ElGamal cipher, called RSAH, can be shown CPA-secure under a general computational assumption. This variant encrypts a random nonce with textbook RSA before one-time-padding the message with the hashing function applied to the nonce. In the ROM and provided the RSA problem is hard for GenRSA, RSAH is CPA-secure. A similar construction in the ROM can be used to show its CCA-security. The scheme is not as efficient as OAEP however. Finally, we have shown that in the ROM, the hash-and-sign paradigm applied to the textbook RSA signature scheme, called RSA-FDH, is secure against choosen messages attacks provided the RSA problem is hard for GenRSA.


Liens utiles

  • Une liste d'errata pour la deuxième édition du livre du cours.

Examen Final (Matière)

ATTENTION: L'examen final est lundi le 15 avril à 11:30 jusqu'à 14:30 au local 1175 du pavillon André-Aisenstadt. Il n'y aura pas de séance d'examen mercredi le 17 avril. La présence à l'examen est requise pour toute sa durée.

PLEASE NOTE: The final exam is Monday, April 15th from 11:30 to 14:30. The room is 1175 in André-Aisenstadt building. You must be present for the whole duration of the exam, the 3 hours on Monday 15th.

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-10 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 décroissant de préférence. Faites vos choix le plus rapidement possible. Vous pouvez également me proposer d'autres choix, dans la mesure où le sujet est similaire à des concepts que nous avons vus.p

Choose a topic among the following. Maybe you'll have to read more than one paper to understand the subject. Some topics have more than one paper related to them in the following list. Your presentation should last at most 25mins. You should be ready to answer questions during about 5-10 minutes. Select 3 topics in order of preference and send me your list by email. I will decide which one of your 3 subjects will be yours. Make your selection as fast as possible. You can also have your own proposal as long as the subject is related to something we have seen in the course.

Voici la liste des articles/Here are the papers:
  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. K. Nyberg, Perfect nonlinear S-boxes, Advances in Cryptology: EUCOCRYPT'91, Donald W. Davies editor, Lecture Notes in Computer Science, vol. 547, Springer, pp. 378--386, 1991.
  9. J. Vandewalle, R. Govaerts et B. Preneel, Hash functions based on block ciphers: a synthetic approach, Advances in Cryptology: CRYPTO'93, Donald W. Davies, editor, Lecture Notes in Computer Science, vol. 773, Springer, pp. 368--378, 1994.
  10. 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.
  11. 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.
  12. M. Naor and O. Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited, Journal of Cryptology, Springer, vol. 12, 1999.
  13. 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-Verlag 765, pp. 391-408, 2006.
  14. S. Goldwasser, S. Micali, R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, Society for Industrial and Applied Mathematics, 1988.
  15. M. Bellare, S. Miner, A forward-secure digital signature scheme, Lecture Notes in Comptuer Science, CRYPTO '99, Springer-Verlag, 1999.
  16. 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.
  17. 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-Verlag 576, pp. 433-444, 1992.
  18. U. Maurer, Secret key agreement by public discussion from common information, IEEE Transactions on Information Theory, 1993.
  19. 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, pp. 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.
  20. A. Shamir, Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology, proceedings of CRYPTO '84, Lecture Notes in Computer Science, Springer-Verlag 196, pp. 47-53, 1984.
  21. P. C. Kocher, J. Jaffe, B. Jun, Differential Power Analysis. Advances in Cryptology, proceedings of CRYPTO '99, Lecture Notes in Computer Science, Springer-Verlag 1666, pp. 388-397, 1999.
  22. A. Fiat, A. Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology, proceedings of CRYPTO '86, Lecture Notes in Computer Science, Springer-Verlag 263, pp. 186-194, 1986.
  23. M. Stevens, E. Bursztein, P. Karpman, A. Albertini, Y. Markov, The first collision for full SHA-1 Marc Stevens1. Advances in Cryptology, proceedings of CRYPTO '2017, Lecture Notes in Computer Science, Springer-Verlag 10401, pp. 570-598, 2017.
  24. M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory, vol. 12, no 1,‎ 1980, p. 128–138.
  25. S. Goldwasser, S. Micali, Probabilistic Encryption, Journal of Computer and System Sciences. 28 (2): 270–299, 1984.

Horaire de l'examen

Les dates et les emplacements pour les présentations finales seront donnés plus tard. La première journée de présentations sera de 11:30 à 13:30 le lundi 15 avril 2019.

Mise-à-jour

Date de la dernière mise à jour: 11/04/2019.