The security of all RSA and discrete log bits
Johan Håstad, Mats Näslund · Journal of the ACM · 2004
We study the security of individual bits in an RSA encrypted message E N ( x ). We show that given E N ( x ), predicting any single bit in x with only a nonnegligible advantage over the trivial guessing strategy, is (through a polynomial-time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O (log log N ) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme.Considering the discrete exponentiation function g x modulo p , with probability 1 − o (1) over random choices of the prime p , the analog results are demonstrated. The results do not rely on group representation, and therefore applies to general cyclic groups as well. Finally, we prove that the bits of ax + b modulo p give hard core predicates for any one-way function f .All our results follow from a general result on the chosen multiplier hidden number problem: given an integer N , and access to an algorithm P x that on input a random a ∈ Z N , returns a guess of the i th bit of ax mod N , recover x . We show that for any i , if P x has at least a nonnegligible advantage in predicting the i th bit, we either recover x , or, obtain a nontrivial factor of N in polynomial time. The result also extends to prove the results about simultaneous security of blocks of O (log log N ) bits.