# Common modulus attack on RSA when the 2 public exponents differ by a single bit

This is an exam question an i have no idea how to recover the message m.

John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and so John sends an email to Mary to ask for the key. mary's email reply is intercepted by Peter who replaces Mary's public key $\{e,n\}$ with $\{e_2, n\}$ where $e_2$ is obtained by changing one bit in $e$ from $0$ to $1$. Now john encrypts a message $m$ to Mary by using $\{e_2, n\}$. As Mary cannot decrypt the message, she resends her public key to John and asks John to send the encrypted message to her again. Peter does not interrupt this time. However, Peter eavesdrops the whole communication and obtains both encrypted message (one encrypted by $\{e_2,n\}$ and one by $\{e,n\}$. Explain how Peter can recover the message $m$.

How can encryption with both $\{e_2,n\}$ and $\{e,n\}$ be used to recover the message $m$?

I did think that it is related to common module attack, but i have no idea how to prove that $\gcd(e,e_2)=1$.

Does anyone have some idea on how to recover the message?

• Remember, it doesn't say which bit in $e$ is changed from $0$ to $1$. That is something you get to choose. If you can pick a bit to change so that $\gcd(e,e_2)=1$, the common modulus attack will work. – mikeazo Aug 14 '12 at 13:15
• Are you talking about real RSA with padding, or just paddingless textbook RSA? – CodesInChaos Aug 15 '12 at 9:28

Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property

$\gcd(e, e_2) = \gcd(e, e-e_2)$

Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime factor. On the other hand, we know $e$ is odd (because it is an RSA exponent), and so $e$ and $e-e_2$ do not have any prime factors in common (and hence, $e$ and $e_2$ do not either).

This result implies that the method you already have (which is effectively using the Euclidean method on the values $e$ and $e_2$ to compute $M^{gcd(e, e_2)}$) will give you $M$.

• Thanks for your answer , may i know why gcd(e,e2) = gcd(e,e-e2) – Kit Ho Aug 14 '12 at 14:45
• @KitHo: one way to show that is to go back to the definition of gcd, which is the largest value $n$ that is a divisor of both $e$ and $e_2$. If $n$ divides $e$ and $e_2$ (that is, if $an = e$ and $bn = e_2$, for some integers $a$ and $b$), it also divides $e-e_2$ (that is, $cn = (e-e_2)$ for some integer $c$, specifically, $c = a-b$). Conversely, if $n$ divides both $e$ and $e-e_2$, it also divides $e_2$ (same logic). And so, if a value $n$ is the maximum value that divides one pair, it must also be the maximum value that divides the other. – poncho Aug 14 '12 at 14:53
• sorry for my stupid question, why n can be divided by e-e2?, is that a property? or can it prove? – Kit Ho Aug 14 '12 at 14:59
• @KitHo: it's the other way around; $n$ divides $e-e_2$. Specifically, if $n = gcd(e, e-e_2)$, then $n$ divides $e - e_2$, that is, there's an integer $c$ such that $cn = e - e_2$. – poncho Aug 14 '12 at 15:04
• @KiHo: if $e/n$ and $e_2/n$ are integers, then $(e-e_2)/n = e/n - e_2/n$ is an integer as well. – poncho Aug 14 '12 at 16:43