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

Question

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$?

So for my current question/exercise. I take any prime numbers p and q which gives me 2537 when I multiply them? Like p=43 and q=59? — user9132502, Jun 10 '19 at 01:10
Ok thanks Randall, I'm still kinda lost, but I'll try to understand it — user9132502, Jun 10 '19 at 01:12
I'm guessing because you've shown no background or efforts. It reads like a "here's my homework" problem. — Randall, Jun 10 '19 at 01:22
No it's not my homework problem trust me on this. I can't really start the exercise without knowing how to start it, I'm not asking for you guys to do it for me — user9132502, Jun 10 '19 at 04:58

score 0 · Accepted Answer · answered Jun 10 '19 at 08:17

0

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.

answered Jun 10 '19 at 08:17

Henno Brandsma

242,131

The result will be $1819$ $1415$, some encoding of the alphabet, maybe? – Henno Brandsma Jun 10 '19 at 11:14
Looks like 'STOP' to me. – Henno Brandsma Jun 10 '19 at 11:20

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

1 Answers1