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.

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?

share|improve this question
    
You should probably do your own homework problems. They are assigned for a good reason, you know (hint: it's not to test your Google skills). –  D.W. Nov 13 '12 at 6:39
add comment

2 Answers

up vote 2 down vote accepted

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?

share|improve this answer
    
okay, thank you very very much –  Sam Nov 12 '12 at 9:38
3  
@Kemo: I suppose this answer helped you to find the proof, as you accepted it. Could you add your own answer with a more complete proof, for all of us who don't have this as a homework, but are nevertheless interested? –  Paŭlo Ebermann Nov 12 '12 at 19:06
add comment

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

share|improve this answer
add comment

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.