Breaking RSA, given a special kind of oracle that decrypts related ciphertexts for us

Question

Let $c=E^{RSA}_{e}(w)$ be the ciphertext belonging to the plaintext $w$ if an $RSA$ system is used. Assume that the public exponent $e$ satisfies $e \le 10$. Furthermore, assume there is an oracle that, on input $r>0$, responds with the value $c_{r}= E^{RSA}_{e} (w + r)$.

Can the plaintext be decrypted efficiently, given this oracle?

Answer 1

Hint 1: what's the binomial expansion of $E_e^{RSA}(w+r)$? That is, how can that be expressed as a polynomial in variables $w$ and $r$? What degree are those polynomials, in terms of $w$?

Hint 2: suppose we ask for $E_e^{RSA}(w+r)$ for $0 < r < e$ (and we also know $E_e^{RSA}(w)$); what can we do with the corresponding $e$ polynomials?

Answer 2

Here is a simple example for the algorithm given in the last two hints:

Let $n=55,e=3$ and let $w$ be the plaintext and let

$E_{e}^{RSA}(w)=25,E_{e}^{RSA}(w+1)=21,E_{e}^{RSA}(w+2)=33$

but:

$E_{e}^{RSA}(w)=25\;\;\;\;\;\; \Rightarrow w^{3}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\equiv 25\;mod\;55\;\;............(1)$ $E_{e}^{RSA}(w+1)=21 \Rightarrow w^{3}+3w^{2}+3w+1\;\,\equiv 21\;mod\;55\;\;............(2)$ $E_{e}^{RSA}(w+2)=33 \Rightarrow w^{3}+6w^{2}+12w+8\equiv 33\;mod\;55\;\;............(3)$

Now we just solve this system of congruence equations and then we choose the solution which lives in $\mathcal{Z}_{n}$,

We multiply the first congruence equation with $(-1)$ and add it to the second and third:

$3w^{2}+3w+1\;\,\equiv -4\;mod\;55 \Rightarrow 3w^{2}+3w\;\,\equiv -5\;mod\;55 .....(4)$ $6w^{2}+12w+8\equiv 8\;mod\;55\;\Rightarrow\;\; 6w^{2}+12w\equiv 0\;\;\;\;mod\;55 .....(5)$

We multiply the $4^{th}$ congruence equation with $(-2)$ and add it to the $5^{th}$ then we get:

$6w\equiv10\;mod\;55$

Which is a linear congruence equation and can be efficient solved: $gcd(6,55)=1|10$ so it has a solution and using the extended euclidean algorithm we get:

$6(-9)+55(1)=1 \Rightarrow 6(-90)+55(10)=10 \Rightarrow 6(-90)\equiv 10\; mod\;55$ so the general solution is $w\equiv -90\;mod\;55$ and the solution which lives in $Z_{55}$ is $w=20$.