Cryptography - RSA algorithm - basic question

Question

I have just read a very basic introduction to the RSA algorithm.

Let's suppose my two prime numbers are $p=29$ and $q=37$. Then $n=pq=1073$ and $e=5$. $n$ and $e$ are public.

If I want to send the letter U, which is n°21 in the alphabet, I would send $21^e$ (mod $1073$) that is $263$.

Normally I should calculate $(21^e)^d$, where $d=605$. But why not calculate $(263)^{1/5}$ ?

The problem is that calculating $(263)^{1/5}$ is hard, when working modulo an $n$ with unknown prime factors. How would you calculate this $5$th root? — TMM, Nov 14 '12 at 16:02

score 1 · Accepted Answer · answered Nov 14 '12 at 16:02

1

Because modular exponentiation is easy. How would you calculate $263^{1/5}?$ If you could, the encryption would not be secure.

answered Nov 14 '12 at 16:02

Ross Millikan

Thanks to all of you. Is it hard or impossible ? – Tom Nov 14 '12 at 16:50
@Tom: For this case, you can just try all the numbers from $1$ to $1072$ and see which works. If there were a general answer, that would break RSA. – Ross Millikan Nov 14 '12 at 16:58

score 0 · Answer 2 · edited Jan 31 '13 at 09:32

0

You already calculated $ d= 605 \equiv 5^{-1} \equiv 1 / 5 \pmod{ \phi(n)} $ .

edited Jan 31 '13 at 09:32

Stefan Hansen

answered Jan 31 '13 at 09:15

AHH

2 Answers2