Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$

share|improve this question
add comment

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

share|improve this answer
    
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)$ –  curious Dec 20 '12 at 22:20
    
@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)$ –  poncho Dec 20 '12 at 22:24
    
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)$ –  curious Dec 20 '12 at 22:36
    
and why $gcd(e_b,V)=1$ , according to your notation where $V=e_a \cdot d_a -1$ –  curious Dec 20 '12 at 23:43
    
@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. –  poncho Dec 21 '12 at 3:03
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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