R.S.A. Encryption: find $d$ if we know $n$ and $e$

2.2k Views Asked by At

If an R.S.A. system has $n=55$ and the encryption key is 13

Do I choose $p$ and $q$ as 5 and 11 so $n = 5 \times 11$ and then $\varphi(n) = (5-1) \times (11-1) = 40$

Is this the correct start? Will that mean the public key is (13,77) and to find the decryption key $d$ I take the inverse of 13 in $\mathbb{Z}_{40}$?

1

There are 1 best solutions below

2
On BEST ANSWER

You can see another example at Computing RSA Algorithm or RSA Algorithm.

We are given (although we typically choose these randomly)

$$n = 55 \implies p = 5, q = 11$$

Note, we could also have chosen $p = 11, q = 5$.

We are given (although we can choose one that meets the criteria)

$$e = 13$$

The Extended Euclidean Algorithm takes $p, q, \mbox{and}~ e$ as input and gives $d$ as output. That is, $d$ is the modular inverse of $e$ in $Z_{40}$

$$d \equiv e^{-1} \bmod (p − 1)(q − 1)$$

This results in $$d = 37$$

You can find an Extended Euclidean Algorithm calculator here.

The public key is $(n, e) = (55, 13)$.

The private key is $(n, d) = (55, 37)$.