Cryptanalyses et preuves de sécurité du cryptosystème RSA

Jean-Sébastien Coron

Cette thèse a pour but d'étudier la sécurité de certains schémas de chiffrement et de signature basés sur l'algorithme RSA. Cette thèse peut se diviser en deux parties: une partie ``cryptanalyse" et une partie ``preuve de sécurité".

Dans la première partie, on montre que certains schémas cryptographiques existants et couramment utilisés dans la pratique présentent des faiblesses qui les rendent vulnérables à certaines attaques. Ainsi, on met en défaut la sécurité des standards de signature digitale ISO 9796-1 et ISO 9796-2, ainsi que la sécurité de la norme de chiffrement PKCS#1 v1.5. On étend aussi l'attaque de Girault et Misarsky sur les signatures RSA à redondance affine.

Dans la seconde partie, on étudie les moyens de prouver la sécurité des schémas de signature à clef publique. Cela consiste à formaliser les notions de sécurité que l'on souhaite atteindre, pour ensuite montrer que certains schémas satisfont ces propriétés sous certaines hypothèses. Dans cette thèse, on donne une preuve de sécurité améliorée du schéma de signature Full-Domain-Hash et du schéma de signature de Gennaro-Halevi-Rabin. On montre également qu'avec un schéma de signature où chaque message possède une signature unique, on ne peut pas atteindre le même niveau de sécurité qu'avec un schéma où chaque message a plusieurs signatures possibles.

Les attaques présentées dans la première partie de cette thèse confirment une nouvelle fois l'importance des preuves de sécurité, une branche de la cryptographie en plein essor actuellement. En effet, aucun des schémas attaqués dans la première partie ne possédaient de preuve de sécurité.

***

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.