Decipher the message $2081\ 2182$ knowing that it was encrypted using the RSA system with the key $(2537, 13)$

99 Views Asked by At

Decipher the message $2081 \ 2182$ knowing that it was encrypted using the RSA system with the key $(2537, 13).$

$(2537, 13)$ is a public key $(n, e)$. To decipher the message I need to find the inverse modulo of e which is d:

$$d= e^{-1} \mod (p-1)(q-1)$$

I have $n$, how can I find $p$ and $q$?

1

There are 1 best solutions below

2
On BEST ANSWER

For a realistic $n$ you cannot find the primes $p$ and $q$ from $n=pq$, that's what makes RSA secure..

This is a very small $n$ so here we can use algorithms to find $p$ and $q$ that are fast enough.

An online resource like Wolfram alpha can do it easily (you could easily write a little program to to do trial division as well), and gives $p=43$, $q=59$ as the solution. Now you try and do the rest.