2
$\begingroup$

Reading another user's question, a doubt came to me.

Suppose an RSA oracle exists, with which it is possible to interact to encrypt and decrypt some text. The oracle output is not the decrypted text of the sent ciphertext, but the last n-bits.

The decryption takes place according to the law $ (C^e\bmod N)\bmod 2^n$, having indicated the number of bits with $n$.
If we wanted to recover the plain-text (still unknown to us), relating to a ciphertext (known to us), would it be correct to exploit the properties of the modular inverse $\bmod N$?

That is, using the knowledge of the remainder of $r =(C^e \bmod N) \bmod 2^n$, we calculate the multiplicative inverse of $r_{\text{inv}} = r^{-1} \bmod N$, from which $\ {r_{\text{inv}}}^e \bmod N = r_{\text{cinv}}$.

We multiply this result by the ciphertext, and ask the oracle to decrypt $C*r_{\text{cinv}}$ thus obtaining: $P* r_{\text{minus}} \bmod 2^n$, thus deriving the next $n$-bits of the plain-text?

$\endgroup$
1
  • $\begingroup$ In RSA, $(N,e)$ is assumed public, thus we can always make a chosen plain-text attack and need not an oracle "with which it is possible to interact to encrypt": we can encrypt at will. Event stranger is this idea of the oracle giving $(C^e\bmod N)\bmod 2^n$, isn't that $(C^d\bmod N)\bmod 2^n$ as in this other recent question? And accordingly, shouldn't the title be chosen ciphertext attack? Independently: the question does not tell what it's $r_{\text{minus}}$ is, and thus does not describe a full-blown attack. $\endgroup$
    – fgrieu
    Apr 5, 2023 at 11:48

1 Answer 1

1
$\begingroup$

I assume that, as in this recent question that seems related:

  • We are considering a partial decryption oracle that accepts $X$ and gives $(X^d\bmod N)\bmod2^n$ for some known fixed $n>1$ with $2^n\ll N$
  • We know textbook RSA ciphertext $C=P^e\bmod N$ for some unknown plaintext $P\in[0,N)$ that we want to find†.
  • We know the RSA public key $(N,e)$. Notice this makes any encryption oracle redundant.

The question's plan seems to be:

  • Submit $C$ to the partial decryption oracle, which outputs $r$. It holds $r=P\bmod N\bmod2^n$. This is the low-order $n$ bits of $P$.
  • Compute $r_{\text{inv}}=r^{-1}\bmod N$
  • Compute $r_{\text{cinv}}={r_{\text{inv}}}^e\bmod N$
  • Compute and submit $X=C*r_{\text{cinv}}$ (or rather, equivalently, $X=C*r_{\text{cinv}}\bmod N$) to the partial decryption oracle, which outputs $r'$ such that $$\begin{align}r'&=({({r_{\text{inv}}}^e*C)}^d\bmod N)\bmod 2^n\\ &=(r^{-1}*P\bmod N)\bmod 2^n\\ &=((P\bmod2^n)^{-1}*P\bmod N)\bmod 2^n\\ \end{align}$$

Would (that be) deriving the next $n$ bits of the plain-text?

No. The question's plan looks like a dead end to me.


Hint: $\lfloor 2^nP/N\rfloor$ is an at most $n$-bit quantity that can be computed by making a single query to the partial decryption oracle. Next targets are $\lfloor 2^{2n}P/N\rfloor$, $\lfloor 2^{3n}P/N\rfloor$


† With as few queries of the oracle as possible: if we are OK with as many queries as there are bits in $N$, or if $n=1$, a solution is there.

$\endgroup$
1
  • $\begingroup$ I'm giving a hint rather than the full solution because the questions is likely a CTF or homework. $\endgroup$
    – fgrieu
    Apr 5, 2023 at 17:34

Your Answer

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

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