0

I will be grateful for some tips on how to bite a task like so: I need to break a RSA code. I know that public key is $n=462257, e=13$. I also have cryptogram $c=139552$. The goal is to find a number that is encrypted here. I have written some things on wikipedia about RSA, but I am brand new on this area and I don't know how to even start. What is $c$ for in this task? What steps should I take to find the answer?

George V. Williams
  • 5,213
Cris
  • 131
  • Your task is to find a number $m$, the "message," such that $m^e\equiv c$ mod $n$. – Barry Cipra Mar 29 '15 at 19:26
  • Should we assume that we don't know, and can't compute that $503×919=462257$ or can we use that? – Nathanson Mar 29 '15 at 19:29
  • I think that we can assume what you have written – Cris Mar 29 '15 at 19:29
  • I'm a bit curious. What can anyone write about RSA on wikipedia, if this is a mystery? – Jyrki Lahtonen Mar 29 '15 at 19:32
  • @JyrkiLahtonen The content of Wikipedia is supposed to come from sources. You don't have to know anything about a topic to write a whole article about it. Of course, knowing makes it easier, but not knowing is very far from being an impediment. – Nathanson Mar 29 '15 at 19:35
  • @Nathanson: Somebody here (Pete Clark?) told me that mathematical wikipedia-articles, at least those in English, have been checked by pros. If what you say is true, that does explain a few things I've seen (in my favorite tags and in Finnish :-) – Jyrki Lahtonen Mar 29 '15 at 19:43
  • 3
    @JyrkiLahtonen, I think the OP meant to say "read" instead of "written." – Barry Cipra Mar 29 '15 at 19:46
  • I hope so, @Barry. Sorry about sounding a bit. critical. – Jyrki Lahtonen Mar 29 '15 at 19:53

2 Answers2

4

Start by factoring $n = 462257 = 503 \cdot 919 $. You can calculate $\varphi(n)$ and $d$ now since you know that $d \equiv e^{-1} \pmod{\varphi(n)}$. Given $d$, you can decrypt $m$ as usual. Alternatively, use the method suggested by Barry Cipra in the comments (brute force $m^{13} \equiv 139552 \pmod{462257}$).

You should get $m = 4242$.

George V. Williams
  • 5,213
  • Just to be clear, I wasn't suggesting a "method" in my comment beneath the OP, I was just addressing the question "What is $c$ for?" – Barry Cipra Mar 29 '15 at 19:41
  • It is very hard area for me. Thank you for the answer, even if I can't understand those things when I have tips ;) – Cris Mar 29 '15 at 19:45
  • @BarryCipra, sorry for misrepresenting you, I thought that you meant to simply bruteforce all values of $m$. – George V. Williams Mar 29 '15 at 19:47
0

Doing the cycling attack for this case yields $m=4242$ after $1500$ steps in less than a second (small Python program).

Henno Brandsma
  • 242,131