Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this wikipedia article about RSA, At step 5, How are they calclulating value of $d$? Can anybody give me a step-by-step explanation?

Compute $d$, the modular multiplicative inverse of $e \pmod{\phi(n)}$ yielding $d=2753$.

share|improve this question
    
Why are you linking to an old version of the page? –  Arturo Magidin Feb 27 '12 at 22:13
    
Copy paste issue :( –  iraSenthil Feb 28 '12 at 14:11

3 Answers 3

up vote 5 down vote accepted

The most efficient way would be the Euclidean algorithm.

http://en.wikipedia.org/wiki/Euclidean_algorithm

You use the Euclidean algorithm to find $d, a$ such that $d \cdot e + a \cdot \phi(n) = 1$. Taking this mod $\phi(n)$ gives $d \cdot e \equiv 1$.

For your specific case where $\phi(n) = 3120$ and $e = 17$, you start with $3120 / 17$, which is 183 with a remainder of 9. Write this as:

$$3120 = 17 \cdot 183 + 9$$ Now, repeat this process with 17 and 9. $$17 = 9 \cdot 1 + 8$$ Now, repeat this process with 9 and 8. $$9 = 8 \cdot 1 + 1$$ Now that you have obtained 1, "solve" for 1 using back substitution, with an end goal of getting 1 as a linear combination of 3120 and 17. First, the three above equations become

$$\begin{align*} 1 &= 9 - 8 \\ 8 &= 17 - 9 \\ 9 &= 3120 - 17 \cdot 183 \end{align*}$$

So, doing back substitution gives

$$1 = 9 - 8 = 9 - (17 - 9) = 9 \cdot 2 - 17 = [3120 - 17 \cdot 183] \cdot 2 - 17 = 3120 \cdot 2 - 17 \cdot 367$$

As I said above, taking everything mod 3120 gives $$17 \cdot -367 \equiv 1$$ and since $-367 + 3120 = 2753$, we see that $-367 \equiv 2753$ mod 3120. Thus, $-367$, or $2753$ is the multiplicative inverse of 17 mod 3120.

share|improve this answer
    
Can you use this in a example? –  iraSenthil Feb 27 '12 at 22:05
    
@iraSenthil I read your question more carefully and understood you wanted to see the detail, so I added it. –  Graphth Feb 27 '12 at 22:08

You use the Extended Euclidean algorithm.

You know $\phi(n)$ (because you know $n=pq$ with $p$ and $q$ primes, so that $\phi(n)=(p-1)(q-1)$). So it is an easy matter to apply the Extended Euclidean Algorithm to $e$ and to $(p-1)(q-1)$ to obtain integers $x$ and $y$ such that $$1 = xe + y\phi(n).$$ (If $\gcd(e,\phi(n))\gt 1$, you are supposed to pick a different $e$).

The number $d$ you are looking for is the coefficient $x$ in this expression.

In the specific example given: $p=61$, $q=53$, $n=61\times 53=3233$, $\phi(n) = 60\times 52 = 3120$, and $e=17$.

Divide $\phi(n)$ by $e$ with remainder: $$3120 = 183\times {\color{magenta}{17}} + {\color{blue}9}. \tag{1}$$ Now divide ${\color{magenta}{17}}$ by the remainder ${\color{blue}9}$: $${\color{magenta}{17}} = 1\times {\color{blue}9} + {\color{red}8}.\tag{2}$$ Now divide ${\color{blue}9}$ by the remainder ${\color{red}8}$: $${\color{blue}9} = 1\times{\color{red}8} + {\color{green}1}.\tag{3}$$ This will be the last step in the Euclidean algorithm, since when you divide ${\color{red}8}$ by $\color{green}1$, you will obtain a remainder of $0$; the gcd is the last nonzero remainder.

Now backtrack to write ${\color{green}1}$ as a linear combination of $3120$ and $17$: $$\begin{align*} {\color{green}1} &= {\color{blue}9} - 1\times{\color{red}8} &\text{(by (3))}\\ &= {\color{blue}9} - 1\times({\color{magenta}{17}} - 1\times{\color{blue}9}) &\text{(by (2))}\\ &= {\color{blue}9} - {\color{magenta}{17}} + {\color{blue}9}\\ &= 2\times{\color{blue}9} - 1\times{\color{magenta}{17}}\\ &= 2\times(3120 - 183\times{\color{magenta}{17}}) - 1\times{\color{magenta}{17}}&\text{(by (1))}\\ &= 2\times 3120 - 366\times{\color{magenta}{17}} - {\color{magenta}{17}}\\ &= 2\times 3120 - 367\times{\color{magenta}{17}}. \end{align*}$$ So $d\equiv -367 \equiv 3120-367 \equiv 2753\pmod{3120}$.

share|improve this answer
    
Can you give me an example? –  iraSenthil Feb 27 '12 at 22:07
    
@iraSenthil Here is a description of one simple way to manually execute the extended Euclidean algorithm. –  Bill Dubuque Feb 28 '12 at 21:55

I spent a lot of time trying to figure out the algebra from the above answer. I personally like parenthesis. They tend to make math more clear not less clear so i am rewriting the above answer for people that have the same preference. I hope this helps some people, and great job to the person above me. It helped a lot.

Now backtrack to write 1 as a linear combination of 3120 and 17:

 1=9−1×8,
 1=9−1×(17−1×9),
 1=9+(-1)(17-9),
 1=9−17+9,
 1=2×9−17,
 1=(2x9)-(1x17),
 1=2×[3120−(183×17)]−1×17,
 1=(2)(3120)-(2)(183x17)-1x17,
 1=(2x3120)+(-2)(183x17)-1x17,
 1=(2x3120)+(-366x17)-(1x17),
 1=(2x3120)+[17(-366-1)],
 1=(2x3120)+[17x-367],
 1=(2x3120)+[-367x17],
 1=(2x3120)+(-1x367x17),
 1=(2x3120)-(1x367x17),
 1=(2x3120)-(367x17),

I know many of these parenthesis are not necessary, but I believe they make the math easier to follow. It is just my preference, and I typed this up to help the next person who has the same preference. Anyway, thanks for the above answers. They helped me a great deal.

share|improve this answer

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.