Why the following attack in common modulus RSA works?

Question

Suppose that i share a common modulus $N$ with two users $u_1$ and $u_2$ with public, secret keys ($e_a,d_a$), ($e_b,d_b$). Why then $gcd(V,e_b)=1$ where $V=d_a*e_a-1/$W and $W=gcd(e_b,d_a*e_a-1)$ and as a consequence with extended euclidena algorithm i compute $α,β$ such that $α*e_b+β*V=1$ and it comes that $α=d_b$

Answer 1

One correction to your question: it's not necessarily true that your procedure will give you $\alpha = d_b$; however, the $\alpha$ you do get will work as a private key corresponding to $e_b$, just not necessarily the exact value that the user $u_2$ has.

With that in mind, here's an outline of why that is so:

First of all, two keys $(e, d)$ will work as corresponding public/secret exponents with an RSA modulus $N$ if and only if $e \cdot d \equiv 1 \space ( \bmod \space\lambda(N) )$, where $\lambda(N) = lcm(p-1, q-1)$.

So, we can restate the problem as: given values $(e_a, d_a)$ with $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$, and a value $e_b$, find a value $\alpha$ such that $e_b \cdot \alpha \equiv 1 \space ( \bmod \space\lambda(N) )$ (even if we don't know the value of $\lambda(N)$)

Now, the condition $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$ is precisely equivalent to the statement that there exists an integer $k$ such that $e_a \cdot d_a - 1 = k \cdot \lambda(N)$; let us call the value $k \cdot \lambda(N) = V$. Note that, even though we don't know the values of either $k$ or $\lambda(N)$, we can compute $V$.

Now, given that we know the values $e_b, V$, we can certainly run the Extended Euclidean algorithm, and find values $\alpha, \beta$ with $\alpha \cdot e_b + \beta \cdot V = 1$. Now, if reduce both sides modulo $\lambda(N)$, we find that $(\alpha \cdot e_b + \beta \cdot V) \bmod \lambda(N) = (\alpha \cdot e_b) \bmod \lambda(N) + 0 = 1$ (because $V$ is a multiple of $\lambda(N)$), and so $\alpha$ does meet the requirements of a private key corresponding to $e_b$.

Now, a few notes:

• The above argument shows that the result is correct, however it doesn't say why someone would happen to stumble upon it in the first place. Actually, it's not nearly as mysterious as it would seem; what we want is $e_b^{-1} \bmod V$, that is, the multiplicative inverse of $e_b$ modulo $V$, and the Extended Euclidean method is the standard way to compute that.

• The algorithm you have divides $V$ by $W$. It turns out that doesn't change anything; $W$ will be relatively prime to $\lambda(N)$; we know this because $W$ is a divisor of $e_b$, and $e_b$ must be relatively prime to $\lambda(N)$. So, dividing $V$ by $W$ effectively makes $V = (k/W) \cdot \lambda(N)$; $(k/W)$ is an integer (which is all we cared about $k$ anyways), and so it doesn't change the above argument.

• If someone does have a $(e,d)$ public/private key pair for a modulus $N$, it turns out that they can also efficiently factor $N$; however, the explination for how to do that would require a bit more work to explain.