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$


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.

  • $\begingroup$ I don't understand the involvement of $\lambda(N) = lcm(p-1, q-1)$. As far as i know $e \cdot d \equiv 1 mod\phi(N)$ $\endgroup$ – curious Dec 20 '12 at 22:20
  • $\begingroup$ @curious: actually, as I stated, $e \cdot d \equiv 1 \bmod \lambda(N)$ is both necessary and sufficient. To show that $\phi(N)$ is not necessary, consider the toy example with $e=3$, $d=11$, $N=85$. Here, $(M^e)^d \equiv M (\bmod N)$ for all $M$; however, $e \cdot d \neq 1 \bmod \phi(N)$ $\endgroup$ – poncho Dec 20 '12 at 22:24
  • $\begingroup$ So why in every book, research paper, textbook, the requirement is $e \cdot d \equiv 1 \phi(N)$ and not $e \cdot d \equiv 1 \lambda(N)$ $\endgroup$ – curious Dec 20 '12 at 22:36
  • $\begingroup$ and why $gcd(e_b,V)=1$ , according to your notation where $V=e_a \cdot d_a -1$ $\endgroup$ – curious Dec 20 '12 at 23:43
  • $\begingroup$ @curious: you've read every book, research paper and textbook on RSA??? In any case, that's not true; for example, FIPS 186-3 (the US government statement on how to do, among other things, RSA), it has $1 = (ed) \bmod lcm(p-1,q-1)$ (see B.3.1, requirement 3). Showing that $e \cdot d \equiv 1 \bmod \lambda(N)$ is sufficient is actually fairly easy (it's mostly Chinese Remainder Theorem and Fermat's Little Theorem); to show it is necessary requires digging a bit more into the number theory. $\endgroup$ – poncho Dec 21 '12 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.