caa a22 4500 475827228 CHVBK 20180406123831.0 cr unu---uuuuu 170329e20000301xx s 000 0 eng 10.1007/s001459910008 doi (NATIONALLICENCE)springer-10.1007/s001459910008 Stronger Security Proofs for RSA and Rabin Bits [Elektronische Daten] [R. Fischlin, C. P. Schnorr] Abstract. : The RSA and Rabin encryption functions are respectively defined as E N (x) = x e mod N and E N (x) = x 2 mod N , where N is a product of two large random primes p , q and e is relatively prime to φ (N) . We present a simpler and tighter proof of the result of Alexi et al. [ACGS] that the following problems are equivalent by probabilistic polynomial time reductions: (1) given E N (x) find x; (2) given E N (x) predict the least-significant bit of x with success probability 1/2 + 1/poly(n) , where N has n bits. The new proof consists of a more efficient algorithm for inverting the RSA/ Rabin function with the help of an oracle that predicts the least-significant bit of x . It yields provable security guarantees for RSA message bits and for the RSA random number generator for modules N of practical size. International Association for Cryptologic Research, 2000 Key words. RSA function, Rabin function, RSA random number generator, Perfect pseudorandom number generator nationallicence Fischlin R. Fachbereich Mathematik/Informatik, Universität Frankfurt, PSF 111932, 60054, Frankfurt/Main, Germany aut Schnorr C. P. Fachbereich Mathematik/Informatik, Universität Frankfurt, PSF 111932, 60054, Frankfurt/Main, Germany aut Journal of Cryptology Springer Berlin Heidelberg 13/2(2000-03-01), 221-244 0933-2790 13:2<221 2000 13 145 https://doi.org/10.1007/s001459910008 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s001459910008 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fischlin R. Fachbereich Mathematik/Informatik, Universität Frankfurt, PSF 111932, 60054, Frankfurt/Main, Germany aut NATIONALLICENCE 700 1- Schnorr C. P. Fachbereich Mathematik/Informatik, Universität Frankfurt, PSF 111932, 60054, Frankfurt/Main, Germany aut NATIONALLICENCE 773 0- Journal of Cryptology Springer Berlin Heidelberg 13/2(2000-03-01), 221-244 0933-2790 13:2<221 2000 13 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer