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):
- 2.7 et 2.8 (2.5)
- 2.9 et 2.10 (2.13 (a) et/and (b))
- 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.
- (3.5)
- (3.6 (a), (b), (c))
- (3.10 (a), (b))
- (3.12)
- (3.14)
- (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):
- 3.21 (3.29)
- 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.
- 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.
- 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.
- 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.
- (4.7 (a), (b), (c))
- (4.8)
- (4.14 (a), (b))
- (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:
- (8.20)
- (10.1)
- (11.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:
- (12.2)
- (12.8) (a), (b), (c)
- (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:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- M. Naor and O. Reingold, On the construction of pseudo-random
permutations: Luby-Rackoff revisited, Journal of Cryptology,
Springer, vol. 12,
1999.
- 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.
- S. Goldwasser, S. Micali, R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks,
Society for Industrial and Applied Mathematics, 1988.
- M. Bellare, S. Miner, A forward-secure digital signature scheme, Lecture Notes in Comptuer Science, CRYPTO '99,
Springer-Verlag, 1999.
- 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.
- 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.
- U. Maurer, Secret key agreement by public discussion from
common information, IEEE Transactions on Information Theory, 1993.
- 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.
- 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.
- 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.
- 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.
- 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.
- M. O. Rabin, Probabilistic algorithm for testing primality,
Journal of Number Theory, vol. 12, no 1, 1980, p. 128–138.
- 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.
|