How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions?

I have access to an oracle that can encrypt and partially decrypt a number with RSA-1024 algorithm.

For encryption: $$C = M^e\bmod n$$ But for decryption, result will be $\bmod256$: $$\textit{partialM} = (C^d\bmod n)\bmod 256$$ Also I know $e=65537$, and $d$ and $n$ will remain unchanged.
I want to know if it's possible for a given $C$ to find $M$. If yes, how?

• What is $d=\mathit{ct}$ and $n=\mathit{ct}$ supposed to mean? May 12, 2016 at 9:56
• Means that $d$ and $n$ will remain unchanged.
– user34194
May 12, 2016 at 10:55

• It's not a homework, I want to learn about cryptography and reverse engineering. @Ben can you tell me please if I am on the right path? I was thinking to compute $C_i = i^e \bmod n$ and $C'=C*C_i$ with $i = 2,3,4..$ and then I will be able to find $r_i=i*M\bmod 256$ (constraint). Now I have to find $M$ that satisfy as many possible constraints? Or I must focus finding $N$ first and then compute $M$? Also, can you recommend me some article about this problem?