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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Take a look at the extended Euclidean algorithm $\endgroup$ – DrLecter Dec 6 '13 at 3:21
  • $\begingroup$ I figured it out and I'll answer my question soon $\endgroup$ – Ali Gajani Dec 6 '13 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 '13 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 '13 at 10:42
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}$

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • 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 '13 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$ – Cryptographeur Dec 7 '13 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$ – harperville Mar 8 '20 at 0:17

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.