# Individual bits of Textbook RSA

This question relates to the underlying RSA assumption. Forgetting about the fact that Textbook RSA is deterministic, I am curious about the assumed strength of the RSA problem.

Does RSA hide all bits of the message, or are there some bits that can be easily revealed. Concretely,

$$m^e \space \bmod \space N$$

Can any part of $m$ be learned(with significant probability) without learning the secret key, and if so how?

Under the assumption that $m$ is unknown to the adversary, and random in $[0,N-1]$, then to the best of our knowledge, $m^e\bmod N$ does not reveal anything about any bit of $m$ to an adversary unable to factor $N$.
Update: in the above, "bit of $m$" is in the sense of binary digit of $m$ (for some integer $k≥0$, the value of $⌊m/2^k⌋\bmod 2$), not tiny amount of information. Revealing $m^e\bmod N$ does reveal information abut $m$; most notably the adversary knows the Jacobi symbol $\left(\frac m N\right)$ since that's also $\left(\frac{m^e\bmod N}N\right)$; and can test if an $x$ with $0≤x<N$ is $m$, by checking if $x^e\bmod N$ is $m^e\bmod N$.
• One should clarify what a "bit" is here: the RSA function is indeed known to leak (at least) one bit of information about $m$. The conjecture that every bit is hardcore (which is how I interpreted your answer) would not contradict this. – David Cash Dec 17 '12 at 18:41
• @user4544: The Jacobi symbol of $m$ can be computed from $m^e \mod N$. – David Cash Dec 17 '12 at 19:46
• @DavidCash Thanks-you. To answer my original question then, none of $m$ can be recovered? So this would imply that if we apply RSA to a random $r$ then under RSA Assumption, no bit of $r$ can be recovered. And we can achieve IND-CPA PKE by using $r$ as in the one time pad--$r \space xor \space m$. This is a simpler scheme than any secure-RSA schemes i have seen, so I was skeptical. – user4544 Dec 17 '12 at 20:24