2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Cash
    Dec 17, 2012 at 18:41
  • $\begingroup$ 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? $\endgroup$
    – user4544
    Dec 17, 2012 at 18:52
  • 1
    $\begingroup$ @user4544: The Jacobi symbol of $m$ can be computed from $m^e \mod N$. $\endgroup$
    – David Cash
    Dec 17, 2012 at 19:46
  • $\begingroup$ @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. $\endgroup$
    – user4544
    Dec 17, 2012 at 20:24
  • $\begingroup$ @DavidCash: thanks for the note, the update was much needed. $\endgroup$
    – fgrieu ♦
    Dec 17, 2012 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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