Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
1  
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
    
If every bit is hardcore then how could it leak a bit of information. And what exactly is this information that it is known to leak? –  user4544 Dec 17 '12 at 18:52
1  
@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
    
@DavidCash: thanks for the note, the update was much needed. –  fgrieu Dec 17 '12 at 20:46
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.