# 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: \begin{equation} C = M^e\bmod n \end{equation} But for decryption, result will be $\bmod256$: \begin{equation} \textit{partialM} = (C^d\bmod n)\bmod 256 \end{equation} 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? – yyyyyyy May 12 '16 at 9:56
• Means that $d$ and $n$ will remain unchanged. – user34194 May 12 '16 at 10:55

## 1 Answer

So this feels like a homework question, as such I"m not going to give you the full answer, but yes, yes you can. https://en.wikipedia.org/wiki/Homomorphic_encryption#Unpadded_RSA Is the best starting point I can give without giving away the barn, but essentially rsa is homomorphic, and you can exploit that and repeated calls to the oracle to do what you want.

• 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? – Jorj May 12 '16 at 16:24
• Since you know what N is you can actually multiply by a number which is equivalent to dividing by 256. On each iteration you multiply by this constant which will give you the next lowest byte until you've done it to each byte. This would be exploiting the homomorphic property from wikipedia above, and a little bit of number theory. – Ben May 13 '16 at 3:45