5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented Aug 14, 2012 at 13:15
  • $\begingroup$ Are you talking about real RSA with padding, or just paddingless textbook RSA? $\endgroup$
    – CodesInChaos
    Commented Aug 15, 2012 at 9:28

1 Answer 1

Reset to default
9
$\begingroup$

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$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for your answer , may i know why gcd(e,e2) = gcd(e,e-e2) $\endgroup$
    – Kit Ho
    Commented Aug 14, 2012 at 14:45
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Aug 14, 2012 at 14:53
  • $\begingroup$ sorry for my stupid question, why n can be divided by e-e2?, is that a property? or can it prove? $\endgroup$
    – Kit Ho
    Commented Aug 14, 2012 at 14:59
  • $\begingroup$ @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$. $\endgroup$
    – poncho
    Commented Aug 14, 2012 at 15:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Aug 14, 2012 at 16:43

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.