# RSA problem - how to find $d$ [duplicate]

For example, let $p = 3$ and $q= 11$, choose $e = 3$. What computation I have to apply in order to find the corresponding $d$? I know it's 7, but I want to know the exact process to be applied to find it.

## marked as duplicate by mikeazoAug 3 '15 at 12:49

• There are an incalculable number of threads on this site alone, let alone the whole internet, that address the process of deriving $d$ from $e$. Have you tried searching for them? Hint, there are at least two in the related questions list on the right. – Thomas Aug 3 '15 at 11:29
• This is not exactly a duplicate because the linked question does not address how $d$ is found (only which property it satisfies). I think a good answer to this question should mention the extended Euclidean algorithm. Maybe it would be a good idea to add it to the answer in the linked question... – fkraiem Aug 3 '15 at 12:34
• @fkraiem I see your point. I've now closed it as a duplicate of a different question. Let me know what you think of this one. – mikeazo Aug 3 '15 at 12:50
• @mikeazo Yes this one is excellent. – fkraiem Aug 3 '15 at 12:52
• @fkraiem thanks for pointing it out. After looking at it close, you were definitely right that the first "duplicate" wasn't good enough. – mikeazo Aug 3 '15 at 12:54

Ok, RSA is a asymmetric crypto system. Which means you have a separate key for encryption and decryption.

Remember RSA is based on cyclic groups. So don't forget the modulo.

Here are the basic equations. $n$ is the product of $p$ and $q$. $\varphi(n) = (p-1)*(q-1)$

$gcd (e, \varphi(n)) = 1$ - for calculating the e. e is random but must fit this equation.

$d = e^{-1} \bmod{\varphi(N)}$ And now you can calculate d.

Hope I could help you. But this would only take 2 minutes to google

• You had a typo in the original. You had $d=e\bmod{\varphi(N)}$ instead of $d=e^{-1}\bmod{\varphi(N)}$. I also added tex formatting. – mikeazo Aug 3 '15 at 12:06
• Also, $e$ is typically not random. Usually $e=65537$ is used. There are a few other popular choices for $e$. – mikeazo Aug 3 '15 at 12:23
• Oh thank you. According to e: Yes in real life its not random. But for learning and with small numbers it is. As long as the equation above is true. Also you would never choose three and eleven for p and q – user281874 Aug 3 '15 at 12:31
• I know what RSA is, I just don't understand how $3^{-1}\bmod{20}$ could be $7$. That's it. It's not a duplicate question because my question is focused only on finding $d$. I'm not asking what RSA is for god's sake. – pa5h1nh0 Aug 3 '15 at 12:46
• @pa5h1nh0: 3^-1 is 7. Use the extended euclidean algorithm – user281874 Aug 3 '15 at 13:11