# Cryptographic Reduction: Last Bit of RSA Suffices to Recover the Plaintext

Out of interest I have started studying a script on the mathematical foundations of cryptography. I have now however stumbled upon a statement which I could not prove:

If there exists an (efficient) algorithm $LSB(\cdot)$ which, for a given $k$-bit RSA modulus $n$ and cyphertext $c$ computes the $LSB$ of the corresponding plaintext $m$ (where $c = m^e$), then there exists an efficient algorithm which for a given $c$ computes the entire corresponding $m$.

The proof of this statement begins as follows:

By the mulitiplicate property we have

\begin{equation} (2m)^e = 2^e m^e = 2^e c \end{equation}

(All calculations are carried out $\mod n$.)

If $2m < n$, $2m$ will not be reduced (i.e. $n$ will not be subtracted) and $LSB(2m) = 0$. On the other hand, if $2m > n$ and with $n$ odd we get $LSB(2m) = 1$.

Therefore we can write $LSB(2^e c) = 0 \iff 2m < n$

My question concerns the implication in bold: Clearly the statement is true for $e = 1$ but I don't see how it extends to higher values. My attempt so far, with which I get stuck, is to proceed by induction:

We want to prove that $LSB(2^e c) = 0 \implies 2m < n$ for all positive integers $e$. Clearly this holds for $e = 1$. Now let

\begin{align*} a &= (2m)^{e - 1} \mod n \\ b &= 2m \mod n \end{align*}

Then we proceed by case distinction: Assume $ab \mod n$ is even, then we first consider

\begin{equation} ab = (2k)n + 2b \end{equation}

for some suitable $k$ and $b$. This clearly implies that $ab$ must be even which in turn implies that at least one of the factors is even. By the induction assumption this further implies that $2m < n$.

Now consider the case

\begin{equation} ab = (2k + 1)n + 2b \end{equation}

Here we need to conclude that $ab$ is odd which is satisfied iff both $a$ and $b$ are odd. Here I cannot continue.

Could someone clarify where I am going wrong or explain to me the key insight needed to tackle this proof?

We are assuming a $k$-bit RSA-modulus $n$. Moreover we assume we have an algorithm $\tt{LSB}$ which, given a ciphertext $c$, outputs the least significant bit of the corresponding plaintext $m$. In crypto-terminology, this is what is usually referred to as an oracle. Think of it like a black box you have sitting on your table: whenever you give it $c$, it outputs a single bit $b\in\left\{0,1\right\}$ and nothing else, and you have no idea how $b$ was computed. All you know is that ${\tt LSB}(m)=b$. Now that seems like a very strong tool to have, and indeed the theorem you are stating says that having this box allows you to decrypt any given ciphertext.
So now we are sitting at our table, and we have in one hand a ciphertext $c$ and in the other the oracle ${\tt LSB}$. What inputs do we give to ${\tt LSB}$ so that we obtain all of $m$? Well, we can start by feeding it $c$. By definition, we obtain ${\tt LSB}(m)$, which is a good start! But of course this is not enough.
Here is the main idea of the theorem: consider inputting $2^ec$. Then there exist some plaintext $m_1$ corresponding to $2^ec$, and we obtain ${\tt LSB}(m_1)$. Then what information does ${\tt LSB}(m_1)$ give us? This is really the key idea, so you could try to figure things out from here!
Well, we know that by definition $$m_1=\left(2^ec\right)^d=\left(2^em^e\right)^d=\left(2m\right)^{ed}=2m,$$ so there is a clear relation between $m$ and $m_1$! Now we know that $m\in[0,n-1]$, hence $2m\in[0,2n-2]$, and $2m$ is even (viewed as an integer). Now here is an implicit assumption on the oracle ${\tt LSB}$: it will output the least significant bit of the unique representation of $m_1$ in $[0,n-1]$. So what is the representation of $m_1=2m$ in $[0,n-1]$? If $2m < n$, then it is the even integer $2m$. If however $2m\geq n$, it is the odd integer $2m-n$. So we have the following two statements: \begin{align*} {\tt LSB}(m_1) = 0 &\iff 2m < n,\\ {\tt LSB}(m_1) = 1 &\iff 2m \geq n. \end{align*} We have cut the number os possible plantexts in half, as either $m < n/2$ or $m\geq n/2$. Now we want to continue in similar fashion, inputting a next cleverly chosen ciphertext into the oracle.
• And once more: I am deeply obliged :) After reading your elaborate explanation my mistake is obvious; for some reason (I blame the ambiguous notation) I have shifted from assuming that $\text{LSB}(c)$ computes the LSB of $m$ to assuming that it computes the LSB of $c$. – R.G. Nov 27 '16 at 12:28