Jean-Sébastien Coron
Ph.D. Thesis: Cryptanalysis
and Security Proofs for Public-key Schemes.
May 16th, 2001
Download:
Cryptanalyses et preuves
de sécurité de schémas à clef publique
Abstract
This thesis deals with the security of
encryption schemes and signature schemes based on the RSA algorithm, which are
commonly used in real-world applications. It is split into two parts,
"cryptanalysis" and "security proofs".
In the first part, we show that some existing cryptographic schemes have
weaknesses which make them vulnerable to some attacks. The RSA-based digital
signature standards ISO 9796-1 and ISO 9796-2, and the RSA-based encryption
standard PKCS#1 v1.5 are shown to be insecure. We also extend Girault and
Misarsky's attack on RSA signatures with affine redundancy.
In the second part, we study security proofs for signature schemes. We provide
an improved security proof for the Full-Domain-Hash signature scheme, and for
the Gennaro-Halevi-Rabin signature scheme. We also show that a signature scheme
in which each message has a unique signature can not reach the same level of
security as a signature scheme which messages have many possible signatures.
The attacks presented in the first part of this thesis illustrate the risk induced
by using cryptographic schemes which security is not clearly justified. This
strongly motivates the search for provably secure schemes.
Jury
-
Mihir Bellare (UCSD, USA)
- Marc
Girault (CNET, France)
- David
Naccache (Gemplus, France)
- Ronald
Rivest (MIT, USA)
- Adi
Shamir (Weizmann Institute of Science, Israel)
- Jacques
Stern (ENS, France)
- Jean-Marc
Steyaert (Ecole Polytechnique, France)
-
Serge Vaudenay (EPFL,
Switzerland)
From left to right: Marc Girault, Adi Shamir, Jean-Marc Steyaert, Jean-Sebastien
Coron, Ronald Rivest, Jacques Stern and David Naccache. Are not present on the photo Mihir Bellare and
Serge Vaudenay.