4
$\begingroup$

Given $n=pq$ for $p,q$ known, I can calculate $\phi(n)$.

$e$ is selected such that $\gcd (e,\phi(n)) = 1$.

Using this, how do I calculate the RSA private key?


Example:

I have $n = 35$, with $(p,q)=(5,7)$. I have also computed $\phi(n)=24$, and selected $e$ such that $\gcd (e,\phi(n)) = 1$ by taking $e=23$.

Calculate the private key.

$\endgroup$
4
  • 1
    $\begingroup$ Take a look at the extended Euclidean algorithm $\endgroup$
    – DrLecter
    Dec 6, 2013 at 3:21
  • $\begingroup$ I figured it out and I'll answer my question soon $\endgroup$
    – Ali Gajani
    Dec 6, 2013 at 3:25
  • 2
    $\begingroup$ This question appears to be off-topic because its scope is too local. It's unlikely that anyone else will need to calculate a key with these exact parameters. Maybe if you edited the question to make it more general... $\endgroup$
    – rath
    Dec 6, 2013 at 6:24
  • $\begingroup$ I recommend you reading Conrado's post in here, it's easier to understand than that on the Wiki $\endgroup$
    – T.B
    Dec 6, 2013 at 10:42

2 Answers 2

2
$\begingroup$

The private key $d$ of RSA algorithm with public parameters $(N,e)$ is such that:

$ed \equiv 1\mod{\phi(N)}$. Since by definition $e$ and $\phi(N)$ are coprime then with extended euclidean algorithm you can find such $d$: $ed +k\phi(N)=1$

Consider that to compute $\phi(N)$ you should know how to factor $N$ since $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$

To see why this is correct imagine an encryption of the message $m$ to be $c=m^e\mod{N}$. Then to decrypt you compute $c^d=m^{ed}\mod{N}=m \mod{N}$

$\endgroup$
2
$\begingroup$

I figured out the decent way of solving for $d$ (the private key).

I have $n=35$, with $(p,q)=(5,7)$. I have also computed $\phi(n)=24$, and selected $e$ such that $\gcd(e,\phi(n))=1$ by taking $e=23$. To calculate the private key, we need to use the formula:

$$d = e^{-1} \mod \phi(n)$$

This gives us $d = 23$, which happens to be the same as $e$, a coincidence.

$\endgroup$
4
  • 1
    $\begingroup$ These are standard techniques you can find in all books.We say the same thing.In order to compute the inverse you can use the extended euclidean algorithm $\endgroup$
    – curious
    Dec 7, 2013 at 12:09
  • 4
    $\begingroup$ Also, this isn't a much of a coincidence, because $e=23=-1\pmod{24}$ and so $e^2=(-1)^2=1\pmod {24}$. $\endgroup$ Dec 7, 2013 at 15:42
  • $\begingroup$ Can you elaborate more on what it is you're pointing out? If e=23 then $e^2$=$23^2$ and 529 mod 24 = 1 but why is it not a coincidence that d and e are both 23? In my very limited travels in cryptography, I usually don't see d and e being the same value. I'm not sure what I'm supposed to be realizing. $\endgroup$ Mar 8, 2020 at 0:17
  • 1
    $\begingroup$ The world of algebra knows no luck or coincidence. $\endgroup$
    – Quinten C
    Jan 2, 2022 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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