Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094059
Contributor : Pierre-Alain Fouque <>
Submitted on : Thursday, December 11, 2014 - 3:42:57 PM
Last modification on : Thursday, January 7, 2021 - 4:33:30 PM
Long-term archiving on: : Saturday, April 15, 2017 - 7:51:47 AM

File

micali.pdf
Files produced by the author(s)

Identifiers

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. pp.525 - 536, ⟨10.1007/978-3-319-08783-2_45⟩. ⟨hal-01094059⟩

Share

Metrics

Record views

442

Files downloads

448