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$
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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: