Statistical Properties of Short RSA Distribution and Their Cryptographic Applications

Abstract : In this paper, we study some computational security assump-tions involve in two cryptographic applications related to the RSA cryp-tosystem. To this end, we use exponential sums to bound the statistical distances between these distributions and the uniform distribution. We are interesting studying the k least (or most) significant bits of x e mod N , where N is a RSA modulus when x is restricted to a small part of [0, N). First of all, we provide the first rigorous evidence that the cryptographic pseudo-random generator proposed by Micali and Schnorr is based on firm foundations. This proof is missing in the original paper and do not cover the parameters chosen by the authors. Consequently, we extend the proof to get a new result closer to the parameters using a recent work of Wooley on exponential sums and we show some limitations of our technique. Finally, we look at the semantic security of the RSA padding scheme called PKCS#1 v1.5 which is still used a lot in practice. We show that parts of the ciphertexts are indistinguisable from uniform bitstrings.
Type de document :
Communication dans un congrès
Computing and Combinatorics, Aug 2014, Atlanta, United States. Springer, LNCS 8591, pp.525 - 536, 2014, COCOON 2014. 〈10.1007/978-3-319-08783-2_45〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094059
Contributeur : Pierre-Alain Fouque <>
Soumis le : jeudi 11 décembre 2014 - 15:42:57
Dernière modification le : mercredi 11 avril 2018 - 02:00:57
Document(s) archivé(s) le : samedi 15 avril 2017 - 07:51:47

Fichier

micali.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierre-Alain Fouque, Jean-Christophe Zapalowicz. Statistical Properties of Short RSA Distribution and Their Cryptographic Applications. Computing and Combinatorics, Aug 2014, Atlanta, United States. Springer, LNCS 8591, pp.525 - 536, 2014, COCOON 2014. 〈10.1007/978-3-319-08783-2_45〉. 〈hal-01094059〉

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

153